Homework 1

```                    UNIVERSITY OF CALIFORNIA
College of Engineering
Department of Electrical Engineering
and Computer Sciences
Computer Science Division

CS 162                                        Prof. Alan J. Smith

Assignment 1

In this assignment, you are to write a simulation of CPU schedul-
ing.  How to do this will be discussed in section.

You are to simulate a simple open queueing system that looks like
this:

_____            ______
|          |     |
---------->------>||||||||--------> | CPU |------------>
^      _____|           _____|
|                          |
|                          |
|---------<---------<------|

Arrivals

You  are  to  simulate  the arrival of 1000 customers.  Cus-
tomers arrive with exponentially distributed  interarrival  times
with  mean  interarrival  time 1.0.  Please generate the interar-
rival times only once; save them in an array and reuse  the  same
interarrival time that is less than 0.02 or  greater  than  40.0.
If  you have such a value, throw it away and generate a new one.)
The simulation ends when the 1000’th  customer  arrives.   Please
compute  the  actual  mean and standard deviation of the interar-
rival times, for all 1000, and print them out  as  part  of  your
answer.   Note  that  the system starts empty, and that the first
customer arrives at time T1, (not 0); i.e. after the first inter-
arrival time is added to zero.

Note:   Use at least 32-bit arithmetic for all calculations;
64-bit would be even better.  (That includes  all  random  number
generation,  interarrival  times and service times.)  With 32-bit
arithmetic, the chances that two numbers will be equal (e.g. that
two  events will happen at the same time) should be less than one
in one million.

-2-

Service Times

The service time of customers will be hyperexponential, dis-
tributed as follows:  With probability .8, the customer’s service
time will be exponential with mean 0.20.  With  probability  .15,
the customer’s service time will be exponential with mean service
time 1.0.  With probability .05, the customer’s service time will
be exponential with mean 10.0.  Please generate the service times
only once, and save them for use  in  each  simulation.   (Please
discard  any  service time that is less than 0.02 or greater than
40.0.  If you have such a value, throw it away and generate a new
one.)   Please  compute the actual mean and standard deviation of
the service times, for all 1000, and print them out  as  part  of

Note  that  for  each  simulation (below), the i’th customer
will arrive at the same time, and will require the same amount of
service  time.   Thus any difference in performance should be due
to the different scheduling algorithms, not  differences  in  the
random numbers.

Scheduling Algorithms

You are to simulate the following scheduling algorithms.  In
each case, consider three cases:  The time X  to  switch  between
processes is either 0.0, 0.01, or 0.10.  (I.e. each simulation is
run 3 times.)  This overhead is incurred whenever: (a) there is a
task  switch from job A to job B or (b) a job arrives to an empty
system.  If (c) the clock interrupts at the end of a quantum  and
the  same  job  is  resumed,  the overhead is X/2. (d) When a job
arrives to a busy system, the overhead is X/2  if  the  currently
running  job continues (after the arrival of the new job), and is
X if the running (currently active) job changes.  Logically,  you
can  consider  the  overhead in item (d) to consist of two parts:
X/2 overhead to accept the new job, and put it in the job  queue.
X/2  overhead to start whichever job starts next, if it is a dif-
ferent job.

Overhead times are not atomic.  If a job arrives in the mid-
arrival is processed (with its own overhead), and then the  prior

In each case, please compute the mean flow time for all cus-
tomers that have completed service and left the system, the  mean
number  of  customers  in the system (in the queue + in service),
the standard deviation of the flow time, and the mean  and  stan-
dard  deviation  of f(i)/s(i), where s(i) is the service time for
the i’th customer and f(i) is the flow time  for  the  i’th  cus-
tomer.   For  the  flow  time computation, please ignore any cus-
tomers left in the system after  the  1000’th  customer  arrives.
(I.e. your computation includes only customers who have completed
service and have left the system.)

-3-

First Come, First Serve

Please simulate the system using FCFS scheduling, with  each
job run to completion.

Shortest Remaining Processing Time

Please  simulate  the  system using SRPT scheduling.  At any
given time, you are to be running the job with the least  remain-
ing processing time.

Note:  Consider  the following case:  You are running job A.
Job B arrives, which is shorter than the remaining time of job A.
You  enter the task switch overhead to switch to job B.  While in
the task switch overhead, job C arrives, and C  is  shorter  than
the  remaining  time  for B.  You should process it the following
way:  Overhead X/2 to accept job B and put it in the  job  queue.
Overhead  of  X/2  to  accept  job C and put it in the job queue.
Overhead of X/2 to start job C.

Round Robin

Please simulate the  system  with  round  robin  scheduling,
using  a  time slice (quantum) of Q=0.0111, 0.11, and 1.0.  (I.e.
each of these simulations is run for  each  quantum  size.   Thus
this item requires that you run 9 simulations.)  If there is only
one job in the system, the switching overhead (X/2) still  occurs
every  time quantum, since the clock interrupts at that interval.

When a new job arrives, it always goes in the  back  of  the
queue.

Shortest Job First

Please  simulate the system using SJF scheduling.  Note that
this is not preemptive; once a job starts, it runs to  completion
(except  for  overhead  to  accept new jobs and enter them in the
queue).

Shortest Elapsed Time

Please simulate the system using SET scheduling.  Note  that
when  a  job  starts a period of execution, it will be allowed to
run for some time Q (Q=0.0111, 0.11, and 1.0) before being inter-
rupted,  unless  it completes first.  (I.e. each of these simula-
tions is run for each value of Q.)  Note  that  an  arriving  job
isn’t eligible to run until the quantum for the currently running
job ends.

Data

As noted above, you should generate  your  own  arrival  and
service  times.  For debugging purposes, we will also provide you
with a sample set of arrival and service times.  They will be  in

-4-

the  ~cs162/Homework directory.  You should also show the results
of all of your simulations using the  provided  (sample)  arrival
and service times.

Writeup

in some clear and useful manner.  Please do a  writeup,  approxi-
mately  one page single spaced, commenting and explaining on what
you’ve observed from the simulation runs.  Please relate what you
will depend on the quality and clarity of your writeup; it should
be in grammatically correct standard English.

Below  are the answers to some questions that have occurred.

1. If the first job ends at the same time the second  job  enters
the  queue, is this considered entry into an empty system, assum-
ing no other jobs in the queue?

This shouldn’t happen, but if it does, the answer is "no."

Note: If two events appear to  happen  at  identical  times,
then assume that the one that was entered in the event list first
happens first.  But in general, there should never  be  genuinely
simultaneous  events  -  if you are using 32-bit or 64-bit arith-
metic, what are the chances that  two  numbers  are  exactly  the
same??

2.  Is the "arrival time" of a job affected by the overhead asso-
ciated with getting the job into the system? Do we say a job  has
not arrived until the work has been done to introduce it into the
system?

No, the arrival time is simply (arrival time  of  j(i-1))  +
(interarrival time of j(i)).

3.  In  the timesliced algorithms, if a job arrives in the middle
of an executing job’s quantum,

a. is the overhead of the arriving job during or  after  the
quantum?

b.  does  the  running  job  get to run until the end of its
quantum, or does the scheduler run right away?

c. does the running job get to run for  its  entire  alotted
time,  i.e.  t(end_of_quantum)  +  overhead  of all arriving
jobs, if overhead is incurred during a quantum?

-5-

a. during; b. the arriving job is put  into  the  job  queue
immediately,  and then the job continues to run to the end of its
quantum; c. yes, the job runs for its entire alloted time, so the
time  of the end of the quantum will be affected by the number of
jobs that arrive during it.

General Instructions

1. The assignment must be programmed in Java.

2. The following files, and _only_ the following files,  must  be
submitted:  program  source,  writeup, README (optional - special
information for readers), makefile (optional).  3. If the program
is run with no arguments, it should generate random data for 1000
customers as specified in parts 1 and 2 of the assignment and run
the simulation on that data.

If  the  program  is  run  with the name of a file in the current
directory as an argument, it should read data  (interarrival  and
service  times) from that file and run a simulation on that data.

4. The program should print the following to the standard  output
when run (with the table filled in, of course):

% hw1
mean interarrival time: xx
std dev of interarrival times: xx
mean service time: xx
std dev of service times: xx

A    B    C    D    E    F    G
--------------------------------------------------------------------

FCFS   0
FCFS   0.01
FCFS   0.1
SRPT   0
SRPT   0.01
SRPT   0.1
RR     0      0.0111
RR     0      0.11
RR     0      1.0
RR     0.01   0.0111
RR     0.01   0.11
RR     0.01   1.0
RR     0.1    0.0111
RR     0.1    0.11
RR     0.1    1.0
SJF    0
SJF    0.01
SJF    0.1
SET    0      0.0111
SET    0      0.11

-6-

SET    0      1.0
SET    0.01   0.0111
SET    0.01   0.11
SET    0.01   1.0
SET    0.1    0.0111
SET    0.1    0.11
SET    0.1    1.0

key --
B: Quantum (if applicable)
C: Mean Flow Time
D: Std Dev of Flow Time
E: Mean flow_time(i) / service_time(i)
F: Std dev of flow_time(i) / service_time(i)
G: Mean number of customers

Hints and Information

1.  You should write an event driven simulation, not a clock
or interval type simulation.  What this means is that your  simu-
lator  basically  cycles through the following loop:  (get event)
(reset clock to event time) (update  system  statistics)  (update
system  state)  (generate  any  new  events and put them on event
list) (continue loop).

The TAs will talk more about event driven simulation in dis-
cussion section.

2.  You  can  generate  an  exponentially distributed random
variable with mean 1.0 by generating a Uniform (0,1] random  num-
ber  U,  and computing (-ln (U)).  ("ln" is the natural log.)  If
you want an exponentially distributed random number with mean  K,
multiply the one you generate by K.