Hardware Reference
In-Depth Information
normal execution
critical section
τ
1
blocked
τ
1
τ
2
τ
3
t
0
t
1
t
2
t
3
t
4
t
5
t
6
t
7
Figure 7.4
An example of priority inversion.
Unfortunately, in the general case, the blocking time of a task on a busy resource
cannot be bounded by the duration of the critical section executed by the lower-priority
task. In fact, consider the example illustrated in Figure 7.4. Here, three tasks
τ
1
,
τ
2
,
and
τ
3
have decreasing priorities, and
τ
1
and
τ
3
share an exclusive resource protected
by a binary semaphore
S
.
If
τ
3
starts at time
t
0
, it may happen that
τ
1
arrives at time
t
2
and preempts
τ
3
inside
its critical section. At time
t
3
,
τ
1
attempts to use the resource, but it is blocked on the
semaphore
S
; thus,
τ
3
continues the execution inside its critical section. Now, if
τ
2
arrives at time
t
4
, it preempts
τ
3
(because it has a higher priority) and increases the
blocking time of
τ
1
by its entire duration. As a consequence, the maximum blocking
time that
τ
1
may experience does depend not only on the length of the critical section
executed by
τ
3
but also on the worst-case execution time of
τ
2
! This is a situation
that, if it recurs with other medium-priority tasks, can lead to uncontrolled blocking
and can cause critical deadlines to be missed. A
priority inversion
is said to occur in
the interval [
t
3
,t
6
], since the highest-priority task
τ
1
waits for the execution of lower-
priority tasks (
τ
2
and
τ
3
). In general, the duration of priority inversion is unbounded,
since any intermediate-priority task that can preempt
τ
3
will indirectly block
τ
1
.
Several approaches have been defined to avoid priority inversion, both under fixed
and dynamic priority scheduling.
1
All the methods developed in the context of fixed
priority scheduling consist in raising the priority of a task when accessing a shared
resource, according to a given protocol for entering and exiting critical sections.
1
Under EDF, such a phenomenon is sometimes referred to as
deadline inversion
.
Search WWH ::
Custom Search