diff options
Diffstat (limited to '')
-rw-r--r-- | c_user/scheduling_concepts.rst | 692 |
1 files changed, 337 insertions, 355 deletions
diff --git a/c_user/scheduling_concepts.rst b/c_user/scheduling_concepts.rst index d5b261e..ea77157 100644 --- a/c_user/scheduling_concepts.rst +++ b/c_user/scheduling_concepts.rst @@ -1,3 +1,7 @@ +.. COMMENT: COPYRIGHT (c) 1988-2008. +.. COMMENT: On-Line Applications Research Corporation (OAR). +.. COMMENT: All rights reserved. + Scheduling Concepts ################### @@ -7,102 +11,101 @@ Scheduling Concepts 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 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. +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. +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. +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: + +.. note:: + + 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. +- 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. +- 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. +- 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. +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 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 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. @@ -110,94 +113,92 @@ 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. +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 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 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. +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 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. +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 +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. +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. +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: +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. +- 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. +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 ================================== @@ -215,268 +216,249 @@ scheduling decisions: - 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. +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. +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 +---------- +.. 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. +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:: 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. +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 +------------------ +.. 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. +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. +================= +.. 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 +====================== +.. 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. + +.. COMMENT: .. code:: c +.. COMMENT: +.. COMMENT: +-------------------------------------------------------------+ +.. COMMENT: | Non-existent | +.. COMMENT: | +-------------------------------------------------------+ | +.. COMMENT: | | | | +.. COMMENT: | | | | +.. COMMENT: | | Creating +---------+ Deleting | | +.. COMMENT: | | -------------------> | Dormant | -------------------> | | +.. COMMENT: | | +---------+ | | +.. COMMENT: | | | | | +.. COMMENT: | | Starting | | | +.. COMMENT: | | | | | +.. COMMENT: | | V Deleting | | +.. COMMENT: | | +-------> +-------+ -------------------> | | +.. COMMENT: | | Yielding / +----- | Ready | ------+ | | +.. COMMENT: | | / / +-------+ <--+ \\ | | +.. COMMENT: | | / / \\ \\ Blocking | | +.. COMMENT: | | / / Dispatching Readying \\ \\ | | +.. COMMENT: | | / V \\ V | | +.. COMMENT: | | +-----------+ Blocking +---------+ | | +.. COMMENT: | | | Executing | --------------> | Blocked | | | +.. COMMENT: | | +-----------+ +---------+ | | +.. COMMENT: | | | | +.. COMMENT: | | | | +.. COMMENT: | +-------------------------------------------------------+ | +.. COMMENT: | Non-existent | +.. COMMENT: +-------------------------------------------------------------+ + +.. figure:: states.png + :width: 70% + :align: center + :alt: Task State Transitions + +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 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 running task issues a ``rtems_semaphore_release`` directive which releases + the semaphore on which the blocked task is waiting. -- 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 by a call to the + ``rtems_task_wake_after`` directive. -- A timeout interval expires for a task which was blocked - waiting on a message, event, semaphore, or segment with a - timeout specified. +- A timeout period expires for a task which blocked by a call to the + ``rtems_task_wake_when`` directive. -- 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_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 running task issues a ``rtems_task_restart`` - directive for the blocked task. +- A rate monotonic period expires for a task which blocked by a call to the + ``rtems_rate_monotonic_period`` directive. -- 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: +- A timeout interval expires for a task which was blocked waiting on a message, + event, semaphore, or segment with a timeout specified. -- The task is the highest priority ready task in the - system. +- A running task issues a directive which deletes a message queue, a semaphore, + or a region on which the blocked task is waiting. -- 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. +- A running task issues a ``rtems_task_restart`` directive for the blocked + task. -- 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, 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 running task lowers its own priority and another - task is of higher priority as a result. +- The task is the highest priority ready task in the system. -- The running task raises the priority of a task above its - own and the running task is in preemption mode. +- 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. -.. COMMENT: COPYRIGHT (c) 1988-2008. - -.. COMMENT: On-Line Applications Research Corporation (OAR). +- 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. -.. COMMENT: All rights reserved. +- 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. |