程式中總是有某些流程必須同時並行,多執行緒是解決問題的方案之一,然而,總充滿著許多負面之評。

其中,多半牽涉了資源共享而帶來的競爭與同步問題,開發者多半知道基本的互斥鎖定,不過那並非解決問題的唯一方式。

基於鎖定的機制

程式語言中多半會提供鎖定機制,像是Java在語言層面提供了synchronized,進入synchronized區域的執行緒,必須獲取物件上唯一的鎖定,未獲取鎖定的執行緒會被阻斷,直到前一執行緒釋放鎖定。為了減少其他執行緒的等待時間,synchronized可以只標示在方法內部,只會發生競爭問題的關鍵區塊,目的是只保護資料而非程式碼,以便盡可能地讓持有鎖定的執行緒越快釋放鎖定。

然而,就算可以將synchronized區域儘量縮小,在某些條件下,持有鎖定的執行緒在synchronized區域中,也會遇上一些阻斷操作,此時,為了能透過執行其他任務來掩蓋阻塞操作的事實,可以請執行緒等待並釋放鎖定,讓其他執行緒有機會取得鎖定並執行任務,在某個條件符合之後,再來通知先前等待的執行緒繼續執行,以Java來說,這可透過Object的wait()、notify()、notifyAll()機制來完成。

Java也在API層面提供了Lock實作,最基本的實作是可重入鎖定Reentrantlock,顧名思義,就是同一執行緒可以重複進入鎖定區域,synchronized本身其實也是可重入的,不過鎖定範圍局限於區塊範圍,不能跨方法、有彈性地進行鎖定或釋放鎖定,也無法計算重入次數。同一執行緒若執行了Reentrantlock的lock()數次,就要有對應的unlock()次數,才能釋放鎖定。

使用Reentrantlock時,一個常見的實作錯誤是,忘了或不正確地使用try......finally,lock()必須在放在try......finally之外,而unlock()必須放在finally中,前者是避免lock()失敗拋出例外時,不致於執行了unlock(),而後者保證在lock()之後,進一步執行try中的程式碼時,若發生了例外,一定會執行finally,釋放鎖定。

Condition是將Object的wait()、notify()等方法之作用,重構至個別的Condition實例,除了可用結合Lock,以便替代低階的wait()、notify()等方法之外,若某個物件本身必須有多個等待集合,就可以使用多個Condition實例來實作,依條件通知不同來等待集合中的執行緒(而不是全部的執行緒)。

鎖定的分離

在純函數式的語言中,並沒有鎖定的問題,因為資料本質上不會變動,而在命令式的語言中,必須得進行鎖定的原因就在於,共享的資料狀態是可變的,只使用一個鎖的問題在於,如果兩個執行緒單純都只是進行讀取的動作,其中一個執行緒仍無可避免地必須等待。

對於讀取多而寫入少的簡單場合,Copy-On-Write是個可用的策略,在讀取時不加鎖定,而在寫入時進行鎖定,此時會複製出一份資料,在複本上進行寫入的動作,最後才將參考指向複本,因此,讀取時會具有很高的效率,然而,寫入時會因為複製資料而有較大的開銷,另一個要考量的問題是,如果寫入資料的同時,有另一個執行緒正在執行讀取動作,那它可能讀取的是舊的資料。

如果要求資料的一致性,使用Read-Write-Lock是一個方式,以Java的ReentrantReadWriteLock實作為例,只要沒有任何寫入鎖定時,就可以取得讀取鎖定,而沒有任何讀取或寫入鎖定時,才可以取得寫入鎖定,然而,如果讀取執行緒很多,使用ReentrantReadWriteLock可能會使得寫入執行緒遭受飢餓(Starvation)問題,也就是寫入執行緒可能遲遲無法競爭到鎖定,而一直處於等待狀態。

一個折衷的方案是,讀取資料先不實際進行鎖定,後續在發現讀取資料發現不一致時才加以鎖定,這可以透過一個戳記(Stamp)來進行比對,以Java 8的StampedLock為例,呼叫tryOptimisticRead()並不會真的獲得鎖定,而是會得到一個戳記,這之後可以讀取資料,然後使用validate()驗證戳記是否相同,如果不同,表示資料被寫入過而不一致,此時可執行readLock()真正進行鎖定。

基本上,StampedLock類別是一種樂觀讀取(Optimistic Reading)實作,也就是若讀取執行緒很多,寫入執行緒甚少的情況下,可以樂觀地認為,寫入與讀取同時發生的機會甚少,因此不會悲觀地使用完全的讀取鎖定。

CAS與ABA

在多執行緒的場合,越是能減少鎖定的使用頻率與粒度,就越有可能減少對效能的影響。

另一方面,有人朝無鎖(Lock-free)的方向著手,其中Compare and Swap (CAS) 是著名且常見的無鎖演算,它的基本概念是,在一個原子(Atomic)操作過程中,比較目前實際值與一個舊值,如果相同,表示資料沒有變異,此時使用指定值更新資料,並告知操作是否成功,以維基百科〈Compare and swap〉條目的虛擬碼為例:

function cas(p : pointer to int, old : int, new : int) returns bool {
    if *p ≠ old { return false }
    *p ← new
    return true
}

現在許多處理器都提供了CAS在硬體上的支援,在Java中,java.util.concurrent.atomic提供了API上的實現,使用上的基本演算是,在一個迴圈中取得舊資料,試著使用CAS操作比較舊資料與設定新資料,若失敗就持續重試,以AtomicLongArray的getAndUpdate(int i, LongUnaryOperator updateFunction)實作為例:

long offset = checkedByteOffset(i);
long prev, next;
do {
        prev = getRaw(offset);
        next = updateFunction.applyAsLong(prev);
} while (!compareAndSetRaw(offset, prev, next));
return prev; 

實際上,compareAndSetRaw()使用了sun.misc.Unsafe的compareAndSwapLong(),它使用了CPU的CAS指令。在使用CAS時,有個著名的ABA問題,也就是某個執行緒讀取了數值A,此時另一執行緒將資料改為B而後又改回A,實際上資料變動過了,然而這時前一執行緒進行比較時發現資料仍是A,因此會繼續執行程式。

解決ABA的方式之一是使用戳記,當資料變化時改變戳記值(例如遞增),像是AtomicStampedReference的compareAndSet()就必須提供舊戳記與新戳記,只有在舊戳記與現有戳記相符下,才會傳回true。

善用高階API與進行測試

還有其他的鎖定機制,像是鎖定分離(Lock Stripping),可使用多個鎖來控制資料的不同部份,避免整塊資料鎖定,進一步地可實現多個寫入同時進行,而讀取時不需要鎖定,像是Java中的ConcurrentHashMap。

當然,認識歸認識,實際上,在實作相關程式碼的時候,還是有一定的複雜度,可以的話,應認清競爭的資源與程度,並且,懂得善用java.util.concurrent中CopyOnWriteArrayList、BlockingQueue、ConcurrentMap等高階API實作,同時瞭解底層實作機制的優缺點,並進行測試,看看實際上是否真能增加效能。

專欄作者

熱門新聞

Advertisement