Read-Write-Lock

January 13, 2022

如果有個資料,可能同時間會有許多執行緒對它進行讀取與寫入,你可能要注意資料的同步問題,簡單的方式是,若有執行緒正在讀或寫,就鎖定物件,其他執行緒這時想讀或寫,就必須等待,然而,這種完全的鎖定,效率上比較不佳,特別是寫入少而讀取多的情況。

讀寫鎖

若有執行緒正在讀取物件狀態,由於沒有變更狀態,其他執行緒若也是讀取,可以不用鎖定物件,這時只要針對寫入執行緒鎖定就可以了;若有執行緒正在寫入,可以鎖定物件,其他執行緒必須等待寫入完成,才能取得讀取鎖定。

看似單純,不過在讀取時,由於不鎖定,也就會有許多執行緒正在讀取的可能性,這時就必須記錄讀取執行緒的數量;另外,為了避免寫入者飢餓,因為有過多讀取執行緒,造成寫入執行緒遲遲無法取得鎖定,你可能得考慮寫入執行緒優先取得鎖定的問題。

將這些任務考量進去,會構成複雜的鎖定邏輯,比較好的方式是,設計一個專門管理鎖定的物件,由它來負責讀寫的鎖定與解除問題:

public void readData() {
    lock.readLock();
    doRead();
    lock.readUnLock();
}

public void writeData() {
    lock.writeLock();
    doWrite();
    lock.writeUnLock();
}

lock 會是個專門管理鎖定的物件,readLockwriteLock 等方法的實現概念可能像是:

private boolean writerFirst = true; // 寫入優先
 
public synchronized void readLock() throws InterruptedException{
    while(writingWriters > 0 || (writerFirst && waitingWriters > 0)) {
        wait();
    }

    readingReaders++;
}
 
public synchronized void readUnLock() {
    readingReaders--;
    writerFirst = true;
    notifyAll();
}
 
public synchronized void writeLock() throws InterruptedException {
    waitingWriters++

    while(readingReaders > 0 || writingWriters > 0) {
        wait();
    }

    waitingWriters--;
    writingWriters++;
}
 
public synchronized void writeUnLock() {
    writingWriters--;
    writerFirst = false;
    notifyAll();
}

其中 writerFirst 是寫入優先的旗標,目的是在有寫入執行緒等待的話,在解除鎖定時,可以優先由寫入執行緒取得鎖定,不過缺點就是寫入的動作頻繁時,讀取者必須等待機率增多;相反地若設為讀取優先,讀取的回應性會增高,資料更新機會下降。

Java 的 ReadWriteLock

可以看到,讀寫鎖的需求複雜,實作上更複雜,可以的話,尋找程式庫的方案,詳細瞭解方案是為了解決哪些讀寫鎖定需求,才是務實的做法,甚至可以察覺到需求中未曾考量的細節。

例如,Java 標準 API 的 ReadWriteLock 介面定義了讀取鎖定與寫入鎖定行為,可以使用 readLockwriteLock 方法傳回 Lock 實作物件,可以依需求取得不同的讀寫鎖定實作物件。

例如,ReentrantReadWriteLockReadWriteLock 介面的主要實作類別,readLock 方法會傳回 ReentrantReadWriteLock.ReadLock 實例,writeLock 方法會傳回 ReentrantReadWriteLock.WriteLock 實例。

ReentrantReadWriteLock.ReadLock 實作了 Lock 介面,呼叫其 lock 方法時,若沒有 ReentrantReadWriteLock.WriteLock 實例呼叫過 lock 方法,也就是沒有任何寫入鎖定時,才能取得讀取鎖定。

ReentrantReadWriteLock.WriteLock 實作了 Lock 介面,呼叫其 lock 方法時,若沒有 ReentrantReadWriteLock.ReadLockReentrantReadWriteLock.WriteLock 實例呼叫過 lock 方法,也就是沒有任何讀取或寫入鎖定時,才能取得寫入鎖定。

來看看一個實際應用的例子,針對讀取多而寫入少,想增加讀取效率的情況:

import java.util.Arrays;
import java.util.concurrent.locks.*;

public class ArrayList<E> {
    private ReadWriteLock lock = new ReentrantReadWriteLock();
    private Object[] elems;
    private int next;
   
    public ArrayList(int capacity) {
        elems = new Object[capacity];
    }

    public ArrayList() {
        this(16);
    }

    public void add(E elem) {
        lock.writeLock().lock();
        try {
            if(next == elems.length) {
                elems = Arrays.copyOf(elems, elems.length * 2);
            }
            elems[next++] = elem;
        } finally {
            lock.writeLock().unlock();
        }
    }
    
    public E get(int index) {
        lock.readLock().lock();
        try {
            return (E) elems[index];
        } finally {
            lock.readLock().unlock();
        }
    }
    
    public int size() {
        lock.readLock().lock();
        try {
            return next;
        } finally {
            lock.readLock().unlock();
        }
    }
}