Modeling and Analysis of Computer Systems
                        Breadth Screening Exam

                       University of Wisconsin
                             Spring 1987


     Directions:   All students taking the exam should answer ALL
     FOUR of the questions below.  The answers to these questions
     will be collected after 2 hours.

     Define the notation you use, and/or explain  your  reasoning
     in deriving an answer whenever appropriate.


     Question 1

     Define each of the following and  explain  specifically  why
     each is important:
     (a)  Markov Chain

     (b)  Product Form Queueing Network

     (c)  Local Balance Queues

     (d)  The Arrival Theorem


     Question 2

     Consider an M/M/1 queue with customer arrival rate  $lambda$
     and  service rate $mu$.  Assume there is an additional "sys-
     tem  reset"  arrival  process  that  is  Poisson  with  rate
     $alpha$.   Each system reset event immediately flushes (i.e.
     terminates) all jobs in the queue, including the job in ser-
     vice.


     (a)  Draw the Markov Chain diagram for this system.

     (b)  What condition(s) must be satisfied for the queue to be
          stable?


     Question 3

     A Stochastic Petri Net (SPN) is a  Petri  Net  in  which  an
     exponentially  distributed  delay  is  associated  with each
     transition.  An SPN analyzer will  use  Markov  Chain  tech-
     niques  to  compute  the steady state probability of finding
     the system in each state that is reachable from the  initial
     state, the steady state distribution of tokens in each place
     in the net, and the mean number of tokens in each  place  in
     steady  state.   Consider  the SPN model below.  Show how to
     compute the mean number of times  transition  t4  fires  per
     firing of t1, from the results produced by the analyzer.


     Question 4

     Consider a closed queueing network with K queues.   Consider
     a  particular  queue within the network, which will be meas-
     ured in two experiments.  In the first experiment,  schedul-
     ing discipline A is used at the queue.  In the second exper-
     iment, scheduling discipline B is used at the  queue.   Both
     experiments  are  run  over the interval [0,t] with the same
     workload, and all queues  other  than  the  measured  queues
     being  identical.   The measurements show that the number of
     observed job completions during the measurement interval  is
     greater  for  scheduling discipline A than for discipline B,
     but that the utilization of the server is lower for  discip-
     line  A  than for B.  Is there an explanation of real system
     behavior that explains this  result,  or  do  these  results
     indicate  clearly  that  there is some error in the measure-
     ments?