Concurrency, Synchronization, and Persistence Research
Synchronization serves to constrain the interleaving of actions performed by multiple threads of control (e.g., on a multicore processor), allowing only correct executions. Over the years, this ongoing project has developed some of the most efficient and widely used algorithms for locking, concurrent data structures, transactional memory, and persistence.
Available on GitHub:
Overview
With the explosion in multicore processors, performance and ease of
programming for shared-memory multithreaded code have become critical to
the future of computing. In the early 1990s, our work helped pioneer the
field of scalable synchronization, developing locking
mechanisms that scale well to very large numbers of
processors/cores. Over the years we have also explored a variety of
related topics, including (1) mechanisms for cooperative synchronization
and scheduling, which minimize unnecessary spinning, maximize processor
locality, and avoid contention for both lock and non-lock data; (2)
comparative evaluation of alternative mechanisms for atomic update of
shared data structures, including locks, nonblocking synchronization,
and function shipping; (3) implementation of atomic hardware primitives
on scalable architectures; (4) evaluation of the interaction of
synchronization with coherence; (5) timeout-capable spin locks for
user-level code; and (6) nonblocking “dual” data structures,
which combine lock freedom with condition synchronization. Much of our
recent work has focused on (7) software transactional memory, including
conflict detection and validation mechanisms, contention management,
privatization, language and compiler support, formal semantics, and
hardware acceleration; and (8) data structures, locking mechanisms,
transactions, and proof techniques for live update of persistent data
intended to survive program executions and system crashes.
Work stemming originally from
“Algorithms
for Scalable Synchronization
on Shared-Memory Multiprocessors,”
by John M. Mellor-Crummey and Michael L. Scott, [ACM TOCS, Feb. 1991],
winner of the 2006 Edsger
W. Dijkstra Prize in Distributed Computing.
Supported by NSF grants
CCR-9319445 (4/94–9/97),
CCR-0204344 (6/02–5/05),
CNS-0615139 (9/06–8/09),
CCF-0702505 (9/07–8/10),
CSR-0720796 (9/07–8/10),
CCR-0963759 (7/10–6/14),
CCF-1116055 (8/11–7/14),
CNS-1116109 (8/11–7/13),
CCF-1337224 (9/13–8/16),
CCF-1422649 (9/14–8/17),
CCF-1717712 (9/17–8/20),
CNS-1900803 (10/19–9/25),
and CNS-1955498 (10/20–9/26);
by equipment grants from IBM and Oracle (Sun), and by financial support
from Oracle, Intel, Microsoft, IBM, and Google.
People
Principal investigator
PhD alumni
MS alumni
BS alumni
- Athul Acharya
- Eric Bluestein
- David Eisenstat
- Matthew Graichen
- Julian Herwitz
- Chris Heriot
- Jake Pershing
- Corey Proscia
- Aaron Rolett
|
- Kyle Sabo
- Michael Silverman
- Andrew Sveikauskas
- Nicholas Wrem
- Matthew Graichen
- Chris Kjellqvist
- Jack Yu
- Beakal Lemeneh
|
Postdocs and visiting scholars
Pseudocode
-
Scalable spinlocks and barriers.
Includes test-and-set and ticket locks; queue locks; and
centralized, tree-based, and FFT-style (“butterfly”)
barriers.
From the 1991
TOCS paper, with later additions due to (a) Craig,
Landin, and Hagersten, and (b) Auslander, Edelsohn, Krieger,
Rosenburg, and Wisniewski.
-
Scalable busy-wait reader-writer locks.
Includes reader-preference, writer-preference, and fair locks.
From the
1991
PPoPP paper.
-
Scalable adaptive combining tree barriers.
Combine local-only spinning, logarithmic critical paths, amortization of
overhead for skewed arrival, and “fuzziness.”
From the
1994
IJPP paper.
-
Variations on Lamport’s fast mutual exclusion lock.
Use no atomic instructions other than read and write.
From
UR TR 460 (1993).
-
Preemption-safe and scheduler-conscious synchronization algorithms.
Includes two queue-based mutual exclusion locks; test-and-set and ticket
locks; a fair, scalable, queue-based reader-writer lock; competitive and
optimal-time small-scale barriers; and a scalable barrier.
All algorithms avoid busy-waiting for action by preempted processes,
including those waiting in line for a FIFO queue or ticket lock.
Most employ a widened kernel-user interface.
From the
1997
TOCS paper.
-
A highly-concurrent multi-lock concurrent priority queue.
Uses bottom-up insertions and “bit-reversal” choice among
fringe nodes. From the
1996
IPL paper.
-
Fast concurrent queue algorithms.
The lock-free queue in particular is widely used. Among other
places, it has been adopted into the
java.util.concurrent package of JSR 166, incorporated
into the standard Java library as of
JDK 1.5.0.
From the
1996
PODC and
1998
JPDC papers.
-
Timeout-capable queue-based locks
-
Scalable Queue-Based Spin Locks with Timeout.
Combine fairness and scalability (from queueing and local-only
spinning) with the ability to time out and abandon an attempt to
acquire a lock. Make it safe to use queue-based locks in user-level
code without OS modifications. From the
2001
PPoPP paper.
-
Non-Blocking Timeout in Scalable Queue-Based Spin Locks.
Improve upon the PPoPP 2001 results by making timeout a
nonblocking operation, at the expense of worst-case (but extremely
unlikely) unbounded space requirements.
Guaranteed to complete in a bounded number of time steps even in the
face of preemption of other threads. From the
2002
PODC paper.
-
Non-Blocking
Timeout in a NUMA-Aware Queue-Based Lock.
Settles, in the affirmative, an open question posed (in Feb. 2000) by
Mike O’Donnell and colleagues at
Mercury Computer
Systems: namely, whether it is possible to build a fair,
contention-free, timeout-capable lock on a no-remote-caching machine
without a universal atomic primitive (e.g.,
compare-and-swap or
load-linked/store-conditional).
-
Time-Published
Queue-Based Spin Locks.
Combine fairness, scalability, timeout, and preemption tolerance.
Make it feasible, for the first time, to use queue-based spin locks on
multiprogrammed systems with a standard kernel interface.
To accompany the 2005
HiPC paper.
-
Lock-free
dualstack and dualqueue.
Nonblocking data structures that can hold either data or
reservations.
Pop and dequeue
operations spin if no data is avaialble. While spinning they cause no
contention. Furthermore, pending requests are guaranteed to be
fulfilled in LIFO (for the dualstack) or FIFO (for the dualqueue)
order.
From the 2004 DISC
paper.
-
Generic
dual structures and fast dual queues.
From the 2017
TOPC paper.
These (1) allow any nonblocking container for data to be paired with
almost any nonblocking container for requests, and (2) leverage the
LCRQ of Morrison
& Afek to provide very high throughput on machines with
fetch-and-increment.
Last Change:
03 November 2025 /
