2026-07-25T12:37:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18045 2024-03-06T11:01:19Z ddc:004 open_access

Optimal Multiprocessor Locking Protocols Under FIFO Scheduling Ahmed, Shareef Anderson, James H. Real-Time Systems Real-Time Synchronization Multiprocessors Real-time locking protocols are typically designed to reduce any priority-inversion blocking (pi-blocking) a task may incur while waiting to access a shared resource. For the multiprocessor case, a number of such protocols have been developed that ensure asymptotically optimal pi-blocking bounds under job-level fixed-priority scheduling. Unfortunately, no optimal multiprocessor real-time locking protocols are known that ensure tight pi-blocking bounds under any scheduler. This paper presents the first such protocols. Specifically, protocols are presented for mutual exclusion, reader-writer synchronization, and k-exclusion that are optimal under first-in-first-out (FIFO) scheduling when schedulability analysis treats suspension times as computation. Experiments are presented that demonstrate the effectiveness of these protocols. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shareef Ahmed and James H. Anderson 2023 Is Part Of LIPIcs, Volume 262, 35th Euromicro Conference on Real-Time Systems (ECRTS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ECRTS.2023.16 urn:nbn:de:0030-drops-180451 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2023.16 eng https://creativecommons.org/licenses/by/4.0/legalcode