In: Computer Science
Objective: Write a C++ -program that will implement 4
Memory Management algorithms
Algorithms:
A) Best-Fit
B) First-Fit
C) Next-Fit
D) Worst-Fit
Your program must do the following:
1. Program Input:
User will input to the program
a. Main Memory information, including
i. The Number of Memory partitions.
ii. The Size of each memory partition.
b. Process information (assign a unique identifier to each
job)
i. User will input the number of processes
ii. Memory requirements for each process/job
2. For each algorithm, your program should have a data
structure(class or struct) that will include the following:
Job/Process Class
• Name of the process/ job(number or word)
• Process/job status (Run/Wait),
• partition number the process/job was assigned to
Memory Partition Class
• Name of the partition (Alphanumeric ID, ie string or char
string)
• Total size of the partition(int)
• Is a job assigned? (bool)
• Job id assigned to it
• Waste or excess produced by the job assignment (int)
You can create an array or list of the object to represent the job
queue.
3. Program output:
a) Initial memory allocation: Calculate and display a list of
initial memory allocation, i.e which partitions contain which
process after the first round of allocation
b) Memory waste: Program will calculate and display the memory
waste for each partition
c. total waste for each algorithm.
e. A list of Processes in the waiting State(was not assigned to a
partition).
Hi,
Please find the code below.
(A) Best-Fit Algorithm Program
#include<iostream>
using namespace std;
int main()
{
int frag[20],b[20],p[20],i,j,nb,np,temp,lowest=9999;
static int barray[20],parray[20];
cout<<"\n\t\t\tMemory Management Scheme - Best Fit";
cout<<"Enter no. of memory partitions: ";
cin>>nb;
cout<<"\nEnter the number of processes:";
cin>>np;
cout<<"\nEnter size of each mermory partition: \n";
for(i=1;i<=nb;i++)
{
cout<<"Partition no."<<i<<":";
cin>>b[i];
}
cout<<"\nEnter the size of each process :-\n";
for(i=1;i<=np;i++)
{
cout<<"Process no. "<<i<<":";
cin>>p[i];
}
for(i=1;i<=np;i++)
{
for(j=1;j<=nb;j++)
{
if(barray[j]!=1)
{
temp=b[j]-p[i];
if(temp>=0)
if(lowest>temp)
{
parray[i]=j;
lowest=temp;
}
}
}
frag[i]=lowest;
barray[parray[i]]=1;
lowest=10000;
}
cout<<"\nProcess_no\tProcess_size\tBlock_no\tBlock_size\tFragment";
for(i=1;i<=np && parray[i]!=0;i++)
cout<<"\n"<<i<<"\t\t"<<p[i]<<"\t\t"<<parray[i]<<"\t\t"<<b[parray[i]]<<"\t\t"<<frag[i];
return 0;
}
(B) First-Fit Algorithm Program
#include<iostream>
using namespace std;
int main()
{
int bsize[10], psize[10], bno, pno, flags[10], alloc[10], i, j;
for(i = 0; i < 10; i++)
{
flags[i] = 0;
alloc[i] = -1;
}
cout<<"Enter no. of memory partitions: ";
cin>>bno;
cout<<"\nEnter size of each mermory partition: ";
for(i = 0; i < bno; i++)
cin>>bsize[i];
cout<<"\nEnter no. of processes: ";
cin>>pno;
cout<<"\nEnter size of each process: ";
for(i = 0; i < pno; i++)
cin>>psize[i];
for(i = 0; i < pno; i++) //allocation as per first fit
for(j = 0; j < bno; j++)
if(flags[j] == 0 && bsize[j] >= psize[i])
{
alloc[j] = i;
flags[j] = 1;
break;
}
//display allocation details
cout<<"\nBlock no.\tsize\t\tprocess no.\t\tsize";
for(i = 0; i < bno; i++)
{
cout<<"\n"<<
i+1<<"\t\t"<<bsize[i]<<"\t\t";
if(flags[i] == 1)
cout<<alloc[i]+1<<"\t\t\t"<<psize[alloc[i]];
else
cout<<"Not allocated";
}
return 0;
}
(C) Next-Fit Algorithm Program
#include <iostream>
using namespace std;
int main()
{
int memory_size[10][2], process_size[10][3];
int i, j, total_processes = 0, total_memory = 0;
cout<<"\nEnter the Total Number of Processes:\t";
cin>>total_processes;
cout<<"\nEnter the Size of Each Process\n";
for(int i = 0; i < total_processes; i++)
{
cout<<"Enter Size of Process "<<"\t"<<i +
1;
cin>>process_size[i][0];
process_size[i][1] = 0;
process_size[i][2] = i;
}
cout<<"\nEnter no. of memory partitions:\t";
cin>>total_memory;
cout<<"\nEnter the size of each partition:\n";
for(i = 0; i < total_processes; i++)
{
cout<<"Enter size of partition "<<"\t"<<i +
1;;
cin>>memory_size[i][0];
memory_size[i][1] = 0;
}
for(i = 0; i < total_processes; i++)
{
while(j < total_memory)
{
if(memory_size[j][1] == 0 && process_size[i][0] <=
memory_size[j][0])
{
process_size[i][1] = 1;
memory_size[j][1] = 1;
cout<<"Process
"<<"["<<i+1<<"]"<<"Allocated to Memory
Block:\t"<<j+1;
break;
}
j++;
}
}
for(i = 0; i < total_memory; i++)
{
if(process_size[i][1] == 0)
{
cout<<"Process
"<<"["<<i+1<<"]"<<"Unallocated";
}
}
cout<<"\n";
return 0;
}
(D) Worst-Fit Algorithm Program
#include<bits/stdc++.h>
using namespace std;
// Function to allocate memory to blocks as per worst fit
// algorithm
void worstFit(int blockSize[], int m, int processSize[],
int n)
{
// Stores block id of the block allocated to a
// process
int alloc[n];
// Initially no block is assigned to any process
memset(alloc -1, sizeof(alloc));
// pick each process and find suitable blocks
// according to its size ad assign to it
for (int i=0; i<n; i++)
{
// Find the best fit block for current process
int ws = -1;
for (int j=0; j<m; j++)
{
if (blockSize[j] >= processSize[i])
{
if (ws == -1)
ws = j;
else if (blockSize[ws] < blockSize[j])
ws = j;
}
}
// If we could find a block for current process
if (ws != -1)
{
// allocate block j to p[i] process
alloc[i] = ws;
// Reduce available memory in this block.
blockSize[ws] -= processSize[i];
}
}
cout << "\nProcess No.\tProcess Size\tBlock no.\n";
for (int i = 0; i < n; i++)
{
cout << " " << i+1 << "\t\t" <<
processSize[i] << "\t\t";
if (alloc[i] != -1)
cout << alloc[i] + 1;
else
cout << "Not Allocated";
cout << endl;
}
}
// Driver code
int main()
{
int m, n;
cout<<"Enter no. of memory partitions: ";
cin>>m;
cout<<"\nEnter the number of processes:";
cin>>n;
int blockSize[m];
int processSize[n];
cout<<"\nEnter size of each mermory partition: \n";
for(int i=1;i<=m;i++) {
cout<<"Partition no."<<i<<":";
cin>>blockSize[i];
}
cout<<"\nEnter the size of each process :-\n";
for(int i=1;i<=n;i++) {
cout<<"Process no. "<<i<<":";
cin>>processSize[i];
}
worstFit(blockSize, m, processSize, n);
return 0 ;
}
Please contact me if you need any clarification.
Thank you :)