Package com.orientechnologies.common.concur.lock

Class ScalableRWLock

java.lang.Object
com.orientechnologies.common.concur.lock.ScalableRWLock
All Implemented Interfaces:
Serializable, ReadWriteLock
public class ScalableRWLock extends Object implements ReadWriteLock, Serializable

Scalable Read-Write Lock

A Read-Write Lock that is scalable with the number of threads doing Read. Uses a two-state-machine for the Readers, and averages two synchronized operations.
Although this mechanism was independently designed and implemented by the authors, the idea is very similar to the algorithm C-RW-WP described in this paper: NUMA-Aware Reader-Writer locks
Relative to the paper, there are two differences: The threads have no particular order, which means this implementation is not NUMA-aware; Threads attempting a read-lock for the first time are added to a list and removed when the thread terminates, following the mechanism described below. To manage the adding and removal of new Reader threads, we use a ConcurrentLinkedQueue instance named readersStateList containing all the references to ReadersEntry (Reader's states), which the Writer scans to determine if the Readers have completed or not. After a thread terminates, the finalize() of the associated ReaderEntry instance will be called, which will remove the Reader's state reference from the readersStateList, to avoid memory leaking. Advantages:
  • Implements java.util.concurrent.locks.ReadWriteLock
  • When there are very few Writes, the performance scales with the number of Reader threads
  • No need to call initialization/cleanup functions per thread
  • No limitation on the number of concurrent threads
Disadvantages:
  • Not Reentrant
  • Has Writer-Preference
  • Memory footprint increases with number of threads by sizeof(ReadersEntry) x O(N_threads)
  • Does not support lockInterruptibly()
  • Does not support newCondition()
For scenarios with few writes, the average case for sharedLock() is two synchronized calls: an AtomicInteger.set() on a cache line that is held in exclusive mode by the core where the current thread is running, and an AtomicLong.get() on a shared cache line.
This means that when doing several sequential calls of sharedLock()/unlock() on the same instance, the performance penalty will be small because the accessed variables will most likely be in L1/L2 cache.
Author:
Pedro Ramalhete, Andreia Correia
See Also:

  • Constructor Details

    • ScalableRWLock

      public ScalableRWLock()
      Default constructor

  • Method Details

    • readLock

      public Lock readLock()
      Specified by:
      readLock in interface ReadWriteLock

    • writeLock

      public Lock writeLock()
      Specified by:
      writeLock in interface ReadWriteLock

    • removeState

      protected void removeState(AtomicInteger state)
      This function should be called only from ReadersEntry.finalize()
      Parameters:
      state - The reader's state that we wish to remove from the ConcurrentLinkedQueue

    • sharedLock

      public void sharedLock()
      Acquires the read lock.

      Acquires the read lock if the write lock is not held by another thread and returns immediately.

      If the write lock is held by another thread then the current thread yields until the write lock is released.

    • sharedUnlock

      public void sharedUnlock()
      Attempts to release the read lock.

      If the current thread is the holder of this lock then the reentrantReaderCount is decremented. If the reentrantReaderCount is now zero then the lock is released. If the current thread is not the holder of this lock then IllegalMonitorStateException is thrown.

      Throws:
      IllegalMonitorStateException - if the current thread does not hold this lock.

    • exclusiveLock

      public void exclusiveLock()
      Acquires the write lock.

      Acquires the write lock if neither the read nor write lock are held by another thread and returns immediately, setting the write lock reentrantWriterCount to one.

      If the current thread already holds the write lock then the reentrantWriterCount is incremented by one and the method returns immediately.

      If the lock is held by another thread, then the current thread yields and lies dormant until the write lock has been acquired, at which time the reentrantWriterCount is set to one.

    • exclusiveUnlock

      public void exclusiveUnlock()
      Attempts to release the write lock.

      If the current thread is the holder of this lock then the reentrantWriterCount is decremented. If reentrantWriterCount is now zero then the lock is released. If the current thread is not the holder of this lock then IllegalMonitorStateException is thrown.

      Throws:
      IllegalMonitorStateException - if the current thread does not hold this lock.

    • sharedTryLock

      public boolean sharedTryLock()
      Acquires the read lock only if the write lock is not held by another thread at the time of invocation.

      Acquires the read lock if the write lock is not held by another thread and returns immediately with the value true.

      If the write lock is held by another thread then this method will return immediately with the value false.

      Returns:
      true if the read lock was acquired

    • sharedTryLockNanos

      public boolean sharedTryLockNanos(long nanosTimeout)
      Acquires the read lock if the write lock is not held by another thread within the given waiting time.

      Acquires the read lock if the write lock is not held by another thread and returns immediately with the value true.

      If the write lock is held by another thread then the current thread yields execution until one of two things happens:

      • The read lock is acquired by the current thread; or
      • The specified waiting time elapses.

      If the read lock is acquired then the value true is returned.

      Parameters:
      nanosTimeout - the time to wait for the read lock in nanoseconds
      Returns:
      true if the read lock was acquired

    • exclusiveTryLock

      public boolean exclusiveTryLock()
      Acquires the write lock only if it is not held by another thread at the time of invocation.

      Acquires the write lock if the write lock is not held by another thread and returns immediately with the value true if and only if no other thread is attempting a read lock, setting the write lock writerLoop count to one.

      If the current thread already holds this lock then the reentrantWriterCount count is incremented by one and the method returns true.

      If the write lock is held by another thread then this method will return immediately with the value false.

      Returns:
      true if the write lock was free and was acquired by the current thread, or the write lock was already held by the current thread; and false otherwise.

    • exclusiveTryLockNanos

      public boolean exclusiveTryLockNanos(long nanosTimeout) throws InterruptedException
      Acquires the write lock if it is not held by another thread within the given waiting time.

      Acquires the write lock if the write lock is not held by another thread and returns immediately with the value true if and only if no other thread is attempting a read lock, setting the write lock reentrantWriterCount to one. If another thread is attempting a read lock, this function may yield until the read lock is released.

      If the current thread already holds this lock then the reentrantWriterCount is incremented by one and the method returns true.

      If the write lock is held by another thread then the current thread yields and lies dormant until one of two things happens:

      • The write lock is acquired by the current thread; or
      • The specified waiting time elapses

      If the write lock is acquired then the value true is returned and the write lock reentrantWriterCount is set to one.

      Parameters:
      nanosTimeout - the time to wait for the write lock in nanoseconds
      Returns:
      true if the lock was free and was acquired by the current thread, or the write lock was already held by the current thread; and false if the waiting time elapsed before the lock could be acquired.
      Throws:
      InterruptedException