Write a C++ program that emulate the operating systems responsibility of allocating memory to certain programs. This will be a very simple page-based view of memory management. On startup, your program will have some 32 pages of contiguous, unused memory. Each page will be 4 KB long.
It should then allow the users (i.e., your TAs) to run programs that require chunks of this memory for some period of time. It should also allow the users to kill programs (i.e., Ctrl-c or kill -9 in most OSs) that are in progress. The pages used by programs that are killed can then be re-used for future programs.
The purpose of this project is two-fold. First, you need to get practice with linked lists and pointers. Secondly, you should examine critically the results of different algorithms of allocating memory on the fragmentation of the memory.
1. (Data Structures:) You are required to implement a linked-list data structure to repre- sent the memory of the operating system. It is suggested that each node of the linked list should represent some chunk (page) of memory.
2. One strong suggestion is to use 2 linked lists in your program: one to maintain the free space and one to maintain the used space. Initially, the free space contains a single node representing the entire memory. The used list is then empty. When a program is added, you then have to split the node in the free list and add a new node to your used list.
3. Another way: Every node in your list is a page of memory with a given sequence number (Page 0 Page 1 Page 2, etc). So, when your program starts, your free list should contain all 32 pages in sequence. As more programs are added, the pages move from the free list into the used list. Note that the order of the lists must be maintained! [Note: This approach works OK for small memory size, but it will have scalability issue when the main memory is reaching gigabyte range (e.g., 1GB/4KB = 250,000 page-nodes)]
4. (Algorithms:) When your OS/MM program is launched, it needs to decide which algorithm to allocate the contiguous memory for programs. To solve this issue, you are required to implement the best-fit and worst-fit algorithms when choosing pages.
5. When a program is killed, your OS needs to reclaim that memory. This means that you will need to add the memory used by that program to your free list. Note that if there is free memory immediately adjacent to this memory, you may need to combine them.
6. (Computation:) At any given point, the users should be able to query your OS to get the number of fragments in memory. You will also certainly want some way of printing out your memory to the screen to ease the debugging process.
Try to keep your output as close to the given format as possible:
> ./a.out worst
Using worst fit algorithm
1. Add program
2. Kill program
3. Fragmentation
4. Print memory
5. Exit
choice - 1
Program name - P1
Program size (KB) - 8
Program P1 added successfully: 2 page(s) used.
choice - 1
Program name - P2
Program size (KB) - 7
Program P2 added successfully: 2 page(s) used.
choice - 1
Program name - P3
Program size (KB) - 9
Program P3 added successfully: 3 page(s) used.
choice - 3
There are 1 fragment(s).
choice - 4
P1 P1 P2 P2 P3 P3 P3 Free
Free Free Free Free Free Free Free Free
Free Free Free Free Free Free Free Free
Free Free Free Free Free Free Free Free
choice - 2
Program name - P2
Program P2 successfully killed, 2 page(s) reclaimed.
choice - 3
There are 2 fragment(s).
choice - 4
P1 P1 Free Free P3 P3 P3 Free
Free Free Free Free Free Free Free Free
Free Free Free Free Free Free Free Free
Free Free Free Free Free Free Free Free
choice - 1
Program name - P4
Program size (KB) - 3
Program P4 added successfully, 1 page(s) used.
choice - 4
P1 P1 Free Free P3 P3 P3 P4
Free Free Free Free Free Free Free Free
Free Free Free Free Free Free Free Free
Free Free Free Free Free Free Free Free
choice - 1
Program Name - P1
Program Size (KB) - 5
Error, Program P1 already running.
choice - 1
Program name - P5
Program size (KB) - 1000000
Error, Not enough memory for Program P5
choice - 5
1. You should get your linked list data structure working well before you try to move on to the memory management part. The memory management will inevitably just make use of certain methods in your linked list class.
2. Be wary of bad user input. Think about many test cases when the users could mess up (reasonably).
3. The TAs will perform at least two runs. One run is for the best-fit algorithm, and the other is for the worst-fit algorithm. The fragmentation can be different when different algorithms are used for the same add/kill-scenario.