Overview

This article is part 1 of an overview series specifically about the Scheduler in a Real-time Operating System (RTOS). Examples of such systems can be found in almost anything from automotive application such as airbags, emergency breaks to avionics, and also infotainment, multi-media systems like video playback and QoS in web servers.

A real-time system is one in which the correctness of the system depends not only on the logical results of computation, but also on the time at which the results are generated.

This means that they both have to look at the output of the system and at the time at which the output was generated to determine whether an execution is successful.

Prerequisite

• Assuming you have foundation knowledge about
  • Programming, Big-O Notation, Algorithm, Interrupt and Computer Architecture
  • Real-time Operating System (RTOS) knowledge would make it more comprehensive

More about type of Real-time Systems coming later.

• (Optional) Schedule Simulation software SimSo which offer all Platform Compatibility (Python-powered)

Understand the needs for Scheduler

That said, in the heart of RTOS is the Scheduler and as the software complexity advances, the scheduling become more complex and thus expect extreme scheduling methods. For instance, there are only two Electronic Control Units (ECUs) in luxury class cars in mid-80s to control most of the Engine, Exhaust, etc. and by the time this article was written, the BMW 7-series models have as many as 150 ECUs¹ and average at 80 ECUs in total.

There are primarily two distinction of Real-time Systems, a missed deadline

• In Hard Real-time: is catastrophic
• In Soft Real-time: can lead to significant loss

One important concern in such a system like RTOS is the predictability of system behavior, meaning there should be no space for un-accountability, everything must be accountable and predictable. This is often achieved by either static or dynamic scheduling of Real-time tasks to meet their deadlines.

Taxonomy of Real-time Systems Scheduling Scheme. Classified by system type and scheduling mechanism

Task Structure

The Task Structure in RTOS includes the planning and the scheduling of workload on a processor and guarantees that the workload timeline is never violated. That workload can be quantified into discrete pieces, i.e. a Task. The functionality of a Task will be executed over and over again and thus differentiate between each iteration by an instance of a task, a.k.a. a Job.

A periodic task, which will release a new job every time units, is usually defined by

1. Period (P): time interval between releases of jobs in a task
   • Side Note: in reality, this interval is not necessarily constant with the presence of jitter between task transition.
2. Execution time ($E_t$): how long the job is
3. Deadline (D): the deadline of a task

Example of Task $T_1$ with $P=3$ , $E_t=1s$ on x-axis of timeslice $t=1$

Since there is a latest time at which a task must be completed, all tasks must never violate its deadline. Although, a deadline can be defined as absolute or relative in Hard Real-time or Soft Real-time respectively.

The longer the execution time, the more CPU resources are needed and if $E_t$ becomes too large, the CPU gets overloaded and it cannot handle all the tasks within the time limit.

Task Jitter

From the Task Structure, it is necessary to ensure the consistency between tasks and the amount of time it takes to complete current task and move on to the next task while not overloading the CPU. In reality, the transition is delayed due to various reasons: current task not completely finished, resource is not released and furthermore.

The total amount of time for such delay is called Task Jitter. Ideally, no jitter is desirable, and Hard real-time scheduling ensures that with extremely precise scheduling, leaving no wasted time between task transition or context switching.

NOTE: A Hard Real-time OS has less jitter than a Soft Real-time OS in general.

Example from this SO discussion clearly demonstrate the scenario where Task Jitter is inevitable.

A task should be started after 10ms, but for whatever reason, it is started after 15ms. In our example the jitter is 5ms.

All tasks would use no more than 100ms per scheduled time, a task that requires and uses 150ms would cause significant scheduling jitter.

Data Inconsistency

When the scheduler switches the CPU from executing one task to execute another, the resource from the current running task is released for another task, usually higher priority, to take control and this process is called context switching.

A Context Switch enables multiple tasks to share a single CPU by storing/restoring the state and context so that the execution can be preempted and resumed later without interrupting current progress.

The context/shared memory require special attention since switching tasks will inevitably causing data inconsistency where any task could alter the values or worse completely corrupt it. This is partly solved by creating a temporary lock on the resources, buffer snapshot or other mechanisms such as Semaphore (Signaling) or Mutual Exclusion (Locking) to maintain the correct values between tasks.

The O(1) Task Scheduler in Linux

Another reason for the needs of a Scheduler is efficiency when it comes to task priority, what instruction should run first which would require more computing resources to calculate the order. This is what the O(1) Task Scheduler introduced in Linux 2.6 trying to solve.

Essentially, there is a First-In-First-Out (FIFO) Active Runqueues and another FIFO Expired Runqueues, each with their own tasks and their priorties. All tasks are scheduled based on priorities inside the Active Runqueue and ran based on a pre-defined timeslice, and swap in the Tasks from Expired Runqueue once similar priorities from Active Runqueue is emptied.

The time it takes for the Linux Task Scheduler to find a task to execute depends not on the number of active tasks but instead on the number of priorities which is constant since there are only 140 priorities.

This makes the Linux 2.6 Task Scheduler an O(1) process because the time to schedule is both fixed and deterministic regardless of the number of active tasks.

Side note: Linux 2.6 Task Scheduler also supports preemption, that is prioritize when a higher-priority task is ready to run and re-schedules the lower-priority task. It also offers Dynamic Task Prioritization at runtime in addition with the Static Task Prioritization defined at compile time.

Static Scheduling

As mentioned, predictability for an RTOS is an important characteristic and Static Scheduling provides just that, the ability to schedule, optimize for the tasks at runtime with very low complexity. Although, this also means that every modification requires execution of the scheduling algorithm again.

Taxonomy of Static Scheduling binded with Priority Scheduling Scheme. Different methodologies include timeslice, periodicity, and priority

For Static Scheduling, all parameters of all the tasks are assumed knownn in which the Scheduler built a schedule based on this information. This characterstic makes it simplier to schedule by timeslice based on task arrival pattern since there will be no change throughout the schedules.

Despite being fixed at runtime, Static Scheduling can be implemented in Search Tree where the tree level is Time Unit and the tree depth is Period in the schedule.

Another applications can be Process Control System where all sensory and actuator data range of all tasks are known before hand.

Clock-Driven Scheduling

Clock-Driven Scheduling is a Static Scheduling mechanism that consist of the following characteristics:

• Schedule is created off-line at compile time
• Precedence is treated explicitly between tasks
• Scheduler operates when timer expires, i.e. Timer interrupt

Following is example of Clock-Driven Scheduling with a timeslice of Scheduling time $t=1s$ and three tasks $T_1$ , $T_2$ , $T_3$ scheduled at compile time.

Table of Schedule for 3 Tasks with their Execution Time, Period and Deadline

Before any scheduling, a concept of CPU Utilization is important since tasks with fast period and long execution time will occupy a large amount of CPU resources.

CPU Utilization is defined as the sum of all tasks’ Execution times $\sum E_i$ divided by their Periods $\sum P_i$. If the sum is greater than 1, then the system is guaranteed not feasible.

For this example of 3 Tasks, $U = \frac{1}{3} + \frac{1}{4} + \frac{1}{5} = 0.78$, and thus the system will not be unfeasible. It does not mean the system is feasible yet, this point will be discussed in the schedule plot.

On the following plot, the Scheduler generates and allocates Tasks with start-of-task one direction arrow ($\uparrow$) and end-of-task small dot (.) at the end of Execution Time (filled range).

Task $T_1$, $T_2$, $T_3$ and Processor $P_0$ plotted on Scheduling time ($t$) x-axis in 20 seconds. Plotted on SimSo Simulation

1. On the first line of Task 1, the timer interrupts the system at time 0 and $T_1$ is selected. The job of $T_1$ is then executed through out its $E_{t1}$ and come to a stop at $t=1$ then the next task is up.
   • Side Note: similarly the second and third lines of Task 2 and 3 respectively.
2. Since $T_3$ start-of-task is $t=1$, it takes control next.
   • Side Note: there is no concept of priority yet, the only determinants are which Task available and ready.
3. At time $t=3$, the Scheduler selects $T_1$ eventhough $T_2$ also starts at $t=3$. That is because Task 3 Period is $P_3=4$ and thus not executed until the next timeslice $t=4$.

From the schedule plot, it seems all tasks executed promptly and the schedule is feasible. However, as mentioned on CPU Utilization, because of task jitter between transition or some jobs occur simultaneously, the schedule will go wrong even if there are available CPU resources because the schedule is static.

Acknowledgement

This series is heavily influenced by a Coursera online course aiming for Master’s student created by the EIT-Digital University in Turku, Finland as part of the on-campus course on Real-Time Systems as given in their Embedded Systems master curriculum.