TAOCP 2.2.2 Exercise 6
Using the memory configuration of Fig.
Section 2.2.2: Sequential Allocation
Exercise 6. [10] Starting with the memory configuration shown in Fig. 4, determine which of the following sequences of operations causes overflow or underflow:
$(a)\ I_1;\quad (b)\ I_2;\quad (c)\ I_3;\quad (d)\ I_4I_4I_4I_4I_4;\quad (e)\ D_2D_2I_2I_2I_2.$
Verified: no
Solve time: -
Using the memory configuration of Fig. 4, stacks 1, 2, and 3 are empty, while stack 4 occupies the available space to the right. Hence TOP[1] = BASE[1], TOP[2] = BASE[2], and TOP[3] = BASE[3], so deletion from stacks 1, 2, or 3 gives UNDERFLOW. Stack 4 has free space available only after repacking according to cases (a) or (b).
For the given operation sequences:
(a) $I_1$ causes OVERFLOW, since stack 2 immediately blocks stack 1 and no stack to the right has spare room.
(b) $I_2$ causes OVERFLOW, by the same argument.
(c) $I_3$ causes OVERFLOW, since stack 4 occupies all remaining space and no room can be created.
(d) $I_4I_4I_4I_4I_4$ causes no OVERFLOW; stack 4 already has unused space extending to $L_\infty = 20$, and five insertions fit.
(e) $D_2D_2I_2I_2I_2$ gives UNDERFLOW immediately on the first operation $D_2$, because stack 2 is empty. Therefore the sequence cannot proceed further.
$$ \boxed{\text{(a) OVERFLOW;\ (b) OVERFLOW;\ (c) OVERFLOW;\ (d) no overflow or underflow;\ (e) UNDERFLOW at }D_2} $$