Please use this identifier to cite or link to this item:
Title: Priority assignment on partitioned multiprocessor systems with shared resources
Authors: Zhao, Shuai
Chang, Wanli
Wei, Ran
Liu, Weichen
Guan, Nan
Burns, Alan
Wellings, Andy
Keywords: Engineering::Computer science and engineering
Issue Date: 2020
Source: Zhao, S., Chang, W., Wei, R., Liu, W., Guan, N., Burns, A. & Wellings, A. (2020). Priority assignment on partitioned multiprocessor systems with shared resources. IEEE Transactions On Computers, 70(7), 1006-1018.
Journal: IEEE Transactions on Computers
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.
ISSN: 0018-9340
DOI: 10.1109/TC.2020.3000051
Schools: School of Computer Science and Engineering 
Rights: © 2020 IEEE. All rights reserved.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SCSE Journal Articles

Citations 50

Updated on Jun 16, 2024

Web of ScienceTM
Citations 50

Updated on Oct 31, 2023

Page view(s)

Updated on Jun 19, 2024

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.