diff options
Diffstat (limited to 'doc/user/schedule.t')
| -rw-r--r-- | doc/user/schedule.t | 426 |
1 files changed, 426 insertions, 0 deletions
diff --git a/doc/user/schedule.t b/doc/user/schedule.t new file mode 100644 index 0000000000..5781a670b7 --- /dev/null +++ b/doc/user/schedule.t @@ -0,0 +1,426 @@ +@c +@c COPYRIGHT (c) 1996. +@c On-Line Applications Research Corporation (OAR). +@c All rights reserved. +@c + +@c +@c This figure is not included: +@c Figure 17-1 RTEMS Task State Transitions +@c + +@ifinfo +@node Scheduling Concepts, Scheduling Concepts Introduction, FATAL_ERROR_OCCURRED - Invoke the fatal error handler, Top +@end ifinfo +@chapter Scheduling Concepts +@ifinfo +@menu +* Scheduling Concepts Introduction:: +* Scheduling Concepts Scheduling Mechanisms:: +* Scheduling Concepts Task State Transitions:: +@end menu +@end ifinfo + +@ifinfo +@node Scheduling Concepts Introduction, Scheduling Concepts Scheduling Mechanisms, Scheduling Concepts, Scheduling Concepts +@end ifinfo +@section 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. The RTEMS scheduler 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. + +There are two common methods of accomplishing the +mechanics of this algorithm. Both ways involve a list or chain +of tasks in the ready state. One 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 other 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. RTEMS schedules tasks using +the second method to guarantee faster response times to external +events. + +@ifinfo +@node Scheduling Concepts Scheduling Mechanisms, Task Priority and Scheduling, Scheduling Concepts Introduction, Scheduling Concepts +@end ifinfo +@section Scheduling Mechanisms +@ifinfo +@menu +* Task Priority and Scheduling:: +* Preemption:: +* Timeslicing:: +* Manual Round-Robin:: +* Dispatching Tasks:: +@end menu +@end ifinfo + +RTEMS provides four mechanisms which allow the user +to impact the task scheduling process: + +@itemize @bullet +@item user-selectable task priority level +@item task preemption control +@item task timeslicing control +@item manual round-robin selection +@end itemize + +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. + +@ifinfo +@node Task Priority and Scheduling, Preemption, Scheduling Concepts Scheduling Mechanisms, Scheduling Concepts Scheduling Mechanisms +@end ifinfo +@subsection Task Priority and Scheduling + +The most significant of these mechanisms 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 provides 255 priority levels. +Level 255 is the lowest priority and level 1 is the highest. +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: + +@itemize @code{ } +@item @b{The RTEMS scheduler will always select the highest +priority task that is ready to run when allocating the processor +to a task.} +@end itemize + +@ifinfo +@node Preemption, Timeslicing, Task Priority and Scheduling, Scheduling Concepts Scheduling Mechanisms +@end ifinfo +@subsection Preemption + +Another way the user can alter the basic scheduling +algorithm is by manipulating the preemption mode flag +(PREEMPT_MASK) of individual tasks. If preemption is disabled +for a task (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. + +@ifinfo +@node Timeslicing, Manual Round-Robin, Preemption, Scheduling Concepts Scheduling Mechanisms +@end ifinfo +@subsection Timeslicing + +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 +(TIMESLICE_MASK). If timeslicing is enabled for a task +(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. + +@ifinfo +@node Manual Round-Robin, Dispatching Tasks, Timeslicing, Scheduling Concepts Scheduling Mechanisms +@end ifinfo +@subsection 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 task_wake_after directive with a time +interval of 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. + +@ifinfo +@node Dispatching Tasks, Scheduling Concepts Task State Transitions, Manual Round-Robin, Scheduling Concepts Scheduling Mechanisms +@end ifinfo +@subsection Dispatching Tasks + +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 FLOATING_POINT attribute require additional +operations during a context switch. These additional operations +are necessary to save and restore the floating point context of +FLOATING_POINT tasks. To avoid unnecessary save and restore +operations, the state of the numeric coprocessor is only saved +when a FLOATING_POINT task is dispatched and that task was not +the last task to utilize the coprocessor. + +@ifinfo +@node Scheduling Concepts Task State Transitions, Rate Monotonic Manager, Dispatching Tasks, Scheduling Concepts +@end ifinfo +@section 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. + +@ifset use-ascii +@example +@group + +-------------------------------------------------------------+ + | Non-existent | + | +-------------------------------------------------------+ | + | | | | + | | | | + | | Creating +---------+ Deleting | | + | | -------------------> | Dormant | -------------------> | | + | | +---------+ | | + | | | | | + | | Starting | | | + | | | | | + | | V Deleting | | + | | +-------> +-------+ -------------------> | | + | | Yielding / +----- | Ready | ------+ | | + | | / / +-------+ <--+ \ | | + | | / / \ \ Blocking | | + | | / / Dispatching Readying \ \ | | + | | / V \ V | | + | | +-----------+ Blocking +---------+ | | + | | | Executing | --------------> | Blocked | | | + | | +-----------+ +---------+ | | + | | | | + | | | | + | +-------------------------------------------------------+ | + | Non-existent | + +-------------------------------------------------------------+ +@end group +@end example +@end ifset + +@ifset use-tex +@c for now use the ascii version +@example +@group + +-------------------------------------------------------------+ + | Non-existent | + | +-------------------------------------------------------+ | + | | | | + | | | | + | | Creating +---------+ Deleting | | + | | -------------------> | Dormant | -------------------> | | + | | +---------+ | | + | | | | | + | | Starting | | | + | | | | | + | | V Deleting | | + | | +-------> +-------+ -------------------> | | + | | Yielding / +----- | Ready | ------+ | | + | | / / +-------+ <--+ \ | | + | | / / \ \ Blocking | | + | | / / Dispatching Readying \ \ | | + | | / V \ V | | + | | +-----------+ Blocking +---------+ | | + | | | Executing | --------------> | Blocked | | | + | | +-----------+ +---------+ | | + | | | | + | | | | + | +-------------------------------------------------------+ | + | Non-existent | + +-------------------------------------------------------------+ +@end group +@end example +@tex +@end tex +@end ifset + +@ifset use-html +@html +<IMG SRC="states.gif" WIDTH=550 HEIGHT=400 ALT="RTEMS Task States"> +@end html +@end ifset + +A task occupies the non-existent state before a +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 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 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 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. + +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 task_suspend directive. A task enters the blocked +state due to any of the following conditions: + +@itemize @bullet +@item A task issues a task_suspend directive which blocks +either itself or another task in the system. + +@item The running task issues a message_queue_receive +directive with the wait option and the message queue is empty. + +@item The running task issues an event_receive directive with +the wait option and the currently pending events do not satisfy +the request. + +@item The running task issues a semaphore_obtain directive +with the wait option and the requested semaphore is unavailable. + +@item The running task issues a 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. + +@item The running task issues a task_wake_when directive which +blocks the task until the requested date and time arrives. + +@item The running task issues a region_get_segment directive +with the wait option and there is not an available segment large +enough to satisfy the task's request. + +@item The running task issues a rate_monotonic_period +directive and must wait for the specified rate monotonic period +to conclude. +@end itemize + +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: + +@itemize @bullet + +@item A running task issues a task_resume directive for a task +that is suspended and the task is not blocked waiting on any +resource. + +@item A running task issues a message_queue_send, +message_queue_broadcast, or a message_queue_urgent directive +which posts a message to the queue on which the blocked task is +waiting. + +@item A running task issues an event_send directive which +sends an event condition to a task which is blocked waiting on +that event condition. + +@item A running task issues a semaphore_release directive +which releases the semaphore on which the blocked task is +waiting. + +@item A timeout interval expires for a task which was blocked +by a call to the task_wake_after directive. + +@item A timeout period expires for a task which blocked by a +call to the task_wake_when directive. + +@item A running task issues a 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. + +@item A rate monotonic period expires for a task which blocked +by a call to the rate_monotonic_period directive. + +@item A timeout interval expires for a task which was blocked +waiting on a message, event, semaphore, or segment with a +timeout specified. + +@item A running task issues a directive which deletes a +message queue, a semaphore, or a region on which the blocked +task is waiting. + +@item A running task issues a task_restart directive for the +blocked task. + +@item 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: + +@item The task is the highest priority ready task in the +system. + +@item 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. + +@item 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. + +@item The running task lowers its own priority and another +task is of higher priority as a result. + +@item The running task raises the priority of a task above its +own and the running task is in preemption mode. + +@end itemize |