函式式真的免疫競態條件嗎#

第 1 章說過：函式式程式不會有並行更新的問題——因為它根本不更新。沒有更新就沒有 race condition，因此多執行緒之間互不干擾……理論上。

這個說法雖讓人放心，但不完全正確。本章要證明：即便完全採用函式式風格，多執行緒程式仍可能出現 race condition。

範例：1960 年代的電話呼叫#

當時打電話的事件序列大致如下：

  1. Bob 拿起聽筒（off-hook）
  2. 電信公司（telco）送出撥號音
  3. Bob 撥 Alice 的號碼
  4. telco 對 Alice 的電話送出響鈴電壓，對 Bob 送出回鈴音
  5. Alice 拿起聽筒
  6. telco 把 Bob 與 Alice 連通
  7. Alice 說「Hello」

Figure 15.1: 一通電話的訊息序列圖

1960 年代的 telephony 用語：

  • off-hook：拿起聽筒，等價於通知 telco 你想用電話
  • dial tone：撥號音，代表 telco 準備好接收號碼
  • ringback：回鈴音，當被叫方響鈴時讓主叫者聽到
  • rotary dial：早期電話的轉盤式撥號

整個情境涉及三個有限狀態機：Bob、Alice、telco。Bob 與 Alice 各自跑一份 User 狀態機，telco 則跑 Telco 狀態機。

Figure 15.2: User 狀態機

Figure 15.3: Telco 狀態機

把狀態機寫進 Clojure#

(def user-sm
  {:idle    {:call       [:calling caller-off-hook]
             :ring       [:waiting-for-connection callee-off-hook]
             :disconnect [:idle nil]}
   :calling {:dialtone   [:dialing dial]}
   :dialing {:ringback   [:waiting-for-connection nil]}
   :waiting-for-connection {:connected [:talking talk]}
   :talking {:disconnect [:idle nil]}})

(def telco-sm
  {:idle              {:caller-off-hook [:waiting-for-dial dialtone]
                       :hangup          [:idle nil]}
   :waiting-for-dial  {:dial            [:waiting-for-answer ring]}
   :waiting-for-answer {:callee-off-hook [:waiting-for-hangup connect]}
   :waiting-for-hangup {:hangup [:idle disconnect]}})

每個狀態機就是一個雙層 hash map：

  • 外層的鍵：當下狀態
  • 內層的鍵：事件
  • 值：[新狀態 動作函式]

例：user-sm 在 :idle 收到 :call → 轉到 :calling 並執行 caller-off-hook。

通用 transition 函式#

(defn transition [machine-agent event event-data]
  (swap! log conj (str (:name machine-agent) "<-" event))
  (let [state  (:state machine-agent)
        sm     (:machine machine-agent)
        result (get-in sm [state event])]
    (if (nil? result)
      (do
        (swap! log conj "TILT!")
        machine-agent)
      (do
        (when (second result)
          ((second result) machine-agent event-data))
        (assoc machine-agent :state (first result))))))

get-in 從巢狀 map 取值；(get-in {:a {:b 2}} [:a :b]) 得到 2。

注意 transition 接受 machine-agent 並回傳更新後的它——這正是 Clojure 的 agent STM 工具所要的形態。

agent：序列化所有更新#

(defn make-user-agent [name]
  (agent {:state :idle :name name :machine user-sm}))

(defn make-telco-agent [name]
  (agent {:state :idle :name name :machine telco-sm}))

agent 接受一個資料結構，將所有對它的更新序列化執行——徹底消除並行更新問題。

對 agent 送事件：

(send caller transition :call [telco caller callee])

send 立即返回，transition 函式被排進 agent 自己的執行緒佇列。

動作函式們#

(defn caller-off-hook [sm-agent [telco caller callee :as call-data]]
  (swap! log conj (str (:name @caller) " goes off hook"))
  (send telco transition :caller-off-hook call-data))

(defn dial [sm-agent [telco caller callee :as call-data]]
  (swap! log conj (str (:name @caller) " dials"))
  (send telco transition :dial call-data))

(defn ring [sm-agent [telco caller callee :as call-data]]
  (swap! log conj (str "telco rings " (:name @callee)))
  (send callee transition :ring call-data)
  (send caller transition :ringback call-data))

(defn connect [sm-agent [telco caller callee :as call-data]]
  (swap! log conj "telco connects")
  (send caller transition :connected call-data)
  (send callee transition :connected call-data))

(defn talk [sm-agent [telco caller callee :as call-data]]
  (swap! log conj (str (:name sm-agent) " talks."))
  (Thread/sleep 10)
  (swap! log conj (str (:name sm-agent) " hangs up"))
  (send telco transition :hangup call-data))

順利情境：Bob 打給 Alice#

(it "should make and receive call"
  (let [caller (make-user "Bob")
        callee (make-user "Alice")
        telco  (make-telco "telco")]
    (reset! log [])
    (send caller transition :call [telco caller callee])
    (Thread/sleep 100)
    (prn @log)
    (should= :idle (:state @caller))
    (should= :idle (:state @callee))
    (should= :idle (:state @telco))))

測試通過——三個狀態機在 100ms 內回到 idle。日誌顯示三條執行緒交錯運作：

"Bob<-:call" "Bob goes off hook"
"telco<-:caller-off-hook" "dialtone to Bob"
"Bob<-:dialtone" "Bob dials"
"telco<-:dial" "telco rings Alice"
"Alice<-:ring" "Alice goes off hook"
"Bob<-:ringback"
"telco<-:callee-off-hook" "telco connects"
"Bob<-:connected" "Bob talks"
"Alice<-:connected" "Alice talks"
"Bob hangs up" "Alice hangs up"
"telco<-:hangup" "disconnect"
"Alice<-:disconnect" "Bob<-:disconnect"
"telco<-:hangup"

agent 序列化各自的操作——所以每個 agent 的內部狀態變動是安全的。

沒有 race condition，對吧？……先別下結論。

真實電話系統的 race condition#

1960 年代的電話系統存在一種真實的 race condition——若你還在用市話，可能至今仍然存在。

Figure 15.4: 電話系統中的 race condition

情境：Bob 正打算打給 Alice、Alice 也正要打給 Bob：

  • telco 嘗試讓 Alice 的電話響鈴
  • 在響鈴音真的發出之前，Alice 已經拿起聽筒準備打電話
  • 從 telco 的視角看：「我讓電話響、Alice 接了起來」——它高高興興地把 Bob 與 Alice 連通
  • 但 Alice 此時在等撥號音；Bob 則納悶為什麼回鈴音消失了卻沒人說 hello

最可能的結果：兩個人都掛斷，沒人講到話。要不就上演「誰打給誰」的喜劇橋段。

用測試重現它#

(it "should race"
  (let [caller (make-user "Bob")
        callee (make-user "Alice")
        telco1 (make-telco "telco1")
        telco2 (make-telco "telco2")]
    (reset! log [])
    (send caller transition :call [telco1 caller callee])
    (send callee transition :call [telco2 callee caller])
    (Thread/sleep 100)
    (prn @log)
    (should= :idle (:state @caller))
    (should= :idle (:state @callee))
    (should= :idle (:state @telco1))
    (should= :idle (:state @telco2))))

加入第二個 telco 處理 Alice 打給 Bob 的呼叫——測試失敗了。100ms 後狀態機沒有回到 idle。日誌：

"Bob<-:call" "Bob goes off hook"
"telco1<-:caller-off-hook"
"Alice<-:call" "Alice goes off hook"
"telco2<-:caller-off-hook"
"dialtone to Bob"
"Bob<-:dialtone" "Bob dials"
"telco1<-:dial" "telco rings Alice"
"Bob<-:ringback"
"Alice<-:ring" "TILT!" ...

看到那個 TILT! 沒？我們的 transition 函式在收到非法事件時會記下 TILT。

Alice 此刻仍在 :calling 等待 :dialtone，根本不知道怎麼處理 :ring——這是不可能的轉移。

這次的視窗很窄，作者試了好幾次才成功重現。但只要有可能，就會發生。

結論#

即使沒有並行更新，race condition 仍然可能發生——只要存在多個交互的有限狀態機，就有機會讓它們互相錯失而失去同步。

函式式語言、Moore 定律與多核狂熱#

世紀之交時，Moore 定律的「時脈速度」面向死了——時脈撞到 3GHz 上限後就停了。為了提升吞吐量，硬體工程師開始往晶片上塞更多核心：雙核、四核 ⋯⋯ 人們開始擔心 32、64、128 核怎麼辦。

也就是在那個時間點，函式式語言開始走紅——大家相信：函式式程式不變更資料，多核操作可以自動且輕易地展開。

但 Moore 定律的「元件密度」面向也跟著死了。過去十多年我們的處理器停在 4 核左右（先別講超執行緒）；128 核處理器的恐慌消散，函式式編程的迫切感也跟著減弱。

而且，正如本章所示，那個推論本身就有瑕疵：可變變數的執行緒裡 race condition 也許更頻繁，但任何有並行有限狀態機的系統，都可能因為彼此失去同步而出現 race condition。

Backward GUI 設計模式 Forward