diff options
Diffstat (limited to '')
| -rw-r--r-- | ada_user/scheduling_concepts.rst | 488 |
1 files changed, 0 insertions, 488 deletions
diff --git a/ada_user/scheduling_concepts.rst b/ada_user/scheduling_concepts.rst deleted file mode 100644 index fb888f1..0000000 --- a/ada_user/scheduling_concepts.rst +++ /dev/null @@ -1,488 +0,0 @@ -Scheduling Concepts -################### - -.. index:: scheduling -.. index:: task scheduling - -Introduction -============ - -The concept of scheduling in real-time systems dictates the ability to -provide immediate response to specific external events, particularly -the necessity of scheduling tasks to run within a specified time limit -after the occurrence of an event. For example, software embedded in -life-support systems used to monitor hospital patients must take instant -action if a change in the patient’s status is detected. - -The component of RTEMS responsible for providing this capability is -appropriately called the scheduler. The scheduler’s sole purpose is -to allocate the all important resource of processor time to the various -tasks competing for attention. - -Scheduling Algorithms -===================== - -.. index:: scheduling algorithms - -RTEMS provides a plugin framework which allows it to support -multiple scheduling algorithms. RTEMS now includes multiple -scheduling algorithms in the SuperCore and the user can select which -of these they wish to use in their application. In addition, -the user can implement their own scheduling algorithm and -configure RTEMS to use it. - -Supporting multiple scheduling algorithms gives the end user the -option to select the algorithm which is most appropriate to their use -case. Most real-time operating systems schedule tasks using a priority -based algorithm, possibly with preemption control. The classic -RTEMS scheduling algorithm which was the only algorithm available -in RTEMS 4.10 and earlier, is a priority based scheduling algorithm. -This scheduling algoritm is suitable for single core (e.g. non-SMP) -systems and is now known as the *Deterministic Priority Scheduler*. -Unless the user configures another scheduling algorithm, RTEMS will use -this on single core systems. - -Priority Scheduling -------------------- -.. index:: priority scheduling - -When using priority based scheduling, RTEMS allocates the processor using -a priority-based, preemptive algorithm augmented to provide round-robin -characteristics within individual priority groups. The goal of this -algorithm is to guarantee that the task which is executing on the -processor at any point in time is the one with the highest priority -among all tasks in the ready state. - -When a task is added to the ready chain, it is placed behind all other -tasks of the same priority. This rule provides a round-robin within -priority group scheduling characteristic. This means that in a group of -equal priority tasks, tasks will execute in the order they become ready -or FIFO order. Even though there are ways to manipulate and adjust task -priorities, the most important rule to remember is: - -- *Priority based scheduling algorithms will always select the - highest priority task that is ready to run when allocating the processor - to a task.* - -Priority scheduling is the most commonly used scheduling algorithm. -It should be used by applications in which multiple tasks contend for -CPU time or other resources and there is a need to ensure certain tasks -are given priority over other tasks. - -There are a few common methods of accomplishing the mechanics of this -algorithm. These ways involve a list or chain of tasks in the ready state. - -- The least efficient method is to randomly place tasks in the ready - chain forcing the scheduler to scan the entire chain to determine which - task receives the processor. - -- A more efficient method is to schedule the task by placing it - in the proper place on the ready chain based on the designated scheduling - criteria at the time it enters the ready state. Thus, when the processor - is free, the first task on the ready chain is allocated the processor. - -- Another mechanism is to maintain a list of FIFOs per priority. - When a task is readied, it is placed on the rear of the FIFO for its - priority. This method is often used with a bitmap to assist in locating - which FIFOs have ready tasks on them. - -RTEMS currently includes multiple priority based scheduling algorithms -as well as other algorithms which incorporate deadline. Each algorithm -is discussed in the following sections. - -Deterministic Priority Scheduler --------------------------------- - -This is the scheduler implementation which has always been in RTEMS. -After the 4.10 release series, it was factored into pluggable scheduler -selection. It schedules tasks using a priority based algorithm which -takes into account preemption. It is implemented using an array of FIFOs -with a FIFO per priority. It maintains a bitmap which is used to track -which priorities have ready tasks. - -This algorithm is deterministic (e.g. predictable and fixed) in execution -time. This comes at the cost of using slightly over three (3) kilobytes -of RAM on a system configured to support 256 priority levels. - -This scheduler is only aware of a single core. - -Simple Priority Scheduler -------------------------- - -This scheduler implementation has the same behaviour as the Deterministic -Priority Scheduler but uses only one linked list to manage all ready -tasks. When a task is readied, a linear search of that linked list is -performed to determine where to insert the newly readied task. - -This algorithm uses much less RAM than the Deterministic Priority -Scheduler but is *O(n)* where *n* is the number of ready tasks. -In a small system with a small number of tasks, this will not be a -performance issue. Reducing RAM consumption is often critical in small -systems which are incapable of supporting a large number of tasks. - -This scheduler is only aware of a single core. - -Simple SMP Priority Scheduler ------------------------------ - -This scheduler is based upon the Simple Priority Scheduler and is designed -to have the same behaviour on a single core system. But this scheduler -is capable of scheduling threads across multiple cores in an SMP system. -When given a choice of replacing one of two threads at equal priority -on different cores, this algorithm favors replacing threads which are -preemptible and have executed the longest. - -This algorithm is non-deterministic. When scheduling, it must consider -which tasks are to be executed on each core while avoiding superfluous -task migrations. - -Earliest Deadline First Scheduler ---------------------------------- -.. index:: earliest deadline first scheduling - -This is an alternative scheduler in RTEMS for single core applications. -The primary EDF advantage is high total CPU utilization (theoretically -up to 100%). It assumes that tasks have priorities equal to deadlines. - -This EDF is initially preemptive, however, individual tasks may be declared -not-preemptive. Deadlines are declared using only Rate Monotonic manager which -goal is to handle periodic behavior. Period is always equal to deadline. All -ready tasks reside in a single ready queue implemented using a red-black tree. - -This implementation of EDF schedules two different types of task -priority types while each task may switch between the two types within -its execution. If a task does have a deadline declared using the Rate -Monotonic manager, the task is deadline-driven and its priority is equal -to deadline. On the contrary if a task does not have any deadline or -the deadline is cancelled using the Rate Monotonic manager, the task is -considered a background task with priority equal to that assigned -upon initialization in the same manner as for priority scheduler. Each -background task is of a lower importance than each deadline-driven one -and is scheduled when no deadline-driven task and no higher priority -background task is ready to run. - -Every deadline-driven scheduling algorithm requires means for tasks -to claim a deadline. The Rate Monotonic Manager is responsible for -handling periodic execution. In RTEMS periods are equal to deadlines, -thus if a task announces a period, it has to be finished until the -end of this period. The call of ``rtems_rate_monotonic_period`` -passes the scheduler the length of oncoming deadline. Moreover, the``rtems_rate_monotonic_cancel`` and ``rtems_rate_monotonic_delete`` -calls clear the deadlines assigned to the task. - -Constant Bandwidth Server Scheduling (CBS) ------------------------------------------- -.. index:: constant bandwidth server scheduling - -This is an alternative scheduler in RTEMS for single core applications. -The CBS is a budget aware extension of EDF scheduler. The main goal of this -scheduler is to ensure temporal isolation of tasks meaning that a task’s -execution in terms of meeting deadlines must not be influenced by other -tasks as if they were run on multiple independent processors. - -Each task can be assigned a server (current implementation supports only -one task per server). The server is characterized by period (deadline) -and computation time (budget). The ratio budget/period yields bandwidth, -which is the fraction of CPU to be reserved by the scheduler for each -subsequent period. - -The CBS is equipped with a set of rules applied to tasks attached to servers -ensuring that deadline miss because of another task cannot occur. -In case a task breaks one of the rules, its priority is pulled to background -until the end of its period and then restored again. The rules are: - -- Task cannot exceed its registered budget, - -- Task cannot be - unblocked when a ratio between remaining budget and remaining deadline - is higher than declared bandwidth. - -The CBS provides an extensive API. Unlike EDF, the``rtems_rate_monotonic_period`` does not declare a deadline because -it is carried out using CBS API. This call only announces next period. - -Scheduling Modification Mechanisms -================================== - -.. index:: scheduling mechanisms - -RTEMS provides four mechanisms which allow the user to alter the task -scheduling decisions: - -- user-selectable task priority level - -- task preemption control - -- task timeslicing control - -- manual round-robin selection - -Each of these methods provides a powerful capability to customize sets -of tasks to satisfy the unique and particular requirements encountered -in custom real-time applications. Although each mechanism operates -independently, there is a precedence relationship which governs the -effects of scheduling modifications. The evaluation order for scheduling -characteristics is always priority, preemption mode, and timeslicing. -When reading the descriptions of timeslicing and manual round-robin -it is important to keep in mind that preemption (if enabled) of a task -by higher priority tasks will occur as required, overriding the other -factors presented in the description. - -Task Priority and Scheduling ----------------------------- -.. index:: task priority - -The most significant task scheduling modification mechanism is the ability -for the user to assign a priority level to each individual task when it -is created and to alter a task’s priority at run-time. RTEMS supports -up to 255 priority levels. Level 255 is the lowest priority and level -1 is the highest. - -Preemption -----------.. index:: preemption - -Another way the user can alter the basic scheduling algorithm is by -manipulating the preemption mode flag (``RTEMS.PREEMPT_MASK``) -of individual tasks. If preemption is disabled for a task -(``RTEMS.NO_PREEMPT``), then the task will not relinquish -control of the processor until it terminates, blocks, or re-enables -preemption. Even tasks which become ready to run and possess higher -priority levels will not be allowed to execute. Note that the preemption -setting has no effect on the manner in which a task is scheduled. -It only applies once a task has control of the processor. - -Timeslicing ------------.. index:: timeslicing -.. index:: round robin scheduling - -Timeslicing or round-robin scheduling is an additional method which -can be used to alter the basic scheduling algorithm. Like preemption, -timeslicing is specified on a task by task basis using the timeslicing -mode flag (``RTEMS.TIMESLICE_MASK``). If timeslicing is -enabled for a task (``RTEMS.TIMESLICE``), then RTEMS will -limit the amount of time the task can execute before the processor is -allocated to another task. Each tick of the real-time clock reduces -the currently running task’s timeslice. When the execution time equals -the timeslice, RTEMS will dispatch another task of the same priority -to execute. If there are no other tasks of the same priority ready to -execute, then the current task is allocated an additional timeslice and -continues to run. Remember that a higher priority task will preempt -the task (unless preemption is disabled) as soon as it is ready to run, -even if the task has not used up its entire timeslice. - -Manual Round-Robin -------------------.. index:: manual round robin - -The final mechanism for altering the RTEMS scheduling algorithm is -called manual round-robin. Manual round-robin is invoked by using the``rtems.task_wake_after`` directive with a time interval -of ``RTEMS.YIELD_PROCESSOR``. This allows a task to give -up the processor and be immediately returned to the ready chain at the -end of its priority group. If no other tasks of the same priority are -ready to run, then the task does not lose control of the processor. - -Dispatching Tasks -=================.. index:: dispatching - -The dispatcher is the RTEMS component responsible for -allocating the processor to a ready task. In order to allocate -the processor to one task, it must be deallocated or retrieved -from the task currently using it. This involves a concept -called a context switch. To perform a context switch, the -dispatcher saves the context of the current task and restores -the context of the task which has been allocated to the -processor. Saving and restoring a task’s context is the -storing/loading of all the essential information about a task to -enable it to continue execution without any effects of the -interruption. For example, the contents of a task’s register -set must be the same when it is given the processor as they were -when it was taken away. All of the information that must be -saved or restored for a context switch is located either in the -TCB or on the task’s stacks. - -Tasks that utilize a numeric coprocessor and are created with the``RTEMS.FLOATING_POINT`` attribute require additional -operations during a context switch. These additional operations -are necessary to save and restore the floating point context of``RTEMS.FLOATING_POINT`` tasks. To avoid unnecessary save -and restore operations, the state of the numeric coprocessor is only -saved when a ``RTEMS.FLOATING_POINT`` task is dispatched -and that task was not the last task to utilize the coprocessor. - -Task State Transitions -======================.. index:: task state transitions - -Tasks in an RTEMS system must always be in one of the -five allowable task states. These states are: executing, ready, -blocked, dormant, and non-existent. - -A task occupies the non-existent state before -a ``rtems.task_create`` has been issued on its behalf. -A task enters the non-existent state from any other state in the system -when it is deleted with the ``rtems.task_delete`` directive. -While a task occupies this state it does not have a TCB or a task ID -assigned to it; therefore, no other tasks in the system may reference -this task. - -When a task is created via the ``rtems.task_create`` -directive it enters the dormant state. This state is not entered through -any other means. Although the task exists in the system, it cannot -actively compete for system resources. It will remain in the dormant -state until it is started via the ``rtems.task_start`` -directive, at which time it enters the ready state. The task is now -permitted to be scheduled for the processor and to compete for other -system resources. - -.. code:: c - - +-------------------------------------------------------------+ - | Non-existent | - | +-------------------------------------------------------+ | - | | | | - | | | | - | | Creating +---------+ Deleting | | - | | -------------------> | Dormant | -------------------> | | - | | +---------+ | | - | | | | | - | | Starting | | | - | | | | | - | | V Deleting | | - | | +-------> +-------+ -------------------> | | - | | Yielding / +----- | Ready | ------+ | | - | | / / +-------+ <--+ \\ | | - | | / / \\ \\ Blocking | | - | | / / Dispatching Readying \\ \\ | | - | | / V \\ V | | - | | +-----------+ Blocking +---------+ | | - | | | Executing | --------------> | Blocked | | | - | | +-----------+ +---------+ | | - | | | | - | | | | - | +-------------------------------------------------------+ | - | Non-existent | - +-------------------------------------------------------------+ - -A task occupies the blocked state whenever it is unable to be scheduled -to run. A running task may block itself or be blocked by other tasks in -the system. The running task blocks itself through voluntary operations -that cause the task to wait. The only way a task can block a task other -than itself is with the ``rtems.task_suspend`` directive. -A task enters the blocked state due to any of the following conditions: - -- A task issues a ``rtems.task_suspend`` directive - which blocks either itself or another task in the system. - -- The running task issues a ``rtems.barrier_wait`` - directive. - -- The running task issues a ``rtems.message_queue_receive`` - directive with the wait option and the message queue is empty. - -- The running task issues an ``rtems.event_receive`` - directive with the wait option and the currently pending events do not - satisfy the request. - -- The running task issues a ``rtems.semaphore_obtain`` - directive with the wait option and the requested semaphore is unavailable. - -- The running task issues a ``rtems.task_wake_after`` - directive which blocks the task for the given time interval. If the time - interval specified is zero, the task yields the processor and remains - in the ready state. - -- The running task issues a ``rtems.task_wake_when`` - directive which blocks the task until the requested date and time arrives. - -- The running task issues a ``rtems.rate_monotonic_period`` - directive and must wait for the specified rate monotonic period - to conclude. - -- The running task issues a ``rtems.region_get_segment`` - directive with the wait option and there is not an available segment large - enough to satisfy the task’s request. - -A blocked task may also be suspended. Therefore, both the suspension -and the blocking condition must be removed before the task becomes ready -to run again. - -A task occupies the ready state when it is able to be scheduled to run, -but currently does not have control of the processor. Tasks of the same -or higher priority will yield the processor by either becoming blocked, -completing their timeslice, or being deleted. All tasks with the same -priority will execute in FIFO order. A task enters the ready state due -to any of the following conditions: - -- A running task issues a ``rtems.task_resume`` - directive for a task that is suspended and the task is not blocked - waiting on any resource. - -- A running task issues a ``rtems.message_queue_send``,``rtems.message_queue_broadcast``, or a``rtems.message_queue_urgent`` directive - which posts a message to the queue on which the blocked task is - waiting. - -- A running task issues an ``rtems.event_send`` - directive which sends an event condition to a task which is blocked - waiting on that event condition. - -- A running task issues a ``rtems.semaphore_release`` - directive which releases the semaphore on which the blocked task is - waiting. - -- A timeout interval expires for a task which was blocked - by a call to the ``rtems.task_wake_after`` directive. - -- A timeout period expires for a task which blocked by a - call to the ``rtems.task_wake_when`` directive. - -- A running task issues a ``rtems.region_return_segment`` - directive which releases a segment to the region on which the blocked task - is waiting and a resulting segment is large enough to satisfy - the task’s request. - -- A rate monotonic period expires for a task which blocked - by a call to the ``rtems.rate_monotonic_period`` directive. - -- A timeout interval expires for a task which was blocked - waiting on a message, event, semaphore, or segment with a - timeout specified. - -- A running task issues a directive which deletes a - message queue, a semaphore, or a region on which the blocked - task is waiting. - -- A running task issues a ``rtems.task_restart`` - directive for the blocked task. - -- The running task, with its preemption mode enabled, may - be made ready by issuing any of the directives that may unblock - a task with a higher priority. This directive may be issued - from the running task itself or from an ISR. - A ready task occupies the executing state when it has - control of the CPU. A task enters the executing state due to - any of the following conditions: - -- The task is the highest priority ready task in the - system. - -- The running task blocks and the task is next in the - scheduling queue. The task may be of equal priority as in - round-robin scheduling or the task may possess the highest - priority of the remaining ready tasks. - -- The running task may reenable its preemption mode and a - task exists in the ready queue that has a higher priority than - the running task. - -- The running task lowers its own priority and another - task is of higher priority as a result. - -- The running task raises the priority of a task above its - own and the running task is in preemption mode. - -.. COMMENT: COPYRIGHT (c) 1988-2013. - -.. COMMENT: On-Line Applications Research Corporation (OAR). - -.. COMMENT: All rights reserved. - -.. COMMENT: Open Issues - -.. COMMENT: - nicen up the tables - -.. COMMENT: - use math mode to print formulas - |