Problem Statement:
You will implement a framework for CPU scheduling with three scheduling algorithms: FIFO, round robin, and shortest job first (SJF). Jobs arrive at the CPU scheduler at arbitrary times. When a job arrives, its computation time is known. Assume that all jobs involve only computation, and perform no Input/Output. Jobs thus need to run on the CPU for a total duration equal to their known computation times. When they complete, they leave the system.
FIFO
Jobs are processed on a first-in-first-out basis.
Round-robin time-slicing
Pick head of queue, run a job for a time quantum, preempt it, run the next one and so on. A new job goes at the tail of the queue and so does a preempted one. If a new job arrives at the same time as a time quantum completes, the new job goes at the end of the queue.
Shortest Job First - Preemptive version (Shortest Remaining Time First)
If there is more than one job, select the one with the shortest execution time. If a new job has shorter REMAINING time, preempt current job and switch to new one.
Solution Specification: The input to your program will be a file containing job IDs with their arrival times and required computation times.
Input Format
The input command line format should be as follows (where sched is the name of your executable):
sched -[Rk|S|F]
Where the command-line flag:
- R is round robin, k is an integer specifying the time-slice
- S is shortest job first
- F is FIFO
- is the name of the input file whose format is described below
Format of the input file
You must use the following format for your input to enable us to grade your project easily. The file must contain the description of one process per line where each line has the following fields (all fields are integers separated by ",") in the following order:
id: The id of the job
arrival time: Arrival time of the job after start of simulation
comptime: Computation time
A sample input file looks like this:
0,9,25
1,17,10
2,32,7
3,35,20
The output consists of the completion time of each job. Below is the corresponding output for the test input above. The first column represents id of the job and the second column represents the completion time:
sched -F for FIFO
0 34
1 44
2 51
3 71
sched -S for SJF-preemptive
0 51
1 27
2 39
3 71
sched -R8 for RR with k = 8 (time-slicing begins at 9 in this case because that is when the first job arrives)
0 59
1 50
2 48
3 71
NOTE: If the quantum expires on an old job and a new job arrives at the same time in RR, put the new job at the end of the queue, after the old one.
Write-up:
Your write-up should include any known bugs and limitations in your programs. If you made any assumptions, document what you decided. This write-up should be in text format and should be submitted along with your code.