C++ , memory management, linked lists, best fit algorithm, worst fit algorithm P
ID: 3677914 • Letter: C
Question
C++ , memory management, linked lists, best fit algorithm, worst fit algorithm
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 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/AKB 250.000 page-nodes)]Explanation / Answer
#include <iostream>
#include <string>
#include <stdlib.h>
#include <iomanip>
using namespace std;
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);
//void 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);
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");
}
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);
}
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);
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)
{
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;
}
case 5:
{
exit(0);
break;
}
}
}
}
void worstFit()
{
int userChoice = 0;
int programSize;
int pagesUsed = 0;
int pageDeleteCounter = 0;
int largestFreePages = 0;
string pName;
struct page *freeMemory = new page;
struct page *usedMemory = new page;
for(int counter = 1; counter <= 32; counter++){
addPage(freeMemory, "Free");
}
cout << "Using the Worst 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 (pagesUsed < 32)
{
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);
}
cout << "Program " << pName << " Successfully Added! ("<< programSize << " Page(s) Used)" << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
}
else
{
page *startingBlock = usedLargest(usedMemory, largestFreePages);
if(largestFreePages >= programSize)
{
pagesUsed = pagesUsed + programSize;
writeToUsed(startingBlock, programSize, pName);
cout << "Program " << pName << " Successfully Added! ("<< programSize << " Page(s) Used)" << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
}
else if(largestFreePages < programSize){
cout << "Error, Not Enough Memory to Add " << pName << "!" << endl;
displayMenu();
cout << "Option: ";
cin >> userChoice;
}
largestFreePages = 0;
}
}
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
{
cout << "Not Enough Memory to Add More Programs!" << 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;
}
case 5:
{
exit(0);
break;
}
}
}
}
void displayMenu()
{
cout << endl;
cout << "1. Add Program" << endl;
cout << "2. Kill Program" << endl;
cout << "3. Fragmentation" << endl;
cout << "4. Print Memory" << endl;
cout << "5. Exit" << endl;
cout << endl;
}
void initPage(struct page *head, string programName){
head -> programName = programName;
head -> nextPage = NULL;
}
void addPage(struct page *head, string programName){
if(head == NULL)
{
initPage(head, programName);
return;
}
page *newPage = new page;
newPage -> programName = programName;
newPage -> nextPage = NULL;
page *current = head;
while(current)
{
if(current -> nextPage == NULL)
{
current -> nextPage = newPage;
return;
}
current = current -> nextPage;
}
}
bool deletePage(struct page **head, page *pageDelete)
{
page *current = *head;
if(pageDelete == *head)
{
*head = current -> nextPage;
delete(pageDelete);
return true;
}
while(current)
{
if(current -> nextPage == pageDelete)
{
current -> nextPage = pageDelete -> nextPage;
delete(pageDelete);
return true;
}
current = current -> nextPage;
}
return false;
}
void deleteEnd(struct page *head)
{
if (head -> nextPage == NULL)
{
delete head;
head = NULL;
}
else
{
page *nextToEnd = head;
page *end = head -> nextPage;
while (end->nextPage != NULL)
{
nextToEnd = end;
end = end->nextPage;
}
delete end;
nextToEnd->nextPage = NULL;
}
}
void outputMemory(struct page *head, struct page *head2)
{
int counter = 0;
page *usedMemory = head;
page *freeMemory = head2;
usedMemory = usedMemory->nextPage;
freeMemory = freeMemory->nextPage;
while(usedMemory)
{
if(counter % 9 == 0)
{
cout << endl;
counter++;
}
else
{
cout << setw(10) << usedMemory->programName;
usedMemory = usedMemory->nextPage;
counter++;
}
}
while(freeMemory)
{
if(counter % 9 == 0)
{
cout << endl;
counter++;
}
else
{
cout << setw(10) << freeMemory->programName;
freeMemory = freeMemory->nextPage;
counter++;
}
}
}
void allocateFree(struct page **head, page *pagetoFree)
{
pagetoFree -> programName = "Free";
}
struct page *searchPage(struct page *head, string programName)
{
page *current = head;
while(current){
if(current -> programName == programName) return current;
current = current -> nextPage;
}
throw 1;
}
int kbtoPages(int kb)
{
int pages;
pages = kb / 4;
if(kb % 4 > 0)
{
pages++;
}
return pages;
}
int listLength(struct page *head)
{
int counter = 0;
while (head != NULL)
{
counter++;
head = head -> nextPage;
}
counter = counter - 1;
return counter;
}
bool inMemory(struct page *head, string programName){
page *current = head;
while(current)
{
if(current -> programName == programName) return true;
current = current -> nextPage;
}
return false;
}
struct page *usedSmallest(struct page *head, int &smlstFree, int minimumSize){
int smallestNumberFreePages = 32;
int freePageCounter = 0;
struct page *theSmallestBlock = NULL;
struct page *smallestBlockStart = NULL;
page *current = head;
current = current -> nextPage;
while(current)
{
if(current -> programName == "Free" && current -> nextPage != NULL){
if(smallestBlockStart == NULL){
smallestBlockStart = current;
}
freePageCounter++;
}
else if(current -> programName == "Free" && current -> nextPage == NULL){
if(smallestBlockStart == NULL){
smallestBlockStart = current;
}
freePageCounter++;
if(freePageCounter <= smallestNumberFreePages && freePageCounter >= minimumSize)
{
theSmallestBlock = smallestBlockStart;
smallestBlockStart = NULL;
smallestNumberFreePages = freePageCounter;
freePageCounter = 0;
}
}
else if(current -> programName != "Free" && current ->nextPage == NULL){
if(freePageCounter <= smallestNumberFreePages && freePageCounter >= minimumSize && freePageCounter != 0){
theSmallestBlock = smallestBlockStart;
smallestBlockStart = NULL;
smallestNumberFreePages = freePageCounter;
freePageCounter = 0;
}
else if(freePageCounter == 0 && (smallestNumberFreePages == 0 || smallestNumberFreePages == 32)){
smallestNumberFreePages = 0;
}
}
else if(current -> programName != "Free" && current ->nextPage != NULL){
if(freePageCounter <= smallestNumberFreePages && freePageCounter >= minimumSize && freePageCounter != 0){
theSmallestBlock = smallestBlockStart;
smallestBlockStart = NULL;
smallestNumberFreePages = freePageCounter;
freePageCounter = 0;
}
}
current = current -> nextPage;
}
smlstFree = smallestNumberFreePages;
cout << "Number of Pages Available: " << smlstFree << endl;
return theSmallestBlock;
}
struct page *usedLargest(struct page *head, int &lrgstFree)
{
int largestNumberFreePages = 0;
int freePageCounter = 0;
struct page *theLargestBlock = NULL;
struct page *largestBlockStart = NULL;
page *current = head;
current = current -> nextPage;
while(current)
{
if(current -> programName == "Free" && current -> nextPage != NULL){
if(largestBlockStart == NULL)
{
largestBlockStart = current;
}
freePageCounter++;
}
else if(current -> programName == "Free" && current -> nextPage == NULL){
if(largestBlockStart == NULL){
largestBlockStart = current;
}
freePageCounter++;
if(freePageCounter > largestNumberFreePages)
{
theLargestBlock = largestBlockStart;
largestBlockStart = NULL;
largestNumberFreePages = freePageCounter;
freePageCounter = 0;
}
}
else if(current -> programName != "Free")
{
if(freePageCounter > largestNumberFreePages) {
theLargestBlock = largestBlockStart;
largestBlockStart = NULL;
largestNumberFreePages = freePageCounter;
freePageCounter = 0;
}
}
current = current -> nextPage;
}
lrgstFree = largestNumberFreePages;
return theLargestBlock;
}
void writeToUsed(page *startNode, int numPages, string pgrmName)
{
page *current = startNode;
for(int counter = 1; counter <= numPages; counter++){
if(current -> programName == "Free")
{
current -> programName = pgrmName;
}
else if(current -> programName != "Free"){
cout << "ERROR! Attempted Overwrite of Program in Memory!";
return;
}
current = current -> nextPage;
}
}
void countFragments(struct page *head){
page *current = head;
int numberOfFragments = 0;
string placeHolder;
bool startingFragment = false;
current = current->nextPage;
placeHolder = current->programName;
if (placeHolder == "Free") {
startingFragment = true;
}
while (current)
{
if (current->programName == placeHolder && current->nextPage != NULL) {}
else if (current->programName != placeHolder && current->nextPage != NULL) {
if (current->programName != "Free" && placeHolder == "Free") {
numberOfFragments++;
placeHolder = current->programName;
}
else if (current->programName != "Free" && placeHolder != "Free") {
placeHolder = current->programName;
}
else if (current->programName == "Free" && placeHolder != "Free") {
placeHolder = current->programName;
}
}
else if(current->nextPage == NULL && listLength(head) != 32 && current->programName != "Free" && !startingFragment){
numberOfFragments++;
}
else if(current->nextPage == NULL && listLength(head) == 32 && !startingFragment){
numberOfFragments++;
}
current = current->nextPage;
}
cout << "There are " << numberOfFragments << " fragment(s)" << endl;
}
*/
void countFragments(struct page *head, struct page *head2){
int numberOfFragments = 0;
string placeHolder;
page *mergedPage = new page;
bool startingFragment = false;
page *current = head;
current = current->nextPage;
while (current)
{
addPage(mergedPage, current -> programName);
current = current->nextPage;
}
current = head2;
current = current->nextPage;
while (current)
{
addPage(mergedPage, current -> programName);
current = current->nextPage;
}
current = mergedPage;
current = current -> nextPage;
placeHolder = current->programName;
if (placeHolder == "Free")
{
startingFragment = true;
}
while(current)
{
if (current->programName == placeHolder && current->nextPage != NULL) {}
else if (current->programName != placeHolder && current->nextPage != NULL) {
if (current->programName != "Free" && placeHolder == "Free")
{
numberOfFragments++;
placeHolder = current->programName;
}
else if (current->programName != "Free" && placeHolder != "Free") {
placeHolder = current->programName;
}
else if (current->programName == "Free" && placeHolder != "Free") {
placeHolder = current->programName;
}
}
current = current->nextPage;
}
if(!startingFragment)
{
numberOfFragments++;
}
cout << "There are " << numberOfFragments << " fragment(s)" << endl;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.