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

Подробнее о Java-конференциях: — весной — JPoint: https://jrg.su/gTrwHx — осенью — Joker: https://jrg.su/h7yvG4 — — . . . . 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.