BASIC PRIORITY-INHERITANCE PROTOCOL: The priority-inheritance protocol proposed by Sha, et al. [ShRL90] is also a simple protocol. It works with any preemptive, priority-driven scheduling algorithm. Like the NPCS protocol, it does not require prior knowledge on resource requirements of jobs. The priority-inheritance protocol does not prevent deadlock. When there is no deadlock (i.e., when some other method is used to prevent deadlock), the protocol ensures that no job is ever blocked for an indefinitely long time because uncontrolled priority inversion cannot occur.
In this and the next three sections, we confine our attention to the special case where there is only 1 unit of each resource. (This is the reason for calling the version described here the basic version.) By doing so, we relieve ourselves temporarily of the details that arise due to multiple resource units, so we can focus on the essence of the protocols and the behavior of the system under their control. We will return in Section 8.9 to remove this restrictive assumption.
Definition of Basic Priority-Inheritance Protocol: In the definition of this protocol, as well as other protocols described later, we call the priority that is assigned to a job according to the scheduling algorithm its assigned priority. As you will see shortly, 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. In particular, 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). Hereafter, when there is no need to be specific or there is no possible confusion, we will simply say priority when we mean either current or assigned priority.
In its simplest form, the priority-inheritance protocol is defined by the following rules. These rules govern the ways current priorities of jobs are set and jobs are scheduled when some of them contend for resources. Again, this version assumes that every resource has only 1 unit.
Rules of the Basic Priority-Inheritance Protocol
1. Scheduling Rule: Ready jobs are scheduled on the processor preemptively in a prioritydriven manner according to their current priorities. 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 ,
(a) if R is free, R is allocated to J until J releases the resource, and
(b) 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. (You will see shortly that this is not true for some other protocols.) At time t when it requests the resource, J has the highest priority among all ready jobs. The current priority πl (t) of the job Jl directly blocking J is never higher than the priority π(t) of J . Rule 3 relies on this fact.
The simple example in Figure 8–7(b) illustrates how priority inheritance affects the way jobs are scheduled and executed. The three jobs in this figure are the same as the ones in Figure 8–7(a). When J1 requests resource R and becomes blocked by J3 at time 3, job J3 inherits the priority π1 of J1. When job J2 becomes ready at 5, it cannot preempt J3 because its priority π2 is lower than the inherited priority π1 of J3. As a consequence, J3 completes its critical section as soon as possible. In this way, 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.
Figure 8–8 gives a more complex example. In this example, there are five jobs and two resources Black and Shaded. The parameters of the jobs and their critical sections are listed in part (a). As usual, jobs are indexed in decreasing order of their priorities: The priority πi of Ji is i , and the smaller the integer, the higher the priority. In the schedule in part (b) of this figure, black boxes show the critical sections when the jobs are holding Black. Shaded boxes show the critical sections when the jobs are holding Shaded.
11. At time 15, J1 completes. J2 is granted the resource Black and is now the job with the highest priority. Consequently, it begins to execute.
12. At time 17, J2 completes. Afterwards, jobs J3, J4, and J5 execute in turn to completion.