Blocking Optimality in Distributed Real-Time Locking Protocols
Lower and upper bounds on the maximum priority inversion blocking (pi-blocking) that is generally unavoidable in distributed multiprocessor real-time locking protocols (where resources may be accessed only from specific synchronization processors) are established. Prior work on suspension-based shar...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
2014-09-01
|
| Series: | Leibniz Transactions on Embedded Systems |
| Subjects: | |
| Online Access: | https://drops.dagstuhl.de/storage/07lites/lites_vol001/lites_vol001_issue002/LITES-v001-i002-a001/LITES-v001-i002-a001.pdf |
| _version_ | 1827283555917496320 |
|---|---|
| author | Brandenburg, Björn Bernhard |
| author_facet | Brandenburg, Björn Bernhard |
| author_sort | Brandenburg, Björn Bernhard |
| collection | DOAJ |
| description | Lower and upper bounds on the maximum priority inversion blocking (pi-blocking) that is generally unavoidable in distributed multiprocessor real-time locking protocols (where resources may be accessed only from specific synchronization processors) are established. Prior work on suspension-based shared-memory multiprocessor locking protocols (which require resources to be accessible from all processors) has established asymptotically tight bounds of Ω(m) and Ω(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. In this paper, it is shown that, in the case of distributed semaphore protocols, there exist two different task allocation scenarios that give rise to distinct lower bounds. In the case of co-hosted task allocation, where application tasks may also be assigned to synchronization processors (i.e., processors hosting critical sections), Ω(Φ · n) maximum pi-blocking is unavoidable for some tasks under any locking protocol under both suspension-aware and suspension-oblivious schedulability analysis, where Φ 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 Ω(m) and Ω(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 and suspension-aware analysis, respectively. |
| first_indexed | 2024-04-24T09:37:30Z |
| format | Article |
| id | doaj.art-5fc2c6fea5da4a4c9d1d42ca2b071a74 |
| institution | Directory Open Access Journal |
| issn | 2199-2002 |
| language | English |
| last_indexed | 2024-04-24T09:37:30Z |
| publishDate | 2014-09-01 |
| publisher | Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik |
| record_format | Article |
| series | Leibniz Transactions on Embedded Systems |
| spelling | doaj.art-5fc2c6fea5da4a4c9d1d42ca2b071a742024-04-15T07:55:31ZengSchloss Dagstuhl -- Leibniz-Zentrum fuer InformatikLeibniz Transactions on Embedded Systems2199-20022014-09-011201:101:2210.4230/LITES-v001-i002-a0017Blocking Optimality in Distributed Real-Time Locking ProtocolsBrandenburg, Björn Bernhard0Max Planck Institute for Software Systems (MPI-SWS)Lower and upper bounds on the maximum priority inversion blocking (pi-blocking) that is generally unavoidable in distributed multiprocessor real-time locking protocols (where resources may be accessed only from specific synchronization processors) are established. Prior work on suspension-based shared-memory multiprocessor locking protocols (which require resources to be accessible from all processors) has established asymptotically tight bounds of Ω(m) and Ω(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. In this paper, it is shown that, in the case of distributed semaphore protocols, there exist two different task allocation scenarios that give rise to distinct lower bounds. In the case of co-hosted task allocation, where application tasks may also be assigned to synchronization processors (i.e., processors hosting critical sections), Ω(Φ · n) maximum pi-blocking is unavoidable for some tasks under any locking protocol under both suspension-aware and suspension-oblivious schedulability analysis, where Φ 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 Ω(m) and Ω(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 and suspension-aware analysis, respectively.https://drops.dagstuhl.de/storage/07lites/lites_vol001/lites_vol001_issue002/LITES-v001-i002-a001/LITES-v001-i002-a001.pdfdistributed multiprocessor real-time systemsreal-time lockingpriority inversionblocking optimality |
| spellingShingle | Brandenburg, Björn Bernhard Blocking Optimality in Distributed Real-Time Locking Protocols Leibniz Transactions on Embedded Systems distributed multiprocessor real-time systems real-time locking priority inversion blocking optimality |
| title | Blocking Optimality in Distributed Real-Time Locking Protocols |
| title_full | Blocking Optimality in Distributed Real-Time Locking Protocols |
| title_fullStr | Blocking Optimality in Distributed Real-Time Locking Protocols |
| title_full_unstemmed | Blocking Optimality in Distributed Real-Time Locking Protocols |
| title_short | Blocking Optimality in Distributed Real-Time Locking Protocols |
| title_sort | blocking optimality in distributed real time locking protocols |
| topic | distributed multiprocessor real-time systems real-time locking priority inversion blocking optimality |
| url | https://drops.dagstuhl.de/storage/07lites/lites_vol001/lites_vol001_issue002/LITES-v001-i002-a001/LITES-v001-i002-a001.pdf |
| work_keys_str_mv | AT brandenburgbjornbernhard blockingoptimalityindistributedrealtimelockingprotocols |