Analysis and implementation of scheduling algorithm
Posted on 2008-11-11
Purpose : To bring together various ideas of OS we have learned so far. Designing a small part of the operating system and dealing with the details of the implementation of the design. We will also learn to deal with unanticipated problems and work in teams.
Problem Statement : Your team is in charge of implementing and studying the effects of six scheduling algorithms. The algorithms to be studied are given below.
* First Come First Serve (FCFS)
* Shortest Job Remaining (SJR)
* Round-Robin (RR)
* Shortest Job First (SJF)
* Priority Scheduling (PS)
* Multi-level Feedback Queue Scheduling (MFQ)
In the system you are building, each process arrives one at a time. Each process is characterized by three parameters : the CPU burst, I/O burst needed and the id of the process. Assume that you have only one i/o burst and if a process needs an i/o operation, it occurs exactly half way through the CPU burst (for example, process 1 has as its parameters (CPU burst - 10 seconds, I/O burst - 5 seconds, id - p_1), then I/O burst occurs after the process has run for 5 seconds).
You should be able to read the information about processes from a file. Note that FCFS and SJF are non-preemptive and SJR, RR, MFQ and PS are preemptive. For the RR algorithm assume the quantum is 3 units. For the MFQ assume there are three Queues. The first queue will have a time quantum of 3, the second with a quantum of 6 and the third will be treated FCFS. Processes in the lower queues will be assigned the CPU only if higher queues are empty.
Keep all units in seconds. Break all ties based on the Bakery Algorithm (the process with the smaller process id number will get ahead). Assume you have infinite instances of I/O devices (i.e. no need to create an I/O queue to schedule I/O). There should be no need for user interaction.
Input should be:executable input_filename number_of_processes snapshot_time_interval (for example $mysched file1.dat 10 10 - for the executable named mysched with input data in a file called file1.dat with 10 processes and snapshot taken every 10 units of time)
% Sample Input File
% P_ID CPU_burst I/O_burst Priority
0 10 4 2
1 8 2 1
2 12 0 5
3 2 4 4
4 8 3 0
5 6 4 2
6 4 0 5
7 16 7 5
8 14 0 1
9 2 10 1