Modeling and Analysis of Computer Systems
                        Breadth Screening Exam

                       University of Wisconsin
                              Fall 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)  XXXXXXX

     (b)  the Erlang distribution

     (c)  XXXXXXX

     (d)  Petri Net


     Question 2

     Assume a queueing system that conists of a single queue  and
     two  servers.   Customers arrive at the queue according to a
     known stochastic process.  The service demand of a  customer
     is  a  random  variable  with a known distribution.  The two
     servers have different service rates


     (a)  What is the highest achievable throughput of  the  sys-
          tem?

     (b)  Which states in such a system are undesirable i) if the
          goal  is to maximize the system throughput?  ii) if the
          goal is to minimize customer response time?

     (c)  When a new job arrives and at least one server is idle,
          the  system  scheduler may either place it in the queue
          or assign it to a server. How would you use information
          about  the  residual  life  of the job(s) in service to
          make an intelligent decision about where to  place  the
          incoming job?  Motivate your answer!


     Question 3

     A closed queuing network with exponential service  times  at
     all centers may have a reducible Markov Chain.

     (a)  Show how a closed queueing network that consists of two
          FCFS  queues  may  have  such  states.   Give the state
          diagram of the network.

     (b)  Does the network in (a) satisfy local balance? Explain!

     (c)  Can the network in (a) reach steady state? Explain!

     (d)  How would you derive the mean cycle time of the network
          in  (a)?  You do not have to give a closed form expres-
          sion for the mean cycle time. Just describe a method to
          derive it.


     Question 4

     Suppose that two processes in a parallel program synchronize
     through  a  single lock variable.  Furthermore, suppose that
     each process repeatedly performs the following  four  opera-
     tions:  1)  execute  for a random amount of time that can be
     represented by a two-stage Erlang distribution, 2)  ask  for
     the  lock,  and  if necessary busy wait until it is free, 3)
     hold the lock for a  random  amount  of  time  that  can  be
     represented  by  an exponential distribution, and 4) release
     the lock.


     (a)  Construct a simple model that would allow you to calcu-
          late  mean waiting time for the lock.  (Note that there
          is more than one correct answer to this question.)

     (b)  Outline in detail how the model is solved and  how  the
          waiting time is calculated.