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.

Read Part 1: Task Scheduler in RTOS

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.

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.

Task ( $T$ )	Period ( $P$ )	Execution Time ( $E_t$ )	Deadline ( $D$ )
$T_1$	3	1	3
$T_2$	4	1	4
$T_3$	10	2	10

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.

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

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

On the first line of Task 1, the timer interrupts the system at time 0 and $T_1$ $T_{1}$ is selected. The job of $T_1$ $T_{1}$ is then executed through out its $E_{t1}$ $E_{t 1}$ and come to a stop at $t=1$ $t = 1$ then the next task is up.
- Side note: similarly the second and third lines of Task 2 and 3 respectively.
Since $T_3$ $T_{3}$ start-of-task is $t=1$ $t = 1$ , it takes control next.
- Side note: there is no concept of priority yet, the only determinants are which Task available and ready.
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$ .

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.