TAOCP 5.4.9 Exercise 21

Exercise 21. ▶ [M15] How many blocks of an $L$-block file go on disk $j$ when the file is striped on $D$ disks?

Verified: no
Solve time: 45s

Solution

Let the file consist of (L) blocks, indexed (0,1,\dots,L-1). The file is striped across (D) disks, meaning that block (k) is placed on disk ((k \bmod D)). Disks are numbered (0,1,\dots,D-1). We want the number of blocks assigned to disk (j) ((0 \le j < D)).

Apply the division algorithm to (L) and (D): [ L = qD + r,\qquad 0 \le r < D. ] The blocks assigned to disk (j) are exactly those with indices (j + mD) for integers (m \ge 0) such that (j + mD < L).

If (j < r): the largest admissible (m) is (q), because (j + qD \le r-1 + qD = qD+r-1 = L-1), while (j + (q+1)D \ge D > L-1). Hence there are (q+1) blocks.
If (j \ge r): the largest admissible (m) is (q-1), because (j + (q-1)D \le D-1 + qD - D = qD-1 \le L-1) (since (r < D)), while (j + qD \ge r + qD = L). Hence there are (q) blocks.

If (D > L), then (q = 0) and (r = L). The rule still holds: disks with (j < L) receive (1) block, disks with (j \ge L) receive (0) blocks.

Therefore, the number of blocks on disk (j) is [ \boxed{\left\lfloor \frac{L}{D} \right\rfloor + \begin{cases} 1 & \text{if } j < L \bmod D,\[2pt] 0 & \text{otherwise.} \end{cases}} ] (If disks are numbered (1) through (D) instead, replace (j) by (j-1) in the condition.)