preface
The previous article examined one of the practical uses of AQS: the implementation of ReentrantLock. ReentrantLock and synchronized are exclusive locks, while AQS also supports shared locks. This article will analyze the practical application of AQS shared locks. Through this article, you will learn:
1. Differences between shared lock and exclusive lock 2. Realization principle of read lock 3. Realization principle of write lock 4
1, shared lock, exclusive lock difference
The basic difference between
Shared locks and exclusive locks are implemented in AQS with the core value of “state” :
As shown above, for shared locks, multiple threads are allowed to effectively modify state.
Introduction of read/write locks
According to the figure above, state can represent only one lock at a time, either an exclusive lock or a shared lock. However, in actual application scenarios, multiple threads often read and write. In this case, state needs to be modified in order to cooperate with the reading and writing threads. First, let’s look at the definition of AQS State:
#AbstractQueuedSynchronizer.java
private volatile int state;
Copy the codeYou can see is of type int (of course also has a long, in AbstractQueuedLongSynchronizer. In Java, this paper int, for example)
2. The realization principle of read lock
The structure of the ReentrantReadWriteLock
ReentrantReadWriteLock does not implement the Lock interface as ReentrantLock does. Instead, ReentrantReadWriteLock holds member variables of type ReadLock and WriteLock respectively, both of which implement the Lock interface.
# ReentrantReadWriteLock. Java public ReentrantReadWriteLock () {/ / the default not fair lock this (false); } public ReentrantReadWriteLock(boolean fair) { sync = fair ? new FairSync() : new NonfairSync(); ReaderLock = new ReadLock(this); WriterLock = new WriteLock(this); }Copy the codeReentrantReadWriteLock By default, read and write locks support unfair and fair locks. After reading and writing the lock construct, expose the lock for external use:
# ReentrantReadWriteLock. Java / / public access to write lock object ReentrantReadWriteLock. WriteLock WriteLock () {return writerLock; } / / get read lock object public ReentrantReadWriteLock. ReadLock ReadLock () {return readerLock; }Copy the codeAcquiring a lock
When ReentrantLock analyzes an exclusive lock, it looks like this:
tryAcquireShared & tryReleaseShared
Take a look at the process of acquiring a lock:
# ReentrantReadWriteLock. ReadLock public void the lock () {/ / Shared lock sync acquireShared (1); } #AbstractQueuedSynchronizer.java public final void acquireShared(int arg) { if (tryAcquireShared(arg) < 0) DoAcquireShared implements doAcquireShared(arg) in AQS; }Copy the codeThe focus is on tryAcquireShared (xx) :
#ReentrantReadWriteLock.java protected final int tryAcquireShared(int unused) { Thread current = Thread.currentThread(); Int c = getState(); // exclusiveCount: state is 16 bits lower than state. If state is not 0, a thread is holding the write lock. ------------>(1) if (exclusiveCount(c)! = 0 && getExclusiveOwnerThread() ! = current) return -1; Int r = sharedCount(c); int r = sharedCount(c); // Whether the current thread should block if (! ReaderShouldBlock () && / / -- -- -- -- -- -- -- -- -- -- -- -- > (2) r < MAX_COUNT && / / if shouldn't be blocked, Then try the CAS modify state high 16-bit value compareAndSetState (c, c + SHARED_UNIT)) {/ / -- -- -- -- -- -- -- -- record number of threads/reentrant -- -- -- -- -- -- -- -- -- -- - > (3) / / modify state is successful, If (r == 0) {firstReader = current; FirstReaderHoldCount = 1; } else if (firstReader == current) {firstReaderHoldCount++; } else {// Another thread is holding the lock // fetch the cache HoldCounter HoldCounter rh = cachedHoldCounter; / / if the cache is empty, or stored in the cache is not the current thread if (rh = = null | | rh. Dar! //readHolds are of type ThreadLocalHoldCounter, Inherit from ThreadLocal cachedHoldCounter = rh = readHolds.get(); Else if (rh.count == 0) // if cachedHoldCounter is removed from threadLocal, ------------>(4) readHolds. Set (rh); Rh.count ++; //-------- Number of threads/reentrant -----------} return 1; } //------------>(5) return fullTryAcquireShared(current); }Copy the codeThe above is the core code to acquire the read lock, annotated with 5 key points, respectively to analyze. (1) There is a message here:
If the current thread has already acquired the write lock, it can continue to attempt to acquire the read lock. When it releases the write lock, only the read lock is left. This process can be understood as the degradation of the lock.
(2) Whether the thread has a chance to acquire the read lock requires two judgments:
ReaderShouldBlock (); 2. Check whether the number of read locks is used up. The threshold is 2^16-1.
ReaderShouldBlock () is the implementation of readerShouldBlock().
Let’s start with unfair read locks:
#ReentrantReadWriteLock.java final boolean readerShouldBlock() { return apparentlyFirstQueuedIsExclusive(); } # AbstractQueuedSynchronizer. Java final Boolean apparentlyFirstQueuedIsExclusive () {/ / whether the second Node in the waiting queue waiting for the write lock Node h, s, return (h = head) ! = null && (s = h.next) ! = null && ! s.isShared() && s.thread ! = null; }Copy the codeIf the second node in the wait queue is waiting for a write lock, then the read lock cannot be obtained. This is different from ReentrantLock, where the implementation of an unfair lock attempts to acquire the lock regardless of whether there are nodes in the wait queue.
Let’s look at fair read locks
#ReentrantReadWriteLock.java
final boolean readerShouldBlock() {
return hasQueuedPredecessors();
}
Copy the codeDetermine whether there are nodes in the queue that are queued earlier than the current thread. This method was analyzed in depth in the previous analysis of ReentrantLock and will not be described here.
(3) This part of the code looks a lot, but in fact it is to record the reentrant times and introduce some caching for efficiency. To allow for the possibility that only one thread will always acquire the read lock, we define two variables that also count the reentrant count:
# ReentrantReadWriteLock. Java Thread fetching the read lock / / records the first private transient Thread firstReader = null; Private TRANSIENT int firstReaderHoldCount; private TRANSIENT int firstReaderHoldCount;Copy the codeConsidering that there are multiple threads acquiring locks, and they also need to record the number of locks acquired, we came up with a ThreadLocal and defined it as:
private transient ThreadLocalHoldCounter readHolds;
Copy the codeTo record the HoldCounter(store the number of locks acquired and the id of the bound thread). In order not to query the data in ThreadLocal every time, we define a variable to cache the HoldCounter:
#ReentrantReadWriteLock.java
private transient HoldCounter cachedHoldCounter;
Copy the code(4) CachedHoldCounter. count == 0 in tryReleaseShared(xx), and when the thread has completely released the read lock, the HoldCounter will be removed from ThreadLocal.
(5) At this stage, it indicates that the previous operation to obtain the lock failed, for three reasons:
ReaderShouldBlock () == true 2, r >= MAX_COUNT 3. Some other thread changed state halfway through.
FullTryAcquireShared (xx) is similar to tryAcquireShared(xx) in that the purpose is to get the lock. For fullTryAcquireShared(xx), there is an infinite loop in which the state value is continuously obtained. If the value is 1 or 2, the loop will exit. Otherwise, the CAS will try to modify the state value.
To summarize:
FullTryAcquireShared (xx) fails to acquire the lock and returns -1. The following processing logic is passed to AQS and the thread may be suspended. FullTryAcquireShared (xx) If the lock is obtained successfully, return 1.
Release the lock
The logic for releasing locks is simple:
#ReentrantReadWriteLock.ReadLock public void lock() { sync.acquireShared(1); } # AbstractQueuedSynchronizer. Java public final Boolean releaseShared (int arg) {if (tryReleaseShared (arg)) {/ / in AQS doReleaseShared(); return true; } return false; }Copy the codeThe focus is on tryReleaseShared (xx) :
#ReentrantReadWriteLock.java protected final boolean tryReleaseShared(int unused) { Thread current = Thread.currentThread(); If (firstReader == current) {if (firstReaderHoldCount == 1); else firstReaderHoldCount--; } else {// take HoldCounter rh = cachedHoldCounter; if (rh == null || rh.tid ! GetThreadId (current)); rholds = readHolds (); int count = rh.count; If (count <= 1) {// If (count <= 1) {ThreadLocal readHolds. Remove (); if (count <= 0) throw unmatchedUnlockException(); } --rh.count; } for (;;) {// modify state int c = getState(); int nextc = c - SHARED_UNIT; If (compareAndSetState(c, nexTC)) // If (compareAndSetState(c, nexTC)) // If (compareAndSetState(c, nexTC)) // If state is 0, both read and write locks are released. }}Copy the codeTryReleaseShared (xx) will return false if the read and write locks are not fully released. The process of releasing shared locks in AQS is as follows:
#AbstractQueuedSynchronizer.java
public final boolean releaseShared(int arg) {
if (tryReleaseShared(arg)) {
doReleaseShared();
return true;
}
return false;
}
Copy the codeThat is, in this case, doReleaseShared() will not be called and will not wake up the nodes in the synchronization queue. Here’s why:
If only the read lock is released, the write lock is still occupied. Because write locks are exclusive locks, other threads cannot acquire them, so it is useless to wake them up.
3. Realization principle of write lock
Acquiring a lock
Write locks are exclusive locks, so focus on tryAcquire(xx):
#ReentrantReadWriteLock.java protected final boolean tryAcquire(int acquires) { Thread current = Thread.currentThread(); Int c = getState(); Int w = exclusiveCount(c); if (c ! =0) {//1, w==0, c! = 0, indicating a thread lock has read, can no longer access to write lock / / 2, if the write lock is being used, but not the current thread, it can no longer access to write locks the if (w = = 0 | | current! = getExclusiveOwnerThread()) return false; If (w + exclusiveCount(acquires) > MAX_COUNT) throw new Error("Maximum lock count exceeded"); SetState (c + acquires); // Set setState(c + acquires); return true; } / / c = = 0, if read lock at this time, don't write lock threads / / whether the thread should be blocked, or attempt to obtain write locks -- -- -- -- -- -- -- > (1) if (writerShouldBlock () | |! compareAndSetState(c, c + acquires)) return false; SetExclusiveOwnerThread (current); return true; }Copy the codeLook at writerShouldBlock(), this is where write lock fairness/injustice is implemented.
Let’s start with non-fair write locks:
# ReentrantReadWriteLock. Java final Boolean writerShouldBlock () {/ / don't block the return false; // writers can always barge }Copy the codeAn unfair write lock should not block.
Let’s look at fair write lock:
# ReentrantReadWriteLock. Java final Boolean writerShouldBlock () {/ / waiting for the return to determine whether a queue with effective node hasQueuedPredecessors (); }Copy the codeSame judgment condition as fair read lock.
summary
1. If the read/write lock has been occupied by another thread, the new thread will not be able to acquire the write lock. 2. Write locks can be reentrant.
Release the lock
Focus on tryRelease(xx):
# # ReentrantReadWriteLock. Java protected final Boolean tryRelease (int releases) {/ / whether the current thread holds a write lock the if (! isHeldExclusively()) throw new IllegalMonitorStateException(); Int nexTC = getState() -releases; Boolean Free = exclusiveCount(nexTC) == 0; If (free) // Unassociate setExclusiveOwnerThread(null); // setState setState(nextc); return free; }Copy the codeIf tryRelease(xx) returns true, the AQS will wake up the waiting thread.
4, read and write lock tryLock principle
Read lock tryLock
#ReentrantReadWriteLock.java
public boolean tryLock() {
return sync.tryReadLock();
}
final boolean tryReadLock() {
Thread current = Thread.currentThread();
for (;;) {
//for 循环为了检测最新的state
int c = getState();
if (exclusiveCount(c) != 0 &&
getExclusiveOwnerThread() != current)
return false;
int r = sharedCount(c);
if (r == MAX_COUNT)
throw new Error("Maximum lock count exceeded");
if (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 true;
}
}
}
Copy the codeTryReadLock (xx) : as long as no other thread owns the write lock and the number of read locks does not exceed the limit, it will try to acquire the read lock until it does.
Write lock tryLock
public boolean tryLock() { return sync.tryWriteLock(); } final boolean tryWriteLock() { Thread current = Thread.currentThread(); int c = getState(); if (c ! = 0) { int w = exclusiveCount(c); if (w == 0 || current ! = getExclusiveOwnerThread()) return false; if (w == MAX_COUNT) throw new Error("Maximum lock count exceeded"); } if (! compareAndSetState(c, c + 1)) return false; setExclusiveOwnerThread(current); return true; }Copy the codeWrite lock attempts CAS only once and returns on failure. Finally, the functions realized by read lock and write lock are shown in the graph:
Read lock and write lock:
5, read and write lock application
After analyzing the principle, let’s look at the simple application.
public class TestThread { static ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock(); static ReentrantReadWriteLock.ReadLock readLock = readWriteLock.readLock(); static ReentrantReadWriteLock.WriteLock writeLock = readWriteLock.writeLock(); Public static void main(String args[]) {// read for (int I = 0; i < 10; i++) { new Thread(new Runnable() { @Override public void run() { String threadName = Thread.currentThread().getName(); try { System.out.println("thread " + threadName + " acquire read lock"); readLock.lock(); System.out.println("thread " + threadName + " read locking"); Thread.sleep(1000); } catch (InterruptedException e) { e.printStackTrace(); } finally { readLock.unlock(); System.out.println("thread " + threadName + " release read lock remain read count:" + readWriteLock.getReadLockCount()); } } }, "" + i).start(); } // write for (int I = 0; i < 10; i++) { new Thread(new Runnable() { @Override public void run() { String threadName = Thread.currentThread().getName(); try { System.out.println("thread " + threadName + " acquire write lock"); writeLock.lock(); System.out.println("thread " + threadName + " write locking"); Thread.sleep(1000); } catch (InterruptedException e) { e.printStackTrace(); } finally { writeLock.unlock(); System.out.println("thread " + threadName + " release write lock remain write count:" + readWriteLock.getWriteHoldCount()); } } }, "" + i).start(); }}}Copy the codeTen threads acquire the read lock and ten threads acquire the write lock. Read/write lock application scenarios:
- ReentrantReadWriteLock is suitable for scenarios with too many reads and too few writes to improve multi-threaded read efficiency and throughput.
Read lock and write lock relationships for the same thread:
public class TestThread { static ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock(); static ReentrantReadWriteLock.ReadLock readLock = readWriteLock.readLock(); static ReentrantReadWriteLock.WriteLock writeLock = readWriteLock.writeLock(); public static void main(String args[]) { // new TestThread().testReadWriteLock(); ------>1; // new TestThread().testWritereadlock (); ------>2, private void testReadWriteLock() {system.out.println ("before read lock"); readLock.lock(); System.out.println("before write lock"); writeLock.lock(); System.out.println("after write lock"); } private void testWriteReadLock() { System.out.println("before write lock"); writeLock.lock(); System.out.println("before read lock"); readLock.lock(); System.out.println("after read lock"); }}Copy the codeOpen comments 1 and 2 respectively and find:
1. The thread is suspended at the write lock if the read lock is acquired first and then the write lock is acquired. 2. Acquire the write lock first, then acquire the read lock, then can obtain the lock normally.
This is consistent with our above theoretical analysis.
The next part will analyze the principles of Semaphore, CountDownLatch and CyclicBarrier and their applications.
This article is based on JDK1.8.