Effects of Resource Contention and

Resource Access Control

A resource access control protocol is a set of rules that govern

 When and under what conditions each request for resource is granted
 How jobs requiring resources are scheduled.

One of the major objective of resources access control is to minimize the undesirable
effects of resource allocation.

The undesirable effects of resource contention are

1. Priority Inversion
2. Timing anomalies
3. Deadlock

Priority Inversion

Priority inversion can occur when execution of some jobs or portions of jobs is non-
preemptable. As resources are allocated to jobs on a non-preemptive basis, a higher
priority job can be blocked by a lower priority job if the jobs conflict, even when the
execution of both jobs is preemptable.

In this example, there are three jobs, J1, J2, and J3, whose feasible intervals are (6,
14], (2, 17] and (0, 18], respectively. Here the lowest priority job J3 first blocks J2
and then blocks J1 while it holds the resource R such that Priority Inversion occurs in
intervals (4,6] and (8,9] .

Let us take another example

Here, jobs J1 and J3 have the highest priority and lowest priority, respectively. At
time 0, J3 becomes ready and executes. It acquires the resource R shortly
afterwards and continues to execute. After R is allocated to J3, J1 becomes ready. It
preempts J3 and executes until it requests resource R at time 3. Because the
resource is in use, J1 becomes blocked, and a priority inversion begins.

While J3 is holding the resource and executes, a job J2 with a priority higher than J3
but lower than J1 is released. Moreover, J2 does not require the resource R. This job
preempts J3 and executes to completion. Thus, J2 lengthens the duration of this
priority inversion. In this situation, the priority inversion is said to be uncontrolled.

Timing anomalies

When priority inversion occurs, timing anomalies invariably follow i.e. there may be
the chance of miss the deadline. This condition is called timing anomalies. Suppose
the critical section J3 is [R; 2.5] in the above example then J1 misses its deadline as
it does not complete until 14.5.

Deadlock
If two jobs need resource Rx and Ry and if one acquires the lock in the order Rx
then Ry and the other job acquires them in opposite order Ry then Rx then deadlock
occurs.

Here the deadlocks occurs when J1 needs Rx locked by J2 and J2 needs Ry locked
by J1.

Non-Preemptive Critical Section:

 The simplest way to control access of resources is to schedule all critical
sections on the processor non-preemptively.
 When a job holds any resources, it executes at priority higher than the priority
of all This protocol is call non-preemptive critical section protocol (NPCS).
Because no job is ever preempted when it holds any resource, deadlock can
never occur.
 The most important advantages of NPCS protocol is its simplicity especially
when the number of resource units are arbitrary.
 The protocol does not need any prior knowledge about resource requirement
of jobs.
 It is simple to implement and can be used in both fixed priority and dynamic
priority systems.
 It is clearly a good protocol when all the critical sections are short and when
most of jobs conflict with each other.
 Short coming of this protocol is that every job can be blocked by every lower
priority jobs with a critical section even if there is no resource and shows very
poor performance.

For example:

Job ri ei Critical Section

J1 6 5 R,2
J2 2 7 R,4
J3 0 6 R,4

Basic-Priority Inheritance Protocol:

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
o If R is free, R is allocated to J until J releases the resource.
o 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
 o Direct blocking: due to resource lock.
o Priority inheritance blocking 
o 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.
Priority Ceiling Protocol: 
The priority ceiling protocol extends the priority inheritance protocol to prevent
deadlocks and to further reduce the blocking time. This protocols makes following
assumptions.

 The assigned priorities of all jobs are fixed.

 The resources required by all jobs are known a priori before the execution of any job
begins.

The protocol makes use of a parameter called priority ceiling of every resource. The
priority ceiling of any resource Ri is the highest priority of all the jobs that require Ri
and is denoted by Π (Ri). At any time t, the current priority ceiling Π (t) of the system
is equal to the highest priority ceiling of the resources that are in use at that time, if
some resources are in use. If all the resources are free at the time, the current
ceiling Π (t) is Ω, a non-existing priority level that is lower than the lowest priority of
all jobs.

Rules of Priority Ceiling Protocol:

1. Scheduling rule:
c. 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.
d. Every ready job J is scheduled preemptively and in a priority driven manner at
its current priority π (t).
2. Allocation rule:

Whenever a job J requests a resource R at time t, one of the following two conditions
occurs:

a. R is held by another job J‟s request fails and J becomes blocked.

b. R is free then
0. If J’s priority π (t) is higher than current priority ceiling, R is allocated to J.
i. If J’s priority π (t) is not higher than the current priority ceiling of the system, R
is allocated to J only if J is the job holding the resource whose priority ceiling
is equal to current priority ceiling otherwise J’s request is denied and J
becomes blocked.

1. Priority Inheritance Rule:

When J becomes blocked the job Jl which blocked J inherits the current priority π (t)
of J. Jl executes at its inherited priority until the time when it releases every resource
whose priority ceiling is equal to or higher than π (t). At that time, priority of Jl returns
to its priority πl  (t’) at time t’ when it was granted the resource.

For example:

Consider a system with following parameters:

            

 The priority ceiling of the black resource is two since J2 is the highest priority job
among the jobs requiring it.
 The priority ceiling of the shaded resource is one.
 In the priority inheritance protocol figure [0,1) current ceiling of the system is Ω lower
than 5.
 In (1, 3] interval black is held by J5 so the current ceiling of the system is 2.
 In (3, 13] interval when shaded is also in use the current ceiling of the system is 1.

The access to resources are controlled by the priority ceiling protocol. Here the
priority ceiling of the resources Black and Shaded are two and one respectively.
                  

 In the interval (0,3], this schedule is the same as the schedule which is produced
under the basic priority inheritance protocol, the ceiling of the system at time 1 is Ω,
when J5 requests black it is allocated the resource according to (i) in part (b) of rule 2
after black is allocated the ceiling of the system is raised to two the priority ceiling of
black
 At time 3, J4 requests shaded, shaded is free. However, because the ceiling pi(3) is
equal to two of the system is higher than the priority of J4 ,J4’s request is denied
according to ii in part of (b) of rule two J4 is blocked and J5 inherits J4‟s priority and
executes at priority 4
 At time 4, J3 preempts J5 and at time 5 J2 preempts J3 at time 6, J2 requests black
and becomes directly blocked by J5. So J5 inherits the priority 2. It executes until J1
becomes ready and preempts During all this time , the ceiling of the system remains
at two
 When J1 request shaded at time 8, its priority is higher than the ceiling of the system.
So its request if granted according to i in part (b) of rule 2 allowing it to enter its
critical section and complete by the time 10 at time 10, J3 and J5 are ready. The
latter has a higher priority 2 ; It resumes
 At 11, when J5 releases black, its priority returns to 5 and the ceiling of the system
drops to Ω. J2 becomes unblocked is allocated black and starts to execute
 At time 14 ,after J2 and J3 complete J4 has the processor and is granted the
resource shaded because its priority is higher than Ω, the ceiling of the system at the
time. It starts to execute. The ceiling of the system is raised to one. The priority
ceiling of shaded.
 At time 16, J4 requests black, which is free, the priority of J4 is lower than current
priority ceiling Π(16), but J4 is the job holding the shaded resource whose priority
ceiling is equal to Π(16) hence J4 is granted black . It continues to execute