From 90379988d69067bf4963c04496a75d47880461f8 Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Fri, 7 Jul 2017 15:50:51 +0200 Subject: c-user: Update scheduler/task chapter Reflect EDF SMP scheduler changes. Close #3059. Close #3063. --- c-user/scheduling_concepts.rst | 114 +++++++++++++++++++++++++++++------------ c-user/task_manager.rst | 7 ++- 2 files changed, 87 insertions(+), 34 deletions(-) diff --git a/c-user/scheduling_concepts.rst b/c-user/scheduling_concepts.rst index 7a77a33..bd9b6b3 100644 --- a/c-user/scheduling_concepts.rst +++ b/c-user/scheduling_concepts.rst @@ -36,25 +36,25 @@ The directives provided by the scheduler manager are: - rtems_scheduler_remove_processor_ - Remove processor from a scheduler Scheduling Algorithms -===================== +--------------------- .. index:: scheduling algorithms RTEMS provides a plugin framework which allows it to support multiple -scheduling algorithms. RTEMS now includes multiple scheduling algorithms in the -SuperCore and the user can select which of these they wish to use in their -application. In addition, the user can implement their own scheduling -algorithm and configure RTEMS to use it. +scheduling algorithms. RTEMS includes multiple scheduling algorithms and the +user can select which of these they wish to use in their application at +link-time. In addition, the user can implement their own scheduling algorithm +and configure RTEMS to use it. Supporting multiple scheduling algorithms gives the end user the option to select the algorithm which is most appropriate to their use case. Most real-time operating systems schedule tasks using a priority based algorithm, possibly with preemption control. The classic RTEMS scheduling algorithm which -was the only algorithm available in RTEMS 4.10 and earlier, is a priority based -scheduling algorithm. This scheduling algoritm is suitable for single core -(e.g. non-SMP) systems and is now known as the *Deterministic Priority +was the only algorithm available in RTEMS 4.10 and earlier, is a fixed-priority +scheduling algorithm. This scheduling algoritm is suitable for uniprocessor +(e.g. non-SMP) systems and is known as the *Deterministic Priority Scheduler*. Unless the user configures another scheduling algorithm, RTEMS -will use this on single core systems. +will use this on uniprocessor systems. Priority Scheduling ------------------- @@ -99,12 +99,24 @@ algorithm. These ways involve a list or chain of tasks in the ready state. - Another mechanism is to maintain a list of FIFOs per priority. When a task is readied, it is placed on the rear of the FIFO for its priority. This method is often used with a bitmap to assist in locating which FIFOs have - ready tasks on them. + ready tasks on them. This data structure has :math:`O(1)` insert, extract + and find highest ready run-time complexities. + +- A red-black tree may be used for the ready queue with the priority as the + key. This data structure has :math:`O(log(n))` insert, extract and find + highest ready run-time complexities while :math:`n` is the count of tasks in + the ready queue. RTEMS currently includes multiple priority based scheduling algorithms as well as other algorithms which incorporate deadline. Each algorithm is discussed in the following sections. +Uniprocessor Schedulers +======================= + +All uniprocessor schedulers included in RTEMS are priority based. The +processor is allocated to the highest priority task allowed to run. + Deterministic Priority Scheduler -------------------------------- @@ -137,20 +149,6 @@ supporting a large number of tasks. This scheduler is only aware of a single core. -Simple SMP Priority Scheduler ------------------------------ - -This scheduler is based upon the Simple Priority Scheduler and is designed to -have the same behaviour on a single core system. But this scheduler is capable -of scheduling threads across multiple cores in an SMP system. When given a -choice of replacing one of two threads at equal priority on different cores, -this algorithm favors replacing threads which are preemptible and have executed -the longest. - -This algorithm is non-deterministic. When scheduling, it must consider which -tasks are to be executed on each core while avoiding superfluous task -migrations. - Earliest Deadline First Scheduler --------------------------------- .. index:: earliest deadline first scheduling @@ -183,13 +181,6 @@ period, it has to be finished until the end of this period. The call of deadline. Moreover, the ``rtems_rate_monotonic_cancel`` and ``rtems_rate_monotonic_delete`` calls clear the deadlines assigned to the task. -Earliest Deadline First SMP Scheduler -------------------------------------- - -An EDF scheduler with SMP support. The processors managed by this scheduler -are allocated to the highest priority (earliest deadline) tasks which are ready -to execute. - Constant Bandwidth Server Scheduling (CBS) ------------------------------------------ .. index:: constant bandwidth server scheduling @@ -219,6 +210,56 @@ The CBS provides an extensive API. Unlike EDF, the ``rtems_rate_monotonic_period`` does not declare a deadline because it is carried out using CBS API. This call only announces next period. +SMP Schedulers +============== + +All SMP schedulers included in RTEMS are priority based. The processors +managed by a scheduler instance are allocated to the highest priority tasks +allowed to run. + +Earliest Deadline First SMP Scheduler +------------------------------------- + +A job-level fixed-priority scheduler using the Earliest Deadline First (EDF) +method. By convention, the maximum priority level is +:math:`min(INT\_MAX, 2^{63} - 1)` for background tasks. The tasks with an +active deadline have a higher priority than the background tasks. This +scheduler supports task processor affinities of one-to-one and one-to-all, e.g. +a task can execute on exactly one processor or all processors managed by the +scheduler instance. This is the default scheduler in SMP configurations if +more than one processor is configured. The processor affinity set of a task +must contain all online processors to select the one-to-all affinity. This is +to avoid pathological cases if processors are added/removed to/from the +scheduler instance at run-time. In case the processor affinity set contains +not all online processors, then a one-to-one affinity will be used selecting +the processor with the largest index within the set of processores currently +owned by the scheduler instance. + +Deterministic Priority SMP Scheduler +------------------------------------ + +A fixed-priority scheduler which uses a table of chains with one chain per +priority level for the ready tasks. The maximum priority level is +configurable. By default, the maximum priority level is 255 (256 priority +levels). + +Simple Priority SMP Scheduler +----------------------------- + +A fixed-priority scheduler which uses a sorted chain for the ready tasks. By +convention, the maximum priority level is 255. The implementation limit is +actually :math:`2^{64} - 1`. + +Aribitary Processor Affinity Priority SMP Scheduler +--------------------------------------------------- + +A fixed-priority scheduler which uses a table of chains with one chain per +priority level for the ready tasks. The maximum priority level is +configurable. By default, the maximum priority level is 255 (256 priority +levels). This scheduler supports arbitrary task processor affinities. The +worst-case run-time complexity of some scheduler operations exceeds +:math:`O(n)` while :math:`n` is the count of ready tasks. + Scheduling Modification Mechanisms ================================== @@ -251,8 +292,10 @@ Task Priority and Scheduling The most significant task scheduling modification mechanism is the ability for the user to assign a priority level to each individual task when it is created -and to alter a task's priority at run-time. RTEMS supports up to 255 priority -levels. Level 255 is the lowest priority and level 1 is the highest. +and to alter a task's priority at run-time. The maximum priority level depends +on the configured scheduler. A lower priority level means higher priority +(higher importance). The maximum priority level of the default uniprocessor +scheduler is 255. Preemption ---------- @@ -608,6 +651,11 @@ DIRECTIVE STATUS CODES: - The set of processors owned by the specified scheduler instance would be empty after the processor removal and there exists a non-idle task that uses this scheduler instance as its home scheduler instance. + * - ``RTEMS_RESOURCE_IN_USE`` + - A task with a restricted processor affinity exists that uses this + scheduler instance as its home scheduler instance and it would be no + longer possible to allocate a processor for this task after the + removal of this processor. DESCRIPTION: Removes a processor from set of processors owned by the specified scheduler diff --git a/c-user/task_manager.rst b/c-user/task_manager.rst index 511d48b..65f2468 100644 --- a/c-user/task_manager.rst +++ b/c-user/task_manager.rst @@ -1544,7 +1544,7 @@ DESCRIPTION: processor and a cleared bit means the opposite. NOTES: - None. + The task processor affinity is initialized to the set of online processors. .. raw:: latex @@ -1594,6 +1594,11 @@ NOTES: an error if the processor affinity set contains processors that are not part of the system. + In case a scheduler without support for task affinites is used for the + task, then the task processor affinity set must contain all online + processors of the system. This prevents odd corner cases if processors are + added/removed at run-time to/from scheduler instances. + .. raw:: latex \clearpage -- cgit v1.2.3