” 辅导ECSE 427程序、 写作Systems编程语言、c/c++程序ECSE 427/COMP 310 Operating Systems Assignment 03 Memory AllocatorFall 2020 (version 1) Page 1 11/5/2020Simple Memory AllocatorCheck My Courses for Due DateHigh-Level DescriptionMost of your programs rely on dynamic memory allocation to implement complex data structures.By default, in Unix/Linux you use the malloc library for dynamic memory allocation. You couldinstall other libraries instead of malloc for dynamic memory allocation. In this assignment, youwill develop a library Called Simple Memory Allocator (SMA) for dynamic memory management.Because your library is working at the user-level, your library would grab memory in bulk fromthe kernel and then distribute it to the application requests as they come in. The applicationprogram is going to use the API provided by your Simple Memory Allocator to manage dynamicmemory.Here is an example program using the SMA.#include stdio.h#include sma.hint main(int argc, char *argv[]){int i;char *c[32];// Allocating 32 kbytes of memory..for(i=0; i32; i++)c[i] = (char*)sma_malloc(1024);use_memory(c);// Now deallocatingfor(i=0; i32; i++)sma_free(c[i]);puts(Print Some information..);sma_mallinfo();return(0);}In the above program, we are allocating 32 KB of memory and passing the memory block (heldby the array of pointers) to a function. After the function returns, we dont need the memory blockany further. We call the free function provided by SMA to release the memory. Notice that we arenot initializing the SMA library before using it. The library is initialized appropriately at first usein the implementation. The last SMA call (sma_mallinfo) is asking the library to print outinformation about its internal operation.More Details on SMAThe SMA library you develop is equivalent to the malloc library provided by Unix-like operatingsystems. Like the malloc library, the SMA allocates variable sized contiguous memory chunkson the heap, which is the memory segment just after the uninitialized data segment. The currentend of the heap is denoted by the program break as shown in the figure below. We use the brk()ECSE 427/COMP 310 Operating Systems Assignment 03 Memory AllocatorFall 2020 (version 1) Page 2 11/5/2020and sbrk() calls to Get memory in bulk (i.e., large chunks) from the heap. The SMA is going tohold the heap memory that it got from the OS and use it to allocate the requests from theapplication. This means the actual heap is not going to grow and shrink in direct relation toallocations and deallocations of memory by the application. The heap growth and shrinkagedepend on the SMA actions as well. For example, the application might release lot of memory, butthe SMA might still be holding it. As a result, the heap will not shrink to correspond to the memoryrelease operations.To allocate memory on the heap, we need to tell the kernel that the process program break islocated at a different address such that there is additional room in the heap. Initially, the programbreak lies just past the end of the uninitialized data segment. After the program break is increased,the program can access the memory in the newly created heap space. The brk() system call setsthe program break to the location specified by its argument. The sbrk() library routine is similarwhere an increment can be specified to increase the program break.The call sbrk(0) returns the current value of the program break without changing it. It can beuseful to track the size of the heap to monitor the behavior of the memory allocation package.Your memory allocation package needs to provide the following functions for managing the heap.void *sma_malloc(int size)ECSE 427/COMP 310 Operating Systems Assignment 03 Memory AllocatorFall 2020 (version 1) Page 3 11/5/2020This function returns void pointer that we can assign to any C pointer. If memory could not beallocated, then sma_malloc() returns NULL and sets a global error string variable given by thefollowing declaration.extern char *sma_malloc_errorThe possibility of error in memory allocation may be small, but it is important to providemechanisms to handle the error conditions.void sma_free(void *ptr)This function deallocates the block of memory pointed by the ptr argument. The ptr should bean address previously allocated by the Memory Allocation Package.In UNIX/Linux, free() does not lower the program break. It adds the block of freed memory to thefree list so it Could be recycled by future calls to malloc(). This is done for several reasons. The block being freed could be somewhere in the middle of the heap. Minimize the number of sbrk() calls that the program must perform to minimize thenumber of system calls. In many cases, lowering the program break would not help programs that allocate largeamounts of memory. Such programs tend to either hold onto the allocation for longperiods of times or repeatedly allocate and deallocate memory segments.You could consider these reasons when deciding what sma_free() should be doing. If theargument of sma_free() is NULL, then the call should not free anything. Callingsma_free() on a ptr value can lead to unpredictable results.The sma_free() should reduce the program break if the top free block is larger than 128 Kbytes.void sma_mallopt(int policy)This function specifies the memory allocation policy. You need implement two policies as part ofthis assignment: next fit and worst fit. Refer to the lecture slides for more information about thesepolicies.void sma_mallinfo()This function prints statistics about the memory allocation performed so far by the library. Youneed to include The following parameters: total number of bytes allocated, total free space, largestcontiguous free space, and others of your choice.void *sma_realloc(void *ptr, int size)This function is similar to sma_malloc(). The major difference is instead of freshly allocatingmemory, it is resizing the memory pointed by ptr, which was previously allocated bysma_malloc(). The freshly reallocated block of memory can be in a different memory areabecause the previous block could not be expanded. In this case, the library needs to copy the datafrom the old memory block to the new block.Proposed ApproachDO NOT USE malloc, calloc, or other variations offered by the operating system in thisassignment. Remember you are using lower level system calls and library routines forimplementing the memory management library. Using malloc routines will change the heapECSE 427/COMP 310 Operating Systems Assignment 03 Memory AllocatorFall 2020 (version 1) Page 4 11/5/2020configuration and destroy your setup. Some library routines like printf() also use malloc, so youneed to avoid their use as well. Use puts() and sprintf() instead of printf().The implementation of the SMA library is straightforward. It maintains a list of free memoryblocks at all times. When a memory allocation request comes in (i.e., sma_malloc() call), itwill find one of the memory blocks from this list that is suitable for the request. The suitability ofa free memory block for satisfying a request depends on the memory allocation policy that is ineffect at the allocation time. In this assignment, you are expected to support next fit and worst fit.The available Free memory blocks is due to previous deallocations via sma_free() calls. In anallocation call (i.e., sma_malloc(), we are looking for a free block that is going to satisfy therequest according to the allocation policy. If a free block is found and it is larger than the request,we would split the block and a portion is returned as the allocation while the other portion remainsin the free list. If no block is found on the free memory block list, sbrk() is used to allocate morememory. To reduce the number of calls to sbrk(), rather than allocating exactly the number ofrequired bytes, sma_malloc() increases the program break in larger units and puts the excessmemory into the free list. The excess memory cannot be more than 128 Kbytes to be consistentwith the way sma_free() works.One of the challenges is deallocating the correct number of bytes when sma_free() is called.To know the correct number of bytes to place in the free list, sma_free() gets a little help fromsma_malloc(). When sma_malloc() allocates the block, it allocates extra bytes to hold aninteger containing the size of the block. The integer is located at the beginning of the block; theaddress actually returned to the caller points to the location just past this length value, as shown inthe figure below.When a block is placed on the double linked free list, sma_free() uses a structure such as thefollowing to represent the free block. It should be noted that all the free blocks are connected in adoubly linked list while the allocated ones are not.As blocks are deallocated and reallocated over time, the blocks of the free list will becomeintermingled with the blocks of the allocated memory as shown below.ECSE 427/COMP 310 Operating Systems Assignment 03 Memory AllocatorFall 2020 (version 1) Page 5 11/5/2020When sma_free() runs, it is essential to check adjacent blocks for their status. If free blocksare next to the block being freed, you need to merge them into a larger free block. To easily detectadjacent free blocks, a Boundary-tag scheme could be implemented. The boundary tag is a slightvariation of the scheme shown above. The figure below shows an example boundary-tag scheme.You may return a slightly larger block than what is requested from sma_malloc() to reduceexternal fragmentation.What to Handin?Submit the following files separately:1. A README file that explains any design decisions the TA should be aware of whengrading your assignment.2. If you have not fully implemented all, then list the parts that work so that you can be sureto receive credit for the parts you do have working. Indicate any issues you ran into doingthis assignment. If you point out an error that you know occurs in your problem, it maylead the TA to give you More partial credit.ECSE 427/COMP 310 Operating Systems Assignment 03 Memory AllocatorFall 2020 (version 1) Page 6 11/5/20203. All source files needed to compile, run and test your code. If multiple source files arepresent, provide a Makefile for compiling them. Do not submit object or executable files.4. Output from your testing of your program.5. You need to submit the testing routine that you used to test the assignment.如有需要，请加QQ：99515681 或邮箱：99515681@qq.com
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
