CMPT 201 - Winter 2021, Assignment 2 Due: Friday March 19​th​, 2021, 11:00 pm. Weight: 12% of your final mark Work type: Individual assignment Objective Your assignment is to implement a dynamic...

C language


CMPT 201 - Winter 2021, Assignment 2 Due: Friday March 19​th​, 2021, 11:00 pm. Weight: 12% of your final mark Work type: Individual assignment Objective Your assignment is to implement a dynamic memory manager module and use it to allocate and free memory regions. Milestones This assignment has two milestones which are to be met: ● Milestone 1: o Finish the quiz on Blackboard​ Due: Friday February 26​th​, 11:00 PM​. ● Milestone 2: o You must have the implementation of the ​initializeMemory and ​myMalloc function working and submit it using e-submit. In the same file, write a main function that calls your functions with a few values and prints the return value to stdin. Name the file ​A2M2.c. ​and upload it to ​eSubmit​.​ Due: Friday March 5​th​, 11:00 PM​. Memory manager: "The essential requirement of memory manager is to provide ways to dynamically allocate portions of memory to programs at their request, and free it for reuse when no longer needed." [​https://en.wikipedia.org/wiki/Memory_management​]. For more information on memory managers please read: "​A memory allocator​", by Doug Lea. "​A Malloc Tutorial​" by Marwan Burelle, is also very informative, but it does not use the most eloquent English ​? ​. For this assignment you will create a memory manager for a simulated memory of 64 Kb. Note that some of those bytes will be used for metadata, so your memory manager in reality will be only able to allocate less than those 64 Kb. The two main functions are ​myMalloc ​and​ myFree. myMalloc ​allocates a contiguous block of bytes from the simulated memory and returns a reference to the first byte in the block. myFree ​takes a reference to a contiguous block of bytes (previously returned by ​myMalloc​) and frees it. In general: ● Memory addresses and sizes are represented in 2 bytes (16 bits) and are aligned at four bytes. This means that all memory addresses and sizes are multiples of 4. ● NOTE: ​Since all memory chunks are aligned at 4 bytes, the last bit of the size will be used as a status flag to indicate if the chunk is in use or free: 1 represents in use and 0 free. ● A chunk of memory will need to store some metadata. ● A used chunk will need to store its size as metadata (in addition to actual user data). A used chunk will consist of: o Fsize – the size of the chunk of memory. It is 4 bytes more than the size of the user data space. It occupies the first two bytes of the chunk. o user data space​ – used for storage o Esize – the size of the chunk of memory. It occupies the last two bytes of the chunk. Esize is a duplicate of Fsize, needed to mark the end of a chunk. https://en.wikipedia.org/wiki/Memory_management http://gee.cs.oswego.edu/dl/html/malloc.html https://wiki-prog.infoprepa.epita.fr/images/0/04/Malloc_tutorial.pdf https://wiki-prog.infoprepa.epita.fr/images/0/04/Malloc_tutorial.pdf ● We need to keep track of free chunks. We will maintain a circular double linked list for that purpose. The forward link to the first free chunk will be saved in the first two bytes of memory and the backward link to the last free chunk will be saved in the second two bytes of memory. Think of those four bytes as the ​header​ of the memory. The free chunks are sorted in order of address value. ● A free chunk will store only metadata. A free chunk will consist of: o Fsize – the size of the chunk of memory. It is 4 bytes more than the size of the user data space. It occupies the first two bytes of the chunk. o FW – forward link to the next free chunk in the circular double linked list. It occupies the third and fourth bytes of the chunk. o BW – backward link to the previous free chunk in the circular double linked list. It occupies the fifth and sixth bytes of the chunk. o Esize – the size of the chunk of memory. It occupies the last two bytes of the chunk. Esize is a duplicate of Fsize, needed to mark the end of a chunk. o Each of ​Fsize​, ​FW​, ​BW (and ​Esize​) occupies 2 bytes. Therefore, ​Esize will be stored Fsize-2 bytes after the start of the chunk (i.e. if the chunk starts at address ​a​, then ​Esize is stored at address ​a+Fsize-2​). ● Notice that a free chunk does not store user data and a used chunk does not store forward and backward links. ● Initially memory is made of a single free chunk of size 65532 bytes (including the bytes for ​Fsize and Esize​). The header will consist of forward and backward links that refer to each other (an empty circular double linked list). ● Allocation involves scanning the circular double linked list from the beginning until you find a contiguous block of free bytes and returning the (relative) address of the user data space to the user. ● If no chunk of the exact requested size is available, you scan the circular double linked list from the beginning until you find a chunk that is big enough to accommodate the user request. The free chunk is now divided into a chunk of requested size and a left-over free chunk. ● When a memory region is freed, first its neighbors are checked and if they are free too, the regions are coalesced into a larger region. The resulting region is inserted into the circular double linked list such that the order is maintained. Specification for the memory manager module: You must make and justify any important design decisions for your implementation, based on the following important requirements: ● memManager.h is given to supply your module with a common public interface. You must have these functions written to spec. This way we can link your module with our own test program. You may add whatever other functions you need to this module, but it must run under these conditions. ● memManager.c ​contains your implementation of the memory manager ● We will test your memory manager implementation under the assumption that it can handle any number of entries (if memory is available). ● You must implement the memory manager, test it appropriately, and then report your effort in a test report (see below). Test your programs extensively; including automated rules for your tests (we want to run the same tests that you have!). ● Your makefile must include a rule so that ​make test ​runs the test program. The test program must perform a series of allocations and frees by calling the functions ​myMalloc and ​myFree​. This series