Hardware Reference
In-Depth Information
7.6.1
PROTOCOL DEFINITION
The Priority Inheritance Protocol can be defined as follows:
Tasks are scheduled based on their active priorities. Tasks with the same priority
are executed in a First Come First Served discipline.
When task
τ
i
tries to enter a critical section
z
i,k
and resource
R
k
is already held
by a lower-priority task
τ
j
, then
τ
i
is blocked.
τ
i
is said to be blocked by the task
τ
j
that holds the resource. Otherwise,
τ
i
enters the critical section
z
i,k
.
When a task
τ
i
is blocked on a semaphore, it transmits its active priority to the
task, say
τ
j
, that holds that semaphore. Hence,
τ
j
resumes and executes the rest
of its critical section with a priority
p
j
=
p
i
. Task
τ
j
is said to
inherit
the priority
of
τ
i
. In general, a task inherits the highest priority of the tasks it blocks. That is,
at every instant,
p
j
(
R
k
)=max
{
P
j
,
ma
h
{
P
h
|
τ
h
is blocked on
R
k
}}
.
(7.8)
When
τ
j
exits a critical section, it unlocks the semaphore, and the highest-priority
task blocked on that semaphore, if any, is awakened. Moreover, the active priority
of
τ
j
is updated as follows: if no other tasks are blocked by
τ
j
,
p
j
is set to its
nominal priority
P
j
; otherwise it is set to the highest priority of the tasks blocked
by
τ
j
, according to Equation (7.8).
Priority inheritance is transitive; that is, if a task
τ
3
blocks a task
τ
2
, and
τ
2
blocks
a task
τ
1
, then
τ
3
inherits the priority of
τ
1
via
τ
2
.
EXAMPLES
We first consider the same situation presented in Figure 7.4 and show how the prior-
ity inversion phenomenon can be bounded by the Priority Inheritance Protocol. The
modified schedule is illustrated in Figure 7.8. Until time
t
3
there is no variation in the
schedule, since no priority inheritance takes place. At time
t
3
,
τ
1
is blocked by
τ
3
,
thus
τ
3
inherits the priority of
τ
1
and executes the remaining part of its critical section
(from
t
3
to
t
5
) at the highest priority. In this condition, at time
t
4
,
τ
2
cannot preempt
τ
3
and cannot create additional interference on
τ
1
.As
τ
3
exits its critical section,
τ
1
is awakened and
τ
3
resumes its original priority. At time
t
5
, the processor is assigned
to
τ
1
, which is the highest-priority task ready to execute, and task
τ
2
can only start at
time
t
6
, when
τ
1
has completed. The active priority of
τ
3
as a function of time is also
shown in Figure 7.8 on the lowest timeline.
Search WWH ::
Custom Search