CPSC503 Operating Systems Spring 2016 Project 1 CPU Scheduling Problem Statement: You will implement a framework for CPU scheduling with three scheduling algorithms: FIFO, round robin, and shortest remaining job first (SRJF). Jobs arrive at the CPU scheduler at arbitrary times ranging from 1 to 20 time slots and at least 15 jobs. 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. Brief descriptions of three algorithms 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 Remaining Job First This is a preemptive scheduling algorithm. 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 [-v] -[Rk|S|F] [-f |-r n] 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 The -v option indicates a verbose output mode (i.e. more information is displayed) The r option indicates creating n jobs randomly whose format is the same as filename The f 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 (CPU Burst time) A sample input file looks like this: 0,9,25 1,17,10 2,32,7 3,35,20 In the default mode (i.e., without the -v flag), the output consists of the completion time of each job. Below is the corresponding output for the test input above without the verbose flag. 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 SRJF 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. Read the verbose mode for further clarification. In verbose mode, in addition to the above information, your program should display the complete job state transition information as in the following example. Below is the corresponding output for the test input above with the verbose flag: for FIFO At time 9, job 0 READY At time 9, job 0 READY->RUNNING At time 17, job 1 READY At time 32, job 2 READY At time 34, job 0 RUNNING->TERMINATED At time 34, job 1 READY->RUNNING At time 35, job 3 READY At time 44, job 1 RUNNING->TERMINATED At time 44, job 2 READY->RUNNING At time 51, job 2 RUNNING->TERMINATED At time 51, job 3 READY->RUNNING At time 71, job 3 RUNNING->TERMINATED for SRJF At time 9, job 0 READY At time 9, job 0 READY->RUNNING At time 17, job 1 READY At time 17, job 0 RUNNING->READY At time 17, job 1 READY->RUNNING At time 27, job 1 RUNNING->TERMINATED At time 27, job 0 READY->RUNNING At time 32, job 2 READY At time 32, job 0 RUNNING->READY At time 32, job 2 READY->RUNNING At time 35, job 3 READY At time 39, job 2 RUNNING->TERMINATED At time 39, job 0 READY->RUNNING At time 51, job 0 RUNNING->TERMINATED At time 51, job 3 READY->RUNNING At time 71, job 3 RUNNING->TERMINATED for RR with k = 8 (time-slicing begins at 9 in this case because that is when the first job arrives) At time 9, job 0 READY At time 9, job 0 READY->RUNNING At time 17, job 1 READY At time 25, job 0 RUNNING->READY At time 25, job 1 READY->RUNNING At time 32, job 2 READY At time 33, job 1 RUNNING->READY At time 33, job 0 READY->RUNNING At time 35, job 3 READY At time 41, job 0 RUNNING->READY At time 41, job 2 READY->RUNNING At time 48, job 2 RUNNING->TERMINATED At time 48, job 1 READY->RUNNING At time 50, job 1 RUNNING->TERMINATED At time 50, job 3 READY->RUNNING At time 58, job 3 RUNNING->READY At time 58, job 0 READY->RUNNING At time 59, job 0 RUNNING->TERMINATED At time 59, job 3 READY->RUNNING At time 71, job 3 RUNNING->TERMINATED sched -F r 10 for FIFO with randomly generated 10 jobs 0,9,25 1,17,10 2,32,7 3,35,20 In case of random generation, first randomly generated jobs are displayed first, and then process them as above. Write-up You should submit a write-up as well as your program. Your write-up should include any known bugs, limitations, and assumptions in your program. This wirte-up should be in text-format and titled as README. It should be submitted along with your code. GA will use the README file to compile (or install) and run your program. If the TA has trouble with your program then he will contact you to makeup it. Submission You will submit your program to Canvas. You should zip your source files and write-up (README) into a single file and submit it. Be sure that you include everything necessary to unzip this file on another machine and compile and run it. This might includes forms, modules, classes, configuration file, etc. DO NOT include the executable file itself, we will recompile it. The name of your submitted zip file should be your UB account_ID_project1. For example, jelee_000000_project1.zip. Make sure your name and UB ID are listed in both your write-up and source code. You may resubmit your program at any time. However, please do not ask the GA to grade your program and then resubmit it. The submission time of the latest submission will be used for determining whether the assignment is on time or not. Late submissions will be accepted at a penalty of 10 points per day. In other words, it may pay you to do this project early on the off chance that something prohibits your submitting it in a timely way. If your program is not working by the deadline, submit it anyway and review it together with GA for partial credit. Do not take a zero on any lab just because the program isnt working yet. If you have trouble getting started, ask the professor or the GA. Grading 20 points: FIFO works correctly 20 points: SRJF works correctly 20 points: RR works correctly 10 points: Proper output, according to guideline above (none verbose) 10 points: Proper output, according to guideline above (verbose mode) 10 points: Random generated jobs 5 points: Write up document with proper instructions 5 points: Comments in code To receive full credit for comments in the code you should have headers at the start of every module, subroutine, or function explaining the inputs, outputs and function of the module. You should have a comment on every data item explaining what it is about. (Almost) every line of code should have a comment explaining what is going on. A comment such as /* add 1 to counter */ will not be sufficient. The comment should explain what is being counted.