source: rtems/doc/user/schedule.t @ 6449498
Last change on this file since 6449498 was 6449498, checked in by Joel Sherrill <joel.sherrill@…>, on Jan 17, 2002 at 9:47:47 PM

2001-01-17 Joel Sherrill <joel@…>

  • SUPPORT, LICENSE: New files.
  • Numerous files touched as part of merging the 4.5 branch onto the mainline development trunk and ensuring that the script that cuts snapshots and releases works on the documentation.
  • Property mode set to 100644
File size: 17.4 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
33attention.  The RTEMS scheduler allocates the processor using a
34priority-based, preemptive algorithm augmented to provide
35round-robin characteristics within individual priority groups.
36The goal of this algorithm is to guarantee that the task which
37is executing on the processor at any point in time is the one
38with the highest priority among all tasks in the ready state.
40There are two common methods of accomplishing the
41mechanics of this algorithm.  Both ways involve a list or chain
42of tasks in the ready state.  One method is to randomly place
43tasks in the ready chain forcing the scheduler to scan the
44entire chain to determine which task receives the processor.
45The other method is to schedule the task by placing it in the
46proper place on the ready chain based on the designated
47scheduling criteria at the time it enters the ready state.
48Thus, when the processor is free, the first task on the ready
49chain is allocated the processor.  RTEMS schedules tasks using
50the second method to guarantee faster response times to external
53@section Scheduling Mechanisms
55@cindex scheduling mechanisms
57RTEMS provides four mechanisms which allow the user
58to impact the task scheduling process:
60@itemize @bullet
61@item user-selectable task priority level
62@item task preemption control
63@item task timeslicing control
64@item manual round-robin selection
65@end itemize
67Each of these methods provides a powerful capability
68to customize sets of tasks to satisfy the unique and particular
69requirements encountered in custom real-time applications.
70Although each mechanism operates independently, there is a
71precedence relationship which governs the effects of scheduling
72modifications.  The evaluation order for scheduling
73characteristics is always priority, preemption mode, and
74timeslicing.  When reading the descriptions of timeslicing and
75manual round-robin it is important to keep in mind that
76preemption (if enabled) of a task by higher priority tasks will
77occur as required, overriding the other factors presented in the
80@subsection Task Priority and Scheduling
82@cindex task priority
84The most significant of these mechanisms is the
85ability for the user to assign a priority level to each
86individual task when it is created and to alter a task's
87priority at run-time.  RTEMS provides 255 priority levels.
88Level 255 is the lowest priority and level 1 is the highest.
89When a task is added to the ready chain, it is placed behind all
90other tasks of the same priority.  This rule provides a
91round-robin within priority group scheduling characteristic.
92This means that in a group of equal priority tasks, tasks will
93execute in the order they become ready or FIFO order.  Even
94though there are ways to manipulate and adjust task priorities,
95the most important rule to remember is:
97@itemize @code{ }
98@item @b{The RTEMS scheduler will always select the highest
99priority task that is ready to run when allocating the processor
100to a task.}
101@end itemize
103@subsection Preemption
105@cindex preemption
107Another way the user can alter the basic scheduling
108algorithm is by manipulating the preemption mode flag
109(@code{@value{RPREFIX}PREEMPT_MASK}) of individual tasks.  If preemption is disabled
110for a task (@code{@value{RPREFIX}NO_PREEMPT}), then the task will not relinquish
111control of the processor until it terminates, blocks, or
112re-enables preemption.  Even tasks which become ready to run and
113possess higher priority levels will not be allowed to execute.
114Note that the preemption setting has no effect on the manner in
115which a task is scheduled.  It only applies once a task has
116control of the processor.
118@subsection Timeslicing
120@cindex timeslicing
121@cindex round robin scheduling
123Timeslicing or round-robin scheduling is an
124additional method which can be used to alter the basic
125scheduling algorithm.  Like preemption, timeslicing is specified
126on a task by task basis using the timeslicing mode flag
127(@code{@value{RPREFIX}TIMESLICE_MASK}).  If timeslicing is enabled for a task
128(@code{@value{RPREFIX}TIMESLICE}), then RTEMS will limit the amount of time the task
129can execute before the processor is allocated to another task.
130Each tick of the real-time clock reduces the currently running
131task's timeslice.  When the execution time equals the timeslice,
132RTEMS will dispatch another task of the same priority to
133execute.  If there are no other tasks of the same priority ready
134to execute, then the current task is allocated an additional
135timeslice and continues to run.  Remember that a higher priority
136task will preempt the task (unless preemption is disabled) as
137soon as it is ready to run, even if the task has not used up its
138entire timeslice.
140@subsection Manual Round-Robin
142@cindex manual round robin
144The final mechanism for altering the RTEMS scheduling
145algorithm is called manual round-robin.  Manual round-robin is
146invoked by using the @code{@value{DIRPREFIX}task_wake_after}
147directive with a time interval of @code{@value{RPREFIX}YIELD_PROCESSOR}. 
148This allows a task to give up the
149processor and be immediately returned to the ready chain at the
150end of its priority group.  If no other tasks of the same
151priority are ready to run, then the task does not lose control
152of the processor.
154@subsection Dispatching Tasks
156@cindex dispatching
158The dispatcher is the RTEMS component responsible for
159allocating the processor to a ready task.  In order to allocate
160the processor to one task, it must be deallocated or retrieved
161from the task currently using it.  This involves a concept
162called a context switch.  To perform a context switch, the
163dispatcher saves the context of the current task and restores
164the context of the task which has been allocated to the
165processor.  Saving and restoring a task's context is the
166storing/loading of all the essential information about a task to
167enable it to continue execution without any effects of the
168interruption.  For example, the contents of a task's register
169set must be the same when it is given the processor as they were
170when it was taken away.  All of the information that must be
171saved or restored for a context switch is located either in the
172TCB or on the task's stacks.
174Tasks that utilize a numeric coprocessor and are
175created with the @code{@value{RPREFIX}FLOATING_POINT} attribute
176require additional operations during a context switch.  These
177additional operations
178are necessary to save and restore the floating point context of
179@code{@value{RPREFIX}FLOATING_POINT} tasks.  To avoid unnecessary save and restore
180operations, the state of the numeric coprocessor is only saved
181when a @code{@value{RPREFIX}FLOATING_POINT} task is dispatched and that task was not
182the last task to utilize the coprocessor.
184@section Task State Transitions
186@cindex task state transitions
188Tasks in an RTEMS system must always be in one of the
189five allowable task states.  These states are: executing, ready,
190blocked, dormant, and non-existent.
192A task occupies the non-existent state before a
193@code{@value{DIRPREFIX}task_create} has been
194issued on its behalf.  A task enters the
195non-existent state from any other state in the system when it is
196deleted with the @code{@value{DIRPREFIX}task_delete}
197directive.  While a task occupies
198this state it does not have a TCB or a task ID assigned to it;
199therefore, no other tasks in the system may reference this task.
201When a task is created via the @code{@value{DIRPREFIX}task_create} directive
202it enters the dormant state.  This state is not entered through
203any other means.  Although the task exists in the system, it
204cannot actively compete for system resources.  It will remain in
205the dormant state until it is started via the @code{@value{DIRPREFIX}task_start}
206directive, at which time it enters the ready state.  The task is
207now permitted to be scheduled for the processor and to compete
208for other system resources.
210@ifset use-ascii
213     +-------------------------------------------------------------+
214     |                         Non-existent                        |
215     |  +-------------------------------------------------------+  |
216     |  |                                                       |  |
217     |  |                                                       |  |
218     |  |      Creating        +---------+     Deleting         |  |
219     |  | -------------------> | Dormant | -------------------> |  |
220     |  |                      +---------+                      |  |
221     |  |                           |                           |  |
222     |  |                  Starting |                           |  |
223     |  |                           |                           |  |
224     |  |                           V          Deleting         |  |
225     |  |             +-------> +-------+ ------------------->  |  |
226     |  |  Yielding  /   +----- | Ready | ------+               |  |
227     |  |           /   /       +-------+ <--+   \              |  |
228     |  |          /   /                      \   \ Blocking    |  |
229     |  |         /   / Dispatching   Readying \   \            |  |
230     |  |        /   V                          \   V           |  |
231     |  |      +-----------+    Blocking     +---------+        |  |
232     |  |      | Executing | --------------> | Blocked |        |  |
233     |  |      +-----------+                 +---------+        |  |
234     |  |                                                       |  |
235     |  |                                                       |  |
236     |  +-------------------------------------------------------+  |
237     |                         Non-existent                        |
238     +-------------------------------------------------------------+
239@end group
240@end example
241@end ifset
243@ifset use-tex
244@c @page
247@c @group
248@c      +-------------------------------------------------------------+
249@c      |                         Non-existent                        |
250@c      |  +-------------------------------------------------------+  |
251@c      |  |                                                       |  |
252@c      |  |                                                       |  |
253@c      |  |      Creating        +---------+     Deleting         |  |
254@c      |  | -------------------> | Dormant | -------------------> |  |
255@c      |  |                      +---------+                      |  |
256@c      |  |                           |                           |  |
257@c      |  |                  Starting |                           |  |
258@c      |  |                           |                           |  |
259@c      |  |                           V          Deleting         |  |
260@c      |  |             +-------> +-------+ ------------------->  |  |
261@c      |  |  Yielding  /   +----- | Ready | ------+               |  |
262@c      |  |           /   /       +-------+ <--+   \              |  |
263@c      |  |          /   /                      \   \ Blocking    |  |
264@c      |  |         /   / Dispatching   Readying \   \            |  |
265@c      |  |        /   V                          \   V           |  |
266@c      |  |      +-----------+    Blocking     +---------+        |  |
267@c      |  |      | Executing | --------------> | Blocked |        |  |
268@c      |  |      +-----------+                 +---------+        |  |
269@c      |  |                                                       |  |
270@c      |  |                                                       |  |
271@c      |  +-------------------------------------------------------+  |
272@c      |                         Non-existent                        |
273@c      +-------------------------------------------------------------+
274@c @end group
275@end example
276@end ifset
278@ifset use-html
280<IMG SRC="states.png" WIDTH=550 HEIGHT=400 ALT="RTEMS Task States">
281@end html
282@end ifset
284A task occupies the blocked state whenever it is
285unable to be scheduled to run.  A running task may block itself
286or be blocked by other tasks in the system.  The running task
287blocks itself through voluntary operations that cause the task
288to wait.  The only way a task can block a task other than itself
289is with the @code{@value{DIRPREFIX}task_suspend} directive. 
290A task enters the blocked state due to any of the following conditions:
292@itemize @bullet
293@item A task issues a @code{@value{DIRPREFIX}task_suspend} directive
294which blocks either itself or another task in the system.
296@item The running task issues a @code{@value{DIRPREFIX}message_queue_receive}
297directive with the wait option and the message queue is empty.
299@item The running task issues an @code{@value{DIRPREFIX}event_receive}
300directive with the wait option and the currently pending events do not
301satisfy the request.
303@item The running task issues a @code{@value{DIRPREFIX}semaphore_obtain}
304directive with the wait option and the requested semaphore is unavailable.
306@item The running task issues a @code{@value{DIRPREFIX}task_wake_after}
307directive which blocks the task for the given time interval.  If the time
308interval specified is zero, the task yields the processor and
309remains in the ready state.
311@item The running task issues a @code{@value{DIRPREFIX}task_wake_when}
312directive which blocks the task until the requested date and time arrives.
314@item The running task issues a @code{@value{DIRPREFIX}region_get_segment}
315directive with the wait option and there is not an available segment large
316enough to satisfy the task's request.
318@item The running task issues a @code{@value{DIRPREFIX}rate_monotonic_period}
319directive and must wait for the specified rate monotonic period
320to conclude.
321@end itemize
323A blocked task may also be suspended.  Therefore,
324both the suspension and the blocking condition must be removed
325before the task becomes ready to run again.
327A task occupies the ready state when it is able to be
328scheduled to run, but currently does not have control of the
329processor.  Tasks of the same or higher priority will yield the
330processor by either becoming blocked, completing their
331timeslice, or being deleted.  All tasks with the same priority
332will execute in FIFO order.  A task enters the ready state due
333to any of the following conditions:
335@itemize @bullet
337@item A running task issues a @code{@value{DIRPREFIX}task_resume}
338directive for a task that is suspended and the task is not blocked
339waiting on any resource.
341@item A running task issues a @code{@value{DIRPREFIX}message_queue_send},
342@code{@value{DIRPREFIX}message_queue_broadcast}, or a
343@code{@value{DIRPREFIX}message_queue_urgent} directive
344which posts a message to the queue on which the blocked task is
347@item A running task issues an @code{@value{DIRPREFIX}event_send}
348directive which sends an event condition to a task which is blocked
349waiting on that event condition.
351@item A running task issues a @code{@value{DIRPREFIX}semaphore_release}
352directive which releases the semaphore on which the blocked task is
355@item A timeout interval expires for a task which was blocked
356by a call to the @code{@value{DIRPREFIX}task_wake_after} directive.
358@item A timeout period expires for a task which blocked by a
359call to the @code{@value{DIRPREFIX}task_wake_when} directive.
361@item A running task issues a @code{@value{DIRPREFIX}region_return_segment}
362directive which releases a segment to the region on which the blocked task
363is waiting and a resulting segment is large enough to satisfy
364the task's request.
366@item A rate monotonic period expires for a task which blocked
367by a call to the @code{@value{DIRPREFIX}rate_monotonic_period} directive.
369@item A timeout interval expires for a task which was blocked
370waiting on a message, event, semaphore, or segment with a
371timeout specified.
373@item A running task issues a directive which deletes a
374message queue, a semaphore, or a region on which the blocked
375task is waiting.
377@item A running task issues a @code{@value{DIRPREFIX}task_restart}
378directive for the blocked task.
380@item The running task, with its preemption mode enabled, may
381be made ready by issuing any of the directives that may unblock
382a task with a higher priority.  This directive may be issued
383from the running task itself or from an ISR.
385A ready task occupies the executing state when it has
386control of the CPU.  A task enters the executing state due to
387any of the following conditions:
389@item The task is the highest priority ready task in the
392@item The running task blocks and the task is next in the
393scheduling queue.  The task may be of equal priority as in
394round-robin scheduling or the task may possess the highest
395priority of the remaining ready tasks.
397@item The running task may reenable its preemption mode and a
398task exists in the ready queue that has a higher priority than
399the running task.
401@item The running task lowers its own priority and another
402task is of higher priority as a result.
404@item The running task raises the priority of a task above its
405own and the running task is in preemption mode.
407@end itemize
Note: See TracBrowser for help on using the repository browser.