CPU Scheduling Algorithms and Memory Management Techniques
CPU Scheduling FCFS
#include
#include
#include
void main()
{
int i,j,n,bt[10],compt[10],at[10],
wt[10],tat[10]; float
sumwt=0.0,sumtat=0.0,avgwt,avgtat;
printf(“Enter number of processes: “);
scanf(“%d”,&n);
printf(“Enter the burst time of %d process\n”,
n); for(i=0;i
{
scanf(“%d”,&bt[i]);
}
printf(“Enter the arrival time of %d process\n”,
n); for(i=0;i
{
scanf(“%d”,&at[i]);
}
compt[0]=bt[0]-at[0];
for(i=1;i
compt[i]=bt[i]+compt[i-
1]; for(i=0;i
{
tat[i]=compt[i]-at[i];
wt[i]=tat[i]-bt[i];
sumtat+=tat[i];
sumwt+=wt[i];
}
avgwt=sumwt/n;
avgtat=sumtat/n;
printf(“——————————— “);
; printf(“PN\tBt\tCt\tTat\tWt\n”);
printf(“———————————- “);
for(i=0;i
{
printf(“%d\t%2d\t%2d\t%2d\t%2d\n”,i,bt[i],compt[i],tat[i],wt[i]);
}
printf(“————————————– \n”);
printf(” Avgwt = %.2f\tAvgtat = %.2f\n”,avgwt,avgtat);
printf(“—————————————- “);
}
Shortest job first CPU scheduling
#include
#include
#include
void main()
{
int i,j,n,bt[10],compt[10],
wt[10],tat[10],temp;
float sumwt=0.0,sumtat=0.0,avgwt,avgtat;
printf(“Enter number of processes: “);
scanf(“%d”,&n);
printf(“Enter the burst time of %d process\n”, n);
for(i=0;i
{
scanf(“%d”,&bt[i]);
}
for(i=0;i
for(j=i+1;j
if(bt[i]>bt[j])
{
temp=bt[i];
bt[i]=bt[j];
bt[j]=temp;
}
compt[0]=bt[0];
for(i=1;i
compt[i]=bt[i]+compt[i-1];
for(i=0;i
{
tat[i]=compt[i];
wt[i]=tat[i]-
bt[i];
sumtat+=tat[i];
sumwt+=wt[i];
}
avgwt=sumwt/n;
avgtat=sumtat/n;
printf(“_________________________________ “);
printf(“Bt\tCt\tTat\tWt\n”);
printf(“_________________________________ “);
for(i=0;i
{
printf(“%2d\t %2d\t %2d\t %2d\n”,i,bt[i],compt[i],tat[i],wt[i]);
}
printf(“________________________________________ “);
printf(” Avgwt = %.2f\tAvgtat = %.2f\n”,avgwt,avgtat);
printf(“__________________________________________ “);
}
Procedure and consumer using semaphores
#include
#include
int
mutex=1,full=0,empty=3,x=0;
int main()
{
int n;
void producer();
void consumer();
int wait(int);
int signal(int);
printf(“\n1.Producer\n2.Consumer\n3.Exit”);
while(1)
{
printf(“\nEnter your choice:”);
scanf(“%d”,&n);
switch(n)
{
case 1: if((mutex==1)&&(empty!=0))
producer();
else
printf(“Buffer is full!!”);
break;
case 2: if((mutex==1)&&(full!=0))
consumer();
else
printf(“Buffer is empty!!”);
break;
case 3:
exit(0);
break;
}
}
return 0;
}
int wait(int s)
{
return (–s);
}
int signal(int s)
{
return(++s);
}
void producer()
{
mutex=wait(mutex);
full=signal(full);
empty=wait(empty);
x++;
printf(“\nProducer produces the item %d”,x);
mutex=signal(mutex);
}
void consumer()
{
mutex=wait(mutex);
full=wait(full);
empty=signal(empty);
printf(“\nConsumer consumes item %d”,x);
x–;
mutex=signal(mutex);
}
Banker Algorithm
#include
int main()
{
// P0, P1, P2, P3, P4 are the Process names here
int n, m, i, j, k;
n = 5; // Number of processes
m = 3; // Number of resources
int alloc[5][3] = { { 0, 1, 0 }, // P0 // Allocation Matrix
{ 2, 0, 0 }, // P1
{ 3, 0, 2 }, // P2
{ 2, 1, 1 }, // P3
{ 0, 0, 2 } }; // P4
int max[5][3] = { { 7, 5, 3 }, // P0 // MAX Matrix
{ 3, 2, 2 }, // P1
{ 9, 0, 2 }, // P2
{ 2, 2, 2 }, // P3
{ 4, 3, 3 } }; // P4
int avail[3] = { 3, 3, 2 }; // Available Resources
int f[n], ans[n], ind =
0; for (k = 0; k
k++) {
f[k] = 0;
}
int need[n][m];
for (i = 0; i
for (j = 0; j
j++)
need[i][j] = max[i][j] – alloc[i][j];
}
int y = 0;
for (k = 0; k
for (i = 0; i
{ if (f[i] == 0) {
int flag = 0;
for (j = 0; j
{
if (need[i][j] >
avail[j]){ flag = 1;
break;
}
}
if (flag == 0) {
ans[ind++] =
i;
for (y = 0; y
avail[y] +=
alloc[i][y];
f[i] = 1;
}
}
}
}
printf(“Following is the SAFE Sequence\n”);
for (i = 0; i
printf(” P%d ->”,
ans[i]); printf(” P%d”, ans[n -1]);
return (0);
}
Best Fit
#include
//#include // Removed conio.h
#define max 25
int main() // Changed void main() to int main()
{
int frag[max], b[max], f[max], i, j, nb, nf, temp, lowest = 10000;
int bf[max] = {0}, ff[max] = {0}; // Initialize arrays
//clrscr(); // Removed clrscr()
printf(“\nEnter the number of blocks and files: “); // Combined prompts
scanf(“%d %d”, &nb, &nf); // Combined inputs
printf(“\nEnter the size of the blocks:\n”);
for (i = 0; i
{
printf(“Block %d: “, i + 1); // Adjusted index display
scanf(“%d”, &b[i]);
}
printf(“Enter the size of the files :-\n”);
for (i = 0; i
{
printf(“File %d: “, i + 1); // Adjusted index display
scanf(“%d”, &f[i]);
}
for (i = 0; i
{
for (j = 0; j
{
if (bf[j] != 1)
{
temp = b[j] – f[i];
if (temp >= 0)
{
if (lowest > temp)
{
ff[i] = j;
lowest = temp;
}
}
}
}
frag[i] = lowest;
bf[ff[i]] = 1;
lowest = 10000;
}
printf(“\nFile No\tFile Size\tBlock No\tBlock Size\tFragment\n”);
for (i = 0; i
printf(“%d\t\t%d\t\t%d\t\t%d\t\t%d\n”, i + 1, f[i], ff[i] + 1, b[ff[i]], frag[i]);
}
First Fit
#include
//#include // Removed conio.h
#define max 25
int main() // Changed void main() to int main()
{
int frag[max], b[max], f[max], i, j, nb, nf, temp, highest = 0;
int bf[max] = {0}, ff[max] = {0}; // Initialize arrays
//clrscr(); // Removed clrscr()
printf(“\n\tMemory Management Scheme – Worst Fit\n”);
printf(“Enter the number of blocks and files: “);
scanf(“%d %d”, &nb, &nf); // Combined inputs
printf(“\nEnter the size of the blocks:\n”);
for (i = 0; i
{
printf(“Block %d: “, i + 1); // Adjusted index display
scanf(“%d”, &b[i]);
}
printf(“Enter the size of the files:\n”);
for (i = 0; i
{
printf(“File %d: “, i + 1); // Adjusted index display
scanf(“%d”, &f[i]);
}
for (i = 0; i
{
for (j = 0; j
{
if (bf[j] != 1) // if bf[j] is not allocated
{
temp = b[j] – f[i];
if (temp >= 0)
{
if (highest
{
ff[i] = j;
highest = temp;
}
}
}
}
frag[i] = highest;
bf[ff[i]] = 1;
highest = 0;
}
printf(“\nFile_no:\tFile_size:\tBlock_no:\tBlock_size:\tFragment\n”);
for (i = 0; i
printf(“%d\t\t%d\t\t%d\t\t%d\t\t%d\n”, i + 1, f[i], ff[i] + 1, b[ff[i]], frag[i]);
FIFO page replacement
//Program to implement FIFO page replacement algorithm/
#include
#include
void main()
{
int i, j, k, f, pf=0, count=0, rs[25], m[10], n;
//clrscr();
printf(“\n Enter the length of reference string — “);
scanf(“%d”,&n);
printf(“\n Enter the reference string — “);
for(i=0;i
scanf(“%d”,&rs[i]);
printf(“\n Enter no. of frames — “);
scanf(“%d”,&f);
for(i=0;i
m[i]=-1;
printf(“\n The Page Replacement Processis — \n”);
for(i=0;i
{
for(k=0;k
{
if(m[k]==rs[i])
break;
}
if(k==f)
{
m[count++]=rs[i];
pf++;
}
for(j=0;j
printf(“\t%d”,m[j]);
if(k==f)
printf(“\tPF No. %d”,pf);
printf(“\n”);
if(count==f)
count=0;
}
printf(“\n The number of Page Faults using FIFO are %d”,pf);
//getch();
} //71,3,0,3,5,6,3
Least recently used(LRU)
#include
#include
void main()
{
int i, j , k, min, rs[25], m[10], count[10], flag[25], n, f, pf=0,
next=1;
//clrscr();
printf(“Enter the length ofreference string — “);
scanf(“%d”,&n);
printf(“Enter the reference string — “);
for(i=0;i
{
scanf(“%d”,&rs[i]);
flag[i]=0;
}
printf(“Enterthe number of frames — “);
scanf(“%d”,&f);
for(i=0;i
{
count[i]=0;
m[i]=-1;
}
printf(“\nThe Page Replacement process is– \n”);
for(i=0;i
{
for(j=0;j
{
if(m[j]==rs[i])
{
flag[i]=1;
count[j]=next;
next++;
}
}
if(flag[i]==0)
{
if(i
{
m[i]=rs[i];
count[i]=next;
next++;
}
else
{
min=0;
for(j=1;j
if(count[min] > count[j])
min=j;
m[min]=rs[i];
count[min]=next;
next++;
}
pf++;
}
for(j=0;j
printf(“%d\t”, m[j]);
if(flag[i]==0)
printf(“PF No. — %d” , pf);
printf(“\n”);
}
printf(“\nThe number of page faults using LRU are %d”,pf);
//getch();
} //7 1,3,0,3,5,6,3
FCFS Disk Scheduling
#include
int main()
{ int queue[20],n,head,i,j,k,seek=0,max,diff;
float avg;
printf(“Enter the max range of disk\n”);
scanf(“%d”,&max);
printf(“Enter the size of queue request\n”);
scanf(“%d”,&n);
printf(“Enter the queue of disk positions to be read\n”);
for(i=1;i
scanf(“%d”,&queue[i]);
printf(“Enter the initial head position\n”);
scanf(“%d”,&head);
queue[0]=head;
for(j=0;j
{ diff=abs(queue[j+1]-queue[j]); seek+=diff;
printf(“Disk head moves from %d to %d with seek %d\n”,queue[j],queue[j+1],diff);
}
printf(“Total seek time is %d\n”,seek);
avg=seek/(float)n;
printf(“Average seek time is %f\n”,avg);
return 0;
} //255 5 176 78 60 34 111 0
Scan disk scheduling
#include
int main() {
int queue[20], n, head, i, j, seek = 0, max, diff, temp, queue1[20], queue2[20], temp1 = 0, temp2 = 0;
float avg;
printf(“Enter the max range of disk\n”);
scanf(“%d”, &max);
printf(“Enter the initial head position\n”);
scanf(“%d”, &head);
printf(“Enter the size of queue request\n”);
scanf(“%d”, &n);
printf(“Enter the queue of disk positions to be read\n”);
for (i = 0; i
scanf(“%d”, &temp);
if (temp >= head) {
queue1[temp1] = temp;
temp1++;
} else {
queue2[temp2] = temp;
temp2++;
}
}
// Sorting queue1 in ascending order
for (i = 0; i
for (j = i + 1; j
if (queue1[i] > queue1[j]) {
temp = queue1[i];
queue1[i] = queue1[j];
queue1[j] = temp;
}
}
}
// Sorting queue2 in descending order
for (i = 0; i
for (j = i + 1; j
if (queue2[i]
temp = queue2[i];
queue2[i] = queue2[j];
queue2[j] = temp;
}
}
}
// Merging sorted queues into a single queue
for (i = 1, j = 0; j
queue[i] = queue1[j];
queue[i++] = max;
for (j = 0; j
queue[i] = queue2[j];
queue[i++] = 0;
queue[0] = head;
// Calculating seek time
for (j = 0; j
diff = abs(queue[j + 1] – queue[j]);
seek += diff;
printf(“Disk head moves from %d to %d with seek %d\n”, queue[j], queue[j + 1], diff);
}
printf(“Total seek time is %d\n”, seek);
avg = (float)seek / n;
printf(“Average seek time is %f\n”, avg);
return 0;
}//25505 12 215 48 110 83
C-Scan disk scheduling
#include
int main() {
int queue[20], n, head, i, j, seek = 0, max, diff, temp, queue1[20], queue2[20], temp1 = 0, temp2 = 0;
float avg;
printf(“Enter the max range of disk\n”);
scanf(“%d”, &max);
printf(“Enter the initial head position\n”);
scanf(“%d”, &head);
printf(“Enter the size of queue request\n”);
scanf(“%d”, &n);
printf(“Enter the queue of disk positions to be read\n”);
for (i = 0; i
scanf(“%d”, &temp);
if (temp >= head) {
queue1[temp1] = temp;
temp1++;
}
else {
queue2[temp2] = temp;
temp2++;
}
}
// Sorting queue1 in ascending order
for (i = 0; i
for (j = i + 1; j
if (queue1[i] > queue1[j]) {
temp = queue1[i];
queue1[i] = queue1[j];
queue1[j] = temp;
}
}
}
// Sorting queue2 in ascending order
for (i = 0; i
for (j = i + 1; j
if (queue2[i] > queue2[j]) {
temp = queue2[i];
queue2[i] = queue2[j];
queue2[j] = temp;
}
}
}
// Merging sorted queues into a single queue
for (i = 1, j = 0; j
queue[i] = queue1[j];
queue[i++] = max;
for (j = 0; j
queue[i] = queue2[j];
queue[i++] = 0;
queue[0] = head;
// Calculating seek time
for (j = 0; j
diff = abs(queue[j + 1] – queue[j]);
seek += diff;
printf(“Disk head moves from %d to %d with seek %d\n”, queue[j], queue[j + 1], diff);
}
printf(“Total seek time is %d\n”, seek);
avg = (float)seek / n;
printf(“Average seek time is %f\n”, avg);
return 0;
}// 25504 254 9 84 110