2018/09/08 by Jian-Jia Chen, Georg von der Brüggen, Chen, Jian-Jia +5
Computer Science · #Distributed systems and fault tolerance #FOS: Computer and information sciences #Interconnection Networks and Systems #Operating Systems (cs.OS) #Real-Time Systems Scheduling #cs.OS
paper · pdf · doi:10.48550/arxiv.1809.02892
accepted and to appear in IEEE Real-Time System Symposium (RTSS) 2018
arxiv created 2018/09/08 · openalex publication_date 2018/09/08 · arxiv updated 2018/09/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Over the years, many multiprocessor locking protocols have been designed and analyzed. However, the performance of these protocols highly depends on how the tasks are partitioned and prioritized and how the resources are shared locally and globally. This paper answers a few fundamental questions when real-time tasks share resources in multiprocessor systems. We explore the fundamental difficulty of the multiprocessor synchronization problem and show that a very simplified version of this problem is \mathcal NP-hard in the strong sense regardless of the number of processors and the underlying scheduling paradigm. Therefore, the allowance of preemption or migration does not reduce the computational complexity. For the positive side, we develop a dependency-graph approach, that is specifically useful for frame-based real-time tasks, in which all tasks have the same period and release their jobs always at the same time. We present a series of algorithms with speedup factors between 2 and 3 under semi-partitioned scheduling. We further explore methodologies and tradeoffs of preemptive against non-preemptive scheduling algorithms and partitioned against semi-partitioned scheduling algorithms. The approach is extended to periodic tasks under certain conditions.