You are required to submit your work through UTSA Learn (f. Blackboard or BB)
!!! No e-mail submissions !!!
!!!! Please carefully check the DUE DATE on BB Learn !!!!
!!!! NO LATE SUBMISSION WILL BE ACCEPTED !!!
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 command 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 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 CPUreg[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,
- read a line consisting of three integers: Process Id, Process
Priority, CPU Burst time. fscanf(...,"%d %d %d", &id, &pr, &burst); will be OK
- dynamically create a struct PCB_st pointed by PCB,
- save the given data into correponding fields of PCB(e.g., PCB->ProcId = id; ),
- set all PCB->Reg[8] to the Process ID (e.g., for(k=0; k < 8; k++) PCB->myReg[k] = 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 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) :
- Remove the PCB from the head of the linked list (but don't free it yet)
- Do context-switching:
- copy PCB->myReg[i] into CPUreg[i], (you
need a loop to copy all 8 registers, for(i=0; i < 8; 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 does not affect delay calculations because we ignore
the context switching time in this assignment.
- 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.
-
- When the while loop ends, 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)
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 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 we did for FIFO.
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.
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:
- copy PCB->myReg[i] into CPUreg[i],
(you need a loop to copy all 8 registers, for(i=0; i< 8; i++) { })
- suppose
some work is done on CPU (e.g, you need a loop to increment each CPUreg by one),
- copy CPUreg[i] into PCB->myReg[i]
(you need a loop to copy all 8 registers)
- 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, When the while loop ends, print the perfromance metrics as mentioned before:
- Total_waiting_time / Total_job,
- Total_turnaround_time / Total_job,
- Total_job / CLOCK
Deliverables