RESOURCE ACCESS PROTOCOLS - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 212

7.4.1 BLOCKING TIME COMPUTATION

Since a task τ i cannot preempt a lower priority task τ j if τ j is inside a critical section,
then τ i can potentially be blocked by any critical section belonging to a lower priority
task. Hence,

γ i = { Z j,k | P j <P i ,k =1 ,...,m }

Moreover, since a task inside a resource R cannot be preempted, only one resource
can be locked at any time t . Hence, a task τ i can be blocked at most for the length
of a single critical section belonging to lower priority tasks. As a consequence, the
maximum blocking time τ i can suffer is given by the duration of the longest critical
section among those belonging to lower priority tasks. That is,

B i =max

j,k {

δ j,k − 1 | Z j,k ∈ γ i } . (7.4)

Note that one unit of time is subtracted from δ j,k since Z j,k must start before the
arrival of τ i to block it. The unnecessary blocking illustrated in Figure 7.6 can easily
be avoided by raising the priority inside a critical section at an opportune level that
does not prevent a high priority task to preempt when it is not sharing that resource.

7.5 HIGHEST LOCKER PRIORITY PROTOCOL

The Highest Locker Priority (HLP) protocol improves NPP by raising the priority of
a task that enters a resource R k to the highest priority among the tasks sharing that
resource. In particular, as soon as a task τ i enters a resource R k , its dynamic priority

is raised to the level

p i ( R k )=ma h { P h | τ h uses R k } . (7.5)

The dynamic priority is then reset to the nominal value P i when the task exits the
critical section. The online computation of the priority level in Equation (7.5) can be
simplified by assigning each resource R k a priority ceiling C ( R k ) (computed off-line)
equal to the maximum priority of the tasks sharing R k ; that is:

C ( R k ) de =ma h {

P h | τ h uses R k } . (7.6)

Then, as soon as a task τ i enters a resource R k , its dynamic priority is raised to the
ceiling of the resource. For this reason, this protocol is also referred to as Immediate
Priority Ceiling .