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 inversio...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 2019-06, Vol.68 (6), p.882-898
Main Authors: Yang, Maolin, Huang, Wen-Hung, Chen, Jian-Jia
Format: Article
Language:English
Subjects:
Algorithms
fixed-priority scheduling
Inversions
Locking
locking protocols
Multiprocessing
Multiprocessor real-time systems
Operating systems
partitioned scheduling
Processor scheduling
Program processors
Protocols
Real time
Real-time systems
Resource management
Resource scheduling
Scheduling
shared resources
speedup factor
Task analysis
worst-case response time
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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)11-6/(m+1) on a platform consisting of mm 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.
ISSN:0018-9340
1557-9956
DOI:10.1109/TC.2018.2889985