Multi-Thread scheduling in real-time operating systems (RTOS)

Real-time operating systems (RTOS) play an important role in ensuring that embedded systems meet strict timing constraints. These systems are employed in a wide range of applications, which include automotive control systems, medical devices, aerospace, and industrial automation, etc. Here, the timely and deterministic execution of tasks is paramount. One of the key features that make RTOS suitable for these applications is their multi-thread scheduling mechanism.

Real-time scheduling

Real-time scheduling in RTOS involves the management and execution of multiple threads (also known as tasks) with the objective of ensuring that tasks meet their deadlines consistently. Each task in the system has associated properties, including priority, execution time, and periodicityHow often the task recurs, which the scheduler uses to determine the order in which tasks are executed. The primary goal of real-time scheduling is to minimize task latencies and guarantee the completion of critical tasks within their specified time constraints.

Before exploring the different scheduling algorithms, it is important to understand the fundamental characteristics of a single task, namely:

Period: The period of the task is the time between two subsequent occurrences of the task. It quantifies how often we can expect the task to occur.
Deadlines: The deadline is the time within which each task that must be executed. If a task is not completed within the deadline, it is considered a failure.
Execution time: The execution time is a measure of how long does it take to fully process as task.

Scheduling algorithms

RTOS systems implement various scheduling algorithms to manage the execution of tasks. Let’s look at some of the most commonly used scheduling algorithms.

Fixed-priority preemptive scheduling

In this approach, each task is assigned a fixed priority level, and the scheduler selects the highest priority task ready to run. Tasks with higher priority preempt tasks with lower priority, ensuring that higher priority tasks are executed without delay. Fixed-priority scheduling is simple and suitable for systems where task priorities remain constant.

In the illustration above, we can see that as Task 2 has the highest priority, the scheduler abandons any other task it is processing to first cater to it. Only after Task 2 has been executed does the scheduler move on to the other tasks, according to the priority list.

Round-robin scheduling

Round-robin is a time-sharing scheduling algorithm where tasks are assigned a fixed time range. Each task runs for its allotted time, and if it isn’t completed within the range, it is moved to the back of the queue, allowing other tasks to execute. Round-robin is useful but may not be ideal for real-time systems with strict deadlines.

In the illustration above, we can see that Task 1 occurs most frequently, thus, it is given the highest priority. Task 2 comes next on the priority list, followed by Task 3. The scheduler always prioritizes Task 1, abandoning other tasks if Task 1 occurs. The other tasks are only processed after Task 1 is completed.

Earliest deadline first scheduling

Commonly known as EDF, this algorithm assigns priorities dynamically based on each task’s next deadline. The task with the earliest deadline is given the highest priority. EDF ensures that tasks with impending deadlines are executed first, but requires more complex scheduling algorithms.

In the illustration above, we can see that the task that has the closest deadlines is prioritized over other tasks. When Task 3 is being executed, Task 1 occurs, and because its deadline is closer, the scheduler abandons Task 3 to process Task 1 first. Thus, tasks with the shortest deadlines are mostly processed in one go, while tasks with very long deadlines are mostly processed in small chunks.

Selecting a scheduling algorithm

Choosing the right scheduling algorithm for an RTOS system depends on various factors:

Task characteristics: Consider the nature of the tasks, whether they are periodic, aperiodic, or sporadicThese tasks have a strict deadline and can reoccur at random instant.. Some algorithms, like rate-monotonic, are well-suited for periodic tasks, while others, like EDF, handle aperiodic tasks more effectively.
System requirements: Analyze the system’s real-time requirements, including deadlines, response times, and throughput. Ensure that the selected algorithm can meet these requirements.
Resource constraints: Assess the hardware resources available, such as CPU cores, memory, and I/O devices. Some algorithms may be more efficient in utilizing these resources than others.
Predictability: Different algorithms offer varying levels of predictability. Fixed-priority algorithms are generally more predictable, while dynamic algorithms like EDF offer better responsiveness but can be harder to analyze.
Complexity: Consider the complexity of the scheduling algorithm in relation to the available computing resources. Simpler algorithms are easier to implement and debug.

In addition to the scheduling algorithms introduced above, there are several other algorithms, such as cooperative scheduling, fixed-priority non-preemptive scheduling, critical section preemptive scheduling, and static time scheduling, etc. Each algorithm has its strengths and weaknesses, and deciding which one to use requires careful analysis of our system and the required outputs.

Conclusion

Multi-thread scheduling is a critical aspect of real-time operating systems, enabling the timely execution of tasks in applications where deterministic behavior is essential. Choosing the right scheduling algorithm is crucial to meet the system's real-time requirements. Careful consideration of task characteristics, system requirements, and available resources is essential when selecting the appropriate scheduling algorithm. Ultimately, the choice of scheduling algorithm should align with the specific needs and constraints of the embedded system, ensuring reliable and predictable performance.