Ed Yourdon - Just Enough Structured Analysis

G.1 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 Appendices F and G, you will see why.

G.2 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.