鎖？還是不鎖？

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

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

基於鎖定的機制

程式語言中多半會提供鎖定機制，像是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實作，同時瞭解底層實作機制的優缺點，並進行測試，看看實際上是否真能增加效能。