Hardware Reference
In-Depth Information
normal execution
critical section
τ
1
a
b
τ
2
b
b
τ
3
a
a
Figure 7.12
Example of chained blocking.
If the queue of semaphore
s
is not empty, the highest-priority task in the queue is
awakened, its identifier is stored in
s.holder
, the active priority of the executing
task is updated and the ready task with the highest priority is assigned to the
processor.
7.6.5
UNSOLVED PROBLEMS
Although the Priority Inheritance Protocol bounds the priority inversion phenomenon,
the blocking duration for a task can still be substantial because a chain of blocking can
be formed. Another problem is that the protocol does not prevent deadlocks.
CHAINED BLOCKING
Consider three tasks
τ
1
,
τ
2
and
τ
3
with decreasing priorities that share two semaphores
S
a
and
S
b
. Suppose that
τ
1
needs to sequentially access
S
a
and
S
b
,
τ
2
accesses
S
b
,
and
τ
3
S
a
. Also suppose that
τ
3
locks
S
a
and it is preempted by
τ
2
within its critical
section. Similarly,
τ
2
locks
S
b
and it is preempted by
τ
1
within its critical section.
The example is shown in Figure 7.12. In this situation, when attempting to use its
resources,
τ
1
is blocked for the duration of two critical sections, once to wait for
τ
3
to release
S
a
and then to wait for
τ
2
to release
S
b
. This is called a
chained blocking
.
In the worst case, if
τ
1
accesses
n
distinct semaphores that have been locked by
n
lower-priority tasks,
τ
1
will be blocked for the duration of
n
critical sections.
Search WWH ::
Custom Search