Real-Time Concepts for Embedded Systems

The resources that every task requires are also known before execution. The current priority ceiling for a running system at any time is the highest priority ceiling of all resources in use at that time.

For example, if four resources are in use and if R1 has a priority ceiling of 4, R2 has a priority ceiling of 9, R3 of a priority ceiling 10, and R4 of a priority ceiling 8, the current priority ceiling of the system is 10. Note that different tasks can hold these resources.

This access control protocol follows the rules in Table 16.3 when a task T requests a resource R.

Table 16.3: Priority ceiling protocol rules.

Rule #	Description
1	If R is in use, T is blocked.
2	If R is free and if the priority of T is higher than the current priority ceiling, R is allocated to T.
3	If the current priority ceiling belongs to one of the resources that T currently holds, R is allocated to T, and otherwise T is blocked
4	The task that blocks T inherits T's priority if it is higher and executes at this priority until it releases every resource whose priority ceiling is higher than or equal to T's priority. The task then returns to its previous priority.

In the priority ceiling protocol, a requesting task can be blocked for one of three causes. The first cause is when the resource is current in use, which is direct resource contention blocking, and is the result of rule #1. The second cause is when the blocking task has inherited a higher priority and its current execution priority is higher than that of the requesting task. This cause is priority inheritance blocking and is the result of rule #4. A task can be blocked when its priority is lower than the current priority ceiling even when the requested resource is free. This cause is priority ceiling blocking and is a direct consequence of the 'otherwise' clause of rule #3. Rule #3 prevents a task from blocking itself if it holds a resource that has defined the current priority ceiling.

One of the deadlock prevention strategies in the 'Deadlock Prevention' on section 16.3.5, is to impose ordering on the resources. The resource ordering can be realized by using the priority ceilings of the resources. Rule #2 says if the priority of T is higher than the current priority ceiling, T does not require any resources that are in use. This issue occurs because otherwise the current priority ceiling would be either equal to or higher than the priority of T, which implies that tasks with a priority higher than T's do not require the resources currently in use. Consequently, none of the tasks that are holding resources in use can inherit a higher priority, preempt task T, and then request a resource that T holds. This feature prevents the circular-wait condition. This feature is also why deadlock cannot occur when using the priority ceiling protocol as an access control protocol. The same induction process shows that the condition in which a task blocks another task but is in turn blocked by a third task, transitive blocking, does not occur under the priority ceiling protocol.

The priority ceiling protocol has these characteristics:

· A requesting task can be blocked by only one task; therefore, the blocking interval is at most the duration of one critical section.

· Transitive blocking never occurs under the priority ceiling protocol.

· Deadlock never occurs under the priority ceiling protocol.

16.5 Points to Remember

Some points to remember include the following:

· Resources can be classified as either preemptible or non-preemptible resources.

· Deadlock occurs when all four of these conditions are true: mutual exclusion, no preemption, hold-and- wait, and circular wait.

· Resource requests can be classified into Single, AND, OR, and AND-OR request models.

· Strategies exist for dealing with deadlocks: deadlock detection and recovery, deadlock avoidance, and deadlock prevention.

· Access control protocols exist for dealing with priority inversion: priority inheritance protocol, ceiling priority protocol, and priority ceiling protocol.

· Deadlock never occurs under the priority ceiling protocol.

Appendix A: References

Almasi, George S., and Allan Gottlieb. 1994. Highly Parallel Computing. 2nd ed. Redwood City, CA: The Benjamin/Cummings Publishing Company, Inc.

Association of Computing Machinery. 'Source of Unbounded Priority Inversions in Real-Time Systems and a Comparative Study of Possible Solutions.' ACM Operating Systems Review 26, no. 2 (April 1992): 110-20.

Barr, Michael. 1999. Programming Embedded Systems in C and C++. Sebastopol, CA: O'Reilly&Associates, Inc.

Coffman, E.G., Jr., M.J. Elphick, and A. Shoshani. 'System Deadlocks.' Computing Surveys 3, no. 2 (June 1971).

Douglass, Bruce Powel. 1999. Doing Hard Time. Reading, MA: Addison- Wesley.

Fontao, Rafael O. 'A Concurrent Algorithm for Avoiding Deadlocks in Multiprocess Multiple Resource Systems.' Tech Report No. 70-5, Department of Computer Science, Cornell University, Ithaca, NY (January 1970).

Frailery, Dennis J. 'A Practical Approach to Managing Resources and Avoiding Deadlocks.' Communications of ACM 16, no. 5 (May 1973).

Gomaa, Hassan. 1996. Designing Concurrent, Distributed, and Real-Time Applications with UML. Boston, MA: Addison-Wesley.

Goodenough, John B. and Lui Sha. 'The Priority Ceiling Protocol: A method of minimizing the blocking of high priority Ada tasks.'

Ada Letters, Special Issues: Proc. 2 nd Int'l Workshop on Real-Time Ada Issues