TAOCP 5.4.9 Exercise 23

Section 5.4.9: Disks and Drums

Exercise 23. ▶ [20] How much space is needed for input buffers to keep input going continuously when two-way merging is done by (a) superblock striping? (b) the Gilbreath principle?

Verified: no
Solve time: 17m53s

Solution

The problem asks for the input buffer space required to keep the drum(s) busy continuously during a two‑way merge, using two different techniques.
The relevant parameters from the section are:

• 1 track = 5000 characters.
• Drum revolution time = 25 ms (so reading one full track takes 25 ms).
• Internal processing rate = 1 record per 500 µs.
• Record length = 100 characters → 50 records per track.
• Processing one track = 50 × 500 µs = 25 ms, exactly matching the read time.

Because the read time and the processing time per track are equal, a single buffer would give only 50 % drum utilization (read 25 ms, process 25 ms, read 25 ms, …). To achieve 100 % utilization the next track must be read while the current track is being processed; this requires at least two buffers in the standard double‑buffering scheme. The two methods mentioned, however, have different buffer requirements because of the way they organise the data.

(a) Superblock striping

In superblock striping the two input files are placed on two separate drum units.
A “superblock” is exactly one track (5000 characters). To keep both drums busy continuously we must read a track from one drum while the other drum’s track is being processed.
The algorithm works as follows:

1. Read track 1 of file A into buffer A (25 ms).
2. Read track 1 of file B into buffer B (25 ms).
3. Merge the two tracks. Because the merge consumes records from both buffers, one buffer will become empty first (or both simultaneously). As soon as a buffer becomes empty, we immediately start reading the next track of the corresponding file into that same buffer. The other buffer still contains data that will last at least 25 ms (since the total merge time for two tracks is 50 ms and the first buffer lasted at most 25 ms). Hence the read of the next track finishes exactly when the second buffer is exhausted, and the drum is never idle.

This scheme uses two input buffers (one per drum), each of one track.
Total space = 2 × 5000 = 10 000 characters.

(b) The Gilbreath principle

The Gilbreath principle merges two files on a single drum. The blocks of the two files are interleaved on the drum in the order
(a_1, b_1, a_2, b_2, \dots)
and the first key of each block is stored at the end of the preceding block of the other file (see Exercise 22). Concretely, block (b_j) contains the key (\alpha_{j+1}) (the first key of the next (a) block), and block (a_j) contains the key (\beta_{j+1}).

The merge proceeds with only one input buffer:

• Read block (a_1) into the buffer. The first key of (b_1) is already known (it was stored in a register from the previous step, or initially it is the first key of the file).
• Merge records from the buffer with the (known) current key of the (b) file. When the buffer is exhausted, we already know the first key of (b_2) (it was stored in (a_1)). We then read (b_1) into the same buffer.
• While reading (b_1) we continue merging using the (now known) first key of (a_2) (which was stored in (b_1)). Because the drum has no seek time and the blocks are contiguous, the next block is always under the head when the current read finishes. The read of the next block starts immediately after the previous read completes, so the drum is busy 100 % of the time.

No second input buffer is ever needed; the look‑ahead keys are kept in a few registers.
Total space = 5000 characters (one track).

Answers

[ \boxed{\text{(a) } 10,000 \text{ characters (2 tracks)} \qquad \text{(b) } 5,000 \text{ characters (1 track)}} ]

∎