Design and Blocking Analysis of Locking Protocols for Real-Time DAG Tasks under Federated Scheduling

Real-time systems require locking protocols to coordinate access to shared resources. With the booming revolution of parallel processing technology in real-time systems, there has been some work addressing the problem of extending classic locking protocols for sequential real-time tasks to parallel tasks. However, it may not be most effective to trivially follow the progress mechanisms and queue orders designed for sequential tasks since the intrastructure information within a parallel task is not taken into consideration. This article investigates the design of locking protocols for parallel tasks using a novel mechanism - longest normal Section first (LNSF) - to consider the impact of normal sections on blocking behavior in parallel tasks and further improve real-time performance. LNSF is then implemented in a locking protocol for parallel tasks named POMIP, and associated blocking analysis techniques are presented. Empirical evaluations show that our proposed analysis dominated other state-of-the-art analysis - in best cases, the acceptance ratio of the task set can be improved by around 17%.