Question

Objective: Write a C++ -program that will implement 4 Memory Management algorithms A) Best-Fit B) First-Fit C) Next-Fit D) Worst-Fit Your program must do the followin 1. Program Input a. User will input to the program, Number of partitions, and Memory Sizes for each partition/partitions b. User will input the name for each process, and the amount of memory the process needs 2. For each algorithm, your program should have a data structure(class) that will include the job status (Run/Wait), and the partition number assigned to the job (if the job was allocated) You can create an array or list of the class to represent the job queue 3. Program output a. Calculate and display a list of initial memory allocation, i.e which partitions contain which process after the first round of allocation b. Program will calculate and display the memory waste for each partition. c. A list of Processes not assigned to any partitiorn

The second picture that I attached is the input and output. I already did the code but I also have to add the partition number assigned to the job (if the job was allocated). Can you please do that for me? I copied and pasted my code below.

#include <iostream>

#include <string.h>

#include <stdio.h>

using std::cout;

using std::cin;

using std::endl;

unsigned int memorySize;

// Function prototypes

unsigned int FirstFit(struct Partition *, int, struct Job *, int);

unsigned int BestFit(struct Partition *, int, struct Job *, int);

unsigned int NextFit(struct Partition *, int, struct Job *, int);

unsigned int WorstFit(struct Partition *, int, struct Job *, int);

// Partition struct descriptor

struct Partition

{

unsigned int size;

int number;

bool free;

unsigned int hole;

char jobName[7];

};

// Job struct descriptor

struct Job

{

char name[4];

unsigned int size;

bool running; // Run/Wait

int partitionNumber;

};

int main()

{

Partition *partitions;

Job *jobs;

int numPartitions;

int numJobs;

unsigned int totalPartitionSize = 0;

// Prompt user for information needed

cout << "Input memory size: ";

cin >> memorySize;

cout << "Input number of partitions (max. 5): ";

cin >> numPartitions;

// Allocate memory for partitions

partitions = new Partition[numPartitions];

// Initialize each partition

for (int i = 0; i < numPartitions; i++)

{

int partitionSize;

cout << "Input size for partition " << i + 1 << ": ";

cin >> partitionSize;

totalPartitionSize += partitionSize;

// Check if enough memory available

if (totalPartitionSize > memorySize)

{

cout << "Error: Total partition size is more than memory size available" << endl;

delete[] partitions;

return -1;

}

partitions[i].size = partitionSize;

partitions[i].number = i + 1;

partitions[i].free = true;

partitions[i].hole = 0;

strncpy(partitions[i].jobName, "", sizeof(partitions[i].jobName));

}

cout << "Input number of jobs: ";

cin >> numJobs;

// Allocate memory for partitions

jobs = new Job[numJobs];

for (int i = 0; i < numJobs; i++)

{

snprintf(jobs[i].name, sizeof(jobs[i].name), "J%02d", i + 1);

cout << "Input size for " << jobs[i].name << ": ";

cin >> jobs[i].size;

jobs[i].running = false;

jobs[i].partitionNumber = 0;

}

while(true)

{

for (int i = 0; i < numPartitions; i++)

{

partitions[i].free = true;

partitions[i].hole = 0;

}

for (int i = 0; i < numJobs; i++)

{

jobs[i].running = false;

jobs[i].partitionNumber = 0;

}

int choice = 0;

while (!(choice >= 1 && choice <= 4))

{

cout << "Input memory management algorithm (1-4):" << endl;

cout << "1. First Fit" << endl;

cout << "2. Best Fit" << endl;

cout << "3. Next Fit" << endl;

cout << "4. Worst Fit" << endl;

cin >> choice;

}

unsigned int memoryWasted = 0;

if (choice == 1)

memoryWasted = FirstFit(partitions, numPartitions, jobs, numJobs);

else if (choice == 2)

memoryWasted = BestFit(partitions, numPartitions, jobs, numJobs);

else if (choice == 3)

memoryWasted = NextFit(partitions, numPartitions, jobs, numJobs);

else if (choice == 4)

memoryWasted = WorstFit(partitions, numPartitions, jobs, numJobs);

cout << "Choice was: " << choice << endl;

for(int i = 0; i < numPartitions;i++)

{

cout << partitions[i].jobName << "/" << partitions[i].hole << endl;

}

cout << "Total memory waste: " << memoryWasted << endl;

cout << "Jobs waiting: ";

int waitingCount = 0;

for (int i = 0; i < numJobs; i++)

{

if (!jobs[i].running)

{

cout << jobs[i].name;

if (i != numJobs - 1)

cout << ", ";

waitingCount++;

}

}

if (waitingCount == 0)

cout << "None" << endl;

cout << endl;

}

// Free memory

delete[] jobs;

delete[] partitions;

return 0;

}

// First fit algorithm

unsigned int FirstFit(Partition *partitions, int numPartitions, Job *jobs, int numJobs)

{

// Total memory waste

unsigned int memoryWaste = 0;

for (int i = 0; i < numJobs; i++)

{

// If job already running, skip it

if (jobs[i].running)

continue;

for (int j = 0; j < numPartitions; j++)

{

// Skip partitions that are either not free or not big enough to hold the job

if (!partitions[j].free || partitions[j].size < jobs[i].size)

continue;

// Update partition status

partitions[j].free = false;

memoryWaste += partitions[j].hole = partitions[j].size - jobs[i].size;

strncpy(partitions[j].jobName, jobs[i].name, sizeof(partitions[j].jobName));

// Update job status

jobs[i].running = true;

jobs[i].partitionNumber = partitions[j].number;

break;

}

}

return memoryWaste;

}

// Best fit algorithm

unsigned int BestFit(Partition *partitions, int numPartitions, Job *jobs, int numJobs)

{

// Total memory waste

unsigned int memoryWaste = 0;

for (int i = 0; i < numJobs; i++)

{

// If job already running, skip it

if (jobs[i].running)

continue;

int bestIndex = -1;

for (int j = 0; j < numPartitions; j++)

{

// Skip partitions that are either not free or not big enough to hold the job

if (!partitions[j].free || partitions[j].size < jobs[i].size)

continue;

if (bestIndex == -1)

bestIndex = j;

else if (partitions[j].size < partitions[bestIndex].size)

bestIndex = j;

}

if (bestIndex >= 0)

{

// Update partition status

partitions[bestIndex].free = false;

memoryWaste += partitions[bestIndex].hole = partitions[bestIndex].size - jobs[i].size;

strncpy(partitions[bestIndex].jobName, jobs[i].name, sizeof(partitions[bestIndex].jobName));

// Update job status

jobs[i].running = true;

jobs[i].partitionNumber = partitions[bestIndex].number;

}

}

return memoryWaste;

}

// Next fit algorithm

unsigned int NextFit(Partition *partitions, int numPartitions, Job *jobs, int numJobs)

{

// Total memory waste

unsigned int memoryWaste = 0;

int lastIndex = -1;

for (int i = 0; i < numJobs; i++)

{

// If job already running, skip it

if (jobs[i].running)

continue;

int curIndex = lastIndex;

for (;;)

{

curIndex++;

if (curIndex >= numPartitions)

{

if (lastIndex == -1 || lastIndex == 0)

break;

curIndex = 0;

}

else if (curIndex == lastIndex)

break;

// Skip partitions that are either not free or not big enough to hold the job

if (!partitions[curIndex].free || partitions[curIndex].size < jobs[i].size)

continue;

// Update partition status

partitions[curIndex].free = false;

memoryWaste += partitions[curIndex].hole = partitions[curIndex].size - jobs[i].size;

strncpy(partitions[curIndex].jobName, jobs[i].name, sizeof(partitions[curIndex].jobName));

// Update job status

jobs[i].running = true;

jobs[i].partitionNumber = partitions[curIndex].number;

lastIndex = curIndex;

break;

}

}

return memoryWaste;

}

unsigned int WorstFit(Partition *partitions, int numPartitions, Job *jobs, int numJobs)

{

unsigned int memoryWaste = 0;

for(int i = 0; i < numJobs; i++)

{

if(jobs[i].running)

continue;

int worstIndex = -1;

for(int j = 0; j < numPartitions; j++)

{

if((partitions[j].free && partitions[j].size < jobs[i].size) || (!partitions[j].free && partitions[j].hole < jobs[i].size))

continue;

if(worstIndex == -1)

worstIndex = j;

else if(partitions[j].free && partitions[j].size > partitions[worstIndex].size)

worstIndex = j;

else if(!partitions[j].free && partitions[j].hole > partitions[worstIndex].size)

worstIndex = j;

}

if(worstIndex >= 0)

{

if(partitions[worstIndex].free)

{

partitions[worstIndex].free = false;

memoryWaste += partitions[worstIndex].hole = partitions[worstIndex].size - jobs[i].size;

strncpy(partitions[worstIndex].jobName, jobs[i].name, sizeof(partitions[worstIndex].jobName));

jobs[i].running = true;

jobs[i].partitionNumber = partitions[worstIndex].number;

}

else

{

memoryWaste += partitions[worstIndex].hole = partitions[worstIndex].hole - jobs[i].size;

strncat(partitions[worstIndex].jobName, jobs[i].name, sizeof(partitions[worstIndex].jobName));

jobs[i].running = true;

jobs[i].partitionNumber = partitions[worstIndex].number;

}

}

}

return memoryWaste;

}

// Worst fit algorithm

/*unsigned int WorstFit(Partition *partitions, int numPartitions, Job *jobs, int numJobs)

{

// Total memory waste

unsigned int memoryWaste = 0;

for (int i = 0; i < numJobs; i++)

{

// If job already running, skip it

if (jobs[i].running)

continue;

int worstIndex = -1;

for (int j = 0; j < numPartitions; j++)

{

// Skip partitions that are either not free or not big enough to hold the job

if (!partitions[j].free || partitions[j].size < jobs[i].size)

continue;

if (worstIndex == -1)

worstIndex = j;

else if (partitions[j].size > partitions[worstIndex].size)

worstIndex = j;

}

if (worstIndex >= 0)

{

// Update partition status

partitions[worstIndex].free = false;

memoryWaste += partitions[worstIndex].hole = partitions[worstIndex].size - jobs[i].size;

strncpy(partitions[worstIndex].jobName, jobs[i].name, sizeof(partitions[worstIndex].jobName));

// Update job status

jobs[i].running = true;

jobs[i].partitionNumber = partitions[worstIndex].number;

}

}

return memoryWaste;

}*/

Answer 1

I have added an int array named

int partitionNumberArray[numPartitions];

It maintains an array with partition number which is used for the Job and prints it with the final output.

The code is redundant and added to every function to support that.

If you want code optimization. you can create a function and call it from every fit function(first/best/next/worst).

#include <iostream>

#include <string.h>

#include <stdio.h>

using std::cout;

using std::cin;

using std::endl;

unsigned int memorySize;

// Function prototypes

unsigned int FirstFit(struct Partition *, int, struct Job *, int, int *);

unsigned int BestFit(struct Partition *, int, struct Job *, int, int *);

unsigned int NextFit(struct Partition *, int, struct Job *, int, int *);

unsigned int WorstFit(struct Partition *, int, struct Job *, int, int *);

// Partition struct descriptor

struct Partition

{

unsigned int size;

int number;

bool free;

unsigned int hole;

char jobName[7];

};

// Job struct descriptor

struct Job

{

char name[4];

unsigned int size;

bool running; // Run/Wait

int partitionNumber;

};

int main()

{

Partition *partitions;

Job *jobs;

int numPartitions;

int numJobs;

unsigned int totalPartitionSize = 0;

// Prompt user for information needed

cout << "Input memory size: ";

cin >> memorySize;

cout << "Input number of partitions (max. 5): ";

cin >> numPartitions;
int partitionNumberArray[numPartitions];

// Allocate memory for partitions

partitions = new Partition[numPartitions];

// Initialize each partition

for (int i = 0; i < numPartitions; i++)

{

int partitionSize;

cout << "Input size for partition " << i + 1 << ": ";

cin >> partitionSize;

totalPartitionSize += partitionSize;

// Check if enough memory available

if (totalPartitionSize > memorySize)

{

cout << "Error: Total partition size is more than memory size available" << endl;

delete[] partitions;

return -1;

}

partitions[i].size = partitionSize;

partitions[i].number = i + 1;

partitions[i].free = true;

partitions[i].hole = 0;

strncpy(partitions[i].jobName, "", sizeof(partitions[i].jobName));

}

cout << "Input number of jobs: ";

cin >> numJobs;

// Allocate memory for partitions

jobs = new Job[numJobs];

for (int i = 0; i < numJobs; i++)

{

snprintf(jobs[i].name, sizeof(jobs[i].name), "J%02d", i + 1);

cout << "Input size for " << jobs[i].name << ": ";

cin >> jobs[i].size;

jobs[i].running = false;

jobs[i].partitionNumber = 0;

}

while(true)

{

for (int i = 0; i < numPartitions; i++)

{

partitions[i].free = true;

partitions[i].hole = 0;

}

for (int i = 0; i < numJobs; i++)

{

jobs[i].running = false;

jobs[i].partitionNumber = 0;

}

int choice = 0;

while (!(choice >= 1 && choice <= 4))

{

cout << "Input memory management algorithm (1-4):" << endl;

cout << "1. First Fit" << endl;

cout << "2. Best Fit" << endl;

cout << "3. Next Fit" << endl;

cout << "4. Worst Fit" << endl;

cin >> choice;

}

unsigned int memoryWasted = 0;

if (choice == 1)

memoryWasted = FirstFit(partitions, numPartitions, jobs, numJobs,partitionNumberArray);

else if (choice == 2)

memoryWasted = BestFit(partitions, numPartitions, jobs, numJobs,partitionNumberArray);

else if (choice == 3)

memoryWasted = NextFit(partitions, numPartitions, jobs, numJobs,partitionNumberArray);

else if (choice == 4)

memoryWasted = WorstFit(partitions, numPartitions, jobs, numJobs,partitionNumberArray);

cout << "Choice was: " << choice << endl;

for(int i = 0; i < numPartitions;i++)

{
if(partitions[i].free)
continue;
cout << partitions[i].jobName << "/" <<"P"<<partitions[i].number<<"/"<<partitions[i].hole << endl;
//cout<< jobs[i].name <<"/"<<"P"<<jobs[i].partitionNumber<<"/"<<partitions[i].hole << endl;
}

cout << "Total memory waste: " << memoryWasted << endl;

cout << "Jobs waiting: ";

int waitingCount = 0;

for (int i = 0; i < numJobs; i++)

{

if (!jobs[i].running)

{

cout << jobs[i].name;

if (i != numJobs - 1)

cout << ", ";

waitingCount++;

}

}

if (waitingCount == 0)

cout << "None" << endl;

cout << endl;

}

// Free memory

delete[] jobs;

delete[] partitions;

return 0;

}

// First fit algorithm

unsigned int FirstFit(Partition *partitions, int numPartitions, Job *jobs, int numJobs,int *partitionNumberArray)

{

// Total memory waste
int pn = 0;
unsigned int memoryWaste = 0;

for (int i = 0; i < numJobs; i++)

{

// If job already running, skip it

if (jobs[i].running)

continue;

for (int j = 0; j < numPartitions; j++)

{

// Skip partitions that are either not free or not big enough to hold the job

if (!partitions[j].free || partitions[j].size < jobs[i].size)

continue;

// Update partition status

partitions[j].free = false;

memoryWaste += partitions[j].hole = partitions[j].size - jobs[i].size;

strncpy(partitions[j].jobName, jobs[i].name, sizeof(partitions[j].jobName));

// Update job status

jobs[i].running = true;

jobs[i].partitionNumber = partitions[j].number;

//cout<<" jobs[i].name : "<<jobs[i].name<<" jobs[i].partitionNumber : "<<jobs[i].partitionNumber<<" i:"<<i<<endl;

//Update Partition Number
if(pn<numPartitions)
{
partitionNumberArray[pn] = jobs[i].partitionNumber;
//cout<<"partitionNumberArray[pn] : "<<partitionNumberArray[pn]<<" pn:"<<pn<<endl;
pn++;

}

break;

}

}

return memoryWaste;

}

// Best fit algorithm

unsigned int BestFit(Partition *partitions, int numPartitions, Job *jobs, int numJobs,int *partitionNumberArray)

{

// Total memory waste
int pn = 0;
unsigned int memoryWaste = 0;

for (int i = 0; i < numJobs; i++)

{

// If job already running, skip it

if (jobs[i].running)

continue;

int bestIndex = -1;

for (int j = 0; j < numPartitions; j++)

{

// Skip partitions that are either not free or not big enough to hold the job

if (!partitions[j].free || partitions[j].size < jobs[i].size)

continue;

if (bestIndex == -1)

bestIndex = j;

else if (partitions[j].size < partitions[bestIndex].size)

bestIndex = j;

}

if (bestIndex >= 0)

{

// Update partition status

partitions[bestIndex].free = false;

memoryWaste += partitions[bestIndex].hole = partitions[bestIndex].size - jobs[i].size;

strncpy(partitions[bestIndex].jobName, jobs[i].name, sizeof(partitions[bestIndex].jobName));

// Update job status

jobs[i].running = true;

jobs[i].partitionNumber = partitions[bestIndex].number;

//Update Partition Number
if(pn<numPartitions)
{
partitionNumberArray[pn] = jobs[i].partitionNumber;
pn++;
}

}

}

return memoryWaste;

}

// Next fit algorithm

unsigned int NextFit(Partition *partitions, int numPartitions, Job *jobs, int numJobs,int *partitionNumberArray)

{

// Total memory waste
int pn = 0;
unsigned int memoryWaste = 0;

int lastIndex = -1;

for (int i = 0; i < numJobs; i++)

{

// If job already running, skip it

if (jobs[i].running)

continue;

int curIndex = lastIndex;

for (;;)

{

curIndex++;

if (curIndex >= numPartitions)

{

if (lastIndex == -1 || lastIndex == 0)

break;

curIndex = 0;

}

else if (curIndex == lastIndex)

break;

// Skip partitions that are either not free or not big enough to hold the job

if (!partitions[curIndex].free || partitions[curIndex].size < jobs[i].size)

continue;

// Update partition status

partitions[curIndex].free = false;

memoryWaste += partitions[curIndex].hole = partitions[curIndex].size - jobs[i].size;

strncpy(partitions[curIndex].jobName, jobs[i].name, sizeof(partitions[curIndex].jobName));

// Update job status

jobs[i].running = true;

jobs[i].partitionNumber = partitions[curIndex].number;

lastIndex = curIndex;

//Update Partition Number
if(pn<numPartitions)
{
partitionNumberArray[pn] = jobs[i].partitionNumber;
pn++;
}

break;

}

}

return memoryWaste;

}

unsigned int WorstFit(Partition *partitions, int numPartitions, Job *jobs, int numJobs,int *partitionNumberArray)

{

unsigned int memoryWaste = 0;
int pn=0;

for(int i = 0; i < numJobs; i++)

{

if(jobs[i].running)

continue;

int worstIndex = -1;

for(int j = 0; j < numPartitions; j++)

{

if((partitions[j].free && partitions[j].size < jobs[i].size) || (!partitions[j].free && partitions[j].hole < jobs[i].size))

continue;

if(worstIndex == -1)

worstIndex = j;

else if(partitions[j].free && partitions[j].size > partitions[worstIndex].size)

worstIndex = j;

else if(!partitions[j].free && partitions[j].hole > partitions[worstIndex].size)

worstIndex = j;

}

if(worstIndex >= 0)

{

if(partitions[worstIndex].free)

{

partitions[worstIndex].free = false;

memoryWaste += partitions[worstIndex].hole = partitions[worstIndex].size - jobs[i].size;

strncpy(partitions[worstIndex].jobName, jobs[i].name, sizeof(partitions[worstIndex].jobName));

jobs[i].running = true;

jobs[i].partitionNumber = partitions[worstIndex].number;

//Update Partition Number
if(pn<numPartitions)
{
partitionNumberArray[pn] = jobs[i].partitionNumber;
pn++;
}

}

else

{

memoryWaste += partitions[worstIndex].hole = partitions[worstIndex].hole - jobs[i].size;

strncat(partitions[worstIndex].jobName, jobs[i].name, sizeof(partitions[worstIndex].jobName));

jobs[i].running = true;

jobs[i].partitionNumber = partitions[worstIndex].number;

//Update Partition Number
if(pn<numPartitions)
{
partitionNumberArray[pn] = jobs[i].partitionNumber;
pn++;
}

}

}

}

return memoryWaste;

}

// Worst fit algorithm

/*unsigned int WorstFit(Partition *partitions, int numPartitions, Job *jobs, int numJobs)

{

// Total memory waste

unsigned int memoryWaste = 0;

for (int i = 0; i < numJobs; i++)

{

// If job already running, skip it

if (jobs[i].running)

continue;

int worstIndex = -1;

for (int j = 0; j < numPartitions; j++)

{

// Skip partitions that are either not free or not big enough to hold the job

if (!partitions[j].free || partitions[j].size < jobs[i].size)

continue;

if (worstIndex == -1)

worstIndex = j;

else if (partitions[j].size > partitions[worstIndex].size)

worstIndex = j;

}

if (worstIndex >= 0)

{

// Update partition status

partitions[worstIndex].free = false;

memoryWaste += partitions[worstIndex].hole = partitions[worstIndex].size - jobs[i].size;

strncpy(partitions[worstIndex].jobName, jobs[i].name, sizeof(partitions[worstIndex].jobName));

// Update job status

jobs[i].running = true;

jobs[i].partitionNumber = partitions[worstIndex].number;

}

}

return memoryWaste;

}*/