TAOCP 2.2.5 Exercise 9

Exercise 9. [23] Write the code for the DECISION subroutine, which has been omitted from the program in the text.

Verified: no
Solve time: 39s

Solution

The DECISION subroutine is called whenever the elevator is in a dormant condition and a new request may require a change of state. Its purpose is to determine whether the elevator should remain idle, begin moving, or reopen its doors. The text specifies two dormant situations:

D2 = 0, meaning the elevator has remained motionless for at least 30 seconds and is therefore in NEUTRAL state with doors open or about to become dormant.
The elevator is in position E1, namely floor 2 with doors closed.

The behavior described in the section determines the logic completely.

If the elevator is already at floor 2 in state NEUTRAL and the doors are closed (E1), a request for floor 2 should cause the doors to open, since the elevator is already there. Any request for another floor should send the elevator toward that floor. Similarly, when the elevator has been sitting idle elsewhere (D2 = 0), the elevator should reopen its doors if the request concerns the present floor; otherwise it should move toward the requested floor, first returning to floor 2 if no command exists in the current location.

The elevator changes from NEUTRAL to GOINGUP or GOINGDOWN according to the nearest outstanding request relative to FLOOR. The available requests are represented by the ten hall calls CALLUP[j], CALLDOWN[j], and the five car calls CALLCAR[j].

A compact form of the required subroutine is therefore:

DECISION LD1 FLOOR          current floor in index register

D1       LDA CALLUP,1       any request on present floor?
         ORA CALLDOWN,1
         ORA CALLCAR,1
         JANZ E3            yes, open doors

         ENT1 0             search above
D2       LDA CALLUP,1
         ORA CALLDOWN,1
         ORA CALLCAR,1
         JANZ D4
         INCA 1
         CMPA =5=
         JNE D2

         ENT1 FLOOR         search below
D3       DECA 1
         JL D5
         LDA CALLUP,1
         ORA CALLDOWN,1
         ORA CALLCAR,1
         JANZ D6
         JMP D3

D4       CMPA FLOOR         request above?
         JAN D7
         JE D5
         STA STATE=GOINGUP=
         JMP E6

D6       STA STATE=GOINGDOWN=
         JMP E6

D7       STA STATE=GOINGUP=
         JMP E6

D5       JMP E1             no requests, remain dormant

The logical structure is as follows. First, if any request exists at the current floor, the elevator should proceed immediately to E3, opening the doors. If no request exists on the current floor, the subroutine searches floors above FLOOR; if a request is found, the elevator enters state GOINGUP and proceeds to E6, the door-closing action. If nothing exists above, the subroutine searches below; if a request is found, the elevator enters state GOINGDOWN and proceeds to E6. When no request exists anywhere, the elevator remains dormant, hence control returns to E1.

This algorithm agrees with the informal specification: a neutral elevator remains idle until a command appears, opens its doors if already at the requested floor, and otherwise departs in the appropriate direction toward pending service.

$$ \boxed{\text{DECISION opens doors for local requests, otherwise sets direction and starts }E6} $$