Programming Assignment III
Simulator Details
Detailed Overview
System
The simulation consists primarily of jobs, devices, and schedulers. The
jobs arrive at the system from the trace file and are scheduled to use
the system devices (the CPU and the disk). The amount of computing a job
wants to do before performing disk I/O or finishing execution is called
a burst. The program cycles through waiting for devices to interrupt
and then handling those interrupts -- which could entail removing a job
from a device and scheduling it with another device or discarding a job
that has finished. In the picture below, the Main Loop waits for a device
to interrupt. When it does, the Main Loop removes the job from that device
and either reschedules it with the same device (as in the case of a clock
interrupt), or it removes the current job from the device and enqueues
it with another.
Jobs
A Job
object represents a customer of services. It records the job's current
state and maintains statistics about its lifetime.
One Job is created
from each line of the input trace file, and a Job object spends its
lifetime being passed between
Schedulers
and
Devices.
The resources required by a Job are characterized by an amount of CPU
time needed (all times are in milliseconds) and the number of I/O operations
needed (each representing one disk transfer of Sim.BLOCKSIZE bytes of data).
The CPU time is generally distributed as evenly as possible into uniform
bursts between I/O operations (unless the job does no I/O at all); however,
occasionally a little randomness is injected into the system, and the CPU
burst is less than or greater than expected.
-
Attributes of a Job Object
-
Information about the starting state of the job
-
time of arrival
-
total amount of CPU time needed (in milliseconds)
-
total number of I/O operations needed
-
Information about the current state of the job
-
total CPU time remaining
-
number of I/O operations remaining
-
the length of the current burst
-
the time when the job started the current burst;
arrived or became ready
-
the amount of time remaining in the current burst
-
time the job last started using the CPU
-
Pointer to another Job object (allows Jobs to be chained together in a
linked-list fashion)
-
Methods of a Job Object
-
Constructor will read in a line from the file and initialize the job
-
void start() starts the job running
on the CPU (sets up the start time)
-
void stop() stops the job running
on the CPU (updates remaining CPU times)
-
int nextBurst() returns burst time
remaining
-
void doIO() does an I/O operation
(updates I/O remaining)
-
JobStats finish() completes the job
(returns job statistics)
-
int state() returns the current state
-
States
-
DONE - Job has completed
-
BLOCKED - Job is waiting for I/O
-
READY - Job is ready to execute on
the CPU
Devices
A Device
object represents a resource such as the Disk, the Clock, or the CPU. It
can be running or stopped; however once started, it will ``interrupt''
at some time in the future. The Device object keeps track of the current
device state as well as at what time the next interrupt will occur. The
method
Sim.mainLoop()
monitors devices closely for their interrupts, and when one occurs, Sim.mainLoop()
advances its current time to the interrupt time, stops the device, and
does what an ``interrupt handler'' for the device would do.
-
Attributes
-
current job (if running)
-
time of the next interrupt (Integer.MAX_VALUE
if not running)
-
time last started running
-
total time device has been running
-
Methods
-
void start(Job, amount) starts the
device running and determines next interrupt time
-
Job stop() stops the device and returns
the current job running
-
int nextInterrupt() returns time
of next interrupt
-
boolean isBusy() returns whether
the device is currently running
-
void printStats() prints the percentage
utilization of this device (time active / total time)
Schedulers
Schedulers
exist for the CPU and the Disk and schedule Jobs seeking service from a
device. They maintain a queue of waiting jobs and determine which of those
jobs will be the next to access the device. (Job objects contain pointers
to other Job objects -- these can be used to create the Job lists.) The
default
CPU scheduler uses a Round-Robin (RR) algorithm to determine the next
job to run; the
Disk
Scheduler uses a simple FCFS queuing algorithm.
The
Scheduler
base class presents a uniform interface for the scheduling of Jobs. It
also maintains statistics about the queue length of the scheduler.
-
Methods
-
boolean add(Job) adds a new job wanting
service. It returns true if the currently running job should be
preempted in favor of one of the queued jobs (probably the one just added).
-
Job remove() returns the next job
the scheduler has decided to run (and removes it from the queue).
-
boolean reschedule(Job job) is called
on a clock interrupt. It returns true if there is a reason to stop
the current job and run another instead. The argument is the current job.
-
printStats() prints
queue statistics (maximum length, average length, percent of time spent
at the various lengths)
Class
RRScheduler
is the provided CPU scheduling class (you will create the others). It maintains
its Jobs in a simple FIFO queue and always chooses the Job at the front
of the queue for the next CPU access. The reschedule()
method always returns true because
jobs are always rescheduled at the end of a quantum, and the add()
method always returns false because
jobs are not preempted by new arrivals.
-
Attributes
-
CPU device being scheduled
-
clock device for time slicing
-
pointer to the last Job in a circular queue
-
Methods
-
void add(Job) adds a job to the end
of the queue
-
Job remove() retrieves and removes
the job most recently served
-
Job first() returns the first job
in the queue without removing it
-
boolean reschedule() returns true
only if there is at least one other job waiting
DiskScheduler:
You don't need to worry about the disk scheduler for this assignment. In
brief, it maintains a FIFO queue of jobs and will provide access to the
disk in a FCFS (First Come First Served) order.
The main loop (found in
Sim.java)
cycles waiting for interrupts from the various devices. When one occurs,
the loop handles it as described earlier. The picture below shows the main
loop waiting on the various types of devices that can interrupt.
An informal trace of the main loop's code follows:
-
Create devices for Job Arrival, CPU, Disk, and Clock.
-
Create Schedulers for CPU and Disk.
-
repeat
-
Determine which device interrupts next and the time of the interrupt
-
If the time of the interrupt is ``infinity,'' terminate the simulation.
-
Update the current time
-
Stop the device
-
If the interrupt is a ....
-
Job Interrupt: Remove the job from the JobArrival device,
schedule it with the CPU or Disk Scheduler, and get the next job from the
trace file.
-
Disk Interrupt: Remove the job from the Disk and reschedule
it with the CPU or Disk Scheduler (if job is not finished).
-
CPU Interrupt: Remove the job from the CPU and reschedule
it with the Disk Scheduler (if job is not finished).
-
Clock Interrupt: Ask the CPU Scheduler if it wants to preempt the
current job. If so, remove that job from the CPU and return it to the CPU
scheduler.
-
In any case, if any device is idle, try to get a job from the associated
scheduler and start the device running servicing that job.
Input File
The simulation is driven by a trace file generated from an actual
Unix system. The lines of the trace file are sorted by program starting
time and are of the form:
CommandName StartTime CPUTime IOCount
-
CommandName: Character string name of the program.
-
StartTime: Time in 10 millisecond increments (100ths of a second)
since midnight - this is the time that the program arrived in the system.
-
CPUTime: 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, with blocks being 1K (1024
bytes). The number of disk operations required for a job is IOCount/Sim.BLOCKSIZE
rounded upwards.
Trace File Example:
sendmail 6724 0.00 6144
df 7509 0.11 447
sh 9888 0.05 1384
ksh 9890 0.06 942
ransleep 9891 0.03 186
sendmail 10325 0.02 6144
condor_v 10647 0.23 23768
Statistics and Debugging Output
On termination, the simulation prints a large number of statistics about
the run, including
-
The utilization of each device.
-
Information about each scheduler queue, including the maximum and average
queue lengths, and the percentage of the time it had various lengths.
-
Information about jobs, including the number of jobs run and throughput,
and summary statistics (min, max, and mean) about the per-job elapsed time,
CPU time, I/O operations, and penalty ratio.
-
Information about burst waiting times (elapsed time of the burst minus
duration of the burst). Waiting time includes both queuing delay
(time the burst sits in the CPU Scheduler queue) and scheduling overhead
(2ms for each process switch, in this simulation).
A log of significant events is also provided if the -v flag is
included on the command line. The -v may be repeated. One -v
traces job arrivals and departures. Two -v's adds events when
jobs become blocked or ready. Three -v's call for a trace of all
events, including clock interrupts. It also causes jobs to be indicated
in a more verbose format:
tcsh:3[0:00:00.080;3500/3266/234;15/14]
indicates that job tcsh, which was
the third job to arrive, arrived at time 0:00:00.080
(zero hours, zero minutes, zero seconds, and 80 milliseconds after start-up).
It needs a total of 3.5 seconds of CPU time, of which 3.266 seconds remain.
The current burst has 234ms of time remaining. Of a total of 15 I/O operations,
14 remain. Four -v's prints all queues each time around the main
loop.
The -t option requests a trace of significant events for each
job (printed when the job terminates) and for each device (printed at the
end of the simulation). This option slows the simulation considerably,
so you might want to use a shortened version of the data file.