CPU Scheduling Algorithm Evaluation
Assignment 2:
CPU Scheduling Algorithm Evaluation
The Scenario
You have been recently hired as a junior developer for a new operating system company,
PS-OS that is investigating the possibility of OS’s in bionic implantables. Before investing
valuable development time into a single CPU scheduling algorithm, the boss wants you to
evaluate a number of scheduling algorithms on a test set of processes that they predict the
system will be running when it boots up.
The Assignment
One of the main tasks of an operating system is scheduling processes to run on the CPU i.e.
to decide the order in which processes can access a processor. In this assignment, you will
build a program which schedules simulated CPU processes. Your simulator program will
implement four of the CPU scheduling algorithms discussed in this module, and evaluate
their effects on a set of processes.
The simulator selects a process to run from the ready queue based on the scheduling
algorithm chosen at runtime. Since the assignment intends to simulate a CPU scheduler, it
does not require any actual process creation or execution. When the CPU scheduler
chooses the next process, the simulator will simply print out which process was selected to
run at that time. The simulator output is similar to the Gantt chart.
Design
1. Write a class called Process which stores the Process ID, Burst Time, Arrival Time,
and Priority of a process, all are integers. You can also add data members to keep
track of information in order to compute the statistics about the process such as its
waiting time, response time, and turnaround time. When developing your solution,
assume that the time to switch processes is 0. The methods of the Process class are
the get and set methods for each data member, the constructor for the class, and any
method needed to compute the statistics for that process.
2. Write a class called Scheduler to simulate a CPU scheduler for an operating system.
The scheduler contains the ready queue and the ready queue is a circular linked list.
The only operations the scheduler performs is add and remove. The add operation
adds a process into the ready queue into its appropriate spot within the ready queue
according to the CPU scheduling algorithm implemented. The remove operation
removes a process from the ready queue according to the CPU scheduling algorithm
Page #1 of 4
implemented. You’ll implement the following CPU scheduling algorithms: First Come
First Serve (FCFS), Shortest Remaining Time First (SRTF), which is the
preemptive version of Shortest Job First (SJF), Priority Scheduling (PS) (a higher
priority number indicates higher priority) and Round Robin (RR). Here is a perfect
use of inheritance. If needed, you can add an additional methods to the circular
linked list class to help in the use of the ready queue for a particular CPU scheduling
algorithm.
3. Create a driver class and make the name of the driver class SchedulerSim and it
should only contain only one method:
public static void main(String args[])
The main method receives, via the command line arguments, the name of the CPU
scheduler that your simulator program will execute. If Round Robin is the CPU
scheduler chosen then the time quantum value is also received via a command line
argument. The main method opens the file Processes.txt reading in the entire set of
processes and initiates execution of the simulator program. Assume there is only a
single processor with only one core. The main method itself should be fairly short.
The command to launch your program using First Come First Serve scheduling:
java SchedulerSim FCFS
The command to launch your program using Shortest Remaining Time First
scheduling:
java SchedulerSim SRTF
The command to launch your program using Priority Scheduling:
java SchedulerSim PS
The command to launch your program using Round Robin scheduling with a time
quantum of 10:
java SchedulerSim RR 10
Note: You will need to modify the provided sources to add support for command line
options.
4. Each line in the input file Processes.txt represents a process, 4 integers separated
by spaces. The process information includes the Process ID, Burst Time, Arrival
Time, and Priority of a process. Process IDs are unique. Arrival time is the time at
which the scheduler receives the process and places it in the ready queue. Arrival
times may be duplicated, which means multiple processes may arrive at the same
time. Burst Time is the CPU time that a process needs to complete it task. Priority
indicates the importance of a Process. A higher value indicates higher priority.
Page #2 of 4
You will first be given a list of 200 processes in a text file in the following format (with the
header omitted). Remember, the integers on each line are separated by a space or spaces.
The following table is an example of a three process input file.
Process ID Burst Time Arrival Time Priority
1001 83 0 3
1002 86 0 5
1003 49 0 5
... ... ... ...
Submission Instructions:
You will submit your Java source code along with a brief document outlining your results.
Later on, you will be asked to attempt a Canvas Quiz related to this assignment, which will
be used to grade your assignment submissions. A few sample questions are given at the
end.
Useful Definitions
Efficiency: percentage of time the processor is busy.
Throughput: number of processes completed per time unit
Process turnaround time: process completion time - process submission time
Waiting time: the amount of time the process spends in the ready queue
Response time: Time from submission to ready queue until first input onto CPU
Calculating process wait time with preemption:
Process waiting time = last start time - arrival time - ((number of preemptions) x quantum)
= completion time - burst time
Page #3 of 4
Sample Questions
Q1: When using the FCFS scheduling algorithm on the set of processes, what is the
Process ID of the 42nd process to run?
Q2: When using the FCFS scheduling algorithm on the set of processes, what is the
average turn around time?
Q3: When using the Priority scheduling algorithm on the set of processes, what is the
average waiting time?
Q4: When using the RR scheduling algorithm with a time quantum of 20 on the set of
processes, what is the average waiting time?
Q5: When using the SRTF scheduling algorithm on the given set of processes, what is the
throughput of the system?
Page #4 of 4