Sources
Help build the largest human-edited directory on the web.
Submit a site - Become an editor
Wikipedia. Licensed under the GNU Free Documentation License.
Are you an expert in this subject? Join the discussion and share your knowledge at Wikipedia.org.
Priority inheritance
From Wikipedia, the free encyclopedia
 |
This article may require cleanup to meet Wikipedia's quality standards. Please discuss this issue on the talk page or replace this tag with a more specific message. This article has been tagged since March 2007. |
In computer science, 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.
Contents |
Consider three jobs:
| Job Name | Priority |
|---|---|
| A | High |
| B | Medium |
| C | Low |
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.
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.
- Priority Inheritance Protocols: By Sha, Rajkumar and Lehoczky.
- Embedded Systems Material at IIT Bombay
- Article "The Real Story" by Doug Locke
- Article "Against Priority Inheritance" by Victor Yodaiken
- Article "Implementing Concurrency Control With Priority Inheritance in Real-Time CORBA" by Steven Wohlever, Victor Fay Wolfe and Russell Johnston
- Article "Implementing Priority Inheritance Algorithms in an Ada Runtime System" by Mark W. Borger and Ragunathan Rajkumar
- Article "Priority Inheritance Spin Locks for Multiprocessor Real-Time Systems" by Cai-Dong Wang, Hiroaki Takada and Ken Sakamura
- Article "Hardware Support for Priority Inheritance" by Bilge E. S. Akgul, Vincent J. Mooney, Henrik Thane and Pramote Kuacharoen
- Citations from CiteSeer
