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. MSRP and MrsP are two major protocols that manage access to shared resources. Both of them can be applied to 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 work, we investigate three mainstream priority assignment algorithms -- DMPO, OPA, and RPA, in the context of partitioned multiprocessor systems with shared resources. We prove that DMPO is optimal with the traditional schedulability tests and that DMPO is not optimal with the tighter holistic schedulability tests. We analyse the pessimism arising from the adoption of OPA and RPA with the holistic tests, and propose SPO that minimises such pessimism with polynomial time complexity.