Appendix G

The Elevator System Case Study

INTRODUCTION

This appendix shows the essential model for an elevator scheduler and controller. Its primary purpose is to illustrate the use of structured analysis models for real-time systems; you will see examples of control flows, control processes, and state-transition diagrams that would typically not be used in a business-oriented system.

In the next section, a narrative description of the problem is given. Following that are the various diagrams that make up the essential model, as well as the data dictionary and process specifications. Note that most of the process specifications use the precondition/postcondition approach discussed in Chapter 11.

The elevator problem was used in a workshop sponsored by the Washington, D.C., chapter of the ACM in 1986. The models provided here were originally developed by Dennis Stipe, formerly of YOURDON inc. The dataflow diagrams and data dictionary were produced on a Macintosh II computer with MacBubbles from StarSys, Inc.; the state-transition diagrams were produced with MacDraw.

It is important that you see how different the diagrams in this chapter are from the diagrams in Appendix F, which were produced by Design from Meta Software. MacBubbles is a CASE product that is specifically tailored for drawing dataflow diagrams (with balancing between parent and child diagrams, etc.). Design is a more general-purpose object-oriented drawing program, which can be used to draw flowcharts, data flow diagrams, or virtually any other software diagram. From an aesthetic viewpoint, the diagrams produced by the two programs are very different; I think that the editors who produced this book would have preferred a reliable human artist to both packages. As mentioned in Chapter 9, the style and format of dataflow diagrams can be a sensitive issue with many users; when you compare Appendix F and Appendix G, you will see why.

A NARRATIVE DESCRIPTION

The general requirement is to design and implement a program to schedule and control four elevators in a building with 40 floors. The elevators will be used to carry people from one floor to another in the conventional way.

• Efficiency: The program should schedule the elevators efficiently and reasonably. For example, if someone summons an elevator by pushing the down button on the fourth floor, the next elevator that reaches the fourth floor traveling down should stop at the fourth floor to accept the passenger(s). On the other hand, if an elevator has no passengers (no outstanding destination requests), it should park at the last floor it visited until it is needed again. An elevator should not reverse its direction of travel until its passengers who want to travel in its current direction have reached their destinations. (As we will see below, the program cannot really have information about an elevator’s actual passengers; it only knows about destination button presses for a given elevator.

For example, if some mischievous or sociopathic passenger boards the elevator at the first floor and then presses the destination buttons for the fourth, fifth, and twentieth floor, the program will cause the elevator to travel to and stop at the fourth, fifth, and twentieth floors. The computer and its program have no information about actual passenger boardings and exits.) An elevator that is filled to capacity should not respond to a new summon request. (There is an overweight sensor for each elevator. The computer and its program can interrogate these sensors.)

• Destination button: The interior of each elevator is furnished with a panel containing an array of 40 buttons, one button for each floor, marked with the floor numbers (1 to 40). These destination buttons can be illuminated by signals sent from the computer to the panel. When a passenger presses a destination button not already lit, the circuitry behind the panel sends an interrupt to the computer (there is a separate interrupt for each elevator). When the computer receives one of these (vectored) interrupts, its program can read the appropriate memory mapped eight-bit input registers (there is one for each interrupt, hence one for each elevator) that contains the floor number corresponding to the destination button that caused the interrupt. Of course, the circuitry behind the panel writes the floor number into the appropriate memory-mapped input register when it causes the vectored interrupt. (Since there are 40 floors in this application, only the first six bits of each input register will be used by the implementation; but the hardware would support a building with up to 256 floors.)
• Destination button lights: As mentioned earlier, the destination buttons can be illuminated (by bulbs behind the panels). When the interrupt service routine in the program receives a destination button interrupt, it should send a signal to the appropriate panel to illuminate the appropriate button. This signal is sent by the program’s loading the number of the button into the appropriate memory-mapped output register (there is one such register for each elevator). The illumination of a button notifies the passenger(s) that the system has taken note of his or her request and also prevents further interrupts caused by additional (impatient?) pressing of the button. When the controller stops an elevator at a floor, it should send a signal to its destination button panel to turn off the destination button for that floor.
• Floor sensors: There is a floor sensor switch for each floor for each elevator shaft. When an elevator is within eight inches of a floor, a wheel on the elevator closes the switch for that floor and sends an interrupt to the computer (there is a separate interrupt for the set of switches in each elevator shaft). When the computer receives one of these (vectored) interrupts, its program can read the appropriate memory mapped eight-bit input register (there is one for each interrupt, hence one for each elevator) that contains the floor number corresponding to the floor sensor switch that caused the interrupt.
• Arrival lights: The interior of each elevator is furnished with a panel containing one illuminable indicator for each floor number. This panel is located just above the doors. The purpose of this panel is to tell the passengers in the elevator the number of the floor at which the elevator is arriving (and at which it may be stopping). The program should illuminate the indicator for a floor when it arrives at the floor and extinguish the indicator for a floor when it leaves a floor or arrives at a different floor. This signal is sent by the program’s loading the number of the floor indicator into the appropriate memory-mapped output register (there is one register for each elevator).
• Summons buttons: Each floor of the building is furnished with a panel containing summon button(s). Each floor except the ground floor (floor 1) and the top floor (floor 40) is furnished with a panel containing two summon buttons, one marked UP and one marked DOWN. The ground floor summon panel has only an UP button. The top floor summon panel has only a DOWN button. Thus, there are 78 summon buttons altogether, 39 UP buttons and 39 DOWN buttons. Would-be passengers press these buttons in order to summon an elevator. (Of course, the would-be passenger cannot summon a particular elevator. The scheduler decides which elevator should respond to a summon request.) These summon buttons can be illuminated by signals sent from the computer to the panel. When a passenger presses a summon button not already lit, the circuitry behind the panel sends a vectored interrupt to the computer (there is one interrupt for UP buttons and another for DOWN buttons). When the computer receives one of these two (vectored) interrupts, its program can read the appropriate memory mapped eight-bit input register that contains the floor number corresponding to the summon button that caused the interrupt. Of course, the circuitry behind the panel writes the floor number into the appropriate memory-mapped input register when it causes the vectored interrupt.
• Summon button lights: The summon buttons can be illuminated (by bulbs behind the panels). When the summon button interrupt service routine in the program receives an UP or DOWN button vectored interrupt, it should send a signal to the appropriate panel to illuminate the appropriate button. This signal is sent by the program’s loading the number of the button in the appropriate memory-mapped output register, one for the UP buttons and one for the DOWN buttons. The illumination of a button notifies the passenger(s) that the system has taken note of his or her request and also prevents further interrupts caused by additional pressing of the button. When the controller stops an elevator at a floor, it should send a signal to the floor’s summon button panel to turn off the appropriate (UP or DOWN) button for that floor.
• Elevator motor controls (Up, Down, Stop): There is a memory-mapped control word for each elevator motor. Bit 0 of this word commands the elevator to go up, bit 1 commands the elevator to do down, and bit 2 commands the elevator to stop at the floor whose sensor switch is closed. The elevator mechanism will not obey any inappropriate or unsafe command. If no floor sensor switch is closed when the computer issues a stop signal, the elevator mechanism ignores the stop signal until a floor sensor switch is closed. The computer program does not have to worry about controlling an elevator’s doors or stopping an elevator exactly at a level (home) position at a floor. The elevator manufacturer uses conventional switches, relays, circuits, and safety interlocks for these purposes so that the manufacturer can certify the safety of the elevators without regard for the computer controller. For example, if the computer issues a stop command for an elevator when it is within eight inches of a floor (so that its floor sensor switch is closed), the conventional, approved mechanism stops and levels the elevator at that floor, opens and holds its doors open appropriately, and then closes its door. If the computer issues an up or down command during this period (while the door is open, for example), the manufacturer’s mechanism ignores the command until its conditions for movement are met. (Therefore, it is safe for the computer to issue and up or down command while an elevator’s door is still open.) One condition for an elevator’s movement is that its stop button not be depressed. Each elevator’s destination button panel contains a stop button. This button does not go to the computer. Its sole purpose is to hold an elevator at a floor with its door open when the elevator is currently stopped at a floor. A red emergency stop switch stops and holds the elevator at the very next floor it reaches irrespective of computer scheduling. The red switch may also turn on an audible alarm. The red switch is not connected to the computer.
• Target machine: The elevator scheduler and controller may be implemented for any contemporary microcomputer capable of handling this application.

The Environmental Model

The Statement of Purpose

The general requirement is to design and implement a program to schedule and control four elevators in a building with 40 floors. The elevators will be used to carry people from one floor to another in the conventional way.

The Context Diagram

Elevator Essential Model

Expanded Context Diagram

The Event List

1. Passenger issues up summons request.
2. Passenger issues down summons request.
3. Elevator reaches summoned floor.
4. Elevator not available for summons request.
5. Elevator becomes available for summons request.
6. Passenger issues destination request.
7. Elevator reaches requested destination.
8. Elevator arrives at floor.
9. Elevator departs floor.
10. Elevator fails to move (goes out of service).
11. Elevator returns to normal service.
12. Elevator becomes overloaded.
13. Elevator load becomes normal.

The Behavioral Model

Data Flow Diagram

Figure 0. Schedule and Control Elevator

Figure 0: Schedule and Control Elevator

Figure 1. Store and Display Request

Figure 1: Store and Display Request

Figure 1.1: Manage Summons Request.

Figure 1.1.1: Control Summons Request.

Figure 1.2: Manage Destination Request.

Figure 1.2.1: Control Destination Request.

Figure 2. Control Elevator

Figure 2: Control Elevator

Figure 2.1: Manage Elevator Destination.

Figure 2.1.1: Control Destination.

Figure 2.2: Manage Floor Arrival.

Figure 2.2.1: Move Elevator to Floor.

Figure 3. Schedule Elevator

Figure 3: Schedule Elevator

Figure 3.1: Manage Summons Schedule.

Figure 3.1.2: Control Summons Scheduling.

Figure 3.2: Manage Destination Schedule.

Figure 3.2.1: Control Destination Schedule.

Data Dictionary

arrival indication = values: 1-40
NOTES: indication of floor at which elevator has arrived

at floor
NOTES: signal that elevator reached a floor

current floor = values: 1-40
NOTES: floor number where an elevator is currently located

current-floor = values: 1-40
NOTES: floor number where an elevator floor is currently located

desired floor reached
NOTES: signal

destination direction = [destination-up|destination-down]

destination-down =
NOTES: signal that required direction is down

destination-floor = values: 1-40
NOTES: floor numbers where an elevator is scheduled to stop

destination-indication = values: 1-40
NOTES: indication of floor numbers where an elevator is scheduled to stop

destination-pending = values: [on | off]
NOTES: indication that elevator has destinations subsequent to current floor

destination-request = @elevator-number+{floor-number}

destination-request-entered
NOTES: signal that passenger has entered request

destination-request-received
NOTES: signal that request is ready for scheduling

destination-requests = {destination-request}

destination-schedule = @elevator-number+{destination-floor}+request -source+destination-pending

destination-schedules = {destination-schedule}

destinations-pending = [summons-pending | destination-pending | summons-pending + destination-pending]
NOTES: signal that a destination schedule exists

destination-up
NOTES: signal that required direction is up

down-direction
NOTES: *** Generated Entry ***

elevator-control-signal = elevator-up-control+elevator-down-control+elevator-stop-control

elevator-down-control
NOTES: signal to hardware

elevator-floor = values: 1-40

elevator-not-available
NOTES: signal that an elevator is not available to honor a summons request

elevator-number = values: 1-4

elevator-selected
NOTES: signal that an elevator has been scheduled for a summons request

elevator-status = @elevator-number+elevator-state+current-floor

elevator-state = [parked|moving-up|moving-down|stopped|out-of-service]

elevator-statuses = {elevator-status}

elevator-stop-control
NOTES: signal to hardware

elevator-up-control
NOTES: signal to hardware

floor-number = values: 1-40
NOTES: *** Generated Entry ***

moving-down
NOTES: *** Generated Entry ***

moving-up
NOTES: *** Generated Entry ***

off
NOTES: *** Generated Entry ***

on
NOTES: *** Generated Entry ***

out-of-service
NOTES: signal that elevator has failed to respond to movement command

overload
NOTES: signal from hardware

parked
NOTES: signal

request-received = summons-request-received + destination-request-received

request-source = [summons | destination-floor | summons + destination-floor]

requests = summons-requests + destination-requests

reschedule-elevator
NOTES: signal to initiate rescheduling summons assigned to failed elevator

summons-pending = values: [on | off]

summons-request = @elevator-floor + [up-direction | down-direction | up-direction + down-direction] + elevator-number

stopped
NOTES: *** Generated Entry ***

summons
NOTES: *** Generated Entry ***

summons-indication = values: 1-40
NOTES: indication of floor numbers where an elevator is scheduled to stop

summons-request = @elevator-floor + [up-direction | down-direction | up-direction + down-direction] + elevator-number

summons-request-issued
NOTES: signal

summons-request-received
NOTES: signal

summons-requests = {summons-request}

up-direction
NOTES: *** Generated Entry ***

values
NOTES: *** Generated Entry ***

Process Specifications

1.1.2 STORE SUMMONS REQUEST

Precondition

input-summons-request occurs

Postcondition

input-summons-request is stored

summons-request-entered is produced

1.1.3 CLEAR COMPLETED SUMMONS

Precondition

There is an elevator-number in elevator-statuses that matches elevator-number-assigned in summons-request

and

There is a corresponding current-floor in elevator-statuses that matches floor-number in summons-requests

Postcondition

Corresponding entry in summons-request is null

1.1.4 DISPLAY SUMMONS REQUEST

Precondition

None

Postcondition

summons-requests are displayed

1.2.3 CLEAR COMPLETED DESTINATIONS

Preconditon

There is an elevator-number in elevator-statuses that matches elevator-number in destination-requests

and

There is a corresponding current-floor in elevator-statuses that matches floor-number in destination-requests

Postcondition

Corresponding entry in destination-requests is null

1.2.4 DISPLAY DESTINATION REQUEST

Precondition

None

Postcondition

destination-requests are displayed

2.1.2 DETERMINE FINAL DESTINATION

Precondition

There is an elevator-number in elevator-statuses that matches elevator-number in destination-schedules

and

There is a corresponding current-floor in elevator-statuses that matches destination-floor in destination-schedules

and

corresponding destination-pending = off in destination-schedules

Postcondition

final-destination-reached is produced

2.1.3 DETERMINE DIRECTION REQUIRED

Local term match is a matching elevator-number in destination-schedules and elevator-number in elevator-status Precondition 1

match exists

and

There exists in destination-schedules a destination-floor > current-floor in elevator-status

Postcondition 1

destination-up is produced

Precondition 2

match exists

and

There exists in destination-schedules a destination-floor < current-floor in elevator-status

Postcondition 2

destination-down is produced

2.2.2 MONITOR FLOOR ARRIVAL

Precondition 1

floor occurs

Postcondition 1

arrival-indication is cleared for previous floor

and

arrival-indication is produced for corresponding floor

and

at-floor is produced

and

current-floor is updated in elevator-statuses

2.2.3 MONITOR ELEVATOR MOVEMENT

current-floor is read from elevator-statuses Precondition

10 seconds elapse and current-floor is unchanged

Postcondition

move-timeout occurs

2.2.4 STORE ELEVATOR STATUS

Precondition

input signal is received

Postcondition

elevator-state is updated in elevator-status

2.2.5 DETERMINE DESIRED FLOOR

Precondition

There is an elevator-number in elevator-statuses that matches elevator-number in destination-statuses

and

There is a corresponding current-floor in elevator-statuses that matches destination-floor in destination-schedules

Postcondition

desired-floor-reached is produced

3.1.1 SCHEDULE SUMMONS

BEGIN

with summons-request, elevator-status, and overload

DO WHILE elevator-selected has not been signaled

Find closest elevator

IF elevator is moving in correction direction

or elevator is parked

IF elevator is not overloaded

enter summons-request by elevator-number in destination-schedule

set request-source to summons or summons + destination

ENDIF

IF destination-pending = off

set destination-pending = on

ENDIF

signal elevator-selected

ELSE

Find next closest elevator

END DO

IF no elevator found

Signal elevator not available

ENDIF

END

3.1.3 CLEAR SUMMONED DESTINATIONS

Precondition

There is an elevator-number in elevator-statuses that matches elevator-number in destination-schedules

and

corresponding elevator-state = out-of-service in

elevator-statuses

and

corresponding request-source = summons

in destination-schedules

Postcondition

Corresponding entries of destination-floor are null

3.2.2 SCHEDULE-DESTINATION-REQUEST

Precondition

None

Postcondition

destination-schedules is updated by destination-requests matching elevator-number

Set request-source = destination or summons + destination

IF destination-pending = off THEN

Set destination-pending = off

ENDIF

3.2.3 UPDATE DESTINATION SCHEDULE

Precondition 1

There is an elevator-number in elevator-statuses that matches elevator-number in destination-schedules

and

There is a corresponding current-floor in elevator-statuses that matches destination-floor in destination-schedule

Postcondition 1

Corresponding destination-floor entry is null

Precondition 2

same condition as Precondition 1

and

no other corresponding destination-floor entries are present

Postcondition 2

corresponding destination-floor entry is null

and

corresponding destination-pending is set to off