非阻塞演算法（non-blocking algorithm）

想想當共享任務上的某個工人突然去喝杯咖啡、休息很久時會出什麼差錯。在阻塞（blocking）設計——也就是建立在鎖之上的設計——若那個工人正握著鎖，其他人就會凍住，直到他回來。非阻塞（non-blocking）設計則是：任何執行緒的暫停都絕不會凍住其他執行緒。這是本領域整個技術家族的統稱。

精確地說：一個演算法是非阻塞的，是指任何執行緒的暫停或失敗都不能阻止其他執行緒取得進展。沒有由鎖保護的臨界區間（critical section）；執行緒改以原子讀改寫指令（如比較並交換 compare-and-swap）來協調。非阻塞正好是你已認識的三個進展類別的聯集：等待無關、無鎖、無障礙全都是非阻塞，依強度遞減。相對的是阻塞演算法——任何會讓一個執行緒等待另一個執行緒的設計，這正是互斥鎖、條件變數與號誌所做的事。

其動機既在於穩健，也在於速度。因為沒有執行緒能握住別人必須等待的資源，非阻塞演算法對若干困擾有鎖程式碼的災難免疫：在更新中途被殺掉的執行緒不會讓系統死結；優先權反轉（priority inversion，低優先權執行緒握著高優先權執行緒所需的鎖）不會發生；也不會出現一列執行緒堆在一個慢吞吞的持鎖者後面的車隊現象。代價是非阻塞演算法遠更難設計、證明正確與測試——這就是為什麼大多數程式對大多數事情仍然用鎖。