無鎖進展（lock-free progress）

想像一間忙碌的廚房，幾位廚師共用一塊砧板。避免碰撞的常見做法是一條規則：誰拿著砧板就歸誰，其他人等。那種等待就是鎖。現在想像另一種設計，沒有人需要排隊等候——廚師快速嘗試搶下一個位置，若發生碰撞，總有至少一人成功，工作因而向前推進。無鎖（lock-free）就是這第二種風格的精確說法。它是關於一整群執行緒（thread）的進展保證，而不是關於任何單一執行緒。

精確地說：一個演算法是無鎖的，是指只要程式執行得夠久，就總有至少一個執行緒在取得進展——完成一次操作——無論作業系統如何暫停、拖慢或交錯（interleave）其他執行緒。關鍵的後果是：整個系統永遠不會卡死。即使某個執行緒在工作中途被永久暫停，其他執行緒仍能完成自己的操作；它們不會因為等待那個凍住的執行緒醒來釋放某樣東西而被阻塞（blocking）。這正是互斥鎖（mutex）做不到的：若持有互斥鎖的執行緒被排程器暫停，所有在該鎖上等待的執行緒都會卡住，直到它恢復為止。

要小心無鎖「不」代表什麼。它不代表更快——在低競爭下，調校良好的有鎖設計輕易就能勝過無鎖設計。它不代表無鎖程式碼自動更好。最關鍵的是，它不保證任何單一執行緒會完成；無鎖允許某個倒楣的執行緒被永久飢餓（starvation），不斷重試、不斷失敗，而它的鄰居們持續成功。這份保證只說「總有某人」在前進。那個更強的「每個執行緒」承諾叫做等待無關（wait-freedom），是另一個更難達成的性質。