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