Priority inheritance
Encyclopedia
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.
Suppose H is blocked by L for some shared resource. The priority inheritance protocol requires that L executes its critical section
at the (high) priority of H. 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 now inherits the priority of H. When L exits its critical section, it regains its original (low) priority and awakens H (which was blocked by L). H, having high priority, immediately preempts L and runs to completion. This enables M and L to resume in succession and run to completion.
Real-time computing
In computer science, real-time computing , or reactive computing, is the study of hardware and software systems that are subject to a "real-time constraint"— e.g. operational deadlines from event to system response. Real-time programs must guarantee response within strict time constraints...
, priority inheritance is a method for eliminating priority inversion
Priority inversion
In computer science, priority inversion is a problematic scenario in scheduling when a higher priority task is indirectly preempted by a lower priority task effectively "inverting" the relative priorities of the two tasks....
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
Resource (computer science)
A resource, or system resource, is any physical or virtual component of limited availability within a computer system. Every device connected to a computer system is a resource. Every internal system component is a resource...
on which the process has a resource lock
Lock (computer science)
In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...
.
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
Critical section
In concurrent programming a critical section is a piece of code that accesses a shared resource that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will have to wait a fixed time to...
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:| Job Name | Priority |
|---|---|
| H | High |
| M | Medium |
| L | Low |
Suppose H is blocked by L for some shared resource. The priority inheritance protocol requires that L executes its critical section
Critical section
In concurrent programming a critical section is a piece of code that accesses a shared resource that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will have to wait a fixed time to...
at the (high) priority of H. As a result, M will be unable to preempt
Preempt
Preempt is a bid in contract bridge whose primary objectives are to thwart opponents ability to bid to their best contract, with some safety, and to fully describe one's hand to one's partner in a single bid. A preemptive bid is usually made by jumping, i.e. skipping one or more bidding levels...
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 now inherits the priority of H. When L exits its critical section, it regains its original (low) priority and awakens H (which was blocked by L). H, having high priority, immediately preempts L and runs to completion. This enables M and L to resume in succession and run to completion.
Problems
The basic priority inheritance protocol has two problems:- It does not prevent a deadlockDeadlockA deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg"...
from happening in a program with circular lock dependencies. - A chain of blocking may be formed; blocking duration can be substantial, though bounded.
External links
- Article "Priority Inheritance: 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 SakamuraKen Sakamurais a Japanese professor in Information science at the University of Tokyo. He is the creator of the real-time operating system architecture TRON.In 2001, he shared the Takeda Award for Social/Economic Well-Being with Richard Stallman and Linus Torvalds....
- Article "Hardware Support for Priority Inheritance" by Bilge E. S. Akgul, Vincent J. Mooney, Henrik Thane and Pramote Kuacharoen