Basic Priority-inheritance And Priority-ceiling Protocols

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.

1. At time 0, job J5 becomes ready and executes at its assigned priority 5. At time 1, it is granted the resource Black.
2. At time 2, J4 is released. It preempts J5 and starts to execute.
3. At time 3, J4 requests Shaded. Shaded, being free, is granted to the job. The job continues to execute.
4. At time 4, J3 is released and preempts J4. At time 5, J2 is released and preempts J3.
5. At time 6, J2 executes L(Black) to request Black; L(Black) fails because Black is in use by J5. J2 is now directly blocked by J5. According to rule 3, J5 inherits the priority 2 of J2. Because J5’s priority is now the highest among all ready jobs, J5 starts to execute.
6. J1 is released at time 7. Having the highest priority 1, it preempts J5 and starts to execute.
7. 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, and J5. Therefore, it starts to execute.
8. 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.
9. At time 11, J5 releases the resource Black. 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. Consequently, J4 enters its inner critical section and proceeds to complete this and the outer critical section.
10. At time 13, J4 releases Shaded. The job no longer holds any resource; its priority returns to 4, its assigned priority. J1 becomes unblocked, acquires Shaded, and begins to execute.

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.