Deterministic Systems: Intro

Alex Egg,

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 an authentic RTOS system.

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 TinyOS), 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

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.

FIGURE HERE
http://www.embedded.com/design/operating-systems/4371651/Comparing-the-real-time-scheduling-policies-of-the-Linux-kernel-and-an-RTOS-

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.

Permalink: deterministic-systems-intro

Tags:

Last edited by Alex Egg, 2016-11-06 02:12:26
View Revision History