Let’s put our cards on the table, and this time it’s me

Read/write locks in JDK5 will have deadlocks.

In Java 5, the read lock behaves more like a Semaphore than a lock, maintaining only the number of active reader threads regardless of their identity. This behavior was changed in Java 6 to record which threads have acquired read locks. One reason for this change is that in Java 5’s lock implementation, there is no way to distinguish between a thread’s first read lock request and a reentrable lock request, potentially deadlocking a fair read-write lock.

See here has not been able to understand how this deadlock is happening, and then put the problem to the company group, a few big bosses gave ideas and made an explanation on the source level, it is to understand this problem thoroughly, here to think about the process of sorting out a summary.

Repetition of deadlock

Let’s try emersion books described in A deadlock scenario happens, the basic idea is to run two threads, assuming that A and B, respectively, read-write lock set to fair lock, thread A first to get A read lock, and then thread attempts to acquire B write lock, in the action of thread B to thread A try again after get read lock, the code is as follows:

public class Jdk5DeadLockTest { public static void main(String[] args) { ReentrantReadWriteLock lock = new ReentrantReadWriteLock(true); ReentrantReadWriteLock.ReadLock readLock = lock.readLock(); ReentrantReadWriteLock.WriteLock writeLock = lock.writeLock(); // the current thread acquires the readLock readlock. lock(); System.out.println("main thread get read lock."); Thread threadA = new Thread(new Runnable() {@override public void run() {system.out.println (" Thread A try ") to get write lock."); writeLock.lock(); System.out.println("thread A get write lock."); try { Thread.sleep(1000); } catch (InterruptedException e) { e.printStackTrace(); } System.out.println("thread A release write lock."); }}); threadA.start(); try { Thread.sleep(1000); } catch (InterruptedException e) { e.printStackTrace(); System.out.println("main thread try to get read lock again."); readLock.lock(); System.out.println("main thread get read lock again."); readLock.unlock(); readLock.unlock(); System.out.println("main thread release read lock."); }}Copy the code

The above code is based onJDK5Under the version ofReentrantReadWriteLockIn executionmain()After method, the output result is as follows:This can be found by console printingThread ABlocked after trying to acquire the write lock, whileThe main threadAlso blocks where reentrant acquires the read lock,jstackIf you look at the thread log, you can see that both places are waitingReentrantReadWriteLock$FairSyncThis resource. The deadlock phenomenon described in the book is reproduced by us.

How do deadlocks occur: the lock() method that reads and writes locks in JDK5

Let’s look at the first place where the thread waits: ReentrantReadWriteLock$FairSync$wlock() ¶ FairSync$wlock() ¶

// ReentrantReadWriteLock$FairSync$wlock() final void wlock() { // no fast path acquire(1); } / / AbstractQueuedSynchronizer $acquire () public final void acquire (int arg) {/ / tryAcquire () failed to get the lock, The current thread is placed in a wait queue to spin if (! tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); } // ReentrantReadWriteLock$FairSync$tryAcquire(int) protected final boolean tryAcquire(int acquires) { // mask out readlocks if called from condition methods acquires = exclusiveCount(acquires); Thread current = Thread.currentThread(); Thread first; int c = getState(); int w = exclusiveCount(c); if (w + acquires >= SHARED_UNIT) { throw new Error("Maximum lock count exceeded"); } // In the scenario simulated by the above replay code, w=0(the first time the thread acquired the write lock), c! =0(the main thread has already acquired the lock once); if ((w == 0 || current ! = owner) && (c ! = 0 || ((first = getFirstQueuedThread()) ! = null && first ! = current))) { return false; } if (! compareAndSetState(c, c + acquires)) { return false; } owner = current; return true; }Copy the code

The main flow is shown in the following figure. The thread that acquired the write lock is suspended:

Moving on to the second place where threads wait: ReentrantReadWriteLock$FairSync$acquireShared(); readLock.lock(); FairSync$acquireShared() ¶

AQS acquireShared(), if tryAcquireShared() is less than 0, the read lock has failed, and the thread that is currently acquiring the read lock will be wrapped into the AQS wait queue and spin to re-acquire the read lock. Public final void acquireShared(int arg) {if (tryAcquireShared(arg) < 0) doAcquireShared(arg); } // ReentrantReadWriteLock$FairSync$tryAcquireShared(int) protected final int tryAcquireShared(int acquires) { Thread current = Thread.currentThread(); for (;;) { int c = getState(); // Call 'exclusiveCount(c)' to get the number of threads that have acquired the write lock. If (exclusiveCount(c)! = 0) { if (owner ! = current) { return -1; }} else {// Call getFirstQueuedThread() to get the head thread of the current AQS queue. A Thread first = getFirstQueuedThread(); TryAcquireShared () returns -1 if (first! = null && first ! = current) { return -1; } } int nextc = c + (acquires << SHARED_SHIFT); if (nextc < c) { throw new Error("Maximum lock count exceeded"); } if (compareAndSetState(c, nextc)) { return 1; Public final Thread getFirstQueuedThread() {// Recheck count if lost CAS {// Recheck count if lost CAS}} public final Thread getFirstQueuedThread() {// FullGetFirstQueuedThread () return (head == tail)? null : fullGetFirstQueuedThread(); }Copy the code

The main process is similar to the previous process of acquiring write locks, as shown in the figure below. However, the run result shows that when acquiring read locks for the second time,The main threadIt was also suspended.

Now let’s combine these two processes to see how deadlocks occur. Locksupport. park(Object Blocker). In our test scenario, we passed in ReentrantReadWriteLock$FairSync as the blocker. Thread A fails to acquire A write lock and is suspended waiting for FairSync resource to be released. Then thread main fails to acquire A readLock and is suspended waiting for FairSync resource to be released. However, readlock. unlock(), the code that releases the resource, occurs after the second readLock. A deadlock occurs when the main thread blocks and the FairSync resource cannot be released.

How to fix deadlocks: The lock() method that reads and writes locks in JDK8

Now that we have found the cause of the fair read/write lock in JDK5, how can we fix the problem? The Jdk5DeadLockTest test class given earlier works in the JDK8 version (ps). The deadlock does not occur in JDK6, so let’s take a look at how to resolve this issue.

ReentrantReadWriteLock is a major update to the JDK5 version, but we can look at how fair read/write locks are handled when a read lock is acquired.

// ReentrantReadWriteLock$ReadLock$lock() public void lock() { sync.acquireShared(1); } / / AbstractQueuedSynchronizer $acquireShared (int) failed to get read lock / / waiting queue to spin public final void acquireShared (int arg) {if (tryAcquireShared(arg) < 0) doAcquireShared(arg); } // ReentrantReadWriteLock$Sync$tryAcquireShared(int) protected final int tryAcquireShared(int unused) { Thread current  = Thread.currentThread(); // Omit some code, irrelevant to the problem we are analyzing...... Return fullTryAcquireShared(current); return fullTryAcquireShared(current); } // ReentrantReadWriteLock$Sync$fullTryAcquireShared(Thread) final int fullTryAcquireShared(Thread current) { HoldCounter rh = null; for (;;) { int c = getState(); // In our test scenario, no thread has acquired the write lock yet, so the 'exclusiveCount(c)=0' condition is false if (' exclusiveCount(c)! = 0) { if (getExclusiveOwnerThread() ! = current) return -1; // else we hold the exclusive lock; Blocking here // would cause deadlock.} else if (readerShouldBlock()) {// The readerShouldBlock() method checks whether the current thread is a head of the wait queue // In the scenario simulated by our test code, this returns true // the firstReader variable records the first thread that successfully acquired the read lock. Here returns true 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; If (sharedCount(c) == MAX_COUNT) throw new Error("Maximum lock count exceeded"); State if (compareAndSetState(c, c + SHARED_UNIT)) {if (sharedCount(c) == 0) { FirstReader = current; firstReader = current; FirstReaderHoldCount = 1; firstReaderHoldCount = 1; } else if (firstReader == current) {// In our test scenario, firstReader == current condition will be judged true, // increase the number of read locks held by the firstReader thread. FirstReaderHoldCount++; If (rh == null) // cachedHoldCounter records the number of read locks held by the last thread that successfully acquired the read lock rh = cachedHoldCounter; if (rh == null || rh.tid ! Rshholds (); rshholds (); rshholds (); rshholds (); else if (rh.count == 0) readHolds.set(rh); rh.count++; cachedHoldCounter = rh; // cache for release} // the thread reenters the lock successfully and returns a non-negative 1. } } } // ReentrantReadWriteLock$FairSync$readerShouldBlock() final boolean readerShouldBlock() { return hasQueuedPredecessors(); } / / AbstractQueuedSynchronizer $hasQueuedPredecessors () / / this method can detect whether the current thread to wait for the queue head node, is false, Public final Boolean hasqueued24 () {Node t = tail; // Read fields in reverse initialization order Node h = head; Node s; return h ! = t && ((s = h.next) == null || s.thread ! = Thread.currentThread()); }Copy the code

The main source code for the same thread reentrant read lock acquisition in JDK8 is presented above, and the key processing logic is annotated. The main idea is to introduce firstReader, firstReaderHoldCount, readHolds, cachedHoldCounter and other variables to store the number of read locks held by each read lock thread, so as to handle special cases such as reentrantread lock.

Afterword.

Thanks for the ideas and solutions provided by the company leaders, which solved the problem that PUZZLED me for a long time. Finally, as usual, I will refer to the resources:

  • Java Concurrent Programming
  • JDK5 / JDK8 ReentrantReadWriteLock source code
  • JDK5 source code download