Overview This assignment is about process scheduling. In Part 1, you will write a C program (e.g., prog.c) to implement necessary linked list functions for FIFO CPU scheduling and perform the very basic steps in context-switching. In the remining parts, 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 simple, we assume each process has a single CPU burst without any I/O burst and all processes arrive at the same time in a given order. The order of processes will be given in a simple input file, where each line 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 as command line arguments. In general, here how your program should be executed

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

The order of commant line arguments and their associated data could be given in different orders:

For Part 1 (FIFO), you can run it as:

> prog -alg FIFO -input input1.txt

or

> prog -input input1.txt -alg FIFO

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

Student Name: Your firstname lastname 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)

In the other parts, you will implement and test the other three CPU scheduling algorithms. They will also have the same output format with different values.

Part 2 (SJF): Detailed Steps

For Part 2 (SJF), you will just run it as:

> prog -alg SJF -input input1.txt

or

> prog -input input1.txt -alg SJF

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

Part 3 (PR): Detailed Steps

For Part 3 (PR), you will just run it as:

> prog -alg PR -input input1.txt

or

> prog -input input1.txt -alg PR

Implement a PR_Scheduling() function and call it to print the order of completed processes when -alg PR option is given. 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 linked 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: (so, this is non-premptive PR) Do context-switch, Data collection, Free PCB. Finally, print the performance metrics as before.

input1.txt

1 3 5 2 3 7 3 1 6 4 5 4

Part 1 (FIFO): Detailed Steps Create a directory called assign2 under cs3733 and write your program (prog.c) under assign2. Define a very basic PCB structure: struct PCB_st {int ProcId; int ProcPR; int CPUburst; int myReg[8]; int queueEnterclock, waitingTime; /* you can add other fields */ struct PCB_st *next; } Define a very basic CPU consisting of 8 integer registers: int coureg[8] = {0}; Initialize your linked list: struct PCB_st *Head=NULL; struct PCB_st *Tail=NULL; Initialize your other data: int CLOCK=0; int Total_waiting_time=0; int Total_turnaround_time=0; int Total_job=0; You can declare all the above varibales/arrays as global variables/arrays! Open the input file For each input line, o read a line consisting of three integers: Process Id, Process Priority, CPU Burst time. fscanf(..., "%d %d %d",...); will be OK o dynamically create a struct PCB_st pointed by PCB, o save the given data into correponding fields of PCB, o set all PCB->Reg[8] to the Process ID, set PCB->queueEnterclock and PCB->waitingTime to 0, then o 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 in the other parts too Now implement a FIFO_Scheduling() function and call it to print the order of completed processes when -alg FIFO option is given. This function mainly implements the following steps in while( the linked list is not empty) : o Remove the PCB from the head of the linked list o Do context-switching: copy PCB->myReg[i] into CPUreg[i], (you need a loop to copy all registers, for(i=0; i) suppose some work is done on CPU (e.g, increment each CPUreg by one, you need a loop for that too), copy CPUreg[i] into PCB->myReg[i] (you need a loop to copy all 8 registers!) Note: here we simply copy all 8 registers from cpu into PCB and restore them because we just want to mimic what happens in an actual system when doing context switching. it doe not affect calculations because we ignore the context switching time in this assignment. o 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; o 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. When the while loop ends, print the perfromance metrics mentioned before: 0 Total_waiting time / Total_job, O Total_turnaround_time / Total_job, 0 Total_job / CLOCK For each input file, copy/paste your screen output into a textfile (say output1.txt) Make sure your program works and generates the above output for the given input file. Then extend this program in the remaining parts to perform other three basic CPU scheduling algorithms, namely SJF, PR, RR (quantum) Part 4 (RR): Detailed Steps For Part t (RR), you will just run it as: > prog -alg RR -quantum 5 -input input1.txt or > prog -input input1.txt -alg RR -quantum 5 Implement a RR_Scheduling() function and call it to print the order of completed processes when -alg RR option is given along with quantum integer(ms). 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 followings: Do context switching: o copy PCB->myReg[i] into cPureg[i], (you need a loop to copy all 8 registers, for(i=0; imyReg[i] (you need a loop to copy all 8 registers) If PCB->CPUburst 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; o Free PCB. Since there no more CPUburst or I/O burst, this process is terminated here! Else that is PCB->CPUburst > quantum, O PCB->waitingTime PCB->waitingTime + CLOCK - PCB->queueEnterclock; O CLOCK = CLOCK + quantum; O PCB->CPUburst - PCB->CPUburst - quantum; O 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 Part 1 (FIFO): Detailed Steps Create a directory called assign2 under cs3733 and write your program (prog.c) under assign2. Define a very basic PCB structure: struct PCB_st {int ProcId; int ProcPR; int CPUburst; int myReg[8]; int queueEnterclock, waitingTime; /* you can add other fields */ struct PCB_st *next; } Define a very basic CPU consisting of 8 integer registers: int coureg[8] = {0}; Initialize your linked list: struct PCB_st *Head=NULL; struct PCB_st *Tail=NULL; Initialize your other data: int CLOCK=0; int Total_waiting_time=0; int Total_turnaround_time=0; int Total_job=0; You can declare all the above varibales/arrays as global variables/arrays! Open the input file For each input line, o read a line consisting of three integers: Process Id, Process Priority, CPU Burst time. fscanf(..., "%d %d %d",...); will be OK o dynamically create a struct PCB_st pointed by PCB, o save the given data into correponding fields of PCB, o set all PCB->Reg[8] to the Process ID, set PCB->queueEnterclock and PCB->waitingTime to 0, then o 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 in the other parts too Now implement a FIFO_Scheduling() function and call it to print the order of completed processes when -alg FIFO option is given. This function mainly implements the following steps in while( the linked list is not empty) : o Remove the PCB from the head of the linked list o Do context-switching: copy PCB->myReg[i] into CPUreg[i], (you need a loop to copy all registers, for(i=0; i) suppose some work is done on CPU (e.g, increment each CPUreg by one, you need a loop for that too), copy CPUreg[i] into PCB->myReg[i] (you need a loop to copy all 8 registers!) Note: here we simply copy all 8 registers from cpu into PCB and restore them because we just want to mimic what happens in an actual system when doing context switching. it doe not affect calculations because we ignore the context switching time in this assignment. o 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; o 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. When the while loop ends, print the perfromance metrics mentioned before: 0 Total_waiting time / Total_job, O Total_turnaround_time / Total_job, 0 Total_job / CLOCK For each input file, copy/paste your screen output into a textfile (say output1.txt) Make sure your program works and generates the above output for the given input file. Then extend this program in the remaining parts to perform other three basic CPU scheduling algorithms, namely SJF, PR, RR (quantum) Part 4 (RR): Detailed Steps For Part t (RR), you will just run it as: > prog -alg RR -quantum 5 -input input1.txt or > prog -input input1.txt -alg RR -quantum 5 Implement a RR_Scheduling() function and call it to print the order of completed processes when -alg RR option is given along with quantum integer(ms). 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 followings: Do context switching: o copy PCB->myReg[i] into cPureg[i], (you need a loop to copy all 8 registers, for(i=0; imyReg[i] (you need a loop to copy all 8 registers) If PCB->CPUburst 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; o Free PCB. Since there no more CPUburst or I/O burst, this process is terminated here! Else that is PCB->CPUburst > quantum, O PCB->waitingTime PCB->waitingTime + CLOCK - PCB->queueEnterclock; O CLOCK = CLOCK + quantum; O PCB->CPUburst - PCB->CPUburst - quantum; O 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