### 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:

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?