source: rtems/doc/user/schedule.t @ db9964f1

Last change on this file since db9964f1 was db9964f1, checked in by Joel Sherrill <joel.sherrill@…>, on Nov 24, 2010 at 3:52:21 PM

2010-11-24 Gedare Bloom <giddyup44@…>

PR 1647/cpukit

  • user/conf.t, user/schedule.t: Update documentation to reflect refactoring of SuperCore? to add Scheduler and ability for user to configure a scheduler.
  • Property mode set to 100644
File size: 16.9 KB
2@c  COPYRIGHT (c) 1988-2002.
3@c  On-Line Applications Research Corporation (OAR).
4@c  All rights reserved.
6@c  $Id$
10@c   This figure is not included:
11@c      Figure 17-1  RTEMS Task State Transitions
14@chapter Scheduling Concepts
16@cindex scheduling
17@cindex task scheduling
19@section Introduction
21The concept of scheduling in real-time systems
22dictates the ability to provide immediate response to specific
23external events, particularly the necessity of scheduling tasks
24to run within a specified time limit after the occurrence of an
25event.  For example, software embedded in life-support systems
26used to monitor hospital patients must take instant action if a
27change in the patient's status is detected.
29The component of RTEMS responsible for providing this
30capability is appropriately called the scheduler.  The
31scheduler's sole purpose is to allocate the all important
32resource of processor time to the various tasks competing for
35@section Scheduling Algorithms
37@cindex scheduling algorithms
39RTEMS provides multiple possible scheduling algorithms, each
40of which are appropriate to different use case scenarios.
41The classic RTEMS scheduling algorithm -- the only
42algorithm available in RTEMS 4.10 and earlier -- is the priority
43scheduling algorithm.  When not specified, the priority scheduling
44algorithm can be assumed.
46RTEMS currently supports the following scheduling algorithms:
48@itemize @bullet
49@item Priority scheduling
50@end itemize
52@subsection Priority Scheduling
54@cindex priority scheduling
56The RTEMS scheduler allocates the processor using a
57priority-based, preemptive algorithm augmented to provide
58round-robin characteristics within individual priority groups.
59The goal of this algorithm is to guarantee that the task which
60is executing on the processor at any point in time is the one
61with the highest priority among all tasks in the ready state.
63There are two common methods of accomplishing the
64mechanics of this algorithm.  Both ways involve a list or chain
65of tasks in the ready state.  One method is to randomly place
66tasks in the ready chain forcing the scheduler to scan the
67entire chain to determine which task receives the processor.
68The other method is to schedule the task by placing it in the
69proper place on the ready chain based on the designated
70scheduling criteria at the time it enters the ready state.
71Thus, when the processor is free, the first task on the ready
72chain is allocated the processor.  RTEMS schedules tasks using
73the second method to guarantee faster response times to external
76Priority scheduling is the most commonly used scheduling algorithm.
77It should be used by applications in which multiple tasks contend for
78CPU time or other resources and there is a need to ensure certain tasks
79are given priority over other tasks.
81@section Scheduling Mechanisms
83@cindex scheduling mechanisms
85RTEMS provides four mechanisms which allow the user
86to impact the task scheduling process:
88@itemize @bullet
89@item user-selectable task priority level
90@item task preemption control
91@item task timeslicing control
92@item manual round-robin selection
93@end itemize
95Each of these methods provides a powerful capability
96to customize sets of tasks to satisfy the unique and particular
97requirements encountered in custom real-time applications.
98Although each mechanism operates independently, there is a
99precedence relationship which governs the effects of scheduling
100modifications.  The evaluation order for scheduling
101characteristics is always priority, preemption mode, and
102timeslicing.  When reading the descriptions of timeslicing and
103manual round-robin it is important to keep in mind that
104preemption (if enabled) of a task by higher priority tasks will
105occur as required, overriding the other factors presented in the
108@subsection Task Priority and Scheduling
110@cindex task priority
112This mechanism affects the following scheduling algorithms:
113@itemize @bullet
114@item Priority scheduling
115@end itemize
117The most significant of these mechanisms is the
118ability for the user to assign a priority level to each
119individual task when it is created and to alter a task's
120priority at run-time.  RTEMS provides 255 priority levels.
121Level 255 is the lowest priority and level 1 is the highest.
122When a task is added to the ready chain, it is placed behind all
123other tasks of the same priority.  This rule provides a
124round-robin within priority group scheduling characteristic.
125This means that in a group of equal priority tasks, tasks will
126execute in the order they become ready or FIFO order.  Even
127though there are ways to manipulate and adjust task priorities,
128the most important rule to remember is:
130@itemize @code{ }
131@item @b{The RTEMS scheduler will always select the highest
132priority task that is ready to run when allocating the processor
133to a task.}
134@end itemize
136@subsection Preemption
138@cindex preemption
140This mechanism affects the following scheduling algorithms:
141@itemize @bullet
142@item Priority scheduling
143@end itemize
145Another way the user can alter the basic scheduling
146algorithm is by manipulating the preemption mode flag
147(@code{@value{RPREFIX}PREEMPT_MASK}) of individual tasks.  If preemption is disabled
148for a task (@code{@value{RPREFIX}NO_PREEMPT}), then the task will not relinquish
149control of the processor until it terminates, blocks, or
150re-enables preemption.  Even tasks which become ready to run and
151possess higher priority levels will not be allowed to execute.
152Note that the preemption setting has no effect on the manner in
153which a task is scheduled.  It only applies once a task has
154control of the processor.
156@subsection Timeslicing
158@cindex timeslicing
159@cindex round robin scheduling
161This mechanism affects the following scheduling algorithms:
162@itemize @bullet
163@item Priority scheduling
164@end itemize
166Timeslicing or round-robin scheduling is an
167additional method which can be used to alter the basic
168scheduling algorithm.  Like preemption, timeslicing is specified
169on a task by task basis using the timeslicing mode flag
170(@code{@value{RPREFIX}TIMESLICE_MASK}).  If timeslicing is enabled for a task
171(@code{@value{RPREFIX}TIMESLICE}), then RTEMS will limit the amount of time the task
172can execute before the processor is allocated to another task.
173Each tick of the real-time clock reduces the currently running
174task's timeslice.  When the execution time equals the timeslice,
175RTEMS will dispatch another task of the same priority to
176execute.  If there are no other tasks of the same priority ready
177to execute, then the current task is allocated an additional
178timeslice and continues to run.  Remember that a higher priority
179task will preempt the task (unless preemption is disabled) as
180soon as it is ready to run, even if the task has not used up its
181entire timeslice.
183@subsection Manual Round-Robin
185@cindex manual round robin
187This mechanism affects the following scheduling algorithms:
188@itemize @bullet
189@item Priority scheduling
190@end itemize
192The final mechanism for altering the RTEMS scheduling
193algorithm is called manual round-robin.  Manual round-robin is
194invoked by using the @code{@value{DIRPREFIX}task_wake_after}
195directive with a time interval of @code{@value{RPREFIX}YIELD_PROCESSOR}. 
196This allows a task to give up the
197processor and be immediately returned to the ready chain at the
198end of its priority group.  If no other tasks of the same
199priority are ready to run, then the task does not lose control
200of the processor.
202@section Dispatching Tasks
204@cindex dispatching
206The dispatcher is the RTEMS component responsible for
207allocating the processor to a ready task.  In order to allocate
208the processor to one task, it must be deallocated or retrieved
209from the task currently using it.  This involves a concept
210called a context switch.  To perform a context switch, the
211dispatcher saves the context of the current task and restores
212the context of the task which has been allocated to the
213processor.  Saving and restoring a task's context is the
214storing/loading of all the essential information about a task to
215enable it to continue execution without any effects of the
216interruption.  For example, the contents of a task's register
217set must be the same when it is given the processor as they were
218when it was taken away.  All of the information that must be
219saved or restored for a context switch is located either in the
220TCB or on the task's stacks.
222Tasks that utilize a numeric coprocessor and are
223created with the @code{@value{RPREFIX}FLOATING_POINT} attribute
224require additional operations during a context switch.  These
225additional operations
226are necessary to save and restore the floating point context of
227@code{@value{RPREFIX}FLOATING_POINT} tasks.  To avoid unnecessary save and restore
228operations, the state of the numeric coprocessor is only saved
229when a @code{@value{RPREFIX}FLOATING_POINT} task is dispatched and that task was not
230the last task to utilize the coprocessor.
232@section Task State Transitions
234@cindex task state transitions
236Tasks in an RTEMS system must always be in one of the
237five allowable task states.  These states are: executing, ready,
238blocked, dormant, and non-existent.
240A task occupies the non-existent state before a
241@code{@value{DIRPREFIX}task_create} has been
242issued on its behalf.  A task enters the
243non-existent state from any other state in the system when it is
244deleted with the @code{@value{DIRPREFIX}task_delete}
245directive.  While a task occupies
246this state it does not have a TCB or a task ID assigned to it;
247therefore, no other tasks in the system may reference this task.
249When a task is created via the @code{@value{DIRPREFIX}task_create} directive
250it enters the dormant state.  This state is not entered through
251any other means.  Although the task exists in the system, it
252cannot actively compete for system resources.  It will remain in
253the dormant state until it is started via the @code{@value{DIRPREFIX}task_start}
254directive, at which time it enters the ready state.  The task is
255now permitted to be scheduled for the processor and to compete
256for other system resources.
258@float Figure,fig:RTEMS-Task-States
259@caption{RTEMS Task States}
261@ifset use-ascii
264     +-------------------------------------------------------------+
265     |                         Non-existent                        |
266     |  +-------------------------------------------------------+  |
267     |  |                                                       |  |
268     |  |                                                       |  |
269     |  |      Creating        +---------+     Deleting         |  |
270     |  | -------------------> | Dormant | -------------------> |  |
271     |  |                      +---------+                      |  |
272     |  |                           |                           |  |
273     |  |                  Starting |                           |  |
274     |  |                           |                           |  |
275     |  |                           V          Deleting         |  |
276     |  |             +-------> +-------+ ------------------->  |  |
277     |  |  Yielding  /   +----- | Ready | ------+               |  |
278     |  |           /   /       +-------+ <--+   \              |  |
279     |  |          /   /                      \   \ Blocking    |  |
280     |  |         /   / Dispatching   Readying \   \            |  |
281     |  |        /   V                          \   V           |  |
282     |  |      +-----------+    Blocking     +---------+        |  |
283     |  |      | Executing | --------------> | Blocked |        |  |
284     |  |      +-----------+                 +---------+        |  |
285     |  |                                                       |  |
286     |  |                                                       |  |
287     |  +-------------------------------------------------------+  |
288     |                         Non-existent                        |
289     +-------------------------------------------------------------+
290@end group
291@end example
292@end ifset
294@ifset use-tex
295@c @page
297@center{@image{states,,3in,RTEMS Task States}}
298@end example
299@end ifset
301@ifset use-html
303<IMG SRC="states.png" WIDTH=550 HEIGHT=400 ALT="RTEMS Task States">
304@end html
305@end ifset
306@end float
308A task occupies the blocked state whenever it is
309unable to be scheduled to run.  A running task may block itself
310or be blocked by other tasks in the system.  The running task
311blocks itself through voluntary operations that cause the task
312to wait.  The only way a task can block a task other than itself
313is with the @code{@value{DIRPREFIX}task_suspend} directive. 
314A task enters the blocked state due to any of the following conditions:
316@itemize @bullet
317@item A task issues a @code{@value{DIRPREFIX}task_suspend} directive
318which blocks either itself or another task in the system.
320@item The running task issues a @code{@value{DIRPREFIX}message_queue_receive}
321directive with the wait option and the message queue is empty.
323@item The running task issues an @code{@value{DIRPREFIX}event_receive}
324directive with the wait option and the currently pending events do not
325satisfy the request.
327@item The running task issues a @code{@value{DIRPREFIX}semaphore_obtain}
328directive with the wait option and the requested semaphore is unavailable.
330@item The running task issues a @code{@value{DIRPREFIX}task_wake_after}
331directive which blocks the task for the given time interval.  If the time
332interval specified is zero, the task yields the processor and
333remains in the ready state.
335@item The running task issues a @code{@value{DIRPREFIX}task_wake_when}
336directive which blocks the task until the requested date and time arrives.
338@item The running task issues a @code{@value{DIRPREFIX}region_get_segment}
339directive with the wait option and there is not an available segment large
340enough to satisfy the task's request.
342@item The running task issues a @code{@value{DIRPREFIX}rate_monotonic_period}
343directive and must wait for the specified rate monotonic period
344to conclude.
345@end itemize
347A blocked task may also be suspended.  Therefore,
348both the suspension and the blocking condition must be removed
349before the task becomes ready to run again.
351A task occupies the ready state when it is able to be
352scheduled to run, but currently does not have control of the
353processor.  Tasks of the same or higher priority will yield the
354processor by either becoming blocked, completing their
355timeslice, or being deleted.  All tasks with the same priority
356will execute in FIFO order.  A task enters the ready state due
357to any of the following conditions:
359@itemize @bullet
361@item A running task issues a @code{@value{DIRPREFIX}task_resume}
362directive for a task that is suspended and the task is not blocked
363waiting on any resource.
365@item A running task issues a @code{@value{DIRPREFIX}message_queue_send},
366@code{@value{DIRPREFIX}message_queue_broadcast}, or a
367@code{@value{DIRPREFIX}message_queue_urgent} directive
368which posts a message to the queue on which the blocked task is
371@item A running task issues an @code{@value{DIRPREFIX}event_send}
372directive which sends an event condition to a task which is blocked
373waiting on that event condition.
375@item A running task issues a @code{@value{DIRPREFIX}semaphore_release}
376directive which releases the semaphore on which the blocked task is
379@item A timeout interval expires for a task which was blocked
380by a call to the @code{@value{DIRPREFIX}task_wake_after} directive.
382@item A timeout period expires for a task which blocked by a
383call to the @code{@value{DIRPREFIX}task_wake_when} directive.
385@item A running task issues a @code{@value{DIRPREFIX}region_return_segment}
386directive which releases a segment to the region on which the blocked task
387is waiting and a resulting segment is large enough to satisfy
388the task's request.
390@item A rate monotonic period expires for a task which blocked
391by a call to the @code{@value{DIRPREFIX}rate_monotonic_period} directive.
393@item A timeout interval expires for a task which was blocked
394waiting on a message, event, semaphore, or segment with a
395timeout specified.
397@item A running task issues a directive which deletes a
398message queue, a semaphore, or a region on which the blocked
399task is waiting.
401@item A running task issues a @code{@value{DIRPREFIX}task_restart}
402directive for the blocked task.
404@item The running task, with its preemption mode enabled, may
405be made ready by issuing any of the directives that may unblock
406a task with a higher priority.  This directive may be issued
407from the running task itself or from an ISR.
409A ready task occupies the executing state when it has
410control of the CPU.  A task enters the executing state due to
411any of the following conditions:
413@item The task is the highest priority ready task in the
416@item The running task blocks and the task is next in the
417scheduling queue.  The task may be of equal priority as in
418round-robin scheduling or the task may possess the highest
419priority of the remaining ready tasks.
421@item The running task may reenable its preemption mode and a
422task exists in the ready queue that has a higher priority than
423the running task.
425@item The running task lowers its own priority and another
426task is of higher priority as a result.
428@item The running task raises the priority of a task above its
429own and the running task is in preemption mode.
431@end itemize
Note: See TracBrowser for help on using the repository browser.