Comp111: Operating Systems
Classroom Exercise 14 Answers
Queues and Little's Laws
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 λ.
- Recall that a single-queue system is in balance only
if λ/μ<1. Under what conditions is this two-queue
system in balance? Why?
We need both queues to behave, which means that we require
both λ/μ1 < 1
and λ/μ2 < 1.
- 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?
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 λ.
- 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.
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
- 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 λ?
By Little's law, 3/λ + 4/λ = 2 seconds,
so that λ = 7/2 = 3.5 requests per second.
- (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?
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.
- (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
Both of these increase processing time.
So the prediction from theory is a lower bound for jobs in system.
- Job processing is not independent, which increases processing time.
- Arrivals are not independent; there are flash crowds.