How do Real Time Operating Systems work?

Question

I mean how and why are realtime OSes able to meet deadlines without ever missing them? Or is this just a myth (that they do not miss deadlines)? How are they different from any regular OS and what prevents a regular OS from being an RTOS?

Solution 1

Meeting deadlines is a function of the application you write. The RTOS simply provides facilities that help you with meeting deadlines. You could also program on "bare metal" (w/o a RTOS) in a big main loop and meet you deadlines.

Also keep in mind that unlike a more general purpose OS, an RTOS has a very limited set of tasks and processes running.

Some of the facilities an RTOS provide:

• Priority-based Scheduler
• System Clock interrupt routine
• Deterministic behavior

Priority-based Scheduler

Most RTOS have between 32 and 256 possible priorities for individual tasks/processes. The scheduler will run the task with the highest priority. When a running task gives up the CPU, the next highest priority task runs, and so on...

The highest priority task in the system will have the CPU until:

• it runs to completion (i.e. it voluntarily give up the CPU)
• a higher priority task is made ready, in which case the original task is pre-empted by the new (higher priority) task.

As a developer, it is your job to assign the task priorities such that your deadlines will be met.

System Clock Interrupt routines

The RTOS will typically provide some sort of system clock (anywhere from 500 uS to 100ms) that allows you to perform time-sensitive operations. If you have a 1ms system clock, and you need to do a task every 50ms, there is usually an API that allows you to say "In 50ms, wake me up". At that point, the task would be sleeping until the RTOS wakes it up.

Note that just being woken up does not insure you will run exactly at that time. It depends on the priority. If a task with a higher priority is currently running, you could be delayed.

Deterministic Behavior

The RTOS goes to great length to ensure that whether you have 10 tasks, or 100 tasks, it does not take any longer to switch context, determine what the next highest priority task is, etc...

In general, the RTOS operation tries to be O(1).

One of the prime areas for deterministic behavior in an RTOS is the interrupt handling. When an interrupt line is signaled, the RTOS immediately switches to the correct Interrupt Service Routine and handles the interrupt without delay (regardless of the priority of any task currently running).

Note that most hardware-specific ISRs would be written by the developers on the project. The RTOS might already provide ISRs for serial ports, system clock, maybe networking hardware but anything specialized (pacemaker signals, actuators, etc...) would not be part of the RTOS.

This is a gross generalization and as with everything else, there is a large variety of RTOS implementations. Some RTOS do things differently, but the description above should be applicable to a large portion of existing RTOSes.

Solution 2

In RTOSes the most critical parameters which should be taken care of are lower latencies and time determinism. Which it pleasantly does by following certain policies and tricks.

Whereas in GPOSes, along with acceptable latencies the critical parameters is high throughput. you cannot count on GPOS for time determinism.

RTOSes have tasks which are much lighter than processes/threads in GPOS.

Solution 3

Your RTOS is designed in such a way that it can guarantee timings for important events, like hardware interrupt handling and waking up sleeping processes exactly when they need to be.

This exact timing allows the programmer to be sure that his (say) pacemaker is going to output a pulse exactly when it needs to, not a few tens of milliseconds later because the OS was busy with another inefficient task.

It's usually a much simpler OS than a fully-fledged Linux or Windows, simply because it's easier to analyse and predict the behaviour of simple code. There is nothing stopping a fully-fledged OS like Linux being used in a RTOS environment, and it has RTOS extensions. Because of the complexity of the code base it will not be able to guarantee its timings down to as small-a scale as a smaller OS.

The RTOS scheduler is also more strict than a general purpose scheduler. It's important to know the scheduler isn't going to change your task priority because you've been running a long time and don't have any interactive users. Most OS would reduce internal the priority of this type of process to favour short-term interactive programs where the interface should not be seen to lag.

Solution 4

It is not that they are able to meet deadlines, it is rather that they have deadlines fixed whereas in a regular OS there is no such deadline.

In a regular OS the task scheduler is not really strict. That is the processor will execute so many instructions per second, but it may occasionally not do so. For example a task might be pre-empted to allow a higher priority one to execute (and may be for longer time). In RTOS the processor will always execute the same number of tasks.

Additionally there is usually a time limit for tasks to completed after which a failure is reported. This does not happen in regular OS.

Obviously there is lot more detail to explain, but the above are two of the important design aspects that are used in RTOS.

Solution 5

You might find it helpful to read the source of a typical RTOS. There are several open-source examples out there, and the following yielded links in a little bit of quick searching:

• FreeRTOS
• eCos

A commercial RTOS that is well documented, available in source code form, and easy to work with is µC/OS-II. It has a very permissive license for educational use, and (a mildly out of date version of) its source can be had bound into a book describing its theory of operation using the actual implementation as example code. The book is MicroC OS II: The Real Time Kernel by Jean Labrosse.

I have used µC/OS-II in several projects over the years, and can recommend it.

View more solutions

Comments

[TJ Seabrooks]

It's also important to notice the difference between a soft' real time system and a 'hard' real time system.

[Adam Hawes]

A RTOS makes very strict guarantees on things that are important, like interrupt servicing times, task switching latency, etc Real-time applications are NOT possible without a proper RTOS.

[Tamas Czinege]

It's not just scheduling - the OS must make sure that no random things kick in like garbage collection or memory address space defragmentation, so that you know that malloc() will always return without a delay, so (for example) the aeroplane the autopilot is controlling will not crash.

[mouviciel]

I am just speaking of what I have seen. And more than often, realtime problems are solved by huge CPU frequencies and a lot of time margin.

[Sandeep Datta]

"This task will run to completion" sounds like Windows 3.1! Then you mean RTOSes are non preemptive?

[Sandeep Datta]

"Basically, you have to code each "task" in the RTOS such that they will terminate in a finite time" - then its the application that should be called realtime and not the OS.

[Sandeep Datta]

What happens when a task runs out of time?

[Benoit]

No, if you are the highest priority you run until you voluntarily give up, OR a higher priority task than you becomes ready, at which time the (old) high priority gets pre-empted. I'll clarify in the main text. Thanks!

[Spence]

the task is forcibly preempted and restarted on its next time slice. A good RTOS would raise an error or notify that this had occured.

[Sandeep Datta]

"If you really want to be deterministic poll everything." - What if you miss an event of higher priority inbetween poll cycles? Will this not make the OS response non real time for those events?

[robert.berger]

Of course it will, but you did your analysis and made sure that all the events from outside of the OS come within certain time boundaries (something like a sporadic server for your inputs). In a fault condition (cracked cable) you should throw away the events anyhow. What you make sure by polling and not using any interrupts is, that the fact the you use interrupt is not anymore degrading determinism.

[Sandeep Datta]

Are you trying to say that this is effectively a trade off between latency and determinism? IMO the "events at well defined boundaries" model fails when you have an event hierarchy (i.e. prioritized events). There is no reason why a totally unrelated event should have to respect the time boundaries of a low priority (LP) event/task. The LP task needs to be preempted even if the HP event occurs at t0+dt. Where dt is an infinitesimally small period of time and t0 is the time when the LP task started.

[robert.berger]

You first need to define what (hard) real-time means for you and your system. Do you need (hard) real-time? 1) deterministic (event+time), which strictly speaking means no interrupts. 2) best effort - not so deterministic anymore, most of the times you will have low latency. But what if this unexpected thing happens where you suddenly have all this noise on one of your interrupt lines together with the timer tick interrupt and some user pressed some button which causes another INT - while the system is executing code from cache - you are not time deterministic anymore - maybe low latency?

[Sandeep Datta]

Noise on interrupt lines sounds like a hardware problem - use a H/W low pass filter (LPF). If that is not an option then how about selectively masking the noisy interrupt line (for example until the ISR returns) instead of disabling all interrupts? I think when you choose to say that you will have prioritized events you are effectively declaring that in the presence of High priority tasks the tasks with lower priorities do not have to be real time.

[robert.berger]

Sometimes it's not as easy as filtering out noise with a low pass filter, like when a sensor or cable are broken and sending funny stuff. Also I would no go for polling without interrupts because of this issue. In case the low priority tasks don't have real-time requirements we are not talking about a deterministic hard real-time system anymore. Anyhow, just image a happy real-time system with only a timer interrupt, not even cache. Even this is strictly speaking non time deterministic due to the drift of the crystal from which the timer tick is derived. Add cache and determinism goes away.

[Sandeep Datta]

Ok I think the difference of opinion stems from the fact that I am making an implicit assumption here that it's impossible to guarantee hard real time deadlines in a system with purely random events hence RTOSes are always "best effort" (IMO). Now if we are talking about crystal drift then the main clock generator (used by the microprocessor) is also susceptible which implies polling cannot be guaranteed to be deterministic either.

[Sandeep Datta]

"...which passes some test suites to prove that it does what it's supposed to do" my thoughts exactly. I agree with your conclusion!

[vorou]

Thanks for the great answer. Could you please clarify how System Clock Interrupt routines behavior you described is specific to RTOS? I mean, how is it different from a standard timer API each general-purpose OS has?