Priority inheritance

Priority inheritance

In real-time computing, priority inheritance is a method for eliminating priority inversion problems. Using this programming method, a process scheduling algorithm will increase the priority of a process to the maximum priority of any process waiting for any resource on which the process has a resource lock.

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 the highest priority level of all the jobs it blocks. After executing its critical section, the job returns to its original priority level.

Example

Consider three jobs:

Suppose A is blocked by C for some shared resource. The priority inheritance protocol requires that C executes its critical section at the (high) priority of A. As a result, B will be unable to preempt C and will be blocked. That is, the higher priority job B must wait for the critical section of the lower priority job C to be executed, because C now inherits the priority of A. When C exits its critical section, it regains its original (low) priority and awakens A (which was blocked by C). A, having high priority, immediately preempts C and runs to completion. This enables B and C to resume in succession and run to completion.

Problems

The basic priority inheritance protocol has two problems:

#It does not prevent a deadlock from happening in a program with circular lock dependencies.
#A chain of blocking may be formed; blocking duration can be substantial, though bounded.

ee also

*priority ceiling protocol

References

*cite journal
author = Lui Sha, Ragunathan Rajkumar, and John P. Lehoczky
month = September
year = 1990
title = Priority Inheritance Protocols: An Approach to Real-Time Synchronization
journal = IEEE Transactions on Computers
volume = 39
issue = 9
pages = 1175–1185
issn = 0018-9340
url = http://www-md.e-technik.uni-rostock.de/ma/gol/rtsys-bib/90-toc-pcp.pdf
doi = 10.1109/12.57058

External links

*Article " [http://www.linuxdevices.com/articles/AT5698775833.html The Real Story] " by Doug Locke
*Article " [http://www.linuxdevices.com/articles/AT7168794919.html Against Priority Inheritance] " by Victor Yodaiken
*Article " [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
*Article " [http://www.sei.cmu.edu/publications/documents/89.reports/89.tr.015.html Implementing Priority Inheritance Algorithms in an Ada Runtime System] " by Mark W. Borger and Ragunathan Rajkumar
*Article " [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
*Article " [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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Priority Inheritance — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia

  • Priority Inheritance Protocol — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia

  • Priority inversion — In scheduling, priority inversion is the scenario where a low priority task holds a shared resource that is required by a high priority task. This causes the execution of the high priority task to be blocked until the low priority task has… …   Wikipedia

  • Priority ceiling protocol — In real time computing, the priority ceiling protocol is a synchronization protocol for shared resources to avoid unbounded priority inversion and mutual deadlock due to wrong nesting of critical sections. In this protocol each resource is… …   Wikipedia

  • Priority inversion — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia

  • Mendelian inheritance — For a non technical introduction to the topic, see Introduction to genetics. Part of a series on Genetics Key components Chromosome DNA • RNA Genome Heredity …   Wikipedia

  • Rate-monotonic scheduling — In computer science, rate monotonic scheduling [citation|first1=C. L.|last1=Liu|authorlink1=Chung Laung Liu|first2=J.|last2=Layland|title=Scheduling algorithms for multiprogramming in a hard real time environment|journal=Journal of the ACM|volume …   Wikipedia

  • Prioritätsvererbung — Die Prioritätsvererbung (englisch: priority inheritance) ist neben der der Prioritätsgrenze oder schranke (Priority Ceiling) eine Methode zur Behebung des Problems der Prioritätsinversion. Zu Prioritätsinversion kann es bei mindestens drei Tasks… …   Deutsch Wikipedia

  • Windows CE — Microsoft Windows CE Company / developer Microsoft Programmed in C[1] …   Wikipedia

  • OSEK — (Offene Systeme und deren Schnittstellen für die Elektronik in Kraftfahrzeugen; English: Open Systems and their Interfaces for the Electronics in Motor Vehicles ) is a standards body that has produced specifications for an embedded operating… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”