source: rtems-docs/c-user/scheduling_concepts.rst @ ba781f9

5
Last change on this file since ba781f9 was ba781f9, checked in by Sebastian Huber <sebastian.huber@…>, on 02/01/17 at 12:32:41

c-user: Move scheduler directives

  • Property mode set to 100644
File size: 25.0 KB
Line 
1.. comment SPDX-License-Identifier: CC-BY-SA-4.0
2
3.. COMMENT: COPYRIGHT (c) 1988-2008.
4.. COMMENT: On-Line Applications Research Corporation (OAR).
5.. COMMENT: All rights reserved.
6
7Scheduling Concepts
8*******************
9
10.. index:: scheduling
11.. index:: task scheduling
12
13Introduction
14============
15
16The concept of scheduling in real-time systems dictates the ability to provide
17immediate response to specific external events, particularly the necessity of
18scheduling tasks to run within a specified time limit after the occurrence of
19an event.  For example, software embedded in life-support systems used to
20monitor hospital patients must take instant action if a change in the patient's
21status is detected.
22
23The component of RTEMS responsible for providing this capability is
24appropriately called the scheduler.  The scheduler's sole purpose is to
25allocate the all important resource of processor time to the various tasks
26competing for attention.
27
28The directives provided by the scheduler manager are:
29
30- rtems_scheduler_ident_ - Get ID of a scheduler
31
32- rtems_scheduler_get_processor_set_ - Get processor set of a scheduler
33
34- rtems_scheduler_add_processor_ - Add processor to a scheduler
35
36- rtems_scheduler_remove_processor_ - Remove processor from a scheduler
37
38Scheduling Algorithms
39=====================
40
41.. index:: scheduling algorithms
42
43RTEMS provides a plugin framework which allows it to support multiple
44scheduling algorithms. RTEMS now includes multiple scheduling algorithms in the
45SuperCore and the user can select which of these they wish to use in their
46application.  In addition, the user can implement their own scheduling
47algorithm and configure RTEMS to use it.
48
49Supporting multiple scheduling algorithms gives the end user the option to
50select the algorithm which is most appropriate to their use case. Most
51real-time operating systems schedule tasks using a priority based algorithm,
52possibly with preemption control.  The classic RTEMS scheduling algorithm which
53was the only algorithm available in RTEMS 4.10 and earlier, is a priority based
54scheduling algorithm.  This scheduling algoritm is suitable for single core
55(e.g. non-SMP) systems and is now known as the *Deterministic Priority
56Scheduler*.  Unless the user configures another scheduling algorithm, RTEMS
57will use this on single core systems.
58
59Priority Scheduling
60-------------------
61.. index:: priority scheduling
62
63When using priority based scheduling, RTEMS allocates the processor using a
64priority-based, preemptive algorithm augmented to provide round-robin
65characteristics within individual priority groups.  The goal of this algorithm
66is to guarantee that the task which is executing on the processor at any point
67in time is the one with the highest priority among all tasks in the ready
68state.
69
70When a task is added to the ready chain, it is placed behind all other tasks of
71the same priority.  This rule provides a round-robin within priority group
72scheduling characteristic.  This means that in a group of equal priority tasks,
73tasks will execute in the order they become ready or FIFO order.  Even though
74there are ways to manipulate and adjust task priorities, the most important
75rule to remember is:
76
77.. note::
78
79  Priority based scheduling algorithms will always select the highest priority
80  task that is ready to run when allocating the processor to a task.
81
82Priority scheduling is the most commonly used scheduling algorithm.  It should
83be used by applications in which multiple tasks contend for CPU time or other
84resources and there is a need to ensure certain tasks are given priority over
85other tasks.
86
87There are a few common methods of accomplishing the mechanics of this
88algorithm.  These ways involve a list or chain of tasks in the ready state.
89
90- The least efficient method is to randomly place tasks in the ready chain
91  forcing the scheduler to scan the entire chain to determine which task
92  receives the processor.
93
94- A more efficient method is to schedule the task by placing it in the proper
95  place on the ready chain based on the designated scheduling criteria at the
96  time it enters the ready state.  Thus, when the processor is free, the first
97  task on the ready chain is allocated the processor.
98
99- Another mechanism is to maintain a list of FIFOs per priority.  When a task
100  is readied, it is placed on the rear of the FIFO for its priority.  This
101  method is often used with a bitmap to assist in locating which FIFOs have
102  ready tasks on them.
103
104RTEMS currently includes multiple priority based scheduling algorithms as well
105as other algorithms which incorporate deadline.  Each algorithm is discussed in
106the following sections.
107
108Deterministic Priority Scheduler
109--------------------------------
110
111This is the scheduler implementation which has always been in RTEMS.  After the
1124.10 release series, it was factored into pluggable scheduler selection.  It
113schedules tasks using a priority based algorithm which takes into account
114preemption.  It is implemented using an array of FIFOs with a FIFO per
115priority.  It maintains a bitmap which is used to track which priorities have
116ready tasks.
117
118This algorithm is deterministic (e.g. predictable and fixed) in execution time.
119This comes at the cost of using slightly over three (3) kilobytes of RAM on a
120system configured to support 256 priority levels.
121
122This scheduler is only aware of a single core.
123
124Simple Priority Scheduler
125-------------------------
126
127This scheduler implementation has the same behaviour as the Deterministic
128Priority Scheduler but uses only one linked list to manage all ready tasks.
129When a task is readied, a linear search of that linked list is performed to
130determine where to insert the newly readied task.
131
132This algorithm uses much less RAM than the Deterministic Priority Scheduler but
133is *O(n)* where *n* is the number of ready tasks.  In a small system with a
134small number of tasks, this will not be a performance issue.  Reducing RAM
135consumption is often critical in small systems which are incapable of
136supporting a large number of tasks.
137
138This scheduler is only aware of a single core.
139
140Simple SMP Priority Scheduler
141-----------------------------
142
143This scheduler is based upon the Simple Priority Scheduler and is designed to
144have the same behaviour on a single core system.  But this scheduler is capable
145of scheduling threads across multiple cores in an SMP system.  When given a
146choice of replacing one of two threads at equal priority on different cores,
147this algorithm favors replacing threads which are preemptible and have executed
148the longest.
149
150This algorithm is non-deterministic. When scheduling, it must consider which
151tasks are to be executed on each core while avoiding superfluous task
152migrations.
153
154Earliest Deadline First Scheduler
155---------------------------------
156.. index:: earliest deadline first scheduling
157
158This is an alternative scheduler in RTEMS for single core applications.  The
159primary EDF advantage is high total CPU utilization (theoretically up to
160100%). It assumes that tasks have priorities equal to deadlines.
161
162This EDF is initially preemptive, however, individual tasks may be declared
163not-preemptive. Deadlines are declared using only Rate Monotonic manager which
164goal is to handle periodic behavior. Period is always equal to deadline. All
165ready tasks reside in a single ready queue implemented using a red-black tree.
166
167This implementation of EDF schedules two different types of task priority types
168while each task may switch between the two types within its execution. If a
169task does have a deadline declared using the Rate Monotonic manager, the task
170is deadline-driven and its priority is equal to deadline.  On the contrary if a
171task does not have any deadline or the deadline is cancelled using the Rate
172Monotonic manager, the task is considered a background task with priority equal
173to that assigned upon initialization in the same manner as for priority
174scheduler. Each background task is of a lower importance than each
175deadline-driven one and is scheduled when no deadline-driven task and no higher
176priority background task is ready to run.
177
178Every deadline-driven scheduling algorithm requires means for tasks to claim a
179deadline.  The Rate Monotonic Manager is responsible for handling periodic
180execution. In RTEMS periods are equal to deadlines, thus if a task announces a
181period, it has to be finished until the end of this period. The call of
182``rtems_rate_monotonic_period`` passes the scheduler the length of oncoming
183deadline. Moreover, the ``rtems_rate_monotonic_cancel`` and
184``rtems_rate_monotonic_delete`` calls clear the deadlines assigned to the task.
185
186Constant Bandwidth Server Scheduling (CBS)
187------------------------------------------
188.. index:: constant bandwidth server scheduling
189
190This is an alternative scheduler in RTEMS for single core applications.  The
191CBS is a budget aware extension of EDF scheduler. The main goal of this
192scheduler is to ensure temporal isolation of tasks meaning that a task's
193execution in terms of meeting deadlines must not be influenced by other tasks
194as if they were run on multiple independent processors.
195
196Each task can be assigned a server (current implementation supports only one
197task per server). The server is characterized by period (deadline) and
198computation time (budget). The ratio budget/period yields bandwidth, which is
199the fraction of CPU to be reserved by the scheduler for each subsequent period.
200
201The CBS is equipped with a set of rules applied to tasks attached to servers
202ensuring that deadline miss because of another task cannot occur.  In case a
203task breaks one of the rules, its priority is pulled to background until the
204end of its period and then restored again. The rules are:
205
206- Task cannot exceed its registered budget,
207
208- Task cannot be unblocked when a ratio between remaining budget and remaining
209  deadline is higher than declared bandwidth.
210
211The CBS provides an extensive API. Unlike EDF, the
212``rtems_rate_monotonic_period`` does not declare a deadline because it is
213carried out using CBS API. This call only announces next period.
214
215Scheduling Modification Mechanisms
216==================================
217
218.. index:: scheduling mechanisms
219
220RTEMS provides four mechanisms which allow the user to alter the task
221scheduling decisions:
222
223- user-selectable task priority level
224
225- task preemption control
226
227- task timeslicing control
228
229- manual round-robin selection
230
231Each of these methods provides a powerful capability to customize sets of tasks
232to satisfy the unique and particular requirements encountered in custom
233real-time applications.  Although each mechanism operates independently, there
234is a precedence relationship which governs the effects of scheduling
235modifications.  The evaluation order for scheduling characteristics is always
236priority, preemption mode, and timeslicing.  When reading the descriptions of
237timeslicing and manual round-robin it is important to keep in mind that
238preemption (if enabled) of a task by higher priority tasks will occur as
239required, overriding the other factors presented in the description.
240
241Task Priority and Scheduling
242----------------------------
243.. index:: task priority
244
245The most significant task scheduling modification mechanism is the ability for
246the user to assign a priority level to each individual task when it is created
247and to alter a task's priority at run-time.  RTEMS supports up to 255 priority
248levels.  Level 255 is the lowest priority and level 1 is the highest.
249
250Preemption
251----------
252.. index:: preemption
253
254Another way the user can alter the basic scheduling algorithm is by
255manipulating the preemption mode flag (``RTEMS_PREEMPT_MASK``) of individual
256tasks.  If preemption is disabled for a task (``RTEMS_NO_PREEMPT``), then the
257task will not relinquish control of the processor until it terminates, blocks,
258or re-enables preemption.  Even tasks which become ready to run and possess
259higher priority levels will not be allowed to execute.  Note that the
260preemption setting has no effect on the manner in which a task is scheduled.
261It only applies once a task has control of the processor.
262
263Timeslicing
264-----------
265.. index:: timeslicing
266.. index:: round robin scheduling
267
268Timeslicing or round-robin scheduling is an additional method which can be used
269to alter the basic scheduling algorithm.  Like preemption, timeslicing is
270specified on a task by task basis using the timeslicing mode flag
271(``RTEMS_TIMESLICE_MASK``).  If timeslicing is enabled for a task
272(``RTEMS_TIMESLICE``), then RTEMS will limit the amount of time the task can
273execute before the processor is allocated to another task.  Each tick of the
274real-time clock reduces the currently running task's timeslice.  When the
275execution time equals the timeslice, RTEMS will dispatch another task of the
276same priority to execute.  If there are no other tasks of the same priority
277ready to execute, then the current task is allocated an additional timeslice
278and continues to run.  Remember that a higher priority task will preempt the
279task (unless preemption is disabled) as soon as it is ready to run, even if the
280task has not used up its entire timeslice.
281
282Manual Round-Robin
283------------------
284.. index:: manual round robin
285
286The final mechanism for altering the RTEMS scheduling algorithm is called
287manual round-robin.  Manual round-robin is invoked by using
288the ``rtems_task_wake_after`` directive with a time interval of
289``RTEMS_YIELD_PROCESSOR``.  This allows a task to give up the processor and be
290immediately returned to the ready chain at the end of its priority group.  If
291no other tasks of the same priority are ready to run, then the task does not
292lose control of the processor.
293
294Dispatching Tasks
295=================
296.. index:: dispatching
297
298The dispatcher is the RTEMS component responsible for allocating the processor
299to a ready task.  In order to allocate the processor to one task, it must be
300deallocated or retrieved from the task currently using it.  This involves a
301concept called a context switch.  To perform a context switch, the dispatcher
302saves the context of the current task and restores the context of the task
303which has been allocated to the processor.  Saving and restoring a task's
304context is the storing/loading of all the essential information about a task to
305enable it to continue execution without any effects of the interruption.  For
306example, the contents of a task's register set must be the same when it is
307given the processor as they were when it was taken away.  All of the
308information that must be saved or restored for a context switch is located
309either in the TCB or on the task's stacks.
310
311Tasks that utilize a numeric coprocessor and are created with the
312``RTEMS_FLOATING_POINT`` attribute require additional operations during a
313context switch.  These additional operations are necessary to save and restore
314the floating point context of ``RTEMS_FLOATING_POINT`` tasks.  To avoid
315unnecessary save and restore operations, the state of the numeric coprocessor
316is only saved when a ``RTEMS_FLOATING_POINT`` task is dispatched and that task
317was not the last task to utilize the coprocessor.
318
319Task State Transitions
320======================
321.. index:: task state transitions
322
323Tasks in an RTEMS system must always be in one of the five allowable task
324states.  These states are: executing, ready, blocked, dormant, and
325non-existent.
326
327A task occupies the non-existent state before a ``rtems_task_create`` has been
328issued on its behalf.  A task enters the non-existent state from any other
329state in the system when it is deleted with the ``rtems_task_delete``
330directive.  While a task occupies this state it does not have a TCB or a task
331ID assigned to it; therefore, no other tasks in the system may reference this
332task.
333
334When a task is created via the ``rtems_task_create`` directive it enters the
335dormant state.  This state is not entered through any other means.  Although
336the task exists in the system, it cannot actively compete for system resources.
337It will remain in the dormant state until it is started via the
338``rtems_task_start`` directive, at which time it enters the ready state.  The
339task is now permitted to be scheduled for the processor and to compete for
340other system resources.
341
342.. figure:: ../images/c_user/states.png
343         :width: 70%
344         :align: center
345         :alt: Task State Transitions
346
347A task occupies the blocked state whenever it is unable to be scheduled to run.
348A running task may block itself or be blocked by other tasks in the system.
349The running task blocks itself through voluntary operations that cause the task
350to wait.  The only way a task can block a task other than itself is with the
351``rtems_task_suspend`` directive.  A task enters the blocked state due to any
352of the following conditions:
353
354- A task issues a ``rtems_task_suspend`` directive which blocks either itself
355  or another task in the system.
356
357- The running task issues a ``rtems_barrier_wait`` directive.
358
359- The running task issues a ``rtems_message_queue_receive`` directive with the
360  wait option and the message queue is empty.
361
362- The running task issues an ``rtems_event_receive`` directive with the wait
363  option and the currently pending events do not satisfy the request.
364
365- The running task issues a ``rtems_semaphore_obtain`` directive with the wait
366  option and the requested semaphore is unavailable.
367
368- The running task issues a ``rtems_task_wake_after`` directive which blocks
369  the task for the given time interval.  If the time interval specified is
370  zero, the task yields the processor and remains in the ready state.
371
372- The running task issues a ``rtems_task_wake_when`` directive which blocks the
373  task until the requested date and time arrives.
374
375- The running task issues a ``rtems_rate_monotonic_period`` directive and must
376  wait for the specified rate monotonic period to conclude.
377
378- The running task issues a ``rtems_region_get_segment`` directive with the
379  wait option and there is not an available segment large enough to satisfy the
380  task's request.
381
382A blocked task may also be suspended.  Therefore, both the suspension and the
383blocking condition must be removed before the task becomes ready to run again.
384
385A task occupies the ready state when it is able to be scheduled to run, but
386currently does not have control of the processor.  Tasks of the same or higher
387priority will yield the processor by either becoming blocked, completing their
388timeslice, or being deleted.  All tasks with the same priority will execute in
389FIFO order.  A task enters the ready state due to any of the following
390conditions:
391
392- A running task issues a ``rtems_task_resume`` directive for a task that is
393  suspended and the task is not blocked waiting on any resource.
394
395- A running task issues a ``rtems_message_queue_send``,
396  ``rtems_message_queue_broadcast``, or a ``rtems_message_queue_urgent``
397  directive which posts a message to the queue on which the blocked task is
398  waiting.
399
400- A running task issues an ``rtems_event_send`` directive which sends an event
401  condition to a task which is blocked waiting on that event condition.
402
403- A running task issues a ``rtems_semaphore_release`` directive which releases
404  the semaphore on which the blocked task is waiting.
405
406- A timeout interval expires for a task which was blocked by a call to the
407  ``rtems_task_wake_after`` directive.
408
409- A timeout period expires for a task which blocked by a call to the
410  ``rtems_task_wake_when`` directive.
411
412- A running task issues a ``rtems_region_return_segment`` directive which
413  releases a segment to the region on which the blocked task is waiting and a
414  resulting segment is large enough to satisfy the task's request.
415
416- A rate monotonic period expires for a task which blocked by a call to the
417  ``rtems_rate_monotonic_period`` directive.
418
419- A timeout interval expires for a task which was blocked waiting on a message,
420  event, semaphore, or segment with a timeout specified.
421
422- A running task issues a directive which deletes a message queue, a semaphore,
423  or a region on which the blocked task is waiting.
424
425- A running task issues a ``rtems_task_restart`` directive for the blocked
426  task.
427
428- The running task, with its preemption mode enabled, may be made ready by
429  issuing any of the directives that may unblock a task with a higher priority.
430  This directive may be issued from the running task itself or from an ISR.  A
431  ready task occupies the executing state when it has control of the CPU.  A
432  task enters the executing state due to any of the following conditions:
433
434- The task is the highest priority ready task in the system.
435
436- The running task blocks and the task is next in the scheduling queue.  The
437  task may be of equal priority as in round-robin scheduling or the task may
438  possess the highest priority of the remaining ready tasks.
439
440- The running task may reenable its preemption mode and a task exists in the
441  ready queue that has a higher priority than the running task.
442
443- The running task lowers its own priority and another task is of higher
444  priority as a result.
445
446- The running task raises the priority of a task above its own and the running
447  task is in preemption mode.
448
449Directives
450==========
451
452This section details the scheduler manager.  A subsection is dedicated to each
453of these services and describes the calling sequence, related constants, usage,
454and status codes.
455
456.. raw:: latex
457
458   \clearpage
459
460.. _rtems_scheduler_ident:
461
462SCHEDULER_IDENT - Get ID of a scheduler
463---------------------------------------
464
465CALLING SEQUENCE:
466    .. code-block:: c
467
468        rtems_status_code rtems_scheduler_ident(
469            rtems_name  name,
470            rtems_id   *id
471        );
472
473DIRECTIVE STATUS CODES:
474    .. list-table::
475     :class: rtems-table
476
477     * - ``RTEMS_SUCCESSFUL``
478       - Successful operation.
479     * - ``RTEMS_INVALID_ADDRESS``
480       - The ``id`` parameter is ``NULL``.
481     * - ``RTEMS_INVALID_NAME``
482       - Invalid scheduler name.
483
484DESCRIPTION:
485    Identifies a scheduler by its name.  The scheduler name is determined by
486    the scheduler configuration.  See :ref:`Configuring Clustered Schedulers`
487    and :ref:`Configuring a Scheduler Name`.
488
489NOTES:
490    None.
491
492.. raw:: latex
493
494   \clearpage
495
496.. _rtems_scheduler_get_processor_set:
497
498SCHEDULER_GET_PROCESSOR_SET - Get processor set of a scheduler
499--------------------------------------------------------------
500
501CALLING SEQUENCE:
502    .. code-block:: c
503
504        rtems_status_code rtems_scheduler_get_processor_set(
505            rtems_id   scheduler_id,
506            size_t     cpusetsize,
507            cpu_set_t *cpuset
508        );
509
510DIRECTIVE STATUS CODES:
511    .. list-table::
512     :class: rtems-table
513
514     * - ``RTEMS_SUCCESSFUL``
515       - Successful operation.
516     * - ``RTEMS_INVALID_ID``
517       - Invalid scheduler instance identifier.
518     * - ``RTEMS_INVALID_ADDRESS``
519       - The ``cpuset`` parameter is ``NULL``.
520     * - ``RTEMS_INVALID_NUMBER``
521       - The processor set buffer is too small for the set of processors owned
522         by the scheduler instance.
523
524DESCRIPTION:
525    Returns the processor set owned by the scheduler instance in ``cpuset``.  A
526    set bit in the processor set means that this processor is owned by the
527    scheduler instance and a cleared bit means the opposite.
528
529NOTES:
530    None.
531
532.. raw:: latex
533
534   \clearpage
535
536.. _rtems_scheduler_add_processor:
537
538SCHEDULER_ADD_PROCESSOR - Add processor to a scheduler
539------------------------------------------------------
540
541CALLING SEQUENCE:
542    .. code-block:: c
543
544        rtems_status_code rtems_scheduler_add_processor(
545            rtems_id scheduler_id,
546            uint32_t cpu_index
547        );
548
549DIRECTIVE STATUS CODES:
550    .. list-table::
551     :class: rtems-table
552
553     * - ``RTEMS_SUCCESSFUL``
554       - Successful operation.
555     * - ``RTEMS_INVALID_ID``
556       - Invalid scheduler instance identifier.
557     * - ``RTEMS_NOT_CONFIGURED``
558       - The processor is not configured to be used by the application.
559     * - ``RTEMS_INCORRECT_STATE``
560       - The processor is configured to be used by the application, however, it
561         is not online.
562     * - ``RTEMS_RESOURCE_IN_USE``
563       - The processor is already assigned to a scheduler instance.
564
565DESCRIPTION:
566    Adds a processor to the set of processors owned by the specified scheduler
567    instance.
568
569NOTES:
570    Must be called from task context.  This operation obtains and releases the
571    objects allocator lock.
572
573.. raw:: latex
574
575   \clearpage
576
577.. _rtems_scheduler_remove_processor:
578
579SCHEDULER_REMOVE_PROCESSOR - Remove processor from a scheduler
580--------------------------------------------------------------
581
582CALLING SEQUENCE:
583    .. code-block:: c
584
585        rtems_status_code rtems_scheduler_remove_processor(
586            rtems_id scheduler_id,
587            uint32_t cpu_index
588        );
589
590DIRECTIVE STATUS CODES:
591    .. list-table::
592     :class: rtems-table
593
594     * - ``RTEMS_SUCCESSFUL``
595       - Successful operation.
596     * - ``RTEMS_INVALID_ID``
597       - Invalid scheduler instance identifier.
598     * - ``RTEMS_INVALID_NUMBER``
599       - The processor is not owned by the specified scheduler instance.
600     * - ``RTEMS_RESOURCE_IN_USE``
601       - The set of processors owned by the specified scheduler instance would
602         be empty after the processor removal and there exists a non-idle task
603         that uses this scheduler instance as its home scheduler instance.
604
605DESCRIPTION:
606    Removes a processor from set of processors owned by the specified scheduler
607    instance.
608
609NOTES:
610    Must be called from task context.  This operation obtains and releases the
611    objects allocator lock.  Removing a processor from a scheduler is a complex
612    operation that involves all tasks of the system.
Note: See TracBrowser for help on using the repository browser.