Problem Description Write a C++ program that emulate the operating system’s resp
ID: 674227 • Letter: P
Question
Problem Description
Write a C++ program that emulate the operating system’s 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 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
Explanation / Answer
#include <iostream>
#include <string>
#include <stdlib.h>
#include <iomanip>
using namespace std;
/* Function Prototypes */
void bestFit();
void worstFit();
void displayMenu();
void initPage(struct page *head, string programName);
void addPage(struct page *head, string programName);
bool deletePage(struct page **head, page *pageDelete);
void deleteEnd(struct page *head);
void outputMemory(struct page *head, struct page *head2);
void allocateFree(struct page **head, page *pagetoFree);
countFragments(struct page *head);
void countFragments(struct page *head, struct page *head2);
int kbtoPages(int kb);
int listLength(struct page *head);
void writeToUsed(page *startNode, int numPages, string pgrmName);
struct page *usedLargest(struct page *head, int &lrgstFree
struct page *usedSmallest(struct page *head, int &smlstFree, int minimumSize);
struct page *searchPage(struct page *head, string programName);
bool inMemory(struct page *head, string programName);
// Memory Page Structure:
struct page{
string programName;
page *nextPage;
};
int main(int argc, char *argv[])
{
if(argc != 2)
{
cout << "Wrong Number of Arguments!" << endl;
return -1;
}
else if(string(argv[1]) == "worst")
{
worstFit();
}
else if(string(argv[1]) == "best")
{
bestFit();
}
else
{
cout << "Unrecognized Parameter!" << endl;
return -1;
}
return 0;
}
void bestFit()
{
int userChoice = 0;
int programSize;
int pagesUsed = 0;
int pageDeleteCounter = 0;
int smallestFreePages = 0;
string pName;
struct page *freeMemory = new page;
struct page *usedMemory = new page;
for(int counter = 1; counter <= 32; counter++)
{
addPage(freeMemory, "Free");
}
// Output User Menu
cout << "Using the Best Fit Algorithm" << endl;
cout << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
while(userChoice != 5)
{
switch (userChoice)
{
default:
{
cout << "Sorry, Unrecognized Input!" << endl;
cout << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
break;
}
case 1:
{
if(listLength(usedMemory) == 0)
{
cout << "Enter the Program Name: ";
cin >> pName;
cout << "Program Size (KB): ";
cin >> programSize;
programSize = kbtoPages(programSize);
if (pagesUsed + programSize <= 32 && !inMemory(usedMemory, pName))
{
if (listLength(freeMemory) >= programSize) {
pagesUsed = pagesUsed + programSize;
for (int counter = 1; counter <= programSize; counter++) {
addPage(usedMemory, pName);
deleteEnd(freeMemory);
}
// Success Output
cout << "Program " << pName << " Successfully Added! ("
<< programSize << " Page(s) Used)" << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
}
else{
cout << "Error, Not Enough Memory to Add " << pName << "!" << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
}
}
else if(pagesUsed + programSize > 32){
cout << "Error, Not Enough Memory to Add " << pName << "!" << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
}
else if(inMemory(usedMemory, pName)){
cout << "Error, Program " << pName << " is Already in Memory!" << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
}
else{
cout << "Unknown Error!" << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
}
}
else if(listLength(usedMemory) != 0){
cout << "Enter the Program Name: ";
cin >> pName;
cout << "Program Size (KB): ";
cin >> programSize;
programSize = kbtoPages(programSize);
page *startingBlock = usedSmallest(usedMemory, smallestFreePages, programSize);
if(startingBlock != NULL && smallestFreePages != 0) {
if (smallestFreePages >= programSize) {
pagesUsed = pagesUsed + programSize;
writeToUsed(startingBlock, programSize, pName);
// Success Output
cout << "Program " << pName << " Successfully Added! ("
<< programSize << " Page(s) Used)" << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
}
else if(smallestFreePages < programSize){
cout << "Error, Not Enough Memory to Add " << pName << "!" << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
}
smallestFreePages = 0;
}
else if(startingBlock == NULL || smallestFreePages == 0){
if (pagesUsed + programSize <= 32 && !inMemory(usedMemory, pName)) {
if (listLength(freeMemory) >= programSize) {
// Updating the Number of Pages Used
pagesUsed = pagesUsed + programSize;
for (int counter = 1; counter <= programSize; counter++) {
addPage(usedMemory, pName);
deleteEnd(freeMemory);
}
cout << "Program " << pName << " Successfully Added! ("
<< programSize << " Page(s) Used)" << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
}
else{
cout << "Error, Not Enough Memory to Add " << pName << "!" << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
}
}
else if(pagesUsed + programSize > 32){
cout << "Error, Not Enough Memory to Add " << pName << "!" << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
}
else if(inMemory(usedMemory, pName)){
cout << "Error, Program " << pName << " is Already in Memory!" << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
}
else{
cout << "Unknown Error!" << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
}
}
}
break;
}
case 2: {
cout << "Enter the Program Name: ";
cin >> pName;
if (!inMemory(usedMemory, pName)) {
cout << "Program " << pName << " is not in Memory!" << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
}
else if (inMemory(usedMemory, pName)) {
while (inMemory(usedMemory, pName)) {
page *pageInMemory = searchPage(usedMemory, pName);
allocateFree(&usedMemory, pageInMemory);
pagesUsed--;
pageDeleteCounter++;
}
cout << "Program " << pName << " Killed Successfully! (" << pageDeleteCounter << " page(s) freed)" << endl;
pageDeleteCounter = 0;
displayMenu();
cout << "Option: ";
cin >> userChoice;
}
else {
cout << "Unknown Error!" << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
}
break;
}
case 3:{
if(listLength(freeMemory) == 32){
cout << "There is No Fragmentation" << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
break;
}
else {
countFragments(usedMemory, freeMemory);
cout << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
break;
}
}
case 4: {
outputMemory(usedMemory, freeMemory);
cout << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
break;
}
// Exit Program
case 5: {
exit(0);
break;
}
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.