死結
活結(livelock)
還記得窄走廊裡那兩個有禮貌的人嗎?他們不斷互相讓道、又一起往同一邊閃、再一起閃回來,反反覆覆。他們非常「忙」——一直在動——卻始終擦不過彼此。這就是活結:行程不斷改變狀態、做著工作,卻沒有任何實際進展,只是沒完沒了地互相反應,而非前進。
活結是死結的「活躍版」表親。在真正的死結中,卡住的行程是被阻塞的——它們坐著等待、不耗用 CPU。在活結中,行程是可執行且忙碌的:每一個都針對其他行程反覆採取某種動作(退讓、重試、讓出、再試),但它們動作的組合永遠無法讓任何一個完成。常見起因是一個天真的死結避免嘗試:「若我拿不到第二把鎖,就放掉第一把再重試。」若兩個執行緒步調一致地這麼做,它們就會永遠以完美而徒勞的同步釋放、再重抓。解法通常是加入隨機性(隨機退避,如乙太網路的碰撞處理)或不對稱性,讓執行緒不再彼此鏡像。
這個誠實的區別很重要,因為活結會騙你。那些靠尋找被阻塞、等待中的行程來偵測死結的工具,會什麼異常都看不到——CPU 忙碌、執行緒在跑、程式「看起來還活著」。然而毫無有用的工作在進行,這可能比直白的死結更難診斷。活結也與飢餓相關卻不同:飢餓是某個特定行程持續被拒、而其他行程仍有進展;活結則是整個互動的群體空轉、全無進展。
兩個執行緒都用這條規則去抓兩把鎖:lock(first); 若 try_lock(second) 失敗,就 release(first) 再重試。在完美同步下兩者都抓到第一把、都在第二把失敗、都釋放,然後永遠迴圈——忙碌卻卡住。在重試前加入一點隨機延遲就能打破對稱。
活結:持續活動、零進展,因為執行緒不斷彼此鏡像。
活結不同於死結:死結的行程被阻塞、不耗 CPU,而活結的行程忙碌且可執行卻毫無進展——所以偵測被阻塞行程的死結偵測器會完全錯過它。
又稱
另見