Problem Description

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.

Details

1. (Data Structures:) You are required to implement a linked-list data structure to represent 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.

Example Run

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 memory5. 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

Hints

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.

Submission Guide-lines

1. You must finish this assignment with your individual effort. Your C++ source code file MUST be named as pa2.cpp and C++ header/class file should be named as pa2.h. Both pa2.h and pa2.cpp are required to be submitted for this assignment.
2. Please test your program via g++ compiler (i.e., g++ -std=c++11 -Wall) on the CISE machines to make sure it runs correctly. All source code must be able to run on C++11.
3. You must use a Linked List for this assignment.
4. Please upload the source code file(s) to CANVAS system as the attachment(s). Please submit the source code file(s) ONLY. NO need to compress the source code file(s) if the size is small.
5. Make sure you submit your assignment BEFORE the deadline. Late submission will NOT be graded !!

Grading Criteria

1. Successful Compilation (30%): Your source code should be able to compile using g++ -std=c++11 -Wall command without any error or warning. The output should be a valid executable. See lab tutorial for the commends. Please note that we will be using g++ compiler on Linux to grade your programs. If you are using other compilers or IDE (e.g., Visual C++), it is recommended that you test the source codes with g++ before the CANVAS submission (i.e., make sure there is no warning).
2. Program Correctness (40%): The executable should be able to run correctly by giving out the required output.
3. Programming Style (30%): Good coding style is a key to efficient programming. We encourage you to write clear and readable codes. You should adopt a sensible set of coding conventions, including proper indentation, necessary comments and more. Here are some guidelines of good programming style: http://en.wikipedia.org/wiki/Programmingstyle

Final Notes

1. AGAIN, remember to start the programming assignments as soon as possible. Unlike the conventional assignments, programming assignments sometimes take un-predictable amount of time to finish. Thus, have the code running first, then polish it later with the extra time before the deadline.
2. Remember you should always write your own code and never copy-and-paste from other students work or other sources. There are indeed many tools (like Stanford Moss) to detect the code similarity.
3. Programming assignments are usually designed by TAs. If you have any question or concern, please feel free to contact TAs. Our goal is to let you experience the fundamentals of computer science. If you like the programming experience, you are one of us !!
4. HAPPY CODING and GOOD LUCK !!