TAOCP 2.2.5 Exercise 8

Step `E8` is the action that occurs after the elevator has moved one floor in its current direction.

taocpmathematicsalgorithmsvolume-1medium

Section 2.2.5: Doubly Linked Lists

Exercise 8. [21] Write the code for step E8, lines 277-292, which has been omitted from the program in the text.

Verified: no
Solve time: 30s

Solution

Step E8 is the action that occurs after the elevator has moved one floor in its current direction. At this point the elevator must

  1. update FLOOR;
  2. determine whether a stop is required at the new floor;
  3. if a stop is required, open the doors;
  4. otherwise continue moving in the same direction.

The stopping criterion is determined entirely by the pending requests represented by the CALL variables. When the elevator is in state GOINGUP, it must stop if

  • CALLUP[FLOOR] = 1, since passengers on this floor wish to go up;
  • CALLCAR[FLOOR] = 1, since a passenger wishes to leave here;
  • there are no requests above the present floor, and CALLDOWN[FLOOR] = 1.

The last condition is necessary because a downward request at the current floor should be served when the elevator reaches the highest requested floor and begins its return. Symmetrically, when the elevator is in state GOINGDOWN, it must stop if

  • CALLDOWN[FLOOR] = 1;
  • CALLCAR[FLOOR] = 1;
  • there are no requests below the present floor, and CALLUP[FLOOR] = 1.

The omitted MIX code therefore performs the following logical test:

$$ \begin{aligned} \text{STOP} \equiv {} & \text{CALLCAR[FLOOR]} \ &\lor (\text{STATE}=\text{GOINGUP}\land \text{CALLUP[FLOOR]}) \ &\lor (\text{STATE}=\text{GOINGDOWN}\land \text{CALLDOWN[FLOOR]}) \ &\lor (\text{STATE}=\text{GOINGUP}\land \neg\text{ABOVE}\land \text{CALLDOWN[FLOOR]}) \ &\lor (\text{STATE}=\text{GOINGDOWN}\land \neg\text{BELOW}\land \text{CALLUP[FLOOR]}). \end{aligned} $$

If STOP is true, control passes to the door-opening sequence (E3); otherwise another floor-to-floor movement is scheduled.

A compact MIXAL implementation is:

* E8. ARRIVE AT NEW FLOOR

E8       LDA     FLOOR
          CMPA    =GOINGUP=
          JE      E8UP

* GOINGDOWN

          LDX     FLOOR
          LDA     CALLCAR, X
          JANZ    E3

          LDA     CALLDOWN, X
          JANZ    E3

          LDA     BELOW
          JANZ    E8GO

          LDA     CALLUP, X
          JANZ    E3
          JMP     E8GO

* GOINGUP

E8UP     LDX     FLOOR
          LDA     CALLCAR, X
          JANZ    E3

          LDA     CALLUP, X
          JANZ    E3

          LDA     ABOVE
          JANZ    E8GO

          LDA     CALLDOWN, X
          JANZ    E3

* CONTINUE MOVING

E8GO     JMP     E7

This code embodies exactly the stopping rules described by the elevator algorithm. If a request at the current floor requires service, control transfers to E3; otherwise the elevator continues its motion by returning to the movement cycle. The omitted step E8 is therefore the decision procedure that determines whether the newly reached floor is a stopping floor or merely an intermediate floor.

$$ \boxed{\text{E8 tests the stop conditions at the newly reached floor and transfers either to }E3\text{ or back to the motion cycle.}} $$