Solution to COMP9334 Revision Problems – Week 3B
Revision Problem #1
The states are 2-tuple (x,y) where x is the number of calls at the receptionist and y is the number of calls at the technical staff. We have x = 0 or 1; and, y = 0, 1, 2. There are altogether 6 states (0,0), (0,1), (0,2), (1,0), (1,1) and (1,2). The state space diagram is as follows:
Note that in the state transition diagram, the transition rate from (0,2) to (0,1) should be 2q. The reason is that each call departs with a rate q and if any one of them has finished, then the state will move from (0,2) to (0,1). Based on the above state space diagram, the balance equations are
P(0,0) p = P(0,1) q
P(0,1) (p+q) = P(1,0) r + P(0,2) 2q P(0,2) (p+2q) = P(1,1) r + P(1,2) r P(1,0) r = P(0,0) p + P(1,1) q P(1,1) (q+r) = P(0,1) p + P(1,2) 2q P(1,2) (2q+r) = P(0,2) p
Where P(0,0) = Probability in State (0,0) etc.
You can choose any five of these equations together with the conservation of probability relation
P(0,0) + P(0,1) + P(0,2) + P(1,0) + P(1,1) + P(1,2) = 1 to solve for the probabilities.
To find the probability that a technical staff is busy: This is the probability in the states (0,1), (0,2), (1,1) and (1,2) where there is at least one call being answered by a technical staff. The required probability is the sum P(0,1)+P(0,2)+P(1,1)+P(1,2)
To find the probability that an arriving call is dropped by the receptionist: This is the probability that the receptionist is busy. The receptionist is busy in the states (1,0), (1,1) and (1,2). The required probability is the sum P(1,0) + P(1,1) + P(1,2)
Finally, we are asked to calculate the “good” throughput of the call centre (i.e. the rate at which satisfied customers leave the call centre, having their calls answered by both the receptionist and the technical staff). This is effectively the total departure rate of the calls answered by the technical staff. The answer is therefore
P(0,1) q + P(0,2) 2q + P(1,1) q + P(1,2) 2q
An alternative viewpoint is the rate at which the receptionist transfers the calls to the technical staff. The “good” throughput is also give by:
P(1,0) r + P(1,1) r
You can use the flow balance equations to prove that these two answers are the same.
Revision problem #2
If we speed up the CPU by k times, then the mean processing rate of the CPU will be 6k transactions per minute. Since the workload remains the same, we can use the same Markov chain that was used in the lecture except that we need to multiply the transition rates from the CPU by k times.
Thus, if we speed up the CPU by k times, the Markov chain should be:
For any given value of k, you can solve this Markov chain to obtain the response time via the following steps:
• Form the balance equations
• Solve the balance equations together with conservation of probability relation
to obtain the steady state probabilities.
• Compute the throughput from the steady state probabilities
• Use Little’s Law to obtain the mean response time.
(This is exactly the same procedure that we used in the lecture)
What this means is that for every value of k, you will be able to find the response time. You can write a computer program which for a given value of k, determine what
the response time is for that value of k. An example of such a program in Python is “cpu_speedup.py”.
By using the results from this program, you can plot a graph to see how the speed up factor k influences the response time. (You can modify the program cpu_speedup.py slightly so that it will calculate the response time for a number of values of k and plot the graph, see the program cpu_speedup_graph.py)
From this graph, you can see that if you want the response time to reduce to 0.65 minutes per transaction, you need to speed up the CPU by 1.86 times.
Speeding up the CPU may not be the best idea, because the bottleneck of the system is the slow disk. A more effective solution is to upgrade the slow disk.