Title: Dependency Graph Approach for Multiprocessor Real-Time Synchronization,
Abstract: Over the years, many multiprocessor locking protocols have been designed and
analyzed. However, the performance of these protocols highly depends on how the
tasks are partitioned and prioritized and how the resources are shared locally
and globally. This paper answers a few fundamental questions when real-time
tasks share resources in multiprocessor systems. We explore the fundamental
difficulty of the multiprocessor synchronization problem and show that a very
simplified version of this problem is ${\mathcal NP}$-hard in the strong sense
regardless of the number of processors and the underlying scheduling paradigm.
Therefore, the allowance of preemption or migration does not reduce the
computational complexity. For the positive side, we develop a dependency-graph
approach, that is specifically useful for frame-based real-time tasks, in which
all tasks have the same period and release their jobs always at the same time.
We present a series of algorithms with speedup factors between $2$ and $3$
under semi-partitioned scheduling. We further explore methodologies and
tradeoffs of preemptive against non-preemptive scheduling algorithms and
partitioned against semi-partitioned scheduling algorithms. The approach is
extended to periodic tasks under certain conditions.