Background A linked list implementation of a memory allocation system is described in the OSTEP text book, section 17.2: http:/lpages.cs.wisc.edu/remzi/OSTEP/vm-freespace.pdf A summary is described below. Use the provided figures and code snippets to complete this assignment Consider an empty heap of size 4KB (4096 bytes). To manage a free list (regions of memory not in use), a node t struct is used, which incurs a small overhead: typedef struct node t ( //size of free space in region int size; structnode t *next; //pointer to next free region node ti head size: 4088 next: the rest of the 4KB chunk If 100 bytes are requested for dynamic memory allocation, a chunk of the heap will be split from the 4088 available bytes, as shown below: size: 100 magic: 1234567 The 100 bytes now allocated IH head size: 3980 next: The free 3980 byte chunk Each of the allocated chunks of memory has its own overhead: typedef structheader t t int size: I/size of allocated space int magic: //unique identifier: NOT USED IN THIS ASSIGNMENT header ti The allocation of three chunks of memory (each with 100 usable bytes) results in the figure below: size 100 magic: 1234567 100 bytes still allocated size: 100 magic: 1234567 100 bytes still allocated (but about to be freed) 100 magic: 1234567 100-bytes still allocated head size: 3764 next: The free 3764-byte chunk When a chunk of allocated memory is to be freed, a pointer (sptr in the figure above) is used. The header_t is replaced by a node_t to represent a change from an allocated region of memory to a free one. Also note that the new node_t is the head of the free list linked list, with its struct node_t *next pointing to the other free node_t. [virtual address: 16KB] 100 magic: 1234567 100 bytes still allocated head 100 next: 16708 (now a free chunk of memory) size: 100 magic: 1234567 100-bytes still allocated size: 3764 next: The free 3764-byte chunk Finally, when multiple free regions are adjacent to each other, they can be coalesced to reduce the overhead [virtual address: 16KB] 100 16492 size (now free) size: next: 16708 (now free) head size 1000 next: 16384 (now free) size 3764 next: C0 The free 3764-byte chunk Note that in the figures above, the sizes of the header_t and node_t structs are 8 bytes each, but in 64-bit computers (including on Cloud9), the size of a pointer (i.e. memory address) is 8 bytes. In contrast, the magic number in the header t struct will be omitted. The size of the node_t struct will be 16 bytes The size of the header_t struct will be 4 bytes Instructions Write a program in C named allocator.c that simulates a dynamic memory allocation system, with the following requirements: Accept a commandline argument for the size of the heap to be simulated and use the malloc () system call to make space for the given size Give the user a menu of options * 1. malloc: Allocate memory within the heap for N bytes 2. free: Deallocate memory from the heap using relative address 3. coalesce: Detect and remove adjacent free regions 4. view: Traverse the free list and print its information as well as total overhead in bytes 5. quit: Exit the program enu options 2 and Sample Output $ ./allocator 4096 heap: 18436112, 0, size-4096 ALLOCATOR: ENTER AN OPTION 1. malloc 2. Iree 3. coalesce 4. vieiw 5. quit CHOICE: 4 Traversing linked list of free regions. . . curr: 18436112, 0, size 4080 Total overhead: free regions 1 (16 bytes per) used chunks: 0 (4 bytes per) 16 bytes ALLOCATOR: ENTER AN OPTION 1. malloc 2. Iree 3. coalesce 4. view 5. quit CHOICE: 1 ENTER THE SIZE IN BYTES: 100 ptr: 18436116, 4, size-100 Background A linked list implementation of a memory allocation system is described in the OSTEP text book, section 17.2: http:/lpages.cs.wisc.edu/remzi/OSTEP/vm-freespace.pdf A summary is described below. Use the provided figures and code snippets to complete this assignment Consider an empty heap of size 4KB (4096 bytes). To manage a free list (regions of memory not in use), a node t struct is used, which incurs a small overhead: typedef struct node t ( //size of free space in region int size; structnode t *next; //pointer to next free region node ti head size: 4088 next: the rest of the 4KB chunk If 100 bytes are requested for dynamic memory allocation, a chunk of the heap will be split from the 4088 available bytes, as shown below: size: 100 magic: 1234567 The 100 bytes now allocated IH head size: 3980 next: The free 3980 byte chunk Each of the allocated chunks of memory has its own overhead: typedef structheader t t int size: I/size of allocated space int magic: //unique identifier: NOT USED IN THIS ASSIGNMENT header ti The allocation of three chunks of memory (each with 100 usable bytes) results in the figure below: size 100 magic: 1234567 100 bytes still allocated size: 100 magic: 1234567 100 bytes still allocated (but about to be freed) 100 magic: 1234567 100-bytes still allocated head size: 3764 next: The free 3764-byte chunk When a chunk of allocated memory is to be freed, a pointer (sptr in the figure above) is used. The header_t is replaced by a node_t to represent a change from an allocated region of memory to a free one. Also note that the new node_t is the head of the free list linked list, with its struct node_t *next pointing to the other free node_t. [virtual address: 16KB] 100 magic: 1234567 100 bytes still allocated head 100 next: 16708 (now a free chunk of memory) size: 100 magic: 1234567 100-bytes still allocated size: 3764 next: The free 3764-byte chunk Finally, when multiple free regions are adjacent to each other, they can be coalesced to reduce the overhead [virtual address: 16KB] 100 16492 size (now free) size: next: 16708 (now free) head size 1000 next: 16384 (now free) size 3764 next: C0 The free 3764-byte chunk Note that in the figures above, the sizes of the header_t and node_t structs are 8 bytes each, but in 64-bit computers (including on Cloud9), the size of a pointer (i.e. memory address) is 8 bytes. In contrast, the magic number in the header t struct will be omitted. The size of the node_t struct will be 16 bytes The size of the header_t struct will be 4 bytes Instructions Write a program in C named allocator.c that simulates a dynamic memory allocation system, with the following requirements: Accept a commandline argument for the size of the heap to be simulated and use the malloc () system call to make space for the given size Give the user a menu of options * 1. malloc: Allocate memory within the heap for N bytes 2. free: Deallocate memory from the heap using relative address 3. coalesce: Detect and remove adjacent free regions 4. view: Traverse the free list and print its information as well as total overhead in bytes 5. quit: Exit the program enu options 2 and Sample Output $ ./allocator 4096 heap: 18436112, 0, size-4096 ALLOCATOR: ENTER AN OPTION 1. malloc 2. Iree 3. coalesce 4. vieiw 5. quit CHOICE: 4 Traversing linked list of free regions. . . curr: 18436112, 0, size 4080 Total overhead: free regions 1 (16 bytes per) used chunks: 0 (4 bytes per) 16 bytes ALLOCATOR: ENTER AN OPTION 1. malloc 2. Iree 3. coalesce 4. view 5. quit CHOICE: 1 ENTER THE SIZE IN BYTES: 100 ptr: 18436116, 4, size-100