Comp111: Operating Systems
Classroom Exercise 17
Queueing Theory
Fall 2018
group member 1: ____________________________ login: ______________
group member 2: ____________________________ login: ______________
group member 3: ____________________________ login: ______________
group member 4: ____________________________ login: ______________
group member 5: ____________________________ login: ______________
group member 6: ____________________________ login: ______________
group member 7: ____________________________ login: ______________
group member 8: ____________________________ login: ______________
A twostage pipeline is a queueing system in which two
independent M/M/1 queues with processing rates
μ_{1} and μ_{2} are connected in series:
The input to the pipeline is a stream of requests
whose interarrival rate is λ.
 Recall that a singlequeue system is in balance only
if λ/μ<1. Under what conditions is this twoqueue
system in balance? Why?

If a system is in balance, the output rate = the input rate.
Is it possible for a system to be in balance if the middle rate
in the above (between the two queues) does not match the input rate? Why?

Recall that for a single M/M/1 queue, the average jobs in system
is p/(1p), where p=λ/μ. What is the average waiting time
between request and response for the twoqueue system above?
Hint: by Little's law, waiting time * arrival rate = jobs in system.
 Suppose that we observe that average jobs in system for
μ_{1} and μ_{2} are 3 and 4, respectively and that
the wait time for a request to travel through the pipeline is 2
seconds. What is the average arrival rate λ?
 (Advanced) We have seen that a tworate source is equivalent
to a singlerate source
whose (interarrival) rate is the sum. Is a twoqueue pipeline with
task completion rates μ_{1}
and μ_{2} equivalent to a single M/M/1 queue
with some task completion rate μ? Why or why not?
 (Advanced) In class I have suggested that no real system satisfies
the queueing assumptions and that all queueing results are approximations.
I did not describe the kind of approximation. In particular, consider the M/M/1
result that the mean jobs in system are p/(1  p), where p=λ/μ.
Given that interarrival times are not exponential, and processing is not memoryless, Is this figure too high or too low? Why?