Real-Time System References and Reading Materials

Elec 494 Course on Real-Time Software - Spring, 1995
University of British Columbia
Dept. of Electrical Engineering
Donald W. Gillies - Professor


In a hard real-time system the correctness of a computation depends not only on the computed results but also on the time at which they are produced. A result produced on or after the deadline is typically useless.

A hard real-time system typically has many time constraints that must be satisfied simultaneously and periodically. Conventional operating systems and conventional data structures are optimized to meet one performance constraint - to optimize job throughput. Conventional performance techniques are nearly useless for hard real-time software.

Only the "core" of a hard real-time system must meet hard deadlines. The rest of the software is typically "soft" or "non" realtime. For example, consider the design of the Iridium satellite. The "core" tasks station keeping (flying precisely in the low earth orbit box) and keeping the solar panels pointed towards the sun. Phone calls would be nice to have but they aren't as mission-critical as these tasks. The "soft real-time tasks" are flash uploads, memory scrubbing (to repair radiation errors), heater maintenance, data checkpoint, power saving, etc. In particular, some activities like shifting users to different channels in order to power down a cluster of radio channels, and reorganizing memory to respond quickly to new phone-call or handoff arrivals, can run endlessly at very low priority. Every extra joule of power saved extends the satellite battery life and reduces the monthly subscription cost for the Iridium service, but there is no _hard target_ for power savings.

In a system with both hard and soft real-time tasks, the operating system and the software libraries must support the "core", and so a hard real-time OS and library must be used.

In the design of a highly concurrent system, care must be taken to minimize synchronization costs. A clever system designer will cast the software architecture into a form that requires no busy waiting and very few semaphores, if any. Operations that occur at similar frequencies or have a great deal of data flow or sharing will appear in the same task, to reduce context-switching overhead. Once the system is decomposed into tasks, the two most popular real-time system scheduling techniques are the cyclic executive and the static-priority preemptive kernel.

In a cyclic executive, a periodic schedule is planned as the software is designed. In the Boeing 777, a 200 ms schedule (called a super frame) was produced using combinatorial optimization and branch and bound programming. Resource contention was solved during this step so semaphores were not needed during execution. This 200 ms schedule is replayed endlessly onboard the airplane. In other systems (such as the MARS pathfinder), static priority preemptive scheduling is used to semi-dynamically select tasks for execution. These systems are easier to change (no replanning is necessary), and background and unused time is aggregated by the scheduler for more efficiency in soft real-time processing.

Some examples of software ideas found in real-time systems today are:

Data structures

System primitives

Few real-time operating systems today have more than 3 of these features. For example, UNIX and Windows-NT have none of these features.

In this reading list, we focus mainly on higher-level scheduling and macro performance analysis of real-time systems at the task level.

It often happens that the performance budgets are not met, and the application must be redesigned after the system is built. For ideas and testing techniques in performance-based application design and testing see the section on "Performance-Oriented Software Design".

In some cases, the engineers may write (very expensive) "negative instruction cycles" in order to meet all the deadlines. The book by Phillipe Laplante covers the topic of software tuning thoroughly.

I have been asked to identify a few seminal papers that could be read by someone just getting started in this field. In the reading list below, I have outlined these papers in BOLD FACE and I have provided a short description of why the paper is important to the field.

Journals and Conferences


Performance-Oriented Software Design

Real-Time System Architectures

Static-Priority Schedulability Utilization Theory

Static-Priority Engineering Critical Sections (Static-Priority Environment) Producer-Consumer Synchronization Testing Task Timing Analysis Tools

Memory Allocation

Fault Tolerance and Clock Synchronization I/O Case Study - CAN Case Study - Olympus Case Study - Bus Architectures Case Study - PLC's Misconceptions and Future of Real-Time Next Time