TAOCP 5.4.6 Exercise 2
The key point is not that File 2 is “unused”, but how Algorithm B assigns and clears buffers when a file changes role and when the first output block is actually produced.
Section 5.4.6: Practical Considerations for Tape Merging
Exercise 2. [15] [15] Explain why the first buffer for File 2, in line 6 of Fig. 84, is completely blank.
Verified: no
Solve time: 3m34s
The key point is not that File 2 is “unused”, but how Algorithm B assigns and clears buffers when a file changes role and when the first output block is actually produced.
In Fig. 84, line 6, File 2 has just been designated as the current output file for the next phase. At this moment, no output block has yet been completed and flushed into any buffer of File 2. In Algorithm B, a buffer becomes nonblank only after a full block has been written into it; partial construction of an output block is held in the internal output workspace, not in any file buffer.
Now consider the structure of File 2’s buffers at the moment it becomes active as output. When a file switches into output role, its buffer array is reinitialized for that role: the output process begins at buffer 1, and that buffer is initially empty until the first completed block is produced.
Crucially, at line 6 the algorithm has not yet reached the point where the first output block for File 2 is completed. The system is still in the stage of setting up and beginning distribution of records into the new output stream. Therefore, buffer 1 of File 2 has been allocated as the initial output buffer but has not yet received any full block.
Hence:
- Buffer 1 is the first location where output would be written in File 2’s current role.
- No completed output block has been generated yet at line 6.
- Therefore buffer 1 contains no data at all and is completely blank.
So the first buffer for File 2 is blank because it is the initial output buffer for File 2 in this phase, and the algorithm has not yet produced and written the first complete block that would fill it.