求推薦Lock-Free 演算法相關論文？

12-26

最近對無鎖演算法比較感興趣，看了一些介紹無鎖並發數據結構相關的一些論文，現在我想看一些經典的無鎖演算法相關的論文，希望大家能推薦一些，謝謝了~~

正好從事這方面的研究，補充一下已有的回答。

多核並發演算法發展了近三十多年，很多經典的論文已經被整編起來變成了教科書。這裡推薦一本 @Chao Mai 提到了的 The Art of Multiprocessor Programming by Maurice Herlihy and Nir Shavit 。這本書也是我的老闆教課選用的教材，其兩位作者都是領域內的大牛。

無鎖演算法 (lock-free algorithm) 和無等待演算法 (wait-free algorithm) 的近代起源可以追溯到Herlihy的論文 Wait-free synchronization,1991。在此之前，計算機硬體所提供的同步原語 (synchronization primitives) 只有原子寄存器 (atomic registers) 和少數經典原語比如 test_and_set 和 fetch_and_add。演算法的研究也因此局限在利用這些有限的同步原語來設計簡單的並發對象 (concurrent object)。Herlihy的這篇論文從理論上證明了現有同步原語不夠強大，不足以用來實現所有的並行對象。論文的核心在於用解決共識協議 (consensus protocol) 的能力來衡量同步原語的同步能力。原子寄存器只能解決一個線程的共識問題，所以共識數 (consensus number) 是1；而 fetch_and_add 能解決最多兩個線程的共識問題，其共識數是2。Herlihy更進一步提出了存在共識數為無限的同步原語，也就是現在被主流硬體所廣泛採用的 compare_and_swap，能用來實現所有的並發對象。

從此依賴原子寄存器的演算法成了歷史，compare_and_swap 可以輕易實現各種簡單的並發對象比如互斥鎖。隨後Herlihy在 A methodology for implementing highly concurrent data objects, 1993 中提出了一種通用構建 (universal construction) 能把所有的順序數據結構 (sequential data structure) 轉化為無鎖數據結構。基本思路是線程間共享一個指向數據結構的指針。每當一個線程企圖修改數據結構的時候，它在線程局部創建一個當前數據結構的拷貝然後做出相應的修改。完成修改後使用 compare_and_swap 來嘗試將共享的數據結構指針更新成指向本地拷貝的指針。如果 compare_and_swap 失敗則說明有其他線程搶先完成了修改，這個線程將重新讀取共享指針並重複拷貝和修改的操作直到 compare_and_swap 成功。這個演算法保證了無鎖進展 (lock-free progress)：就算任何一個線程在操作數據結構時崩潰，都不會影響到其他線程，系統作為一個整體總是能保證進展。但是不難想到這種通用構建的效率並不高，因為它實質上阻止了任何對於數據結構的並發操作——任何時刻都只可能有一個線程成功修改共享的數據結構指針，其他線程的操作必然會失敗和重試。

進入九十年代和二十一世紀就有了無鎖數據結構的蓬勃發展。利用 compare_and_swap 這個萬能同步原語，大部分的常用數據結構都有了相應的無鎖甚至是無等待版本（參見@Chao Mai 的回答）。比起Herlihy早期的通用構建，新的演算法都嘗試利用數據結構本身對並發訪問 (concurrent access) 的支持來增加可擴展性 (scalability)。比如鏈表 (linked list)，如果兩個線程分別訪問兩個不同的節點，好的無鎖演算法都應該允許這兩個操作並發進行。僅當發生訪問衝突時需要協調線程間的操作。反過來說，如果一個數據結構本身對並發訪問有很好支持那麼其轉化為無鎖演算法後的可擴展性潛力就越大。反面教材比如堆棧 (stack) 其本身的操作語義就限制了並發性 (concurrency)：其壓棧和退棧操作訪問都是棧頂的元素，並發訪問會產生很多額外的競爭 (contention) 導致效率下降。稍好一點的比如隊列 (FIFO queue)，其語義至少可以允許並發的入隊和出隊。然後並發的入隊同樣會導致競爭。一個很有意思的例子是跳躍列表 (skip-list)。William Pugh 發明的跳躍列表最早是作為平衡樹的替換演算法被提出來的。因為其節點的隨機分布特性，跳躍列表不需要平衡就能擁有搜索樹一樣的log(n)的時間複雜度。但是跳躍列表真正閃光是人們發現它的分散式結構和對並發訪問的良好支持後。現有的並發字典和集合多半是都是基於條約列表的。對比之下現有的無鎖搜索樹很多都是不平衡的，導致無法投入實際使用。因為平衡樹的過程中需要鎖定訪問大量的節點，設計搜索樹的無鎖平衡演算法也一直是研究難點。

再補充幾個沒有提到的數據結構：

數組 (vector)
Damian Dechev, Peter Pirkelbauer, Bjarne Stroustrup, Lock-free Dynamically Resizable Arrays

Steven Feldman, Carlos Valeraleon, Damian Dechev, An Efficient Wait-Free Vector

哈希表 (hash table)
Shalev, Ori, and Nir Shavit, Split-ordered lists: Lock-free extensible hash tables

Michael, Maged M, High performance dynamic lock-free hash tables and list-based sets

隊列 (queue)
Michael, Maged M., and Michael L. Scott, Simple, fast, and practical non-blocking and blocking concurrent queue algorithms

跳躍列表 (skip-list)
Herlihy, Maurice, et al., A simple optimistic skiplist algorithm

Fraser, Keir, and Tim Harris, Concurrent programming without locks 註：Fraser的實現被認為是效率最高，代碼可以從作者網站下載。

優先隊列 (priority queue)
Lindén, Jonatan, and Bengt Jonsson, A skiplist-based concurrent priority queue with minimal memory contention

順便推銷一下自己的演算法 Zhang, Deli, and Damian Dechev, A Lock-free Priority Queue Design Based on Multi-dimensional Linked Lists

兩個開源庫
Tervel
Libcds

論文

Linked List

lock free linked lists using compare-and-swap, John D. Valois
A Pragmatic Implementation of Non-Blocking Linked-Lists, Timothy L. Harris

Queue

A Non-Blocking Concurrent Queue Algorithm, Bruno Didot
Implementing Lock-Free Queues, John D. Valois
SnapQueue: Lock-Free Queue with Constant Time Snapshots, Aleksandar Prokopec

Tree

A Practical Concurrent Binary Search Tree, Nathan G. Bronson, etc.
Non-blocking k-ary Search Trees, Trevor Brown and Joanna Helga
Non-blocking Binary Search Trees, Faith Ellen, etc.
Range Queries in Non-blocking k-ary Search Trees, Trevor Brown
Chromatic binary search trees A structure for concurrent rebalancing, Otto Nurmi, etc.

Trie

Concurrent Tries with Ef?cient Non-Blocking Snapshots, Aleksandar Prokopec

書籍
The Art of Multiprocessor Programming, Maurice Herlihy, Nir Shavit
C++ Concurrency in Action: Practical Multithreading, Anthony Williams
Is Parallel Programming Hard, And, If So, What Can You Do About It?, Paul E. McKenney, etc
Memory Ordering in Modern Microprocessors, Paul E. McKenney
Practical lock-freedom, Keir Fraser

博客
An Introduction to Lock-Free Programming
Trevor Brown"s home page
Lock-free Data Structures. 1
何登成的技術博客
Concurrency Freaks
Paul E. McKenney
Paul E. McKenney: Read-Copy Update (RCU) （既然 @廖統浪提到了RCU）
Yebangyu"s Blog

Library and Some Implementation
khizmax/libcds · GitHub
concurrencykit/ck · GitHub
gramoli/synchrobench · GitHub （README.md中有很多論文）
scala/src/library/scala/collection/concurrent at 2.11.x · scala/scala · GitHub （Concurrent Tries with Ef?cient Non-Blocking Snapshots的實現）

Talk and Presentation
CPU Cache and Memory Ordering——並發程序設計入門
CppCon 2014: Herb Sutter "Lock-Free Programming (or, Juggling Razor Blades), Part I"
CppCon 2014: Jeff Preshing "How Ubisoft Develops Games for Multicore - Before and After C++11"
CppCon 2015: Michael Wong 「C++11/14/17 atomics and memory model..."

人
John D. Valois
Nir Shavit
Paul E. McKenney
Trevor Brown
Aleksandar Prokopec
Herb Sutter
Doug lea

Lock-free linked lists using compare-and-swap
Non-blocking binary search trees
An Introduction to Lock-Free Programming 系列

看這個網站吧
建議先看hazard pointer那篇
http://liblfds.org/mediawiki/index.php?title=White_Papers

Concurrent programming without locks
Practical lock-freedom - The Computer Laboratory

我在玩linux的時候發現rcu這個神奇的技巧, 相關文檔在 Documentation/RCU 目錄里. 應該算Lock-Free的一個分支吧: http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/Documentation/RCU/

Lock-Free Data Structures using STMs in Haskell

用ghc提供的STM機制寫無鎖數據結構的講解，簡單實用。

經典論文集錦：JerryYangSH/LockFreeProgrammingPractice ，幾百頁的papers，慢慢看看吧