FCFS CPU Scheduling / Process Scheduling Algorithm

/*
FCFS CPU Scheduling Algorithm / Process Scheduling Algorithm
Author : Charudatta Ekbote ( Space Computer Education, SpaceComp Tutorials)
Note   : 
1) This program is developed to simulate FCFS Process Scheduling or CPU Scheduling Algorithm 
2) Program demonstrates the short term scheduler's (STS) working.
3) Program is based on input from user (dynamic data).
4) Program is not checking basic validations for any inputs. 
5) Program is desgined to work under ubuntu ( or any linux platform but not for window platform)
6) Program generates Gantt Chart and also outputs Average Turn Around Time, Waiting Time
*/

#include <stdio.h>
#include <stdlib.h>

int nJobs;
struct JobTable
{
int cpuBurst, arrivalTime, nextArrivalTime, completionTime, totalCpuUsed;
} *jt;

struct node
{
int pid, cpuBurst, priority;
struct node *next;
} *head, *end, *cj;   // cj is current job selected by STS

void AppendToReadyQueue(int pid, int cpuBurst)
{
struct node *newnode;
newnode = malloc(sizeof(struct node));
newnode->pid = pid;
newnode->cpuBurst = cpuBurst;
newnode->next = NULL;
if( head == NULL )
head = end = newnode;
else
{
end->next = newnode;
end = newnode;
}
}

int time;
void DisplayReadyQueue()
{
struct node *temp = head;
printf("\033[%d;%df",1,15);
printf("@time = %d [", time);
while( temp )
{
printf("P%d(%d)->", temp->pid,temp->cpuBurst);
temp = temp->next;
}
printf("null]                                    ");
}

void LoadJobsInReadyQueue()
{
int i;
for(i=0; i<nJobs; ++i)
{
if( jt[i].nextArrivalTime == time )
AppendToReadyQueue(i, jt[i].cpuBurst);
}
}

int IncompleteJobs()
{
int i;
for(i=0; i<nJobs; ++i)
{
if( jt[i].completionTime == 0 )
return 1;
}

return 0;
}
           
struct node * FCFS()
{
return head;
}
           
int DeleteFromReadyQueue()
{
struct node *temp  = head;
head = temp->next;
int pid = temp->pid;
free(temp);
return pid;
}

void GetJobPoolData()
{
int i;
printf("enter total jobs in job pool : ");
scanf("%d",&nJobs);
jt = malloc(sizeof(struct JobTable) * nJobs);

for(i=0; i<nJobs; ++i)
{
printf("\nenter job%d details : \n",i);
printf("1st cpu burst : " ); scanf("%d",&jt[i].cpuBurst);
printf("arrival time  : " ); scanf("%d",&jt[i].arrivalTime);

jt[i].totalCpuUsed = jt[i].cpuBurst;
jt[i].nextArrivalTime = jt[i].arrivalTime;
jt[i].completionTime = 0;
}
}

main()
{
int r=5,c=1,pid;
system("clear");

GetJobPoolData();
system("clear");

while( IncompleteJobs() )
{
LoadJobsInReadyQueue();
DisplayReadyQueue();

if( cj==NULL )
cj = FCFS();

printf("\033[%d;%df",r,c);
printf("%2d",time);
++time;

if( cj != NULL )
{
printf("\033[%d;%df",r-1,c);
printf("P%d",cj->pid);

--cj->cpuBurst;
if( cj->cpuBurst == 0 )
{
pid = DeleteFromReadyQueue();
cj = NULL;

int r = random()%4;  // replace random()%4 with 0 to avoid next cpu burst generations
if( r == 0 )
jt[pid].completionTime = time;
else
{
jt[pid].cpuBurst = r;
jt[pid].totalCpuUsed += r;
jt[pid].nextArrivalTime = time + 2;
}
}
}
c+=4;
if( c>70 )
{
r += 4;
c = 1;
}
getchar();getchar();
}

printf("\033[%d;%df",r,c);
printf("%2d",time);
printf("\033[%d;%df",r-1,c);
printf("P%d",pid);

DisplayReadyQueue();
getchar();getchar();

int totalTat =0, totalWaitingTime =0,tat, waiting_time,i;
c= 1;
printf("\033[%d;%df",r+5,c);
printf("pid\tcpu_used\tarrival\t\tcompletion\ttat\twaiting\n");
for(i=0; i<nJobs; ++i)
{
tat = jt[i].completionTime-jt[i].arrivalTime;
waiting_time = tat - jt[i].totalCpuUsed;

printf("P%d\t%d\t\t%d\t\t1%d\t\t%d\t%d\n",i,jt[i].totalCpuUsed,jt[i].arrivalTime,jt[i].completionTime, tat, waiting_time);
totalTat += tat;
totalWaitingTime += waiting_time;
}

printf("\nAvg Turn Around Time : %f",(float) totalTat / nJobs );
printf("\nAvg Waiting Time : %f",(float) totalWaitingTime / nJobs );
getchar();getchar();
}

Banker Algorithm (Dynamic Code for Slip 8,23,24)

/*
Banker Algorithm ( Dynamic )
Author : Charudatta Ekbote ( Space Computer Education, SpaceComp Tutorials)
Note   : 
1) This program is developed to simulate banker's algorithm to demonstrate deadlock avoidance approach.
2) Program is based on input from user (dynamic data).
3) Program is not doing any validation-check on input data.
4) Program is desgined to work under ubuntu ( or any linux platform but not for window platform)
*/

#include <stdio.h>
#include <stdlib.h>
#define print 1
#define noprint 0
#define notfound 0


int **max,**allocation,**need;
int *available,*request,*finish;
int processes, resources;

void allocateMemory()
{
int i,j;
printf("enter number of processes : ");
scanf("%d",&processes);
printf("enter number of resources : ");
scanf("%d",&resources);

//request array memory allocation
request = malloc(sizeof(int) * resources );

//available array memory allocation
available = malloc(sizeof(int) * resources );

//need array memory allocation
need = malloc(sizeof(int*) * processes);
for(i=0; i<processes; ++i)
need[i] = malloc( sizeof(int) * resources );

//max array memory allocation
max = malloc(sizeof(int*) * processes);
for(i=0; i<processes; ++i)
max[i] = malloc( sizeof(int) * resources );

//allocation array memory allocation
allocation = malloc(sizeof(int*) * processes);
for(i=0; i<processes; ++i)
allocation[i] = malloc( sizeof(int) * resources );

//get inputs for max requirements
printf("\nenter contents for max requirement of each process\n");
for(i=0; i<processes; ++i)
{
for(j=0; j<resources; ++j)
{
printf("max requirement of process P%d for resource%d :",i,j);
scanf("%d",&max[i][j]);
}
printf("\n");
}

//get inputs for allocation requirements
printf("\nenter contents for current allocation of resources for each process\n");
for(i=0; i<processes; ++i)
{
for(j=0; j<resources; ++j)
{
printf("current allocation of process %d for resource%d :",i,j);
scanf("%d",&allocation[i][j]);
}
printf("\n");
}

//get inputs for availablity requirements
printf("\nenter contents for availability of resources\n");
for(j=0; j<resources; ++j)
{
printf("availability for resource%d :",j);
scanf("%d",&available[j]);
}
}

void saveResourceAllocationState()
{
FILE *fp;
fp = fopen("temp.bak","w");
fwrite(available,sizeof(int) * resources,1,fp);
fclose(fp);
}

void restoreResourceAllocationState()
{
FILE *fp;
fp = fopen("temp.bak","r");
fread(available,sizeof(int) * resources,1,fp);
fclose(fp);
}

void calculateNeedArray(int param)
{
int i,j;
if(param == print)
printf("\tR1\tR2\tR3\n");

for(i=0; i<processes; ++i)
{
printf("\t");
for(j=0; j<resources; ++j)
{
need[i][j] = max[i][j] - allocation[i][j];
if( param == print )
printf("%d\t",need[i][j]);
}
if( param == print )
printf("\n");
}
}

int isRequestValid(int i)
{
int j;
for(j=0; j<resources; ++j)
{
if( request[j] > need[i][j]  || request[j] > available[j] )
return 0;
}

return 1;
}

int isNeedValid(int i)
{
int j;
for(j=0; j<resources; ++j)
{
if( need[i][j] > available[j] )
return 0;
}

return 1;
}

int safeSequence(int param)
{
int *finish;
int stockChanging, cnt=0, i ,j;
saveResourceAllocationState();

finish = calloc(sizeof(int), processes);
if( param == print )
printf("\t<");
do
{
stockChanging = 0;
for(i=0; i<processes; ++i)
{
if( finish[i] == 1 )
continue;

if( isNeedValid(i) == 1 )
{
for(j=0; j<resources; ++j)
available[j] += allocation[i][j];

finish[i] = 1;
++cnt;

stockChanging = 1;
if( param == print )
printf("P%d, ", i);
}
}
} while(stockChanging);

restoreResourceAllocationState();
if( cnt == processes )
{
if( param == print )
printf(">\n");
return 1;
}
else
{
printf("\n");
return 0;
}
}

int menu()
{
int ch;
system("clear");
printf("\n\t0) Exit");
printf("\n\t1) Accept Resource Request");
printf("\n\t2) Print Available Resources");
printf("\n\t3) Print Safe Sequence");
printf("\n\t4) Print Need Array");
printf("\n\t5) Print Resource Allocation State");
printf("\n\tEnter Choice : ");
scanf("%d",&ch);
return ch;//Banker Algorithm ( Dynamic )
//Author : Charudatta Ekbote ( Space Computer Education, SpaceComp Tutorials)
//Note   : This program is developed to simulate banker's algorithm to demonstrate deadlock avoidance approach.
//   Program is based on input from user (dynamic data).
//   Program is not doing basic validations for max, allocation, available or request array inputs. 
//   Program is desgined to work under ubuntu ( or any linux platform but not for window platform)


#include <stdio.h>
#include <stdlib.h>
#define print 1
#define noprint 0
#define notfound 0


int **max,**allocation,**need;
int *available,*request,*finish;
int processes, resources;

void allocateMemory()
{
int i,j;
printf("enter number of processes : ");
scanf("%d",&processes);
printf("enter number of resources : ");
scanf("%d",&resources);

//request array memory allocation
request = malloc(sizeof(int) * resources );

//available array memory allocation
available = malloc(sizeof(int) * resources );

//need array memory allocation
need = malloc(sizeof(int*) * processes);
for(i=0; i<processes; ++i)
need[i] = malloc( sizeof(int) * resources );

//max array memory allocation
max = malloc(sizeof(int*) * processes);
for(i=0; i<processes; ++i)
max[i] = malloc( sizeof(int) * resources );

//allocation array memory allocation
allocation = malloc(sizeof(int*) * processes);
for(i=0; i<processes; ++i)
allocation[i] = malloc( sizeof(int) * resources );

//get inputs for max requirements
printf("\nenter contents for max requirement of each process\n");
for(i=0; i<processes; ++i)
{
for(j=0; j<resources; ++j)
{
printf("max requirement of process P%d for resource%d :",i,j);
scanf("%d",&max[i][j]);
}
printf("\n");
}

//get inputs for allocation requirements
printf("\nenter contents for current allocation of resources for each process\n");
for(i=0; i<processes; ++i)
{
for(j=0; j<resources; ++j)
{
printf("current allocation of process %d for resource%d :",i,j);
scanf("%d",&allocation[i][j]);
}
printf("\n");
}

//get inputs for availablity requirements
printf("\nenter contents for availability of resources\n");
for(j=0; j<resources; ++j)
{
printf("availability for resource%d :",j);
scanf("%d",&available[j]);
}
}

void saveResourceAllocationState()
{
FILE *fp;
fp = fopen("temp.bak","w");
fwrite(available,sizeof(int) * resources,1,fp);
fclose(fp);
}

void restoreResourceAllocationState()
{
FILE *fp;
fp = fopen("temp.bak","r");
fread(available,sizeof(int) * resources,1,fp);
fclose(fp);
}

void calculateNeedArray(int param)
{
int i,j;
if(param == print)
printf("\tR1\tR2\tR3\n");

for(i=0; i<processes; ++i)
{
printf("\t");
for(j=0; j<resources; ++j)
{
need[i][j] = max[i][j] - allocation[i][j];
if( param == print )
printf("%d\t",need[i][j]);
}
if( param == print )
printf("\n");
}
}

int isRequestValid(int i)
{
int j;
for(j=0; j<resources; ++j)
{
if( request[j] > need[i][j]  || request[j] > available[j] )
return 0;
}

return 1;
}

int isNeedValid(int i)
{
int j;
for(j=0; j<resources; ++j)
{
if( need[i][j] > available[j] )
return 0;
}

return 1;
}

int safeSequence(int param)
{
int *finish;
int stockChanging, cnt=0, i ,j;
saveResourceAllocationState();

finish = calloc(sizeof(int), processes);
if( param == print )
printf("\t<");
do
{
stockChanging = 0;
for(i=0; i<processes; ++i)
{
if( finish[i] == 1 )
continue;

if( isNeedValid(i) == 1 )
{
for(j=0; j<resources; ++j)
available[j] += allocation[i][j];

finish[i] = 1;
++cnt;

stockChanging = 1;
if( param == print )
printf("P%d, ", i);
}
}
} while(stockChanging);

restoreResourceAllocationState();
if( cnt == processes )
{
if( param == print )
printf(">\n");
return 1;
}
else
{
printf("\n");
return 0;
}
}

int menu()
{
int ch;
system("clear");
printf("\n\t0) Exit");
printf("\n\t1) Accept Resource Request");
printf("\n\t2) Print Available Resources");
printf("\n\t3) Print Safe Sequence");
printf("\n\t4) Print Need Array");
printf("\n\t5) Print Resource Allocation State");
printf("\n\tEnter Choice : ");
scanf("%d",&ch);
return ch;
}

void printResourceAllocationState()
{
int r=10, c=5,temp,i,j;

printf("\033[%d;%df",r-1,c);
printf("max required");
for(i=0; i<processes; ++i)
{
c = 5;
for(j=0; j<resources; ++j)
{
printf("\033[%d;%df",r+i,c+=2);
printf("%d",max[i][j]);
}
printf("\n");
}

temp = c+10;
printf("\033[%d;%df",r-1,c+10);
printf("current allocated");
for(i=0; i<processes; ++i)
{
c = temp;
printf("\033[%d;%df",r+i,c);
for(j=0; j<resources; ++j)
{
printf("\033[%d;%df",r+i,c+=2);
printf("%d\t",allocation[i][j]);
}
printf("\n");
}


temp = c+20;
printf("\033[%d;%df",r-1,c+20);
printf("future need");
for(i=0; i<processes; ++i)
{
c = temp;
printf("\033[%d;%df",r+i,c);
for(j=0; j<resources; ++j)
{
printf("\033[%d;%df",r+i,c+=2);
printf("%d\t",max[i][j] - allocation[i][j]);
}
printf("\n");
}
}

main()
{
int ch,i,j;

allocateMemory();

calculateNeedArray(noprint);
if( safeSequence(noprint) == notfound )
{
printf("system is not in Safe State...exiting !");
return;
}

while((ch=menu())!=0)
{
if(ch==5)
{
printResourceAllocationState();
getchar();getchar();
}
else
if(ch==4)
{
calculateNeedArray(print);
getchar();getchar();
}
else
if(ch==3)
{
safeSequence(print);
getchar();getchar();
}
else
if(ch==2)
{
printf("\tR1\tR2\tR3\n");
for(j=0; j<resources; ++j)
printf("\t%d",available[j]);

getchar();getchar();
}
else
if(ch==1)
{
int i;
printf("\n\tenter process number : " );
scanf("%d",&i);

for( j=0; j<resources; ++j )
{
printf("\tresource_%d qty : ",j);
scanf("%d",&request[j]);
}

if( isRequestValid(i) )
{
for(j=0; j<resources; ++j)
{
available[j] -= request[j];
need[i][j] -= request[j];
allocation[i][j] += request[j];
}

if( safeSequence(noprint) == notfound )
{
printf("\tSorry, resources can not be given immediately !\n");
for(j=0; j<resources; ++j)
{
available[j] += request[j];
need[i][j] += request[j];
allocation[i][j] -= request[j];
}
}
else
printf("\tCongratulations process P%d got the resources\n",i);
}
else
printf("\tOops, request is not valid, can not be completed");

getchar();getchar();
}
}
}

}

void printResourceAllocationState()
{
int r=10, c=5,temp,i,j;

printf("\033[%d;%df",r-1,c);
printf("max required");
for(i=0; i<processes; ++i)
{
c = 5;
for(j=0; j<resources; ++j)
{
printf("\033[%d;%df",r+i,c+=2);
printf("%d",max[i][j]);
}
printf("\n");
}

temp = c+10;
printf("\033[%d;%df",r-1,c+10);
printf("current allocated");
for(i=0; i<processes; ++i)
{
c = temp;
printf("\033[%d;%df",r+i,c);
for(j=0; j<resources; ++j)
{
printf("\033[%d;%df",r+i,c+=2);
printf("%d\t",allocation[i][j]);
}
printf("\n");
}


temp = c+20;
printf("\033[%d;%df",r-1,c+20);
printf("future need");
for(i=0; i<processes; ++i)
{
c = temp;
printf("\033[%d;%df",r+i,c);
for(j=0; j<resources; ++j)
{
printf("\033[%d;%df",r+i,c+=2);
printf("%d\t",max[i][j] - allocation[i][j]);
}
printf("\n");
}
}

main()
{
int ch,i,j;

allocateMemory();

calculateNeedArray(noprint);
if( safeSequence(noprint) == notfound )
{
printf("system is not in Safe State...exiting !");
return;
}

while((ch=menu())!=0)
{
if(ch==5)
{
printResourceAllocationState();
getchar();getchar();
}
else
if(ch==4)
{
calculateNeedArray(print);
getchar();getchar();
}
else
if(ch==3)
{
safeSequence(print);
getchar();getchar();
}
else
if(ch==2)
{
printf("\tR1\tR2\tR3\n");
for(j=0; j<resources; ++j)
printf("\t%d",available[j]);

getchar();getchar();
}
else
if(ch==1)
{
int i;
printf("\n\tenter process number : " );
scanf("%d",&i);

for( j=0; j<resources; ++j )
{
printf("\tresource_%d qty : ",j);
scanf("%d",&request[j]);
}

if( isRequestValid(i) )
{
for(j=0; j<resources; ++j)
{
available[j] -= request[j];
need[i][j] -= request[j];
allocation[i][j] += request[j];
}

if( safeSequence(noprint) == notfound )
{
printf("\tSorry, resources can not be given immediately !\n");
for(j=0; j<resources; ++j)
{
available[j] += request[j];
need[i][j] += request[j];
allocation[i][j] -= request[j];
}
}
else
printf("\tCongratulations process P%d got the resources\n",i);
}
else
printf("\tOops, request is not valid, can not be completed");

getchar();getchar();
}
}
}

Banker Algorithm (Static Code for Slip 8, 23 and 24)

/*

Banker Algorithm (Static i.e. user need not input values)

Author : Charudatta Ekbote ( Space Computer Education, SpaceComp Tutorials)

Note about program :

1) This program is developed to simulate banker's algorithm to demonstrate deadlock avoidance approach.

2) Program is using some static data for 5 processes and 3 resources.

3) Program is not doing any validation-check on input data.
4) Program is desgined to work under ubuntu ( or any linux platform but not for window platform)
*/

#include <stdio.h>

#define processes 5

#define resources 3

#define print 1

#define noprint 0

#define notfound 0

int max[processes][resources] = { {7,5,3}, {3,2,2}, {9,0,2}, {2,2,2}, {4,3,3} };

int allocation[processes][resources] = { {0,1,0}, {2,0,0}, {3,0,2}, {2,1,1}, {0,0,2} };

int need[processes][resources];

int available[resources] = { 3,3,2 };

int request[resources] = { 0,0,0 };

void saveResourceAllocationState()

{

FILE *fp;

fp = fopen("temp.bak","w");

fwrite(available,sizeof(available),1,fp);

fclose(fp);

}

void restoreResourceAllocationState()

{

FILE *fp;

fp = fopen("temp.bak","r");

fread(available,sizeof(available),1,fp);

fclose(fp);

}

void calculateNeedArray(int param)

{

int i,j;

if(param == print)

printf("\tR1\tR2\tR3\n");

for(i=0; i<processes; ++i)

{

printf("\t");

for(j=0; j<resources; ++j)

{

need[i][j] = max[i][j] - allocation[i][j];

if( param == print )

printf("%d\t",need[i][j]);

}

if( param == print )

printf("\n");

}

}

int isRequestValid(int i)

{

int j;

for(j=0; j<resources; ++j)

{

if( request[j] > need[i][j]  || request[j] > available[j] )

return 0;

}   

return 1;

}

int isNeedValid(int i)

{

int j;

for(j=0; j<resources; ++j)

{

if( need[i][j] > available[j] )

return 0;

}   

return 1;

}

int safeSequence(int param)

{

int finish[processes] = {0,0,0,0,0};

int stockChanging, cnt=0, i ,j;

saveResourceAllocationState();

if( param == print )

printf("\t<");

do

{

stockChanging = 0;

for(i=0; i<processes; ++i)

{

if( finish[i] == 1 )

continue;

if( isNeedValid(i) == 1 )

{

for(j=0; j<resources; ++j)

available[j] += allocation[i][j];

  

finish[i] = 1;

++cnt;

 

stockChanging = 1;

if( param == print )

printf("P%d, ", i);

}

}

} while(stockChanging);

restoreResourceAllocationState();

if( cnt == processes )

{

if( param == print )

printf(">\n");

return 1;

}

else

{

printf("\n");

return 0;

}

}

int menu()

{

int ch;

system("clear");

printf("\n\t0) Exit");

printf("\n\t1) Accept Resource Request");

printf("\n\t2) Print Available Resources");

printf("\n\t3) Print Safe Sequence");

printf("\n\t4) Print Need Array");

printf("\n\t5) Print Resource Allocation State");

printf("\n\tEnter Choice : ");

scanf("%d",&ch);

return ch;

}

void printResourceAllocationState()

{

int r=10, c=5,temp,i,j;

printf("\033[%d;%df",r-1,c);

printf("max required");

for(i=0; i<processes; ++i)

{

c = 5;

for(j=0; j<resources; ++j)

{

printf("\033[%d;%df",r+i,c+=2);

printf("%d",max[i][j]);

}

printf("\n");

}

temp = c+10;

printf("\033[%d;%df",r-1,c+10);

printf("current allocated");

for(i=0; i<processes; ++i)

{

c = temp;

printf("\033[%d;%df",r+i,c);

for(j=0; j<resources; ++j)

{

printf("\033[%d;%df",r+i,c+=2);

printf("%d\t",allocation[i][j]);

}

printf("\n");

}

temp = c+20;

printf("\033[%d;%df",r-1,c+20);

printf("future need");

for(i=0; i<processes; ++i)

{

c = temp;

printf("\033[%d;%df",r+i,c);

for(j=0; j<resources; ++j)

{

printf("\033[%d;%df",r+i,c+=2);

printf("%d\t",max[i][j] - allocation[i][j]);

}

printf("\n");

}

}

main()

{

int ch,i,j;

calculateNeedArray(noprint);

if( safeSequence(noprint) == notfound )

{

printf("system is not in Safe State...exiting !");

return;

}

while((ch=menu())!=0)

{

if(ch==5)

{

printResourceAllocationState();

getchar();getchar();

}

else

if(ch==4)

{

calculateNeedArray(print);

getchar();getchar();

}

else

if(ch==3)

{

safeSequence(print);

getchar();getchar();

}33

else

if(ch==2)

{

printf("\tR1\tR2\tR3\n");

for(j=0; j<resources; ++j)

printf("\t%d",available[j]);

getchar();getchar();

}

else

if(ch==1)

{

int i;

printf("\n\tenter process number : " );  

scanf("%d",&i);

for( j=0; j<resources; ++j )

  {

   printf("\tresource_%d qty : ",j);

   scanf("%d",&request[j]);

  }

  if( isRequestValid(i) )

  {

   for(j=0; j<resources; ++j)  

   {

available[j] -= request[j];

need[i][j] -= request[j];

allocation[i][j] += request[j];  

}

   if( safeSequence(noprint) == notfound )

   {

    printf("\tSorry, resources can not be given immediately !\n");

for(j=0; j<resources; ++j)  

{

available[j] += request[j];

need[i][j] += request[j];

allocation[i][j] -= request[j];  

}

   }

else

printf("\tCongratulations process P%d got the resources\n",i);

}

else

printf("\tOops, request is not valid, can not be completed");

 

getchar();getchar();

}

}

}