Hardware Reference
In-Depth Information
dispatching
activa
tion
ter
mination
READY
RUN
preemption
signal
wait
WAIT
Figure 7.1
Waiting state caused by resource constraints.
All tasks blocked on a resource are kept in a queue associated with the semaphore
that protects the resource. When a running task executes a
wait
primitive on a locked
semaphore, it enters a
waiting
state, until another task executes a
signal
primitive that
unlocks the semaphore. When a task leaves the waiting state, it does not go in the
running state, but in the ready state, so that the CPU can be assigned to the highest-
priority task by the scheduling algorithm. The state transition diagram relative to the
situation described above is shown in Figure 7.1.
In this chapter, we describe the main problems that may arise in a uniprocessor system
when concurrent tasks use shared resources in exclusive mode, and we present some
resource access protocols designed to avoid such problems and bound the maximum
blocking time of each task. We then show how such blocking times can be used in the
schedulability analysis to extend the guarantee tests derived for periodic task sets.
7.2
THE PRIORITY INVERSION PHENOMENON
Consider two tasks
τ
1
and
τ
2
that share an exclusive resource
R
k
(such as a list) on
which two operations (such as
insert
and
remove
) are defined. To guarantee the mutual
exclusion, both operations must be defined as critical sections. If a binary semaphore
S
k
is used for this purpose, then each critical section must begin with a
wait(
S
k
)
primitive and must end with a
signal(
S
k
)
primitive (see Figure 7.2).
If preemption is allowed and
τ
1
has a higher priority than
τ
2
, then
τ
1
can be blocked
in the situation depicted in Figure 7.3. Here, task
τ
2
is activated first, and after a
while, it enters the critical section and locks the semaphore. While
τ
2
is executing the
critical section, task
τ
1
arrives, and since it has a higher priority, it preempts
τ
2
and
starts executing. However, at time
t
1
, when attempting to enter its critical section,
τ
1
is blocked on the semaphore, so
τ
2
resumes.
τ
1
has to wait until time
t
2
, when
τ
2
Search WWH ::
Custom Search