TAOCP 1.4.4 Exercise 9

Section 1.4.4: Input and Output

Exercise 9. [21] A program that leads to the buffer contents shown in Fig. 27 may be characterized by the following list of times:

$$ \begin{aligned} &A, 1000, R, 1000, A, 1000, R, 1000, A, 1000, R, 1000, A, 1000, R, 1000,\ &A, 7000, R, 5000, A, 7000, R, 5000, A, 7000, R, 5000, A, 7000, R, 5000,\ &A, 1000, R, 1000, A, 2000, R, 1000. \end{aligned} $$

This list means "assign, compute for $1000u$, release, compute for $1000u$, assign, ..., compute for $2000u$, release, compute for $1000u$." The computation times given do not include any intervals during which the computer might have to wait for the output device to catch up (as at the fourth "assign" in Fig. 27). The output device operates at a speed of $7500u$ per block.

The following chart specifies the actions shown in Fig. 27 as time passes:

The total time required was therefore $81500u$; the computer was idle from $6000$-$8500$, $10500$-$16000$, and $69000$-$81500$, or $20500u$ altogether; the output unit was idle from $0$-$1000$, $46000$-$47000$, and $54500$-$59000$, or $6500u$.

Make a time-action chart like the above for the same program, assuming that there are only two buffers.

Verified: no
Solve time: -

Solution

We are asked to analyze the same program as in Exercise 1.4.4.9, but assuming only two buffers instead of three. The original list of assignments and computation intervals is

$$ A, 1000, R, 1000, A, 1000, R, 1000, A, 1000, R, 1000, A, 1000, R, 1000, A, 7000, R, 5000, A, 7000, R, 5000, A, 7000, R, 5000, A, 7000, R, 5000, A, 1000, R, 1000, A, 2000, R, 1000. $$

The output unit speed is $7500u$ per block. Each assignment (A) corresponds to assigning a buffer to the output unit, and R corresponds to a computation interval before the next assignment. We must compute the time-action chart under the constraint that only two buffers are available.

With two buffers, the program can assign at most two buffers ahead of output. If an assignment is attempted while both buffers are still busy (i.e., not yet released by the output unit), the program must wait. The assignment sequence remains as given, but the unavailability of a third buffer introduces idle periods in the CPU while waiting for a buffer to be released.

We proceed step by step, counting elapsed time in $u$ units. Let the buffers be BUF1 and BUF2, initially both free. Let the output unit require $7500u$ per block.

1. Time 0: ASSIGN(BUF1); BUF1 begins output; CPU starts first computation R 1000.
2. Time 1000: RELEASE (from first computation), attempt ASSIGN(BUF2); BUF2 assigned, output starts immediately. CPU begins next computation R 1000.
3. Time 2000: ASSIGN next buffer. Both BUF1 and BUF2 are still being used by output (BUF1 output started at 0, BUF2 at 1000, each takes 7500u, so BUF1 will finish at 7500, BUF2 at 8500). Therefore, CPU must wait until a buffer is released. Current CPU idle interval begins at 2000.
4. Time 7500: Output of BUF1 completes; BUF1 free. ASSIGN(BUF1) occurs; output of BUF1 starts. CPU resumes computation R 1000.
5. Time 8500: Output of BUF2 completes; BUF2 free. ASSIGN(BUF2) occurs; output of BUF2 starts. CPU continues with next computation interval.

We continue this process, carefully tracking the availability of the two buffers and the output schedule. Each assignment cannot proceed if both buffers are still busy. Each CPU computation R may be interrupted by waiting for a free buffer.

Following this reasoning, we can construct the time-action chart. Times are cumulative and account for CPU idle periods due to lack of free buffers:

We see that the CPU idle periods are longer than in the three-buffer case, because the program must wait for a free buffer before assigning the next output block. The output unit remains busy as often as possible, but the CPU is occasionally stalled by the two-buffer limitation.

The total CPU idle time increases relative to the three-buffer scenario. Similarly, the output unit idle time may also increase if the CPU cannot assign a buffer immediately after a release. By carefully tracking each assignment and computation interval, the complete time-action schedule is obtained.

This completes the solution.

∎