Date: Tue, 05 Nov 1996 00:27:26 GMT Server: NCSA/1.5 Content-type: text/html Last-modified: Thu, 31 Oct 1996 21:38:54 GMT Content-length: 12763 CS 537 - Programming Assignment III

CS 537
Programming Assignment III
CPU Scheduling

Due:

October 22 at the start of class.


Contents


Introduction

A program has been written that simulates a short-term scheduler and allows you to experiment with various scheduling policies. Your assignment is to measure and analyze the performance of several policies, modifying the simulation program as necessary.

Running the Simulator

The current version of the program simulates Round-Robin (RR) scheduling, but it is constructed to allow easy modification for other scheduling policies. The program expects the following command line:

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

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 is 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 a device and will choose which job is the next to access.

The overall execution of the simulator occurs like this: Jobs arrive at the JobArrival device and are entered into the system. A job's lifetime consists of alternating periods of using the CPU (called a burst) and performing I/O. The Main Loop is responsible for moving jobs around the system. It sends them to a scheduler, takes the next job from a scheduler, and starts and stops jobs running on a device. The Disk Scheduler and the CPU Scheduler decide which job should be the next to run on their respective devices. They also buffer jobs that are waiting to run but have not yet been given access. The clock device is used to enable preemption (more on this later).

For those who would like a more detailed description of the system (more than is necessary to do this assignment), you can either read the comments in the code itself, or click here.

Program Modification

For this project, you are going to be focusing almost exclusively on the CPU Scheduler object shown above. The provided simulator performs Round-Robin (RR) scheduling. You are to create separate versions of the simulator to implement each of the CPU scheduling algorithms described below.

  1. Modify one copy of the program to simulate the Shortest-Job-First (SJF) algorithm described in Section 2.4.4 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.
  2. This policy is non-preemptive: Newly arriving processes do not affect the currently-running process.
  3. Modify another copy of the program 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.
  4. For your final version of the program, modify the SJF algorithm to use 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:
    1. Tn+1 = atn + (1 - a)Tn

    What the formula says is that the predicted value of the next burst length (Tn+1) will be dependent upon both the last measured burst length (tn) and the last predicted burst length (Tn). 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 modify the Job class to record a little more information.

You should have four versions of the simulation program when finished,

Files

The files you will need can be found in
    ~cs537-1/public/src
They include all of the files for the simulator, the data file, and a Makefile. Copy all of these files into one of your directories and type make to run the Round-Robin version of the simulator.

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 SJFScheduler in the copy and in the Makefile.

You should also change the following line in the file Sim.java so your Scheduler is used by the simulator instead of the default:

    Sim.java: 
        cpuScheduler = new RRScheduler();

    becomes 
        cpuScheduler = new SJFScheduler(); 
The methods in RRScheduler which you will have to modify for your assignment include: You may also need to look at the Job class. One useful Job method is:

Experiments

Compare the performance of the four scheduling algorithms. Also compare the performance for various values of the parameters: quantum for RR and a for PSJF). Note that if quantum is very large, RR becomes First-Come-First-Served (FCFS) and if quantum==1 , RR approximates Processor-Sharing (PS).

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 book. 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 have some hypotheses that you confirm or reject based on behaviors observed during well-planned, organized experimentation. 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.

If the program is not printing out all the statistics you would like to see, feel free to modify it to produce better output. You may find additional statistics-reporting code can help explain some of the behavior you observe.

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:

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

Handing In

You should bring your report and all of the .java files you modified (with your additions clearly detailed in your code or in a separate file) to class on the day the project is due. You should also create four directories in your hand-in folder -- one for each of your scheduler versions. Into each directory you should place a copy of the files needed to run that particular scheduler (.java files, trace file) as well as a redirected copy of the output from one execution. A short README file containing the names of you and your partner can just be placed in your hand-in folder. The hand-in directories for project 3 can be found at:

As always, points will be deducted for code that fails to satisfy the minimal criteria for comments and structure specified in the hand-in directions for project 2.


Copyright © 1996 by Marvin Solomon. All rights reserved.