On the Complexity of Worst-Case Blocking Analysis of Nested Critical Sections

Abstract—Accurately bounding the worst-case blocking in finite job sets, a special case of the classic sporadic task model of recurrent real-time systems, using either nested FIFO- or priority-ordered locks on multiprocessors is NP-hard. These intractability results are obtained with reductions from the Multiple-Choice Matching problem. The reductions are quite general and do not depend on (1) whether the locks are spin- or suspension-based, or (2) whether global or partitioned scheduling is used, or (3) which scheduling policy is employed (as long as it work-conserving). Further, we show that the blocking analysis problem for un-ordered spin locks with nested non-preemptable critical sections can be answered in polynomial time by solving a reachability prob-lem on a suitably constructed graph, although (or rather, because) unordered locks do not offer any acquisition-order guarantees. Finally, we identify several challenging open problems, pertain-ing both to circumventing the hardness results and to classifying the inherent hardness more precisely. I