TAOCP 2.2.5 Exercise 5

Section 2.2.5: Doubly Linked Lists

Exercise 5. [20] In Table 1, user 10 arrived on floor 0 at time 1048. Show that if user 10 had arrived on floor 2 instead of floor 0, the elevator would have gone up after receiving its passengers on floor 1, instead of down, in spite of the fact that user 8 wants to go down to floor 0.

Verified: no
Solve time: 39s

Solution

The scenario given concerns the discrete simulation of the Caltech Mathematics building elevator, using the routines described in Section 2.2.5. The elevator is initially at FLOOR = 2, STATE = NEUTRAL, with no passengers on board and no active calls, except as generated by the preceding users. Table 1 indicates that user 10 arrived at FLOOR = 0 at TIME = 1048, but the exercise asks for the hypothetical situation where user 10 instead arrives at FLOOR = 2. We must show that this change affects the direction of the elevator after stopping on floor 1.

First, consider the actual sequence of events when user 10 arrives on floor 0. According to the elevator algorithm, when users press buttons, the corresponding CALLUP or CALLDOWN variable is set to 1 in step U2. The elevator responds to the earliest call via the DECISION subroutine if it is in NEUTRAL state.

User 8, arriving earlier, is waiting on floor 3 to go down to floor 0. User 10, at floor 0, wants to go up or down (floor not specified, but the point is that the call is at a lower floor). After stopping on floor 1 to pick up passengers, the elevator evaluates STATE according to step E5 of the elevator coroutine. The elevator chooses to continue in the direction dictated by pending calls in that direction. With user 10 at floor 0, the nearest pending calls below floor 1 are active, so the elevator moves down.

Now, suppose user 10 arrives instead at floor 2. Step U2 sets either CALLUP[2] or CALLDOWN[2] according to the user's destination. Since FLOOR = 2 initially, the user is already at the elevator's location. Step U5 moves the user into the ELEVATOR list, sets the appropriate CALLCAR variable, and triggers a state change from NEUTRAL to GOINGUP or GOINGDOWN depending on the user's destination.

After picking up passengers on floor 1, the elevator evaluates its STATE. Step E5 examines the CALLUP, CALLDOWN, and CALLCAR variables. In this hypothetical, user 10 is already on board and has a destination above floor 1. The elevator sees a pending upward request at floor 2 or higher. Step E5 thus sets STATE \leftarrow GOINGUP. Although user 8 wishes to go down to floor 0, that request is below the current floor. By the elevator rules, the elevator continues in the current direction until no requests remain in that direction. Therefore, after floor 1, the elevator goes up rather than down.

To formalize, let F denote the current floor after servicing floor 1. Let S denote the elevator state. Let C_\text{up}[j], C_\text{down}[j], and C_\text{car}[j] denote the binary call variables. Step E5 updates S as follows:

If S = NEUTRAL and there exists j > F with C_\text{up}[j] = 1 or C_\text{car}[j] = 1, then S \leftarrow GOINGUP.
If S = NEUTRAL and there exists j < F with C_\text{down}[j] = 1 or C_\text{car}[j] = 1, then S \leftarrow GOINGDOWN.

In the hypothetical, after floor 1, C_\text{car}[j] = 1 for some j > 1 due to user 10. No calls exist above floor 1 other than user 10's destination, so the first condition applies and the elevator moves up. The call for user 8 to go down to floor 0 is below the current floor and does not influence the immediate decision to move up.

Thus, by following the elevator algorithm step by step and observing how STATE is determined based on calls above and below the current floor, we conclude that the elevator would go up after floor 1, rather than down, when user 10 is on floor 2. This completes the proof.

∎

$$ \boxed{\text{Elevator moves up after floor 1 if user 10 arrives on floor 2.}} $$