Resource-Oriented Partitioning for Multiprocessor Systems with Shared Resources

摘要

Predictable scheduling and resource sharing primitives are fundamental aspects of real-time systems. To prevent race conditions, access to shared resources must ensure mutual exclusion, e. g., using semaphores. Further, real-time locking protocols are required to avoid un-controlled priority inversions. For uniprocessor systems, the Priority Ceiling Protocol (PCP) has been widely accepted and supported in real-time operating systems. However, it remains arguable as to whether there exists a preferable approach for resource sharing in multiprocessor systems. In this paper, we show that the proposed Resource-Oriented Partitioned (ROP) scheduling with a distributed resource sharing policy, originating from the concept of the Distributed Priority Ceiling Protocol (DPCP), can achieve a non-trivial speedup factor guarantee. Specifically, we prove that the proposed R-PCP-rm-rm algorithm achieves a speedup factor of 11 - 6/(m + 1) on a platform consisting of m processors, where each job of a task may request at most one shared resource at most one time. Our empirical evaluations show that the proposed algorithm is highly effective in terms of task sets deemed schedulable.