TAOCP 2.2.5 Exercise 6

Section 2.2.5: Doubly Linked Lists

Exercise 6. [23] During the time period 1183-1233 in Table 1, users 7, 8, and 9 all get in the elevator on floor 1; then the elevator goes down to floor 0 and only user 8 gets out. Now the elevator stops again on floor 1, presumably to pick up users 7 and 9 who are already aboard; nobody is actually on floor 1 waiting to get in. (This situation occurs not infrequently at Caltech; if you get on the elevator going the wrong way, you must wait for an extra stop as you go by your original floor again.) In many elevator systems, users 7 and 9 would not have boarded the elevator at time 1183, since lights outside the elevator would show that it was going down, not up; those users would have waited until the elevator came back up and stopped for them. On the system described, there are no such lights and it is impossible to tell which way the elevator is going to go until you are in it; hence Table 1 reflects the actual situation.

What changes should be made to coroutines U and E if we were to simulate the same elevator system, but with indicator lights, so that people do not get on the elevator when its state is contrary to their desired direction?

Verified: no
Solve time: 43s

Solution

The desired change is that a user waiting on floor IN should enter the elevator only if the elevator is accepting passengers whose desired direction agrees with the user's destination. Therefore the elevator must distinguish between people waiting to go up and people waiting to go down, and step E4 must invite only the appropriate class of users to enter.

The variables CALLUP[j] and CALLDOWN[j] already record the desired direction of the waiting passengers, so no new call variables are needed.

Step U3 should be replaced by two queues on each floor, one for passengers wishing to go up and one for passengers wishing to go down. Thus, instead of inserting the user into QUEUE[IN], we insert the user at the rear of QUEUEUP[IN] if OUT>IN, and at the rear of QUEUEDOWN[IN] if OUT<IN. Correspondingly, step U4 deletes the user from the appropriate queue.

The principal modification is in step E4. When the elevator stops at floor j with state GOINGUP, passengers leaving the elevator are handled exactly as before, but only users in QUEUEUP[j] are allowed to enter. Users in QUEUEDOWN[j] remain waiting, even though the doors are open. Similarly, when the elevator stops at floor j with state GOINGDOWN, only users in QUEUEDOWN[j] are allowed to enter.

The case STATE=NEUTRAL requires special treatment. When the elevator is neutral and opens its doors at floor j, it has not yet committed itself to a direction. Therefore all waiting users whose desired direction can be served next should be allowed to enter. This is accomplished by retaining the existing action of step U5: the first entering passenger who selects a destination floor changes STATE to GOINGUP or GOINGDOWN according as OUT>j or OUT<j. Once this direction has been established, step E4 continues boarding passengers only from the corresponding queue. Thus, if the first passenger entering a neutral elevator chooses an upper floor, passengers waiting to go down are not admitted; if the first passenger chooses a lower floor, passengers waiting to go up are not admitted.

With these changes, users 7 and 9 in the example would remain in QUEUEUP[1] when the elevator arrives at floor 1 in state GOINGDOWN. User 8, who wishes to go down, would enter from QUEUEDOWN[1]; users 7 and 9 would wait until the elevator later returns in state GOINGUP.

No other changes to the elevator control logic are necessary. The call variables already distinguish upward and downward requests, and the stopping decisions of the elevator are already based on those variables. The only required modification is that boarding privileges in step E4 depend on the elevator's current state, together with the replacement of QUEUE[j] by separate queues for the two directions.

$$ \boxed{\text{Replace } QUEUE[j] \text{ by } QUEUEUP[j] \text{ and } QUEUEDOWN[j],\ \text{and allow boarding only from the queue matching } STATE.} $$