Lune

DAC2021Top-tier venue

A Finer-Grained Blocking Analysis for Parallel Real-Time Tasks with Spin-Locks

Ze-Wei Chen, Hang Lei, Maolin Yang, Yong Liao, Lei Qiao

Abstract

Real-time synchronization is one of the essential theories in real-time systems, and the recent booming of parallel real-time tasks has brought new challenges to the synchronization analysis. As the easy implementation and negligible overheads, spin-locks have received much interest since the study for sequential tasks. However, existing spin-based blocking analyses for parallel tasks are relied on execution-time inflation, and the substantially more accurate inflation-free analysis has not been fathomed yet. Moreover, existing analyses suffer an overrepresentation problem, which can be further exacerbated for parallel tasks with spin-locks. To overcome such pessimism, we propose an improved blocking analysis for non-preemptive spin-locks based on a finer-grained shared resource model. In particular, we consider individual length for each shared resource request and use the state-of-the-art linear optimization technique to achieve a pinpoint inflation-free analysis. Empirical evaluations show that the proposed analysis dominated other state-of-the-art analysis, which further shows the improved accuracy achieved by the proposed approach.

Ask Lune

Know where this paper stands in minutes, not an afternoon.

Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

its abstract · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Response Time Analysis for Prioritized DAG Task with Mutually Exclusive VerticesRan Bi, Qingqiang He, Jinghao Sun, Zhenyu Sun et al.RTSS 2022 · 10 citations

Related papers

  1. Response-Time Analysis for Non-Preemptive Global Scheduling with FIFO Spin LocksSuhail Nogd, Geoffrey Nelissen, Mitra Nasri, Björn B. BrandenburgRTSS 2020 · 14 citations
  2. FRAP: A Flexible Resource Accessing Protocol for Multiprocessor Real-Time SystemsShuai Zhao, Hanzhi Xu, Nan Chen, Ruoxian Su et al.RTSS 2024 · 3 citations
  3. Scheduling and analysis of real-time tasks with parallel critical sectionsYang Wang, Xu Jiang, Nan Guan, Mingsong Lv et al.DAC 2022 · 3 citations
  4. A Universal Method for Task Allocation on FP-FPS Multiprocessor Systems with Spin LocksShuai Zhao, Nan Chen, Yinjie Fang, Zhao Li et al.DAC 2023 · 8 citations
  5. LEFT-RS: A Lock-Free Fault-Tolerant Resource Sharing Protocol for Multicore Real-Time SystemsNan Chen, Xiaotian Dai, Tong Cheng, Alan Burns et al.RTSS 2025 · 1 citation
Dusk over the sea between two cliffs drawn in fine vertical lines