Hardware Reference
In-Depth Information
τ
1
τ
2
normal execution
critical section
blocked on S
b
blocked on S
wait(S )
wait(S )
a
a
b
τ
1
a
wait(S )
wait(S )
b
a
τ
2
signal(S )
signal(S )
b
b
b
a
t
1
t
2
t
3
t
4
t
5
signal(S )
signal(S )
a
b
Figure 7.13
Example of deadlock.
DEADLOCK
Consider two tasks that use two semaphores in a nested fashion but in reverse order,
as illustrated in Figure 7.13. Now suppose that, at time
t
1
,
τ
2
locks semaphore
S
b
and
enters its critical section. At time
t
2
,
τ
1
preempts
τ
2
before it can lock
S
a
. At time
t
3
,
τ
1
locks
S
a
, which is free, but then is blocked on
S
b
at time
t
4
. At this time,
τ
2
resumes and continues the execution at the priority of
τ
1
. Priority inheritance does
not prevent a deadlock, which occurs at time
t
5
, when
τ
2
attempts to lock
S
a
. Note,
however, that the deadlock does not depend on the Priority Inheritance Protocol but is
caused by an erroneous use of semaphores. In this case, the deadlock problem can be
solved by imposing a total ordering on the semaphore accesses.
7.7
PRIORITY CEILING PROTOCOL
The Priority Ceiling Protocol (PCP) was introduced by Sha, Rajkumar, and Lehoczky
[SRL90] to bound the priority inversion phenomenon and prevent the formation of
deadlocks and chained blocking.
The basic idea of this method is to extend the Priority Inheritance Protocol with a rule
for granting a lock request on a free semaphore. To avoid multiple blocking, this rule
does not allow a task to enter a critical section if there are locked semaphores that
could block it. This means that once a task enters its first critical section, it can never
be blocked by lower-priority tasks until its completion.
Search WWH ::
Custom Search