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:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
ScalableRWLock() Default constructor

Method Summary

Modifier and Type	Method and Description
void	exclusiveLock() Acquires the write lock.
boolean	exclusiveTryLock() Acquires the write lock only if it is not held by another thread at the time of invocation.
boolean	exclusiveTryLockNanos(long nanosTimeout) Acquires the write lock if it is not held by another thread within the given waiting time.
void	exclusiveUnlock() Attempts to release the write lock.
Lock	readLock()
protected void	removeState(AtomicInteger state) This function should be called only from ReadersEntry.finalize()
void	sharedLock() Acquires the read lock.
boolean	sharedTryLock() Acquires the read lock only if the write lock is not held by another thread at the time of invocation.
boolean	sharedTryLockNanos(long nanosTimeout) Acquires the read lock if the write lock is not held by another thread within the given waiting time.
void	sharedUnlock() Attempts to release the read lock.
Lock	writeLock()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ScalableRWLock

public ScalableRWLock()

Default constructor

Method Detail

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