行程同步與臨界區間問題

競爭條件(race condition)

想像兩個室友,各自瞄了一眼共用的購物清單,兩人都看到沒有牛奶了,於是兩人都跑出去買牛奶。結果你家多了兩盒牛奶。兩個人的判斷其實都沒錯;問題在於他們在重疊的時間裡,依據同一份共用資訊各自行動,而最終結果取決於他們的動作恰好怎麼交錯。程式裡的競爭條件就是同一類錯誤:兩條以上的執行緒在重疊的時間裡碰觸共用資料,而你得到的答案,取決於它們的步驟恰好以什麼樣不可預測的順序執行。

來看經典例子。共用變數 count 的值是 5,兩條執行緒各執行一次 count = count + 1。你會以為結果是 7。但 count = count + 1 並不是一個不可分割的動作;CPU 把它拆成好幾步:把 count 讀進暫存器(讀到 5),加 1(得到 6),再把暫存器寫回 count(存入 6)。如果執行緒 A 讀到 5,接著執行緒 B 在 A 寫回之前也讀到 5,兩者都算出 6、都存入 6,於是有一次更新被悄悄丟失了。最終值是 6,不是 7。同樣這兩條執行緒跑一千次,通常都給 7——偶爾才給一次 6。這種間歇性、與順序有關的錯誤,正是競爭條件的招牌。

競爭條件之所以重要,是因為它真實、常見,而且極難抓。它躲在看起來明顯正確的程式碼背後,只在特定時序下才現身,而且常常一加上 print 敘述就消失了(因為那改變了時序)。修正之道絕不是寄望那個壞的交錯不會發生;而是用其他手段讓危險的那段程式對其他執行緒而言不可分割——一把鎖、一個原子指令,或更高階的同步構造。整個行程同步領域的存在,就是為了馴服競爭條件。

兩條執行緒各對一個從 0 開始的共用計數器做 count++ 一萬次。你預期得到 20000。在多核心機器上不做同步地跑,你常常會得到一個較小、而且每次不同的數字,例如 18742——每一筆丟失的更新,就是兩條執行緒互相踩到的一次累加。

count++ 是讀取、相加、寫回三個步驟,所以兩條執行緒可能丟失一次更新。

一個「重現不出來」的競爭條件並沒有消失,只是在你的硬體上很罕見而已。不同的時序——機器忙碌、核心更多、編譯器改版——都可能讓它在通過所有測試後,於正式環境中突然出現。

又称
data race競態資料競爭