ReadWriteLock maintains a pair of associated locks behind it, one for read and one for write. Read locks can be concurrently acquired by multiple reader threads, as long as there are no writer threads. Write locks do not support this. Read-write locks, read-read can coexist, read-write cannot coexist, and write-write cannot coexist.
Since the implementation
If a thread wants to read a resource, no thread is writing to the resource and no thread is requesting a write to the resource.
public class ReadWriteLock {
private int readers = 0;
private int writers = 0;
private int writeRequests = 0;
public synchronized void lockRead(a) throws InterruptedException{
while(writers > 0 || writeRequests > 0){
wait();
}
readers++;
}
public synchronized void unlockRead(a){
readers--;
notifyAll();
}
public synchronized void lockWrite(a) throws InterruptedException{
writeRequests++;
while(readers > 0 || writers > 0){
wait();
}
writeRequests--;
writers++;
}
public synchronized void unlockWrite(a) throws InterruptedException{ writers--; notifyAll(); }}Copy the codeOne of the problems with a relatively simple read-write lock implementation is that if writes are frequent, the reader thread can starve. Note that in both lock release methods (unlockRead, unlockWrite), the notifyAll method is called instead of notify. To explain this, we can imagine the following scenario:
If a thread is waiting to acquire a read lock and another thread is waiting to acquire a write lock. If one of the threads waiting for a lock to be read is woken up by notify(), the woken up thread will block again because there are other threads that requested the lock (writeRequests>0). However, none of the threads waiting to write the lock wake up as if nothing had happened (signal loss). If notifyAll() is used, all threads are woken up to determine whether they can obtain the lock they requested.Copy the codeNotifyAll () has another advantage. If there are multiple reader threads waiting for the lock to be read and there are no threads waiting for the lock to be written, the unlockWrite() method is called, and all the reader threads waiting for the lock to be read will acquire the lock immediately instead of one at a time.
Read/write lock reentrant
The above code does not support readlock reentrant and blocks if a thread that already holds the write lock requests the write lock again. The reason is that there is already one writer thread — itself. Also, consider the following example:
- Thread# 1 acquires the read lock
- Thread# 2 requests a write lock, but because thread#1 holds the read lock, the write lock request is blocked
- Thread# 1 tries to request the read lock again, but since thread#2 is in the write lock state, trying to obtain the read lock again will be blocked
So the idea of reentrant read/write lock is:
- Saves and counts the current thread that acquired the read lock. If the current reader thread has acquired the read lock before, it will directly re-enter. Otherwise, if there is a writer thread or a writer thread is waiting for the lock, it will fail to acquire the read lock and need to wait
- Saves and counts the current thread that acquired the write lock. If there is no reader thread, or no writer thread, the write lock was acquired successfully. Or the same thread can acquire the write lock again.
ReentrantReadWriteLock
The class diagram
ReentrantReadWriteLock.Sync
Data structure:
// Read lock and write lock count constants
// The lock state is logically divided into two unsigned integers:
// The status indicates the exclusive(writer) lock.
// Shared (reader) lock
SHARED_SHIFT = 16; SHARED_SHIFT = 16; SHARED_SHIFT = 16
static final int SHARED_SHIFT = 16;
// 65536, binary: 10000000000000000
static final int SHARED_UNIT = (1 << SHARED_SHIFT);
/ / 65535
static final int MAX_COUNT = (1 << SHARED_SHIFT) - 1;
// 65535, binary: 111111111111111111
static final int EXCLUSIVE_MASK = (1 << SHARED_SHIFT) - 1;
// The first thread to acquire the read lock, that is, the thread that changes shared count from 0 to 1
private transient Thread firstReader = null;
private transient int firstReaderHoldCount;
// The last thread got the count of the read lock
private transient HoldCounter cachedHoldCounter;
// Count the number of reentrant locks held by the current thread
private transient ThreadLocalHoldCounter readHolds;
Copy the codeBuild ReentrantReadWriteLock. Will initialize the Sync operation
Sync() {
readHolds = new ThreadLocalHoldCounter();
setState(getState()); // Default is 0
}
Copy the codeUnfair locking
ReadLock (read)
Read Lock, to achieve the Lock interface, internal dependence on the IMPLEMENTATION of AQS Sync class.
/ / ReadLock class
// If the write lock is not acquired by another thread, return immediately; otherwise, block
public void lock(a) {
sync.acquireShared(1);
}
/ / AQS class
public final void acquireShared(int arg) {
if (tryAcquireShared(arg) < 0)
doAcquireShared(arg);
}
/ / ReentrantReadWriteLock. Sync class
// unused = 1
protected final int tryAcquireShared(int unused) {
/* * 1. If another thread acquires the write lock, it fails * 2. */
Thread current = Thread.currentThread();
int c = getState();
// exclusiveCount(c) => c & 1111111111111111(Sync.EXCLUSIVE_MASK)
// check whether another thread has acquired the write lock. Lock degradation: If the thread that acquired the write lock can acquire the read lock
if(exclusiveCount(c) ! =0&& getExclusiveOwnerThread() ! = current)return -1;
// sharedCount(c) => c >>> 16(sync.shared_shift)
int r = sharedCount(c);
/ / (2) the core
if(! readerShouldBlock() && r < MAX_COUNT && compareAndSetState(c, c + SHARED_UNIT)) {if (r == 0) {
firstReader = current;
firstReaderHoldCount = 1;
} else if (firstReader == current) {
firstReaderHoldCount++;
} else {
HoldCounter rh = cachedHoldCounter;
if (rh == null|| rh.tid ! = getThreadId(current)) cachedHoldCounter = rh = readHolds.get();else if (rh.count == 0)
readHolds.set(rh);
rh.count++;
}
return 1;
}
/ / 3.
return fullTryAcquireShared(current);
}
/ / NonfairSync class
final boolean readerShouldBlock(a) {
return apparentlyFirstQueuedIsExclusive();
}
/ / AQS class
// If the first node waiting in the queue (head does not count as waiting, because it represents the thread holding the lock) is a writer thread,
// The reader thread should be blocked. Objective To prevent writer thread from starvation
final boolean apparentlyFirstQueuedIsExclusive(a) {
// 1. Queue is not initialized
// 1.1 Read thread to acquire read lock, returns false
// 2. The queue is initialized
// 2.1 The queue currently has only one node head, returning false
// 2.2 Queue has more than one node head
2.2.1 The nextWaiter of the first waiting node is not in SHARED mode, return true
Node h, s;
return(h = head) ! =null&& (s = h.next) ! =null&&! s.isShared() && s.thread ! =null;
}
Copy the codeThe core logic in the above tryAcquireShared() method annotation (2) marked if() logic, we step by step to parse. If () judgment condition consists of three parts and is a && relation, that is, as long as one part is not satisfied, it will enter the logical code marked by comment ③.
- ! ReaderShouldBlock () the readerShouldBlock() method logic is explained in the code above. And notice that I’m inverting it.
- R < MAX_COUNT ReentrantReadWriteLock. Sync data structure of a class has said MAX_COUTN fields. The number of read threads cannot exceed 65535; otherwise, an error will be reported.
- CompareAndSetState (c, c + SHARED_UNIT) The c variable is the current state value. If the first reader thread comes in, c = 0, c + SHARED_UNIT = 65536. Because the high 16 bits represent shared reads, and count the number of read threads as C >>> 16. The reader thread acquires the lock and changes the state value to state += 65536.
When the above condition is met, it indicates that the thread has acquired the read lock, and the internal logic of if() determines the condition in three steps:
-
No thread has acquired the read lock, i.e
(getState() >>> SHARED_SHIFT) = 0 Copy the codeRecords the first thread to acquire the read lock and its reentrant count.
-
If the first step is not met, firstReader is the same thread as the current thread. If yes, firstReaderHoldCount is increased.
-
Otherwise, perform the following logic
HoldCounter rh = cachedHoldCounter; // Cache count of the current thread // Rh has not been initialized yet, i.e. no second thread comes in to acquire the read lock if (rh == null|| rh.tid ! = getThreadId(current))// Initialize cachedHoldCounter cachedHoldCounter = rh = readHolds.get(); else if (rh.count == 0) readHolds.set(rh); rh.count++; Copy the code
If the if() judgment of comment ② is not satisfied, i.e. the thread cannot acquire the read lock, or the maximum number of read threads has been reached, or the CAS has failed, then the method fullTryAcquireShared() in comment ③ is entered.
/ / ReentrantReadWriteLock. Sync class
final int fullTryAcquireShared(Thread current) {
HoldCounter rh = null;
/ / death cycle
for (;;) {
int c = getState();
// Whether a writer thread has acquired the multi-write lock. Lock down
if(exclusiveCount(c) ! =0) {
if(getExclusiveOwnerThread() ! = current)// if a writer thread acquires the write lock, the other thread acquires the read lock and returns -1 to queue
return -1;
} else if (readerShouldBlock()) { // No write lock (write lock may be released)
// head(read thread) -> node1(write thread, wait)
if (firstReader == current) {
// assert firstReaderHoldCount > 0;
} else {
if (rh == null) {
rh = cachedHoldCounter;
if (rh == null|| rh.tid ! = getThreadId(current)) { rh = readHolds.get();if (rh.count == 0) readHolds.remove(); }}if (rh.count == 0)
return -1; }}// ③ count design
if (sharedCount(c) == MAX_COUNT)
throw new Error("Maximum lock count exceeded");
if (compareAndSetState(c, c + SHARED_UNIT)) {
if (sharedCount(c) == 0) {
firstReader = current;
firstReaderHoldCount = 1;
} else if (firstReader == current) {
firstReaderHoldCount++;
} else {
if (rh == null)
rh = cachedHoldCounter;
if (rh == null|| rh.tid ! = getThreadId(current)) rh = readHolds.get();else if (rh.count == 0)
readHolds.set(rh);
rh.count++;
cachedHoldCounter = rh; // cache for release
}
return 1; }}}/ / AQS class
// Get read lock
public final void acquireShared(int arg) {
if (tryAcquireShared(arg) < 0)
doAcquireShared(arg);
}
private void doAcquireShared(int arg) {
// Failed to obtain the read lock
final Node node = addWaiter(Node.SHARED);
boolean failed = true;
try {
boolean interrupted = false;
/ / loop
for (;;) {
// Predecessor node
final Node p = node.predecessor();
if (p == head) { // The preceding node is head
int r = tryAcquireShared(arg);
if (r >= 0) { // Get read lock
setHeadAndPropagate(node, r);
p.next = null; // help GC
if (interrupted)
selfInterrupt();
failed = false;
return; }}if (shouldParkAfterFailedAcquire(p, node) &&
parkAndCheckInterrupt())
interrupted = true; }}finally {
if(failed) cancelAcquire(node); }}Copy the codeEnter the fullTryAcquireShared() method in various cases:
-
Write lock degradation means that thread1 has acquired the write lock and is ready to acquire the read lock again
-
Thread B is preparing to acquire the write lock before thread1 acquires the read lock. Thread1 acquires the read lock normally
Enter the code for comment ③
-
Until thread1 acquires the read lock, no other thread is ready to acquire the write lock
-
-
Thread1 acquires the write lock, and thread2 acquires the read lock
WriteLock (write)
The entire process is similar to the lock acquisition logic of the ReentrantLock class.
summary
- A write lock can be downgraded to a read lock, but a read lock cannot be upgraded to a write lock
- If the first node waiting in the synchronization queue is the writer thread, it cannot acquire the read lock and needs to queue
- The reader thread acquires the read lock and needs to pass on the successor node