[rtems-docs commit] c-user: Update clustered scheduling
Sebastian Huber
sebh at rtems.org
Thu Feb 2 08:44:09 UTC 2017
Module: rtems-docs
Branch: master
Commit: 7b1c63cf91830e5db2b3a7eb04ca6ae1d0eb27c0
Changeset: http://git.rtems.org/rtems-docs/commit/?id=7b1c63cf91830e5db2b3a7eb04ca6ae1d0eb27c0
Author: Sebastian Huber <sebastian.huber at embedded-brains.de>
Date: Thu Feb 2 09:43:47 2017 +0100
c-user: Update clustered scheduling
---
c-user/symmetric_multiprocessing_services.rst | 66 ++++++++++++++++++---------
common/refs.bib | 41 ++++++++++++++---
2 files changed, 79 insertions(+), 28 deletions(-)
diff --git a/c-user/symmetric_multiprocessing_services.rst b/c-user/symmetric_multiprocessing_services.rst
index 11b04da..ac6d921 100644
--- a/c-user/symmetric_multiprocessing_services.rst
+++ b/c-user/symmetric_multiprocessing_services.rst
@@ -143,41 +143,65 @@ the most local cache level.
Clustered Scheduling
--------------------
+The scheduler is responsible to assign processors to some of the threads which
+are ready to execute. Trouble starts if more ready threads than processors
+exist at the same time. There are various rules how the processor assignment
+can be performed attempting to fulfill additional constraints or yield some
+overall system properties. As a matter of fact it is impossible to meet all
+requirements at the same time. The way a scheduler works distinguishes
+real-time operating systems from general purpose operating systems.
+
We have clustered scheduling in case the set of processors of a system is
-partitioned into non-empty pairwise-disjoint subsets. These subsets are called
-clusters. Clusters with a cardinality of one are partitions. Each cluster is
-owned by exactly one scheduler instance.
-
-Clustered scheduling helps to control the worst-case latencies in
-multi-processor systems, see :cite:`Brandenburg:2011:SL`. The goal is to reduce
-the amount of shared state in the system and thus prevention of lock
-contention. Modern multi-processor systems tend to have several layers of data
-and instruction caches. With clustered scheduling it is possible to honour the
-cache topology of a system and thus avoid expensive cache synchronization
-traffic. It is easy to implement. The problem is to provide synchronization
+partitioned into non-empty pairwise-disjoint subsets of processors. These
+subsets are called clusters. Clusters with a cardinality of one are
+partitions. Each cluster is owned by exactly one scheduler instance. In case
+the cluster size equals the processor count, it is called global scheduling.
+
+Modern SMP systems have multi-layer caches. An operating system which neglects
+cache constraints in the scheduler will not yield good performance. Real-time
+operating systems usually provide priority (fixed or job-level) based
+schedulers so that each of the highest priority threads is assigned to a
+processor. Priority based schedulers have difficulties in providing cache
+locality for threads and may suffer from excessive thread migrations
+:cite:`Brandenburg:2011:SL` :cite:`Compagnin:2014:RUN`. Schedulers that use local run
+queues and some sort of load-balancing to improve the cache utilization may not
+fulfill global constraints :cite:`Gujarati:2013:LPP` and are more difficult to
+implement than one would normally expect :cite:`Lozi:2016:LSDWC`.
+
+Clustered scheduling was implemented for RTEMS SMP to best use the cache
+topology of a system and to keep the worst-case latencies under control. The
+low-level SMP locks use FIFO ordering. So, the worst-case run-time of
+operations increases with each processor involved. The scheduler configuration
+is quite flexible and done at link-time, see :ref:`Configuring Clustered
+Schedulers`. It is possible to re-assign processors to schedulers during
+run-time via :ref:`rtems_scheduler_add_processor()
+<rtems_scheduler_add_processor>` and :ref:`rtems_scheduler_remove_processor()
+<rtems_scheduler_remove_processor>`. The schedulers are implemented in an
+object-oriented fashion.
+
+The problem is to provide synchronization
primitives for inter-cluster synchronization (more than one cluster is involved
-in the synchronization process). In RTEMS there are currently four means
+in the synchronization process). In RTEMS there are currently some means
available
- events,
- message queues,
-- semaphores using the :ref:`Priority Inheritance` protocol (priority
- boosting), and
+- mutexes using the :ref:`OMIP`,
+
+- mutexes using the :ref:`MrsP`, and
-- semaphores using the Multiprocessor Resource Sharing Protocol :cite:`Burns:2013:MrsP`.
+- binary and counting semaphores.
The clustered scheduling approach enables separation of functions with
real-time requirements and functions that profit from fairness and high
throughput provided the scheduler instances are fully decoupled and adequate
-inter-cluster synchronization primitives are used. This is work in progress.
-
-For the configuration of clustered schedulers see :ref:`Configuring Clustered
-Schedulers`.
+inter-cluster synchronization primitives are used.
-To set the scheduler of a task see :ref:`SCHEDULER_IDENT - Get ID of a
-scheduler` and :ref:`TASK_SET_SCHEDULER - Set scheduler of a task`.
+To set the scheduler of a task see :ref:`rtems_scheduler_ident()
+<rtems_scheduler_ident>` and :ref:`rtems_task_set_scheduler()
+<rtems_task_set_scheduler>`.
Scheduler Helping Protocol
--------------------------
diff --git a/common/refs.bib b/common/refs.bib
index e412fff..018f6d6 100644
--- a/common/refs.bib
+++ b/common/refs.bib
@@ -207,6 +207,13 @@
year = {2013},
url = {http://www.akkadia.org/drepper/tls.pdf},
}
+ at inproceedings{Gujarati:2013:LPP,
+ author = {Gujarati, Arpan and Cerqueira, Felipe and Brandenburg, Björn B.},
+ title = {{Schedulability Analysis of the Linux Push and Pull Scheduler with Arbitrary Processor Affinities}},
+ booktitle = {Proceedings of the 25th Euromicro Conference on Real-Time Systems (ECRTS 2013)},
+ year = {2013},
+ url = {https://people.mpi-sws.org/~bbb/papers/pdf/ecrts13a-rev1.pdf},
+}
@book{PRQA:2013:HIC,
title = {{High Integrity C++ Coding Standard Version 4.0}},
year = {2013},
@@ -214,6 +221,19 @@
publisher = {Programming Research Ltd},
url = {http://www.codingstandard.com/},
}
+ at inproceedings{Cerqueira:2014:LPA,
+ author = {Cerqueira, Felipe and Gujarati, Arpan and Brandenburg, Björn B.},
+ title = {{Linux’s Processor Affinity API, Refined: Shifting Real-Time Tasks towards Higher Schedulability}},
+ booktitle = {Proceedings of the 35th IEEE Real-Time Systems Symposium (RTSS 2014)},
+ year = {2014},
+ url = {http://www.mpi-sws.org/~bbb/papers/pdf/rtss14f.pdf},
+}
+ at inproceedings{Compagnin:2014:RUN,
+ author = {Compagnin, Davide and Mezzetti, Enrico and Vardanega, Tullio},
+ title = {{Putting RUN into practice: implementation and evaluation}},
+ booktitle = {Proceedings of the 26th Euromicro Conference on Real-Time Systems (ECRTS 2014)},
+ year = {2014},
+}
@techreport{Robinson:2014:CilkN3872,
author = {Robinson, Arch},
title = {{A Primer on Scheduling Fork-Join Parallelism with Work Stealing}},
@@ -242,13 +262,6 @@
year = {2016},
publisher = {Carnegie Mellon University},
}
- at INPROCEEDINGS{vonderBr:2016:DynRT,
- author = {von der Br\"uggen, Georg and Chen, Kuan-Hsun and Huang, Wen-Hung and Chen, Jian-Jia},
- booktitle = {IEEE Real-Time Systems Symposium (RTSS)},
- title = {{Systems with Dynamic Real-Time Guarantees in Uncertain and Faulty Execution Environments}},
- year = {2016},
- pages = {303-314},
-}
@inproceedings{Chen:2016:Overrun,
author = {Chen, Kuan-Hsun and von der Br\"uggen, Georg and Chen, Jian-Jia},
title = {{Overrun Handling for Mixed-Criticality Support in RTEMS}},
@@ -257,3 +270,17 @@
year = {2016},
url = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2016-wmc.pdf},
}
+ at inproceedings{vonderBr:2016:DynRT,
+ author = {von der Br\"uggen, Georg and Chen, Kuan-Hsun and Huang, Wen-Hung and Chen, Jian-Jia},
+ booktitle = {IEEE Real-Time Systems Symposium (RTSS)},
+ title = {{Systems with Dynamic Real-Time Guarantees in Uncertain and Faulty Execution Environments}},
+ year = {2016},
+ pages = {303-314},
+}
+ at inproceedings{Lozi:2016:LSDWC,
+ author = {Lozi, Jean-Pierre and Lepers, Baptiste and Funston, Justin and Gaud, Fabien and Quéma, Vivien and Fedorova, Alexandra},
+ title = {{The Linux Scheduler: a Decade of Wasted Cores}},
+ booktitle = {Proceedings of the Eleventh European Conference on Computer Systems (EuroSys '16)},
+ year = {2016},
+ url = {https://hal.archives-ouvertes.fr/hal-01295194/document},
+}
More information about the vc
mailing list