Below is a collection of links to various resources related to synchronization algorithms. BooksTo 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:Blogs & WebsitesPaul "RCU" McKenney's JournalPaul 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. David Dice's Weblog Announces of new research papers and insightful blogs. Lockless 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. Ulrich Drepper's Livejournal Don't know who is Ulrich Drepper? Then go and read "What every programmer should know about memory" (9 parts). Dr. Cliff Click's Blog Detailed blogs about synchronization, hardware transactional memory, implementation of JVM features and so on. Joe Duffy's Weblog 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 Hans J. Boehm Homepage 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. Source Code To StudyIncludes 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 PapersLockfree Linked Lists and Skip Lists (pdf)
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). |
Home > Lockfree Algorithms >