CPU Scheduler Application

Screenshots | Applet | Download | Discussion | Data | Conclusions | Appendices

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

Downloading and Running the Applicaton

This application was written with the Java2 SDK. It's components use the swing framework from the javax package. You can run this program from the web as an applet. But because of applet security you won't be able to open data files or save statistics.

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.

These are the inputs for the simulation
  • 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
These are some auxillary and tracking data
  • 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

Input File of CPU jobs Simulation Results Per Algorithm

Conclusions

Below are the summary statistics for the different algorithms. For a complete table go here

Middle of the road algorithm. Nothing good nothing bad. If your job arrives later even if it is short and of the highest priority it might have to wait a while; especially on busy systems.   First Come First Serve
    Wait Response Turnaround
  Min 0 0 3
  Mean 34.7 34.7 65.32
  Max 156 156 196
  StdDev 43.67 43.67 49.75
                 
This is the elitist's algorithms. "Not only to I get to go before you, if I get in the ready queue and your running I will kick you out." Handy if your a sysadmin, but not a very fair mechanism. Plus, the wait times are high. You could be at your terminal waiting for a long time.If your really low priority then you won't even notice the preemption.   Priority (preemmptive)
    Wait Response Turnaround
  Min 0 0 3
  Mean 34.34 18.2 64.96
  Max 429 363 528
  StdDev 85.6 55.81 96.83
                 
The egalitarian algorithm. Great response times, but turn around times are high. It's kind of the waiter/waitress algorithm. You get service quickly, but the amount of time you get serviced is small and far between. If the queue is really full it you could be waiting a long time for your little quantum.   Round Robin (equal time)
    Wait Response Turnaround
  Min 0 0 3
  Mean 39.96 7.64 70.58
  Max 197 46 296
  StdDev 48.8 11.44 65.81
                 
This is the egalitarian republic algorithm. Everyone is given an equal opportunity at time, but only the really important jobs really get it. What you gain in turn around time, you lose in response time.   Round Robin (prioritized)
    Wait Response Turnaround
  Min 0 0 3
  Mean 41.6 27.44 72.22
  Max 194 108 250
  StdDev 50.42 32.24 61.46
                 
This is just a brain dead version or the preemptive priority algorithm. Same problems, only elite processes get time. If your not important you'll be at your terminal for a while.   Priority (non-preemmptive)
    Wait Response Turnaround
  Min 0 0 3
  Mean 28.52 28.52 59.14
  Max 363 363 386
  StdDev 58.02 58.02 65.74
                 
This is an interesting one. Exempt from the plagues of prioritizing, jobs are chosen based on the size of the job ( a purely scalar value). Long jobs tend to sit and rot unless all the short jobs get run right away. This algorithm works fine for jobs that are spaced far apart.   Shortest Job First
    Wait Response Turnaround
  Min 0 0 3
  Mean 23.4 23.4 54.02
  Max 147 147 246
  StdDev 33.49 33.49 48.95
                 
The addition of preemption to the SJF algorithm give slight increases in wait and tournaround time, without really effecting the response time. Long jobs have an even higher tendency to lag at the back of the queue since they can be interrupted by short jobs. Even when long jobs get a chance to execute, they can be interrupted.   Shortest Job First (preemptive)
    Wait Response Turnaround
  Min 0 0 3
  Mean 18.24 13.68 48.86
  Max 187 147 286
  StdDev 39.06 31.59 57.55

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)

$Date: 2006/03/31 19:07:27 $