Worst-case response time analysis for periodic programs with nested locks

Abstract

Periodic applications include tasks that run continuously over certain intervals, which can lead to data races with concurrency. Locks have been traditionally used as a synchronization mechanism to ensure correctness. However, it is possible that a low priority task gets preempted for a high priority task while holding a lock that the high priority task requires. In safety-critical systems, this can result in undesirable situations where high priority tasks have to wait for low priority tasks to complete, violating its periodicity and priority. While prior works have proposed techniques for race detection in applications without nested locking, these techniques do not generalize to applications using nested locks. In this work, we present a worst-case response time analysis and a sound technique for static race detection in the context of periodic applications having nested locking behavior. Our algorithm offers a conservative upper bound for task response times when dealing with periodicity and addressing the complexities introduced by nested locks. Our approach improves the safety and dependability of concurrent periodic programs with nested locks. We implement our algorithm in Rust, and evaluate its performance and correctness on a set of programs.