TAOCP 1.4.4 Exercise 14
In the multiple-buffering scheme described in the text, the computational program and the CONTROL coroutine communicate by means of the operations ASSIGN and RELEASE.
Section 1.4.4: Input and Output
Exercise 14. [20] Suppose the computational program does not alternate between ASSIGN and RELEASE, but instead gives the sequence of actions ... ASSIGN ... ASSIGN ... RELEASE ... RELEASE. What effect does this have on the algorithms described in the text? Is it possibly useful?
Verified: no
Solve time: -
Solution
In the multiple-buffering scheme described in the text, the computational program and the CONTROL coroutine communicate by means of the operations ASSIGN and RELEASE. Under the normal discipline, every ASSIGN is eventually followed by a RELEASE before another ASSIGN occurs. Thus the computational program holds at most one buffer at a time.
Suppose instead that the computational program executes
$$ \cdots\ \text{ASSIGN}\ \cdots\ \text{ASSIGN}\ \cdots\ \text{RELEASE}\ \cdots\ \text{RELEASE}. $$
After the first ASSIGN, one buffer is removed from the pool of free buffers and is reserved for computation. If a second ASSIGN is executed before the first buffer has been released, a second buffer is removed from the free pool and reserved also. Hence the computational program simultaneously possesses two buffers.
The algorithms themselves require essentially no change. The CONTROL coroutine already maintains a collection of available buffers and supplies one whenever ASSIGN is requested. Therefore repeated ASSIGN operations merely decrease the number of free buffers by a corresponding amount. Later RELEASE operations return those buffers to the free pool. The only restriction is that enough buffers must exist. If all buffers have been assigned and not yet released, a further ASSIGN request must wait until some buffer is released.
The effect is that buffers may accumulate in the computational program. Instead of processing one record and then returning its buffer immediately, the program may retain several records at once. This changes the buffering discipline from simple one-buffer-at-a-time processing to a form of queueing in which the computational routine can look ahead and hold several blocks simultaneously.
Such a modification can be useful. For example, some algorithms require information from two or more successive input blocks before a decision can be made. With the sequence
$$ \text{ASSIGN},\ \text{ASSIGN}, $$
the program may obtain two buffers containing consecutive records, compare them, merge them, or perform computations involving both before either buffer is released. More generally, $k$ successive ASSIGN operations allow the program to keep $k$ buffers available simultaneously, provided that enough buffers exist in the system.
The price paid for this flexibility is a reduction in the number of free buffers available to the I/O process. If too many buffers are retained, input or output may be forced to wait because no free buffer is available. Consequently, excessive use of consecutive ASSIGN operations can reduce the overlap between computation and I/O and thereby diminish the effectiveness of buffering.
Therefore the effect of the sequence
$$ \cdots\ \text{ASSIGN}\ \cdots\ \text{ASSIGN}\ \cdots\ \text{RELEASE}\ \cdots\ \text{RELEASE} $$
is to permit the computational program to hold several buffers simultaneously. This is potentially useful whenever computation must examine multiple buffered records at the same time, although it decreases the number of buffers available for continued input or output activity. ∎