Skip to content

Non-blocking algorithm

In computer science, a non-blocking algorithm ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress regardless of scheduling; wait-free if there is also guaranteed per-thread progress.

Single-consumer

Multiple-consumer

Wait-freedom

Wait-freedom is the strongest non-blocking guarantee of progress, combining guaranteed system-wide throughput with starvation-freedom. An algorithm is wait-free if every operation has a bound on the number of steps the algorithm will take before the operation completes. This property is critical for real-time systems and is always nice to have as long as the performance cost is not too high.

Lock-freedom

Lock-freedom allows individual threads to starve but guarantees system-wide throughput. An algorithm is lock-free if it satisfies that when the program threads are run sufficiently long at least one of the threads makes progress (for some sensible definition of progress). All wait-free algorithms are lock-free.

Single producer single consumer

SPSC (Single-producer single-consumer)

Obstruction-free

Project

  • Awesome Lock-Free
  • The Top 32 Lock Free Open Source Projects
  • Mintomic - A Small, Portable Lock-Free API
  • LMAX Disruptor - High Performance Inter-Thread Messaging Library
  • Boost.Lockfree - Boost lock-free data structures.
  • ConcurrencyKit - Concurrency primitives.
  • Folly - Facebook Open-source Library (has good implementation of MPMC queue).
  • Junction - Concurrent data structures in C++.
  • MPMCQueue - A bounded multi-producer multi-consumer lock-free queue written in C++11.
  • SPSCQueue - A bounded single-producer single-consumer wait-free and lock-free queue written in C++11.
  • Seqlock - Implementation of Seqlock in C++.
  • Userspace RCU - liburcu is a userspace RCU (read-copy-update) library.
  • libcds - A C++ library of Concurrent Data Structures.
  • Lockless - Lockless Performance
  • liblfds - portable, license-free, lock-free data structure library written in C.
  • DKit - C++ Library of Atomic and Lockless Data Structures
  • Microsoft L4 HashTable - L4 (Lock-Free on Read) Hashtable is a C++ library that implements hash table with arbitray byte stream keys/values.
  • xenium - A C++ library providing various concurrent data structures and reclamation schemes.
  • Github - DNedic/lockfree - A collection of lock-free data structures written in standard C++11

Problem

See also

Favorite site

Blogs

Books

Papers

Talks

References

  1. Lock_Free_Programming.pdf ↩

  2. Concurrency-in-action-chapter-7.tar.gz ↩

  3. CppConcurrencyInAction-wiki-880ec15.tar.gz ↩

  4. P298_per-akelarson_vldb2012.pdf ↩

  5. Non-Blocking_Algorithm.pdf ↩