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 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:
a queueing system with two processors in series. Processor 1 completes tasks with rate μ1, while Processor 2 completes tasks with rate μ2. The two stages are connected together in series, and the input rate of processor 1 is the output rate for processor 2; both are λ.
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?

  2. 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?
  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.

  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 λ?

  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?

  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?