Advanced Course on Multiprocessor Real-Time Locking by Björn B. Brandenburg

December 10-12, 2013 – Retis Lab

One of the fundamental problems in real-time systems is how to guarantee predictable, mutually exclusive access to shared resources such that the worst-case blocking incurred by any task remains bounded. On uniprocessors, it has long been known how to solve this problem optimally using Baker's classic Stack Resource Policy (SRP) and Sha et al.'s Priority Ceiling Protocol (PCP). On multiprocessors, however, the problem is considerably more challenging and not yet as well understood. Fortunately, there has been considerable progress in the last couple of years. In this course, I will provide an overview of the key results pertaining to real-time locking on multiprocessors, covering material ranging from classic protocols such as the DPCP and MPCP up to the latest results on asymptotically optimal multiprocessor real-time locking protocols and advanced analysis techniques.
In the first part of the course, we will study various types of simple spin locks (FIFO, priority-ordered, unordered, with preemptable and non-preemptable spinning) using both simple, classic analysis techniques and more recent, less pessimistic techniques. Thereafter, we will study the (more complicated) case of suspension-based, shared-memory semaphore protocols, in which waiting tasks yield their processor to other tasks, which complicates the analysis of such protocols considerably. In the third part of the course, we will study so-called distributed real-time locking protocols, which are semaphore protocols applicable to platforms without shared memory. Finally, the course will conclude with a performance comparison of the studied locking approaches, an answer to the question of how to deal gracefully with nested critical sections, and various related topics, including locking in reservation-based schedulers and non-blocking synchronization approaches.

Brief Bio:
Björn Brandenburg is a tenure-track faculty member at the Max Planck Institute for Software Systems and head of the Real-Time Systems Group. Prior to joining MPI-SWS, he was a graduate student at the University of North Carolina at Chapel Hill (2006-2011). His dissertation was awarded the 2012 UNC Dean's Distinguished Dissertation Award and honored at the national level with the 2012 CGS/ProQuest Distinguished Dissertation Award. His main research interests are real-time systems, operating systems, synchronization protocols, embedded systems, and the design and implementation of systems that are robust, efficient, and amenable to a priori analysis.

PDF icon Flier of Brandenburg Course144.61 KB