Parallel Programming (平行程式設計) 可能會帶來甚麼問題？

本篇原文（標題： Parallel Programming with Swift: What could possibly go wrong?）刊登於作者 Medium，由 Jan Olbrich 所著，並授權翻譯及轉載。

簡介

在之前的幾篇文章中，我們已經探討了幾種不同控制並行 (concurrency) 的方法。作業系統也提供了一些的低階方式，舉例來說，Apple 提供了相關的框架、或是其他像是經常在 JavaScript 中被使用的 Promises 概念。儘管有些陷阱我在之前的文章中已經提過，但我意識到我說得不夠詳細，因此，為了讓你們更充分理解這些概念，本篇文章中的某些部份會重複涵蓋到之前的內容。

這篇文章會講述不瞭解並行概念的話，有可能引致甚麼問題。讓我們開始吧！

原子操作 (Atomic)

原子操作是類似於資料庫中交易 (transaction) 的概念，當你想要寫入一個數值並且表現為單次操作，程式以 32 位元所編譯，若使用 int64_t 而沒有 atomic 操作，可能就會發生相當奇怪的行為。為什麼會這樣？讓我們深入其中一探究竟：

int64_t x = 0
Thread1:
x = 0xFFFF
Thread2:
x = 0xEEDD

進行非原子操作 (non-atomic operation) 可能會導致第一個執行緒開始寫入 x，但是因為我們在 32 位元的作業系統中工作，因此必須將寫入 x 的值分成兩批 0xFF。

當第二個執行緒決定在同一時間寫入 x，那麼就會發生下列操作流程的順序：

Thread1: part1
Thread2: part1
Thread2: part2
Thread1: part2

最後我們會得到：

x == 0xEEFF

那既不是 0xFFFF，也不是 0xEEDD。

使用原子操作來創造一個單次交易的情況，則會出現下列情況：

Thread1: part1
Thread1: part2
Thread2: part1
Thread2: part2

結果，x 是第二個執行緒所設定的數值。Swift 本身還沒有實現原子操作，已經有人提議把它加入到 Swift Evolution 之中，但目前你必須自己實作它。

最近我在修正一個錯誤，那錯誤是由兩個不同的執行緒寫入同一個陣列所導致的。還記得 Swift 中並行的錯誤處理 Operations 嗎？當中包含了一個很容易被忽略的錯誤。如果一組之中的兩個操作能夠同時平行執行和失敗，那會發生什麼事？這樣兩個操作就會同時嘗試寫入那錯誤的陣列，這將導致 Swift.Array 之中的「分配容量 (allocate capacity)」崩潰。為了要修正它，陣列必須保執執行緒安全 (threadsafe)。其中一個解決方法，就是同步陣列 (Synchronized Array)。但總體來說，你還是必須鎖定每個寫入權限。請不要誤會我的意思，讀取的操作也有可能失敗：

var messages: [Message] = []

func dispatch(_ message: Message) {
  messages.append(message)
  dispatchToPlugins()
}

func dispatchToPlugins() {
  while messages.count > 0 {
    for plugin in plugins {
      plugin.dispatch(message: messages[0]) 
    }
    messages.remove(at:0)
  }
}

Thread1:
dispatch(message1)

Thread2:
dispatch(message2)

在上面的情況中，我們不斷重覆一個陣列，並檢查長度不等於 0，然後在調度元素到插件後就刪除它。這個方式很容易會產生 “index out of range” 的異常。

記憶體屏障 (Memory Barriers)

CPU 是一項非凡的科技，特別是現在的 CPU 有著多個 Core 和智能編譯器，我們並不清楚程式碼會在那一顆 CPU 上執行。硬體甚至優化了我們的記憶體操作。簿記 (bookkeeping) 可以確保它們在此 Core 中按順序排列。不幸的是，這可能會導致一個 Core 看到記憶體更改時，順序與實作的順序不同。讓我舉一個簡單的例子：

//Processor #1:
while f == 0 {
  print x
}

//Processor #2:
x = 42
f = 1

你會預期這段程式碼會一直印出 42，因為程式碼是設置於 f 被設定為 false 並停止循環之前。在某些時候，可能會發生第二顆 CPU 看見記憶體以相反順序改變，所以先結束循環並印出數值，後來才發現新的數值是 42。我還沒有在 iOS 上看過這種情形，但不代表這情況不會發生，尤其是在這個越來越多 Core 的時代，你必須多留意這種低階的硬體陷阱。

那麼我們應該怎樣作出修正？Apple 就提供了記憶體屏障。基本上，這些指令是用來確保前一個記憶體操作結束後，才會開始執行下一個操作。這樣就能夠防止 CPU 將我們的程式碼最佳化，也因此程式的效能會稍微差一點。不過除非是高效能的系統，不然你應該不會察覺到當中的差異。

使用方法其實相當簡單，但要注意的是，這是一個作業系統的函式，而不是 Swift，所以 API 是來自 C 語言的。

OSMemoryBarrier() // from < libkern/OSAtomic.h >

上列的範例若使用記憶體屏障，看起來應該像是這樣：

//Processor #1:
while f == 0 {
  OSMemoryBarrier()
  print x
}

//Processor #2:
x = 42
OSMemoryBarrier()
f = 1

這樣我們的記憶體操作就會順序執行，我們不必再擔心硬體將記憶體重新排序所造成的副作用了。

競爭條件 (Race Conditions)

競爭條件是指多個執行緒試圖存取單個執行緒行為的情況。想像一下有兩個執行緒，其中一個計算並儲存結果至 x，另一個稍後開始執行（可能是不同的執行緒，例如：使用者互動），並將結果顯示出來：

var x = 100

func calculate() {
    var y = 0
    for i in 1...1000 {
        y += i
    }
    
    x = y
}

calculate()

print(x)

取決於這些執行緒的時間點，可能會出現一種情況：第二個執行序沒有將計算的結果輸出到螢幕上。相反，它還是保持之前的數值，這是我們預料之外的行為。

另一種情況是兩個不同的執行緒在寫入同一個陣列。假設我們讓第一個執行緒將 “Concurrency with Swift:” 的每一個字詞寫入到陣列，另一個執行緒同樣將 “What could possibly go wrong?” 寫入陣列。我們用相對簡單的方式來實現它：

func write(_ text: String) {
    let words = text.split(separator: " ")
    for word in words {
        title.append(String(word))
    }
}

write("Concurrency with Swift:") // Thread 1
write("What could possibly go wrong?") // Thread 2

我們可能會得到預料之外的行為，就是標題在陣列中被混合在一起：

“Concurrency with What could possibly Swift: go wrong?”

這不是我們所期望的結果，對吧？其實有幾種方式可以解決這情況：

var title : [String] = []
var lock = NSLock()

func write(_ text: String) {
    let words = text.split(separator: " ")
    lock.lock()
    for word in words {
        title.append(String(word))
        print(word)
    }
    lock.unlock()
}

另一種方式會使用到 Dispatch Queues 的技巧：

var title : [String] = []

func write(_ text: String) {
    let words = text.split(separator: " ")
    DispatchQueue.main.async {
        for word in words {
            title.append(String(word))
            print(word)
        }
    }
}

根據個人需要，選擇你認為適合的方式吧！一般而言，我會傾向於使用 Dispatch Queues，這個方法可以同事防止死鎖 (Deadlocks)。接下來，讓我們深入討論死鎖。

死鎖 (Deadlocks)

在之前的教學文章之中，我們已經討論過解決競爭條件不同的方法。假如我們使用到 Locks、Mutexes 或是 Semaphores 方法，就會導致另一個問題：死鎖。

死鎖是循環等待所造成的結果，第一個執行緒在等待第二個執行緒所持有的資源，而第二個執行緒又在等待第一個執行緒所持有的資源。

parallel programming_2

讓我舉一個簡單的例子，假設有一個銀行帳戶需要執行一項交易，這項交易被分為兩個部份：第一是提款、第二是存款。

程式碼看起來應該像這樣：

class Account: NSObject {
    var balance: Double
    var id: Int
    
    override init(id: Int, balance: Double) {
        self.id = id
        self.balance = balance
    }
    
    func withdraw(amount: Double) {
        balance -= amount
    }
    
    func deposit(amount: Double) {
        balance += amount
    }
}

let a = Account(id: 1, balance: 1000)
let b = Account(id: 2, balance: 300)

DispatchQueue.global(qos: .background).async {
    transfer(from: a, to: b, amount: 200)
}

DispatchQueue.global(qos: .background).async {
    transfer(from: b, to: a, amount: 200)
}

func transfer(from: Account, to: Account, amount: Double) {
    from.synchronized(lockObj: self) { () -> T in
        to.synchronized(lockObj: self) { () -> T in
            from.withdraw(amount: amount)
            to.deposit(amount: amount)
        }
    }
}

extension NSObject {
    func synchronized<T>(lockObj: AnyObject!, closure: () throws -> T) rethrows ->  T
    {
        objc_sync_enter(lockObj)
        defer {
            objc_sync_exit(lockObj)
        }
        
        return try closure()
    }
}

若沒有注意到交易過程中相互依賴的關係，就將會導致死鎖。

另一個的問題可以以「哲學家晚餐問題」來闡述，讓我們先看看維基百科的說明：

有五位哲學家圍坐在一張圓形餐桌旁，拿著一碗義大利麵，每個哲學家都必須交替思考和吃義大利麵，吃東西的時候，他們就停止思考，思考的時候也停止吃東西。每兩個哲學家之間有一隻餐叉，假設哲學家必須用兩隻餐叉吃東西。每支叉子同時只能由一位哲學家持有，因此只有當另一位哲學家沒有使用它時，哲學家才能使用它。在一位哲學家吃完之後，他們需要放下兩把叉子，以便叉子可提供他人使用。一個哲學家可以從他們的右邊或左邊的獲得叉子，但是在獲得兩個叉子之前不能開始進食。
假設義大利麵供求無限。

你可能會花許多時間來解決這個問題，但平常的解決辦法會是：

如果你的左邊有叉子就拿起它；
等待右邊的叉子，
2a. 如果右邊有叉子就拿起它，並開始吃義大利麵；
2b. 如果在一定的時間之後，右邊還是沒有叉子，將左手的叉子放下；
從頭再來一遍。

這未必一定有效，而且相當有可能造成死鎖。

活鎖 (Livelock)

死鎖的一個特別情況就是活鎖。死鎖是在等待資源被釋放，而活鎖就是多個執行緒在等待其他執行緒持有的資源，但是這些資源的狀態不斷改變，因此執行緒無法獲得任何進展。

在現實生活中，活鎖的情形可能會發生在小巷子裡：兩個人想要通往對方那一邊，出於禮貌的緣故，兩個人都往旁邊靠，卻恰巧站到同一側。他們嘗試靠往另一側，碰巧兩人都做了同樣的事情，所以再次堵住了對方的去路。這個情況有可能一直持續下去形成了一個活鎖，你可能也曾經有這樣的經驗。

嚴重爭用鎖 (Heavily Contended Locks)

另一個由鎖造成的問題就是嚴重爭用鎖。試想像有一個收費站，要處理的汽車太多，收費站的速度太慢，那麼就會造成塞車。同樣的情況也發生在鎖和執行緒，假如鎖嚴重被爭用，而同步的部份又執行得很緩慢，就會造成許多執行緒排入隊列卻不被執行，這將會影響你的程式效能。

執行緒耗盡 (Thread Starvation)

如同前文所述，執行緒可以有不同的優先權 (priority)。這一點相當有用，可以讓我們確保特定的任務能夠盡快完成。但是，如果我們將少數的任務設定為低優先權，同時將大多數的任務設置為高優先權，那會發生什麼事？那麼低優先權的執行緒將會被耗盡，因為它沒有執行時間，結果任務會花上很長的時間才能執行，甚至是永遠都不會被執行。

優先權倒置 (Priority Inversion)

如果上述的執行緒耗盡再加入鎖的機制，那麼情況會變得非常有趣。假設有一個低優先權的執行緒 3，它鎖定了一個資源。一個高優先權的執行緒 1 想要訪問此資源，所以它必須等待。如果還有一個優先權高於 3 的執行緒 2，就將會引來更大的災難。由於它的優先權高於 3，它將先被執行。如果這個執行緒 2 現在長時間運行，就將會用光所有 3 可以使用的資源。如此一來，3 就無法執行，而 1 及 2 就是將要執行緒，繼而使執行緒 1 耗盡。即使 1 的優先權高於 2，情況也是同樣。

parallel programming_1

過多的執行緒

討論了這麼多執行緒相關的議題，還有一件事非提不可，你未必會遇到這種情況，但它還是有可能發生的。每個執行緒的改變都是一個環境切換 (Context Switch)，記得我們這些開發人員經常抱怨切換任務（或是被人打斷），會降低我們的效率嗎？如果我們進行環境切換，CPU 就會發生類似的情況：所有預先載入的指令都必須刷新，而且短時間內無法做任何的命令預測 (Command Prediction)。

換句話說，當我們過度頻繁地切換執行緒會發生什麼事？CPU 將無法再預測任何事情，繼而降低效率。它變成只能執行目前的指令，然後等待下一個指令，這會導致更高的代價。

執行緒的基本原則就是不要過份使用，也就是「需要才用，越少越好。」

Swift 警告

最後還有一點需要注意，就算你正確做完所有步驟，並已經能夠完全控制同步、鎖、記憶體操作、和執行緒，Swift 編譯器也不保證程式碼的順序能夠保持一致。這可能會導致同步機制與你編寫的順序不符。

換句話說：「Swift 本身並不是 100% 執行緒安全的。」

如果你想確保並行性質（例如：使用 AudioUnits 時）是 100% 執行緒安全的，就可能要回到 Objective-C 的懷抱。

總結

如你所見，並行不是一個簡單的議題，有很多地方都可能會出錯；但同時，它也能夠有很大的幫助。善用好的工具！如果完全依靠自己寫程式碼，就很可能無法除錯，所以請慎選你的工具。

Apple 提供了一些用於並行的除錯工具，像是 Activity groups 和 Breadcrumbs，很可惜它們目前並不支援 Swift（雖然有相關軟體套件在做這件事）。

延引閱讀

本篇原文（標題： Parallel Programming with Swift: What could possibly go wrong?
）刊登於作者 Medium，由 Jan Olbrich 所著，並授權翻譯及轉載。

作者簡介：Jan Olbrich，一名 iOS 開發者，專注於質量和持續交付 (Continuous Delivery)。

譯者簡介：HengJay，iOS 初學者，閒暇之餘習慣透過線上 MOOC 資源學習新的技術，喜歡 Swift 平易近人的語法也喜歡狗狗，目前參與生醫領域相關應用的 App 開發，希望分享文章的同時也能持續精進自己的基礎。

LinkedIn: https://www.linkedin.com/in/hengjiewang/
Facebook: https://www.facebook.com/hengjie.wang