CAS CS 552
Programming Assignment 3: CPU Scheduling

Due: Tuesday November 16, 1999

Contents

• Introduction
• Running the Simulator
• System Overview
• Program Modification
• Files
• Coding
• Experiments
• Report
• Grading
• Handing In

Introduction

Running the Simulator

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

• Proj3: Name of the main class.
• -v, -v -v, etc.: Starts 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: Starts trace mode. Trace mode causes the simulator to maintain a record of all significant events.
• data-file: Name of the file containing the trace data used in the simulation.
• quantum: Length of the time-slice currently used in the Round-Robin scheduling (in milliseconds).

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 that device.

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) there are pages describing all the interfaces in detail, additional documentation about the program, and, of course, comments in the code itself.

Program Modification

1. Modify one copy of the program to simulate a Multilevel Feedback Queues algorithm called Exponential Queues (Version 1):

 

(a)

Jobs are scheduled according to priority, which ranges from 0 (highest priority) to 7 (lowest priority).

(b)

When a job starts a burst (that is, when it becomes ready either because it has just started or because it has finished doing I/O), it is assigned priority 0.

(c)

The scheduler maintains a (FIFO) queue of jobs for each priority level. The scheduler will always run the first job of the highest priority level available (lowest-numbered non-empty queue). For example, if queues 0 and 1 are empty but queue 2 is not, the scheduler will run the first job in queue 2.

(d)

When a job is run, it is assigned a slice, which is a number of quanta based on the priority of the job. A job at priority level 0 has a time slice length of 1 quantum, a job at level 1 has a time slice of 2 quanta, a job at level 2 has a time slice of 4 quanta, and so on. In general, a job with priority i has a time slice of 2ⁱ quanta.

(e)

If a job with priority i uses up its time slice without blocking for I/O or terminating, the scheduler stops it, lowers its priority to i+1, and adds it at the tail of queue i+1, and selects a job as in rule (c).¹ While it is possible that the same job will be selected again--for example, if it is the only ready job--normally a different job will be given the opportunity to run.

(f)

This policy is non-preemptive in the following sense: If a job becomes ready while another job is running, it is added to the tail of queue 0, but the running job is not stopped until it terminates, blocks for I/O, or uses up its time slice.

2. Modify another copy of the program to implement a slightly different version of Exponential Queues (version 2). Jobs arriving at the CPU scheduler can preempt running jobs, and the priority of a job is ``remembered'' from one burst until the next. In more detail, rules (b) and (f) are modified as follows:

 

(b')

When a job becomes ready because it has finished doing I/O, it is given priority i-1, where i is the priority it had when it blocked for I/O.² Newly created jobs are assigned priority 0. 

(f')

This policy is preemptive in the following sense: If a job becomes ready while another job is running, it is added to the tail of the appropriate queue as defined by rule (b'), the running job is stopped and has 1 subtracted from its priority (unless it is already at priority 0), it is added to the tail of the appropriate queue, and another job is selected to run as in rule (c). To make solutions by different teams comparable, these actions should be done in the order specified:

1. add new arrival to queue
2. add current job (if any) to queue
3. choose job to run.

• the original (RR),
• one for Exponential Queues, version 1 (XQ1),
• and one for Exponential Queues, version 2 (XQ2).

Files

    ~matta/cs552/proj3

Coding

    cp RRScheduler.java XQ1Scheduler.java

You should also change the line cpuScheduler = new RRScheduler(); in the file Sim.java to read cpuScheduler = new XQ1Scheduler(). The methods in RRScheduler which you will have to modify for your assignment include:

• boolean add(Job newJob) adds a new job wanting service. This method should return true if the scheduler would like to preempt the current job.
• Job remove() returns the job that the scheduler would like to run next (and removes it from the queue)
• boolean reschedule(Job currentJob) returns true if there is a reason to stop the current job and start another. It is called by mainLoop on a clock interrupt and is essential to implementing preemption. 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.

Experiments

1. Run your simulator for each scheduling policy, with a variety of quantum values. For each version of the simulator, for each input data file, for each quantum value, plot the

(a)

completion time,

(b)

throughput,

(c)

average job elapsed time,

(d)

average job waiting time.

2. From the data in part 1, determine (for each scheduling algorithm) the range of values for the quantum that have a noticeable effect on performance. In other words, what is the smallest and largest quantum that will effect performance?
3. From the data in part 1, note any performance differences and similarities between the scheduling algorithms. Are the results consistent for different input data files? Are the results consistent for different quantum values? Is one algorithm always better than another? Try to figure out if these differences make sense to you and explain these differences and similarities.

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

Grading

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

Handing In

Also, submit a printed copy of your report. 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, and indicate which one of you submitted the electronic copy. 

Footnotes

²There is no level -1, so if a job finishes a burst at priority 0, it stays at priority 0.