source: rtems/doc/user/schedule.t @ 1e524995

4.104.114.84.95
Last change on this file since 1e524995 was 1e524995, checked in by Joel Sherrill <joel.sherrill@…>, on 02/06/98 at 14:14:30

Updated copyrights

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