Page Problem Description Write the C++ programs that emulate the operating syste
ID: 3729006 • Letter: P
Question
Page Problem Description Write the C++ programs 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 sequenoe. 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)] MacBook Pro 80 #3 DiIl F8 Do FS #6 10Explanation / Answer
CODE
#include <iostream>
#include <iomanip>
#include "List.h"
using namespace std;
void init();
void add(string, int);
void remove(string);
void print();
void fSpace_memory(int);
void menu();
void action();
int fSpace_memory();
const int ADD_PROGRAM = 1,
KILL_PROGRAM = 2,
FRAGMENTATION = 3,
PRINT_MEMORY = 4,
EXIT = 5,
PAGES = 32,
PAGE_SIZE = 4;
int ch = 0;
bool worstFit = false;
bool bestFit = false;
LinkedList * freeMemory;
LinkedList * usedMemory;
Node * free_Chunks;
int main(int argc, char ** argv)
{
init();
string fit = "Best";
cout << fit;
if (fit == "Best")
{
bestFit = true;
}
else
{
worstFit = true;
}
do
{
menu();
action();
} while (ch != EXIT);
return 0;
}
void menu()
{
string fit;
if (bestFit)
{
fit = "Best";
}
else
{
fit = "worst";
}
cout << "Using " << fit << " fit algorithm "
<< " 1. Add Program "
<< " 2. Kill Program "
<< " 3. Fragmentation "
<< " 4. Print memory "
<< " 5. Exit " << endl;
}
void action()
{
cout << "choice - ";
cin >> ch;
if (ch > 5)
{
cout << "There is only 5 options. Choose 1-5." << endl;
}
else
{
switch (ch)
{
case ADD_PROGRAM:
{
cout << "Program name - ";
string pName;
cin >> pName;
cout << "Program size (KB) - ";
int size;
cin >> size;
int maxSize = freeMemory->getmaximumVal();
if (size > maxSize*PAGE_SIZE)
{
cout << " Error, not enough memory for Program " << pName << " ";
}
else
{
add(pName, size);
cout << " Program " << pName<< " added successfully. ";
}
break;
}
case KILL_PROGRAM:
{
cout << "Program name - ";
string pName;
cin >> pName;
if (usedMemory->contains(pName))
{
remove(pName);
cout << " Program " << pName<< " successfully killed. ";
}
else
{
cout << " There is no program with that name. ";
}
break;
}
case FRAGMENTATION:
{
int fragments = freeMemory->size();
cout << " There are " << fragments << " fragment(s). ";
break;
}
case PRINT_MEMORY:
{
cout << ' ';
print();
cout << ' ';
break;
}
case EXIT:
{
}
}
}
}
void remove(string n)
{
if (usedMemory->contains(n))
{
usedMemory->transfer(freeMemory, n);
Node *temp = freeMemory->get(n);
temp->name = "FREE";
int pos = temp->pos;
fSpace_memory(pos);
}
}
void fSpace_memory(int x)
{
int pos = x - 1;
while (freeMemory->contains(pos) && pos != 0)
{
Node * ptr = freeMemory->getAt(pos);
int data1 = freeMemory->getDataAtpos(pos + 1);
int data2 = freeMemory->getDataAtpos(pos);
int data = data1 + data2;
ptr->val = data;
freeMemory->removeAt(pos + 1);
freeMemory->posdecrement(pos + 2);
usedMemory->posdecrement(pos + 2);
pos--;
}
pos += 2;
int maxPos = free_Chunks->pos + 1;
while (freeMemory->contains(pos) && pos != maxPos)
{
Node * ptr = freeMemory->getAt(pos - 1);
int data1 = freeMemory->getDataAtpos(pos - 1);
int data2 = freeMemory->getDataAtpos(pos);
int data = data1 + data2;
ptr->val = data;
freeMemory->removeAt(pos);
freeMemory->posdecrement(pos + 1);
usedMemory->posdecrement(pos + 1);
}
}
void init()
{
freeMemory = new LinkedList;
usedMemory = new LinkedList;
freeMemory->insert(PAGES, "FREE");
free_Chunks = freeMemory->get("FREE");
free_Chunks->pos = 1;
}
void add(string n, int size)
{
int pages;
if (size%PAGE_SIZE == 0)
{
pages = size / PAGE_SIZE;
}
else
{
pages = size / PAGE_SIZE + 1;
}
if (worstFit)
{
int memorySize = 0;
int memoryAt = 0;
Node * pos = freeMemory->head;
if (memorySize < pos->val)
{
memorySize = pos->val;
memoryAt = pos->pos;
}
while (pos->next != NULL)
{
if (memorySize< pos->next->val)
{
memorySize = pos->next->val;
memoryAt = pos->next->pos;
}
pos = pos->next;
}
freeMemory->splitAt(memoryAt, pages, n);
Node * temp = freeMemory->get(n);
freeMemory->posincrement(memoryAt);
usedMemory->posincrement(memoryAt);
temp->pos = memoryAt;
freeMemory->transfer(usedMemory, n);
}
else if (bestFit)
{
int memorySize = 0;
int memoryAt = 0;
Node * pos = freeMemory->head;
if (pos->val >= pages)
{
memorySize = pos->val;
memoryAt = pos->pos;
}
while (pos->next != NULL)
{
int tempval = pos->next->val;
if (tempval> = pages && tempval < memorySize)
{
memorySize = pos->next->val;
memoryAt = pos->next->pos;
}
pos = pos->next;
}
freeMemory->splitAt(memoryAt, pages, n);
Node * temp = freeMemory->get(n);
freeMemory->posincrement(memoryAt);
usedMemory->posincrement(memoryAt);
temp->pos = memoryAt;
freeMemory->transfer(usedMemory, n);
}
}
void print()
{
int c = 0;
int m1 = usedMemory->getmaximumPos();
int m2 = freeMemory->getmaximumPos();
int maxpos = 0;
if (m1 < m2)
{
maxpos = m2;
}
else
{
maxpos = m1;
}
for (int i = 1; i <= maxpos; i++)
{
if (usedMemory->getDataAtpos(i) != -1)
{
int temp = usedMemory->getDataAtpos(i);
string name = usedMemory->getNameAtpos(i);
while (temp> = 1)
{
cout << name << " ";
temp--;
c++;
if (c >= 8)
{
c = 0;
cout << endl;
}
}
}
else
{
int temp = freeMemory->getDataAtpos(i);
string name = freeMemory->getNameAtpos(i);
while (temp> = 1)
{
cout << name << " ";
temp--;
c++;
if (c >= 8)
{
c = 0;
cout << endl;
}
}
}
}
}
List.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <iostream>
#include<string>
using namespace std;
class Node
{
public:
int pos;
string name;
int val;
Node *next;
void insert(int val);
void insert(int val, string n);
void add(Node n);
Node(int val);
Node();
};
class LinkedList
{
public:
Node *head;
int size();
void insert(int val);
void insert(int val, string n);
void add(Node n);
Node * get(string n);
Node * getAt(int n);
int getmaximumPos();
int getmaximumVal();
Node getCopy(string n);
void transfer(LinkedList *b, string n);
void remove(int val);
void remove(string n);
void removeAt(int pos);
bool contains(string n);
bool contains(int n);
void printList();
void splitHead(int x, string n);
void splitAt(int pos, int amount, string name);
int getDataAtpos(int x);
string getNameAtpos(int x);
void posincrement(int x);
void posdecrement(int x);
};
#endif
Node::Node()
{
val = 0;
}
Node::Node(int val)
{
this->val = val;
next = NULL;
}
void Node::insert(int val)
{
if (next == NULL)
{
next = new Node(val);
return;
}
next->insert(val);
}
void Node::insert(int val, string num)
{
if (next == NULL)
{
next = new Node(val);
name = num;
return;
}
next->insert(val, num);
}
void Node::add(Node num)
{
if (next == NULL)
{
next = new Node;
*next = num;
next->next = NULL;
return;
}
next->add(num);
}
int LinkedList::size()
{
int s = 0;
Node *pos;
pos = head;
while (pos != NULL)
{
s++;
pos = pos->next;
}
return s;
}
int LinkedList::getmaximumPos()
{
int maximum = 0;
Node *pos;
pos = head;
while (pos != NULL)
{
if (pos->pos > maximum)
{
maximum = pos->pos;
}
pos = pos->next;
}
return maximum;
}
int LinkedList::getmaximumVal()
{
int val = 0;
Node *pos;
pos = head;
while (pos != NULL)
{
if (pos->val > val)
{
val = pos->val;
}
pos = pos->next;
}
return val;
}
void LinkedList::posincrement(int x)
{
Node *pos;
pos = head;
while (pos != NULL)
{
if (pos->pos >= x)
{
pos->pos++;
}
pos = pos->next;
}
}
void LinkedList::posdecrement(int x) {
Node *pos;
pos = head;
while (pos != NULL) {
if (pos->pos >= x) {
pos->pos--;
}
pos = pos->next;
}
}
void LinkedList::insert(int val)
{
if (head == NULL)
{
head = new Node(val);
return;
}
head->insert(val);
}
void LinkedList::insert(int val, string n)
{
if (head == NULL)
{
head = new Node(val);
head->name = n;
return;
}
head->insert(val, n);
}
void LinkedList::remove(int val)
{
Node *pos = new Node;
pos = head;
if (pos->val == val)
{
Node *temp = pos->next;
delete head;
head = temp;
return;
}
while (pos->next != NULL)
{
if (pos->next->val == val)
{
Node *temp = pos->next->next;
delete pos->next;
pos->next = temp;
return;
}
pos = pos->next;
}
if (pos->val == val)
{
delete pos;
pos = NULL;
}
}
void LinkedList::removeAt(int pos)
{
Node *transverse = new Node;
transverse = head;
if (transverse->pos == pos)
{
Node *temp = transverse->next;
delete head;
head = temp;
return;
}
while (transverse->next != NULL)
{
if (transverse->next->pos == pos)
{
Node *temp = transverse->next->next;
delete transverse->next;
transverse->next = temp;
return;
}
transverse = transverse->next;
}
if (transverse->pos == pos) {
delete transverse;
transverse = NULL;
}
}
void LinkedList::remove(string num)
{
Node *pos = new Node;
pos = head;
if (pos->name == num)
{
Node *temp = pos->next;
delete head;
head = temp;
return;
}
while (pos->next != NULL)
{
if (pos->next->name == num)
{
Node *temp = pos->next->next;
delete pos->next;
pos->next = temp;
return;
}
pos = pos->next;
}
if (pos->name == num)
{
delete pos;
pos = NULL;
}
}
bool LinkedList::contains(string n)
{
bool contains = false;
Node *pos;
pos = head;
while (pos != NULL)
{
if (pos->name == n)
{
contains = true;
return contains;
}
pos = pos->next;
}
return contains;
}
bool LinkedList::contains(int n) {
bool contains = false;
Node *pos;
pos = head;
while (pos != NULL) {
if (pos->pos == n) {
contains = true;
return contains;
}
pos = pos->next;
}
return contains;
}
void LinkedList::printList()
{
Node *pos = head;
int t = 1;
while (pos != NULL)
{
cout << t << ": ";
int temp = pos->val;
string temp2 = pos->name;
int temp3 = pos->pos;
cout << temp << ' '<< temp2 << ' ' << temp3 << endl;
pos = pos->next;
t++;
}
}
void LinkedList::splitHead(int x, string num)
{
if (head->val >= x)
{
head->val -= x;
Node * temp = head->next;
head->next = 0;
head->next = new Node(x);
head->next->name = num;
head->next->next = temp;
}
}
void LinkedList::splitAt(int pos, int amount, string n)
{
if (contains(pos))
{
Node *node = getAt(pos);
node->val -= amount;
Node *temp = node->next;
node->next = 0;
node->next = new Node(amount);
node->next->name = n;
node->next->next = temp;
}
}
void LinkedList::transfer(LinkedList *b, string num)
{
if (this->contains(num))
{
Node temp = this->getCopy(num);
b->add(temp);
this->remove(num);
}
}
void LinkedList::add(Node num)
{
if (head == NULL)
{
head = new Node;
*head = num;
head->next = NULL;
return;
}
head->add(num);
}
Node LinkedList::getCopy(string num)
{
Node *pos;
pos = head;
while (pos != NULL)
{
if (pos->name == num)
{
return *pos;
}
pos = pos->next;
}
return 0;
}
Node * LinkedList::get(string num)
{
Node *pos;
pos = head;
while (pos != NULL)
{
if (pos->name == num)
{
return pos;
}
pos = pos->next;
}
return 0;
}
Node * LinkedList::getAt(int num)
{
Node *pos;
pos = head;
while (pos != NULL)
{
if (pos->pos == num)
{
return pos;
}
pos = pos->next;
}
return 0;
}
int LinkedList::getDataAtpos(int num)
{
Node * pos = head;
while (pos != NULL)
{
if (pos->pos == num)
{
return pos->val;
}
pos = pos->next;
}
return -1;
}
string LinkedList::getNameAtpos(int num)
{
Node * pos = head;
while (pos != NULL)
{
if (pos->pos == num)
{
return pos->name;
}
pos = pos->next;
}
return 0;
}
Please make use of it i have implemented and submitted with out any errors
Thank You
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.