It Works with any preemptive, priority driven scheduling algorithm and does not require prior knowledge on resource requirements of jobs. The priority inheritance protocol does not prevent deadlock .

When there is no deadlock the protocol ensures that no job is ever blocked for an indefinitely long time because uncontrolled priority inversion cannot occur.

Definition:

At any time t, each ready job Jl is scheduled and executes at its current priority πl(t) which may differ from its assigned priority and may vary with time. The current priority πl(t) of a job Jl may be raised to the higher priority πh(t) of another job Jh. When this happens, we say that the lower priority job Jl inherits the priority of the higher priority job Jh and that Jl executes at its inherited priority πh(t).

Rules of Priority Inheritance Protocol:

  1. Scheduling Rule: Ready jobs are scheduled on the processor preemptively in a priority driven manner according to their current At its release time t, the current priority π (t) of every job J is equal to its assigned priority. The job remains at this priority except under the condition stated in rule 3.
  2. Allocation Rule: When a job J requests a resource R, at time t
    • If R is free, R is allocated to J until J releases the resource.
    • If R is not free, the request is denied and J is blocked.
  3. Priority Inheritance Rule: When the requesting job J becomes blocked the job Jl which blocks J inherits the current priority π(t) of J . The job Jl executes at its inherited priority π 

    (t) until it releases R at that time, the priority of Jl returns to its priority πl(t’) at the time t’ when it acquires the resource R .

    According to this protocol, a job J is denied a resource only when the resource requested by it is held by another job.


When Jl requests R and becomes blocked by J3 at time 3 , job J3 inherits the priority π1 of Jl When job J2 becomes ready at 5, it cannot preempt J3 as its priority π2 is lower than the inherited priority π1 of J3 So J3 completes its critical section as soon as possible The protocol ensures that the duration of priority inversion is never longer than the duration of an outermost critical section each time a job is blocked.

For another example:

Consider a system with following parameters:

Then the schedule time diagram using priority inheritance rule can be constructed as:

  • At time 0, job J5 becomes ready and executes at its assigned priority 5. At time 1 it is granted the resource black
  • At time 2, J4 is released it preempts J5 and starts to execute
  • At time 3 J4 requests Shaded being free is granted to the job. The job continues to executes
  • At time 4, J3 is released and preempts J4. at time 5, J2 is released and preempts J3
  • At time 6, J2 executes L (black) to request black; L (black) fails as black is in use by J J2 is a now directly blocked by J5. According to rule 3, J5 inherits the priority 2 of J2. as J5‟s priority is now the highest among already jobs J5 starts to execute
  • J1 is released at time Having the highest priority 1 it preempts J5 and starts to execute
  • At time 8, J1 executes L (shaded) which fails, and becomes blocked. Since J4 has shaded at the time, it directly blocks J1 and consequently inherits J1‟s priority 1. J4 now has the highest priority among the ready jobs J3, J4, J5 therefore it starts to execute
  • At time 9, J4 requests the resource black and becomes directly blocked by J5. At this time the current priority of J4 is 1. The priority it has inherited from J1 since time 8. therefore , J5 inherits priority 1 and begins to execute
  • At time 11, J5 releases the resource Its priority returns to 5, which was its priority when it acquired black. The job with the highest priority among all unblocked jobs is J4. J4 enters its inner critical section and proceeds to complete this and the outer critical section
  • At time 13, J4 releases The job no longer holds any resource. Its priority returns to 4, its assigned priority, J1 becomes unblocked acquires shaded and begins to execute
  • At time 15, J1 J2 is granted the resource black and is now the job with the highest priority. Hence it begins to execute.
  • At time 17, J2 completes. Later on, jobs J3, J4 and J5 execute in turn to completion

Properties of Priority Inheritance Protocol:

  • Simple to implement, does not require the prior knowledge of resource requirement.
  • Job exhibits different types of blocking
    • Direct blocking: due to resource lock.
    • Priority inheritance blocking 
    • Transitive blocking
  • Deadlock is not preveted.
  • It can be reduce blocking time compared to non-preemptive critical section but does not guarantee to minimize blocking.