source: rtems-docs/c_user/scheduling_concepts.rst @ 170418a

4.115am
Last change on this file since 170418a was 170418a, checked in by Amar Takhar <verm@…>, on 05/18/16 at 17:47:42

Move images to a common directory.

  • Property mode set to 100644
File size: 20.3 KB
Line 
1.. COMMENT: COPYRIGHT (c) 1988-2008.
2.. COMMENT: On-Line Applications Research Corporation (OAR).
3.. COMMENT: All rights reserved.
4
5Scheduling Concepts
6###################
7
8.. index:: scheduling
9.. index:: task scheduling
10
11Introduction
12============
13
14The concept of scheduling in real-time systems dictates the ability to provide
15immediate response to specific external events, particularly the necessity of
16scheduling tasks to run within a specified time limit after the occurrence of
17an event.  For example, software embedded in life-support systems used to
18monitor hospital patients must take instant action if a change in the patient's
19status is detected.
20
21The component of RTEMS responsible for providing this capability is
22appropriately called the scheduler.  The scheduler's sole purpose is to
23allocate the all important resource of processor time to the various tasks
24competing for attention.
25
26Scheduling Algorithms
27=====================
28
29.. index:: scheduling algorithms
30
31RTEMS provides a plugin framework which allows it to support multiple
32scheduling algorithms. RTEMS now includes multiple scheduling algorithms in the
33SuperCore and the user can select which of these they wish to use in their
34application.  In addition, the user can implement their own scheduling
35algorithm and configure RTEMS to use it.
36
37Supporting multiple scheduling algorithms gives the end user the option to
38select the algorithm which is most appropriate to their use case. Most
39real-time operating systems schedule tasks using a priority based algorithm,
40possibly with preemption control.  The classic RTEMS scheduling algorithm which
41was the only algorithm available in RTEMS 4.10 and earlier, is a priority based
42scheduling algorithm.  This scheduling algoritm is suitable for single core
43(e.g. non-SMP) systems and is now known as the *Deterministic Priority
44Scheduler*.  Unless the user configures another scheduling algorithm, RTEMS
45will use this on single core systems.
46
47Priority Scheduling
48-------------------
49.. index:: priority scheduling
50
51When using priority based scheduling, RTEMS allocates the processor using a
52priority-based, preemptive algorithm augmented to provide round-robin
53characteristics within individual priority groups.  The goal of this algorithm
54is to guarantee that the task which is executing on the processor at any point
55in time is the one with the highest priority among all tasks in the ready
56state.
57
58When a task is added to the ready chain, it is placed behind all other tasks of
59the same priority.  This rule provides a round-robin within priority group
60scheduling characteristic.  This means that in a group of equal priority tasks,
61tasks will execute in the order they become ready or FIFO order.  Even though
62there are ways to manipulate and adjust task priorities, the most important
63rule to remember is:
64
65.. note::
66
67  Priority based scheduling algorithms will always select the highest priority
68  task that is ready to run when allocating the processor to a task.
69
70Priority scheduling is the most commonly used scheduling algorithm.  It should
71be used by applications in which multiple tasks contend for CPU time or other
72resources and there is a need to ensure certain tasks are given priority over
73other tasks.
74
75There are a few common methods of accomplishing the mechanics of this
76algorithm.  These ways involve a list or chain of tasks in the ready state.
77
78- The least efficient method is to randomly place tasks in the ready chain
79  forcing the scheduler to scan the entire chain to determine which task
80  receives the processor.
81
82- A more efficient method is to schedule the task by placing it in the proper
83  place on the ready chain based on the designated scheduling criteria at the
84  time it enters the ready state.  Thus, when the processor is free, the first
85  task on the ready chain is allocated the processor.
86
87- Another mechanism is to maintain a list of FIFOs per priority.  When a task
88  is readied, it is placed on the rear of the FIFO for its priority.  This
89  method is often used with a bitmap to assist in locating which FIFOs have
90  ready tasks on them.
91
92RTEMS currently includes multiple priority based scheduling algorithms as well
93as other algorithms which incorporate deadline.  Each algorithm is discussed in
94the following sections.
95
96Deterministic Priority Scheduler
97--------------------------------
98
99This is the scheduler implementation which has always been in RTEMS.  After the
1004.10 release series, it was factored into pluggable scheduler selection.  It
101schedules tasks using a priority based algorithm which takes into account
102preemption.  It is implemented using an array of FIFOs with a FIFO per
103priority.  It maintains a bitmap which is used to track which priorities have
104ready tasks.
105
106This algorithm is deterministic (e.g. predictable and fixed) in execution time.
107This comes at the cost of using slightly over three (3) kilobytes of RAM on a
108system configured to support 256 priority levels.
109
110This scheduler is only aware of a single core.
111
112Simple Priority Scheduler
113-------------------------
114
115This scheduler implementation has the same behaviour as the Deterministic
116Priority Scheduler but uses only one linked list to manage all ready tasks.
117When a task is readied, a linear search of that linked list is performed to
118determine where to insert the newly readied task.
119
120This algorithm uses much less RAM than the Deterministic Priority Scheduler but
121is *O(n)* where *n* is the number of ready tasks.  In a small system with a
122small number of tasks, this will not be a performance issue.  Reducing RAM
123consumption is often critical in small systems which are incapable of
124supporting a large number of tasks.
125
126This scheduler is only aware of a single core.
127
128Simple SMP Priority Scheduler
129-----------------------------
130
131This scheduler is based upon the Simple Priority Scheduler and is designed to
132have the same behaviour on a single core system.  But this scheduler is capable
133of scheduling threads across multiple cores in an SMP system.  When given a
134choice of replacing one of two threads at equal priority on different cores,
135this algorithm favors replacing threads which are preemptible and have executed
136the longest.
137
138This algorithm is non-deterministic. When scheduling, it must consider which
139tasks are to be executed on each core while avoiding superfluous task
140migrations.
141
142Earliest Deadline First Scheduler
143---------------------------------
144.. index:: earliest deadline first scheduling
145
146This is an alternative scheduler in RTEMS for single core applications.  The
147primary EDF advantage is high total CPU utilization (theoretically up to
148100%). It assumes that tasks have priorities equal to deadlines.
149
150This EDF is initially preemptive, however, individual tasks may be declared
151not-preemptive. Deadlines are declared using only Rate Monotonic manager which
152goal is to handle periodic behavior. Period is always equal to deadline. All
153ready tasks reside in a single ready queue implemented using a red-black tree.
154
155This implementation of EDF schedules two different types of task priority types
156while each task may switch between the two types within its execution. If a
157task does have a deadline declared using the Rate Monotonic manager, the task
158is deadline-driven and its priority is equal to deadline.  On the contrary if a
159task does not have any deadline or the deadline is cancelled using the Rate
160Monotonic manager, the task is considered a background task with priority equal
161to that assigned upon initialization in the same manner as for priority
162scheduler. Each background task is of a lower importance than each
163deadline-driven one and is scheduled when no deadline-driven task and no higher
164priority background task is ready to run.
165
166Every deadline-driven scheduling algorithm requires means for tasks to claim a
167deadline.  The Rate Monotonic Manager is responsible for handling periodic
168execution. In RTEMS periods are equal to deadlines, thus if a task announces a
169period, it has to be finished until the end of this period. The call of
170``rtems_rate_monotonic_period`` passes the scheduler the length of oncoming
171deadline. Moreover, the ``rtems_rate_monotonic_cancel`` and
172``rtems_rate_monotonic_delete`` calls clear the deadlines assigned to the task.
173
174Constant Bandwidth Server Scheduling (CBS)
175------------------------------------------
176.. index:: constant bandwidth server scheduling
177
178This is an alternative scheduler in RTEMS for single core applications.  The
179CBS is a budget aware extension of EDF scheduler. The main goal of this
180scheduler is to ensure temporal isolation of tasks meaning that a task's
181execution in terms of meeting deadlines must not be influenced by other tasks
182as if they were run on multiple independent processors.
183
184Each task can be assigned a server (current implementation supports only one
185task per server). The server is characterized by period (deadline) and
186computation time (budget). The ratio budget/period yields bandwidth, which is
187the fraction of CPU to be reserved by the scheduler for each subsequent period.
188
189The CBS is equipped with a set of rules applied to tasks attached to servers
190ensuring that deadline miss because of another task cannot occur.  In case a
191task breaks one of the rules, its priority is pulled to background until the
192end of its period and then restored again. The rules are:
193
194- Task cannot exceed its registered budget,
195
196- Task cannot be unblocked when a ratio between remaining budget and remaining
197  deadline is higher than declared bandwidth.
198
199The CBS provides an extensive API. Unlike EDF, the
200``rtems_rate_monotonic_period`` does not declare a deadline because it is
201carried out using CBS API. This call only announces next period.
202
203Scheduling Modification Mechanisms
204==================================
205
206.. index:: scheduling mechanisms
207
208RTEMS provides four mechanisms which allow the user to alter the task
209scheduling decisions:
210
211- user-selectable task priority level
212
213- task preemption control
214
215- task timeslicing control
216
217- manual round-robin selection
218
219Each of these methods provides a powerful capability to customize sets of tasks
220to satisfy the unique and particular requirements encountered in custom
221real-time applications.  Although each mechanism operates independently, there
222is a precedence relationship which governs the effects of scheduling
223modifications.  The evaluation order for scheduling characteristics is always
224priority, preemption mode, and timeslicing.  When reading the descriptions of
225timeslicing and manual round-robin it is important to keep in mind that
226preemption (if enabled) of a task by higher priority tasks will occur as
227required, overriding the other factors presented in the description.
228
229Task Priority and Scheduling
230----------------------------
231.. index:: task priority
232
233The most significant task scheduling modification mechanism is the ability for
234the user to assign a priority level to each individual task when it is created
235and to alter a task's priority at run-time.  RTEMS supports up to 255 priority
236levels.  Level 255 is the lowest priority and level 1 is the highest.
237
238Preemption
239----------
240.. index:: preemption
241
242Another way the user can alter the basic scheduling algorithm is by
243manipulating the preemption mode flag (``RTEMS_PREEMPT_MASK``) of individual
244tasks.  If preemption is disabled for a task (``RTEMS_NO_PREEMPT``), then the
245task will not relinquish control of the processor until it terminates, blocks,
246or re-enables preemption.  Even tasks which become ready to run and possess
247higher priority levels will not be allowed to execute.  Note that the
248preemption setting has no effect on the manner in which a task is scheduled.
249It only applies once a task has control of the processor.
250
251Timeslicing
252-----------
253.. index:: timeslicing
254.. index:: round robin scheduling
255
256Timeslicing or round-robin scheduling is an additional method which can be used
257to alter the basic scheduling algorithm.  Like preemption, timeslicing is
258specified on a task by task basis using the timeslicing mode flag
259(``RTEMS_TIMESLICE_MASK``).  If timeslicing is enabled for a task
260(``RTEMS_TIMESLICE``), then RTEMS will limit the amount of time the task can
261execute before the processor is allocated to another task.  Each tick of the
262real-time clock reduces the currently running task's timeslice.  When the
263execution time equals the timeslice, RTEMS will dispatch another task of the
264same priority to execute.  If there are no other tasks of the same priority
265ready to execute, then the current task is allocated an additional timeslice
266and continues to run.  Remember that a higher priority task will preempt the
267task (unless preemption is disabled) as soon as it is ready to run, even if the
268task has not used up its entire timeslice.
269
270Manual Round-Robin
271------------------
272.. index:: manual round robin
273
274The final mechanism for altering the RTEMS scheduling algorithm is called
275manual round-robin.  Manual round-robin is invoked by using
276the ``rtems_task_wake_after`` directive with a time interval of
277``RTEMS_YIELD_PROCESSOR``.  This allows a task to give up the processor and be
278immediately returned to the ready chain at the end of its priority group.  If
279no other tasks of the same priority are ready to run, then the task does not
280lose control of the processor.
281
282Dispatching Tasks
283=================
284.. index:: dispatching
285
286The dispatcher is the RTEMS component responsible for allocating the processor
287to a ready task.  In order to allocate the processor to one task, it must be
288deallocated or retrieved from the task currently using it.  This involves a
289concept called a context switch.  To perform a context switch, the dispatcher
290saves the context of the current task and restores the context of the task
291which has been allocated to the processor.  Saving and restoring a task's
292context is the storing/loading of all the essential information about a task to
293enable it to continue execution without any effects of the interruption.  For
294example, the contents of a task's register set must be the same when it is
295given the processor as they were when it was taken away.  All of the
296information that must be saved or restored for a context switch is located
297either in the TCB or on the task's stacks.
298
299Tasks that utilize a numeric coprocessor and are created with the
300``RTEMS_FLOATING_POINT`` attribute require additional operations during a
301context switch.  These additional operations are necessary to save and restore
302the floating point context of ``RTEMS_FLOATING_POINT`` tasks.  To avoid
303unnecessary save and restore operations, the state of the numeric coprocessor
304is only saved when a ``RTEMS_FLOATING_POINT`` task is dispatched and that task
305was not the last task to utilize the coprocessor.
306
307Task State Transitions
308======================
309.. index:: task state transitions
310
311Tasks in an RTEMS system must always be in one of the five allowable task
312states.  These states are: executing, ready, blocked, dormant, and
313non-existent.
314
315A task occupies the non-existent state before a ``rtems_task_create`` has been
316issued on its behalf.  A task enters the non-existent state from any other
317state in the system when it is deleted with the ``rtems_task_delete``
318directive.  While a task occupies this state it does not have a TCB or a task
319ID assigned to it; therefore, no other tasks in the system may reference this
320task.
321
322When a task is created via the ``rtems_task_create`` directive it enters the
323dormant state.  This state is not entered through any other means.  Although
324the task exists in the system, it cannot actively compete for system resources.
325It will remain in the dormant state until it is started via the
326``rtems_task_start`` directive, at which time it enters the ready state.  The
327task is now permitted to be scheduled for the processor and to compete for
328other system resources.
329
330.. figure:: ../images/c_user/states.png
331         :width: 70%
332         :align: center
333         :alt: Task State Transitions
334
335A task occupies the blocked state whenever it is unable to be scheduled to run.
336A running task may block itself or be blocked by other tasks in the system.
337The running task blocks itself through voluntary operations that cause the task
338to wait.  The only way a task can block a task other than itself is with the
339``rtems_task_suspend`` directive.  A task enters the blocked state due to any
340of the following conditions:
341
342- A task issues a ``rtems_task_suspend`` directive which blocks either itself
343  or another task in the system.
344
345- The running task issues a ``rtems_barrier_wait`` directive.
346
347- The running task issues a ``rtems_message_queue_receive`` directive with the
348  wait option and the message queue is empty.
349
350- The running task issues an ``rtems_event_receive`` directive with the wait
351  option and the currently pending events do not satisfy the request.
352
353- The running task issues a ``rtems_semaphore_obtain`` directive with the wait
354  option and the requested semaphore is unavailable.
355
356- The running task issues a ``rtems_task_wake_after`` directive which blocks
357  the task for the given time interval.  If the time interval specified is
358  zero, the task yields the processor and remains in the ready state.
359
360- The running task issues a ``rtems_task_wake_when`` directive which blocks the
361  task until the requested date and time arrives.
362
363- The running task issues a ``rtems_rate_monotonic_period`` directive and must
364  wait for the specified rate monotonic period to conclude.
365
366- The running task issues a ``rtems_region_get_segment`` directive with the
367  wait option and there is not an available segment large enough to satisfy the
368  task's request.
369
370A blocked task may also be suspended.  Therefore, both the suspension and the
371blocking condition must be removed before the task becomes ready to run again.
372
373A task occupies the ready state when it is able to be scheduled to run, but
374currently does not have control of the processor.  Tasks of the same or higher
375priority will yield the processor by either becoming blocked, completing their
376timeslice, or being deleted.  All tasks with the same priority will execute in
377FIFO order.  A task enters the ready state due to any of the following
378conditions:
379
380- A running task issues a ``rtems_task_resume`` directive for a task that is
381  suspended and the task is not blocked waiting on any resource.
382
383- A running task issues a ``rtems_message_queue_send``,
384  ``rtems_message_queue_broadcast``, or a ``rtems_message_queue_urgent``
385  directive which posts a message to the queue on which the blocked task is
386  waiting.
387
388- A running task issues an ``rtems_event_send`` directive which sends an event
389  condition to a task which is blocked waiting on that event condition.
390
391- A running task issues a ``rtems_semaphore_release`` directive which releases
392  the semaphore on which the blocked task is waiting.
393
394- A timeout interval expires for a task which was blocked by a call to the
395  ``rtems_task_wake_after`` directive.
396
397- A timeout period expires for a task which blocked by a call to the
398  ``rtems_task_wake_when`` directive.
399
400- A running task issues a ``rtems_region_return_segment`` directive which
401  releases a segment to the region on which the blocked task is waiting and a
402  resulting segment is large enough to satisfy the task's request.
403
404- A rate monotonic period expires for a task which blocked by a call to the
405  ``rtems_rate_monotonic_period`` directive.
406
407- A timeout interval expires for a task which was blocked waiting on a message,
408  event, semaphore, or segment with a timeout specified.
409
410- A running task issues a directive which deletes a message queue, a semaphore,
411  or a region on which the blocked task is waiting.
412
413- A running task issues a ``rtems_task_restart`` directive for the blocked
414  task.
415
416- The running task, with its preemption mode enabled, may be made ready by
417  issuing any of the directives that may unblock a task with a higher priority.
418  This directive may be issued from the running task itself or from an ISR.  A
419  ready task occupies the executing state when it has control of the CPU.  A
420  task enters the executing state due to any of the following conditions:
421
422- The task is the highest priority ready task in the system.
423
424- The running task blocks and the task is next in the scheduling queue.  The
425  task may be of equal priority as in round-robin scheduling or the task may
426  possess the highest priority of the remaining ready tasks.
427
428- The running task may reenable its preemption mode and a task exists in the
429  ready queue that has a higher priority than the running task.
430
431- The running task lowers its own priority and another task is of higher
432  priority as a result.
433
434- The running task raises the priority of a task above its own and the running
435  task is in preemption mode.
Note: See TracBrowser for help on using the repository browser.