COMPSCI 386 Optional Homework
The purpose of this assignment is to investigate SRTF (Shortest Remaining Time First) scheduling through
deterministic modeling in Java. For simplicity we are ignoring dispatch latency and assuming that each
process consists of a single CPU burst.
Create a NetBeans project called CPU-Scheduling and upload it to your dropbox folder when you have
completed the assignment.
Write a program that calculates the average waiting time for a given workload using SRTF (i.e., preemp-
tive SJF) and, for the sake of comparison, FCFS. The workload is speci ed by the user entering a series of
integers separated by whitespace:
n a1 b1 a2 b2 an bn
where n is the number of processes and (ak, bk) are positive integers representing the arrival time and CPU
burst length of the k-th process respectively. The processes are given in ascending order of arrival time (i.e.,
ak ak+1). Your program will output the average waiting time for SRTF and, for the sake of comparison,
FCFS. It will also output the execution schedule as shown below. Use A, B, C, ... to denote the processes
in arrival order.
To illustrate the required I/O format, consider the following workload (arranged in columns here for easy
reading, but the user can enter the numbers on a single line):
5
0 10
3 5
4 2
7 8
8 4
This means that process A enters the system at time 0 and will be preempted by B at time 3, which will
then be preempted by C at time 4, and so on. Here is the corresponding output:
SRTF: A A A B C C B B B B E E E E A A A A A A A D D D D D D D D
Average waiting time: 5.8
FCFS: A A A A A A A A A A B B B B B C C D D D D D D D D E E E E
Average waiting time: 9.0
The simulation of SRTF consists of a loop that repeats once for each unit of time. If a process is arriving
at the current time unit, it is put into the ready queue (ordered by CPU burst length). When a process
nishes executing, it is removed from the system and another is taken from the ready queue (if not empty)
to execute. The scheduler must compare the CPU burst length of a newly arriving process with the one
currently executing. FCFS will, of course, be simpler.
Implement a class Process to encapsulate the arrival time, waiting time, and CPU burst length of a
process. For SRTF, use java.util.PriorityQueue for your ready queue, which means that the Process
class will have to implement the Comparable interface for ordering processes by CPU burst length.
The exact design details are up to you, but a good solution, in additon to being logically correct, will
be fully object-oriented and compliant with standard coding conventions for Java. Naturally you will apply
the principles of object-oriented programming that you have learned so far in your career as a CS major.
Consider implementing an abstract class for a generic scheduling algorithm and extending it to concrete
subclasses for SRTF and FCFS.
Remember, the programmer is always responsible for fully testing his or her code. If your application
does not work correctly in all cases, then you must explain this in your documentation and you should
provide the simplest possible example of a workload that is incorrectly handled by your application.