A Unified Blocking Analysis for Parallel Tasks With Spin Locks Under Global Fixed Priority Scheduling

Spin locks are widely used in embedded systems to coordinate mutually exclusive accesses to shared resources from different tasks. Although the design and analysis of locking protocols have been intensively studied for sequential real-time tasks, there have been few works on this topic for parallel real-time tasks. In this paper, we study the analysis of parallel real-time tasks modeled by directed acyclic graphs (DAGs) under global fixed priority scheduling using both preemptable and non-preemptable spin locks to protect accesses to shared resources in three commonly used request serving orders (unordered, FIFO-order and priority-order). In particular, we develop a general schedulability analysis framework where the blocking time caused by resource contention is formally defined, so that the blocking analysis can be performed independently and easy to combine with the traditional interference analysis techniques. Moreover, we present a unified blocking analysis technique where the blocking time is analyzed in a scalable manner based on a linear-programming (LP) approach, making our method flexible and extendable. We conduct comprehensive experiments to evaluate our method with other the-state-of-the-art approaches for scheduling real-time parallel tasks using semaphores and spin locks.

Automated summary

This paper studies the analysis of parallel real-time tasks using spin locks to protect shared resources and proposes a scalable blocking analysis technique based on linear programming. The method is evaluated through comprehensive experiments and compared with other state-of-the-art approaches for scheduling real-time parallel tasks using semaphores and spin locks.