Comparing real-time scheduling on the Linux kernel and an RTOS

Le Trung Thang

April 25, 2012

Le Trung ThangApril 25, 2012

By default, the Linux kernel build used in the many open source distributions is the normal/default kernel which doesn’t support real time scheduling. If an embedded developer wants to compare the scheduling policies of Linux to a real time operating system it is more useful to compare RTOS performance to a version of Linux that does have real-time features.

Fortunately, in addition to this default kernel, there is also available a Real-time kernel version that supports a real-time scheduling policy. In this article and in the code examples that are included, an effort is made to compare the real time operations of standard and real-time Linux with normal RTOS operation and evaluate the differences and similarities.

Normal Linux kernel vs RTOS
Normal Linux Kernel is a preemptive kernel but not real time, of course. In most multithreading environments (also called multitasking), a preemptive kernel allows the thread that has higher priority to receive longer time on the processor. And, conversely a lower priority thread will have less time with the processor.

However, in the normal kernel, no particular thread can monopolize the services of the resident processor all the time, no matter what its priority. So, programs will never hang up even if an arbitrary thread of the program goes into a “forever loop.”

Conversely, with almost any real time OS (such as FreeRTOS, Micrium uC/OS, and ThreadX), the kernel supports both preemption and real-time features. This means that a thread (also called a Task) can run forever when the following conditions are met:  (1) it is not blocked by synchronized resource (I/O block, Mutex, Semaphore…) or (2) it isn’t preempted by threads which may have equal or higher priority.

Figure 1 below shows the differences between the thread scheduling policy of normal Linux and the thread scheduling policy of a RTOS. In Figure 1, we assume that Thread1 has priority 2 and is higher than Thread2 which has priority 1.

In the RTOS scheduler, Thread1, with higher priority, always runs. Thread2 with lower priority never has a chance to run. By comparison the Normal Linux Scheduler does exactly the opposite, bringing up both Thread1 and Thread2 to run. Thread1 with higher priority will have longer time to run as compared with Thread2 which has lower priority.


Click on image to enlarge.

Figure 1. Real Time OS and normal Linux kernel scheduler

Real Time Linux kernel versus RTOS
In a real time kernel version of Linux, the scheduler has three (3) scheduling policies: Normal, FIFO and Round Robin.

In the Normal scheduling policy, a thread will be stopped (suspended) when one of three  conditions occurs:

1. It is blocked by an accessing synchronize resource (I/O block, mutex, semaphone...)
2. It volunteers to give up control of processor (call sleep() or pthread_yield()).
3. The Scheduler suspends the thread when its running time exhausted. The running time depends on each thread’s priority, as noted in Figure 1.

Normal real time scheduling policy is same as the default scheduling policy of normal kernel as described earlier.

With the FIFO scheduling policy, a thread will be stopped (suspended) when one of three conditions occurs:

1. It is blocked by accessing synchronize resource (I/O block, mutex, semaphore...)
2. It is preempted by a higher priority thread.
3. It volunteers to give up control of processor (call sleep() or pthread_yield()).

In the Round Robin scheduling policy, a thread will be stopped (suspended) when one in four following conditions occurs:

1. It is blocked by accessing synchronize resource (I/O block, mutex, semaphore...)
2. Or it is preempted by a higher priority thread.
3. Or it volunteers to give up control of processor (call sleep() or pthread_yield()).
4. Or its Time slice expired.

(Most RTOSes embed Round Robin scheduling policy in their scheduler.)

In Figure 2 below, we have four situations: First, Thread1 and Thread2 are of equal priority and run using the FIFO policy. Second, Thread1 and Thread2 are of equal priority and run on the Round Robin policy. Third, priority of Thread1 is higher priority of Thread2 and they run using the FIFO policy. Fourth, the priority of Thread1 is higher priority of Thread2 and they run using the Round Robin policy.

We also assume that Thread1 starts first, then Thread2 starts later and during running time, Thread1and Thread2 don’t make any system calls or are blocked by any synchronized resource (I/O, Mutex, Semaphore…). The result: the only differences that affect real time performance between the FIFO and Round Robin policies is when Thread1 and Thread2 have same priority.


Click on image to enlarge.

Figure 2. Real time Linux kernel scheduler

Conclusion: Viewed in this context, the typical RTOS scheduler is just a special case of real time Linux scheduler, or in other words, the RTOS scheduler is the real time Linux scheduler running with the Round Robin policy. (Some RTOSes allow configuration of the scheduler to run in a non-preemption mode. However this mode is seldom used.)

The examples included on Page 2 to 8 of this article show the different operational mechanisms of the real time Linux Scheduler in the context of this discussion. To download the source code for these examples, click here.

Important note:  On the following pages, all of the examples are only correct when the program runs in CPU single core and in root permission. To enforce a thread/process so that it only runs in a particular core of the processor, this can be done via the function sched_setaffinity( ) which sets the process CPU affinity. The programs were tested in Real time Linux kernel version 3.0.17.

If you want to install Real Time Linux and test it out yourself, more information is on Page 9, along with some references you may wish to consult.

(Editor’s Note: Any errors in the code listed on the following pages may have been introduced during the conversion process to ready it for online. If so, please contact me directly at bccole@acm.org.)

< Previous
Page 1 of 9
Next >

Loading comments...

Most Commented

  • Currently no items

Parts Search Datasheets.com

KNOWLEDGE CENTER