TAOCP 5.4.9 Exercise 26
A $P$-way merge produces one output block per unit of time, where the time to write a block equals the time to read a block.
Section 5.4.9: Disks and Drums
Exercise 26. [26] [26] How many output buffers will guarantee that a P-way merge with randomized striping will never have to pause for lack of a place in internal memory to put newly merged output? Assume that the time to write a block equals the time to read a block.
Verified: yes
Solve time: 1m29s
Setup
A $P$-way merge produces one output block per unit of time, where the time to write a block equals the time to read a block. Output is written to disks using randomized striping, so successive output blocks are distributed across $D$ disks in a manner that is uniform in the sense of Section 5.4.9.
Each disk $d \in {1,\dots,D}$ receives a subsequence of the output blocks; let $S_d$ denote the stream of blocks assigned to disk $d$. Writing a block to a disk consumes one unit of time, and only one write per disk can be active at a time.
We are asked for the minimum number of output buffers in internal memory that guarantees that the merge never pauses due to lack of available space for newly produced output blocks.
The goal is to determine the smallest $B$ such that a $P$-way merge can run continuously without blocking on output allocation for any admissible randomized striping schedule.
Solution
Each output block is produced by the merge at a steady rate of one block per unit time. Each produced block is immediately assigned to exactly one disk according to the striping scheme, and must be placed into an output buffer until it is written.
Fix a disk $d$. The write operation for that disk takes one unit of time per block. Since the striping distributes blocks uniformly over $D$ disks, the stream $S_d$ receives approximately one block every $D$ time units on average. Thus the service capacity of disk $d$ strictly exceeds its average arrival rate.
However, the merge does not produce blocks in a disk-synchronous order. Two consecutive output blocks may be assigned to the same disk, while that disk is still busy writing the previous block. In that situation, without sufficient buffering, the merge would stall even though the system is stable in average rate.
To prevent any stall, each disk stream must be able to absorb at least one additional block while a write is in progress. Consider disk $d$. If it has only one output buffer, then whenever a block is being written, a newly assigned block for the same disk has no place to go, forcing the merge to pause. With two output buffers assigned to disk $d$, one buffer can be written while the other receives incoming blocks; this removes any dependency between the producer and the completion of the current write.
Thus each disk requires at least two buffers to decouple production from writing. Since there are $D$ disks and each disk stream is independent, the total number of output buffers must be at least $2D$.
To show sufficiency, assign two buffers per disk. When a block is produced, it is placed in the free buffer of its assigned disk. Writing proceeds from the other buffer of that disk whenever it is nonempty. Because a disk can always be writing one buffer while the next block is accumulated in the other, no production step is ever forced to wait for completion of a write.
No smaller allocation can guarantee nonblocking behavior, since reducing any disk below two buffers creates a state in which that disk is simultaneously writing one block and receiving a new block assignment with no free buffer available.
Verification
For each disk $d$, the system alternates between two roles: writing a stored block and accepting a newly produced block. The write operation occupies one buffer for one unit of time, while production may assign a block to the same disk during that interval. With a single buffer, the intersection of these events produces a forced wait condition. With two buffers, the intersection is absorbed without delay, since one buffer is always free whenever the other is occupied.
Since the argument applies independently to each disk stream $S_d$, and the striping ensures every produced block belongs to exactly one such stream, the global system remains nonblocking if and only if every stream has the stated buffering capacity.
This completes the proof. ∎
Answer
$$ \boxed{2D} $$