Comp111: Operating Systems
Classroom Exercise 14 Answers
Queues and Little's Laws
Fall 2017

A two-stage 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 inter-arrival rate is λ.

  1. Recall that a single-queue system is in balance only if λ/μ<1. Under what conditions is this two-queue system in balance? Why?
    Answer: We need both queues to behave, which means that we require both λ/μ1 < 1 and λ/μ2 < 1.
  2. If a system is in balance, the output rate = the input rate. But 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?
    Answer: Suppose the rates for the second and third edges are λ2 and λ3. Since the second queue is in balance, λ3 must equal λ2. But we also know that for the whole system to be in balance, λ3 must equal λ Thus λ2 must equal λ.
  3. Recall that for a single M/M/1 queue, the average jobs in system is p/(1-p), where p=λ/μ. What is the average waiting time between request and response for the two-queue system above? Hint: by Little's law, waiting time * arrival rate = jobs in system.
    Answer: The wait time is the sum of the individual wait times, which is (for each queue) jobs in system / arrival rate. Thus the time for the composite system is p1/(1-p1)/λ + p2/(1-p2)/λ where p1=λ/μ1 and p2=λ/μ2.
  4. 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 λ?
    Answer: By Little's law, 3/λ + 4/λ = 2 seconds, so that λ = 7/2 = 3.5 requests per second.
  5. (Advanced) We have seen that a two-rate source is equivalent to a single-rate source whose (inter-arrival) rate is the sum. Is a two-queue 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?
    Answer: No. We would have to have some μ depending upon μ1 and μ2 for which the total time in system p1/λ(1-p1) + p2/λ(1-p2) = p/λ(1-p), where p=λ/μ and pi=λ/μi. A little algebra will convince you that any expression for μ contains λ, which means that it is impossible to choose a μ depending upon only μ1 and μ2.
  6. (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 inter-arrival times are not exponential, and processing is not memoryless, Is this figure too high or too low? Why?
    Answer: We know that the way "real life" differs is that
    1. Job processing is not independent, which increases processing time.
    2. Arrivals are not independent; there are flash crowds.
    Both of these increase processing time. So the prediction from theory is a lower bound for jobs in system.