Previous Table of Contents Next


Since the jobs must visit the CPU before going to the disks or terminals, the CPU visit ratio is

VCPU =VA +VB + 1 = 181

The first step in operational analysis generally is to determine total service demands Di for all devices. In this case,

DCPU = 5 seconds
DA = SAVA = 0.050 × 80 = 4 seconds
DB = SBVB = 0.030 × 100 = 3 seconds

Using the forced flow law, the throughputs are

Using the utilization law, the device utilizations are

UCPU = XDCPU = 0.1963 × 5 = 98%
UA = XDA = 0.1963 × 4 = 78.4%
UB = XDB = 0.1963 × 3 = 58.8%

Visit ratios are one way of specifying the routing of jobs in a queueing network. Another way is to specify the transition probabilities pij of a job moving to the jth queue after service completion at the ith queue. The visit ratios and transition probabilities are equivalent in the sense that given one we can always find the other. In a system with job flow balance,

Here, subscript 0 is used to denote visits to the outside link. Thus, pi0 is the probability of a job exiting from the system after completion of service at the ith device. Dividing both sides of the equation by C0, we get

Since each visit to the outside link is defined as the completion of the job, we have

V0 = 1 (33.4)

Equations (33.3) and (33.4) are called visit ratio equations and can be used to get visit ratios from transition probabilities. A unique solution is always possible provided the network is operationally connected, that is, each device in the system is visited at least once by each job.

In central server models, after completion of service at every queue, the jobs always move back to the CPU queue:

These probabilities apply to the exit and entrance from the system (i = 0) also. Therefore, the visit ratio equations become

Thus, we can find the visit ratios by dividing the probability p1j of moving to the jth queue from the CPU by the exit probability p10.

Example 33.3 Consider the queueing network of Figure 32.8. The visit ratios given in Example 33.2 are VA = 80, VB = 100, and VCPU = 181.
It is easy to see in this case that after completion of service at the CPU, the probabilities of the job moving to disk A, disk B, or the terminals are respectively. Thus, the transition probabilities are 0.4420, 0.5525, and 0.005525.
Given the transition probabilities, we can find the visit ratios by dividing these probabilities by the exit probability (0.005525):

33.3 LITTLE'S LAW

Little's law is also an operational law. In its derivation in Section 30.3, we used only operational (measurable) quantities. The only assumption required was that the number of arrivals is equal to the number of completions. This is the operationally testable assumption of job flow balance.

We can apply Little's law to relate queue length Qi and response time Ri at the ith device:

Mean number in device = arrival rate × mean time in device

Qi = λ iRi

If the job flow is balanced, the arrival rate is equal to the throughput, and we can write

Qi = XiRi (33.5)

It is this version of Little's law that we will use frequently hereafter. Notice that the queue length Qi is synonymous with the number of jobs at the ith device. It includes not only the jobs waiting in the ith queue but also those getting service at the device.

Example 33.4 The average queue length in the computer system of Example 33.2 was observed to be 8.88, 3.19, and 1.40 jobs at the CPU, disk A, and disk B, respectively. What were the response times of these devices?
In Example 33.2, the device throughputs were determined to be

XCPU = 35.48, XA = 15.70, XB = 19.6

The new information given in this example is

QCPU = 8.88, QA = 3.19, QB = 1.40

Using Little's law, the device response times are
RCPU = QCPU/X = 8.88/35.48 = 0.250 second
RA = QAXA = 3.19/15.70 = 0.203 second
RB = QBXB = 1.40/19.6 = 0.071 second

33.4 GENERAL RESPONSE TIME LAW

All timesharing systems can be divided into two subsystems: the terminal subsystem and the central subsystem consisting of the remaining devices including the CPU, as shown in Figure 33.2. There is one terminal per user and the rest of the system is shared by all users.

It is interesting to note that Little's law can be applied to any part of the system. The only requirement is that the job flow in that part be balanced. In particular, it can be applied to the central subsystem, which gives

Q=XR

Here, Q is the total number of jobs in the system, R is the system response time, and X is the system throughput. Given individual queue lengths Qi at the devices, we can compute Q:

Q = Q1 + Q2 +...+ QM


FIGURE 33.2  Two components of a timesharing system: terminals and the central subsystem.


Previous Table of Contents Next

Copyright © John Wiley & Sons, Inc.