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

7.8.4 BLOCKING TIME COMPUTATION

The maximum blocking time that a task can experience with the SRP is the same as
the one that can be experienced with the Priority Ceiling Protocol. Theorem 7.6, in
fact, guarantees that under the SRP a task τ i can be blocked for at most the duration
of one critical section among those that can block τ i . Lemma 7.8, proved for the PCP,
can be easily extended to the SRP; thus a critical section Z j,k belonging to task τ j

and

guarded by semaphore S k π i .

Note that under the SRP, the ceiling of a semaphore is a dynamic variable, so we have
to consider its maximum value; that is, the one corresponding to a number of units
currently available equal to zero.

can block a task τ i only if π j <π i and max( C S k ) ≥

Hence, a task τ i can only be blocked by critical sections belonging to tasks with pre-
emption level lower than π i and guarded by semaphores with maximum ceiling higher
than or equal to π i . That is,

γ i = { Z j,k | ( π j <π i ) and C S k (0) ≥ π i } . (7.17)

And since τ i can be blocked at most once, the maximum blocking time τ i can suffer
is given by the duration of the longest critical section among those that can block τ i .
That is,

B i =max

j,k {

δ j,k − 1 | Z j,k ∈ γ i } . (7.18)

7.8.5 SHARING RUNTIME STACK

Another interesting implication deriving from the use of the SRP is that it supports
stack sharing among tasks. This is particularly convenient for those applications con-
sisting of a large number of tasks, dedicated to acquisition, monitoring, and control
activities. In conventional operating systems, each process must have a private stack
space, sufficient to store its context (that is, the content of the CPU registers) and its
local variables. A problem with these systems is that, if the number of tasks is large, a
great amount of memory may be required for the stacks of all the tasks.

For example, consider four tasks τ 1 , τ 2 , τ 3 , and τ 4 , with preemption levels 1, 2, 2,
and 3, respectively (3 being the highest preemption level). Figure 7.21 illustrates a
possible evolution of the stacks, assuming that each task is allocated its own stack
space, equal to its maximum requirement. At time t 1 , τ 1 starts executing; τ 2 preempts
at time t 2 and completes at time t 3 , allowing τ 1 to resume. At time t 4 , τ 1 is preempted
by τ 3 , which in turn is preempted by τ 4 at time t 5 . At time t 6 , τ 4 completes and τ 3

resumes. At time t 7 , τ 3 completes and τ 1 resumes.