[rtems-docs commit] c-user: Add Key concept locking protocols
Sebastian Huber
sebh at rtems.org
Wed Feb 1 06:58:46 UTC 2017
Module: rtems-docs
Branch: master
Commit: 8add1793d25b2f76d564028f991cac31e0f871b4
Changeset: http://git.rtems.org/rtems-docs/commit/?id=8add1793d25b2f76d564028f991cac31e0f871b4
Author: Sebastian Huber <sebastian.huber at embedded-brains.de>
Date: Tue Jan 31 13:27:08 2017 +0100
c-user: Add Key concept locking protocols
Update #2412.
Update #2556.
---
c-user/key_concepts.rst | 116 +++++++++++++++++++++++++++++++++++++++++++
c-user/semaphore_manager.rst | 93 +++-------------------------------
common/refs.bib | 16 ++++++
3 files changed, 140 insertions(+), 85 deletions(-)
diff --git a/c-user/key_concepts.rst b/c-user/key_concepts.rst
index 6a50278..6af8067 100644
--- a/c-user/key_concepts.rst
+++ b/c-user/key_concepts.rst
@@ -239,6 +239,122 @@ synchronization, while the event manager primarily provides a high performance
synchronization mechanism. The signal manager supports only asynchronous
communication and is typically used for exception handling.
+Locking Protocols
+=================
+.. index:: locking protocols
+
+RTEMS supports the four locking protocols
+
+* :ref:`PriorityCeiling`,
+
+* :ref:`PriorityInheritance`,
+
+* :ref:`MrsP`, and
+
+* :ref:`OMIP`
+
+for synchronization objects providing mutual-exclusion (mutex). The OMIP is
+only available in SMP configurations and replaces the priority inheritance
+protocol in this case. One aim of the locking protocols is to avoid priority
+inversion.
+
+Since RTEMS 4.12, priority updates due to the locking protocols take place
+immediately and are propagated recursively. The mutex owner and wait for mutex
+relationships define a directed acyclic graph (DAG). The run-time of the mutex
+obtain, release and timeout operations depend on the complexity of this
+resource dependency graph.
+
+.. _PriorityInversion:
+
+Priority Inversion
+------------------
+.. index:: priority inversion
+
+Priority inversion is a form of indefinite postponement which is common in
+multitasking, pre-emptive executives with shared resources. Priority inversion
+occurs when a high priority tasks requests access to shared resource which is
+currently allocated to a low priority task. The high priority task must block
+until the low priority task releases the resource. This problem is exacerbated
+when the low priority task is prevented from executing by one or more medium
+priority tasks. Because the low priority task is not executing, it cannot
+complete its interaction with the resource and release that resource. The high
+priority task is effectively prevented from executing by lower priority tasks.
+
+.. _PriorityCeiling:
+
+Immediate Ceiling Priority Protocol (ICPP)
+------------------------------------------
+.. index:: priority ceiling protocol
+.. index:: immediate ceiling priority protocol
+
+Each mutex using the Immediate Ceiling Priority Protocol (ICPP) has a ceiling
+priority. The priority of the mutex owner is immediately raised to the ceiling
+priority of the mutex. In case the thread owning the mutex releases the mutex,
+then the normal priority of the thread is restored. This locking protocol is
+beneficial for schedulability analysis, see also
+:cite:`Burns:2001:RealTimeSystems`.
+
+This protocol avoids the possibility of changing the priority of the mutex
+owner multiple times since the ceiling priority must be set to the one of
+highest priority thread which will ever attempt to acquire that mutex. This
+requires an overall knowledge of the application as a whole. The need to
+identify the highest priority thread which will attempt to obtain a particular
+mutex can be a difficult task in a large, complicated system. Although the
+priority ceiling protocol is more efficient than the priority inheritance
+protocol with respect to the maximum number of thread priority changes which
+may occur while a thread owns a particular mutex, the priority inheritance
+protocol is more forgiving in that it does not require this apriori
+information.
+
+.. _PriorityInheritance:
+
+Priority Inheritance Protocol
+-----------------------------
+.. index:: priority inheritance protocol
+
+The priority of the mutex owner is raised to the highest priority of all
+threads that currently wait for ownership of this mutex :cite:`Sha:1990:PI`.
+Since RTEMS 4.12, priority updates due to the priority inheritance protocol
+take place immediately and are propagated recursively.
+
+.. _MrsP:
+
+Multiprocessor Resource Sharing Protocol (MrsP)
+-----------------------------------------------
+.. index:: Multiprocessor Resource Sharing Protocol (MrsP)
+
+The Multiprocessor Resource Sharing Protocol (MrsP) is a generalization of the
+priority ceiling protocol to clustered scheduling :cite:`Burns:2013:MrsP`. One
+of the design goals of MrsP is to enable an effective schedulability analysis
+using the sporadic task model. Each mutex using the MrsP has a ceiling
+priority for each scheduler instance. The priority of the mutex owner is
+immediately raised to the ceiling priority of the mutex defined for its home
+scheduler instance. In case the thread owning the mutex releases the mutex,
+then the normal priority of the thread is restored. Threads that wait for
+mutex ownership are not blocked with respect to the scheduler and instead
+perform a busy wait. The MrsP uses temporary thread migrations to foreign
+scheduler instances in case of a pre-emption of the mutex owner. This locking
+protocol is available since RTEMS 4.11. It was re-implemented in RTEMS 4.12 to
+overcome some shortcomings of the original implementation
+:cite:`Catellani:2015:MrsP`.
+
+.. _OMIP:
+
+O(m) Independence-Preserving Protocol (OMIP)
+----------------------------------------------------
+.. index:: O(m) Independence-Preserving Protocol (OMIP)
+
+The :math:`O(m)` Independence-Preserving Protocol (OMIP) is a generalization of
+the priority inheritance protocol to clustered scheduling which avoids the
+non-preemptive sections present with priority boosting
+:cite:`Brandenburg:2013:OMIP`. The :math:`m` denotes the number of processors
+in the system. Similar to the uni-processor priority inheritance protocol, the
+OMIP mutexes do not need any external configuration data, e.g. a ceiling
+priority. This makes them a good choice for general purpose libraries that
+need internal locking. The complex part of the implementation is contained in
+the thread queues and shared with the MrsP support. This locking protocol is
+available since RTEMS 4.12.
+
Thread Queues
=============
.. index:: thread queues
diff --git a/c-user/semaphore_manager.rst b/c-user/semaphore_manager.rst
index 62c6d3e..e184590 100644
--- a/c-user/semaphore_manager.rst
+++ b/c-user/semaphore_manager.rst
@@ -91,108 +91,31 @@ matched with a ``rtems_semaphore_release``.
Simple binary semaphores do not allow nested access and so can be used for task
synchronization.
-.. _Priority Inversion:
-
-Priority Inversion
-------------------
-
-Priority inversion is a form of indefinite postponement which is common in
-multitasking, preemptive executives with shared resources. Priority inversion
-occurs when a high priority tasks requests access to shared resource which is
-currently allocated to low priority task. The high priority task must block
-until the low priority task releases the resource. This problem is exacerbated
-when the low priority task is prevented from executing by one or more medium
-priority tasks. Because the low priority task is not executing, it cannot
-complete its interaction with the resource and release that resource. The high
-priority task is effectively prevented from executing by lower priority tasks.
-
.. _Priority Inheritance:
Priority Inheritance
--------------------
-Priority inheritance is an algorithm that calls for the lower priority task
-holding a resource to have its priority increased to that of the highest
-priority task blocked waiting for that resource. Each time a task blocks
-attempting to obtain the resource, the task holding the resource may have its
-priority increased.
-
-On SMP configurations, in case the task holding the resource and the task that
-blocks attempting to obtain the resource are in different scheduler instances,
-the priority of the holder is raised to the pseudo-interrupt priority (priority
-boosting). The pseudo-interrupt priority is the highest priority.
-
-RTEMS supports priority inheritance for local, binary semaphores that use the
-priority task wait queue blocking discipline. When a task of higher priority
-than the task holding the semaphore blocks, the priority of the task holding
-the semaphore is increased to that of the blocking task. When the task holding
-the task completely releases the binary semaphore (i.e. not for a nested
-release), the holder's priority is restored to the value it had before any
-higher priority was inherited.
-
-The RTEMS implementation of the priority inheritance algorithm takes into
-account the scenario in which a task holds more than one binary semaphore. The
-holding task will execute at the priority of the higher of the highest ceiling
-priority or at the priority of the highest priority task blocked waiting for
-any of the semaphores the task holds. Only when the task releases ALL of the
-binary semaphores it holds will its priority be restored to the normal value.
+RTEMS supports :ref:`priority inheritance <PriorityInheritance>` for local,
+binary semaphores that use the priority task wait queue blocking discipline.
+In SMP configurations, the :ref:`OMIP` is used instead.
.. _Priority Ceiling:
Priority Ceiling
----------------
-Priority ceiling is an algorithm that calls for the lower priority task holding
-a resource to have its priority increased to that of the highest priority task
-which will EVER block waiting for that resource. This algorithm addresses the
-problem of priority inversion although it avoids the possibility of changing
-the priority of the task holding the resource multiple times. The priority
-ceiling algorithm will only change the priority of the task holding the
-resource a maximum of one time. The ceiling priority is set at creation time
-and must be the priority of the highest priority task which will ever attempt
-to acquire that semaphore.
-
-RTEMS supports priority ceiling for local, binary semaphores that use the
-priority task wait queue blocking discipline. When a task of lower priority
-than the ceiling priority successfully obtains the semaphore, its priority is
-raised to the ceiling priority. When the task holding the task completely
-releases the binary semaphore (i.e. not for a nested release), the holder's
-priority is restored to the value it had before any higher priority was put
-into effect.
-
-The need to identify the highest priority task which will attempt to obtain a
-particular semaphore can be a difficult task in a large, complicated system.
-Although the priority ceiling algorithm is more efficient than the priority
-inheritance algorithm with respect to the maximum number of task priority
-changes which may occur while a task holds a particular semaphore, the priority
-inheritance algorithm is more forgiving in that it does not require this
-apriori information.
-
-The RTEMS implementation of the priority ceiling algorithm takes into account
-the scenario in which a task holds more than one binary semaphore. The holding
-task will execute at the priority of the higher of the highest ceiling priority
-or at the priority of the highest priority task blocked waiting for any of the
-semaphores the task holds. Only when the task releases ALL of the binary
-semaphores it holds will its priority be restored to the normal value.
+RTEMS supports :ref:`priority ceiling <PriorityCeiling>` for local, binary
+semaphores that use the priority task wait queue blocking discipline.
.. _Multiprocessor Resource Sharing Protocol:
Multiprocessor Resource Sharing Protocol
----------------------------------------
-The Multiprocessor Resource Sharing Protocol (MrsP) is defined in *A. Burns
-and A.J. Wellings, A Schedulability Compatible Multiprocessor Resource Sharing
-Protocol - MrsP, Proceedings of the 25th Euromicro Conference on Real-Time
-Systems (ECRTS 2013), July 2013*. It is a generalization of the Priority
-Ceiling Protocol to SMP systems. Each MrsP semaphore uses a ceiling priority
-per scheduler instance. These ceiling priorities can be specified with
-``rtems_semaphore_set_priority()``. A task obtaining or owning a MrsP
-semaphore will execute with the ceiling priority for its scheduler instance as
-specified by the MrsP semaphore object. Tasks waiting to get ownership of a
-MrsP semaphore will not relinquish the processor voluntarily. In case the
-owner of a MrsP semaphore gets preempted it can ask all tasks waiting for this
-semaphore to help out and temporarily borrow the right to execute on one of
-their assigned processors.
+RTEMS supports the :ref:`MrsP` for local, binary semaphores that use the
+priority task wait queue blocking discipline. In uni-processor configurations,
+the :ref:`PriorityCeiling` is used instead.
.. _Building a Semaphore Attribute Set:
diff --git a/common/refs.bib b/common/refs.bib
index 0f30cc1..e1f6435 100644
--- a/common/refs.bib
+++ b/common/refs.bib
@@ -38,6 +38,14 @@
volume = {23},
pages = {53-62},
}
+ at article{Sha:1990:PI,
+ author = {Sha, Lui and Rajkumar, Ragunathan and Lehoczky, John P.},
+ journal = {IEEE Transactions on Computers},
+ title = {{Priority Inheritance Protocols: An Approach to Real-Time Synchronization}},
+ year = {1990},
+ volume = {39},
+ pages = {1175-1185},
+}
@ARTICLE{Burns:1991:Review,
author = {Burns, A.},
journal = {Software Engineering Journal},
@@ -63,6 +71,14 @@
pages = {720-748},
volume = 46,
}
+ at book{Burns:2001:RealTimeSystems,
+ author = {Burns, A. and Wellings, A. J.},
+ title = {{Real-Time Systems and Programming Languages: Ada, Real-Time Java and C/Real-Time POSIX}},
+ year = {2001},
+ month = {November},
+ isbn = {978-0321417459},
+ publisher = {Addison-Wesley},
+}
@inproceedings{Franke:2002:Futex,
author = {Franke, Hubertus and Russel, Rusty and Kirkwood, Matthew},
title = {{Fuss, Futexes and Furwocks: Fast Userlevel Locking in Linux}},
More information about the vc
mailing list