Priority Assignment on Partitioned Multiprocessor Systems with Shared Resources

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

2 Scopus Citations
View graph of relations

Author(s)

  • Shuai Zhao
  • Wanli Chang
  • Ran Wei
  • Weichen Liu
  • Alan Burns
  • Andy Wellings

Detail(s)

Original languageEnglish
Article number9109645
Pages (from-to)1006-1018
Journal / PublicationIEEE Transactions on Computers
Volume70
Issue number7
Online published5 Jun 2020
Publication statusPublished - Jul 2021
Externally publishedYes

Abstract

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.

Research Area(s)

  • Priority assignment, real-time multiprocessor systems, resource sharing

Citation Format(s)

Priority Assignment on Partitioned Multiprocessor Systems with Shared Resources. / Zhao, Shuai; Chang, Wanli; Wei, Ran; Liu, Weichen; Guan, Nan; Burns, Alan; Wellings, Andy.

In: IEEE Transactions on Computers, Vol. 70, No. 7, 9109645, 07.2021, p. 1006-1018.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review