From fd6dc8c8de4dbc7ecf8a82a597cd5b43476fc8e3 Mon Sep 17 00:00:00 2001 From: Amar Takhar Date: Sun, 17 Jan 2016 19:19:43 -0500 Subject: Split document into seperate files by section. --- c_user/scheduling_concepts.rst | 482 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 482 insertions(+) create mode 100644 c_user/scheduling_concepts.rst (limited to 'c_user/scheduling_concepts.rst') diff --git a/c_user/scheduling_concepts.rst b/c_user/scheduling_concepts.rst new file mode 100644 index 0000000..56ddc46 --- /dev/null +++ b/c_user/scheduling_concepts.rst @@ -0,0 +1,482 @@ +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-2008. + +.. COMMENT: On-Line Applications Research Corporation (OAR). + +.. COMMENT: All rights reserved. + -- cgit v1.2.3