Links
Below is a collection of links to various resources related to synchronization algorithms.
Books
To the be best of my knowledge there is only one comprehensive book on synchronization algorithms. And, as you may guess, by book on synchronization algorithms I do not mean a one that considers implementation of a producer-consumer queue my means of a mutex and a condition variable. By book on synchronization algorithms I mean a one that considers memory models, atomic RMW operations, lockfree queues, implementation of mutexes, lockfree lists and hash-maps and so on. And here it is:
The authors are Maurice Herlihy and Nir Shavit - also the authors of the better part of research papers mentioned below - so, trust me, they know what they are writing about.
Blogs & Websites
Paul is the guy behind Linux kernel's RCU. Don't miss his "Is Parallel Programming Hard, And, If So, What Can You Do About It?" electronic book.
Announces of new research papers and insightful blogs.
A collection of detailed articles on such things as implementation of plain and reader-writer mutex, queues, events, futexes, condition variables, as well as some C tips and tricks. Recommended.
Doug "Fork/Join" Lea Home Page
Java Memory Model, Java Fork/Join, Java Concurrent Collections. It is there.
Don't know who is Ulrich Drepper? Then go and read "What every programmer should know about memory" (9 parts).
Detailed blogs about synchronization, hardware transactional memory, implementation of JVM features and so on.
Concurrency, memory models issues, guidelines and tips in .NET/C# context.
Practical lockfree data structures
Home page of a research group at the University of Cambridge.
High-Performance Synchronization
Home page of a research group at the University of Rochester.
Scalable Synchronization Research Group
Home page of a research group at Sun Labs at Oracle.
Philippas Tsigas: Publications
Maged Michael: Selected Publications
Maurice Herlihy's Publications
Data-Race (in Russian)
Articles on synchronization algorithms, memory fences, safe memory reclamation, etc.
Intel Guide for Developing Multithreaded Applications
Covers parallel computing basics, typical pitfalls and Intel library and tooling support.
Java synchronization algorithms.
Articles
Intel® 64 and IA-32 ArchitecturesSoftware Developer’s Manual (8.2.2 Memory Ordering in P6 and More Recent Processor Families).
Standard for ProgrammingLanguage C++ (1.10 Multi-threaded executions and data races; 29 Atomic operations library).
Source Code To Study
Includes SPSC queue, stack, eventcount, reader-writer spinlock, SMR as well as some implementation of atomic operations and memory fences. C. From the comp.programming.threads rock star Chris "SenderX" Thomasson.
Includes strongly thread-safe reference counting, fastsmr (SMR+RCU), eventcount, fast condition variable. C/C++. From Joseph Seigh who taught me a lot in the field.
Includes a LOT of concurrent containers for C++ and Java.
Queue, ring buffer, list, stack in C.
Research Papers
Lockfree Linked Lists and Skip Lists (pdf)
Split-Ordered Lists: Lockfree Extensible Hash Tables (ACM, slides). Very interesting lockfree hash table. It uses recursive split-ordering technique. Works on top of any singly linked list. Requires only single word CAS. Requires some kind of PDR. Includes full source and implementation of Michael's lockfree list.
Fast and Lockfree Concurrent Priority Queues for Multi-Thread Systems (pdf). Requires only single word CAS. Requires some kind of PDR. Includes full source.
An Optimistic Approach to Lockfree FIFO Queues (pdf). Requires only single word CAS. Requires some kind of PDR. Includes full source.
A Scalable Lockfree Stack Algorithm (pdf). Uses very interesting trick - elimination-backoff. Intended for very high load on multiprocessor/multicore system.Requires only single word CAS. Requires some kind of PDR. Includes full source.
Lockfree Techniques for Concurrent Access to Shared Objects (pdf). LIFO and FIFO stack implementations. Requires double word CAS. Includes source.
Non-Blocking Algorithms and Preemption-Safe Locking on Multiprogrammed Shared Memory Multiprocessors (pdf).
Obstruction-Free Synchronization: Double-Ended Queues as an Example (pdf). Introduction of obstruction-free synchronization. Very interesting. Requires only single word CAS. Includes full source.
Safe Memory Reclamation for Dynamic Lockfree Objects Using Atomic Reads and Writes (pdf). The so-called SMR (Safe Memory Reclamation) or hazard-pointers. Must read.
Efficient Almost Waitfree Parallel Accessible Dynamic Hash-tables (pdf)
A Pragmatic Implementation of Non-Blocking Linked-Lists (pdf). The so-called Harris list algorithm. Requires only single word CAS. Requires some kind of PDR. Includes source.
Non-blocking hash-tables with open addressing (pdf).
A Provably Correct Scalable Concurrent Skip List (pdf).
A Lazy Concurrent List-Based Set Algorithm (pdf). Upgrade for Michael’s lockfree set algorithm. Very useful.
Non-blocking Memory Management Support for Dynamic-Sized Data Structures (pdf). The so-called ROP (Repeat Offender Problem), PTB (Pass The Buck). SMR analog. Must read.
Bringing Practical Lockfree Synchronization to 64Bit Applications (pdf). LL/SC emulated with CAS. PDR included. Source included. Fullload of CASes per operation included.
Non-blocking k-compare-single-swap (pdf).
MultiLane : a concurrent blocking multiset (pdf).