CONTENTS

15.1 The Priority Inversion Problem

15.2 The Priority Inheritance Protocol

15.3 The Priority Ceiling Protocol

15.4 Schedulability Analysis and Examples

15.5 Summary

15.1 The Priority Inversion Problem

In a real-time system, task interaction must be designed with great care, above all when the tasks being synchronized have different priorities. Informally speaking, when a high-priority task is waiting for a lower-priority task to complete some required computation, the task priority scheme is, in some sense, being hampered because the high-priority task would take precedence over the lower-priority one in the model.

This happens even in very simple cases, for example, when several tasks access a shared resource by means of a critical region protected by a mutual exclusion semaphore. Once a lower-priority task enters its critical region, the semaphore mechanism will block any higher-priority task wanting to enter its own critical region protected by the same semaphore and force it to wait until the former exits. This phenomenon is called priority inversion and, if not adequately addressed, can have adverse effects on the schedulability of the system, to the point of making the response time of some tasks completely unpredictable because the priority inversion region may last for an unbounded amount of time. Accordingly, such as a situation is usually called unbounded priority inversion.

It can easily be seen that priority inversion can (and should) be reduced to a minimum by appropriate software design techniques aimed at avoiding, for instance, redundant task interactions when the system can be designed in a different way. At the same time, however, it is also clear that the problem cannot completely solved in this way except in very simple cases. It can then be addressed in two different ways:

1. Modify the mutual exclusion mechanism by means of an appropriate technique, to be discussed in this chapter. The modification shall guarantee that the blocking time endured by each individual task in the system has a known and finite upper bound. This worst-case blocking time can then be used as an additional ingredient to improve the schedulability analysis methods discussed so far.

2. Depart radically from what was discussed in Chapter 5 and devise a way for tasks to exchange information through a shared memory in a meaningful way without resorting to mutual exclusion or, more in general, without ever forcing them to wait. This has been the topic of Chapter 10.

Before going further with the discussion, presenting a very simple example of unbounded priority inversion is useful to better understand what the priority inversion problem really means from a practical standpoint. The same example will also be used in the following to gain a better understanding of how the different methods address the priority inversion issue.

Let us consider the execution of three real-time tasks τ_H (high priority), τ_M (middle priority), and τ_L (low priority), executed under the control of a fixed-priority scheduler on a single-processor system. We will also assume, as shown in Figure 15.1, that τ_H and τ_L share some information, stored in a certain shared memory area M.

Being written by proficient concurrent programmers (who carefully perused Chapter 5) both τ_H and τ_L make access to M only within a suitable critical region, protected by a mutual exclusion semaphore m. On the contrary, τ_M has nothing to do with τ_H and τ_L, that is, it does not interact with them in any way. The only relationship among τ_M and the other two tasks is that “by chance” it was assigned a priority that happens to be between the priority of τ_H and τ_L.

In the previous statement, the meaning of the term “by chance” is that the peculiar priority relationship may very well be unknown to the programmers who wrote τ_H, τ_M, and τ_L. For example, we saw that, according to the Rate Monotonic (RM) priority assignment, the priority of a task depends only on its period. When different software modules—likely written by distinct groups of programmers and made of several tasks each—are put together to build the complete application, it may be very hard to predict how the priority of a certain task will be located, with respect to the others.

The following sequence of events may happen:

• Initially, neither τ_H nor τ_M are ready for execution. They may be, for instance, periodic tasks waiting for their next execution instance or they may be waiting for the completion of an I/O operation.

• On the other hand, τ_L is ready; the fixed-priority scheduler moves it into the Running state and executes it.

• During its execution, at t₁ in the figure, τ_L enters into its critical region R_L, protected by semaphore m. The semaphore primitive P(m) at the critical region’s boundary is nonblocking because no other tasks are accessing the shared memory M at the moment. Therefore, τ_L is allowed to proceed immediately and keeps running within the critical region.

• If τ_H becomes ready while τ_L still is in the critical region, the fixed-priority scheduler stops executing τ_L, puts it back into the Ready state, moves τ_H into the Running state and executes it. This action has been called preemption in Chapter 12 and takes place at t₂ in the figure.

• At t₃,task τ_M becomes ready for execution and moves into the Ready state, too, but this has no effect on the execution of τ_H, because the priority of τ_M is lower than the priority of τ_H.

• As τ_H proceeds with its execution, it may try to enter its critical region. In the figure, this happens at t₄.At thispoint, τ_H is blocked by the semaphore primitive P(m) because the value of semaphore m is now zero. This behavior is correct since τ_L is within its own critical region R_L, and the semaphore mechanism is just enforcing mutual exclusion between R_L and R_H, the critical region τ_H wants to enter.

• Since τ_H is no longer able to run, the scheduler chooses another task to execute. As τ_M and τ_L are both Ready but the priority of τ_M is greater than the priority of τ_L, the former is brought into the Running state and executed.

Therefore, starting from t₄ in Figure 15.1, a priority inversion region begins: τ_H (the highest priority task in the system) is blocked by τ_L (a lower priority task) and the system executed τ_M (yet another lower priority task). In the figure, this region is highlighted by a gray background.

Although the existence of this priority inversion region cannot be questioned because it entirely depends on how the mutual exclusion mechanism for the shared memory area M has been designed to work, an interesting question is for how long it will last.

Contrary to expectations, the answer is that the duration of the priority inversion region does not depend at all on the two tasks directly involved in it, that is, τ_H and τ_L. In fact, τ_H is in the Blocked state and, by definition, it cannot perform any further action until τ_L exits from R_L and executes V(m) to unblock it. On its part, τ_L is Ready, but it is not being executed because the fixed-priority scheduler does not give it any processor time. Hence, it has no chance of proceeding through R_L and eventually execute V(m).

The length of the priority inversion region depends instead on how much time τ_M keeps running. Unfortunately, as discussed above, τ_M has nothing to do with τ_H and τ_L. The programmers who wrote τ_H and τ_L may even be unaware that τ_M exists. The existence of multiple middle-priority tasks τ_M1, ..., τ_Mn instead of a single one makes the situation even worse. In a rather extreme case, those tasks could take turns entering the Ready state and being executed so that, even if none of them keeps running for a long time individually, taken as a group there is always at least one task τ_Mk in the Ready state at any given instant. In that scenario, τ_H will be blocked for an unbounded amount of time by τ_M1, ..., τ_Mn even if they all have a lower priority than τ_H itself.

In summary, we are willing to accept that a certain amount of blocking of τ_H by some lower-priority tasks cannot be removed. By intuition, when τ_H wants to enter its critical region R_H in the example just discussed, it must be prepared to wait up to the maximum time needed by τ_L to execute within critical region R_L. This is a direct consequence of the mutual exclusion mechanism, which is necessary to access the shared resources in a safe way. However, it is also necessary for the blocking time to have a computable and finite upper bound. Otherwise, the overall schedulability of the whole system, and of τ_H in particular, will be compromised in a rather severe way.

As for many other concurrent programming issues, it must also be remarked that this is not a systematic error. Rather, it is a time-dependent issue that may go undetected when the system is bench tested.

15.2 The Priority Inheritance Protocol

Going back to the example shown in Figure 15.1, it is easy to notice that the root cause of the unbounded priority inversion was the preemption of τ_L by τ_H while τ_L was executing within R_L. If the context switch from τ_L to τ_H had been somewhat delayed until after the execution of V(m) by τ_L—that is, until the end of R_L—the issue would not have occurred.

On a single-processor system, a very simple (albeit drastic) solution to the unbounded priority inversion problem is to forbid preemption completely during the execution of all critical regions. This may be obtained by disabling the operating system scheduler or, even more drastically, turning interrupts off within critical regions. In other words, with this approach any task that successfully enters a critical region implicitly gains the highest possible priority in the system so that no other task can preempt it. The task goes back to its regular priority when it exits from the critical region.

One clear advantage of this method is its extreme simplicity. It is also easy to convince oneself that it really works. Informally speaking, if we prevent any tasks from unexpectedly losing the processor while they are holding any mutual exclusion semaphores, they will not block any higher-priority tasks for this reason should they try to get the same semaphores. At the same time, however, the technique introduces a new kind of blocking, of a different nature.

That is, any higher-priority task τ_M that becomes ready while a low-priority task τ_L is within a critical region will not get executed—and we therefore consider it to be blocked by τ_L—until τ_L exits from the critical region. This happens even if τ_M does not interact with τ_L at all. The problem has been solved anyway because the amount of blocking endured by τ_M is indeed bounded. The upper bound is the maximum amount of time τ_L may actually spend running within its critical region. Nevertheless, we are now blocking some tasks, like τ_M, which were not blocked before.

For this reason, this way of proceeding is only appropriate for very short critical regions, because it causes much unnecessary blocking. A more sophisticated approach is needed in the general case, although introducing additional kinds of blocking into the system in order to set an upper bound on the blocking time is a trade-off common to all the solutions to the unbounded priority inversion problem that we will present in this chapter. We shall see that the approach just discussed is merely a strongly simplified version of the priority ceiling emulation protocol, to be described in Section 15.3.

In any case, the underlying idea is useful: the unbounded priority inversion problem can be solved by means of a better cooperation between the synchronization mechanism used for mutual exclusion and the processor scheduler. This cooperation can be implemented, for instance, by allowing the mutual exclusion mechanism to temporarily change task priorities. This is exactly the way the priority inheritance algorithm, or protocol, works.

The priority inheritance protocol has been proposed by Sha, Rajkumar, and Lehoczky [79], and offers a straightforward solution to the problem of unbounded priority inversion. The general idea is to dynamically increase the priority of a task as soon as it is blocking some higher-priority tasks. In particular, if a task τ_L is blocking a set of n higher-priority tasks τ_H1, ..., τ_Hn at a given instant, it will temporarily inherit the highest priority among them. This prevents any middle-priority task from preempting τ_L and unduly make the blocking experienced by τ_H1, ..., τ_Hn any longer than necessary.

In order to define the priority inheritance protocol in a more rigorous way and look at its most important properties, it is necessary to set forth some additional hypotheses and assumptions about the system being considered. In particular,

• It is first of all necessary to distinguish between the initial, or baseline, priority given to a task by the scheduling algorithm and its current, or active, priority. The baseline priority is used as the initial, default value of the active priority but, as we just saw, the latter can be higher if the task being considered is blocking some higher-priority tasks.

• The tasks are under the control of a fixed-priority scheduler and run within a single-processor system. The scheduler works according to active priorities.

• If there are two or more highest-priority tasks ready for execution, the scheduler picks them in First-Come First-Served (FCFS) order.

• Semaphore wait queues are ordered by active priority as well. In other words, when a task executes a V(s) on a semaphore s and there is at least one task waiting on s, the highest-priority waiting task will be put into the Ready state.

• Semaphore waits due to mutual exclusion are the only source of blocking in the system. Other causes of blocking such as, for example, I/O operations, must be taken into account separately, as discussed in Chapter 16.

The priority inheritance protocol itself consists of the following set of rules:

1. When a task τ_H attempts to enter a critical region that is “busy”—that is, its controlling semaphore has already be taken by another task τ_L—it blocks, but it also transmits its active priority to the task τ_L that is blocking it if the active priority of τ_L is lower than τ_H ’s.

2. As a consequence, τ_L will execute the rest of its critical region with a priority at least equal to the priority it just inherited. In general, a task inherits the highest active priority among all tasks it is blocking.

3. When a task τ_L exits from a critical region and it is no longer blocking any other task, its active priority returns back to the baseline priority.

4. Otherwise, if τ_L is still blocking some tasks—this happens when critical regions are nested into each other—it inherits the highest active priority among them.

Although this is not a formal proof at all, it can be useful to apply the priority inheritance protocol to the example shown in Figure 15.1 to see that it really works, at least in a very simple case. The result is shown in Figure 15.2. The most important events that are different with respect to the previous figure are highlighted with a gray background:

• From t₁ to t₄ the system behaves as before. The priority inheritance protocol has not been called into action yet, because no tasks are blocking any other, and all tasks have got their initial, or baseline, priority.

  

  FIGURE 15.2
  A simple application of the priority inheritance protocol involving three tasks.

• At t₄, τ_H is blocked by the semaphore primitive P(m) because the value of semaphore m is zero. At this point, τ_H is blocked by τ_L because τ_L is within a critical region controlled by the same semaphore m. Therefore, the priority inheritance protocol makes τ_L inherit the priority of τ_H.

• Regardless of the presence of one (or more) middle-priority tasks like τ_M, at t₄ the scheduler resumes the execution of τ_L because its active priority is now the same as τ_H ’s priority.

• At t₅, τ_L eventually finishes its work within the critical region R_L and releases the mutual exclusion semaphore with a V(m). This has two distinct effects: the first one pertains to task synchronization, and the second one concerns the priority inheritance protocol:

  1. Task τ_H acquires the mutual exclusion semaphore and returns to the Ready state;

  2. Task τ_L returns to its baseline priority because it is no longer blocking any other task, namely, it is no longer blocking τ_H.

  Consequently, the scheduler immediately preempts the processor from τ_L and resumes the execution of τ_H.

• Task τ_H executes within its critical region from t₅ until t₆. Then it exits from the critical region, releasing the mutual exclusion semaphore with V(m), and keeps running past t₆.

Even from this simple example, it is clear that the introduction of the priority inheritance protocol makes the concept of blocking more complex than it was before. Looking again at Figure 15.2, there are now two distinct kinds of blocking rather than one, both occurring between t₄ and t₅:

1. Direct blocking occurs when a high-priority task tries to acquire a resource held by a lower-priority task. In this case, τ_H is blocked by τ_L. Direct blocking was already present in the system and is necessary for mutual exclusion, to ensure the consistency of the shared resources.

2. Instead, push-through blocking is a consequence of the priority inheritance protocol. It occurs when an intermediate-priority task (τ_M in this example) cannot run because a lower-priority task (τ_L in our case) has temporarily inherited a higher priority. This kind of blocking may affect a task even if it does not use any shared resource, just as it happens to τ_M in the example. Nevertheless, it is necessary to avoid unbounded priority inversion.

In the following, we will present the main properties of the priority inheritance protocol. The final goal will be to prove that the maximum blocking time that each task may experience is bounded in all cases. The same properties will also be useful to define several algorithms that calculate the worst-case blocking time for each task in order to analyze the schedulability of a periodic task set. As the other schedulability analysis algorithms discussed in Chapters 13 and 14, these algorithms entail a trade-off between the tightness of the bound they compute and their complexity.

For simplicity, in the following discussion the fact that critical regions can be nested into each other will be neglected. Under the assumption that critical regions are properly nested, the set of critical regions belonging to the same task is partially ordered by region inclusion. Proper nesting means that, as shown in Figure 15.3, if two (or more) critical regions R₁ and R₂ overlap in a given task, then either the boundaries of R₂ are entirely contained in R₁ or the other way around.

For each task, it is possible to restrict the attention to the set of maximal blocking critical regions, that is, regions that can be a source of blocking for some other task but are not included within any other critical region with the same property. It can be shown that most results discussed in the following are still valid even if only maximal critical regions are taken into account, unless otherwise specified. The interested reader should refer to Reference [79] for more information about this topic.

The first lemma we shall discuss establishes under which conditions a high-priority task τ_H can be blocked by a lower-priority task.

Proof. The lemma can be proved by observing that if τ_L is not within a critical region when τ_H is released, it will be preempted immediately by τ_H itself. Moreover, it cannot block τ_H in the future, because it does not hold any mutual exclusion semaphore that τ_H may try to acquire, and the priority inheritance protocol will not boost its priority.

On the other hand, if τ_L is within a critical region when τ_H is released but neither of the two conditions is true, there is no way for τ_L to either block τ_H directly or get a priority high enough to block τ_H by means of push-through blocking.

When the hypotheses of Lemma 15.1 are satisfied, then task τ_L can block τ_H. The same concept can also be expressed in two slightly different, but equivalent, ways:

1. When the focus of the discussion is on critical regions, it can also be said that that the critical region Z, being executed by τ_L when τ_H is released, can block τ_H. Another, equivalent way of expressing this concept is to say that Z is a blocking critical region for τ_H.

2. Since critical regions are always protected by mutual exclusion semaphores in our framework, if critical region Z is protected by semaphore S_Z, it can also be said that the semaphore S_Z can block τ_H.

Now that the conditions under which tasks can block each other are clear, another interesting question is how many times a high-priority task τ_H can be blocked by lower-priority tasks during the execution of one of its instances, and for how long. One possible answer is given by the following lemma:

Proof. According to Lemma 15.1, for τ_L to block τ_H, τ_L must be executing a critical region that is a blocking critical region for τ_H. Blocking can by either direct or push-through.

When τ_L eventually exits from that critical region, its active priority will certainly go back to a value less than the priority of τ_H. From this point on, τ_H can preempt τ_L, and it cannot be blocked by τ_L again. Even if τ_H will be blocked again on another critical region, the blocking task will inherit the priority of τ_H itself and thus prevent τ_L from being executed.

The only exception happens when τ_H relinquishes the processor for other reasons, thus offering τ_L a chance to resume execution and acquire another mutual exclusion semaphore. However, this is contrary to the assumption that semaphore waits due to mutual exclusion are the only source of blocking in the system.

In the general case, we consider n lower-priority tasks τ_L1, ..., τ_Ln instead of just one. The previous lemma can be extended to cover this case and conclude that the worst-case blocking time experienced by τ_H is bounded even in that scenario.

Proof. Lemma 15.2 states that each lower-priority task τ_Li can block τ_H for at most the duration of one of its critical sections. The critical section must be one of those that can block τ_H according to Lemma 15.1.

In the worst case, the same scenario may happen for all the n lower-priority tasks, and hence, τ_H can be blocked at most n times, regardless of how many semaphores τ_H uses.

More important information we get from this lemma is that, provided all tasks only spend a finite amount of time executing within their critical regions in all possible circumstances, then the maximum blocking time is bounded. This additional hypothesis is reasonable because, by intuition, if we allowed a task to enter a critical region and execute within it for an unbounded amount of time without ever leaving, the mutual exclusion framework would no longer work correctly anyway since no other tasks would be allowed to get into any critical region controlled by the same semaphore in the meantime.

It has already been discussed that push-through blocking is an additional form of blocking, introduced by the priority inheritance protocol to keep the worst-case blocking time bounded. The following lemma gives a better characterization of this kind of blocking and identifies which semaphores can be responsible for it.

Proof. The lemma can be proved by showing that, if the conditions set forth by the lemma do not hold, then push-through blocking cannot occur.

If S is not accessed by any task τ_L with a priority lower than the priority of τ_H, then, by definition, push-through blocking cannot occur.

Let us then suppose that S is indeed accessed by a task τ_L, with a priority lower than the priority of τ_H. If S is not accessed by any task that has or can inherit a priority higher than the priority of τ_H, then the priority inheritance mechanism will never give to τ_L an active priority higher than τ_H. In this case, τ_H can always preempt τ_L and, again, push-through blocking cannot take place.

If both conditions hold, push-trough blocking of τ_H by τ_L may occur, and the lemma follows.

It is also worth noting that, in the statement of Lemma 15.4, it is crucial to perceive the difference between saying that a task has a certain priority or that it can inherit that priority:

• When we say that a task has a certain priority, we are referring to its baseline priority.

• On the other hand, a task can inherit a certain priority higher than its baseline priority through the priority inheritance mechanism.

Lemma 15.3 states that the number of times a certain task τ_H can be blocked is bounded by n, that is, how many tasks have a priority lower than its own but can block it. The following lemma provides a different bound, based on how many semaphores can block τ_H. As before, the definition of “can block” must be understood according to what is stated in Lemma 15.1.

The two bounds are not equivalent because, in general, there is no oneto-one correspondence between tasks and critical regions, as well as between critical regions and semaphores. For example, τ_H may pass through more than one critical region but, if they are guarded by the same semaphore, it will be blocked at most once. Similarly, a single task τ_L may have more than one blocking critical region for τ_H, but it will nevertheless block τ_H at most once.

Proof. Lemma 15.1 establishes that a certain lower-priority task—let us call it τ_L—can block τ_H only if it is currently executing within a critical region that satisfies the hypotheses presented in the lemma itself and is therefore a blocking critical region for τ_H.

Since each critical region is protected by a mutual exclusion semaphore, τ_L must necessarily have acquired that mutual exclusion semaphore upon entering the critical region and no other tasks can concurrently be within another critical region associated with the same semaphore. Hence, only one of the lower-priority tasks, τ_L in our case, can be within a blocking critical region protected by any given semaphore S_i.

Due to Lemma 15.2, as soon as τ_L leaves the blocking critical region, it can be preempted by τ_H and can no longer block it. Therefore, for each semaphore S_i, at the most one critical region can induce a blocking on τ_H. Repeating the argument for the m semaphores proves the lemma.

At this point, by combining Lemmas 15.3 and 15.5, we obtain the following important theorem, due to Sha, Rajkumar, and Lehoczky [79].

It should be stressed that a critical region or a semaphore can block a certain task τ_H even if the critical region does not belong to τ_H, or τ_H does not use the semaphore.

An important phenomenon that concerns the priority inheritance protocol and makes its analysis more difficult is that priority inheritance must be transitive. A transitive priority inheritance occurs when a high-priority task τ_H is directly blocked by an intermediate-priority task τ_M, which in turn is directly blocked by a low-priority task τ_L.

In this case, the priority of τ_H must be transitively transmitted not only to τ_M but to τ_L, too. Otherwise, the presence of any other intermediate-priority task could still give rise to an unbounded priority inversion by preempting τ_L at the wrong time. The scenario is illustrated in Figure 15.4. There, if there is no transitive priority inheritance, τ_H’s blocking may be unbounded because τ_B can preempt τ_L. Therefore, a critical region of a task can block a higher-priority task via transitive priority inheritance, too.

Fortunately, the following lemma makes it clear that transitive priority inheritance can occur only in a single, well-defined circumstance.

Proof. In the proof, we will use the same task nomenclature just introduced to define transitive priority inheritance. Since τ_H is directly blocked by τ_M, then τ_M must hold a semaphore, say S_M. But, by hypothesis, τ_M is also directly blocked by a third task τ_L on a different semaphore held by τ_L, say S_L.

As a consequence, τ_M must have performed a blocking P() on S_L after successfully acquiring S_M, that is, within the critical region protected by S_M. This corresponds to the definition of properly nested critical regions.

If transitive priority inheritance is ruled out with the help of Lemma 15.6, that is, if nested critical regions are forbidden, a stronger version of Lemma 15.4 holds:

Proof. As long as push-through blocking is concerned, the statement of the lemma is the same as Lemma 15.4, minus the “can inherit” clause. The reasoning is valid because Lemma 15.6 rules out transitive priority inheritance if critical regions are not nested. Moreover, transitive inheritance is the only way for a task to acquire a priority higher than the highest-priority task with which it shares a resource.

The conditions set forth by this lemma also cover direct blocking because semaphore S can directly block a task τ_H only if it is used by another task with a priority less than the priority of τ_H,and by τ_H itself. As a consequence, the lemma is valid for all kinds of blocking (both direct and push-through).

If nested critical regions are forbidden, as before, the following theorem provides an easy way to compute an upper bound on the worst-case blocking time that a task τ_i can possibly experience.

Proof. The proof of this theorem descends from the straightforward application of the previous lemmas. The function usage(k, i) captures the conditions under which semaphore S_k can block τ_i by means of either direct or push-through blocking, set forth by Lemma 15.7.

A single semaphore S_k may guard more than one critical region, and it is generally unknown which specific critical region will actually cause the blocking for task τ_i. It is even possible that, on different execution instances of τ_i, the region will change. However, the worst-case blocking time is still bounded by the worst-case execution time among all critical regions guarded by S_k, that is, C(k).

Eventually, the contributions to the worst-case blocking time coming from the K semaphores are added together because, as stated by Lemma 15.5, τ_i can be blocked at most once for each semaphore.

It should be noted that the algorithm discussed in Theorem 15.2 is not optimal for the priority inheritance protocol, and the bound it computes is not so tight because

• It assumes that if a certain semaphore can block a task, it will actually block it.

• For each semaphore, the blocking time suffered by τ_i is assumed to be equal to the execution time of the longest critical region guarded by that semaphore even if that particular critical region is not a blocking critical region for τ_i.

However, it is an acceptable compromise between the tightness of the bound it calculates and its computational complexity. Better algorithms exist and are able to provide a tighter bound of the worst-case blocking time, but their complexity is much higher.

15.3 The Priority Ceiling Protocol

Even if the priority inheritance protocol just described enforces an upper bound on the number and the duration of blocks a high-priority task τ_H can encounter, it has several shortcomings:

• In the worst case, if τ_H tries to acquire n mutual exclusion semaphores that have been locked by n lower-priority tasks, it will be blocked for the duration of n critical regions. This is called chained blocking.

• The priority inheritance protocol does not prevent deadlock from occurring. Deadlock must be avoided by some other means, for example, by imposing a total order on semaphore accesses, as discussed in Chapter 4.

All of these issues are addressed by the priority ceiling protocols, also proposed by Sha, Rajkumar, and Lehoczky [79]. In this chapter we will discuss the original priority ceiling protocol and its immediate variant; both have the following properties:

1. A high-priority task can be blocked at most once during its execution by lower-priority tasks.

2. They prevent transitive blocking even if critical regions are nested.

3. They prevent deadlock.

4. Mutual exclusive access to resources is ensured by the protocols themselves.

The basic idea of the priority ceiling protocol is to extend the priority inheritance protocol with an additional rule for granting lock requests to a free semaphore. The overall goal of the protocol is to ensure that, if task τ_L holds a semaphore and it could lead to the blocking of an higher-priority task τ_H, then no other semaphores that could also block τ_H are to be acquired by any task other than τ_L itself.

A side effect of this approach is that a task can be blocked, and hence delayed, not only by attempting to lock a busy semaphore but also when granting a lock to a free semaphore could lead to multiple blocking on higher-priority tasks.

In other words, as we already did before, we are trading off some useful properties for an additional form of blocking that did not exist before. This new kind of blocking that the priority ceiling protocol introduces in addition to direct and push-through blocking, is called ceiling blocking.

The underlying hypotheses of the original priority ceiling protocol are the same as those of the priority inheritance protocol. In addition, it is assumed that each semaphore has a static ceiling value associated with it. The ceiling of a semaphore can easily be calculated by looking at the application code and is defined as the maximum initial priority of all tasks that use it.

As in the priority inheritance protocol, each task has a current (or active) priority that is greater than or equal to its initial (or baseline) priority, depending on whether it is blocking some higher-priority tasks or not. The priority inheritance rule is exactly the same in both cases.

A task can immediately acquire a semaphore only if its active priority is higher than the ceiling of any currently locked semaphore, excluding any semaphore that the task has already acquired in the past and not released yet. Otherwise, it will be blocked. It should be noted that this last rule can block the access to busy as well as free semaphores.

The first property of the priority ceiling protocol to be discussed puts an upper bound on the priority a task may get when it is preempted within a critical region.

Proof. The easiest way to prove this lemma is by contradiction. If, contrary to our thesis, τ_L inherits a priority higher than or equal to the priority of τ_M, then it must block a task τ_H. The priority of τ_H must necessarily be higher than or equal to the priority of τ_M. If we call P_H and P_M the priorities of τ_H and τ_M, respectively, it must be P_H ≥ P_M.

On the other hand, since τ_M was allowed to enter Z_M without blocking, its priority must be strictly higher than the maximum ceiling of the semaphores currently locked by any task except τ_M itself. Even more so, if we call C* the maximum ceiling of the semaphores currently locked by tasks with a priority lower than the priority of τ_M, thus including τ_L, it must be P_M > C*.

The value of C* cannot undergo any further changes until τ_M completes because no tasks with a priority lower than its own will be able to run and acquire additional semaphores as long as τ_M is Ready or Running. The same is true also if τ_M is preempted by any higher-priority tasks. Moreover, those higher-priority tasks will never transmit their priority to a lower-priority one because, being P_M > C*, they do not share any semaphore with it. Last, if τ_M ever blocks on a semaphore, it will transmit its priority to the blocking task, which will then get a priority at least equal to the priority of τ_M.

By combining the two previous inequalities by transitivity, we obtain P_H > C*. From this, we can conclude that τ_H cannot be blocked by τ_L because the priority of τ_H is higher than the ceiling of all semaphores locked by τ_L. This is a contradiction and the lemma follows.

Then, we can prove that no transitive blocking can ever occur when the priority ceiling protocol is in use because

Proof. Again, by contradiction, let us suppose that a transitive blocking occurs. By definition, there exist three tasks τ_H, τ_M, and τ_L with decreasing priorities such that τ_L blocks τ_M and τ_M blocks τ_H.

Then, also by definition, τ_L must inherit the priority of τ_H by transitive priority inheritance. However, this contradicts Lemma 15.8. In fact, its hypotheses are fulfilled, and it states that τ_L cannot inherit a priority higher than or equal to the priority of τ_M until τ_M completes.

Another important property of the priority ceiling protocol concerns deadlock prevention and is summarized in the following theorem.

Proof. We assume that a task cannot deadlock “by itself,” that is, by trying to acquire again a mutual exclusion semaphore it already acquired in the past. In terms of program code, this would imply the execution of two consecutive P() on the same semaphore, with no V() in between.

Then, a deadlock can only be formed by a cycle of n ≥ 2tasks {τ₁, ..., τ_n} waiting for each other according to the circular wait condition discussed in Chapter 4. Each of these tasks must be within one of its critical regions; otherwise, deadlock cannot occur because the hold & wait condition is not satisfied.

By Lemma 15.9, it must be n = 2; otherwise, transitive blocking would occur, and hence, we consider only the cycle {τ₁,τ₂}. For a circular wait to occur, one of the tasks was preempted by the other while it was within a critical region because they are being executed by one single processor. Without loss of generality, we suppose that τ₂ was firstly preempted by τ₁ while it was within a critical region. Then, τ₁ entered its own critical region.

In that case, by Lemma 15.8, τ₂ cannot inherit a priority higher than or equal to the priority of τ₁. On the other hand, since τ₁ is blocked by τ₂, then τ₂ must inherit the priority of τ₁, but this is a contradiction and the theorem follows.

This theorem is also very useful from the practical standpoint. It means that, under the priority ceiling protocol, programmers can put into their code an arbitrary number of critical regions, possibly (properly) nested into each other. As long as each task does not deadlock with itself, there will be no deadlock at all in the system.

The next goal is, as before, to compute an upper bound on the worst-case blocking time that a task τ_i can possibly experience. First of all, it is necessary to ascertain how many times a task can be blocked by others.

Proof. Suppose that τ_H is blocked by two lower-priority tasks τ_L and τ_M, where P_L ≤ P_H and P_M ≤ P_H. Both τ_L and τ_M must be in a critical region.

Let τ_L enter its critical region first, and let $C_L^{*}$ be the highest-priority ceiling among all semaphores locked by τ_L at this point. In this scenario, since τ_M was allowed to enter its critical region, it must be $P_M>C_L^{*}$; otherwise, τ_M would be blocked.

Moreover, since we assumed that τ_H can be blocked by τ_L, it must necessarily be $P_H\le C_L^{*}$. However, this implies that P_M > P_H, leading to a contradiction.

The next step is to identify the critical regions of interest for blocking, that is, which critical regions can block a certain task.

Proof. If it were P_L ≥ P_H, then τ_H could not preempt τ_L, and hence, could not be blocked by S. Hence, it must be P_L < P_H for τ_H to be blocked by S.

Let us assume that $C_S^{*}<P_H$, that is, the second part of the hypothesis, is not satisfied, but τ_H is indeed blocked by S. Then, its priority must be less than or equal to the maximum ceiling C* among all semaphores acquired by tasks other than itself, that is, P_H ≤ C*. But it is $P_H>C_S^{*}$, and hence, $C_S^{*}<C$ and another semaphore, not S, must be the source of the blocking in this case.

It is then possible to conclude that τ_H can be blocked by τ_L, by means of semaphore S, only if P_L < P_H and $C_S^{*}\ge P_H$.

By combining the previous two results, the following theorem provides an upper bound on the worst-case blocking time.

Proof. The proof of this theorem descends from the straightforward application of

1. Theorem 15.4, which limits the blocking time to the duration of one critical region, the longest critical region among those that can block τ_i.

2. Lemma 15.10, which identifies which critical regions must be considered for the analysis. In particular, the definition of usage(k, i) is just a slightly different way to state the necessary conditions set forth by the lemma to determine whether a certain semaphore S_K can or cannot block τ_i.

The complete formula is then built with the same method already discussed in the proof of Theorem 15.2.

The only difference between the formulas given in Theorem 15.2 (for priority inheritance) and Theorem 15.5 (for priority ceiling), namely, the presence of a summation instead of a maximum can be easily understood by comparing Lemma 15.5 and Theorem 15.4.

Lemma 15.5 states that, for priority inheritance, a task τ_H can be blocked at most once for each semaphore that satisfies the blocking conditions of Lemma 15.7, and hence, the presence of the summation for priority inheritance. On the other hand, Theorem 15.4 states that, when using priority ceiling, τ_H can be blocked at most once, period, regardless of how many semaphores can potentially block it. In this case, to be conservative, we take the maximum among the worst-case execution times of all critical regions controlled by all semaphores that can potentially block τ_H.

An interesting variant of the priority ceiling protocol, called immediate priority ceiling or priority ceiling emulation protocol, takes a more straightforward approach. It raises the priority of a task to the priority ceiling associated with a resource as soon as the task acquires it, rather than only when the task is blocking a higher-priority task. Hence, it is defined as follows:

1. Each task has an initial, or baseline, priority assigned.

2. Each semaphore has a static ceiling defined, that is, the maximum priority of all tasks that may use it.

3. At each instant a task has a dynamic, active priority, that is, the maximum of its static, initial priority and the ceiling values of any semaphore it has acquired.

It can be proved that, as a consequence of the last rule, a task will only suffer a block at the very beginning of its execution. The worst-case behavior of the immediate priority ceiling protocol is the same as the original protocol, but

• The immediate priority ceiling is easier to implement, as blocking relationships must not be monitored. Also, for this reason, it has been specified in the POSIX standard [48], along with priority inheritance, for mutual exclusion semaphores.

• It leads to less context switches as blocking is prior to the first execution.

• On average, it requires more priority movements, as this happens with all semaphore operations rather than only if a task is actually blocking another.

A different method of addressing the unbounded priority inversion issue, known as adaptive priority ceiling, is used by RTAI, one of the Linux real-time extensions. It has a strong similarity with the algorithms just discussed but entails a different trade-off between the effectiveness of the method and how much complex its implementation is. More details about it can be found in Chapter 18.

15.4 Schedulability Analysis and Examples

In the previous section, an upper bound for the worst-case blocking time B_i that a task τ_i can suffer has been obtained. The bound depends on the way the priority inversion problem has been addressed. The worst-case response time R_i, already introduced in Chapter 14, can be redefined to take B_i into account as follows:

In this way, the worst-case response time R_i of task τ_i is expressed as the sum of three components:

1. the worst-case execution time C_i,

2. the worst-case interference I_i, and

3. the worst-case blocking time B_i.

The corresponding recurrence relationship introduced for Response Time Analysis (RTA) becomes

It can be proved that the new recurrence relationship still has the same properties as the original one. In particular, if it converges, it still provides the worst-case response time R_i for an appropriate choice of $w_i^0$. As before, either 0 or C_i are good starting points.

The main difference is that the new formulation is pessimistic, instead of necessary and sufficient, because the bound B_i on the worst-case blocking time is not tight, and hence, it may be impossible for a task to ever actually incur in a blocking time equal to B_i.

Let us now consider an example. We will consider a simple set of tasks and determine the effect of the priority inheritance and the immediate priority ceiling protocols on their worst-case response time, assuming that their periods are large (> 100 time units). In particular, the system includes

• A high-priority task τ_H, released at t = 4 time units, with a computation time of C_H = 3 time units. It spends the last 2 time units within a critical region guarded by a semaphore, S.

• An intermediate-priority task τ_M, released at t = 2 time units, with a computation time of 4 time units. It does not have any critical region.

• A low-priority task τ_L, released at t = 0 time units, with a computation time of 4 time units. It shares some data with τ_H, hence it spends its middle 2 time units within a critical region guarded by S.

The upper part of Figure 15.5 sketches the internal structure of the three tasks. Each task is represented as a rectangle with the left side aligned with its release time. The rectangle represents the execution of the task if it were alone in the system; the gray area inside the rectangle indicates the location of the critical region the task contains, if any.

The lower part of the figure shows how the system of tasks being considered is scheduled when nothing is done against unbounded priority inversion. When τ_H is blocked by its P(s) at t = 5 time units, task τ_M is resumed because it is the highest-priority task ready for execution. Hence, τ_L is resumed only after τ_M completes its execution, at t = 7 time units.

Thereafter, τ_L leaves its critical region at t = 8 and is immediately preempted by τ_H, which is now no longer blocked by τ_L and is ready to execute again. τ_H completes its execution at t = 10 time units. Last, τ_L is resumed and completes at t = 11 time units.

Overall, the task response times in this case are: R_H = 10 − 4 = 6, R_M = 7 − 2 = 5, R_L = 11 − 0 = 11 time units. Looking at Figure 15.5, it is easy to notice that R_H, the response time of τ_H, includes part of the execution time of τ_M ; even if τ_M ’s priority is lower, there is no interaction at all between τ_H and τ_M, and executing τ_M instead of τ_H is not of help to any other higher-priority tasks.

The behavior of the system with the priority inheritance protocol is shown in Figure 15.6. It is the same as before until t = 5 time units, when τ_H is blocked by the execution of P(s). In this case, τ_H is still blocked as before, but it also transmits its priority to τ_L. In other words τ_L, the blocking task, inherits the priority of τ_H, the blocked one.

Hence, τ_L is executed (instead of τ_M ) and leaves its critical region at t = 6 time units. At that moment, the priority inheritance ends and τ_L returns to its original priority. Due to this, it is immediately preempted by τ_H. At t = 8 time units, τ_H completes and τ_M is resumed. Finally, τ_M and τ_L complete their execution at t = 10 and t = 11 time units, respectively.

With the priority inheritance protocol, the task response times are R_H = 8 − 4 = 4, R_M = 10 − 2 = 8, R_L = 11 − 0 = 11 time units. From Figure 15.6, it can be seen that R_H no longer comprises any part of τ_M. It does include, instead, part of the critical region of τ_L, but this is unavoidable as long as τ_H and τ_L share some data with a mutual exclusion mechanism. In addition, the worst-case contribution it makes to R_H is bounded by the maximum time τ_L spends within its critical region.

It can also be noted that R_M, the response time of τ_M, now includes part of the critical region of τ_L, too. This is a very simple case of push-through blocking and is a side effect of the priority inheritance protocol. In any case, the contribution to R_M is still bounded by the maximum time τ_L spends within its critical region.

As shown in Figure 15.7, with the immediate priority ceiling protocol, τ_L acquires a priority equal to the priority of τ_H, the ceiling of s, as soon as it enters the critical region guarded by s itself at t = 1 time unit.

As a consequence, even if τ_M is released at t = 2, it does not preempt τ_L up to t = 3 when τ_L leaves the critical region and returns to its original priority. Another preemption, of τ_M in favor of τ_H, occurs at t = 4 time units, as soon as τ_H is released.

Then, τ_M is resumed, after the completion of τ_H, at t = 7 time units, and completes at t = 10 time units. Finally, τ_L completes at t = 11 time units. With the immediate priority ceiling protocol, the task response times are R_H = 7 − 4 = 3, R_M = 10 − 2 = 8, R_L = 11 − 0 = 11 time units.

Applying RTA to the example is particularly easy. The task periods are large with respect to their response time, and hence, each interfering task must be taken into account only once, and all the successions converge immediately. Moreover, since there is only one critical section, the worst-case blocking times are the same for both protocols.

The worst-case execution time among all critical regions guarded by s is 2 time units. Therefore,

• B_H = 2 because s can block τ_H;

• B_M = 2 because s can block τ_M ;

• B_L = 0 because s cannot block τ_L.

Substituting back into (15.2), we get

• For τ_H, hp(H) = ∅ and B_H = 2, and hence: R_H = C_H + B_H = 5 time units.

• For τ_M : hp(M ) = {H} and B_M = 2, and hence: R_M = C_M +B_M +C_H = 9 time units.

• For τ_L : hp(L) = {H, M } and B_L = 0, and hence: R_L = C_L+C_H +C_M = 11 time units.

Table 15.1 summarizes the actual response time of the various tasks involved in the example, depending on how the priority inversion problem has been addressed. For comparison, the rightmost column also shows the worst-case response times computed by the RTA method, extended as shown in (15.2). The worst-case response times are the same for both priority inheritance and immediate priority ceiling because their B_i are all the same.

Both the priority inheritance and the immediate priority ceiling protocols bound the maximum blocking time experienced by τ_H. It can be seen that its response time gets lower when any of these protocols are in use. On the other hand, the response time of τ_M increases as a side effect.

The response time of τ_L does not change but this can be expected because it is the lowest priority task. As a consequence, it can only suffer interference from the other tasks in the system but not blocking. For this reason, its response time cannot be affected by any protocol that introduces additional forms of blocking. It can also be seen that RTA provides a satisfactory worst-case response time in all cases except when the priority inversion problem has not been addressed at all.

15.5 Summary

In most concurrent applications of practical interest, tasks must interact with each other to pursue a common goal. In many cases, task interaction also implies blocking, that is, tasks must synchronize their actions and therefore wait for each other.

In this chapter we saw that careless task interactions may undermine priority assignments and, eventually, jeopardize the ability of the whole system to be scheduled because they may lead to an unbounded priority inversion. This happens even if the interactions are very simple, for instance, when tasks manipulate some shared data by means of critical regions.

One way of solving the problem is to set up a better cooperation between the scheduling algorithm and the synchronization mechanism, that is, to allow the synchronization mechanism to modify task priorities as needed. This is the underlying idea of the algorithms discussed in this chapter: priority inheritance and the two variants of priority ceiling.

It is then possible to show that all these algorithms are actually able to force the worst-case blocking time of any task in the system to be upper-bounded. Better yet, it is also possible to calculate the upper bound, starting from a limited amount of additional information about task characteristics, which is usually easy to collect.

Once the upper bound is known, the RTA method can also be extended to take consider it and calculate the worst-case response time of each task in the system, taking task interaction into account.