第一次看到“Dekker算法”這個名字時我正被并發(fā)編程的互斥問題折騰得頭疼。現(xiàn)代硬件上想實現(xiàn)線程互斥最省事的辦法是lock xchg或者std::atomic幾行代碼就能搞定。但問題來了——如果一臺機器沒有任何原子指令、沒有鎖前綴只有對內(nèi)存的普通讀寫你還能不能讓兩個線程老老實實地排隊進臨界區(qū)Dekker算法就是這個問題的一個經(jīng)典答案它只用共享變量和順序邏輯就在軟件層面實現(xiàn)了雙線程互斥。這篇文章會拆解它的完整推導(dǎo)過程、正確性論證以及它放到現(xiàn)代CPU上會遭遇什么。無論你是并發(fā)編程初學(xué)者、面試準備者還是在嵌入式裸環(huán)境里寫多任務(wù)的人這份純軟件互斥的思路都值得吃透。1. 為什么都上原子指令了還要研究“僅用軟件”的互斥1.1 硬件原子指令把互斥變得太容易現(xiàn)代處理器幾乎都對互斥開了綠燈。xchg、cmpxchg、lock前綴再加上編譯器提供的atomic語義隨便擺弄幾下就能守住臨界區(qū)。原因在于硬件設(shè)計者為并發(fā)專門造了原語一條指令從讀取到寫入的整個過程在總線上不可分割其他核心要么看到操作前要么看到操作后不存在中間狀態(tài)。我剛?cè)腴T時也覺得既然有這些方便的指令為什么還要自我折磨去研究一個幾百行都未必寫得對的純軟件算法后來在某高校的一次課程設(shè)計里我需要在一個只有共享RAM、沒有特殊同步指令的模擬多核環(huán)境里實現(xiàn)協(xié)作式多線程才意識到硬件不支持原子操作這個假設(shè)真實存在。更不要說是否能掌握這種無原語條件下的互斥構(gòu)造能力本身也是理解現(xiàn)代并發(fā)原語價值的標尺。1.2 純軟件互斥的適用場景有人會問都21世紀了哪里還有沒有原子指令的機器這問題并不空想。早期多處理器系統(tǒng)確實沒有鎖指令很多嵌入式MCU的DMA和主核之間共享緩沖區(qū)時也只有普通讀寫有些教學(xué)用的軟核處理器干脆不實現(xiàn)原子指令。在這些場景里想在邏輯上保證同一時刻只有一個執(zhí)行流訪問共享資源就只能靠算法層面的互相謙讓。更現(xiàn)實的意義是思維訓(xùn)練。原子指令是硬件替你兜底而純軟件互斥迫使你直視并發(fā)最本質(zhì)的問題兩個執(zhí)行流看到的共享變量可能不是同一份、變量與變量之間的可見性順序可能顛三倒四。把這種思維練扎實了再看lock前綴到底幫你解決了哪幾個問題才會有原來如此的感覺。2. 熱身失敗兩個看似正確卻翻車的經(jīng)典設(shè)計2.1 方案一flag數(shù)組——兩人同時“闖關(guān)”我們先把問題限定為兩個線程共享一個資源每個線程的代碼分為entry進入?yún)^(qū)、critical臨界區(qū)、exit退出區(qū)。最直覺的設(shè)計是每個線程用一個布爾變量表達我想進。// 共享變量 volatile int flag[2] {0, 0}; // flag[i]1 表示線程i想進臨界區(qū) // 線程0 flag[0] 1; while (flag[1] 1) { // 忙等 } // 臨界區(qū) critical_section(); flag[0] 0; // 線程1 flag[1] 1; while (flag[0] 1) { // 忙等 } critical_section(); flag[1] 0;表面上每個線程進臨界區(qū)前都會看一眼對方是否也想進對方想進就等著。問題出在先置flag再檢查這個順序執(zhí)行的假設(shè)上線程0執(zhí)行完flag[0] 1后線程1恰好也執(zhí)行完flag[1] 1。此時兩邊都看到對方flag為1于是雙雙在while里轉(zhuǎn)圈——死鎖?；蛘吒愕男蛄袃蓚€線程都在檢查時看到對方flag為0同時沖進臨界區(qū)互斥直接失敗。這個版本的病根在于flag只表達了我還愿不愿意進沒有解決如果兩個人都想進誰該讓這個裁定問題。兩個人都互不相讓結(jié)局要么一起擠進去要么一起堵在門口。2.2 方案二謙讓令牌turn——不撞了但會餓死既然各自表達意愿會陷入僵持另一個直覺是引入一個輪流令牌共享變量turn表示當(dāng)前輪到誰。只有拿到令牌的線程才能進。volatile int turn 0; // 線程0 while (turn ! 0) { // 謙讓等待 } critical_section(); turn 1; // 線程1 while (turn ! 1) { // 謙讓等待 } critical_section(); turn 0;這個方案絕對不會兩個同時進因為turn只有一個值條件判斷保證了唯一性。但禿鷲也來了假設(shè)線程0進了臨界區(qū)退出時把turn寫成1然后線程0又立刻想要再次進入。它會在while (turn ! 0)里等待——可是令牌已經(jīng)在1手里了線程1如果因為任何原因比如還沒跑到或者被更高優(yōu)先級任務(wù)搶占遲遲不執(zhí)行那么線程0哪怕不需要訪問任何資源也只能干瞪眼。更極致的情形線程1永久停擺線程0也永久進不了臨界區(qū)。這暴露了絕對謙讓的缺陷它把前進的權(quán)利完全交給了對方自己毫無主動權(quán)?；コ庑越鉀Q了但無死鎖和無饑餓敗得一塌糊涂。3. 組合拳flag和turn疊加出的Dekker算法3.1 核心直覺想進的意愿與爭議時的謙讓分開處理兩個失敗方案給了兩條深刻的教訓(xùn)flag方案解決的是表達意圖但缺少仲裁turn方案解決了仲裁卻讓渡了主動權(quán)。Dekker算法的精妙之處在于把兩者組合并且理清了各自職責(zé)——flag用來聲明我想進turn用來裁定當(dāng)兩個人同時想進時誰讓一讓。關(guān)鍵細節(jié)在于何時使用turn。只有在發(fā)現(xiàn)自己和對方都想進時才需要動用令牌決出勝負然后由輸?shù)哪欠街鲃映坊刈约旱膄lag等贏家完成后再把flag立起來重新嘗試。這不是簡單的輪流而是平時各自爭先、沖突時協(xié)商禮讓既避免了兩個人都橫沖直撞又不會因為某個線程退出而永久卡死。3.2 完整代碼與逐行拆解下面這份C語言風(fēng)格的代碼是我常用來教學(xué)的版本共享內(nèi)存模型下可直接映射到大多數(shù)語言volatile int flag[2] {0, 0}; volatile int turn 0; // 0或1表示當(dāng)前爭議偏向讓誰 void thread_0(void) { while (1) { flag[0] 1; // 1. 表達想進 while (flag[1] 1) { // 2. 對方也想進嗎 if (turn ! 0) { // 3. 若輪到對方優(yōu)先 flag[0] 0; // 4. 我暫時撤出競爭 while (turn ! 0) { // 5. 等令牌輪轉(zhuǎn)回來 // 自旋 } flag[0] 1; // 6. 重新表達想進 } } // 7. 此時安全進入臨界區(qū) critical_section(); turn 1; // 8. 退出時把優(yōu)先權(quán)讓給線程1 flag[0] 0; // 9. 清除自己的意愿標志 // 10. 剩余區(qū) } } void thread_1(void) { while (1) { flag[1] 1; while (flag[0] 1) { if (turn ! 1) { flag[1] 0; while (turn ! 1) { // 自旋 } flag[1] 1; } } critical_section(); turn 0; flag[1] 0; } }逐步解釋這個代碼是怎么動的第1步線程0先把flag[0]設(shè)為1宣告自己即將使用資源。這是表達意愿。第2步它檢查線程1的flag。如果線程1不想進那沒有任何競爭者線程0直接進入臨界區(qū)。如果兩個線程同時想進while (flag[1] 1)成立進入內(nèi)部協(xié)商。此時看turn——這是全局的仲裁者。若turn 0說明這輪爭議偏向線程0線程1那邊在類似邏輯中會主動撤出線程0不必讓位繼續(xù)自我旋轉(zhuǎn)直到對方flag變0。若turn ! 0說明仲裁者認為線程1應(yīng)該優(yōu)先線程0立刻將自己的flag撤為0第4步然后死等turn變成0第5步。這等于告訴對方這輪你先我不搶。當(dāng)線程1用完資源把turn改回0后線程0重新立起flag第6步再次試著進入。對稱地線程1的代碼也遵循完全一致的控制流只是把索引和turn的判定反過來。兩者拼在一起就形成了沖突時按turn仲裁、非沖突時快速通過的節(jié)奏。3.3 四段式場景推演從執(zhí)行序列看懂互斥為了徹底理解這段代碼我建議你自己把以下四個場景在紙上推演一遍場景A無競爭線程0單獨進入。線程0將flag[0]置1看到flag[1]為0直接進入臨界區(qū)。不做任何不必要的謙讓。退出時設(shè)置turn1但此時線程1并不在等這個設(shè)置只影響未來可能的爭議。場景B完全同時發(fā)起。線程0和線程1幾乎同時把各自flag置1然后同時看到對方的flag也為1。此時若turn還是0線程1會發(fā)現(xiàn)turn ! 1于是主動撤下自己的flag并等待線程0發(fā)現(xiàn)turn 0不會撤flag只需等線程1的flag變0后即可進入。同理如果turn是1則角色互換。場景C線程0正在臨界區(qū)線程1到來。線程1立flag后看到線程0的flag是1又檢查turn。假設(shè)turn是0線程1會主動把flag撤下并等待。線程0正常退出、改turn、清flag線程1看到flag[0]0后重新立flag進入。互斥沒有被破壞。場景D線程0用完再次申請與線程1再次競爭。由于每次退出臨界區(qū)都會更新turn仲裁會交替偏向。這意味著沒有任何線程能依賴運氣連續(xù)搶到資源也決定了等待時間存在明確上界——這是Dekker算法無饑餓的關(guān)鍵。推演完這四個場景你會發(fā)現(xiàn)互斥的物理根源其實很樸素一個線程只有在對方flag為0對方不想要或?qū)Ψ街鲃映纷寣Ψ桨裦lag置0時才會進入臨界區(qū)。這兩條通道都不會和另一個線程的進入條件同時成立。4. 嚴謹論證互斥性、無死鎖、無饑餓是怎么成立的4.1 證明互斥盯住兩個線程最后一次寫flag口說無憑要證明互斥性我們引入一個簡單的不變量。假設(shè)兩個線程真的同時處于臨界區(qū)考慮它們各自進入臨界區(qū)前最后一次對flag數(shù)組的寫操作。線程0進入臨界區(qū)前必須越過兩關(guān)之一要么它看到flag[1]0要么它經(jīng)歷過撤讓再立起flag后看到flag[1]0。無論走那條路它在最后一次寫flag[0]1之后持續(xù)檢查flag[1]直到觀察到flag[1]0。線程1若也想進入臨界區(qū)那么它必然在某個時刻把flag[1]置為1并且在這個寫操作之后觀察flag[0]。如果兩個線程都在臨界區(qū)這兩個觀察并確認對方flag為0的事件必須先后發(fā)生。設(shè)線程0最后一次寫flag[0]的時刻是T0線程1最后一次寫flag[1]的時刻是T1。若T0早于T1那么線程0看到flag[1]0一定發(fā)生在T1之前而在這個觀察之后、進入臨界區(qū)之前線程1卻把flag[1]寫成了1。線程0卻已經(jīng)進入它不再檢查flag[1]這會破壞只能看到對方為0才進的邏輯嗎不會因為此時線程1還有后續(xù)檢查它會等到flag[0]0。線程0進入臨界區(qū)時flag[0]必定是1于是線程1一定會在while處自旋無法進入臨界區(qū)。反過來同理。兩個線程中至少有一個會被對方flag攔住矛盾消解互斥性得證。4.2 證明無死鎖與無饑餓turn是永遠不會丟失的令牌無死鎖的關(guān)注點是只要至少有一個線程還想進臨界區(qū)系統(tǒng)就不會永遠僵持。證明思路是觀察turn的流轉(zhuǎn)。turn只會在線程退出臨界區(qū)時修改且修改方向是0→1或1→0。如果兩個線程都在互相等待一定是雙方flag同時為1而turn屬于其中一方此時持有turn特權(quán)的一方應(yīng)當(dāng)進入臨界區(qū)另一方在等待。但持有turn的一方為何沒有進入因為它也卡在檢查對方flag的循環(huán)里——這只有在對方flag為1又不撤讓時才可能。而根據(jù)代碼turn偏向誰誰就不撤讓不偏向的一方才撤讓。所以持有turn的一方不會被對方攔住它要么已經(jīng)進入要么正在臨界區(qū)內(nèi)部。一旦持有turn的一方完成退出它會修改turn并把flag清零。另一方從等待turn輪轉(zhuǎn)中醒來重新立起flag發(fā)現(xiàn)自己已經(jīng)獲得仲裁權(quán)進入臨界區(qū)。整個鏈條中沒有一環(huán)會永久阻塞死鎖排除。無饑餓則依賴一個更強的性質(zhì)每個線程在兩次連續(xù)進入臨界區(qū)之間其對手至多進入有限次。原因是每次critical section結(jié)束后線程會把turn讓給對方自己下次再要進時必須等對方主動讓回。這形成了一個嚴格交替的次序即使某個線程非常熱切地不斷申請也只能每隔一輪進入一次。所以等待時間存在由對方臨界區(qū)執(zhí)行時間決定的上界不會出現(xiàn)某個線程永遠輪不到的饑餓。4.3 對照并發(fā)算法的四項基本要求我們可以把Dekker算法放到并發(fā)互斥算法的標準評價框架下核對要求Dekker算法的表現(xiàn)說明互斥滿足由觀察到對方flag為0才能進這一條件保證兩個線程不可能同時滿足無死鎖滿足turn一定偏向某一方持有turn的一方不會被granted阻塞無饑餓滿足turn在退出時強制輪轉(zhuǎn)等待時間有上界無忙等不滿足全部等待都是自旋循環(huán)CPU空轉(zhuǎn)最后一行是重點。Dekker算法是典型的忙等算法等待者不釋放CPU這在線程可搶占的系統(tǒng)里問題不大時間片會輪換但在協(xié)作式調(diào)度或單核優(yōu)先級系統(tǒng)中可能造成低優(yōu)先級線程餓死高優(yōu)先級線程之類的優(yōu)先級反轉(zhuǎn)問題。理解這一點才知道為什么現(xiàn)代系統(tǒng)寧可多花幾條原子指令也要提供真正能睡眠阻塞的鎖。5. 教科書代碼放在現(xiàn)代CPU上會翻車嗎5.1 亂序執(zhí)行、store buffer與內(nèi)存可見性把上面的C代碼原封不動搬進x86或者ARM的多核程序里你會發(fā)現(xiàn)它不一定工作。問題不在算法邏輯而在硬件模型?，F(xiàn)代CPU執(zhí)行普通讀寫指令時允許在不破壞單線程語義的前提下重排順序。編譯器也可能做類似的事情——把循環(huán)里的共享變量訪問優(yōu)化到寄存器里徹底繞開內(nèi)存。對于Dekker算法這種重排是致命的。比如線程0在邏輯上先寫flag[0]1再讀flag[1]但處理器可能先執(zhí)行讀操作或者寫操作雖然執(zhí)行了卻滯留在store buffer中其他核心暫時看不到。于是線程0可能讀到舊值flag[1]0而認為沒有競爭線程1也基于同樣的重排做了相同判斷——兩個線程一起進入臨界區(qū)教科書里的完美證明在現(xiàn)代硬件上瞬間失效。5.2 補救volatile、內(nèi)存屏障與原子類型那么如何讓Dekker算法在現(xiàn)代環(huán)境里真正可運行至少要做到三點使用原子類型把flag和turn都聲明為std::atomic并給所有讀寫指定恰當(dāng)?shù)膬?nèi)存序。memory_order_seq_cst最保守能同時阻止編譯器和CPU層面的重排。必要時顯式插入屏障在寫flag之后、檢查對方flag之前插入std::atomic_thread_fence(std::memory_order_seq_cst)在修改turn前也插入屏障避免讓出特權(quán)和清除意愿這兩個操作被顛倒。避免編譯器優(yōu)化掉自旋變量在純C語言里用volatile只是最低限度它保證變量被當(dāng)作內(nèi)存訪問而不是寄存器緩存但并不能保證內(nèi)存序。所以現(xiàn)代開發(fā)中靠volatile遠遠不夠必須用帶內(nèi)存序語義的原子操作。我實測過一個純volatile版Dekker在x86上的表現(xiàn)在大部分場景下好像沒出事因為x86由于強內(nèi)存模型store-load重排極少發(fā)生?？梢坏Q到ARM這類弱內(nèi)存模型的架構(gòu)或者開足編譯器優(yōu)化問題立刻暴露。這提醒我們算法證明建立在順序一致性模型上真實硬件不是一個級別的模型。5.3 生產(chǎn)環(huán)境里還要不要用Dekker就我的實際項目經(jīng)歷來看幾乎不會。有鎖指令和操作系統(tǒng)提供的互斥鎖為什么還要用一個自旋共享變量的算法Dekker的意義不在實用而在于它沖刷了互斥必須有硬件原語的固有認知并且為理解無鎖編程的memory ordering問題提供了極佳的起點。真正的實用價值可能出現(xiàn)在兩類地方一是不支持原子指令的極簡裸機環(huán)境雖然我很少碰到二是作為教學(xué)和面試題檢驗對并發(fā)缺陷的直覺——很多面試者能寫出flag方案但在追問兩個同時想進怎么辦時卡殼Dekker的協(xié)商撤讓設(shè)計正好是對這個盲區(qū)的補課。6. 從Dekker到我寫并發(fā)代碼的習(xí)慣改變6.1 只靠共享變量寫并發(fā)我學(xué)到的三個思維工具親手把Dekker從紙面推演到現(xiàn)代架構(gòu)上驗證之后我整理出了三條今后寫任何并發(fā)代碼都會套用的思維工具。第一不要假定操作順序。兩個線程各自的步驟在時間軸上可以隨意交錯任何我先執(zhí)行了A再執(zhí)行B所以對方肯定看到A的結(jié)果的推論都要重新檢查。Dekker之所以要那么復(fù)雜的撤讓邏輯正是因為不能假定兩個線程會按某個理想的先后次序運行。第二仲裁變量必須獨立于請求變量。flag表達我想進turn表達爭議時該誰讓。把這兩件事混在一個變量里幾乎所有互斥方案都會出問題。后來我設(shè)計其他共享狀態(tài)協(xié)議時也習(xí)慣性地按請求、授權(quán)、釋放三個角色分離變量職責(zé)清晰不易錯。第三等待必須要能讓自己脫身。flag方案的死鎖是因為等待者不主動改變自身狀態(tài)Dekker里等待的一方會撤下flag把自己的狀態(tài)變成我不參與了讓對方能順利通過。這個主動降低姿態(tài)以打破僵局的模式在解決分布式系統(tǒng)的活鎖問題時同樣適用。6.2 與同類算法的對照換個寫法為何更簡潔學(xué)習(xí)過程中我不可避免會拿它和更簡潔的同類方案做對比。Peterson算法同樣用flag和turn兩個共享變量但它的思想是既然無法在沖突瞬間決定誰進不如直接把入口讓給對方一次把仲裁放在競爭發(fā)生之前。而Dekker的思路是競爭發(fā)生時由turn裁定誰撤讓它更像兩個人走到窄門前發(fā)現(xiàn)同時到達時由門衛(wèi)turn指定誰退一步。后者邏輯鏈條更長需要處理撤讓-等待-重生三個狀態(tài)對理解者更不友好。坦率說如果你只是為了快速完成一個雙線程互斥任務(wù)我會建議先考慮Peterson這種更簡練的方案。但從追溯并發(fā)算法設(shè)計演進的角度Dekker提供了更完整的失敗-修正-驗證過程這也是它至今仍被眾多操作系統(tǒng)教材保留的原因。我在檢驗兩者的等價性時還意外發(fā)現(xiàn)一個細節(jié)Dekker的互斥性不依賴turn的初值——即使初始為0或1互斥都成立只是先讓誰進不同但Peterson的某個變體如果初值給錯或者更新位置不對會直接導(dǎo)致互斥失敗。這種初值敏感性差異在面試辨析題里很常見也提醒我寫并發(fā)算法時永遠要檢查初始化條件。6.3 一點小建議動手仿真而非只讀代碼最后分享一個我在學(xué)習(xí)Dekker時覺得最有效的方法找個支持共享內(nèi)存多線程的仿真環(huán)境比如在任意主流編程語言里開兩個線程按Dekker的步驟去實現(xiàn)并人為制造各種調(diào)度錯位。專門配合亂序、搶占、延時去運行它直到你能預(yù)判出每一個打印順序。很多人說看了證明就懂了但真正動手模擬各種交錯之后那種對變量狀態(tài)轉(zhuǎn)變的肌肉記憶是看任何博客都給不了的。并發(fā)算法的學(xué)習(xí)從來不是背結(jié)論而是把每一個狀態(tài)轉(zhuǎn)換都內(nèi)化成直覺。Dekker算法這個半個多世紀前的純軟件解法在今天仍能提供這種獨特而強烈的訓(xùn)練。