CS 537
Programming Assignment 3
CPU Scheduling

Due:

November 4 at 9:30 am.

Notes

There is now a FAQ (frequently asked questions) page for this project.

Introduction

We have written a program that simulates a short-term scheduler; with this program, you can experiment with various scheduling policies. Your assignment is to implement, measure, and analyze the performance of several policies.

Running the Simulator

The current version of the program simulates (non-preemptive) Round-Robin (RR) scheduling. It is constructed to allow other scheduling policies to be added easily. The program expects the following command line:

java Proj3 [-v...] [-t] CPU-scheduler data-file [ quantum ]

Proj3: Name of the main class.
-v, -v -v, etc.: Requests verbose mode for debugging. Verbose mode causes the simulator to print debugging output to the screen. The more v's in the command line, the greater the verbosity.
-t: Enables trace mode. Trace mode causes the simulator to maintain a record of all significant events.
CPU-scheduler: The name of name of a subclass of class Scheduler, which will be used to schedule requests for the CPU.
data-file: Name of the file containing the trace data used in the simulation.
quantum: Interval between clock interrupts. If this parameter is omitted, the clock device is turned off.

As distributed, the program contains only one CPU scheduler, named RRScheduler. You should be able to run it by typing


    cd private
    mkdir project3
    cd project3
    cp ~cs537/public/project3/* .
    javac *.java
    java Proj3 RRScheduler data.mm1.120.100.5000

System Overview

The Simulator essentially consists of Jobs, Devices, and Schedulers -- all coordinated by a single loop of code. A Job is a customer of services: it represents a process that needs to use system resources during its execution. A Device represents a resource in the system. In this simulation, the devices available to a job are the CPU and the disk. There is also a clock device and a pseudo-device that interrupts whenever a new job arrives in the system. A Scheduler coordinates access to a device. It queues Jobs that are waiting to use the device. Whenever the device becomes idle, the scheduler chooses which Job in the queue gets to use the device next. When a new Job arrives, the scheduler adds the Job to the queue and decides whether the Job currently using the device should be preempted. The CPU scheduler also gets to preempt the running job whenever the Clock device interrupts.

From time to time, the JobArrival "device" interrupts, indicating that a new Job has arrived in the system. A job's lifetime consists of alternating periods of using the CPU (called bursts) and I/O operations. The simulator's main loop is responsible for moving jobs around the system. All of its actions are initiated by Device interrupts. The simulator responds to a JobArrival interrupt by sending the new Job to the CPU scheduler. When the CPU device interrupts, indicating that the currently running Job has requested an I/O operation, the simulator moves the Job to the Disk scheduler. It also asks the CPU scheduler to select a Job from its queue and starts the CPU running that Job. When the Disk device interrupts, the simulator returns the Job to the CPU Scheduler. When the Clock device interrupts, the simulator asks the CPU scheduler whether to preempt the currently running Job. If the answer is yes, the simulator removes the current job from the CPU and gives it to the CPU scheduler to be queued. It then asks the CPU scheduler for another Job and starts that Job running on the CPU.

For those who would like a more detailed description of the system (more than is necessary to do this assignment) there are pages describing all the interfaces in detail, additional documentation about the program, and, of course, comments in the code itself.

Adding New Schedulers

For this project, you are going to be focusing almost exclusively on the CPU Scheduler object shown above. This object is an instance of a subclass of class Scheduler. We have written one such class, RRScheduler, which performs Round-Robin (RR) scheduling. You are to write other subclasses of Scheduler to implement each of the CPU scheduling algorithms described below.

Write a class to implement the Shortest-Job-First (SJF) policy described in the on-line notes and in Section ??? of the text. The next process to be run is the one with the smallest burst. Use FCFS to break ties. Because this is a simulation, you can "cheat" by looking at the burst length of a process when deciding which process to run next. In a real system, that information is not available to the scheduler. This policy is non-preemptive: Newly arriving processes do not affect the currently-running process.
Write another class to implement a preemptive version of SJF, which is called Shortest-Remaining-Time-First (SRTF). In this algorithm, the currently-running process is the one with the least time left in its current burst.
Your final scheduler will be a version of SJF that uses a predicted burst length. We will call this policy Predicted-Shortest-Job-First(PSJF). You can predict the burst length by using an exponential average of the measured lengths of previous CPU bursts. The formula is as follows:
What the formula says is that the predicted value of the next burst length (T_n+1) will be dependent upon both the last measured burst length (t_n) and the last predicted burst length (T_n). The weight the previous two measurements have in calculating the new prediction is contained in a. If a = 1/2, then they will both contribute equally; if a = 1, then only the last measured burst time is used to predict the next burst time. Experiment with different values of a for this section.

To implement PSJF you will have to store some additional information in each Job object. Class Job has a public field named schedulerInfo for this purpose. The simulator program does not do anything with this field. You can put an object you like in this field.

When you are done, you should have four subclasses of class Scheduler.html: the original class RRScheduler.html we wrote for you, SJFScheduler, SRTFScheduler, and PSJFScheduler.

Files

The files you will need can be found in


    ~cs537-1/public/project3

They include all of the files for the simulator, a data file, and a Makefile. Copy all of these files into a sub-directory of your private directory as described above and type make to run the Round-Robin version of the simulator.

Each line of the data file contains three numbers giving the arrival time of the job (in ms from the start of the simulation), the CPU demand of the job (in ms) and the amount of I/O (in bytes) performed by the job. The simulator assumes that I/O will be performed in disk operations of 1k bytes, each of which takes 20 ms to complete. The disk operations are distributed throughout the life of the job, so that a job that performs n disk operations divides it use of the CPU into n bursts. The bursts are approximately equal, but the simulator occasionally makes a burst unusually long or short.

We have provided a data file named data.mm1.120.100.5000, describing 1000 jobs with Poisson arrivals and exponential service times (this situation is called an M/M/1 queue). The mean inter-arrival time is 120 ms, the mean CPU time is 100 ms, and the mean amount of I/O is 5000 bytes. Other data files may be provided later.

Coding

The easiest way to attack this assignment is to modify a copy of the provided Round-Robin scheduler.


    cp RRScheduler.java SJFScheduler.java

Don't forget to change all occurrences of RRScheduler to RRScheduler in the copy. Also add the line


    SJFScheduler.java \

(don't forget the backslash!) to the Makefile following the line


    CLASSES = \

Each Scheduler subclass needs to define the following methods:

boolean add(Job newJob, Job currentJob) adds a new job wanting service. This method should add the new job to the queue of jobs waiting for the CPU and return true if the scheduler would like to preempt the current job. The currentJob parameter is a reference to the job currently using the CPU. If the CPU is idle, currentJob will be null. The scheduler doesn't actually preempt a job. It merely offers an opinion whether the job should be preempted by returning true or false.
Job remove() returns the job that the scheduler would like to run next (and removes it from the queue)
boolean reschedule(Job currentJob) is called whenever the clock device interrupts. This method should return true if there is a reason to stop the current job and start another. If it returns true, the mainLoop will take the current running job off the CPU and return it to the CPU queue (by calling add) and then ask for another job to run by calling remove.

You should not modify any of the original classes provided to you.

Experiments

You will compare the performance of various scheduling algorithms. You will also compare the performance for various values of the parameters quantum and (for PSJF) a. Note that if quantum is very large, RR becomes First-Come-First-Served (FCFS) and if quantum is very small, RR approximates Processor-Sharing (PS). You will find that if you make quantum too small, the simulation will never terminate. The simulator introduces an overhead of 2 ms for switching from one Job to another. If the quantum is too small, the current Job will not get a chance to do any useful work before it is preempted.

Compare the behavior and performance of each of the policies. Discover the strengths and weaknesses of each of them. Compare the performance results you observe with the predictions discussed in class and in the notes. You must supply quantitative data to support your conclusions.

You should approach this portion of the assignment as you would approach a laboratory assignment in a physics course. Use the "scientific method." You should form some hypotheses before you start experimenting and use the experiments to confirm or reject these hypotheses based on observed results. Give careful thought to the correct choice of parameters for the programs. Try a few trial runs with various parameters, print out the results, and go home and think about the results. These preliminary results should help you decide on better parameters for a second round of trials. Remember: It's not the quantity but the quality of data that dictates the quality of the experiments.

Report

You are to prepare a report describing the results of your experiments. Again, approach this report as you would approach a physics laboratory experiment report. You should carefully describe what experiments you did and what the results showed you about the different scheduling policies. We want to see a correlation between the experiments you run and the conclusions you draw. You must supply quantitative data to support your conclusions. The report should be not more than three typewritten pages, excluding tables, graphs, etc.

Grading

You grade will be determined as follows:

50% - Report (experiments, conclusions, presentation)
50% - Implementation (correctness, style, documentation)

You must work in two-person groups for this project.

Handing In

You should put a copy of your code (.java files only) in the directory


    ~cs537/handin/login/P3

where login is the login name of the "senior" member of your team. Include all .java files needed to build the program (even the parts we wrote and you didn't change). Do not include .class files or copies of our data files. Be sure each file contains the names of both partners.

Bring a printed copy of your report to class. As stated above, the report should be at most three pages, not including graphs and tables. Don't forget to put the names of both partners on the printed report.

Footnotes

Last modified: Fri Oct 29 08:00:41 CDT 1999

CS 537 Programming Assignment 3 CPU Scheduling