Now extend this program to perform other three basic CPU scheduling algorithms, namely SJF, PR, RR (quantum)

Implement a SJF_Scheduling() function and call it to print the order of completed processes. Until the linked list is empty, this function simply searches the linked list and removes the PCB with minimum CPUburst from the list. For each PCB, it perfroms the same operations as in FIFO_Scheduling: Do context-switch, Data collection, Free PCB. Finally, print the performance metrics as before.

Implement a PR_Scheduling() function and call it to print the order of completed processes. Until the linked list is empty, this function simply searches the list and removes the process with maximum ProcPR (assume higher the value higher the priority) from the list. (Note: this is similar to the SJF_Scheduling() except finding maximum ProcPR rather than finding minimum CPUBurst, so you can use almost the same programming logic.) For each PCB, it perfroms the same operations as in FIFO_Scheduling: Do context-switch, Data collection, Free PCB. Finally, print the performance metrics as before.

Implement a RR_Scheduling() function and call it to print the order of completed processes. As in FIFO_Scheduling, until the linked list is empty, this function simply removes the PCB from the head of the linked list, but then to take into account the given quantum time it performs the followingsDo context-switching:

copy PCB->Reg[8] into CPUreg[8],

suppose some work is done on CPU (e.g, increment each CPUreg by one),

copy CPUreg[8] into PCB->Reg[8]

If PCB->CPUburst <= quantum, then

PCB->waitingTime = PCB->waitingTime + CLOCK - PCB->queueEnterClock;

Total_waiting_time = Total_waiting_time + PCB->waitingTime ;

CLOCK = CLOCK + PCB->CPUburst;

Total_turnaround_time = Total_turnaround_time + CLOCK;

Total_job = Total_job + 1;

Free PCB. Since there is no more CPUburst or I/O burst, this process is terminated here!

Else that is PCB->CPUburst > quantum,

PCB->waitingTime = PCB->waitingTime + CLOCK - PCB->queueEnterClock;

CLOCK = CLOCK + quantum;

PCB->CPUburst = PCB->CPUburst - quantum;

PCB->queueEnterClock = CLOCK;

Insert this PCB back at the end of the link list.

Finally, print the perfromance metrics as mentioned before:

Total_waiting_time / Total_job,

Total_turnaround_time / Total_job,

Total_job / CLOCK

Code to extend:

#include #include #include #include

struct PCB *Tail=NULL; struct PCB *Head=NULL; int Total_job=0; int Total_turnaround_time=0; int Total_waiting_time=0; int CLOCK=0; int CPUreg[8] = {0}; char print; int digitarray[100]; int count = 0; int maxcount = 0;

struct PCB { int ProcId; int ProcPR; int CPUburst; int Reg[8]; int queueEnterClock; int waitingTime; /* other info */ struct PCB *next; };

void append(struct PCB** head_ref, int ProcessID, int ProcessPrio, int CPUBurstT) { struct PCB* new_node = (struct PCB*) malloc(sizeof(struct PCB));

struct PCB *last = *head_ref; new_node->ProcId = ProcessID; new_node->ProcPR = ProcessPrio; new_node->CPUburst = CPUBurstT; new_node->queueEnterClock = 0; new_node->waitingTime = 0; new_node->Reg[8] = ProcessID;

new_node->next = NULL;

if (*head_ref == NULL) { *head_ref = new_node; return; }

while (last->next != NULL) last = last->next;

last->next = new_node; return; }

void runLL(struct PCB *pcb) { while (pcb != NULL) { CPUreg[8] = pcb->Reg[8]; pcb->Reg[8] = CPUreg[8]; pcb->waitingTime = pcb->waitingTime + CLOCK - pcb->queueEnterClock; Total_waiting_time = Total_waiting_time + pcb->waitingTime; CLOCK = CLOCK + pcb->CPUburst; Total_turnaround_time = Total_turnaround_time + CLOCK; Total_job = Total_job + 1; pcb = pcb->next; } }

void printalg() { printf("Input File Name : input1.txt "); printf("CPU Scheduling Alg : FIFO "); }

void printprefM() { float AWT = (float)Total_waiting_time / (float)Total_job; float ATT = (float)Total_turnaround_time / (float)Total_job; float T = (float)Total_job / (float)CLOCK;

printf("Average Waiting time = %.2f ms (%d/%d) ", AWT,Total_waiting_time,Total_job); printf("Average Turnaround time = %.2f ms (%d/%d) ", ATT,Total_turnaround_time,Total_job); printf("Throughput = %.2f jobs per ms (%d/%d) ", T,Total_job,CLOCK); }

void removeLL(struct PCB **head_ref, int PID) { struct PCB* temp = *head_ref, *prev;

if(temp != NULL && temp->ProcId == PID) { *head_ref = temp->next; free(temp); return; }

while (temp != NULL && temp->ProcId != PID) { prev = temp; temp = temp->next; }

if (temp == NULL) return;

prev->next = temp->next;

free(temp); }

void FIFO_Scheduling() { runLL(Head); struct PCB *pcb = Head; int i = 1; int burstcalc = 0; while(pcb != NULL) { burstcalc = burstcalc + pcb->CPUburst; printf("Process %d is completed at %d ms ",i,burstcalc); pcb = pcb->next; removeLL(&Head,i); i++; }

}

int main(int argc, char *argv[]) { if(argc < 4) { printf("Error (Not enough arguments) "); return 0; }

int i = 0; int runFIFO = 0; int inputspc = 0; int algspc = 0; char *inputptr;

while(i < argc) { if (strncmp("-alg", argv[i],4) == 0) { algspc = 1; }

if (strncmp("FIFO", argv[i],4) == 0) { runFIFO = 1; }

if (strncmp("-input", argv[i],5) == 0) { inputspc = 1; } if (strncmp("input1.txt", argv[i],9) == 0) { inputptr = argv[i];

}

i++; }

if(algspc == 0) { printf("Error (alg not specified) "); return 0; }

if(inputspc == 0) { printf("Error (input not specified) "); return 0; }

FILE *fp; fp=fopen(inputptr, "r");

print = fgetc(fp); while (print != EOF) {

if(isdigit(print)) { int x = print - '0'; digitarray[count] = x; count++; }

print = fgetc(fp);

}

fclose(fp);

maxcount = count; count = 0;

while(count < maxcount) { append(&Head,digitarray[count],digitarray[count + 1],digitarray[count + 2]); count += 3; }

printalg();

if(runFIFO == 1) { FIFO_Scheduling(); }

printprefM();

return 0; }

Details of above code:

In this session, you will set up your account to implement necessary linked list functions for FIFO CPU scheduling and perform the very basic steps in context-switching. In the next session, you will extend this program to implement other three basic CPU scheduling algorithms (namely, SJF, PR, and RR with a given quantum). To keep it simle, we assume each process has a single CPU burst without any I/O burst and that all processes arrive at the same time in a given order. The order of processes will be given in a simple input file. Each line in the input file consists of three integer numbers: Process Id, Process Priority, CPU Burst time (ms). Download input1.txt as a sample input file.

Your program will take the name of the scheduling algorithm, related parameters (if any), and an input file name from command line. In general, here how your program should be executed:

> prog -alg [FIFO|SJF|PR|RR] [-quantum [integer(ms)]] -input [input_file_name.txt]

In this session, you will just run it as:

> prog -alg FIFO -input input1.txt

For the given input file, the output of your program will be as follows:

Student Name: Your name Input File Name : input1.txt CPU Scheduling Alg : FIFO Proces 1 is completed at 5 ms Proces 2 is completed at 12 ms Proces 3 is completed at 18 ms Proces 4 is completed at 22 ms Average Waiting time = 8.75 ms (35/4) Average Turnaround time = 14.25 ms (57/4) Throughput = 0.18 jobs per ms (4/22)

Define a very basic CPU consisting of 8 integer registers: int CPUreg[8] = {0};

Initialize your linked list: struct PCB *Head=NULL; struct PCB *Tail=NULL;

Initialize your other data: int CLOCK=0; int Total_waiting_time=0; int Total_turnaround_time=0; int Total_job=0;

Open the input file

For each input line,

read a line consisting of three integers: Process Id, Process Priority, CPU Burst time.

dynamically create a struct PCB pointed by PCB,

save the given data into correponding fields of PCB,

set all PCB->Reg[8] to the Process ID, set PCB->queueEnterClock and PCB->waitingTime to 0, then

insert this PCB at the end of the link list.

Close input file

Print your name, the name of scheduling algorithm, and the input file name, as mentioned before.

------------------ The above steps will be the same for the next session too -----------------------

Now implement a FIFO_Scheduling() function and call it to print the order of completed processes.

This function simply removes the PCB from the head of the linked list and performs the followings until the linked list is empty: Do context-switching:

copy PCB->Reg[8] into CPUreg[8],

suppose some work is done on CPU (e.g, increment each CPUreg by one),

copy CPUreg[8] into PCB->Reg[8]

Data collection for performance metrics

PCB->waitingTime = PCB->waitingTime + CLOCK - PCB->queueEnterClock;

Total_waiting_time = Total_waiting_time + PCB->waitingTime ;

CLOCK = CLOCK + PCB->CPUburst;

Total_turnaround_time = Total_turnaround_time + CLOCK;

Total_job = Total_job + 1;

Free PCB. Since there is no more CPUburst or I/O burst, this process is terminated here! Otherwise, it will be put in a ready or waiting queue.

Finally, print the perfromance metrics mentioned before:

Total_waiting_time / Total_job,

Total_turnaround_time / Total_job,

Total_job / CLOCK

For each input file, copy/paste your screen output into a textfile (say output1.txt)