Date: Mon, 11 Nov 1996 17:24:43 GMT Server: NCSA/1.5 Content-type: text/html Last-modified: Fri, 26 Apr 1996 15:22:04 GMT Content-length: 9355 CS 537 - Programming Assignment #3
UNIVERSITY OF WISCONSIN-MADISON
Computer Sciences Department
CS 537
Spring 1996
Bart Miller
Programming Assignment #3
(Due Wednesday, May 1, at 5pm)

Simulating CPU Scheduling Algorithms

The goal of this assignment is to evaluate several CPU scheduling algorithms. We will use trace data from our local UNIX systems to test these algorithms.

Your assignment is to write a program that reads in the trace data and simulates the CPU scheduling. You will keep track of various performance statistics and print these out at the completion of the trace file.

The Trace Files

The trace files look similar to the ones you used for Program #1. Each line of the trace file will be of the form:
CommandName StartTime CPUTime IOCount
Each of these three pieces will be separated by some number of blank characters (spaces or tabs).

The lines in the trace files are sorted by program starting time.

Program Information

Your program will be structured as a continuous loop that reads trace records and advances time.

Important Events

Your program will maintain a notion of current time. The "clock" in your simulator will be a variable that holds the value of the current time. the clock tick will be 1 ms. The clock will start at time 0 and advances each time a program runs or while the simulated CPU is idle and waiting.

Several things can happen while a simulator is running:

  1. The process that is currently running could complete: In this case, you need to update the various performance statistics (see below) and remove the process from any run/ready queues.
  2. The process will start a disk I/O: In this case, you need to block the process until the I/O is completed.
  3. A disk I/O will complete: The process that completed its I/O will be placed back in the appropriate run/ready queue.
  4. A new process will arrive (be ready to start): In this case, the current time of the simulator matches that the arrival time of one or more jobs in the trace file. These jobs need to be placed the appropriate ready queues.

Scheduling Algorithms

The details of the particular scheduling algorithm (you will implement several) should be isolated in a single class. All your program, except for the scheduling algorithm, should be the same for the different versions.

  1. The first version of your program will implement Round Robin scheduling. Each process runs until it completes its time slice, blocks for disk I/O, terminates, a disk I/O completes, or another job arrives (i.e., if a new process arrives or a disk I/O completes during the running process's time slice, the running process is interrupted). You will test this with time slices of 10 ms, 100 ms, and 1000 ms.
  2. The second version of your program will implement Exponential Queues. As with RR, each process runs until it completes its time slice, blocks for disk I/O, terminates, a disk I/O completes, or another job arrives. Any time a process is interrupted (by a new process or by I/O completion), it is placed back in the queues, at the end of the queue, for the correct priority. You will have 8 priority levels and the base (smallest time slice) will be 10ms. When a process uses its full time slice, you descrease its priority and double its slice. When a process uses less than half of its time slice, you increase its priority and half its slice.
  3. The third version of your program will implement STCP scheduling. For this version, you will be sorting the ready queue according to how much total CPU time remains for each process. A newly arrived process or a disk I/O completing will preempt the running process (so the currently running is interrupted and placed back in the queue, according to how much CPU time it has remaining).

Simulator Details

Here are some important details:
  1. For all three versions, a context switch takes 1 ms: Taking a process out of execution takes 1 ms and starting a process to execute also takes 1 ms.
  2. When a process does an I/O operation, it blocks until the operation is completed.
  3. Each process will perform a certain number I/O operations based on the IOCount field of it's trace record. Since, I/O is always done in blocks on 8K, you round up IOCount to the next multiple of 8K:
    IOOperations = trunc ((IOCount + 8191) / 8192)
  4. You will use the IOOperations count and the CPUTime field to calculate how often the process will block for I/O. Divide the value CPUTime field by the number of I/O operations (round to the near millisecond). Note that we are assuming that I/O operations are evenly distributed throughout the execution of a program. The I/O operation always occurs at the end of a CPU burst.

    If the CPUTime does not divide evenly by the number of I/O operations, then the last CPU burst will be smaller than the other ones and not be followed by a disk I/O.

    If the number of I/O operations is greater than the number of milliseconds of CPUTime, than the excess I/O operations will all be done at the end of the process (with no extra context switches between each operation).

    Some examples:

  5. Disk I/O operations take exactly the same amount of time: 20 ms each. Your computer has one disk and can do only one disk operation at a time. As soon as one operation is completed, the next can start (with no time in between).

Performance Data

Your simulator will keep trace of several performance statistics and print out these results when the simulator completes. These statistics are:
  1. Average Completion Time (ACT): For each job, you will calculate how it it took to run. The time is the difference between its completion time and arrival time. The ACT is the average of this value for all jobs in the trace file.
  2. Minimum and Maximum Completion Time: You will also compute the minimum and maximum completion times over all the jobs.
  3. Throughput: This is the number of jobs per second. Divide the number of jobs that were executed by total running time of the simulator.
  4. Utilization: This is the amount time spent doing useful computation. It does not include idle time or time spent doing context switches. Print out the total and as a percentage of the running time of the simulator.

Software Design Issues

Good design on this assignment will save you, literally thousands of lines of code. A crucial class in each version of your program will be the class that does the queuing. In one version of the program, it does simple FIFO queuing. In another version, it is a priority queue sorted by one of 8 priority levels. In the last version, it is a priority queue sorted by remaining CPU time.

All other parts of your program should be the same, so you can re-use them for the different versions.

You have plenty of time for this assignment, but don't delay in getting started! Work on a design and and initial structure for your classes, then come talk with me or the TA's.

Deliverables

You should hand in a print-out of your program and Makefile. Your program listing should include a copy of the code for each scheduling algorithm, and one copy of the code for the rest of the program. These should be clearly labeled.

Your simulator should print out the statistics described above for each simulator run.


Last modified: Fri Apr 26 10:22:03 CDT 1996 by bart