Changeset 8add179 in rtems-docs


Ignore:
Timestamp:
Jan 31, 2017, 12:27:08 PM (3 years ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
master
Children:
5dcebd4
Parents:
aaff696
git-author:
Sebastian Huber <sebastian.huber@…> (01/31/17 12:27:08)
git-committer:
Sebastian Huber <sebastian.huber@…> (02/01/17 06:58:30)
Message:

c-user: Add Key concept locking protocols

Update #2412.
Update #2556.

Files:
3 edited

Legend:

Unmodified
Added
Removed
  • c-user/key_concepts.rst

    raaff696 r8add179  
    239239synchronization mechanism.  The signal manager supports only asynchronous
    240240communication and is typically used for exception handling.
     241
     242Locking Protocols
     243=================
     244.. index:: locking protocols
     245
     246RTEMS supports the four locking protocols
     247
     248* :ref:`PriorityCeiling`,
     249
     250* :ref:`PriorityInheritance`,
     251
     252* :ref:`MrsP`, and
     253
     254* :ref:`OMIP`
     255
     256for synchronization objects providing mutual-exclusion (mutex).  The OMIP is
     257only available in SMP configurations and replaces the priority inheritance
     258protocol in this case.  One aim of the locking protocols is to avoid priority
     259inversion.
     260
     261Since RTEMS 4.12, priority updates due to the locking protocols take place
     262immediately and are propagated recursively.  The mutex owner and wait for mutex
     263relationships define a directed acyclic graph (DAG).  The run-time of the mutex
     264obtain, release and timeout operations depend on the complexity of this
     265resource dependency graph.
     266
     267.. _PriorityInversion:
     268
     269Priority Inversion
     270------------------
     271.. index:: priority inversion
     272
     273Priority inversion is a form of indefinite postponement which is common in
     274multitasking, pre-emptive executives with shared resources.  Priority inversion
     275occurs when a high priority tasks requests access to shared resource which is
     276currently allocated to a low priority task.  The high priority task must block
     277until the low priority task releases the resource.  This problem is exacerbated
     278when the low priority task is prevented from executing by one or more medium
     279priority tasks.  Because the low priority task is not executing, it cannot
     280complete its interaction with the resource and release that resource.  The high
     281priority task is effectively prevented from executing by lower priority tasks.
     282
     283.. _PriorityCeiling:
     284
     285Immediate Ceiling Priority Protocol (ICPP)
     286------------------------------------------
     287.. index:: priority ceiling protocol
     288.. index:: immediate ceiling priority protocol
     289
     290Each mutex using the Immediate Ceiling Priority Protocol (ICPP) has a ceiling
     291priority.  The priority of the mutex owner is immediately raised to the ceiling
     292priority of the mutex.  In case the thread owning the mutex releases the mutex,
     293then the normal priority of the thread is restored.  This locking protocol is
     294beneficial for schedulability analysis, see also
     295:cite:`Burns:2001:RealTimeSystems`.
     296
     297This protocol avoids the possibility of changing the priority of the mutex
     298owner multiple times since the ceiling priority must be set to the one of
     299highest priority thread which will ever attempt to acquire that mutex.  This
     300requires an overall knowledge of the application as a whole.  The need to
     301identify the highest priority thread which will attempt to obtain a particular
     302mutex can be a difficult task in a large, complicated system.  Although the
     303priority ceiling protocol is more efficient than the priority inheritance
     304protocol with respect to the maximum number of thread priority changes which
     305may occur while a thread owns a particular mutex, the priority inheritance
     306protocol is more forgiving in that it does not require this apriori
     307information.
     308
     309.. _PriorityInheritance:
     310
     311Priority Inheritance Protocol
     312-----------------------------
     313.. index:: priority inheritance protocol
     314
     315The priority of the mutex owner is raised to the highest priority of all
     316threads that currently wait for ownership of this mutex :cite:`Sha:1990:PI`.
     317Since RTEMS 4.12, priority updates due to the priority inheritance protocol
     318take place immediately and are propagated recursively.
     319
     320.. _MrsP:
     321
     322Multiprocessor Resource Sharing Protocol (MrsP)
     323-----------------------------------------------
     324.. index:: Multiprocessor Resource Sharing Protocol (MrsP)
     325
     326The Multiprocessor Resource Sharing Protocol (MrsP) is a generalization of the
     327priority ceiling protocol to clustered scheduling :cite:`Burns:2013:MrsP`.  One
     328of the design goals of MrsP is to enable an effective schedulability analysis
     329using the sporadic task model.  Each mutex using the MrsP has a ceiling
     330priority for each scheduler instance.  The priority of the mutex owner is
     331immediately raised to the ceiling priority of the mutex defined for its home
     332scheduler instance.  In case the thread owning the mutex releases the mutex,
     333then the normal priority of the thread is restored.  Threads that wait for
     334mutex ownership are not blocked with respect to the scheduler and instead
     335perform a busy wait.  The MrsP uses temporary thread migrations to foreign
     336scheduler instances in case of a pre-emption of the mutex owner.  This locking
     337protocol is available since RTEMS 4.11. It was re-implemented in RTEMS 4.12 to
     338overcome some shortcomings of the original implementation
     339:cite:`Catellani:2015:MrsP`.
     340
     341.. _OMIP:
     342
     343O(m) Independence-Preserving Protocol (OMIP)
     344----------------------------------------------------
     345.. index:: O(m) Independence-Preserving Protocol (OMIP)
     346
     347The :math:`O(m)` Independence-Preserving Protocol (OMIP) is a generalization of
     348the priority inheritance protocol to clustered scheduling which avoids the
     349non-preemptive sections present with priority boosting
     350:cite:`Brandenburg:2013:OMIP`.  The :math:`m` denotes the number of processors
     351in the system.  Similar to the uni-processor priority inheritance protocol, the
     352OMIP mutexes do not need any external configuration data, e.g. a ceiling
     353priority.  This makes them a good choice for general purpose libraries that
     354need internal locking.  The complex part of the implementation is contained in
     355the thread queues and shared with the MrsP support.  This locking protocol is
     356available since RTEMS 4.12.
    241357
    242358Thread Queues
  • c-user/semaphore_manager.rst

    raaff696 r8add179  
    9292synchronization.
    9393
    94 .. _Priority Inversion:
    95 
    96 Priority Inversion
    97 ------------------
    98 
    99 Priority inversion is a form of indefinite postponement which is common in
    100 multitasking, preemptive executives with shared resources.  Priority inversion
    101 occurs when a high priority tasks requests access to shared resource which is
    102 currently allocated to low priority task.  The high priority task must block
    103 until the low priority task releases the resource.  This problem is exacerbated
    104 when the low priority task is prevented from executing by one or more medium
    105 priority tasks.  Because the low priority task is not executing, it cannot
    106 complete its interaction with the resource and release that resource.  The high
    107 priority task is effectively prevented from executing by lower priority tasks.
    108 
    10994.. _Priority Inheritance:
    11095
     
    11297--------------------
    11398
    114 Priority inheritance is an algorithm that calls for the lower priority task
    115 holding a resource to have its priority increased to that of the highest
    116 priority task blocked waiting for that resource.  Each time a task blocks
    117 attempting to obtain the resource, the task holding the resource may have its
    118 priority increased.
    119 
    120 On SMP configurations, in case the task holding the resource and the task that
    121 blocks attempting to obtain the resource are in different scheduler instances,
    122 the priority of the holder is raised to the pseudo-interrupt priority (priority
    123 boosting).  The pseudo-interrupt priority is the highest priority.
    124 
    125 RTEMS supports priority inheritance for local, binary semaphores that use the
    126 priority task wait queue blocking discipline.  When a task of higher priority
    127 than the task holding the semaphore blocks, the priority of the task holding
    128 the semaphore is increased to that of the blocking task.  When the task holding
    129 the task completely releases the binary semaphore (i.e. not for a nested
    130 release), the holder's priority is restored to the value it had before any
    131 higher priority was inherited.
    132 
    133 The RTEMS implementation of the priority inheritance algorithm takes into
    134 account the scenario in which a task holds more than one binary semaphore.  The
    135 holding task will execute at the priority of the higher of the highest ceiling
    136 priority or at the priority of the highest priority task blocked waiting for
    137 any of the semaphores the task holds.  Only when the task releases ALL of the
    138 binary semaphores it holds will its priority be restored to the normal value.
     99RTEMS supports :ref:`priority inheritance <PriorityInheritance>` for local,
     100binary semaphores that use the priority task wait queue blocking discipline.
     101In SMP configurations, the :ref:`OMIP` is used instead.
    139102
    140103.. _Priority Ceiling:
     
    143106----------------
    144107
    145 Priority ceiling is an algorithm that calls for the lower priority task holding
    146 a resource to have its priority increased to that of the highest priority task
    147 which will EVER block waiting for that resource.  This algorithm addresses the
    148 problem of priority inversion although it avoids the possibility of changing
    149 the priority of the task holding the resource multiple times.  The priority
    150 ceiling algorithm will only change the priority of the task holding the
    151 resource a maximum of one time.  The ceiling priority is set at creation time
    152 and must be the priority of the highest priority task which will ever attempt
    153 to acquire that semaphore.
    154 
    155 RTEMS supports priority ceiling for local, binary semaphores that use the
    156 priority task wait queue blocking discipline.  When a task of lower priority
    157 than the ceiling priority successfully obtains the semaphore, its priority is
    158 raised to the ceiling priority.  When the task holding the task completely
    159 releases the binary semaphore (i.e. not for a nested release), the holder's
    160 priority is restored to the value it had before any higher priority was put
    161 into effect.
    162 
    163 The need to identify the highest priority task which will attempt to obtain a
    164 particular semaphore can be a difficult task in a large, complicated system.
    165 Although the priority ceiling algorithm is more efficient than the priority
    166 inheritance algorithm with respect to the maximum number of task priority
    167 changes which may occur while a task holds a particular semaphore, the priority
    168 inheritance algorithm is more forgiving in that it does not require this
    169 apriori information.
    170 
    171 The RTEMS implementation of the priority ceiling algorithm takes into account
    172 the scenario in which a task holds more than one binary semaphore.  The holding
    173 task will execute at the priority of the higher of the highest ceiling priority
    174 or at the priority of the highest priority task blocked waiting for any of the
    175 semaphores the task holds.  Only when the task releases ALL of the binary
    176 semaphores it holds will its priority be restored to the normal value.
     108RTEMS supports :ref:`priority ceiling <PriorityCeiling>` for local, binary
     109semaphores that use the priority task wait queue blocking discipline.
    177110
    178111.. _Multiprocessor Resource Sharing Protocol:
     
    181114----------------------------------------
    182115
    183 The Multiprocessor Resource Sharing Protocol (MrsP) is defined in *A.  Burns
    184 and A.J.  Wellings, A Schedulability Compatible Multiprocessor Resource Sharing
    185 Protocol - MrsP, Proceedings of the 25th Euromicro Conference on Real-Time
    186 Systems (ECRTS 2013), July 2013*.  It is a generalization of the Priority
    187 Ceiling Protocol to SMP systems.  Each MrsP semaphore uses a ceiling priority
    188 per scheduler instance.  These ceiling priorities can be specified with
    189 ``rtems_semaphore_set_priority()``.  A task obtaining or owning a MrsP
    190 semaphore will execute with the ceiling priority for its scheduler instance as
    191 specified by the MrsP semaphore object.  Tasks waiting to get ownership of a
    192 MrsP semaphore will not relinquish the processor voluntarily.  In case the
    193 owner of a MrsP semaphore gets preempted it can ask all tasks waiting for this
    194 semaphore to help out and temporarily borrow the right to execute on one of
    195 their assigned processors.
     116RTEMS supports the :ref:`MrsP` for local, binary semaphores that use the
     117priority task wait queue blocking discipline.  In uni-processor configurations,
     118the :ref:`PriorityCeiling` is used instead.
    196119
    197120.. _Building a Semaphore Attribute Set:
  • common/refs.bib

    raaff696 r8add179  
    3939  pages       = {53-62},
    4040}
     41@article{Sha:1990:PI,
     42  author      = {Sha, Lui and Rajkumar, Ragunathan and Lehoczky, John P.},
     43  journal     = {IEEE Transactions on Computers},
     44  title       = {{Priority Inheritance Protocols: An Approach to Real-Time Synchronization}},
     45  year        = {1990},
     46  volume      = {39},
     47  pages       = {1175-1185},
     48}
    4149@ARTICLE{Burns:1991:Review,
    4250  author      = {Burns, A.},
     
    6371  pages       = {720-748},
    6472  volume      = 46,
     73}
     74@book{Burns:2001:RealTimeSystems,
     75  author      = {Burns, A. and Wellings, A. J.},
     76  title       = {{Real-Time Systems and Programming Languages: Ada, Real-Time Java and C/Real-Time POSIX}},
     77  year        = {2001},
     78  month       = {November},
     79  isbn        = {978-0321417459},
     80  publisher   = {Addison-Wesley},
    6581}
    6682@inproceedings{Franke:2002:Futex,
Note: See TracChangeset for help on using the changeset viewer.