CPU Scheduling Design and implement a program that simulates the non-preemptive
ID: 3547388 • Letter: C
Question
CPU Scheduling
Design and implement a program that simulates the non-preemptive Shortest Job First (SJF) CPU scheduling algorithm. Assume processes will arrive at different random time slots.
The PCB Structure must include the following items:
struct PCB
{
int pid; //Process ID ,Generated Randomly
int iat; //Process Arrival Time, Generated Randomly
int cpu_time; //CPU Burst ,Generated Randomly
int w_time; //Waiting Time ,Calculated
int job_no; //Job Number, Sequence 1,2,3,
char status[10]; //Ready, Runnable or Complete
struct PCB *nextptr; //Pointer to next Node
};
The input to your program is the number of processes to schedule within an interactive screen. Your program must be able to repeat this operation depending on user request (Y, N).
Display the contents of the SJF queue upon each process execution.
Find the average waiting time and total execution time of your program in s.
please use this way of building the program:
1- building ready queue
2- scheme of sorting
3- WT (waiting time)
4- AVT (average waiting time)
you edit this code FCFS to make non-preemptive shortest job first:
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
struct queueNode
{
int pid;
int cpuburst;
int iat;
int wt;
struct queueNode *nextPtr;
};
typedef struct queueNode QUEUENODE;
typedef QUEUENODE *QUEUENODEPTR;
void computeWT (QUEUENODEPTR);
int main()
{
QUEUENODEPTR headPtr=NULL, tailPtr=NULL;
int pid, cpuburst, iat, wt;
int i,n;
printf("Enter no of Jobs: ");
scanf("%d",&n);
srand(time(NULL));
for(i=1;i<=n;i++)
{
pid=rand() % 10000 + 1;
cpuburst=rand() % 5 + 2;
iat=rand() % 4 + 1;
QUEUENODEPTR newPtr;
//newPtr=new QUEUENODE;
newPtr=malloc(sizeof(QUEUENODE));
/* Under Linux use newPtr=malloc(sizeof(QUEUENODE)) to create a new node */
/* To free the memory use free(newPtr) */
if(newPtr !=NULL)
{
newPtr->pid=pid;
newPtr->cpuburst=cpuburst;
newPtr->iat=iat;
newPtr->nextPtr=NULL;
if(i==1)
{
headPtr=newPtr;
tailPtr=newPtr;
}
else
{
tailPtr->nextPtr=newPtr;
tailPtr=newPtr;
}
}
else
printf("No memory Available ");
}
if(headPtr==NULL)
printf("The Queue is Empty: ");
else
{
//----------------Bubble Sort Based on FCFS----------------
QUEUENODEPTR Ptr1=headPtr, Ptr2;
while (Ptr1->nextPtr!=NULL)
{
Ptr2=Ptr1->nextPtr;
while (Ptr2!=NULL)
{
if (Ptr2->iat<Ptr1->iat)
{
iat=Ptr1->iat;
Ptr1->iat=Ptr2->iat;
Ptr2->iat=iat;
cpuburst=Ptr1->cpuburst;
Ptr1->cpuburst=Ptr2->cpuburst;
Ptr2->cpuburst=cpuburst;
pid=Ptr1->pid;
Ptr1->pid=Ptr2->pid;
Ptr2->pid=pid;
}
Ptr2=Ptr2->nextPtr;
}
Ptr1=Ptr1->nextPtr;
}
//----------------Compute wt -----------------------
computeWT(headPtr);
//----------------Compute AWT -----------------------
float SUM=0;
QUEUENODEPTR currentPtr;
currentPtr=headPtr;
while(currentPtr != NULL)
{
SUM=SUM+currentPtr->wt;
currentPtr=currentPtr->nextPtr;
}
//---------------------Starting FCFS Service--------------------
while (headPtr!=NULL)
{
printf("The Ready Queue is: ");
printf("pid iat cpu wt ");
headPtr->wt=0; //set wt=0 for the process upon service
currentPtr=headPtr;
while(currentPtr != NULL)
{
printf("%d %d %d %d ",currentPtr->pid, currentPtr->iat,currentPtr->cpuburst, currentPtr->wt);
currentPtr=currentPtr->nextPtr;
}
printf("Servicing process id %d for %d seconds ", headPtr->pid, headPtr->cpuburst);
sleep(headPtr->cpuburst);
headPtr=headPtr->nextPtr;
}
printf("Done Processing ");
printf("Average Waiting Time=%f ",SUM/n);
}
return(0);
}
void computeWT (QUEUENODEPTR headPtr){
QUEUENODEPTR currentPtr=headPtr, ptrWt;
int clock=0;
while (currentPtr!=NULL)
{
if ((clock-currentPtr->iat)<0)
{
clock=currentPtr->iat;
currentPtr->wt=0;
}
else
currentPtr->wt=clock-currentPtr->iat;
clock=clock+headPtr->cpuburst;
//compare processes for iat<=clock
ptrWt=currentPtr->nextPtr;
while (ptrWt!=NULL)
{
if (ptrWt->iat<=clock)
{
ptrWt->wt=clock-ptrWt->iat;
clock=clock+ptrWt->cpuburst;
currentPtr=ptrWt;
}
ptrWt=ptrWt->nextPtr;
}
currentPtr=currentPtr->nextPtr;
}
}
Explanation / Answer
can you post the anwser of the qustion