Previous Table of Contents Next


TABLE 35.5 State Probabilities for Example 35.5

Number of Jobs at
Terminals CPU Disk
A
Disk
B
Probability

0 0 0 3 0.021
0 0 1 2 0.031
0 0 2 1 0.047
0 0 3 0 0.070
0 1 0 2 0.010
0 1 1 1 0.016
0 1 2 0 0.023
0 2 0 1 0.005
0 2 1 0 0.008
0 3 0 0 0.003
1 0 0 2 0.063
1 0 1 1 0.094
1 0 2 0 0.141
1 1 0 1 0.031
1 1 1 0 0.047
1 2 0 0 0.016
2 0 0 1 0.094
2 0 1 0 0.141
2 1 0 0 0.047
3 0 0 0 0.094
1.000

Without the table, the probability of one job at disk A can be computed as follows:

Similarly, probabilities of 0, 2, and 3 jobs at disk A can be shown to be 0.383, 0.211, and 0.070. Using these values, the average queue length at disk A can be shown to be 0.97 and the variance of the queue length is 0.87.

The system throughput is

The device utilizations are

UCPU = XDCPU = 0.264 × 0.78 = 0.206

UA = XDA = 0.264 × 2.34 = 0.618

UB = XDB = 0.264 × 1.56 = 0.412

The average number of jobs at the devices are

The device reponse times are

The system response time is

We can check the computation by computing the average number of jobs in the system:

N = X(R + Z) = 0.264(6.694 + 4.68) = 3

The complete convolution algorithm is summarized in Box 35.1.

Box 35.1 Convolution Algorithm

Inputs:
α = scaling factor
N = number of users
Z = think time
M = number of devices (not including terminals)
Si = service time per visit to the ith device
Vi = number of visits to the ith device
Outputs:
X = system throughput
Qi = average number of jobs at the ith device
Ri = response time of the ith device
R = system response time
Ui = utilization of the ith device
P(n) = probability of queue length vector being n
Scaling: y0 = αZ
FOR i = 1 to M DO yi = αSiVi
Initialization:
G(0) = 1
FOR n = 1 TO N DO G(n) = yn0/n!
Compute G(N):
FOR i = 1 TO M DO
BEGIN
FOR n = 1 TO N DO G(n) = G(n) + yiG(n–1)
END
Compute performance metrics:

Check: N = X(R + Z)
State probabilities:

EXERCISES

35.1  Consider a batch system with two disks. Each job makes 20 visits to disk B and 4 visits to disk A. The service times per visit to the CPU, disk B, and disk A are 40, 30, and 25 milliseconds. The degree of multiprogramming is 3. Determine the distribution of the CPU queue length. Also, find the system throughput varying the degree of multiprogramming from 1 to 3.
35.2  Analyze the timesharing system of Exercise 33.6 using the convolution method with N = 3 users. Determine the distribution of the CPU queue length.


Previous Table of Contents Next

Copyright © John Wiley & Sons, Inc.