Synchronization Processors in the Distributed Multiprocessor Real-time Locking Protocols
BjÃ¶rn B. Brandenburg
Journal of Information Security Research, Vol. 15, No. 2, 2024.
DOI: https://doi.org/10.6025/jisr/2024/15/2/35-58
Link: https://www.dline.info/jisr/fulltext/v15n2/jisrv15n2_1.pdf
Abstract:
Our research delves into the fascinating world of distributed multiprocessor real-time locking protocols, where resources can only be accessed through certain synchronization processors. We establish the minimum and maximum priority inversion blocking limits that are typically unavoidable in these protocols, building on the foundation laid by previous research on suspension-based shared-memory multiprocessor locking protocols. The W (m) and W (n) maximum pi-blocking under suspension-oblivious and suspension-aware analysis, respectively, where m denotes the total number of processors and n denotes the number of tasks. This paper shows that, in the case of distributed semaphore protocols, two task allocation scenarios exist that give rise to distinct lower bounds. In the case of co-hosted task allocation, where application tasks may also be assigned to synchronisation processors (i.e., processors hosting critical sections), W (F Â· n maximum pi-blocking is unavoidable for some tasks under any locking protocol under both suspension-aware and suspension-oblivious schedulability analysis, where F denotes the ratio of the maximum response time to the shortest period. In contrast, in the case of disjoint task allocation (i.e., if application tasks may not be assigned to synchronization processors), only W (m) and W(n) maximum pi-blocking is fundamentally unavoidable under suspension-oblivious and suspension-aware analysis, respectively, as in the shared-memory case. These bounds are shown to be asymptotically tight with the construction of two new distributed real-time locking protocols that ensure O(m) and O(n) maximum pi-blocking under suspension-oblivious.