RESOURCE ACCESS PROTOCOLS - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 242

τ i

R2 R1

τ 1

R1

τ 2

R2 R2

Figure 7.20 An absurd situation that cannot occur under SRP.

execution without blocking, since the higher-priority tasks released all resources and
when τ started the resources available were sufficient to meet the maximum request
of τ .

Theorem 7.6 (Baker) Under the Stack Resource Policy, a task τ i can be blocked for

at most the duration of one critical section.

Proof. Suppose that τ i is blocked for the duration of two critical sections shared with
two lower-priority tasks, τ 1 and τ 2 . Without loss of generality, assume π 2 <π 1 <π i .
This can happen only if τ 1 and τ 2 hold two different resources (such as R 1 and R 2 )
and τ 2 is preempted by τ 1 inside its critical section. This situation is depicted in
Figure 7.20. This immediately yields to a contradiction. In fact, since τ 1 is not blocked
by the preemption test, we have π 1 > Π s . On the other hand, since τ i is blocked, we

have π i ≤ Π s . Hence, we obtain that π i <π 1 , which contradicts the assumption.

Theorem 7.7 (Baker) The Stack Resource Policy prevents deadlocks.

Proof. By Theorem 7.5, a task cannot be blocked after it starts. Since a task cannot
be blocked while holding a resource, there can be no deadlock.