Danny Hendler — Lock-free concurrent data structures (Part 1)

Ближайшая конференция — JPoint 2025, 3–4 апреля (Москва + трансляция).
— —
. . . . Lock-free algorithms are shared-memory multiprocessor algorithms that can avoid hazardous race conditions and guarantee correctness without using mutual exclusion locks. They are in general more resilient to asynchronous conditions than lock-based algorithms, since they guarantee progress even if some of the threads participating in the algorithm are delayed for a long duration or even fail-stop. On the other hand, lock-free algorithms are less resilient to asynchrony than wait-free ones, since they only guarantee global progress in spite of thread failures, whereas the latter guarantee that any non-failed thread can make progress. On the up side, lock-free algorithms are often easier to devise and more efficient than their wait-free counterparts.

In this mini-course, we will study well-known lock-free algorithms for several concurrent data-structures. In addition to being interesting in their own right, these will serve to convey algorithmic techniques, such as elimination, that can be used for devising high-throughput lock-free implementations. If time permits, we will also discuss the notion of helping and describe open problems that relate to it.

[felipegutierrez]

very good. thanks for posting this video

[stIncMale]

08:19 - "if one thread dies while holding the lock, then other threads can not make progress". This does not seem like a proof that wait-free/lock-free algorithm can not be implemented using locks, because thread-oblivious locks mentioned by Nir Shavit in "Locking, from traditional to modern (Part 3)" (19:45) can be unlocked by any thread.