Reader Writer Lock

Intent

Suppose we have a shared memory area with the basic constraints detailed above. It is possible to protect the shared data behind a mutual exclusion mutex, in which case no two threads can access the data at the same time. However, this solution is suboptimal, because it is possible that a reader R1 might have the lock, and then another reader R2 requests access. It would be foolish for R2 to wait until R1 was done before starting its own read operation; instead, R2 should start right away. This is the motivation for the Reader Writer Lock pattern.

Also known as

multiple readers/single-writer lock or multi-reader lock or push lock

Explanation

Wikipedia Says

In computer science, a readers–writer (RW) or shared-exclusive lock (also known as a multiple readers/single-writer lock or multi-reader lock or push lock) is a synchronization primitive that solves one of the readers–writers problems. An RW lock allows concurrent access for read-only operations, while write operations require exclusive access. This means that multiple threads can read the data in parallel but an exclusive lock is needed for writing or modifying data. When a writer is writing the data, all other writers or readers will be blocked until the writer is finished writing. A common use might be to control access to a data structure in memory that cannot be updated atomically and is invalid (and should not be read by another thread) until the update is complete.

Source code

This example use two mutex to demonstrate the concurrent access of multiple readers and writers.

Class Diagram

Class diagram of Reader Writer Lock Pattern

Step 1: Create Reader class, read when it acquired the read lock.
public class Reader implements Runnable {

  private static final Logger LOGGER = LoggerFactory.getLogger(Reader.class);

  private Lock readLock;

  private String name;
  
  private long readingTime;

  /**
   * Create new Reader
   * 
   * @param name - Name of the thread owning the reader
   * @param readLock - Lock for this reader
   * @param readingTime - amount of time (in milliseconds) for this reader to engage reading
   */
  public Reader(String name, Lock readLock, long readingTime) {
    this.name = name;
    this.readLock = readLock;
    this.readingTime = readingTime;
  }
  
  /**
   * Create new Reader who reads for 250ms
   * 
   * @param name - Name of the thread owning the reader
   * @param readLock - Lock for this reader
   */
  public Reader(String name, Lock readLock) {
    this(name, readLock, 250L);
  }

  @Override
  public void run() {
    readLock.lock();
    try {
      read();
    } catch (InterruptedException e) {
      LOGGER.info("InterruptedException when reading", e);
      Thread.currentThread().interrupt();
    } finally {
      readLock.unlock();
    }
  }

  /**
   * Simulate the read operation
   * 
   */
  public void read() throws InterruptedException {
    LOGGER.info("{} begin", name);
    Thread.sleep(readingTime);
    LOGGER.info("{} finish after reading {}ms", name, readingTime);
  }
}
Step .2: Writer class, write when it acquired the write lock.
public class Writer implements Runnable {

  private static final Logger LOGGER = LoggerFactory.getLogger(Writer.class);

  private Lock writeLock;

  private String name;
  
  private long writingTime;

  /**
   * Create new Writer who writes for 250ms
   * 
   * @param name - Name of the thread owning the writer
   * @param writeLock - Lock for this writer
   */
  public Writer(String name, Lock writeLock) {
    this(name, writeLock, 250L);
  }
  
  /**
   * Create new Writer
   * 
   * @param name - Name of the thread owning the writer
   * @param writeLock - Lock for this writer
   * @param writingTime - amount of time (in milliseconds) for this reader to engage writing
   */
  public Writer(String name, Lock writeLock, long writingTime) {
    this.name = name;
    this.writeLock = writeLock;
    this.writingTime = writingTime;
  }


  @Override
  public void run() {
    writeLock.lock();
    try {
      write();
    } catch (InterruptedException e) {
      LOGGER.info("InterruptedException when writing", e);
      Thread.currentThread().interrupt();
    } finally {
      writeLock.unlock();
    }
  }
  
  /**
   * Simulate the write operation
   */
  public void write() throws InterruptedException {
    LOGGER.info("{} begin", name);
    Thread.sleep(writingTime);
    LOGGER.info("{} finished after writing {}ms", name, writingTime);
  }
}
Step 3: Now it's time to  create ReaderWriterLock class responsible for controlling the access for reader or writer
Allows multiple readers to hold the lock at a same time, but if any writer holds the lock then readers wait. If reader holds the lock then writer waits. This lock is not fair.
public class ReaderWriterLock implements ReadWriteLock {
  
  private static final Logger LOGGER = LoggerFactory.getLogger(ReaderWriterLock.class);


  private Object readerMutex = new Object();

  private int currentReaderCount;

  /**
   * Global mutex is used to indicate that whether reader or writer    * gets the lock in the moment.
   * <p>
   * 1. When it contains the reference of {@link #readerLock}, it means that the lock     * is acquired by the reader, another
   * reader can also do the read operation concurrently. <br>
   * 2. When it contains the reference of reference of {@link #writerLock}, it means that     * the lock is acquired by the
   * writer exclusively, no more reader or writer can get the lock.
   * <p>
   * This is the most important field in this class to control the access for reader/writer.
   */
  private Set<Object> globalMutex = new HashSet<>();

  private ReadLock readerLock = new ReadLock();
  private WriteLock writerLock = new WriteLock();

  @Override
  public Lock readLock() {
    return readerLock;
  }

  @Override
  public Lock writeLock() {
    return writerLock;
  }

  /**
   * return true when globalMutex hold the reference of writerLock
   */
  private boolean doesWriterOwnThisLock() {
    return globalMutex.contains(writerLock);
  }

  /**
   * Nobody get the lock when globalMutex contains nothing
   * 
   */
  private boolean isLockFree() {
    return globalMutex.isEmpty();
  }

  /**
   * Reader Lock, can be access for more than one reader concurrently if no writer get the lock
   */
  private class ReadLock implements Lock {

    @Override
    public void lock() {
      synchronized (readerMutex) {
        currentReaderCount++;
        if (currentReaderCount == 1) {
          acquireForReaders();
        }
      }
    }

    /**
     * Acquire the globalMutex lock on behalf of current and future concurrent readers. Make sure no writers currently
     * owns the lock.
     */
    private void acquireForReaders() {
      // Try to get the globalMutex lock for the first reader
      synchronized (globalMutex) {
        // If the no one get the lock or the lock is locked by reader, just set the reference
        // to the globalMutex to indicate that the lock is locked by Reader.
        while (doesWriterOwnThisLock()) {
          try {
            globalMutex.wait();
          } catch (InterruptedException e) {
            LOGGER.info("InterruptedException while waiting for globalMutex in acquireForReaders", e);
            Thread.currentThread().interrupt();
          }
        }
        globalMutex.add(this);
      }
    }

    @Override
    public void unlock() {

      synchronized (readerMutex) {
        currentReaderCount--;
        // Release the lock only when it is the last reader, it is ensure that the lock is released
        // when all reader is completely.
        if (currentReaderCount == 0) {
          synchronized (globalMutex) {
            // Notify the waiter, mostly the writer
            globalMutex.remove(this);
            globalMutex.notifyAll();
          }
        }
      }

    }

    @Override
    public void lockInterruptibly() throws InterruptedException {
      throw new UnsupportedOperationException();
    }

    @Override
    public boolean tryLock() {
      throw new UnsupportedOperationException();
    }

    @Override
    public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
      throw new UnsupportedOperationException();
    }

    @Override
    public Condition newCondition() {
      throw new UnsupportedOperationException();
    }
  }

  /**
   * Writer Lock, can only be accessed by one writer concurrently
   */
  private class WriteLock implements Lock {

    @Override
    public void lock() {

      synchronized (globalMutex) {

        // Wait until the lock is free.
        while (!isLockFree()) {
          try {
            globalMutex.wait();
          } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
          }
        }
        // When the lock is free, acquire it by placing an entry in globalMutex
        globalMutex.add(this);
      }
    }

    @Override
    public void unlock() {

      synchronized (globalMutex) {
        globalMutex.remove(this);
        // Notify the waiter, other writer or reader
        globalMutex.notifyAll();
      }
    }

    @Override
    public void lockInterruptibly() throws InterruptedException {
      throw new UnsupportedOperationException();
    }

    @Override
    public boolean tryLock() {
      throw new UnsupportedOperationException();
    }

    @Override
    public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
      throw new UnsupportedOperationException();
    }

    @Override
    public Condition newCondition() {
      throw new UnsupportedOperationException();
    }
  }

}
Step 3: let's test this design pattern.
public class ReaderWriterLockDemo {

  private static final Logger LOGGER = LoggerFactory.getLogger(App.class);

  /**
   * Program entry point
   * 
   * @param args command line args
   */
  public static void main(String[] args) {

    ExecutorService executeService = Executors.newFixedThreadPool(10);
    ReaderWriterLock lock = new ReaderWriterLock();
    
    // Start writers
    IntStream.range(0, 5)
        .forEach(i -> executeService.submit(new Writer("Writer " + i, lock.writeLock(), 
            ThreadLocalRandom.current().nextLong(5000))));
    LOGGER.info("Writers added...");

    // Start readers
    IntStream.range(0, 5)
        .forEach(i -> executeService.submit(new Reader("Reader " + i, lock.readLock(), 
            ThreadLocalRandom.current().nextLong(10))));
    LOGGER.info("Readers added...");
    
    try {
      Thread.sleep(5000L);
    } catch (InterruptedException e) {
      LOGGER.error("Error sleeping before adding more readers", e);
      Thread.currentThread().interrupt();
    }

    // Start readers
    IntStream.range(6, 10)
        .forEach(i -> executeService.submit(new Reader("Reader " + i, lock.readLock(), 
            ThreadLocalRandom.current().nextLong(10))));
    LOGGER.info("More readers added...");   

    // write operations are exclusive.
    executeService.shutdown();
    try {
      executeService.awaitTermination(5, TimeUnit.SECONDS);
    } catch (InterruptedException e) {
      LOGGER.error("Error waiting for ExecutorService shutdown", e);
      Thread.currentThread().interrupt();
    }

  }

}

Applicability

Application need to increase the performance of resource synchronize for multiple thread, in particularly there are mixed read/write operations.

Real world examples

Related patterns

Comments