Peter A. Buhr
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Peter A. Buhr has a total of 11 co-authors. Here are the top co-authors by number of shared publications:
- Wim Hendrik Hesselink
Computer Science, University of Groningen, Groningen, Netherlands
6 shared publications David Dice
Oracle Labs Burlington MA USA
4 shared publicationsThierry Delisle
Cheriton School of Computer Science University of Waterloo Waterloo Ontario Canada
2 shared publications- Aaron Moss
University of Portland
1 shared publication Ashif S. Harji
University of Waterloo, 200 University Avenue West, Waterloo, Ontario, Canada N2L 3G1
1 shared publicationC. R. Zarnke
Hayes Microcomputer Products, 295 Phillip Street, Waterloo, Ontario, N2L 3W8
1 shared publication
Latest Publications
- Open Access
- 8 November 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 11 (4) , 1-20
First-Come-First-Served as a Separate Principle
A lock is a mechanism to guarantee mutual exclusion with eventual progress, i.e., some degree of fairness. First-come-first-served (FCFS) progress is perfectly fair. FCFS progress can be offered by a locking algorithm or added by wrapping a non-FCFS lock with a separate FCFS algorithm. A new separate FCFS algorithm is presented that creates FCFS progress by wrapping a lock’s entry protocol (acquire). The algorithm addresses an important safety issue in locking, called barging, where arriving threads proceed before waiting threads or waiting threads are serviced with some bias. Barging increases latency for waiting threads and is non-intuitive to concurrent programmers, even though it is inherent to non-deterministic concurrent execution. A correctness proof is presented for the new FCFS algorithm and verified with the proof assistant PVS. Experimental tests are performed to ensure the presented wrapper provides FCFS progress when used to transform non-FCFS software and hardware locks. The performance of the non-FCFS and transformed FCFS counterparts is compared and contrasted with locks using inherent FCFS progress. The results show the FCFS transforms are performant for most algorithms, providing an additional tool for application developers to achieve correctness without a significant global performance reduction.
- 8 November 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 11 (4) , 1-20
Open AccessFirst-Come-First-Served as a Separate Principle
A lock is a mechanism to guarantee mutual exclusion with eventual progress, i.e., some degree of fairness. First-come-first-served (FCFS) progress is perfectly fair. FCFS progress can be offered by a locking algorithm or added by wrapping a non-FCFS lock with a separate FCFS algorithm. A new separate FCFS algorithm is presented that creates FCFS progress by wrapping a lock’s entry protocol (acquire). The algorithm addresses an important safety issue in locking, called barging, where arriving threads proceed before waiting threads or waiting threads are serviced with some bias. Barging increases latency for waiting threads and is non-intuitive to concurrent programmers, even though it is inherent to non-deterministic concurrent execution. A correctness proof is presented for the new FCFS algorithm and verified with the proof assistant PVS. Experimental tests are performed to ensure the presented wrapper provides FCFS progress when used to transform non-FCFS software and hardware locks. The performance of the non-FCFS and transformed FCFS counterparts is compared and contrasted with locks using inherent FCFS progress. The results show the FCFS transforms are performant for most algorithms, providing an additional tool for application developers to achieve correctness without a significant global performance reduction.
- Open Access
- 16 September 2023
- Published by Wiley in Software: Practice and Experience
- Vol. 53 (12) , 2463-2500
High‐performance extended actors
- 16 September 2023
- Published by Wiley in Software: Practice and Experience
- Vol. 53 (12) , 2463-2500
Open AccessHigh‐performance extended actors
- Open Access
- 20 June 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 10 (2) , 1-23
MCSH, a Lock with the Standard Interface
The MCS lock of Mellor-Crummey and Scott (1991), 23 pages. is a very efficient first-come first-served mutual-exclusion algorithm that uses the atomic hardware primitives fetch-and-store and compare-and-swap. However, it has the disadvantage that the calling thread must provide a pointer to an allocated record. This additional parameter violates the standard locking interface, which has only the lock as a parameter. Hence, it is impossible to switch to MCS without editing and recompiling an application that uses locks. This article provides a variation of MCS with the standard interface, which remains FCFS, called MCSH. One key ingredient is to stack allocate the necessary record in the acquire procedure of the lock, so its life-time only spans the delay to enter a critical section. A second key ingredient is communicating the allocated record between the acquire and release procedures through the lock to maintain the standard locking interface. Both of these practices are known to practitioners, but our solution combines them in a unique way. Furthermore, when these practices are used in prior papers, their correctness is often argued informally. The correctness of MCSH is verified rigorously with the proof assistant PVS, and experiments are run to compare its performance with MCS and similar locks.
- 20 June 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 10 (2) , 1-23
Open AccessMCSH, a Lock with the Standard Interface
The MCS lock of Mellor-Crummey and Scott (1991), 23 pages. is a very efficient first-come first-served mutual-exclusion algorithm that uses the atomic hardware primitives fetch-and-store and compare-and-swap. However, it has the disadvantage that the calling thread must provide a pointer to an allocated record. This additional parameter violates the standard locking interface, which has only the lock as a parameter. Hence, it is impossible to switch to MCS without editing and recompiling an application that uses locks. This article provides a variation of MCS with the standard interface, which remains FCFS, called MCSH. One key ingredient is to stack allocate the necessary record in the acquire procedure of the lock, so its life-time only spans the delay to enter a critical section. A second key ingredient is communicating the allocated record between the acquire and release procedures through the lock to maintain the standard locking interface. Both of these practices are known to practitioners, but our solution combines them in a unique way. Furthermore, when these practices are used in prior papers, their correctness is often argued informally. The correctness of MCSH is verified rigorously with the proof assistant PVS, and experiments are run to compare its performance with MCS and similar locks.
- 1 May 2021
- Published by Wiley in Software: Practice and Experience
- Vol. 51 (5) , 1005-1042
Advanced control-flow and concurrency in C∀
- 1 May 2021
- Published by Wiley in Software: Practice and Experience
- Vol. 51 (5) , 1005-1042
Advanced control-flow and concurrency in C∀
- 20 August 2018
- Published by Wiley in Software: Practice and Experience
- Vol. 48 (12) , 2111-2146
C: Adding modern programming language features to C
Summary: The C programming language is a foundational technology for modern computing with millions of lines of code implementing everything from hobby projects to commercial operating systems. This installation base and the programmers producing it represent a massive software engineering investment spanning decades and likely to continue for decades more. Nevertheless, C, which was first standardized almost 30 years ago, lacks many features that make programming in more modern languages safer and more productive. The goal of the C project (pronounced “C for all”) is to create an extension of C that provides modern safety and productivity features while still ensuring strong backward compatibility with C and its programmers. Prior projects have attempted similar goals but failed to honor the C programming style; for instance, adding object‐oriented or functional programming with garbage collection is a nonstarter for many C developers. Specifically, C is designed to have an orthogonal feature set based closely on the C programming paradigm, so that C features can be added incrementally to existing C code bases, and C programmers can learn C extensions on an as‐needed basis, preserving investment in existing code and programmers. This paper presents a quick tour of C features, showing how their design avoids shortcomings of similar features in C and other C‐like languages. Experimental results are presented to validate several of the new features.
- 20 August 2018
- Published by Wiley in Software: Practice and Experience
- Vol. 48 (12) , 2111-2146
C: Adding modern programming language features to C
Summary: The C programming language is a foundational technology for modern computing with millions of lines of code implementing everything from hobby projects to commercial operating systems. This installation base and the programmers producing it represent a massive software engineering investment spanning decades and likely to continue for decades more. Nevertheless, C, which was first standardized almost 30 years ago, lacks many features that make programming in more modern languages safer and more productive. The goal of the C project (pronounced “C for all”) is to create an extension of C that provides modern safety and productivity features while still ensuring strong backward compatibility with C and its programmers. Prior projects have attempted similar goals but failed to honor the C programming style; for instance, adding object‐oriented or functional programming with garbage collection is a nonstarter for many C developers. Specifically, C is designed to have an orthogonal feature set based closely on the C programming paradigm, so that C features can be added incrementally to existing C code bases, and C programmers can learn C extensions on an as‐needed basis, preserving investment in existing code and programmers. This paper presents a quick tour of C features, showing how their design avoids shortcomings of similar features in C and other C‐like languages. Experimental results are presented to validate several of the new features.
- 17 May 2018
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 30 (18)
High‐contention mutual exclusion by elevator algorithms
Summary: This paper presents new starvation‐free hardware‐assisted and software‐only algorithms for the N‐thread mutual‐exclusion problem. The hardware‐assisted versions use a single atomic‐CAS instruction and no fences. The software‐only algorithms simulate the CAS instruction using a variation of Burns‐Lamport (1 fence) or Lamport's fast algorithm (3 fences). The algorithms are based on Attiya et al, where every thread in the critical section chooses its successor (if one is available). While Attiya et al use a binary tree for this purpose, it can also be done with a linear search. Surprisingly, all software‐only algorithms perform equally well under maximal contention on three different computer architectures; the hardware‐assisted versions perform better under minimal contention. The new algorithms are between −5% to 50% slower for maximal contention than the starvation‐free first‐come first‐served hardware‐assisted MCS algorithm, which uses two atomic instructions (fetch‐store and CAS); they are between 10% to 50% slower than MCS for minimal contention.
- 17 May 2018
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 30 (18)
High‐contention mutual exclusion by elevator algorithms
Summary: This paper presents new starvation‐free hardware‐assisted and software‐only algorithms for the N‐thread mutual‐exclusion problem. The hardware‐assisted versions use a single atomic‐CAS instruction and no fences. The software‐only algorithms simulate the CAS instruction using a variation of Burns‐Lamport (1 fence) or Lamport's fast algorithm (3 fences). The algorithms are based on Attiya et al, where every thread in the critical section chooses its successor (if one is available). While Attiya et al use a binary tree for this purpose, it can also be done with a linear search. Surprisingly, all software‐only algorithms perform equally well under maximal contention on three different computer architectures; the hardware‐assisted versions perform better under minimal contention. The new algorithms are between −5% to 50% slower for maximal contention than the starvation‐free first‐come first‐served hardware‐assisted MCS algorithm, which uses two atomic instructions (fetch‐store and CAS); they are between 10% to 50% slower than MCS for minimal contention.
- 7 November 2017
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 30 (4)
Fast mutual exclusion by the Triangle algorithm
Summary: This paper presents a newstarvation‐freesoftware algorithm for theN‐thread mutual‐exclusion problem. In the absence of contention, the algorithm requires only eight write and four read operations to enter and leave the critical section; to the best of our knowledge, this is optimal. For algorithmswith starvation, five write and two read read operations are optimal. In the presence of contention, the algorithm has excellent performance comparable to the best‐known software solutions using only atomic load and store and to a hardware‐assisted lock (MCS) using stronger atomic primitives and used within the Linux kernel. It is rare for software‐only algorithms for mutual exclusion to perform well for both minimal and maximal contention workloads, making the new algorithm largely self‐tuning when exposed to swings in access patterns.
- 7 November 2017
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 30 (4)
Fast mutual exclusion by the Triangle algorithm
Summary: This paper presents a newstarvation‐freesoftware algorithm for theN‐thread mutual‐exclusion problem. In the absence of contention, the algorithm requires only eight write and four read operations to enter and leave the critical section; to the best of our knowledge, this is optimal. For algorithmswith starvation, five write and two read read operations are optimal. In the presence of contention, the algorithm has excellent performance comparable to the best‐known software solutions using only atomic load and store and to a hardware‐assisted lock (MCS) using stronger atomic primitives and used within the Linux kernel. It is rare for software‐only algorithms for mutual exclusion to perform well for both minimal and maximal contention workloads, making the new algorithm largely self‐tuning when exposed to swings in access patterns.
- 20 September 2015
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 28 (1) , 144-165
Dekker's mutual exclusion algorithm made RW‐safe
- 20 September 2015
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 28 (1) , 144-165
Dekker's mutual exclusion algorithm made RW‐safe
- 6 May 2014
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 27 (3) , 651-701
High‐performanceN‐thread software solutions for mutual exclusion
Summary: Software solutions for mutual exclusion developed over a 30‐year period, starting with complex ad hoc algorithms and progressing to simpler formal ones. While it is easy to dismiss software solutions for mutual exclusion, as this family of algorithms is antiquated and most platforms support atomic hardware instructions, there is still a need for these algorithms in threaded, embedded systems running on low‐cost processors lacking atomic instructions. WhileN‐thread solutions are usually short (10–25 lines of code), each is ingenious with exceptionally subtle aspects, often making it difficult to prove correctness or construct an implementation. This work examines correctness and performance of the implementations. An extensive survey of existing algorithms is presented, with explanations of the intuition behind the algorithms and how they work. Several errors were found and corrections made, as well as a few small improvements, in the existing algorithms; two new high‐performance algorithms were developed. Finally, a worst‐case high‐contention performance experiment is performed to compare the algorithms and contrast them with three common locks based on hardware atomic instructions. The results show our two new algorithms are highly competitive with an equivalent hardware lock (Mellor‐Crummey and Scott) over a range of 1–32 processors. Hence, threading is a viable alternative to event‐driven programming for complex embedded systems without atomic instructions. Copyright © 2014 John Wiley & Sons, Ltd.
- 6 May 2014
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 27 (3) , 651-701
High‐performanceN‐thread software solutions for mutual exclusion
Summary: Software solutions for mutual exclusion developed over a 30‐year period, starting with complex ad hoc algorithms and progressing to simpler formal ones. While it is easy to dismiss software solutions for mutual exclusion, as this family of algorithms is antiquated and most platforms support atomic hardware instructions, there is still a need for these algorithms in threaded, embedded systems running on low‐cost processors lacking atomic instructions. WhileN‐thread solutions are usually short (10–25 lines of code), each is ingenious with exceptionally subtle aspects, often making it difficult to prove correctness or construct an implementation. This work examines correctness and performance of the implementations. An extensive survey of existing algorithms is presented, with explanations of the intuition behind the algorithms and how they work. Several errors were found and corrections made, as well as a few small improvements, in the existing algorithms; two new high‐performance algorithms were developed. Finally, a worst‐case high‐contention performance experiment is performed to compare the algorithms and contrast them with three common locks based on hardware atomic instructions. The results show our two new algorithms are highly competitive with an equivalent hardware lock (Mellor‐Crummey and Scott) over a range of 1–32 processors. Hence, threading is a viable alternative to event‐driven programming for complex embedded systems without atomic instructions. Copyright © 2014 John Wiley & Sons, Ltd.
- 9 March 2005
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 17 (9) , 1133-1172
Concurrent urban legends
- 9 March 2005
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 17 (9) , 1133-1172
Concurrent urban legends