skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Real-Time Multiprocessor Locks with Nesting: Optimizing the Common Case
In prior work on multiprocessor real-time locking protocols, only protocols within the RNLP family support unrestricted lock nesting while guaranteeing asymptotically optimal priority-inversion blocking bounds. However, these protocols support nesting at the expense of increasing the cost of processing non-nested lock requests, which tend to be the common case in practice. To remedy this situation, a newfast-path mechanism is presented herein that extends prior RNLP variants by ensuring that non-nested requests are processed efficiently. This mechanism yields overhead and blocking costs for such requests that are nearly identical to those seen in the most efficient single-resource locking protocols. In experiments, the proposed fast-path mechanism enabled observed blocking times for non-nested requests that were up to 17 times lower than under an existing RNLP variant.  more » « less
Award ID(s):
1717589
PAR ID:
10108199
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Real-Time Systems, special issue of outstanding papers from the 25th International Conference on Real-Time Networks and Systems (RTNS 2017)
Volume:
55
Issue:
2
Page Range / eLocation ID:
296-348
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; (, Proceedings of the 27th International Conference on Real-Time Networks and Systems)
    When designing a real-time multiprocessor locking protocol, the allowance of lock nesting creates complications that can kill parallelism. Such protocols are typically designed by focusing on the arbitration of resource requests that should be prohibited from executing concurrently. This paper proposes "concurrency groups," a new concept that reflects an alternative point of view that focuses instead on requests that can be allowed to execute concurrently. A concurrency group is simply a group of lock requests, determined offline, that can safely execute together. This paper's main contribution is the CGLP, a new real-time multiprocessor locking protocol that supports lock nesting through the use of concurrency groups. The CGLP is able to reap runtime parallelism benefits that have eluded prior protocols by investing effort offline in the construction of concurrency groups. A schedulability study is presented to quantify these benefits, as well as an efficient approach to determining such groups using an Integer Linear Program (ILP) solver. 
    more » « less
  2. ; ; ; (, Proceedings of the 27th International Conference on Real-Time Networks and Systems)
    When designing a real-time multiprocessor locking protocol, the allowance of lock nesting creates complications that can kill parallelism. Such protocols are typically designed by focusing on the arbitration of resource requests that should be prohibited from executing concurrently. This paper proposes “concurrency groups,” a new concept that reflects an alternative point of view that focuses instead on requests that can be allowed to execute concurrently. A concurrency group is simply a group of lock requests, determined offline, that can safely execute together. This paper’s main contribution is the CGLP, a new real-time multiprocessor locking protocol that supports lock nesting through the use of concurrency groups. The CGLP is able to reap runtime parallelism benefits that have eluded prior protocols by investing effort offline in the construction of concurrency groups. A schedulability study is presented to quantify these benefits, as well as an efficient approach to determining such groups using an Integer Linear Program (ILP) solver. 
    more » « less
  3. ; (, Proceedings of the 35th Euromicro Conference on Real-Time Systems)
    Papadopoulos, Alessandro V. (Ed.)
    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. 
    more » « less
  4. ; (, Proceedings of the 35th Euromicro Conference on Real-Time Systems)
    Real-time locking protocols are typically designed to reduce any priority-inversion blocking (pi9 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 fxed-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 frst such protocols. Specifcally, protocols are presented for mutual exclusion, reader-writer synchronization, and k-exclusion that are optimal under frst-in-frst-out (FIFO) scheduling when schedulability analysis treats suspension times as computation. Experiments are presented that demonstrate the efectiveness of these protocols. 
    more » « less
  5. ; ; ; (, Financial Cryptography and Data Security)
    Bitcoin, Ethereum and other blockchain-based cryptocurrencies, as deployed today, cannot support more than several transactions per second. Off-chain payment channels, a “layer 2” solution, are a leading approach for cryptocurrency scaling. They enable two mutually distrustful parties to rapidly send payments between each other and can be linked together to form a payment network, such that payments between any two parties can be routed through the network along a path that connects them. We propose a novel payment channel protocol, called Sprites. The main advantage of Sprites compared with earlier protocols is a reduced “collateral cost,” meaning the amount of money × time that must be locked up before disputes are settled. In the Lightning Network and Raiden, a payment across a path of ` channels requires locking up collateral for Θ(`∆) time, where ∆ is the time to commit an on-chain transaction; every additional node on the path forces an increase in lock time. The Sprites construction provides a constant lock time, reducing the overall collateral cost to Θ(` + ∆). Our presentation of the Sprites protocol is also modular, making use of a generic state channel abstraction. Finally, Sprites improves on prior payment channel constructions by supporting partial withdrawals and deposits without any on-chain transactions. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email