Memory Management

The goal of this lab is to write a simple memory manager based on the topics covered in class. This lab has two parts. (This assignment is worth 2 labs)

1. (75%) Write a memory manager that supports contiguous memory allocation. Implement both first-fit and best-fit policies in your memory manager. For simplicity, assume that processes do not grow or shrink, and that no compaction is performed by the memory manager. You should consider the following issues while designing your memory manager:
   • Efficiency of your search algorithms: Both first-fit and best-fit will require you to search for an appropriate hole to accommodate the new process. You should pay careful attention to your data structures and search algorithms. For instance, keeping the list of holes sorted by size and using binary search to search for a hole might improve efficiency of your best-fit algorithms. We do not require you to use a specific algorithm/data structure to implement best-fit and first-fit; you have the flexibility of using any search algorithm/data structure that is efficient. Try to have a design that is more efficient than a brute-force linear search through an unsorted list of holes. Similarly, use an efficient search algorithm when deallocating a process from the processList. Explain all design decisions, the data structures and search algorithms used clearly in a README file.
   • Free block coalescing: When a process terminates, the memory allocated to that process is returned to the list of holes. You should take care to combine (coalesce) holes that are adjacent to each other and form an larger contiguous hole. This will reduce the degree of fragmentation incurred by your memory manager
2. (25%) Implement compaction in your memory manager. It is sufficient to implement compaction for the best-fit policy. Your memory manager should compact memory every time it sees external fragmentation (this will occur when a new process asks for memory and your memory manager is unable to allocate it due to fragmentation). A simple compaction policy that moves all currently running processes to the start of main memory and creating one hole at the high region of memory will get you full credit

Data structures

Your memory manager class should maintain two lists: a holeList and a processList The holeList is a list of holes, with the start location and size of each hole. The processList is the list of currently active process containing the process Id, the start location and size of each process. You are free to use any data structures (arrays, linked list, doubly linked list, etc) to implement these lists. This decision will also affect the use of search algorithms to search through these lists.

Input file

You program should take input from a input file and perform actions specified in the file, while printing out the result of each action. The format of the input file is as follows:

C++ Language

class Memory Manager public: Memory Manager(int bytes, int policy) { // intialize memory with these many bytes. // Use first-fit if policy-re, best-fit if policy - 1 int allocate(int bytes, int pid) { // allocate these many bytes to the process with this id Il assume that each pid is unique to a process // return 1 if successful // return -1 if unsuccessful; print an error indicating // whether there wasn't sufficient memory or whether // there you ran into external fragmentation int deallocate(int pid) { //deallocate memory allocated to this process // return 1 if successful, -1 otherwise with an error message void printMemoryState() { // print out current state of memory // Example: Il Memory size = 1024 bytes, allocated bytes = 24, free - 1989 // There are currently 19 holes and 3 active process Hole list: 1/ hole 1: start location - e, size = 282 // Process list: Il processid=34, start location 203, size 35 1 . memorySize policy A size pid Dpid initialize memory to this size and use this policy // allocate so much memory to this process // deallocate memory for this process // print current state of memory An actual file may look as follows 8192 1 A 234 1 A 458 2 A 30 3 D1 A 898 4 D 3 70 5 class Memory Manager public: Memory Manager(int bytes, int policy) { // intialize memory with these many bytes. // Use first-fit if policy-re, best-fit if policy - 1 int allocate(int bytes, int pid) { // allocate these many bytes to the process with this id Il assume that each pid is unique to a process // return 1 if successful // return -1 if unsuccessful; print an error indicating // whether there wasn't sufficient memory or whether // there you ran into external fragmentation int deallocate(int pid) { //deallocate memory allocated to this process // return 1 if successful, -1 otherwise with an error message void printMemoryState() { // print out current state of memory // Example: Il Memory size = 1024 bytes, allocated bytes = 24, free - 1989 // There are currently 19 holes and 3 active process Hole list: 1/ hole 1: start location - e, size = 282 // Process list: Il processid=34, start location 203, size 35 1 . memorySize policy A size pid Dpid initialize memory to this size and use this policy // allocate so much memory to this process // deallocate memory for this process // print current state of memory An actual file may look as follows 8192 1 A 234 1 A 458 2 A 30 3 D1 A 898 4 D 3 70 5