Designing large real-time systems with Ada. (2024)

DESIGNING LARGE REAL-TIME SYSTEMS WITH ADA Traditional real-timesystems are designed with the assumption that the primitives requiredfor concurrent operations are provided by a real-time executive (RTE),and that these primitives are utilized whenever executive servicerequests (ESRs) are made. The Ada tasking model [16] incorporates allthe primitives required for a concurrent system; therefore an RTE is notassociated with the Ada programming language. The Ada real-timeservices required are supplied as run-time support, and Ada softwaremodules do not make ESRs to an RTE.

This article first describes traditional real-time design methodsand the aspects of Ada that are different from a traditional higherorder language (HOL) and an associated RTE. It continues with adescription of several suggested methods for Ada design, and concludeswith a discussion of the shortcomings of the suggested methods and aproposal for a consistent method for designing large real-time systemsin Ada. A sample design of a real-time system is included to illustratethe proposed methodology.

TRADITIONAL REAL-TIME DESIGN METHODS

Real-time systems can be characterized as software-controlledsystems that must perform all of their processing functions withinspecified time constraints. Examples of such systems include airlinereservations, air traffic control, and process automation. Real-timedesigns typically include a set of concurrent processes that operateasynchronously to accommodate the different speed requirements ofvarious hardware devices. The processes usually have to communicate,and synchronization points are included in the designs to provide formessage passing and protection of shared data. Design methods used tocreate these systems include the Design Approach for Real-Time Systems(DARTS), as discussed in [7]; the use of layered virtual machines [1, 6,8]; and the use of finite-state machines [1, 3]. These methods aredescribed briefly below.

Design Approach for Real-Time Systems (DARTS)

The DARTS methodology is based on traditional structured design andstarts with data-flow diagrams (DFDs) for describing the functionalityof the system. This functionality is used to decompose the system intoa set of concurrent processes. A set of criteria for how the system canbe decomposed would consist of (1) dependency on input/output (I/O), (2)time-critical functions, (3) computational requirements, (4) functionalcohesion, (5) temporal cohesion, and (6) periodic execution.

The set of concurrent processes is depicted in a process structurechart that contains all the interfaces between the processes. Theseinterfaces include loose and tight coupling, signaling, message passing,and access to shared data. The designer must determine the appropriateimplementation for these interfaces according to the primitives that areavailable for the particular HOL and associated RTE. If a process isfound to be too large to be contained in a single module, that processis further decomposed into several modules (procedures and functions)using traditional structure charts.

Layered Virtual Machines

Various design methods involving layered (hierarchical) virtualmachines have been suggested. The use of layered virtual machines is away of creating a set of layered (hierarchical) abstractions thatsimplify the design process by deferring implementation details, and byusing the principle of information hiding [14]. It has been suggested[1] that layered abstractions will promote a high degree ofmaintainability with the possibility of replacing a complete hierarchywith a new virtual machine. This may not be so easy to accomplish in adeeply nested top-down tree-structured design.

A set of hierarchical levels was used in the construction of theTHE Multiprogramming System [6]. Processor allocation, interrupthandling, and priority rules for concurrent processes were reserved forthe lowest hierarchical level, whereas synchronization actions betweenprocesses were included in the next to the lowest level. Processidentification and creation, and buffering of I/O streams as well aserror detection were included in the next two higher levels,respectively. The next highest level was reserved for independent userprograms, and the highest level dealt with operator actions.

A set of layered virtual machines also constituted the real-timesystem solution in [1]: (1) the hardware, (2) a real-time machine (e.g.,for process scheduling), and (3) a process machine (e.g., for processcommunication and synchronization). The process machine included aprogramming language (high order or assembly) and support for datastructuring. Application processes were created using data structuringtechniques [10].

Finite-State Machines

A finite-state machine (FSM) is commonly used to describe all thepossible states of a process and its associated operations that cantransition the process from one state to another [1]. The transition toa future state depends on both the input and the current state. An FSMcan be represented graphically in a state transition diagram, as shownin Figure 1. This figure represents a simplified view of the possiblestates of a process and the operations that will cause a transition fromone state to another:

(1) A running process can transition to a blocked state with ablock operation or to a ready state with a timer run-out operation.

(2) A blocked state can transition to a ready state with a wake-upoperation.

(3) A ready state can transition to a running state with a dispatchoperation.

The FSM can be implemented with the traditional approach of usingstate and operator tables. In Ada the FSM can be embedded in a taskusing "selective wait" statements [3].

WHY ADA IS DIFFERENT

Ada requires a new design method for real-time systems since itdiffers from conventional language/executive combinations in twoimportant ways: (1) concurrency and process communication are inherentin the language and do not require a separate RTE; and (2) the nature ofthe tasking model is different from the current popular approaches usedfor task scheduling, communication, and synchronization.

Concurrency Inherent in the Language

Figure 2 illustrates the difference between the conventionalapproach and the Ada approach, involving features to support concurrencyintrinsic to the language. Ada provides tasks as its mechanism forimplementing processes that execute concurrently. If a process hasadditional internal concurrent activity, it may be implemented asseveral tasks. Ada has no explicit task activation, suspend/resume,message passing (e.g., via a "mailbox"), or synchronizationprimitives such as semaphores. Task creation, cooperation, andcompletion are intimately related to the structure of the language andresulting programs, and hence to their design. An Ada-oriented designapproach can take simultaneous advantage of both tasking features andother program structuring characteristics in order to create effectivedesigns.

Nature of the Tasking Model

The Ada tasking model is different from other models currentlybeing used to build real-time systems. It is based on the rendezvousconcept [4] to provide a procedure-like interface between two tasks.The rendezvous approach has never previously been employed in a widelyused programming language or executive to implement a major real-timesystem. The rendezvous has several characteristics that influencesystem design: (1) It is a single mechanism for synchronization andcommunication; (2) it provides for simultaneous two-way transmission ofinformation; (3) it allows instructions to be executed on behalf of twocooperating tasks; and (4) it is an asymmetric process, providingdifferent capabilities for a "calling" task (which issues anentry call) than for a "called" task (which accepts an entrycall). The aspect of asymmetry is of particular importance for thedesign of task interaction. The rendezvous is asymmetric in three ways:

(1) The calling task must know the name of the called task (and itsentries), but not vice versa.

(2) A call can occur in a subprogram (either subordinate to a taskor in a separate package) or in the initialization part of a packagebody, whereas the acceptance of a call must occur only in the sequenceof statements of a task body.

(3) A calling task can call only one other task and can be on onlya single entry queue of tasks waiting for a call to be accepted. Acalled task, on the other hand, can wait for any of many different typesof calls and can have many queues of callers (one queue for each entry)waiting for its attention.

The first kind of asymmetry allows for the programming ofgeneral-purpose library or service tasks. The second kind has an effecton modularization. The third kind is fundamental to the Ada taskingmodel and is concerned with determining which task will have greatercontrol over the rendezvous.

The called task, using the select statement with guards, has morecontrol over its fate than does a calling task. The called task,however, has a degree of nondeterminism since it must be prepared torespond to a call to any of the accepts in the select statement. Thisdistinction has led Pyle [15] to differentiate between active (calling)tasks and passive (called) tasks. He states [15, p. 96] that "theprogrammer using tasks will mainly write active tasks, taking advantageof previously written passive tasks." This may not be completelytrue since many tasks may have both calling and called aspects, but itis certainly true that programmers must learn "how to designprograms the Ada way" [18, p. 338].

ADA DESIGN MODELS

Various design models have been suggested for Ada real-timesystems. We will describe three such models and assess their usefulnessas general design methodologies for large real-time systems.

Object-Oriented design

The object-oriented design method [2] utilizes data abstractions tocreate a set of software objects and their associated operations. Themethod is formalized as follows:

(1) Define the problem by analyzing the system requirements andusing DFDs, or another suitable method, to define the problem at a highlevel.

(2) Develop an informal strategy by describing the requirementswith English language descriptions that take account of the basiccontrol structures (sequential, conditional, and iterative). If therequirements document is not already written in this format, another(informal) description has to be created to accommodate the next step inthis methodology.

(3) Formalize the strategy by underlining nouns, adjectives, verbs,and adverbs in the informal strategy description. The nouns andadjectives become objects with certain attributes, and the correspondingverbs and adverbs become the operations (sub-programs and/or tasks to beperformed on these objects). The final step is to define the interfacesbetween the objects and their operations, and to define local objectsand their associated operations.

(4) Implement the formal strategy by implementing objects as Adapackages, types, or identifiers. Operations are implemented asprocedures, tasks, and functions.

The major criticism of object-oriented design is that it is onlyuseful for relatively small projects where the informal strategy isalready known. The approach of underlining verb and noun phrases inlarge requirements documents is simply not appropriate, and is adifficult and awkward way to adequately determine objects and theirassociated operations. This design method also fails to address thedetermination of concurrent processes for a real-time system.

Process Abstraction Method

The Process Abstraction Method (PAM) [5] uses data and processabstractions to focus on synchronization and communication between tasksas a system is decomposed into a set of concurrent processes. A processis here defined as a program unit capable of running in parallel withother program units. The processes are either single-thread (primitive)or multithread (nonprimitive). Nonprimitive processes are furtherdecomposed into son processes. In Ada terminology a process is either apackage or a task, where a package may contain nested packages. Acentral concept in PAM is that a process transforms data, while dataflows connect processes. A process is a caller if it takes or providesdata by a call to a procedure or task entry. A process is a server ifit only accepts a call. An abbreviated outline of PAM consists of thefollowing steps:

(1) Transform the requirements into a hierarchical process graph(HPG), an example of which is given in Figure 3. Two important featuresof the HPG are that it shows data flows between processes, and that itshows the hierarchy of processes: Buffer character and interpret inputare components of the higher level process input system.

(2) Transform the first-level process graph into an Ada master(main) procedure, and transform each lower level nonprimitive processinto an Ada package body:

(a) Determine suitable library units:

* Package the global data types and constants.

* Package the hardware-dependent information.

* Package generic program units.

(b) Determine interfaces for the communicating processes:

* Make caller/server (also referred to as caller/called) decisionsfor each data flow.

* Determine parameter modes and types for interprocess calls.

* Specify exceptions raised and handled.

(c) Specify nonprimitive and promitive processes:

* Transform each nonprimitive process into a package specification.

* Transform each primitive process into a task specification.

* Document in each specification (with appropriate comments) allthe interfaces of the particular process with the external entities(devices) and other processes in the process graph.

* Declare a body stub for each primitive and nonprimitive process.

(d) Transform package body stubs into complete bodies. Repeatsteps 2b and c for each remaining package body.

(e) Transform each task body stub into its internal logic (properbody).

PAM offers several advantages over object-oriented design. First,it is methodological and should thus be reasonably easy to teach tonovice Ada designers. Second, it lends itself to the use of ahierarchical decomposition similar to the procedures used for sequentialdecomposition (DFD and structure charts). Third, it provides anisomorphism from the process graph to the package specifications.Fourth, it provides an extendable set of heuristics and rules that canbe utilized in the teaching process.

The primary objection to PAM is that it tends to create a highlynested set of Ada packages and tasks as a result of several levels ofdecomposition. The scope of identifiers is extended to all of thenested packages and violates the "need-to-know" principle forthe nested units. There is also more compilation required when changesare made to modules in a nested design.

Edges-IN Approach

This is an informal method for Ada design based on the data flowsutilized in structured design [3]. The approach consists of thefollowing steps:

(1) A starting point for the design is provided by identifying themajor functions of the system at the edges. The internal functionalityis collected in a single central function.

(2) A preliminary DFD is created (for doodling purposes) based onthe initial identification of the functions along the system edges.

(3) Additional functions are added to provide the requiredconnections between the edge functions. These functions will usuallyinclude control and exception handling.

(4) Software modules are created by assigning suitable functionsidentified in the DFD to Ada packages, subprograms, and tasks.

(5) Structure graphs (a special Ada-oriented graphics method usedto describe concurrent Ada designs) are drawn to shown th initial systemarchitecture in terms of Ada packages, subprograms, and tasks. Datatypes and ata structures have not yet been defined.

(6) Design decisions for the task interfaces are made regardingcaller/called tasks (direction of entry calls in a rendezvous).Intermediary tasks are introduced to provide appropriate coupling forinterprocess communication. The structure graph is redrawn to show theinterfaces between the Ada tasks, subprograms, and packages.

(7) The details of the module interfaces are completed includingdata types and structures, and the algorithms are provided for the taskand subprogram bodies.

(8) Appropriate design reviews are held at the completion of eachof the major steps listed above.

This approach (as outlined in [3]) is primarily useful for systemswhere the internal functionality can be transformed to a single-threadmodule with no further decomposition required. The Ada designmethodology that follows extends this approach to include adecomposition of the internal functionality into other concurrentprocesses. Steps 1-3 are first performed on the edge functions and thenrepeated for the internal functions. Steps 4-8 are perpormed on thesystem as a whole after the internal functionality has been decomposed.

The primary problem with this method is that it does not provide aspecific procedure for the decomposition of the internal functionality("the middle part"). This decomposition is left as anartistic exercise rather than an engineering discipline as provide, forexample, by PAM. A successful methodology for Ada design must includeprescriptions for the packaging of software modules into Ada tasks,packages, and subprograms. Another problem is that abstract data typesare not created in parallel with the determination of processes andtheir interfaces.

ADA DESIGN METHODOLOGY

The proposed methodology consists of a combination of the edges-inapproach and a prescription for the creation of the middle part usingsome specific guidelines. For example, one of the most simpleguidelines is that each interrupting device is to be handled by its ownprocess. The processes frequently encapsulate an object in the sense ofobject-oriented design, or hide design decisions in the sense ofinformation hiding. That is, the processes represent abstractions ofthe concurrency requirements of the system.

Assuming that the designer has a keen understanding of therequirements of the real-time system to be implemented, the followingsteps must be accomplished to develop top-level system design:

(1) Establish interfaces with external devices.

(2) Decompose the middle part into a set of concurrent processes.

(3) Provide communication for the concurrent processes.

(4) Establish the most suitable architecture for the system(including abstract data types).

Establishing the interfaces with external devices is primarily amatter of creating device drivers and interrupt handlers. Decompositionhas to do with the identification of the system's concurrentprocesses or tasks, communication with the passing of data andsynchronization between tasks, and architecture with the manner in whichthe tasks and data structures are encapsulated in Ada packages.

External Devices

A general guideline for the creation of processes that interfacewith the external devices is that each device should be allocated to aseparate process. This means that a separate device or interrupthandler is designed for each device. Each handler will consist of atleast one Ada task, and intermediary tasks can be added as interfaces tothe processes in the middle part. The tasks that interface directlywith the external devices should perform a single function and should bedesigned to operate as efficiently as possible. Buffering tasks mayhave to be added to allow the device or interrupt handlers to mostefficiently service the devices while operating asynchronously withapplication-oriented tasks. This portion of the design process isaccomplished by following the steps outlined above for the edges-inmethod.

Decomposition

With the exception of a class of real-time system using a cyclicexecutive [11], real-time systems are oriented toward asynchronouslyexecuting concurrent processes. The concurrency occurs as a resulteither of multiple processors or of the requirements of aninterrupt-driven system. The next step is to identify the concurrentprocesses of the middle part, and to create appropriate interfaces tothe processes along the edges (device and interrupt handlers).

This step is frequently accomplished by a combination of analysisand synthesis. By analysis we mean the separation or decomposition of awhole system into its component parts; by synthesis, the combiningtogether of components so as to construct a system or a major part of asystem.

In traditional real-time design, analysis is almost alwaysaccomplished through DFDs [13, 17, 20]. The transforms of DFDs are thencombined (the synthesis step) to form concurrently executing tasksthrough application of principles such as common access to data, time ofexecution, and degree of common functioning [7]. Such principles canalso be applied to Ada designs.

Ada, however, provides the possibility for a greater degree of"process abstraction" than older languages/RTEs and henceallows an alternate view of task decomposition. The principal Adafeature allowing this new viewpoint is the capability of allowing a setof layered abstractions of concurrent processes; that is, concurrentprocesses may depend on other concurrent processes in a convenient andclear manner. This may or may not involve literal nesting of theprocesses, but, in any event, establishes a hierarchy or layering ofconcurrent functionality.

The important change that results from this new viewpoint is thatthe decomposition phase is not a process of analysis-synthesis as intraditional real-time design, but is rather a process of hierarchicaldecomposition directly into the concurrent processes represented by Adatasks. This approach is strongly and directly influenced by PAMELA [5],and also by object-oriented design [2] and principles of informationhiding [14].

After all major concurrent processes are identified, they areinvestigated for instances of internal concurrency and need for furtherprocess abstraction. If instances are found, they are furtherdecomposed into processes (more analysis) in a manner similar to theinitial decomposition step. This process is repeated at each level ofthe decomposition until all instances of concurrency (abstractprocesses) are identified.

The entire decomposition process is supported by a set f graphicalmethods for pictorially illustrating the design. The pictures arecalled process graphs, and are simple to draw and change. They aresimilar to DFDs--in fact, the entire decomposition process is similar innature to the development of a set of "leveled" DFDs, thedifference being that the process graphs represent data transforms thatwill be directly implemented as Ada concurrent constructs. Oneimportant difference from traditional DFDs is that the process graphsshow control as well as data flow.

The next step is to address the communication between the abstractprocesses.

Communication

Ada provides a rich set of options for task communication throughthe mechanism of the rendezvous. The asymmetry of the rendezvous (thecalled task having greater flexibility) makes the decision about whichtasks call and which are called a vital design issue. Further, since therendezvous is a tightly coupled [12] mechanism of task communication, itis often important to uncouple processes. Young notes [19, p. 153] thatthere is a "frequent need to introduce 'third party'tasks to decouple asynchronous process." We call these third-partyprocesses "intermediaries."

Intermediary tasks are used to reduce the degree of synchronizationbetween two tasks. They provide a resting place for data, allowing thetasks that use them to operate asynchronuosly. There are three kinds ofintermediary tasks: buffer, transporter, and relay.

In this context, buffer has a special meaning. It specificallyrefers to a temporary data repository (e.g., a queue or stack) that isstrictly a called task--one that makes no calls on other task entries.Typically, one task would call an Enqueue entry while a different taskwould call a Dequeue entry.

A transporter is the exact reverse: It is a temporary data storethat has no entries, but is strictly a calling task. Typically, it willcall one task to get data and another to deliver the data.

A relay is a task that accepts data by being called and deliversdata by calling another task. (Or it may take data by calling andprovide data by being called.)

Buffers and relays will be illustrated in the case study at the endof this article.

The task communication decisions are shown on the process graphs,along with the data flows. In order to retain their simple structure,the process graphs only show the simplest form of the caller/calleddecisions. They show callers and called tasks (including multiple callsto the same entry), and all intermediaries, but do not show propertiesof the design such as timed or conditional entry calls or the use of aselective wait.

Architecture

Given the set of concurrent processes and their communication andsynchronization, the final step in the design is to establish theoverall architecture of the system. This is comprised of packagingdecisions (in Ada this is literally deciding what processes go intowhich packages), compilation decisions (identification of individualcompilation units), and completion of the interfaces between processes.

Important factors during this phase arevisibility/information-hiding decisions, use of already created librarypackages, and the creation of general-purpose packages during thedevelopment of the system being designed. These latter twoconsiderations are of critical importance to Ada's success inleading to a viable and effective "software components"industry.

The packagig decisions are shown in a simple way on the structuregraph by drawing lines around the processes that comprise the specificpackages. The packages are then named.

Up to this point in the design, there has been no Ada code writtenand no (formal) consideration of the detailed design issues of thealgorithms expressed within the task bodies. (Of course, as in anysoftware design process, the top-level and detailed designs interact andchange in an iterative manner; the wise designer gives considerablethought to the detailed needs of the tasks in making caller/called andother task communication decisions.)

The next step is to transform the complete process graph into Adacode. A compilable Program Design Language (PDL) is useful for thispurpose (since it helps create other design products and documentation),but any Ada compiler will do. At the top-level design stage, the PDLshows the package specifications, including all interfaces to otherpackages and all type and exported object definitions. The task bodiesare declared as stubs, using the separate capability of Ada.

It is important to note that considerable design must be performedat this stage that does not directly deal with concurrency; typedefinitions, for example, must be complete before the top-level designis complete. If the tasks are large and complex, the internalfunctionality of the tasks must also be expressed during the top-leveldesign. This article does not address this essentially sequentialaspect of design of real-time systems.

The use of compilable PDL (or an Ada compiler) is important at thisstep since it ensures consistency among system interfaces. This isconsistent with the requirement of complete type definitions at thisstage.

After the top-level design is complete, the detailed design begins.This consists of adding detail to the separate task bodies. The mostimportant additional detail (from a concurrent design sense) is (1) theaddition of the accept statements corresponding to the entries declaredduring top-level design, and (2) the entry calls made by calling tasks.The compilable PDL is again important here to ensure the internalconsistency of the interfaces. These interfaces will typically dependon the complete set of type definitions established during top-leveldesign.

All interface logic, including select statements, guards onaccepts, and conditional or timed entry calls, are shown as complete Adacode at this stage of the design. The remainder of the internal logicof the tasks (and of procedures, either nested in the tasks or inexternal packages providing services) consists of the algorithmsexpressing the functionality of the system. These algorithms aredescribed with comments in the detailed design.

The last step of the design process is to perform extensive reviewsof the proposed architecture. These reviews are conducted withstructure graphs [3] and the PDL as the primary aids for discussing thedesign decisions that have been made. The structure graph shows

(1) how tasks are encapsulated into packages.

(2) what (if any) package nesting results from the hierarchicalflavor of the process decomposition process, and

(3) the details of task communication.

If the is altered as a result of the reviews, both the PDL and thestructure graphs are modified accordingly. A complete isomorphismshould exist between the PDL code and the elements of the structuregraphs for the final design documentation.

The design methodology described above is further illustrated inthe next section with a sample design for a real-time system.

CASE STUDY: REMOTE TEMPERATURE SENSOR

The recommended Ada design methodology is illustrated below with aproblem adapted from the Remote Data Acquisition System suggested byYound [18]. The application presented is a remote temperature sensor(RTS) that obtains temperature readings from a digital thermometer andreports the values back to a host computer.

Problem Specification

The function of the RTS is to periodically query a digitalthermometer for the temperature of a specified furnace. The temperaturevalues are transmitted to a remote host computer, which specifies theinterval between temperature readings for each furnace.

The specific tasks performed by the RTS are

(1) receiving ans storing orders (control packets) from the hostcomputer; the control packets contain

(a) the furnace number, and

(b) the frequency with which the temperature of the furnace is tobe read;

(2) keeping track of time;

(3) querying the digital thermometer and storing temperatures;

(4) transmitting furnace number and temperature (data packets) tothe host computer; and

(5) handling the message protocol with the host computer.

The characteristics of the host computer are that

(1) it is remote from the RTS and digital thermometer;

(2) it transmits control packets to control the frequency withwhich the temperature of each furnace is read;

(3) it receives messages in a simple format, containing

(a) the furnace number, and

(b) the temperature of a given furnace; and

(4) it implements the message protocol with the RTS.

The digital thermometer accepts an input as a furnace number in thernage 0-15 deg. C and provides an output of the temperature of thefurnace in the range 0-1000 deg. C. It generates an interrupt tot heRTS after it has placed the temperature in a designated hardware buffer.

The RTS and host computer exchange messages. The host computersends control packets (CPs) to the RTS, and the RTS sends data packets(DPs) to the host computer. The message formats and the messageexchange protocol are highly simplified for purposes of this case study.The formats are

(1) CP format: (STX) (FF) (SS) (ETX)

(2) DP format: (STX) (FF) (TTTT) (ETX) where FF is the furnacenumber in the range 0-15 deg. C; SS is the seconds between temperaturemeasurements (minimum time between readings) in the range 10-99; TTTT isthe temperature in the range 3-1000 deg. C; STX is the start of text;and ETX is the end of text.

The transmit and receive protocols are the same for both the RTSand the host computer:

(1) Transmit the message, and wait for one of three events:

(a) acknowledgment (ACK) send next message,

(b) negative acknowledgment (NAK) retransmit message, or

(c) time-out (2-second delay) retransmit message.

(2) Receive a message and check for validity:

(a) if valid, send acknowledgment (ACK), or

(b) if invalid, send negative acknowledgment (NAK).

The criteria for validity are that the message must have an STX,and that the two fields of the message must contain numbers in thecorrect range. The messages are transmitted as a continuous sequence ofASCII characters.

Figure 4 shows the interfaces between the RTS and the varioussystem devices. CP[ACK represents either an acknowledgment or negativeacknowledgment (i.e., an ACK or NAK) of a control packet sent from thehost to the RTS. Similarly, CP[ACK represents an ACK or NAK of a datapacket sent from the RTS to the host.

The processing for the RTS must be as follows:

(1) At any time, receive control packets from the host. Buffer upto six control packets at a time. When the buffer is full, ignoreadditional incoming messages. Generate ACK or NAK for incoming controlpackets from the host computer.

(2) At any time, receive ACKs and NAKs of data packets.

(3) Build and maintain a control table containing the frequencywith which each furnace is to be read.

(4) Read the temperature of each furnace periodically, inaccordance with its specified frequency. Query the digital thermometerto determine the temperature of the furnace. Store the necessaryinformation for a data packet in a buffer.

(5) Provide a buffer for the data packet information. Buffer up to100 furnace/temperature readings, overwriting the oldest informationwhen necessary. The queue discipline is first-in-first-out (FIFO). Inorder to store the information as compactly as possible, the buffer mustmust contain information in numeric, rather than ASCII, format. Thefurnace/temperature reading in such a form is called an Internal DataPacket, or IDP.

(6) Whenever there is information in the buffer, build data packetsand transmit them to the host computer in accordance with thecommunication protocol. Transmit ACK or NAK for the control packetsfrom the host computer.

The processig described above depends on three adaptationparameters (system parameters) that must be easy to modify. Theparameters should be highly visible in the code. The only changesnecessary to modify the parameters are a change in one location and arecompilation of the code. The parameters and default values are

(1) time-out before retransmit of a data packet (2 seconds),

(2) periodicity of reading temperatures (5 seconds), and

(3) size of the input buffer for control packets (6 messages).

External Interfaces

The context diagram shown in Figure 4 illustrates the interfacesbetween the RTS and the external devices. Control packets (CPs) andacknowledgments of data packets (DP ACK) are received from the hostcomputer. Positive or negative acknowledgments of the control packets(CP ACK) are returned to the host. A furnace number, representing thefurnace for which the temperature is to be read, is sent from the RTS tothe digital thermometer. A temperature reading for the given furnace isreceived from the digital thermometer. A data packet (DP) isconstructed and sent to the host computer.

EDges-In Approach

The edges-in approach is employed by first determining theprocesses required to interface with the external devices. Figure 5represents a process graph that shows three processes interfacing withthe external devices. The remaining functionality of the RTS iscontained in the middle part and will be decomposed later. The threeedge processes are as follows:

(1) Receive host message (RX Host Msg). This process receiveseither a CP, or an ACK/NAK of a data packet. It determines whether a CPor ACK/NAK is received and passes the CP (STX and ETX are stripped off)or ACK/NAK (single character) to the RTS middle part for furtherprocessing.

(2) Transmit host message (TX Host Msg). This process transmitseither a DP, or an ACK/NAK of a control packet.

(3) Digital thermometer handler (DT Handler). This process sends afurnace number to the digital thermometer and receives from it thecorresponding temperature value.

Decomposing the Middle Part

The DFD shown in Figure 6 represents a restatement of the RTSspecifications, and depicts the required functions and the data flowsbetween them. Functional cohesion has been used as a design principleto combine the functions shown in the DFD into the abstract processesshown in Figure 7. Of the processes shown in Figure 7, three havealready been assigned as edge processes for the hardware interfaces.The remaining five processes, as shown in Figure 8, represent theprocess abstraction of the middle part:

(1) Analyze Hot Input. This process analyzes the imput that comesfrom the host computer and passes it on as follws:

(a) An input message is analyzed for validity, and a CP ACK (ACKfor a valid message, or NAK for an invalid message) is sent to anotherprocess (not shown in Figure 8) for transmission back to the host.

(b) A valid input message is converted from ASCII to decimal valuesand passed on to Manage Temperature Reading. The converted entity iscalled an Internal Control Packet, or ICP.

(c) An invalid input message is discarded.

(2) Manage Temperature Reading. This process manages the table offrequency readings for the various furnaces, and determines the time andorder for the reading of temperatures. The furnace number and time fornext temperature reading are passed to Create IDP.

(3) Create internal data packet (Create IDP). This process sendsthe furnace number received to the DT Handler at the appropriate timeand waits for a return of the respective temperature value. An IDPcontaining decimal values of the furnace number and correspondingtemperature is created and sent to the next process.

(4) Create new data packet (Create New DP). This process gets thenext IDP, and converts the furnace number and corresponding temperatureto ASCII. These ASCII characters are preceded by an STX and followed byan ETX to create the proper format for a new data packet.

(5) Determine Host Output. This process controls the sequence oftransmission of DPs to the host. After initiating transmission of a DP,it waits for either a DP ACK or a time-out. (This satisfies thetransmit protocol described in the problem specification.)

Introducing Intermediary Tasks

The proper decoupling of processes is accomplished by introducingintermediary tasks as shown in Figure 9, next page. The intermediariesare

(1) Buffer Input Msgs,

(2) Relay DP ACK, and

(3) Buffler IDPs.

The input messages from the host are stored in FIFO order in ASCIIformat using the task Buffer Input Msgs. When the buffer is full,additional input messages are ignored. A relay is added between Rx HostMsg and Determine Host Output to ensure asynchronous behavior for thesetwo tasks. If this was not done, incoming characters from the hostcould be lost while Rx Host Msg was waiting for a rendezvous (i.e.,Determine Host Output could be busy interacting with other processes).

The processes Create IDP and Create New DP have been decoupled byintroducing the buffer task Buffer IDPs between them. This allowstemperature readings to be continued to be made even if positive ACKsare not received for the DPs sent. When the IDP buffer is full, theoldest IDPs are overwritten.

Caller/Called Decisions

The introduction of intermediaries allows us to complete thecaller/called decisions of the middle part, as shown in Figure 9. Thecomposition of all the RTS tasks is shown in Figure 10.

Relay tasks accept input from a producer and pass the same input toa consumer. This makes Rx Host Msg (the producer) a caller relative toRelay DP ACK, and Relay DP ACK a caller relative to Determine HostOutput (the consumer). To prevent Rx Host Msg from being delayed (andhence losing input characters), it should make a conditional call onRelay DP ACK.

Buffer tasks are always pure servers. This makes Rx Host Msg andAnalyze Host Input callers with respect to Buffer Input Msgs. Similarly,Create IDP and Create New IDP are callers relative to Buffer IDPs.

Tx Host Msg receives either CP ACK from Analyze Host Input or a DPfrom Determine Host Output, and is considered a pure server. It doesnot make sense to have Tx Host Msg call either of the other two tasks asthis would severely restrict it as a simple device handler.

When the temperature table is scanned, Manage Temperature Readingdetermines the next temperature reading. The task Create IDP should notbe tied up during this scanning and is thus made the called task.

The task DT Handler is a simple device handler for the digitalthermometer and is therefore called by Create IDP. Reversing this callwould add an extra call that is not required here.

Determine Host Output makes a decision whether to send an old DP orto fetch a new DP from Create New DP. This decision process makes itnatural for Determine host Output to call Create New DP.

Ada Packaging

The processes shown in Figure 10 have been encapsulated in Adapackages as shown in Figure 11. Packaging decisions have been madebased on functionality and minimization of coupling [9]. The rationalefor these decisions is as follws:

(1) Device Handlers. This package contains all the tasks thatinterface directly with the hardware devices (Rx host Msg, Tx Host Msg,and DT handler). These device drivers are treated as a group, similarto a collection of mathematical subprograms or a graphics package. Thisrepresents "package coupling" as defined in [9]. The genericrelay task (Relay DP ACK) is instantiated inside the task body of RxHost Msg.

(2) Host Input. This package contains the task Analyze Host Input.The generic buffer task (Buffer Input Msgs) is instantiated inside thepackage body of Host Input. Analyze Host Input is a fairly extensivetask and does not have any functionality in common with the other tasks.It is, therefore, the only task (aside from the buffer task) in thispackage.

(3) Temp Reading. This package contains the two functionallyrelated tasks Manage Temperature Reading and Create IDP.

(4) Host Output. This package contains the two functionallyrelated tasks Determine Host Output and Create New DP. The genericbuffer task (Buffer IDPs) is instantiated inside the package body ofHost Output.

(5) Other Packages. The packages shown in Figure 11 use librarypackages that have been prepared in advance. These packages are withedas required:

(a) Global definitions (definitions). This package contains allthe constants, adaptation parameters, and types required by the otherpackages. This collection represents "definition" coupling asdescribed in [9].

(b) hardware-dependent entities (hdp). This package contains allthe hardware-specific entities such as addresses of hardware interruptsand buffers. This collection also represents definition coupling, sincethe various Ada modules will only use the entities that correspond to agiven hardware device. DT Handler, for example, will use the address ofthe hardware buffer for the digital thermometer in a for-use-at clause.

Program Design Language(PDL)

The PDL phase consists of transforming the design described infigure 11 into a programming structure using Ada constructs. Thetop-level design illustrates the overall structure; it contains a mainprocedure, package specifications, and package bodies. The packagebodies contain subprogram and task declarations, and entrance proceduresfor communication between tasks that reside in different packages. Anentrance procedure allows the task specification to be hidden in thepackage body rather than be visible in the package specification. Thisis good design practice, and Burns recommends that this "proceduralinterface" be used for "all tasks" [4, p. 113]. Detailsof task and subprogram algorithms are deferred to the detailed designphase by using Ada's separate construct. The compiler used toprocess the RTS PDL was the DEC VAX Ada compiler. A description of thetop-level design phase is given below. An example of supplying asubunit for detailed design is also given to illustrate the methodology,but a complete implementation is not given.

Top-Level Design. The top-level design is described below. Thepackage specification only includes the information that is required tobe visible to users of the package. This includes entrance procedures,generic formal parameters (for generic packages), comments that specifycalls to entrance procedures in other packages, and the pragma INLINEwhere appropriate. all other information that is not necessary to bedisclosed to the users of the package is hidden in the package body.The RTS top-level design is as follows:

(1) Support units. Support units must be prepared in a bottom-upfashion before we start the top-level design of the application packagesin a top-down fashion. The following units are used by the applicationpackages:

(A) Definitions. This package constants, adaptation parameters,and types. It imports the package Calendar (supplied with the standardenvironment). The Ada code is shown in Figure 12, page 708.

(b) HDP. This package contains absolute addresses for hardwareinterrupts and buffers for the host input and output channels, and forthe digital thermometer. The Ada code is shown in Figure 13, page 708.

(c) Buffer Ignore. The generic, parameters include the size of thebuffer and the type of elements to be bufferd. the package bodycontains the declaration of the task Buffer, and the bodies of theentrance procedures. The conditional entry call in Engueue ensures thatRx Host Msg does not wait for a rendezvous with Buffer Input Msgs if thebuffer is full. If the call were unconditional, input characters fromthe host could be lost while Rx Host Msg was tied up waiting for spacein the buffer. The details of the implementation of the task Bufferhave been deferred by using the separate clause. The Ada code is shownin Figure 14, page 709.

(d) simple Relay. The generic parameters include the type of itemto be relayed and the procedure name of the consumer. The packagecontains the declaration and body of the task Relay, and the body of theentrance procedure. The Ada code is shown in figure 15, page 709.

(e) Buffer Overwrite. The generic parameters are the size of thebuffer and the type of elements to be buffered. The packages bodycontains the task declaration and bodies of the entrance procedures.The only difference between this generic buffer package and BufferIgnore is that entrance procedure Enqueue does not make a conditionalcall to the buffer task (Buffer IDPs). If the buffer is full, the newelement is stored on top of the oldest. (This is not shown in thetop-level design.) The Ada code is shown in Figure 16, page 709.

(2) Application packages. The following application packages wereprepared for the RTS top-level design:

(a) Device Handlers. Task declarations for the various devicehandlers (Tx Host Msg, Rx Host Msg, and DT Handler) are made in thepackage body. The entities in the package HDP are imported by thepackage body for the use of for-use-at clauses for the interruptentries. The Ada code is shown in Figure 17, page 710.

(b) Host Input. The package body imports the generic packageBuffer Ignore, and instantiates it for a size of Max CP Msgs and type CPFormat. The task Analyze Host Input is declared with commentsindicating calls to other units. This task is a pure caller and has noentries. The Ada code is shown in Figure 18, page 711.

(C) Temp Reading. The tasks Manage Temperature Reading and CreateIDP are declared in the package body, with their bodies declared asseparate. The Ada code is shown in Figure 19.

(d) Host Output. The package body imports the generic packageBuffer Overwrite, and instantiates it for a size of Max IDP and type IDPFormat. Task declarations are included for Determine Host Output andCreate New DP, with details deffered using the separate construct. TheAda code is shown in Figure 20.

(3) Main procedure. Ada requires a main program to start theelaboration process of packages and their objects, subprograms, andtasks. This main procedure is called RTS Main and is shown in Figure21, next page. This procedure simply imports the package Host Input andhas a "null" body. This is sufficient to start theelaboration of the other packages (which contain their own with clauses)and the activation of tasks encapsulated within these packages. Code tobe used during the testing phase, such as declarations of simulationtasks, subprograms, and test data, could be placed in this driver.

This completes the top-level design phase. The remaining part ofthe design process is to supply the Ada subunits that contain thatdetails of the RTS implementation.

Detailed Design. An example of how Ada subunits are prepared isshown in Figure i2 for the task Determine Host Output. The parent (HostOutput) of this subunit is named in the separate clause, and the taskbody is specified with a declarative part and an executable part. Thetask gets the first DP from Create New DP and sends it to DeviceHandlers. Subsequent processing is performed within a selective waitinside an infinite loop. The selection is based on a choice betweenaccepting a DP ACK or waiting for a time-out. If a DP ACK is received,a new DP is obtained and sent to Device Handlers if the DP ACK is anACK. If the DP ACK received is a NAK, an old DP is sent to DeviceHandlers. If the time-out expires (i.e., no DP ACK is received withinRe TX-Delay seconds), an old PD is sent to Device Handlers forretransmission.

The detailed design will proceed by supplying all the remainingsubunits, with the Ada compiler checking interfaces and properimportation of required entities. These entities should be imported byhaving the subunits with the necessary packages and subprograms, ifpossible. This iwll reduce the amount of recompilation required if theimported library units are changed. The structure graph in Figure 23depicts the interfaces between the subprograms and tasks in the variouspackages.

SUMMARY

Traditional real-time design methodologies have been examined withregard to their suitability for designing large real-time systems inAda. Each of these methodologies have some features that can be used inreal-time design, but none of them representas a complete designmethodology for systems built with Ada. A consistent methodology hasbeen proposed here that is specifically tailored to Ada designs andtakes advantage of Ada's excellent design features. The proposedmethod includes a systematic approach for decomposition into concurrentprocesses, specification of process interaction, the use of intermediarytasks to affect the degree of task coupling, packaging of tasks usingAda packages, and the use of a (compilable) PDL for top-level anddetailed design. The methodology is illustrated with a case study.