Changeset 9037998 in rtems-docs


Ignore:
Timestamp:
Jul 7, 2017, 1:50:51 PM (2 years ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
master
Children:
a31dbcb
Parents:
8cf3d75
git-author:
Sebastian Huber <sebastian.huber@…> (07/07/17 13:50:51)
git-committer:
Sebastian Huber <sebastian.huber@…> (07/10/17 07:48:43)
Message:

c-user: Update scheduler/task chapter

Reflect EDF SMP scheduler changes.

Close #3059.
Close #3063.

Location:
c-user
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • c-user/scheduling_concepts.rst

    r8cf3d75 r9037998  
    3737
    3838Scheduling Algorithms
    39 =====================
     39---------------------
    4040
    4141.. index:: scheduling algorithms
    4242
    4343RTEMS provides a plugin framework which allows it to support multiple
    44 scheduling algorithms. RTEMS now includes multiple scheduling algorithms in the
    45 SuperCore and the user can select which of these they wish to use in their
    46 application.  In addition, the user can implement their own scheduling
    47 algorithm and configure RTEMS to use it.
     44scheduling algorithms. RTEMS includes multiple scheduling algorithms and the
     45user can select which of these they wish to use in their application at
     46link-time.  In addition, the user can implement their own scheduling algorithm
     47and configure RTEMS to use it.
    4848
    4949Supporting multiple scheduling algorithms gives the end user the option to
     
    5151real-time operating systems schedule tasks using a priority based algorithm,
    5252possibly with preemption control.  The classic RTEMS scheduling algorithm which
    53 was the only algorithm available in RTEMS 4.10 and earlier, is a priority based
    54 scheduling algorithm.  This scheduling algoritm is suitable for single core
    55 (e.g. non-SMP) systems and is now known as the *Deterministic Priority
     53was the only algorithm available in RTEMS 4.10 and earlier, is a fixed-priority
     54scheduling algorithm.  This scheduling algoritm is suitable for uniprocessor
     55(e.g. non-SMP) systems and is known as the *Deterministic Priority
    5656Scheduler*.  Unless the user configures another scheduling algorithm, RTEMS
    57 will use this on single core systems.
     57will use this on uniprocessor systems.
    5858
    5959Priority Scheduling
     
    100100  is readied, it is placed on the rear of the FIFO for its priority.  This
    101101  method is often used with a bitmap to assist in locating which FIFOs have
    102   ready tasks on them.
     102  ready tasks on them.  This data structure has :math:`O(1)` insert, extract
     103  and find highest ready run-time complexities.
     104
     105- A red-black tree may be used for the ready queue with the priority as the
     106  key.  This data structure has :math:`O(log(n))` insert, extract and find
     107  highest ready run-time complexities while :math:`n` is the count of tasks in
     108  the ready queue.
    103109
    104110RTEMS currently includes multiple priority based scheduling algorithms as well
    105111as other algorithms which incorporate deadline.  Each algorithm is discussed in
    106112the following sections.
     113
     114Uniprocessor Schedulers
     115=======================
     116
     117All uniprocessor schedulers included in RTEMS are priority based.  The
     118processor is allocated to the highest priority task allowed to run.
    107119
    108120Deterministic Priority Scheduler
     
    137149
    138150This scheduler is only aware of a single core.
    139 
    140 Simple SMP Priority Scheduler
    141 -----------------------------
    142 
    143 This scheduler is based upon the Simple Priority Scheduler and is designed to
    144 have the same behaviour on a single core system.  But this scheduler is capable
    145 of scheduling threads across multiple cores in an SMP system.  When given a
    146 choice of replacing one of two threads at equal priority on different cores,
    147 this algorithm favors replacing threads which are preemptible and have executed
    148 the longest.
    149 
    150 This algorithm is non-deterministic. When scheduling, it must consider which
    151 tasks are to be executed on each core while avoiding superfluous task
    152 migrations.
    153151
    154152Earliest Deadline First Scheduler
     
    184182``rtems_rate_monotonic_delete`` calls clear the deadlines assigned to the task.
    185183
    186 Earliest Deadline First SMP Scheduler
    187 -------------------------------------
    188 
    189 An EDF scheduler with SMP support.  The processors managed by this scheduler
    190 are allocated to the highest priority (earliest deadline) tasks which are ready
    191 to execute.
    192 
    193184Constant Bandwidth Server Scheduling (CBS)
    194185------------------------------------------
     
    219210``rtems_rate_monotonic_period`` does not declare a deadline because it is
    220211carried out using CBS API. This call only announces next period.
     212
     213SMP Schedulers
     214==============
     215
     216All SMP schedulers included in RTEMS are priority based.  The processors
     217managed by a scheduler instance are allocated to the highest priority tasks
     218allowed to run.
     219
     220Earliest Deadline First SMP Scheduler
     221-------------------------------------
     222
     223A job-level fixed-priority scheduler using the Earliest Deadline First (EDF)
     224method.  By convention, the maximum priority level is
     225:math:`min(INT\_MAX, 2^{63} - 1)` for background tasks.  The tasks with an
     226active deadline have a higher priority than the background tasks.  This
     227scheduler supports task processor affinities of one-to-one and one-to-all, e.g.
     228a task can execute on exactly one processor or all processors managed by the
     229scheduler instance.  This is the default scheduler in SMP configurations if
     230more than one processor is configured.  The processor affinity set of a task
     231must contain all online processors to select the one-to-all affinity.  This is
     232to avoid pathological cases if processors are added/removed to/from the
     233scheduler instance at run-time.  In case the processor affinity set contains
     234not all online processors, then a one-to-one affinity will be used selecting
     235the processor with the largest index within the set of processores currently
     236owned by the scheduler instance.
     237
     238Deterministic Priority SMP Scheduler
     239------------------------------------
     240
     241A fixed-priority scheduler which uses a table of chains with one chain per
     242priority level for the ready tasks.  The maximum priority level is
     243configurable.  By default, the maximum priority level is 255 (256 priority
     244levels).
     245
     246Simple Priority SMP Scheduler
     247-----------------------------
     248
     249A fixed-priority scheduler which uses a sorted chain for the ready tasks.  By
     250convention, the maximum priority level is 255.  The implementation limit is
     251actually :math:`2^{64} - 1`.
     252
     253Aribitary Processor Affinity Priority SMP Scheduler
     254---------------------------------------------------
     255
     256A fixed-priority scheduler which uses a table of chains with one chain per
     257priority level for the ready tasks.  The maximum priority level is
     258configurable.  By default, the maximum priority level is 255 (256 priority
     259levels).  This scheduler supports arbitrary task processor affinities.  The
     260worst-case run-time complexity of some scheduler operations exceeds
     261:math:`O(n)` while :math:`n` is the count of ready tasks.
    221262
    222263Scheduling Modification Mechanisms
     
    252293The most significant task scheduling modification mechanism is the ability for
    253294the user to assign a priority level to each individual task when it is created
    254 and to alter a task's priority at run-time.  RTEMS supports up to 255 priority
    255 levels.  Level 255 is the lowest priority and level 1 is the highest.
     295and to alter a task's priority at run-time.  The maximum priority level depends
     296on the configured scheduler.  A lower priority level means higher priority
     297(higher importance).  The maximum priority level of the default uniprocessor
     298scheduler is 255.
    256299
    257300Preemption
     
    609652         be empty after the processor removal and there exists a non-idle task
    610653         that uses this scheduler instance as its home scheduler instance.
     654     * - ``RTEMS_RESOURCE_IN_USE``
     655       - A task with a restricted processor affinity exists that uses this
     656         scheduler instance as its home scheduler instance and it would be no
     657         longer possible to allocate a processor for this task after the
     658         removal of this processor.
    611659
    612660DESCRIPTION:
  • c-user/task_manager.rst

    r8cf3d75 r9037998  
    15451545
    15461546NOTES:
    1547     None.
     1547    The task processor affinity is initialized to the set of online processors.
    15481548
    15491549.. raw:: latex
     
    15941594    an error if the processor affinity set contains processors that are not
    15951595    part of the system.
     1596
     1597    In case a scheduler without support for task affinites is used for the
     1598    task, then the task processor affinity set must contain all online
     1599    processors of the system.  This prevents odd corner cases if processors are
     1600    added/removed at run-time to/from scheduler instances.
    15961601
    15971602.. raw:: latex
Note: See TracChangeset for help on using the changeset viewer.