Editing Rate-monotonic scheduling (section)

=== Priority inheritance ===

*The ''basic priority inheritance protocol''<ref>{{citation|first1=B. W.|last1=Lampson|author-link1=Butler Lampson|first2=D. D.|last2=Redell|title=Experience with processes and monitors in Mesa|journal=Communications of the ACM|volume=23|issue=2|year=1980|pages=105–117|doi=10.1145/358818.358824|citeseerx=10.1.1.46.7240|s2cid=1594544}}.</ref> promotes the priority of the task that holds the resource to the priority of the task that requests that resource at the time the request is made. Upon release of the resource, the original priority level before the promotion is restored. This method does not prevent deadlocks and suffers from ''chained blocking''. That is, if a high priority task accesses multiple shared resources in sequence, it may have to wait (block) on a lower priority task for each of the resources.<ref>{{citation|last=Buttazzo|first=Giorgio|title=Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications|publisher=Springer|location=New York, NY|year=2011|edition=Third|page=225}}</ref> The [https://rt.wiki.kernel.org/index.php/Main_Page real-time patch] {{Webarchive|url=https://web.archive.org/web/20201013113111/https://rt.wiki.kernel.org/index.php/Main_Page |date=2020-10-13 }} to the [[Linux kernel]] includes an implementation of this formula.<ref>{{cite web
 | url = https://rt.wiki.kernel.org/index.php/Frequently_Asked_Questions#How_does_the_CONFIG_PREEMPT_RT_patch_work.3F
 | title = Real-Time Linux Wiki
 | date = 2008-03-26 | access-date = 2014-03-14
 | publisher = kernel.org
}}</ref>

*The [[priority ceiling protocol]]<ref>{{citation|first1=L.|last1=Sha|first2=R.|last2=Rajkumar|first3=J. P.|last3=Lehoczky|title=Priority inheritance protocols: an approach to real-time synchronization|journal=IEEE Transactions on Computers|volume=39|issue=9|year=1990|pages=1175–1185|doi=10.1109/12.57058}}.</ref> enhances the basic priority inheritance protocol by assigning a ''ceiling priority'' to each semaphore, which is the priority of the highest job that will ever access that semaphore. A job  cannot preempt a lower priority critical section if its priority is lower than the ceiling priority for that section. This method prevents deadlocks and bounds the blocking time to at most the length of one lower priority critical section. This method can be suboptimal, in that it can cause unnecessary blocking. The priority ceiling protocol is available in the [[VxWorks]] real-time kernel. It is also known as ''Highest Locker's Priority Protocol'' (HLP).<ref>{{citation|last=Buttazzo|first=Giorgio|title=Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications|publisher=Springer|location=New York, NY|year=2011|edition=Third|page=212}}</ref>

Priority inheritance algorithms can be characterized by two parameters. First, is the inheritance lazy (only when essential) or immediate (boost priority before there is a conflict). Second is the inheritance optimistic (boost a minimum amount) or pessimistic (boost by more than the minimum amount):

{| class="wikitable"
|-
!
! pessimistic
! optimistic
|-
! immediate
| <code>OS_ENTER_CRITICAL()</code> / <code>OS_EXIT_CRITICAL()</code>
| <code>splx()</code>, highest locker
|-
! lazy
|
| priority ceiling protocol, basic priority inheritance protocol
|-
|}

In practice there is no mathematical difference (in terms of the Liu-Layland system utilization bound) between the lazy and immediate algorithms, and the immediate algorithms are more efficient to implement, and so they are the ones used by most practical systems.{{Citation needed|date=October 2007}}

An example of usage of basic priority inheritance is related to the "[[Mars Pathfinder]] reset bug" <ref>{{Cite web|url=http://research.microsoft.com/~mbj/Mars_Pathfinder/|title=Mike Jones at Microsoft Research}}</ref><ref>{{Cite web |url=http://anthology.spacemonkeys.ca/archives/770-Mars-Pathfinder-Reset-Bug.html |title=Mars Pathfinder Reset Bug - Anthology of Interest |access-date=2008-09-09 |archive-date=2011-10-05 |archive-url=https://web.archive.org/web/20111005024710/http://anthology.spacemonkeys.ca/archives/770-Mars-Pathfinder-Reset-Bug.html  }}</ref> which was fixed on Mars by changing the creation flags for the semaphore so as to enable the priority inheritance.