Qing Li - Real-Time Concepts for Embedded Systems

With the ceiling priority protocol, the task inherits the priority ceiling of the resource as soon as the task acquires the resource even when no other higher priority tasks contend for the same resource. This rule implies that all critical sections from every sharing task have the same criticality level. The idea is to finish the critical section as soon as possible to avoid possible conflicts.

Similarly to the ceiling priority protocol, the priority of every task is known in the priority ceiling protocol. 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.

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.

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.

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 VIII, Vol. 7, (Fall 1988): 20-31.

Holt, Richard C. 'Some Deadlock Properties of Computer Systems.' Computing Surveys 4, no. 3 (September 1972).

Howard, John H., Jr. 'Mixed Solutions for the Deadlock Problem.' Communications of ACM 16, no. 7 (July 1973)

Institute of Electrical and Electronics Engineers. 'Priority Inheritance Protocols: An approach to real-time synchronization.' IEEE Transactions on Computers 39, 1990.

Knotothanassis, Leonidas I., Robert W. Wisneiwski, and Michael L. Scott. 'Scheduler-Conscious Synchronization.' ACM Transactions on Computer Systems 15, no. 1 (February 1997): 3-40.

Kopetz, Herman. 1997. Real-Time Systems: Design Principles for Distributed Embedded Applications. Norwell, MA: Kluwer Academic Publishers.

Kopetz, H., and G. Gruensteidi. ' TTP-A Protocol for Fault-Tolerant Real-Time Systems.' IEEE Computer 24, no. 1 (1994): 14-23.

Kopetz, H., and T. Thurner. 'TTP-A New Approach to Solving the Interoperability Problem of Independently Developed ECUs.' SAE World Congress 1998 (Detroit, Michigan) , Warrendale, PA: SAE Press.

Klein, M.H., T. Ralya, B. Pollak, R. Obenza, and M.G. Harbour. 1993. A Practitioner's Handbook for Real-Time Analysis: Guide to Rate Monotonic Analysis for Real-Time Systems. Boston, MA: Kluwer Academic Publishers, ISBN 0-7923-9361-9.

Labrosse, Jean J. 2002. Embedded Systems Building Blocks, 2nd ed. Lawrence, KS: CMP Books.