Real-time system design

Real-time system design

73.1 Purpose

This chapter briefly overviews real-time information processing systems. The technical details associated with real-time systems are beyond the scope of this book. This material is intended as background for systems analysts or information system consultants who must communicate with real-time specialists and/or vendors.

73.2 Strengths, weaknesses, and limitations

A real-time system should be considered when response time requirements are extremely tight. Real-time systems tend to be more expensive to develop and to operate than are online, interactive, and batch systems.

73.3 Inputs and related ideas

Developing a real-time system is much like developing any system. Many of the tools discussed in Parts II, IV, V, and VI are used. State transition diagrams (Chapter 30) are valuable for planning and documenting changes in state. Stacks and queues are explained in Chapter 43. Chapter 78 provides some insight on the process of evaluating computer hardware and peripherals. Chapter 79 discusses queuing theory and bottleneck analysis.

73.4 Concepts

A real-time system responds to events as they occur and (typically) provides feedback to influence or control those events. For example, the system that guides a smart bomb to its target is a real-time system. A production control system that monitors and controls a modern steel mill is another example.

The technical details associated with real-time systems are beyond the scope of this book. The material in this chapter is intended as background for systems analysts or information system consultants who must communicate with real-time specialists and/or vendors. Note that numerous references are listed at the end of this chapter.

73.4.1 Events and states

Most real-time system actions and behaviors are performed in response to asynchronous (hence unpredictable) external events. A given external event triggers a change in state (e.g., a change in value, status, or behavior) and the real-time system reacts by taking a pre-specified action or actions. Consequently, real-time system design is sometimes called event-driven design.

73.4.2 Design considerations

In addition to the problems associated with developing a traditional information system, the analyst or designer of a real-time system faces significant constraints and must consider numerous interrelated hardware, software, and data issues.

73.4.2.1 Constraints

Real-time systems typically operate under very tight time constraints. For example, on a production control system, certain crucial events may require response times of a fraction of a second or the transfer of a certain amount of data between two components in a brief period of time. Additionally, high reliability (as measured by mean time between failures) is often essential. For example, the failure of a production control system can literally put a company out of business.

Concurrency, a measure of the number of tasks the system can process concurrently, is another important criterion. Asynchronous events can (by definition) occur at any time and are not synchronized with other events. Consequently, two or more events can occur concurrently or even simultaneously, and the response time constraint might require a response to both events within a very brief time.

73.4.2.2 Hardware

To achieve rapid response time, most real-time systems are dedicated to a specific realtime application (or set of related applications) and designed to be under-loaded. The designer might analyze all possible events, define worst case scenarios (for example, the maximum possible number of concurrent events), determine the processor and memory configuration needed to provide peak load computing power, and then specify double (or triple, or more) than that level of power. Excess computing power means relatively low percentage utilization, but low utilization means that events rarely wait for the system.

Reliability is usually achieved through redundancy. Fault tolerant computers incorporate redundant circuits and components, and in some cases the entire system (the processor, memory, the database, etc.) is replicated. In the event of a system or component failure, special hardware and software automatically switches control to the backup system or component. Uninterruptable power supplies also contribute to reliability.

To achieve concurrency, a computer must support multi-tasking, the ability to concurrently process several tasks. (A task is a single program or routine in memory and available to be executed.) On many systems, multi-tasking is implemented by the operating system (Section 73.4.2.3).

A computer with a single processor can execute only one instruction at a time. Such computers implement multi-tasking by quickly switching the processor’s attention from one task to another and back again. If the computer is equipped with multiple processors, however, several instructions (one per processor) can be executed simultaneously. The simultaneous execution of two or more instructions on a multiple processor system is called multi-processing or parallel processing.

73.4.2.3 The operating system

Multi-tasking would be impossible without the operating system. A serial batch (or single-stream) operating system supports one program or routine at a time. A multi-programming operating system manages the concurrent execution of multiple tasks on a single processor by switching the processor’s attention from task to task. A time-shared operating system manages concurrent execution by assigning the processor to the active task for a brief time slice before moving on to the next task. Multi-processing systems manage the allocation of multiple concurrent or simultaneous tasks to multiple processors.

The operating system routine that manages the processor’s time is called the dispatcher. The dispatcher is responsible for managing the tasks that are already in memory. The operating system’s queuing and scheduling routines manage pending tasks until the memory and processor resources needed to execute them are available.

Multi-tasking implies multiple tasks in memory and executing. (Generally, only key portions of active programs are physically loaded into memory.) Multiple tasks sharing memory implies, in turn, a need for memory management and memory protection. Common memory management techniques include virtual memory, continuous memory allocation, dynamic memory management, fixed partition memory management, and roll-in/roll-out schemes. The purpose of resource allocation is to prevent (or resolve) the deadlocks that can occur when two concurrent tasks request the same resource (e.g., a peripheral or a record) at the same time.

73.4.2.4 Interrupt handling

On many real-time systems, the external event that triggers a change in state generates an interrupt. An interrupt is an electronic signal that causes the computer to stop what it is doing and activate one of the operating system’s interrupt handling routines. The operating system responds to the interrupt signal by activating the routine associated with the particular change in state.

When planning an event-driven real-time system, the designer must specify the status and nature of each interrupt, including the associated state, the address (or name) of the task to be given control, related warnings or error messages, appropriate corrective actions, and so on. After the interrupt is processed, the system must be restored to its original (or pre-interrupt) state. Procedures must also be developed to deal with deviations and/or unexpected actions or behaviors and to log the time, date, precipitating event, and so on for all interrupts. Because interrupts are asynchronous events, the system must also incorporate procedures to deal with concurrent and simultaneous interrupts.

73.4.2.5 Task synchronization and task sequencing

Given the asynchronous nature of real-time events and the need for rapid response, task synchronization and task sequencing are important issues. On many systems, when an interrupt occurs the information needed to activate the associated task is placed on a stack or a queue (Chapter 43). If the various tasks (or events) carry significantly different priorities, however, it may be necessary to implement a prioritization scheme (perhaps in the dispatcher) to ensure that the interrupts are processed in the appropriate order. Additionally, some tasks might be linked; for example, it might be necessary to interrupt task A to perform task B because A depends on B.

73.4.2.6 Event monitoring

Generally, a log is maintained listing (for each real-time event) the preceding event(s), the following event(s), any dependency relationships between the events, any associations among the events (e.g., merging, diverging, converging), any special requirements (e.g., recursive loops, repetitive loops), and any data required or generated by the event. One use for the data generated by event monitoring is establishing the precise state of the system in the event of system failure. State transition diagrams (Chapter 30) are often used to plan and/or document event monitoring.

73.4.2.7 Real-time languages

Such general-purpose third generation languages as C and Pascal have been used to develop real-time systems. Real-time languages (such as Modula-2 and ADA) are preferred, however, because they incorporate embedded real-time features to concurrently handle asynchronous events, an automatic debugger, and such real-time oriented functions as on-line testing and on- line execution simulation.

73.4.2.8 Real-time databases

Such features as concurrency control, locking, and time stamps are extremely important in real-time system database design. Concurrency control synchronizes the database and ensures that all copies of a given file contain the same version of the available information. Locking prevents a user from updating or modifying a record while another user is accessing that record. Time stamps allow the system to monitor the access or processing status of a record.

73.4.3 Developing a real-time system

Developing a real-time system is much like developing any system, and many of the tools described in Parts II, IV, V, and VI are used. This section outlines some parameters that are unique to real-time systems.

Special attention must be paid to time constraints, events, and other performance factors. Also, the analyst must carefully examine the relationships between the system and its input and output operations, clearly identifying the event that triggers each data movement or change in state.

Performance issues must be investigated thoroughly, too. Workload performance analysis focuses on such criteria as throughput, response time, turnaround time, the frequency and size of transactions, and regular and peak time workloads. System performance analysis focuses on such criteria as processing speed in MIPS (millions of instruction per second) or MFLOPS (millions of floating point operations per second), information access time, data transfer rate, instruction execution time, and so on. Other key performance criteria include mean time between failures (MTBF), the nature and frequency of interrupts, the signals and requirements associated with triggering each event, and so on.

A real-time task can be viewed as a program or routine that is executed in response to an event. System control usually depends on events, the inputs to a particular task, and the current state of the system. Consequently, the designer must decide how to synchronize the tasks and must determine the priority of each task. Given the task synchronization rules and priorities, the relevant triggers, inputs, and states for each task are studied. Finally, a table listing each task, its trigger(s), its related inputs, its preceding and following states, and other control criteria is developed as a logical map for system design. Often, one or more state transition diagrams (Chapter 30) are prepared during this stage.

Monitors are programs or hardware devices that detect and report a real-time system’s processing and/or input/output activities. Monitors are used to control, adjust, and/or correct unexpected behaviors in a real-time system. The process of collecting the information needed to define the monitors is called demand analysis. Program profilers are used to track the resources requested and services utilized by a particular program as it executes and, thus, supports utilization analysis. Procedures for incorporating monitors and program profilers into the system must be developed during real-time system design.

73.5 Key terms

Association —

A link between two or more events defined by precedence requirements and similar conditions.

Asynchronous event —

An event that can occur at any time and is not synchronized with other events.

Concurrency —

A measure of the number of tasks a system can process concurrently.

Concurrency control —

A database feature that synchronizes the database and ensures that all copies of a given file contain the same version of the available information.

Concurrent —

Within the same time period.

Convergence —

A process in which several preceding events are combined to form one following event; the opposite of divergence.

Deadlock —

A situation that occurs when two tasks each control a resource needed by the other and neither task is willing to relinquish control.

Dependency —

A relationship in which the implementation of the following event(s) depends on the completion of the preceding event(s).

Dispatcher —

The operating system routine that manages the processor’s time.

Divergence —

A process in which one preceding event is separated into several following events.

Event —

An occurrence.

Event-driven —

A system that responds to events.

Fault tolerant computer —

A computer that incorporates redundant circuits and components to improve reliability.

Interrupt —

An electronic signal that causes the computer to stop what it is doing and activate one of the operating system’s interrupt handling routines; generally, the information needed to restore the system to its pre-interrupt state is captured by hardware as part of the interrupt process.

Locking —

A technique that prevents a user from updating or modifying a record while another user is accessing that record.

Merge —

See convergence.

Monitor —

A program or hardware device that detects and reports a real-time system’s processing and/or input/output activities.

Multi-processing (parallel processing) —

The simultaneous execution of two or more instructions on a multiple processor system.

Multi-programming —

Concurrently executing multiple tasks on a single processor by switching the processor’s attention from task to task.

Multi-tasking —

Concurrently or simultaneously processing several tasks on a single computer.

Program profiler —

A routine or device that tracks the resources requested and services utilized by a particular program as it executes.

Real-time system —

An information system that responds to events as they occur and (typically) provides feedback to influence or control those events.

Redundancy —

The duplication of components to provide backup in case of failure.

Reliability —

A measure of the likelihood that a system or a component will function properly over time; often measured by the mean time between failures.

Response time —

The elapsed time between a request for service and the delivery of that service.

Simultaneous —

At the same instant.

State —

A condition; often, the complete set of attribute values and settings that describes the precise condition of a computer system at a specific instant in time.

System performance analysis —

A type of analysis that focuses on such criteria as processing speed, information access time, data transfer rate, instruction execution time, and so on.

Task —

A single program or routine in memory and available to be executed.

Time-sharing —

Concurrently executing multiple tasks by assigning the processor to a given task for a brief time slice before moving on to the next task.

Workload performance analysis —

A type of analysis that focuses on such criteria as throughput, response time, turnaround time, the frequency and size of transactions, and regular and peak time workloads.

73.6 Software

Real-time programming languages include Modula-2 and ADA.

73.7 References

1.  Aho, A. V., Sethi, R., and Ullman, J. D., Compilers: Principles, Techniques and Tools, Addison-Wesley, Reading, MA, 1986.

2.  Booch, G., Software Engineering with ADA, Benjamin/Cummings, Menlo Park, CA, 1983.

3.  Burch, J. G., Systems Analysis, Design, and Implementation, Boyd & Fraser, Danvers, MA, 1992.

4.  Burd, S. D., Systems Architecture: Hardware and Software in Business Information Systems, Boyd & Fraser, Danvers, MA, 1994.

5.  Davis, W. S., Operating Systems: A Systematic View, 4th ed., Benjamin/ Cummings, Redwood City, CA, 1992.

6.  Dewitz, S. D., Systems Analysis and Design and the Transition to Objects, McGraw-Hill, New York, 1996.

7.  Foster, C. C., Real-Time Programming—Neglected Topics, Addison-Wesley, Reading, MA, 1981.

8.  Gomaa, H., Software development of real-time systems, CACM, 27(9), 938, 1984.

9.  Hinden, H. J. and Rauch-Hinden, W.B., 1984. Real-time systems, Electron. Design, XX, 288, 1983.

10.  Keyes, J., Software Engineering Productivity Handbook, McGraw-Hill, New York, 1993.

11.  Mellichamp, D. A., Real-Time Computing, Van Nostrand Reinhold, New York, 1983.

12.  Norman, R. J., Object-Oriented Systems Analysis and Design, Prentice-Hall, Upper Saddle River, NJ, 1996.

13.  Pressman, R. S., Software Engineering: A Practitioner’s Approach, 2nd ed., McGraw-Hill, New York, 1987.

14.  Savitsky, S., Real-Time Multiprocessor Systems, Van Nostrand Reinhold, New York, 1985.

15.  Steusloff, H. U., Advanced real-time languages for distributed industrial process control, Computer, 17(2), 37, 1984.