Название: Shared-Memory Synchronization, 2nd Edition
Автор: Michael L. Scott, Trevor Brown
Издательство: Springer
Серия: Synthesis Lectures on Computer Architecture
Год: 2024
Страниц: 251
Язык: английский
Формат: pdf (true)
Размер: 10.1 MB

This book offers a comprehensive survey of shared-memory synchronization, with an emphasis on “systems-level” issues. It includes sufficient coverage of architectural details to understand correctness and performance on modern multicore machines, and sufficient coverage of higher-level issues to understand how synchronization is embedded in modern programming languages.

The primary intended audience for this book is “systems programmers”—the authors of operating systems, library packages, language run-time systems, concurrent data structures, and server and utility programs. Much of the discussion should also be of interest to application programmers who want to make good use of the synchronization mechanisms available to them, and to computer architects who want to understand the ramifications of their design decisions on systems-level code.

Chapters 4, 5, and 7 are in some sense the heart of the monograph: they cover spin locks, busy-wait condition synchronization (barriers in particular), and scheduler-based synchronization, respectively. To set the stage for these, Chapter 2 surveys aspects of multicore and multiprocessor architecture that significantly impact the design or performance of synchronizing code, and Chapter 3 introduces formal concepts that illuminate issues of feasibility and correctness.

Chapter 6 considers atomicity mechanisms that have been optimized for the important special case in which most operations are read-only. Later, Chapter 8 provides a brief introduction to nonblocking algorithms, which are designed in such a way that all possible thread interleavings are correct. Chapter 9 provides a similarly brief introduction to transactional memory, which uses speculation to implement atomicity without (in typical cases) requiring mutual exclusion. (A full treatment of both of these topics is beyond the scope of the monograph.)

This second edition, published roughly a decade after the original, has numerous small improvements throughout—clarifications, bug fixes, and references to newer work. It also incorporates two major updates. First, we have re-worked and clarified the memory model and notation used in our examples. In particular, we now employ explicit load and store operations for all accesses to shared (atomic) variables, and we have adopted the C++ convention of making such accesses fully ordered (sequentially consistent) unless otherwise noted. These conventions necessitated changes to most of our algorithmic pseudocode.

Second, we have added significant new material, particularly in Chapter 8 (Nonblocking Algorithms). This includes detailed description of the EFRB tree; a survey of other trees; additional lists, queues, deques, hash tables, and skip lists; extensive discussion of safe memory reclamation; and expanded coverage of high-level atomic constructions.