Title: Memory Allocation Homework

The input will be a series of lines of data. The two kinds of requests will be

allocation requests and release requests. Each allocation will request a block

of memory with a size and an id number to identify the request.

A release request will specify the id of the allocation request and ask to release

that block of memory. Simulate the four memory allocation schemes on at least

10 requests. You choose the memory size and units for your simulation.

The system manages the memory as a list of memory blocks, stored in a data structure that you find appropriate.. As memory is allocated and released, the list of blocks in the memory map changes.

In this homework project, we address the various ways in which memory can be allocated (based on different schemes - Best Fit, First Fit, Next Fit, Worst (Largest) Fit). In addition, we also develop a method to manage the release of memory blocks by processes.

Implement the following five methods:

bestFitAllocate:

This method allocates memory according to the Best Fit scheme. The method is given the process id of the requesting process, size of the memory being requested, and the memory map. It finds the candidate memory blocks that can be allocated, and chooses the one whose size is closest to the requested size. If the free block found is exactly of the same size as the requested size, the method returns a pointer to this memory block. If the free block found is larger than the requested size, the block is split into two pieces - the first piece allocated and the second piece becoming a free block in the memory map. Thus, the method may alter the memory map appropriately. Note that if there is no free block of memory (in the memory map) that is at least as large as the requested size, the method returns null.

firstFitAllocate:

This method allocates memory according to the First Fit scheme. The method is given the process id of the requesting process, size of the memory being requested, and the memory map. It finds the first (lowest starting address) free memory block whose size is at least as large as the requested size. If the free block found is exactly of the same size as the requested size, the method returns a pointer to this memory block. If the free block found is larger than the requested size, the block is split into two pieces - the first piece allocated and the second piece becoming a free block in the memory map. Thus, the method may alter the memory map appropriately. Note that if there is no free block of memory (in the memory map) that is at least as large as the requested size, the method returns null.

worstFitAllocate:

This method allocates memory according to the Worst Fit scheme. The method is given the process id of the requesting process, size of the memory being requested, and the memory map. It finds the candidate memory blocks that can be allocated, and chooses the largest among these blocks. If the free block found is exactly of the same size as the requested size, the method returns a pointer to this memory block. If the free block found is larger than the requested size, the block is split into two pieces - the first piece allocated and the second piece becoming a free block in the memory map. Thus, the method may alter the memory map appropriately. Note that if there is no free block of memory (in the memory map) that is at least as large as the requested size, the method returns null.

nextFitAllocate:

This method allocates memory according to the Next Fit scheme. The method is given the process id of the requesting process, size of the memory being requested, the memory map, and the address of the last block allocated. It finds the first (lowest starting address) free memory block, beyond the previously allocated block address, whose size is at least as the requested size. If the free block found is exactly of the same size as the requested size, the method returns a pointer to this memory block. If the free block found is larger than the requested size, the block is split into two pieces - the first piece allocated and the second piece becoming a free block in the memory map. Thus, the method may alter the memory map appropriately. Note that if there is no free block of memory (in the memory map) that is at least as large as the requested size, the method returns null.

releaseMemory:

This method releases a memory block. Accordingly, it modifies the memory map passed in. Specifically, it marks the released block of memory as free and then it merges that block with adjacent free blocks if any. That is, if the memory block adjacent to the newly released block is free, the memory map is altered to reduce the number of memory blocks by one and the ending address (and the size) of the previous free block extended. Note that the method does not have any explicit return value and instead modifies the memory map passed in.

Be sure to test your program with enough allocates and releases to make it interesting. Hand in the program and sampl