Multiprocessor Priority Ceiling Based Protocols

Abstract

We study resource synchronization in multiprocessor hard real-time systems. Specifically, we propose a multiprocessor resource control protocol which allows a job to simultaneously lock multiple global resources, removing a restriction from previous protocols. Allowing nested critical sections may permit a finer granularity of synchronization, increasing parallelism and throughput. All the protocols discussed belong to the class of priority inheritance protocols and rely in some fashion on priority ceilings for global semaphores. We consider both static and dynamic priorities, building upon the multiprocessor priority ceiling protocol (MPCP) proposed by Rajkumar et al. and the dynamic priority ceiling protocol (DPCP) proposed by Chen and Lin.

The extended protocols prevent deadlock and transitive blocking. We derive bounds for worse case blocking time, and describe sufficient conditions to guarantee that m sets of periodic tasks can be scheduled on an rn multiprocessor system. Performance comparisons of these protocols with MPCP shows that the proposed protocols increase schedulability. (Also cross-referenced as UMIACS-TR-94-42)