CPU Scheduler Application

A nice java application that simulates differnet CPU scheduling algorithms. Now available as an applet.

Downloading and Running the Applicaton

To run this program locally you'll need to download and install Java. Then download my cpu.jar file and run it with the following command:

java -jar cpu.jar

Alternately, you can unpack the tar.gz file onto your hardrive and run the class file from the current directory. This will give you the images directory, all of my source code, and the data files with predefined simulation data sets. It goes like this:

tar -xzvf cpu.tar.gz
cd src
java MainApp

Whether .jar or .class file, if you run the application locally you have the option of opening predetermined datasets from a file and of saving your runtime statistics as a csv file.

Discussion

This application is designed to simulate the short term scheduler in an operating system. Realize that a real operating system CPU scheduler will probably use multi level feedback queues, process aging, and any number of combinations of the algorithms used here, but the application serves as a way to percieve the algorithms visually. My hope is that it can be used to show OS students how these mechanisms work.

• Initial burst time
  This is the amount of CPU time the process will require. In real life this is not really known, but can be predicted with some degree of accuracy.
• Delay
  The time seperating the arrival of processes. The amount of time after the (n-1)th process arrives that this process arrives.
• Priority
  For prioritized algorithms this is the relative weight of this process. The range is from 0 - 9 where 9 is the lowest priority and 0 is the highest
  

• PID
  A Process ID is number to identify a particular process. Each PID is unique to a process.
• Arrival start and finish time
  Record the time a job arrives, when it is started, and when it is finished. These times allow us to derive three quantifiers.
  • Response Time
    The amount of time a ready job sat in the queue befor the process was started.
  • Turnaround Time
    The total life of the process in the ready queue.
  • Wait Time
    The time this process spent in the ready queue waiting for CPU time.

The Scheduling Algorithms

I used four different scheduling algorithms some of which of multiple variations.

• First Come First Serve (FCFS)
  This is the simplest algorithm. It implements a FIFO queue. The first job that arrives in the ready queue is run to completion, and then the next job is selected in arrival order. The FCFS algorithm is neither prioritized nor preemptive.
• Shortest Job First (SJF) (Preemptive, Non-preemptive)
  The SJF algorithm chooses the shortest job. Without preemption jobs run to completion before a new job is selected . If preemption is enabled then the instant a job arrives that is shorter than the one being run the CPU switches to the new shorter job. The processing can be interrupted to run newly arrived shorter jobs.
• Round Robin (RR) (Prioritized, Equal time)
  The Round Robin scheduling algorithm allocates a timeslice to each running process. This is called the quantum and it represents the number of CPU cycles a process gets befor the scheduler searches for a new job to run. Jobs recieve their quantums of CPU time in FCFS order. With priorit scheduling enabled the quantum is multiplied by the magnitude of a processes priority. Thus more important jobs get more CPU time.
• Priority Weighted (PRI) (Preemptive, Non-preemptive)
  The priority scheduling algorithm selects its next job based on the importance of the process. The job that has the highest priority (0 high : 9 low) is run first. If preemption is enabled the new jobs with a higher priority will interrupt the currently executing job. Without preemption the highest priority job is chosen after the active process finishes execution.

The Data

Here is the data from a sample run of each algorithm. The input CSV file has 50 rows (jobs) and each row/job has a column for burst (cpu time required), delay (arrival time), and priority (rank). The data is output to CSV and then manipulated in excel.

All Sample Data as HTML

Summary of Results

• DataSummary.xls

• jobQueue.csv
• jobQueue.xls

• fcfs.csv
• fcfs.xls
• priority-preemptive.csv
• priority-preemptive.xls
• priority.csv
• priority.xls
• rr-pri.csv
• rr-pri.xls
• rr.csv
• rr.xls
• sjf-preemptive.csv
• sjf-preemptive.xls
• sjf.csv
• sjf.xls

Conclusions

Appendices

What (if any) relation holds between the following pairs of sets of algorithms?

1. Priority and SJF
   The SJF algorithm a derivative of the Priority algorithm where the priority of the process is set to according to the size of the job. Shorter jobs have higher priorities.
2. Multilevel feedback queues and FCFS
   FCFS is a good algorithm for one of the sub-queues of a multilevel feedback queueu. Specifically, the batch queue.
3. Priority and FCFS
   FCFS is a sub set of priority; where the higher priority is assigned to the earlier job.
4. RR and SJF
   There is do direct relationship. If given a prioritized scheduler we could set the time quantum equal to the length of the job and give shorter jobs a higher priority.

References

• [Mullen 1985] B. Mullen, The Multics Scheduler, http://www.multicians.org/mult-sched.html (1995)
• [Silberschatz and Galvin 1998] A. Silberschatz, P. Galvin, Operating System Concepts, Addison Wesley Longman, Inc. (1998)