免等待資料結構（wait-free data structure）

免等待是並行程式設計中最強的進展保證。一個資料結構若是免等待的，意思是：每個在它上面操作的執行緒，都保證能在自己有限的步數內完成操作，不論其他任何執行緒在做什麼——沒有任何執行緒會被別人無限期延遲。想像一台 ATM 承諾「不論銀行多忙，你總能在十步之內完成交易」。這是個強承諾：不只是銀行持續在服務某個人（那是無鎖），而是你本人永遠不會被晾在那裡等。

把進展保證從最弱到最強排一排會很有幫助。阻塞式的鎖最弱——若持鎖者被暫停，等待的所有人都卡住。無鎖更強：系統整體總在前進，但某個倒楣的個別執行緒可能永遠重試它的比較並交換迴圈，而別人不斷成功（於是即使系統有進展，它卻毫無進展）。免等待又更強：它藉由為每一個執行緒的工作設下上限，堵住那個漏洞。代價是設計難度。免等待演算法通常需要額外機制——例如協助機制（helping scheme），即將獲勝的執行緒會先把它即將覆蓋掉的操作替別人完成，使那個本會挨餓的執行緒的工作由他人代為做完。

為何要在意這個差別？在硬即時與安全攸關的系統裡，你需要的是每執行緒的最壞情況保證，而非僅僅每系統的保證：一個必須在期限內回應的控制迴圈，無法接受「也許你會一直重試」。那正是免等待發揮價值之處。誠實的提醒是，這個強保證要付代價：免等待結構設計與驗證都很複雜，而協助機制往往使它在常見的低競爭情況下，比更單純的無鎖、甚至鎖式版本還慢。經驗法則是：需要可擴展性與韌性時選無鎖，唯有當每執行緒的上限是真正的需求時才選免等待。