Priority inheritance

From Wikipedia, the free encyclopedia

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 the process has a resource lock on.

Basic idea of Priority Inheritance Protocol is that when a job j 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 job j returns to its original priority level.

Ex.: Consider three jobs j1, j2, j3 arranged in the descending order of priority, i.e., j1 has highest priority, and j3 has low priority. Suppose j1 is blocked by j3 for the shared resources. The priority inheritance protocol requires that the job j3 executes its critical section at the priority of j1. As a result j2 will be unable to preempt j3 and will be blocked. That is, high priority job j2 must wait for critical section of low priority job j3 be executed, because j3 now inherits (uses) the priority of j1. When j3 exits its critical section, it regains its original priority and awakens j1 which was blocked by j3. Job j1 having high priority immediately preempts j3 and runs to completion. This enables j2 and j3 to resume in succession and runs to completion.

Basic Priority Inheritance Protocol has TWO Problems:

1. Does not prevent deadlock.

2. Chain of blocking may be formed i.e., blocking duration can be substantial, though bounded.