Priority Assignment on Partitioned Multiprocessor Systems With Shared Resources

Driven by industry demand, there is an increasing need to develop real-time multiprocessor systems which contain shared resources. The Multiprocessor Stack Resource Policy (MSRP) and Multiprocessor resource sharing Protocol (MrsP) are two major protocols that manage access to shared resources. Both of them can be applied to Fixed-Priority Preemptive Scheduling (FPPS), which is enforced by most commercial real-time systems regulations, and which requires task priorities to be assigned before deployment. Along with MSRP and MrsP, there exist two forms of schedulability tests that bound the worst-case blocking time due to resource accesses: the traditional ones being more widely adopted and the more recently developed holistic ones which deliver tighter analysis. On uniprocessor systems, there are several well-established optimal priority assignment algorithms. Unfortunately, on multiprocessor systems with shared resources, the issue of priority assignment has not been adequately understood. In this article, we investigate three mainstream priority assignment algorithms-Deadline Monotonic Priority Ordering (DMPO), Audsley's Optimal Priority Assignment (OPA), and Robust Priority Assignment (RPA), in the context of partitioned multiprocessor systems with shared resources. Our contributions are multifold: First, we prove that DMPO is optimal with the traditional schedulability tests. Second, two counter examples are given as evidence that DMPO is not optimal with the tighter holistic schedulability tests. Third, we then analyze the pessimism arising from the adoption of OPA and RPA with the holistic tests. Lastly, we propose a Slack-based Priority Ordering (SPO) algorithm that minimises such pessimism, and has polynomial time complexity. Comprehensive experiments show that SPO outperforms (i.e., results in a larger number of schedulable systems) DMPO, OPA, and RPA in general with the holistic schedulability tests, by up to 15 percent. With the theoretical contributions, this paper is a useful guide to priority assignment in real-time partitioned multiprocessor systems with shared resources.