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 +++++++++++++++++++++++++++++++++++++++++++ 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 ` 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 ` 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}, } +@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, } +@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}}, -- cgit v1.2.3