Overview

This article is part 2 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.

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.

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.

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.

$Utilization = \sum_{i=1}^{n}\frac{E_i}{P_i}$

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).

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 created by the EIT-Digital University in Turku, Finland as part of the on-campus course on Real-Time Systems given in their Embedded Systems Master’s curriculum.