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).
-
CommandName
is a character string (maximum length of 10 characters) that contains
the name of the program;
-
StartTime
is the time in 10 millisecond increments (100ths of a second) since midnight -
this is the time that the program arrived in the system;
-
CPUTime
is the total CPU time, in seconds, used by this
program;
-
IOCount
records the total number of bytes of disk I/O done by this program.
Disk I/O always occurs in full blocks; blocks are
8K (8192 bytes).
We will ignore all other types of I/O (such as network or keyboard/display).
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:
-
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.
-
The process will start a disk I/O:
In this case, you need to block the process until the I/O is completed.
-
A disk I/O will complete:
The process that completed its I/O will be placed back in the appropriate
run/ready queue.
-
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.
-
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.
-
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.
-
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:
-
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.
-
When a process does an I/O operation, it blocks until the operation is
completed.
-
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)
-
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:
-
If the CPUTime is 20 and the number of I/O operations
is 4, then the process will need to start an I/O operation after each 5 ms of
execution.
So, the process will execute 5 ms, then do an I/O, execute another 5 ms,
then do an I/O, and so on.
-
If the CPUTime is 23 and the number of I/O operations
is 4, then the process will execute exactly as the above case, with an
additional 3 ms CPU burst after the last disk I/O.
-
If the CPUTime is 5 and the number of I/O operations is 10, then
the process will start one I/O operation after each 1 ms of exectution,
with 6 I/O operations being done together at the end of the last CPU
burst.
-
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:
-
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.
-
Minimum and Maximum Completion Time:
You will also compute the minimum and maximum completion times over all
the jobs.
-
Throughput:
This is the number of jobs per second.
Divide the
number of jobs that were executed
by
total running time of the simulator.
-
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