Task Scheduler in Real-time OSes (Part 1)
Define OS Scheduling based on methodologies such as Timeslice/Priority
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.
Read Part 2: Task Scheduler in RTOS
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 ECUs1 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
- 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.
- Execution time (): how long the job is
- Deadline (D): the deadline of a task
Example of Task with , on x-axis of timeslice .
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 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.
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.