Priority Inheritance Protocol

The use of Priority inheritance allows to avoid the priority inversion problem.

 

Under this scheme, if a high priority task T1 is blocked by a lower priority task T2 (because T2 is currently executing a critical section needed by T1), the lower priority task temporarily inherits the priority of T1. When the blocking stops, T2 resumes its original priority.

 

1. If a task T1 is blocked by T2 (due to contention for a critical section) and The priority of T1 is greater than T2, task T2 inherits the priority of T1 as long as it blocks T1. when T2 exits the critical section, it reverts to its original priority .

 

2. Priority inheritance is transitive. If T3 blocks, which blocks T1(with T1 being the highest priority, T2 the medium priority and T3 being the lower priority), then T3 inherits the priority of T1 through T2.

 

Disadvantages of PIP

Priority inheritance can lead to deadlock during the following situation

 

Consider two tasks T1 and T2 uses two critical sections S1 and S2 in the following order

 

T1: Lock S1; Lock S2;Unlock S2; Unlock S1

T2: Lock S2; Lock S1;Unlock S1; Unlock S2

 

3. Assume T1 is having higher priority over T2.  Suppose T2 starts execution at Time t0. At time t1, it locks S2.
4. At time t2, T1 is initiated and it preempts T2 owing to its higher priority.
5. At time t3, T1 locks S1.
6. At time t4, T1 attempts to lock S2, which is being locked by T2. so T2 inherits the priority of T1 and starts executing,
7. At time t5, T2 tries to lock S1, which is locked by T1.
8. So both the tasks are now deadlocked.

 

This problem can be avoided by means of implementing priority Ceiling protocol