TAOCP 2.2.5 Exercise 7

The statement `JANZ CYCLE` at line 154 was intended to skip the "give up" activity `U4` for a user if the elevator had already arrived at the user's floor.

taocpmathematicsalgorithmsvolume-1medium

Section 2.2.5: Doubly Linked Lists

Exercise 7. [25] Although bugs in programs are often embarrassing to a programmer, if we are to learn from our mistakes we should record them and tell other people about them instead of forgetting them. The following error (among others) was made by the author when he first wrote the program in this section: Line 154 said JANZ CYCLE instead of JANZ U4A. The reasoning was that if indeed the elevator had arrived at this user's floor, there was no need to perform the "give up" activity U4 any more, so we could simply go to CYCLE and continue simulating other activities. What was the error?

Verified: no
Solve time: 40s

Solution

The statement JANZ CYCLE at line 154 was intended to skip the "give up" activity U4 for a user if the elevator had already arrived at the user's floor. The correct line, JANZ U4A, branches instead to a subroutine U4A that handles the cancellation of U4 and allows the user to proceed to enter the elevator (U5).

The error arises because CYCLE is the main control loop for scheduling the next user or elevator action. If the program jumps directly to CYCLE, then the current user's state is not properly updated: the program fails to delete the scheduled U4 activity, and it fails to move the user into ELEVATOR via U5. Consequently, the user remains in QUEUE[IN] indefinitely, and CALLUP[IN] or CALLDOWN[IN] is not reset. This violates the intended simulation logic of steps U4 and U5.

Formally, let X be the location of the current user in QUEUE[IN]. At the instant the elevator arrives at FLOOR = IN, the correct action is to:

  1. Cancel any pending U4 activity for this user.
  2. Remove the user from QUEUE[IN].
  3. Set CALLCAR[OUT] \leftarrow 1.
  4. Transition the user to U5 so they enter the elevator.

The erroneous jump JANZ CYCLE bypasses steps 1–4. In terms of the doubly linked list representing QUEUE[IN], the user's node NODE(X) is not deleted via

$$ \text{RLINK}(\text{LLINK}(X)) \leftarrow \text{RLINK}(X),\qquad \text{LLINK}(\text{RLINK}(X)) \leftarrow \text{LLINK}(X),\qquad \text{AVAIL} \Leftarrow X, $$

so QUEUE[IN] becomes inconsistent, with a node lingering that should have been removed. Any subsequent insertion or deletion in QUEUE[IN] might corrupt the list or produce incorrect simulation behavior. Moreover, the user's GIVEUPTIME is still counted, potentially triggering an erroneous "give up" even though the elevator has already arrived.

The effect of the error is thus a logical deadlock for that user: the simulation never properly progresses through U5 and U6 for the user whose U4 activity was bypassed. Other users are unaffected unless subsequent operations depend on the accurate state of QUEUE[IN] or CALLCAR[OUT].

Replacing JANZ CYCLE with JANZ U4A ensures that the pending U4 activity is canceled, the user enters the elevator correctly, and all link updates in the doubly linked list representation of QUEUE[IN] are performed. This preserves the correctness of the simulation: the user can now proceed through U5 and U6, and the elevator responds appropriately to the updated set of active users.

This completes the proof.

∎