Editing Real-time operating system (section)

==Scheduling==
In typical designs, a task has three states:
# Running (executing on the CPU);
# Ready (ready to be executed);
# Blocked (waiting for an event, I/O for example).

Most tasks are blocked or ready most of the time because generally only one task can run at a time per [[Central processing unit|CPU]] [[Multi-core processor|core]]. The number of items in the ready queue can vary greatly, depending on the number of tasks the system needs to perform and the type of scheduler that the system uses. On simpler non-preemptive but still multitasking systems, a task has to give up its time on the CPU to other tasks, which can cause the ready queue to have a greater number of overall tasks in the ready to be executed state ([[resource starvation]]).

Usually, the data structure of the ready list in the scheduler is designed to minimize the worst-case length of time spent in the scheduler's critical section, during which preemption is inhibited, and, in some cases, all interrupts are disabled, but the choice of data structure depends also on the maximum number of tasks that can be on the ready list.

If there are never more than a few tasks on the ready list, then a [[doubly linked list]] of ready tasks is likely optimal. If the ready list usually contains only a few tasks but occasionally contains more, then the list should be sorted by priority, so that finding the highest priority task to run does not require traversing the list. Instead, inserting a task requires walking the list.

During this search, preemption should not be inhibited. Long critical sections should be divided into smaller pieces. If an interrupt occurs that makes a high priority task ready during the insertion of a low priority task, that high priority task can be inserted and run immediately before the low priority task is inserted.

The critical response time, sometimes called the flyback time, is the time it takes to queue a new ready task and restore the state of the highest priority task to running. In a well-designed RTOS, readying a new task will take 3 to 20 instructions per ready-queue entry, and restoration of the highest-priority ready task will take 5 to 30 instructions.

In advanced systems, real-time tasks share computing resources with many non-real-time tasks, and the ready list can be arbitrarily long. In such systems, a scheduler ready list implemented as a linked list would be inadequate.

===Algorithms===
Some commonly used RTOS scheduling algorithms are:<ref>{{cite web|url=https://www.embedded.com/programming-embedded-systems-rtos-what-is-real-time/|title=Programming embedded systems: RTOS – what is real-time?|date=23 May 2023|website=Embedded.com|author-first=Miro|author-last=Samek|access-date=13 September 2023}}</ref>
* [[Cooperative multitasking|Cooperative scheduling]]
* [[Preemption (computing)|Preemptive scheduling]]
** [[Rate-monotonic scheduling]]
** [[Round-robin scheduling]]
** [[Fixed-priority pre-emptive scheduling]], an implementation of [[time slice|preemptive time slicing]]
** Fixed-priority scheduling with deferred preemption
** Fixed-priority non-preemptive scheduling
** Critical section preemptive scheduling
** Static-time scheduling
* [[Earliest deadline first scheduling|Earliest deadline first]] approach
* [[Stochastic]] [[directed graph|digraphs]] with [[thread (computer science)|multi-threaded]] [[tree traversal|graph traversal]]