A key job of the operating system (OS) is to schedule runnable tasks. The POSIX standard states that a POSIX-complaint OS must provide (at least) three scheduling policies. A scheduling policy is really the scheduling algorithm used by the OS to schedule tasks. In this book, we will not delve into such details, but we do need the application developer to be aware of the scheduling policies available. These are as follows:

• SCHED_FIFO
• SCHED_RR
• SCHED_OTHER (also known as SCHED_NORMAL)

Our discussions on this, naturally, will be solely with regard to the Linux OS.

The first important thing to understand is that the vanilla Linux OS is not an RTOS; it does not support hard real-time and is classified as a General Purpose Operating System (GPOS), like the others—Unix, Windows, and macOS. 

Linux, though a GPOS, easily performs as a soft real-time system. Indeed, its high performance characteristics bring it close to being a firm real-time system. Thus, the predominant use of the Linux OS in consumer electronics (and enterprise) products is not at all surprising.

Next, the first two scheduling policies that we mentioned—SCHED_FIFO and SCHED_RR —are Linux's soft real-time scheduling policies. The SCHED_OTHER (also known as SCHED_NORMAL) policy is the non-real-time scheduling policy and is always the default one. The SCHED_OTHER policy is implemented on modern Linux kernels as the Completely Fair Scheduler (CFS); it's an implementation whose primary design goals are to provide overall high system throughput and fairness to every runnable task (thread), ensuring that a thread does not starve. This is quite the anti-thesis of a real-time policy algorithm, whose overriding motivation is priority of the thread.

For both the SCHED_FIFO and SCHED_RR soft real-time policies, the Linux OS specifies a priority range. This range is from 1 to 99, where 1 is the lowest real-time priority and 99 is the highest. The soft real-time scheduling policy design on Linux follows what is known as fixed priority preemptive scheduling, and this is important to understand. Fixed priority implies that the application decides and fixes the thread priority (and can change it); the OS does not. Preemption is the act of the OS snatching away the CPU from the running thread, relegating it back to its run queue, and context switching to another thread. The precise preemptive semantics with regard to the scheduling policies will be covered next.

We shall now briefly describe, in real-world terms, what it means to be running under these differing scheduling policies.

A running SCHED_FIFO thread can only be preempted under the following three conditions:

• It (in)voluntarily yields the processor (technically, it moves out from the R state). This happens when a task issues a blocking call or invokes a system call like sched_yield(2).
• It stops or dies.
• A higher priority real-time task becomes runnable.

This is the key point to understand: a SCHED_FIFO task is aggressive; it runs with infinite timeslice, and unless it blocks (or is stopped or killed), will continue to run on the processor indefinitely. However, the moment a higher priority thread becomes runnable (state R, entering the run queue), it will be preempted in favor of this thread.

SCHED_RR behavior is nearly identical to that of SCHED_FIFO, except that:

• It has a finite timeslice, and thus has an additional scenario under which it can be preempted: when its timeslice expires.
• When preempted, the task is moved to the tail of the run queue for its priority level, ensuring that all SCHED_RR tasks at the same priority level are executed in turn (hence its name round robin).

Notice that on an RTOS the scheduling algorithm is simple, as all it really has to do is implement this semantic: the highest priority runnable thread must be the thread that is running.

All threads run under the SCHED_OTHER (or SCHED_NORMAL) scheduling policy by default. It is a decidedly non-real-time policy, the emphasis being on fairness and overall throughput. Its implementation from Linux kernel version 2.6.0 up until 2.6.22 (inclusive) was via the so-called O(1) scheduler; from 2.6.23 onward, a further improved algorithm called the Completely Fair Scheduler (CFS) implements this scheduling policy (actually a scheduling class). Refer to the following table for more information: