<r NPSCS-92-017 NAVAL POSTGRADUATE SCHOOL Monterey, California Prototyping Hard Real-Time Ada Systems in a Classroom Environment Luqi, M. Shing, P. Barnes and G. Hughes Approved for public release; distribution is unlimited. Prepared for: Naval Postgraduate School Monterey, California 93943 FEDDOCS D 208.14/2 NPS-CS-92-017 -o\i NAVAL POSTGRADUATE SCHOOL Monterey, California HARRISON SHULL Rear Admiral R.W. West, Jr. Superintendent Provost This report was prepared with research funded by the Naval Research Funds provided by the Naval Postgraduate School. Reproduction of all or part of this report is authorized. This report was prepared by: / g]|JRITVCLASSIFICATIONOF THIS PAGE ___ £CH"UL — REPORT DOCUMENTATION PAG&& 11 REPORT SECURITY CLASSIFICATION w-1mb -RE-S.T-RI.C.T-IIIVIE- MARikjmWimCs.. ! i: 1 UNCLASSIFIED 1 'SECURITYCLASSIFICATION AUTHORITY 3. DISTRIBUTION/AVAILABILITYOr REPORT Approved for public release; - dEClASSiFiCATION,DOWN0RAdINg SCHEDULE distribution is unlimited PERFORMINGORGANIZATION REPORT NUMBER(S) 5. MONITORINGORGANIZATION REPORT NUMBER(S) NPSCS-92-017 NAME OF PERFORMING ORGANIZATION 6b. OFFICE SYMBOL 7a NAME OF MONITORINGORGANIZATION Computer Science Dept. (ifapplicable) cs Naval Postgraduate School ADDRESS (City, State, andZIPCode) 7b ADDRESS (City, State, andZIPCode) Monterey, CA 93943 .NaMEOPFUndin&sPOnsOring 8b. OFFICE SYMBOL 9. PROCUREMENT INSTRUMENT IdENTiFiCATiOn nuMBER ORGANIZATION (ifapplicable) Naval Postgraduate School ADDRESS (City, State, andZIPCode; 10 SOURCE OF FUNDING NUMBERS PROGRAM PROJECT TASK WORK UNIT ELEMENT NO. NO. NO ACCESSION NO. Monterey, CA 93943 TITLE (IncludeSecurityClassification) Prototyping Hard Real-Time Ada Systems in a Classroom Environment PERSONALAUTHOR(S) 2. Luqi, M. Shing, P. Barnes and G. Hughes W 3a.TYPE OF REPORT 13b. TiME COVERED 14 DATE OF REPORT (Year, Month, Day) 15 PAgEc6x;NT FROM TO 1992, December, 31 supplementary notation e. COSATI CODES 18. SUBJECTTERMS (Continueonreverseifnecessaryandidentifybyblocknumber) FIELD GROUP SUB-GROUP 9.ABSTRACT (Continueonreverse ifnecessaryandidentifybyblocknumber) Teaching graduate students how to develop hard real-time Ada software for embedded systems is a challenging task. We successfully used Ada in a series of software engineering courses to teach graduate students the charac- teristics ofhard real-time software and fundamental skills to develop and validate complex systems and timing re- quirements through software prototypes ofthe systems. A research tool, called CAPS (ComputerAided Prototyp- ing System)*, was used by the student software designers to construct software prototypes based on the require- ments of the system as well as to automatically generate Ada code interconnecting reusable modules. The approach greatly stimulated the students' interest and helped them togain first hand experiences in developing hard real-time systems. o. blSTR:BUTiON.AVAILABIL!TYOF ABSTRACT 21. ABSTRACT SECURITY CLASSIFICATION (J UNCLASSIFIED/UNLIMITED ["J SAMEAS RPT. [~J DTIC USERS UNCLASSIFIED 2a. NAME OF RESPONSIBLE INDIVIDUAL 22b. TELEPHONE (IncludeAreaCode) 22c. OFFICE SYMBOL Luqi (408) 656-2735 CSLq DFORM 1473,84MAR 83 APRedition may be used until exhausted SECURITY CLASSIFICATION OFTHIS PAGE All othereditions areobsolete UNCLASSIFIED NAW GRADUATE SCHOOL MONTEREY CA 93943-5101 Prototying Hard Real-Time Ada Systems in a Classroom Environment Luqi, M. Shing, P. Barnes and G. Hughes Computer Science Department Naval Postgraduate School Monterey, CA 93943 ABSTRACT Teaching graduate students how to develop hard real-time Ada software for embedded sys- tem is a challenging task. We successfully used Ada in a series of software engineering courses to teach graduate students the characteristics of hard real-time software and fundamental skills to develop and validate complex systems and timing requirements through software prototypes of the systems. A research tool, called CAPS (Computer Aided Prototyping System)*, was used by the student software designers to construct software prototypes based on the requirements of the system as well as to automatically generate Ada code interconnecting reusable modules. The approach greatly stimulated the students' interest and helped them to gain first hand experiences in developing hard real-time systems. *Thisresearch was supported in part by the National Science Foundation undergrant numberCCR9058453. KEYWORDS Embedded Systems, Software Prototyping, Computer Aided Software Engineering, Ada Education, Hard Real-Time Systems, Requirements Engineering. INTRODUCTION 1. Many embedded software systems are safety critical, and depend on meeting hard real-time deadlines for their successful operation. Patriot missile control software is one example of this kind of system. "On February 25, 1991, a Patriot missile defense system operating at Dhahran. Saudi Arabia, during Operation Dessert Storm failed to track and intercept an incoming Scud. This Scud subsequently hit an Army barracks, killing 28 Americans" [1]. The single most costly event in the Operation Dessert Storm was the result of a software tim- ing error. It underscores the importance and difficulties in the design and development of hard real-time software in our military systems. Hard real-time systems are defined as those software systems in which the correctness of the system depends not only on the logical result ofcomputa- tion, but also on the time at which the results are produced [2, 3]. One of the major differences between a hard real-time system and a conventional system is that the application software must meet its deadlines even under worst case conditions. Hard real-time software systems are typi- cally embedded in larger systems, performing critical control functions. These real-time control functions require the software system to interact with a wide variety of hardware/software sub- systems via networks. The process of design and development of these systems is often plagued with uncertainty, ambiguity and inconsistency. Typical tactical control software consists of numerous processes including communication processing, known-object recognition, track pro- - 1 - cessing, and display processing, among others. While conceptually these processes could fre- quently run concurrently, limitations in hardware resources often force these processes to be sequentialized in a centralized implementation through an interrupt driven prioritization scheme. This scheme produces a completely dynamic schedule whose effects are difficult to predict and control. The timing requirements are difficult for the user to provide and for the analysts to deter- mine. As the software is modified, various aspects of its execution behavior change, including maximum execution times and execution precedences for the subfunctions. Often these changes are only observed after the fact: the system crashes during testing, or required functions don't get processed when needed. The response is often to tweak the schedule until the system appears to run acceptably on the available test cases. There is no assurance that the system will perform acceptably in situations that have not been explicitly tested, which usually includes conditions that may arise during the actual operation of the system. A better approach to such problems involves systematic and automatable methods for con- structing schedules and real-time simulations (or prototypes) ofthe systems. The Computer Aided Prototyping System (CAPS) is a research tool developed at the Naval Postgraduate School to pro- vide an integrated software development environment aimed at rapidly prototyping hard real-time embedded software systems and generating Ada code automatically [4]. CAPS has undergone extensive testing by several classes of graduate students. Teaching graduate students how to develop hard real-time Ada software for embedded sys- tem is a challenging task. Software Engineering is a fast moving discipline. Utilizing the state of the art research results for teaching graduate courses is an important supplemental way to ensure the quality of the courses. Such a practice has been instrumental in refining systematical approaches to requirements analysis [5]. Due to lack of good textbooks, we had to use the same approach to create our own teaching materials based on ourresearch results and tools. As a result, we successfully used Ada in a series of software engineering courses to teach graduate students the characteristics of hard real-time software and fundamental skills to develop and validate com- plex systems and timing requirements through software prototypes of the systems to accomplish the important learning goals of our graduate students for their future DoD system acquisition tasks [6]. The series of Software Engineering courses employing Ada includes "Software Methodolo- gy"(CS3460) as the introductory course for the computer science majors, "Software Development for Combat Systems"(CS3050) as the introductory course for the non-computer science majors, followed by "Software Engineering"(CS4500), "Advanced Software Engineering"(CSS4520), and "Software Engineering with Ada"(CS4530). We developed an advanced textbook, Software Engineering with Abstractions - An Integrated Approachfor Large Ada Software, to support this series ofcourses with a combination offormal approaches, a second-order logic for specifications of concurrent and real-time systems, and detailed examples of practical applications [7]. This textbook is used in CS4500 to give solid graduate education in Software Engineering to the com- puter science majors. Advanced technology, research topics, theoretical issues and skills for soft- ware automation were taught in CS4520 and CS4530. At the beginning of the series, for the non- computer science majors or the graduate students who have never experienced software system development, a fast and practical exploration was needed before they could possibly understand why the rigorous formalism for system specifications was needed in the textbook [7]. In order for the students to gain first hand experience in software development, they are required to work on the large projects in CS3460 or CS3050. In the courses, the student designers used CAPS to construct software prototypes based on the requirements of the system and to auto- matically generate Ada code interconnecting reusable modules. Hardware components and inter- faces were simulated in the CAPS prototype model. The approach greatly stimulated the students' interest and helped them to gain first hand experiences in developing hard real-time systems in Ada. The students in these courses designed and implemented prototypes of several hard real-time systems: the Patriot Missile Defense System, the Robot Motion Control System, the Fish Farm Control System and the Generic Command and Control Station. This paper summarizes the expe- rience gained from these projects. THE COMPUTER AIDED PROTOTYPING SYSTEM 2. CAPS provides facilities for computer-aided design, software component reuse, and auto- mated Ada code generation (Figure 1). These tools are developed to help software engineers rap- idly construct and adapt software, validate and refine user requirements, and to check consistency of proposed design [8]. The process supported by CAPS provides requirements and designs in a form that is useful in the construction of the operational system, as well as in the acquisition pro- cess to assess optimized implementations delivered by contractors, and to integrate independently developed subsystems. CAPS allows the user to specify the requirements of a proposed system informally in a structured top-down fashion using easy-to-understand graphics, assists the designer in augmenting the informal specifications with formal annotations, and automatically translates the result into executable Ada code that realizes the timing requirements based on declared maximum execution times and monitors conformance of actual execution times to the maximum execution times specified in the design. User Interface Figure 1. CAPS Advanced Rapid Prototyping Environment THE CAPS METHOD 2.1 There are four major stages in the CAPS rapid prototyping process: software system design, construction, execution, and debugging/modification (Figure 2). The initial prototype design starts with an analysis ofthe problem and a decision about which parts ofthe proposed system are -3 to be prototyped. Requirements for the prototype are then generated, either informally (e.g. English) or in some formal notation. These requirements may be refined by asking users to verify their completeness and correctness. After the requirements analysis is completed, the designer uses the CAPS graphic editor to draw dataflow diagrams with nonprocedural timing and control constraints as part of the specification of a hierarchically structured prototype, resulting in a pre- liminary, top-level design free from programming level details. The underlying computational model unifies dataflow and control flow, and provides a mechanism for developing top-down decompositions. The user may continue to decompose any software module until its components can be realized via reusable components drawn from the software base or new atomic compo- nents. This high-level specification is then translated into Ada for execution and evaluation. Debugging and modification is assisted by a design database that helps the designers in managing the design history and coordinating changes. Reusable Software L_i Initial requirements DBMS changes Construct/modify Software Design prototype Base Database Translate/schedule prototype in Ada Execution Support System Demonstrate prototype Figure 2. Iterative Prototyping Process in CAPS THE PROTOTYPE SYSTEM DESCRIPTION LANGUAGE 2.2 The CAPS tools are based on the Prototype System Description Language (PSDL). PSDL is a high-level language designed specifically to support the specification of real-time software sys- tems, as well as to organize and retrieve reusable components in the software base [9]. PSDL lets designers sketch a system using computation graphs, where the vertices are operators and the directed edges are data streams, and then refine the design by adding timing and control con- straints in text form. Operators are state machines whose internal states are modeled by state variables. Operators with an empty variable set behave like functions. PSDL operators can be triggered by data (spo- radic operators) or by periodic timing constraints (periodic operators). When triggered, an opera- tor will produce output based on input values and values of internal state variables. There are two kinds of operators: atomic operators and composite operators. An atomic operator is one that can be realized by an implementation stored in the software base or supplied by the software engi- neers, and a composite operator is one that can be decomposed into a network of more primitive operators represented as enhanced dataflow diagrams. Operators communicate via two kinds of data streams: dataflow streams and sampled 4- streams. A dataflow stream can be thought of as a FIFO buffer of capacity one that connects syn- chronized operators. Data in dataflow streams represents discrete transactions, and is removed from the stream when read. A sampled stream can be thought ofas a single memory cell and con- nects operators with uncoordinated rates. This type of data usually comes from a continuous data source and can be used many times or written over before use, depending on the rate of its input and use. Real-time applications, design flexibility, and code reuse motivate the timing and non-proce- dural control constraints of PSDL. Each time critical operator has a maximum execution time con- straint, representing the maximum time the operator may need to complete execution after it is fired, given access to all required resources. In addition, each periodic operator has a.period and a deadline. The period is the interval between triggering times for the operator and the deadline is the maximum duration from the triggering of the operator to the completion of its operation. Each sporadic operator has a maximum response time and a minimum calling period. The minimum calling period is the smallest interval allowed between two successive triggerings of a sporadic- operator. The maximum response time is the maximum duration allowed from the triggering of the sporadic operator to the completion of its operation. To model distributed systems, PSDL also provides the option of specifying the maximum delay associated with any data stream. PSDL also allows the specification of both input and output guards to provide conditional execution of an operator and conditional output of data. Guards can include conditions on timers that measure durations of system states, and can allow operators to execute only when fresh data has been written to an input stream. Control constraints can also trigger exceptions. THE CAPS TOOLS 2.3 The set oftools provided by CAPS includes the user interface, software database system, and execution support system. The user interface in CAPS includes a graphic editor, a syntax-directed editor, and a browser. The graphic editor and the syntax-directed editor together provide a user-friendly environment for the user/software engineer to construct a prototype using a combination of graphical and textual objects. The browser allows software engineers to view reusable components in the software data- base system. The software database system, which consists of a software base and a design database, pro- vides facilities for software reuse, automated project management, and version control. The soft- ware base keeps track of the PSDL descriptions and Ada implementations for all reusable software components in CAPS. The design database coordinates the concurrent efforts of a team of software engineers and manages the different versions and alternatives ofthe design and docu- ments they produce. The execution support system consists of a translator, a static scheduler and a dynamic sched- uler. The translator generates code that binds together the code supplied by the designer and the reusable components extracted from the software base. The static scheduler and the dynamic scheduler together create the real-time schedule and control code needed for executing the proto- type. The resultant Ada main program consists of four parts. The first is a set of data streams, implemented as instantiation of generic packages containing Ada tasks controlling the mutually exclusive read/write access to the data buffers. The second part consists of a set ofdrivers, one for each of the atomic operators. Each driver reads data from the specified input streams, evaluates the input guards, executes the operators, evaluates the output guards and then writes the outputs to -5- the specified data streams accordingly. The third part is a static schedule which is a high priority Ada task that executes all time-critical operators in a deterministic and timely manner. The sched- ule is generated automatically based on the timing constraints and the precedence of the operators specified in the data-flow graph. The last part of the Ada main program is a dynamic schedule, which is a low priority Ada task that executes the non-time-critical operators during the slack time in the static schedule. OUR CLASSROOM EXPERIMENTS 3. Four hard real-time software system prototypes have been designed and developed by stu- dents using CAPS. Due to lack of space, we shall only present the Patriot MissileDefense System and the Generic Command and Control Station prototypes here. THE PATRIOT MISSILE DEFENSE SYSTEM 3.1 Figure 3 shows the PSDL specification ofthe prototype for a simplified two-dimensional ver- sion of the Patriot missile defense system. This prototype was developed by five Weapons System students for the class "Software Development for Combat Systems." In this course, non-com- puter-science students learned the basics ofreal-time systems, software engineering, and real-time Ada programming. They also must learn to use UNIX workstations running X Window Systems and Motif along with software tools such as Verdix Ada Development System (VADS), CAPS and TAE Plus. The prototype shown in Figure 3 has a total of nine atomic operators. The opera- tors patriotjadar, check threat, control_patriort and scud_radar are time-critical, each has a maximum execution time of 10 ms. Figure 4 shows the TAE Plus user interface for the prototype, which was developed using the TAE Work Bench and consists of two panels, one representing the Scud launcher and a tracking radar, and the other representing the Patriot System Console. Two major problems had to be over- come to use TAE Plus user interfaces for the CAPS prototypes. First, the user interface must be subordinate to the real-time system (i.e. execution ofthe time-critical operators cannot be blocked by the user interface processing), while the architecture generated by TAE Plus is one where the user interface is in control, executing application functions as driven by user actions. Second, the X Window System Xlib is non-reentrant. Thus user interface operations may not be interrupted by other user interface operations before completion. Our solution to this problem involved a user interface architecture where all calls to the user interface by the real-time applications are made mutually exclusive through an Ada monitor task. All rendezvous are embodied in a selective wait with a 10 ms time-out. If no rendezvous are ready within the 10 ms, the task exits the selective wait and checks for TAE WPT events. All WPT events are processed before checking for rendez- vous requests again. (Interested readers should refer to [10] for details.) GENERIC COMMAND AND CONTROL STATION 3.2 This prototype was developed by a group of five Computer Science students for a class cre- ated by the first author titled "Software Engineering with Ada." In this course, students learn how to apply the software engineering principles in the design of large, real-time, embedded computer systems through the use ofautomated tools in the Ada environment. The class project was to build upon previous prototyping efforts on a SUN3 workstation [11] and use the CAPS tools to develop an improved prototype for a generic C3I station and simulations ofits interacting external systems on the SPARCstations. Figure 5 shows the PSDL specification of the top-level design of the pro-