Real Time

Depends on	Process Scheduling

In a desktop computer it is often possible to ‘stretch’ time to work out the right answer to a problem. In a real-time system – such as one flying an aeroplane – it is essential not only to get the right answer but to get it before it is too late! This puts a particular burden on the relevant operating system if it has to schedule multiple – potentially ‘independent’ – tasks, all with real-time constraints. This is typical of many embedded systems – systems with a computer working on a dedicated task.

Real-time requirements are sometimes further classified:

• Hard real-time systems may fail catastrophically if they fail to meet their timing constraints. These may be safety-critical systems. Note, for example, the current interest in self-driving vehicles.
  Such systems can be specialist and very challenging.
• Soft real-time systems will attempt to meet a performance requirement but will not regard that as critical. There may also be some ‘elasticity’ in the system timing. Consider, for example, a video or audio player. Clearly there is a real-time constraint in that the input needs to be fetched at the same rate as the output is played (on average) and the output rate is fixed. The usual approach would be to fetch extra data into a local buffer and ‘play’ from there. The delay between a particular image being fetched and it appearing will vary but the target is that the buffer is never entirely empty. Some network delays (for example) can be accommodated. In the worst case, if there is a performance ‘glitch’, no one dies!

Best-effort vs. worst case

An important difference between general-purpose and real-time design is what is optimised for. In a general purpose system the average performance is most important. Statistical techniques are widely used to give high performance in ‘typical’ circumstances. A good example is caching in its various forms, which tries to serve ‘most’ requests quickly. In a real-time system this is less important than ensuring that the worst case constraint is met.

Average cases are less important. Predictability is important. In individual functions latency can be more important than simple performance; in certain tasks the time from input (e.g. the pilot adjusts the controls) to output (the aeroplanes control surfaces and engines react) is the most important factor. Not everything is equally important (e.g. the weather radar display update can safely wait another 100 ms).

Staying predictable

The constraints may mean (for example) not using a hardware memory cache, preferring to manage the memory explicitly in software; this typically means not being subject to the potential (highly unpredictable) delays involved in paging from disk! This is highly likely to compromise the average performance, compared to an interactive system, but a real-time system needs to have time to spare, anyway!

Real-time scheduler

In the following, “task” is used to avoid saying “thread or process” a lot.

Probably the biggest impact of real time requirements at OS-level is on the scheduler. There are some fundamental considerations which are of primary importance:

• All jobs must be completed with time to spare: i.e. the total processing requirement per second must be less than the processor can actually do.
  An interactive system will often try and do as much as possible whilst runnable jobs exist.
• Latency requirements vary from task to task process so priority is very important.

This steers the scheduling policy …

• … away from time-slicing. Why take time/effort swapping jobs when you know the task will block soon anyway?
• … towards pre-emption. When a high-priority task becomes ready to run, make it displace a lower priority task which is currently running. In this manner the latency to the completion (until they block again) of the high-priority tasks is minimised at the expense of the low-priority tasks.
• … to keep the ready queue sorted in priority order rather than some simple ‘round robin’ manner. A pre-empted task would thus be ‘pushed’ onto the front of the queue, rather than added to the back.

The figure shows the highest priority task runs immediately it is required and a high priority task may not be too delayed, although it is pre-empted at one point. The lowest priority task only gets processor time when there is nothing else ready. When everything useful is completed, the processor idles.

The approach outlined above may make some slight change to the process state transition diagram, since a running process can be pre-empted when a formerly blocked, high-priority process is suddenly unblocked, providing another way of pre-empting a running process.

Reliability

Many real-time systems are embedded systems. An embedded system may contain other features to ensure it stays working, such as crash-resistance. One such measure is the watchdog reset. Another – particularly in life-critical applications such as flying aeroplanes – is multiple redundancy. Having several computers can guard against one failing, but introduces other problems such as synchronisation, since no two independent computers will be running at exactly the same speed.

There is not really the space or the scope (perhaps fortunately?!) to go into details here. There is plenty more reading matter ‘out there’ if you’re interested: here’s one example. Plus, frequently informative on many aspects of real world reliability problems, try comp.risks.

Examples

The Real-Time Operating System (RTOS) is a specialist field of O.S. development which endeavours to meet these challenges. Without being partisan, here are a couple of examples of real time operating systems:

• eCos is a free, open-source, real-time OS probably primarily used on small-scale embedded systems.
• QNX is a commercial, Unix-like, real-time OS with high penetration of (e.g. ) the automotive industry.
  (The word “telematics” crops up quite a lot.)

---

Apollo Guidance Computer

Once upon a time, people used to fly to the Moon. (Computers were not quite so ‘pocket-sized’ in those days, though.) The Apollo Guidance Computer is an interesting case-study of an early real-time system and generated some interesting observations about priority scheduling.

There’s a nice video here. (9 mins.)

---

Also refer to:	Operating System Concepts, 10th Edition: Chapter 5.6, pages 227-234

Context Dependencies Dependants

Max. number:

Max. distance:

Next

Articles on Concepts

About this resource • Application Binary Interface (ABI) • Arrays • Atomicity • Boot • Cache • Cacheability • Caching • Concepts • Containers • Context • Context Switching • Deadlock • Direct Memory Access (DMA) • Environment Variables • Exceptions • File Attributes • Fragmentation • Hypervisor • Interrupts • Operation Ordering • PATH • Pointers • Process Scheduling • Processes • Processor Privilege • Queues • Real Time • Reentrancy • Relocatable Code • Spooling and Buffering • Synchronisation • Thrashing • Threads • Virtual Memory • Virtualisation

Articles on Major concepts

Cache • Cacheability • Concepts • Context • Direct Memory Access (DMA) • Exceptions • Hypervisor • Metadata • Process Scheduling • Processor Privilege • Real Time • Reentrancy • Synchronisation • Virtualisation

Articles on Processes

About this resource • Atomicity • Containers • Context • Context Switching • Daemons • Fork Unix • Hypervisor • Idle • Interprocess Communication • Multi Threading • Mutual exclusion • Pipes • Pointer Arithmetic • Process Control Block (PCB) • Process Priority • Process Scheduling • Process States • Processes • Queues • Queues Extra • Race Conditions • Real Time • Resources • Scheduler • Signal and Wait • Sleep • Starvation • Synchronisation • Thrashing • Threads • Unix Signals