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

4.104.11
Last change on this file since bd861cc6 was bd861cc6, checked in by Joel Sherrill <joel.sherrill@…>, on Nov 9, 2009 at 2:36:14 PM

2009-11-09 Joel Sherrill <joel.sherrill@…>

  • ada_user/Makefile.am, ada_user/ada_user.texi, user/Makefile.am, user/c_user.texi, user/concepts.t, user/overview.t, user/preface.texi, user/schedule.t, user/sem.t: Add table of figures. Add text and graphic of tree illustrating valid combinations of semaphore attributes.
  • user/semaphore_attributes.eps, user/semaphore_attributes.png: New files.
  • Property mode set to 100644
File size: 15.7 KB
Line 
1@c
2@c  COPYRIGHT (c) 1988-2002.
3@c  On-Line Applications Research Corporation (OAR).
4@c  All rights reserved.
5@c
6@c  $Id$
7@c
8
9@c
10@c   This figure is not included:
11@c      Figure 17-1  RTEMS Task State Transitions
12@c
13
14@chapter Scheduling Concepts
15
16@cindex scheduling
17@cindex task scheduling
18
19@section Introduction
20
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.
28
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.
39
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
51events.
52
53@section Scheduling Mechanisms
54
55@cindex scheduling mechanisms
56
57RTEMS provides four mechanisms which allow the user
58to impact the task scheduling process:
59
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
66
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
78description.
79
80@subsection Task Priority and Scheduling
81
82@cindex task priority
83
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:
96
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
102
103@subsection Preemption
104
105@cindex preemption
106
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.
117
118@subsection Timeslicing
119
120@cindex timeslicing
121@cindex round robin scheduling
122
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.
139
140@subsection Manual Round-Robin
141
142@cindex manual round robin
143
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.
153
154@subsection Dispatching Tasks
155
156@cindex dispatching
157
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.
173
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.
183
184@section Task State Transitions
185
186@cindex task state transitions
187
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.
191
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.
200
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.
209
210@float Figure,fig:RTEMS-Task-States
211@caption{RTEMS Task States}
212
213@ifset use-ascii
214@example
215@group
216     +-------------------------------------------------------------+
217     |                         Non-existent                        |
218     |  +-------------------------------------------------------+  |
219     |  |                                                       |  |
220     |  |                                                       |  |
221     |  |      Creating        +---------+     Deleting         |  |
222     |  | -------------------> | Dormant | -------------------> |  |
223     |  |                      +---------+                      |  |
224     |  |                           |                           |  |
225     |  |                  Starting |                           |  |
226     |  |                           |                           |  |
227     |  |                           V          Deleting         |  |
228     |  |             +-------> +-------+ ------------------->  |  |
229     |  |  Yielding  /   +----- | Ready | ------+               |  |
230     |  |           /   /       +-------+ <--+   \              |  |
231     |  |          /   /                      \   \ Blocking    |  |
232     |  |         /   / Dispatching   Readying \   \            |  |
233     |  |        /   V                          \   V           |  |
234     |  |      +-----------+    Blocking     +---------+        |  |
235     |  |      | Executing | --------------> | Blocked |        |  |
236     |  |      +-----------+                 +---------+        |  |
237     |  |                                                       |  |
238     |  |                                                       |  |
239     |  +-------------------------------------------------------+  |
240     |                         Non-existent                        |
241     +-------------------------------------------------------------+
242@end group
243@end example
244@end ifset
245
246@ifset use-tex
247@c @page
248@example
249@center{@image{states,,3in,RTEMS Task States}}
250@end example
251@end ifset
252
253@ifset use-html
254@html
255<IMG SRC="states.png" WIDTH=550 HEIGHT=400 ALT="RTEMS Task States">
256@end html
257@end ifset
258@end float
259
260A task occupies the blocked state whenever it is
261unable to be scheduled to run.  A running task may block itself
262or be blocked by other tasks in the system.  The running task
263blocks itself through voluntary operations that cause the task
264to wait.  The only way a task can block a task other than itself
265is with the @code{@value{DIRPREFIX}task_suspend} directive. 
266A task enters the blocked state due to any of the following conditions:
267
268@itemize @bullet
269@item A task issues a @code{@value{DIRPREFIX}task_suspend} directive
270which blocks either itself or another task in the system.
271
272@item The running task issues a @code{@value{DIRPREFIX}message_queue_receive}
273directive with the wait option and the message queue is empty.
274
275@item The running task issues an @code{@value{DIRPREFIX}event_receive}
276directive with the wait option and the currently pending events do not
277satisfy the request.
278
279@item The running task issues a @code{@value{DIRPREFIX}semaphore_obtain}
280directive with the wait option and the requested semaphore is unavailable.
281
282@item The running task issues a @code{@value{DIRPREFIX}task_wake_after}
283directive which blocks the task for the given time interval.  If the time
284interval specified is zero, the task yields the processor and
285remains in the ready state.
286
287@item The running task issues a @code{@value{DIRPREFIX}task_wake_when}
288directive which blocks the task until the requested date and time arrives.
289
290@item The running task issues a @code{@value{DIRPREFIX}region_get_segment}
291directive with the wait option and there is not an available segment large
292enough to satisfy the task's request.
293
294@item The running task issues a @code{@value{DIRPREFIX}rate_monotonic_period}
295directive and must wait for the specified rate monotonic period
296to conclude.
297@end itemize
298
299A blocked task may also be suspended.  Therefore,
300both the suspension and the blocking condition must be removed
301before the task becomes ready to run again.
302
303A task occupies the ready state when it is able to be
304scheduled to run, but currently does not have control of the
305processor.  Tasks of the same or higher priority will yield the
306processor by either becoming blocked, completing their
307timeslice, or being deleted.  All tasks with the same priority
308will execute in FIFO order.  A task enters the ready state due
309to any of the following conditions:
310
311@itemize @bullet
312
313@item A running task issues a @code{@value{DIRPREFIX}task_resume}
314directive for a task that is suspended and the task is not blocked
315waiting on any resource.
316
317@item A running task issues a @code{@value{DIRPREFIX}message_queue_send},
318@code{@value{DIRPREFIX}message_queue_broadcast}, or a
319@code{@value{DIRPREFIX}message_queue_urgent} directive
320which posts a message to the queue on which the blocked task is
321waiting.
322
323@item A running task issues an @code{@value{DIRPREFIX}event_send}
324directive which sends an event condition to a task which is blocked
325waiting on that event condition.
326
327@item A running task issues a @code{@value{DIRPREFIX}semaphore_release}
328directive which releases the semaphore on which the blocked task is
329waiting.
330
331@item A timeout interval expires for a task which was blocked
332by a call to the @code{@value{DIRPREFIX}task_wake_after} directive.
333
334@item A timeout period expires for a task which blocked by a
335call to the @code{@value{DIRPREFIX}task_wake_when} directive.
336
337@item A running task issues a @code{@value{DIRPREFIX}region_return_segment}
338directive which releases a segment to the region on which the blocked task
339is waiting and a resulting segment is large enough to satisfy
340the task's request.
341
342@item A rate monotonic period expires for a task which blocked
343by a call to the @code{@value{DIRPREFIX}rate_monotonic_period} directive.
344
345@item A timeout interval expires for a task which was blocked
346waiting on a message, event, semaphore, or segment with a
347timeout specified.
348
349@item A running task issues a directive which deletes a
350message queue, a semaphore, or a region on which the blocked
351task is waiting.
352
353@item A running task issues a @code{@value{DIRPREFIX}task_restart}
354directive for the blocked task.
355
356@item The running task, with its preemption mode enabled, may
357be made ready by issuing any of the directives that may unblock
358a task with a higher priority.  This directive may be issued
359from the running task itself or from an ISR.
360
361A ready task occupies the executing state when it has
362control of the CPU.  A task enters the executing state due to
363any of the following conditions:
364
365@item The task is the highest priority ready task in the
366system.
367
368@item The running task blocks and the task is next in the
369scheduling queue.  The task may be of equal priority as in
370round-robin scheduling or the task may possess the highest
371priority of the remaining ready tasks.
372
373@item The running task may reenable its preemption mode and a
374task exists in the ready queue that has a higher priority than
375the running task.
376
377@item The running task lowers its own priority and another
378task is of higher priority as a result.
379
380@item The running task raises the priority of a task above its
381own and the running task is in preemption mode.
382
383@end itemize
Note: See TracBrowser for help on using the repository browser.