[資訊] 非阻塞同步(Non-blocking Synchronization)

lock-free介紹
https://www.itread01.com/content/1541791213.html

簡化概念下的 lock-free 程式設計
https://zhuanlan.zhihu.com/p/53012280

Lock-free 程式設計：A Case Study（上）
http://kaiyuan.me/2017/12/14/lock-free-prog1/

Lock-free 程式設計：A Case Study（下）
http://kaiyuan.me/2018/02/07/lock-free-prog2/

求推薦Lock-Free 演算法相關論文？
https://www.zhihu.com/question/23705245

Lock-Free 程式設計
https://www.cnblogs.com/gaochundong/p/lock_free_programming.html

無鎖程式設計 / lock-free / 非阻塞同步，即不使用鎖的情況下實現多執行緒之間的變數同步，也就是在沒有執行緒被阻塞的情況下實現變數的同步，所以也叫非阻塞同步（Non-blocking Synchronization）。

非同步阻塞的實現可以分成三個級別：
wait-free:
是最理想的模式，整個操作保證每個執行緒在有限步驟下完成。保證系統級吞吐（system-wide throughput）以及無執行緒飢餓。截止2011年，沒有多少具體的實現。即使實現了，也需要依賴於具體CPU。
lock-free:
允許個別執行緒飢餓，但保證系統級吞吐。確保至少有一個執行緒能夠繼續執行。wait-free的演算法必定也是lock-free的。
obstruction-free:
在任何時間點，一個執行緒被隔離為一個事務進行執行（其他執行緒suspended），並且在有限步驟內完成。在執行過程中，一旦發現數據被修改（採用時間戳、版本號），則回滾。也叫做樂觀鎖，即樂觀併發控制(OOC)。事務的過程是：1讀取，並寫時間戳；2準備寫入，版本校驗；3校驗通過則寫入，校驗不通過，則回滾。lock-free必定是obstruction-free的。

記憶體模型（Memory Model）對細細微性鎖的影響：
在多執行緒系統中，當多個執行緒同時訪問共用的記憶體時，就需要一個規範來約束不同的執行緒該如何與記憶體互動，這個規範就稱之為記憶體模型（Memory Model）。順序一致性記憶體模型非常的直觀，也易於理解。但實際上，由於該模型在記憶體硬體實現效率上的限制，導致商用的 CPU 架構基本都沒有遵循該模型。一個更貼近實際的多處理器記憶體模型更類似於下圖中的效果。


#非阻塞同步, Non-blocking Synchronization, wait-free, lock-free, obstruction-free, 樂觀鎖, ABA, CPU, Memory