From 8add1793d25b2f76d564028f991cac31e0f871b4 Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Tue, 31 Jan 2017 13:27:08 +0100 Subject: c-user: Add Key concept locking protocols Update #2412. Update #2556. --- c-user/key_concepts.rst | 116 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 116 insertions(+) (limited to 'c-user/key_concepts.rst') 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 -- cgit v1.2.3