TAOCP 1.4.4 Exercise 10
Let the three buffers of exercise 9 be denoted by $\mathrm{BUF1}$, $\mathrm{BUF2}$, and $\mathrm{BUF3}$.
Section 1.4.4: Input and Output
Exercise 10. [21] Repeat exercise 9, except with four buffers.
Verified: no
Solve time: -
Solution
Let the three buffers of exercise 9 be denoted by $\mathrm{BUF1}$, $\mathrm{BUF2}$, and $\mathrm{BUF3}$. With four buffers available, introduce an additional buffer $\mathrm{BUF4}$. The computation schedule is unchanged:
$$ \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} $$
The output device requires $7500u$ per block. Since four buffers are available, the computer can continue assigning buffers during the long output intervals without waiting until all four buffers become occupied. Waiting occurs only if all four buffers are full and no output has yet completed.
The resulting time-action chart is as follows.
| Time | Action | Time | Action |
|---|---|---|---|
| $0$ | ASSIGN(BUF1) | $38500$ | RELEASE |
| $1000$ | RELEASE, OUT BUF1 | $39000$ | ASSIGN(BUF1) |
| $2000$ | ASSIGN(BUF2) | $40000$ | OUT BUF2 |
| $3000$ | RELEASE | $46000$ | ASSIGN(BUF3) |
| $4000$ | ASSIGN(BUF3) | $47000$ | RELEASE |
| $5000$ | RELEASE | $48000$ | ASSIGN(BUF4) |
| $6000$ | ASSIGN(BUF4) | $48500$ | OUT BUF3 |
| $8500$ | OUT BUF2 | $50000$ | RELEASE |
| $9500$ | RELEASE | $51000$ | ASSIGN(BUF1) |
| $10500$ | ASSIGN(BUF1) | $52000$ | OUT BUF4 |
| $16000$ | OUT BUF3 | $58000$ | ASSIGN(BUF2) |
| $23000$ | RELEASE | $59000$ | RELEASE |
| $23500$ | OUT BUF4 | $60000$ | ASSIGN(BUF3) |
| $28000$ | ASSIGN(BUF2) | $60500$ | OUT BUF1 |
| $31000$ | OUT BUF1 | $62000$ | RELEASE |
| $35000$ | RELEASE | $63000$ | ASSIGN(BUF4) |
| $36000$ | ASSIGN(BUF3) | $64000$ | RELEASE |
| $37000$ | RELEASE | $65000$ | ASSIGN(BUF1) |
| $38000$ | ASSIGN(BUF4) | $65500$ | OUT BUF2 |
| $66500$ | OUT BUF3 | $69000$ | Computation stops. |
| $73000$ | OUT BUF4 | $80500$ | OUT BUF1 |
| $88000$ | Output stops. |
The total time required is therefore
$$ 88000u. $$
The computer is idle only after computation finishes at time $69000$, while output continues until time $88000$. Hence the computer is idle for
$$ 88000-69000=19000u. $$
The output device is idle during the intervals
$$ 0\text{-}1000,\qquad 46000\text{-}48500,\qquad 59000\text{-}60500, $$
whose total duration is
$$ 1000+2500+1500=5000u. $$
Thus the final results are
$$ \boxed{\text{Total time }=88000u} $$
$$ \boxed{\text{Computer idle time }=19000u} $$
$$ \boxed{\text{Output idle time }=5000u} $$