Hardware Reference
In-Depth Information
EXAMPLE
In order to illustrate the Priority Ceiling Protocol, consider three tasks
τ
1
,
τ
2
, and
τ
3
having decreasing priorities. The highest-priority task
τ
1
sequentially accesses two
critical sections guarded by semaphores
S
A
and
S
B
; task
τ
2
accesses only a criti-
cal section guarded by semaphore
S
C
; whereas task
τ
3
uses semaphore
S
C
and then
makes a nested access to
S
B
. From tasks' resource requirements, all semaphores are
assigned the following priority ceilings:
⎧
⎨
C
(
S
A
)=
P
1
C
(
S
B
)=
P
1
C
(
S
C
)=
P
2
.
⎩
Now suppose that events evolve as illustrated in Figure 7.14.
At time
t
0
,
τ
3
is activated, and since it is the only task ready to run, it starts
executing and later locks semaphore
S
C
.
At time
t
1
,
τ
2
becomes ready and preempts
τ
3
.
At time
t
2
,
τ
2
attempts to lock
S
C
, but it is blocked by the protocol because
P
2
is not greater than
C
(
S
C
). Then,
τ
3
inherits the priority of
τ
2
and resumes its
execution.
At time
t
3
,
τ
3
successfully enters its nested critical section by locking
S
B
. Note
that
τ
3
is allowed to lock
S
B
because no semaphores are locked by other tasks.
At time
t
4
, while
τ
3
is executing at a priority
p
3
=
P
2
,
τ
1
becomes ready and
preempts
τ
3
because
P
1
>p
3
.
At time
t
5
,
τ
1
attempts to lock
S
A
, which is not locked by any task. However,
τ
1
is blocked by the protocol because its priority is not higher than
C
(
S
B
), which
is the highest ceiling among all semaphores currently locked by the other tasks.
Since
S
B
is locked by
τ
3
,
τ
3
inherits the priority of
τ
1
and resumes its execution.
At time
t
6
,
τ
3
exits its nested critical section, unlocks
S
B
, and, since
τ
1
is awak-
ened,
τ
3
returns to priority
p
3
=
P
2
.
At this point,
P
1
>C
(
S
C
); hence,
τ
1
preempts
τ
3
and executes until completion.
At time
t
7
,
τ
1
is completed, and
τ
3
resumes its execution at a priority
p
3
=
P
2
.
Search WWH ::
Custom Search