22 Result(s)
-
Chapter
Correction to: Shared-Memory Synchronization
Correction to: M. L. Scott and T. Brown, Shared-Memory Synchronization, Synthesis Lectures on Computer Architecture, https://doi.org/10.1007/978-3-031-38684-8
-
Chapter
Read-Mostly Atomicity
In Chapter 4 we considered the topic of busy-wait mutual exclusion, which achieves atomicity by allowing only one thread at a time to execute a critical section. While m...
-
Chapter
Introduction
In computer science, as in real life, concurrency makes it much more difficult to reason about events. In a linear sequence, if \(E_1\)
-
Chapter
Architectural Background
The correctness and performance of synchronization algorithms depend crucially on architectural details of multicore and multiprocessor machines. This chapter provides an overview of these details. It can be s...
-
Chapter
Practical Spin Locks
The mutual exclusion problem was first identified in the early 1960s. Dijkstra attributes the first 2-thread solution to Theodorus Dekker (Dijkstra 1968b). Dijkstra himself published an n-thread solution in 1965 ...
-
Chapter
Nonblocking Algorithms
When devising a concurrent data structure, we typically want to arrange for methods to be atomic—most often linearizable (Sec. 3.1.2). Most concurrent algorithms achieve...
-
Chapter
Essential Theory
Concurrent algorithms and synchronization techniques have a long and very rich history of formalization—far too much to even survey adequately here. Arguably the most accessible resource for practitioners is t...
-
Chapter
Busy-Wait Synchronization with Conditions
In Chapter 1 we suggested that almost all synchronization serves to achieve either atomicity or condition synchronization. Chapter 4 considered spin-based atomicity. The current chapter considers spin-based co...
-
Chapter
Synchronization and Scheduling
So far in this monograph, we have emphasized busy-wait synchronization. In the current chapter we turn to mechanisms built on top of a scheduler, which multiplexes some collection of cores among a (typically larg...
-
Chapter
Transactional Memory
Transactional memory (TM) has been one of the most active areas of synchronization research over the course of the past two decades, spanning literally hundreds of published papers. The current chapter attempt...
-
Chapter and Conference Paper
Linearizability of Persistent Memory Objects Under a Full-System-Crash Failure Model
This paper provides a theoretical and practical framework for crash-resilient data structures on a machine with persistent (nonvolatile) memory but transient registers and cache. In contrast to certain prior w...
-
Chapter and Conference Paper
Generic Multiversion STM
Multiversion software transactional memory (STM) allows a transaction to read old values of a recently updated object, after which the transaction may serialize before transactions that committed earlier in physi...
-
Chapter and Conference Paper
Toward a Formal Semantic Framework for Deterministic Parallel Programming
Deterministic parallelism has become an increasingly attractive concept: a deterministic parallel program may be easier to construct, debug, understand, and maintain. However, there exist many different defini...
-
Chapter and Conference Paper
Fastpath Speculative Parallelization
We describe Fastpath, a system for speculative parallelization of sequential programs on conventional multicore processors. Our system distinguishes between the lead thread, which executes at almost-native speed,...
-
Chapter and Conference Paper
Transactions as the Foundation of a Memory Consistency Model
We argue that traditional synchronization objects, such as locks, conditions, and atomic/volatile variables, should be defined in terms of transactions, rather than the other way around. A traditional critical se...
-
Chapter and Conference Paper
Ordering-Based Semantics for Software Transactional Memory
It has been widely suggested that memory transactions should behave as if they acquired and released a single global lock. Unfortunately, this behavior can be expensive to achieve, particularly when—as in the ...
-
Chapter and Conference Paper
Transaction Safe Nonblocking Data Structures
This brief announcement focuses on interoperability of software transactions with ad hoc nonblocking algorithms. Specifically, we modify arbitrary nonblocking operations so that (1) they can be used both insid...
-
Chapter and Conference Paper
Conflict Detection and Validation Strategies for Software Transactional Memory
In a software transactional memory (STM) system, conflict detection is the problem of determining when two transactions cannot both safely commit. Validation is the related problem of ensuring that a transaction ...
-
Chapter and Conference Paper
Preemption Adaptivity in Time-Published Queue-Based Spin Locks
The proliferation of multiprocessor servers and multithreaded applications has increased the demand for high-performance synchronization. Traditional scheduler-based locks incur the overhead of a full context ...
-
Chapter and Conference Paper
Adaptive Software Transactional Memory
Software Transactional Memory (STM) is a generic synchronization construct that enables automatic conversion of correct sequential objects into correct nonblocking concurrent objects. Recent STM systems, though s...
