The advent of multicore technologies has fueled much recent work on methods for designing, deploying, and verifying multiprocessor implementations of real-time applications. Such methods must necessarily be rooted in resource allocation techniques that facilitate predictable system designs. In work on such techniques, scheduling algorithms, which allocate processor time (an admittedly important resource), have received the greatest attention. Synchronization algorithms, which coordinate access to other resources (as inevitably arise in practical settings), have received much less attention.
The current state-of-the-art regarding real-time multiprocessor synchronization is that simple locking protocols can be supported, but not much else. This is a serious impediment that is limiting the evolution of real-time applications to "multicore-ready" versions. This limited scope with respect to real-time synchronization is arguably the result of a schedulability-centric viewpoint: the main emphasis in prior work has been on how to modify existing schedulability analysis (which is used to check timing constraints) to account for synchronization effects rather than on the design of better synchronization algorithms.
The main thesis of this project is that, by adopting a more synchronization-centric viewpoint that places greater emphasis on the algorithmic properties that a good real-time synchronization protocol should satisfy, a wider range synchronization-related services can be supported with provably better predictability. This thesis is based on recent success within the PIs' research group in devising multiprocessor real-time locking protocols for which blocking bounds due to priority inversions are asymptotically optimal. These are the first such protocols to be proposed with aysmptotically optimal blocking behavior, despite over two decades of work on this topic. Their optimality stems from the usage of more sophisticated techniques in dealing with synchronization-related issues than have been considered before.
The main goal of this project is to expand upon this prior work so that a rich set of real-time synchronization mechanisms can be efficiently provided on multiprocessors. Specific research activities involve investigating a range of synchronization problems, as motivated by real application needs, within several real-time task models, also motivated by real needs. The latter include models for systems where various complexities exist, such as having multiple criticality levels for tasks, multiple subsystems that must be "isolated" through hierarchical scheduling, heterogeneous hardware components, dynamic task behaviors, stochastically-specified execution budgets, etc. In all of this work, the design of optimal synchronization protocols will be an emphasis. These protocols will be prototyped and evaluated within a open-source UNC-produced real-time Linux extension called LITMUSRT .
This project has been motivated by synchronization-related issues that have arisen in collaborative research involving the PIs and colleagues at AT&T and Northrop Grumman. This project will likely lead to further collaborative efforts with these colleagues that impact how researchers and developers at these companies envision supporting real-time workloads on multicore and multiprocessor platforms. More broadly, this project will significantly expand the range of real-time synchronization mechanisms that be efficiently supported on multiprocessors.