Editing Priority inheritance

{{Short description|Computer programming method}}In [[real-time computing]], '''priority inheritance''' is a method for eliminating unbounded [[priority inversion]]. Using this [[Computer programming|programming]] method, a [[process scheduling]] [[algorithm]] increases the priority of a process (A) to the maximum priority of any other process waiting for any [[resource (computer science)|resource]] on which A has a [[Lock (computer science)|resource lock]] (if it is higher than the original priority of A).

The basic idea of the priority inheritance protocol is that when a job blocks one or more high-priority jobs, it ignores its original priority assignment and executes its [[critical section]] at an elevated priority level. After executing its critical section and releasing its locks, the process returns to its original priority level.

==Example==
Consider three jobs:

{| class="wikitable"
|-
! Job Name
! Priority
|-
| H
| High
|-
| M
| Medium
|-
| L
| Low
|}

Suppose that both H and L require some shared resource. If L acquires this shared resource (entering a critical section), and H subsequently requires it, H will block until L releases it (leaving its critical section). Without priority inheritance, process M could [[Preemption (computing)|preempt]] process L during the critical section and delay its completion, in effect causing the lower-priority process M to indirectly preempt the high-priority process H. This is a [[priority inversion]] bug.

With priority inheritance, L will execute its critical section at H's high priority whenever H is blocked on the shared resource. As a result, M will be unable to preempt L and will be blocked. That is, the higher-priority job M must wait for the critical section of the lower priority job L to be executed, because L has inherited H's priority. When L exits its critical section, it regains its original (low) priority and awakens H (which was blocked by L). H, having high priority, preempts L and runs to completion. This enables M and L to resume in succession and run to completion without priority inversion.

==Operating systems supporting priority inheritance==
*[[ERIKA Enterprise]]<ref>{{cite web | url = https://en.wikipedia.org/wiki/ERIKA_Enterprise | title = ERIKA Enterprise | access-date = 2024-01-03 }}</ref>{{Circular reference|date=May 2024}}
*[[FreeRTOS]]
*[[ThreadX|Microsoft Azure RTOS, formerly Express Logic's ThreadX]]
*[[Linux]]<ref>{{cite web | url = https://www.kernel.org/doc/html/v5.15/locking/rt-mutex.html | title = RT-mutex subsystem with PI support | access-date = 2021-11-27 }}</ref>
*[[VxWorks]]
*[[iRMX]]<ref>{{Cite web |url=https://apps.dtic.mil/sti/tr/pdf/ADA408745.pdf#page=7 |title=Resource-centric real-time kernel and middleware services |page=3 |accessdate=2024-01-01}}</ref>

==See also==
*[[Priority ceiling protocol]]

==References==
* {{cite journal
 |author1=Lui Sha |author2=Ragunathan Rajkumar |author3=John P. Lehoczky  |name-list-style=amp |date=September 1990
 |     title = Priority Inheritance Protocols: An Approach to Real-Time Synchronization
 |   journal = [[IEEE Transactions on Computers]]
 |    volume = 39
 |     issue = 9
 |     pages = 1175&ndash;1185
 |       url = https://www.csie.ntu.edu.tw/~r95093/papers/Priority%20Inheritance%20Protocols%20An%20Approach%20to%20Real-Time%20Synchronization.pdf
 |     doi = 10.1109/12.57058
 |archive-url=https://web.archive.org/web/20220419175141/https://www.csie.ntu.edu.tw/~r95093/papers/Priority%20Inheritance%20Protocols%20An%20Approach%20to%20Real-Time%20Synchronization.pdf |archive-date=2022-04-19 }}
{{reflist}}

==External links==
* "[https://web.archive.org/web/20070706071045/http://www.linuxdevices.com/articles/AT5698775833.html Priority Inheritance: The Real Story]" by [[Doug Locke]]
* "[https://web.archive.org/web/20070706071207/http://www.linuxdevices.com/articles/AT7168794919.html Against Priority Inheritance]" by [[Victor Yodaiken]]
* "[http://rtdoc.cs.uri.edu/downloads/wohlever_thesis.pdf Implementing Concurrency Control With Priority Inheritance in Real-Time CORBA]" by [[Steven Wohlever]], [[Victor Fay Wolfe]] and Russell Johnston
* "[http://citeseer.ist.psu.edu/108383.html Priority Inheritance Spin Locks for Multiprocessor Real-Time Systems]" by [[Cai-Dong Wang]], [[Hiroaki Takada]] and [[Ken Sakamura]]
* "[http://doi.ieeecomputersociety.org/10.1109/REAL.2003.1253271 Hardware Support for Priority Inheritance]" by [[Bilge E. S. Akgul]], [[Vincent J. Mooney]], [[Henrik Thane]] and [[Pramote Kuacharoen]]

[[Category:Real-time computing]]
[[Category:Concurrency control]]


{{compu-sci-stub}}