The problem
(1) What is read/write lock?
(2) What are the characteristics of read/write locks?
(3) How does ReentrantReadWriteLock implement read/write locks?
(4) How to use ReenTrantreadWrite elock to achieve efficient and secure TreeMap?
Introduction to the
Read/write lock is a special lock that divides access to shared resources into read access and write access. Multiple threads can simultaneously read and write access to shared resources, but only one thread can write and write access to shared resources at the same time. The read/write lock greatly improves concurrency.
features
Read/write locks have the following features:
| If the mutex | read | write |
|---|---|---|
| read | no | is |
| write | is | is |
As you can see, read/write locks are not mutually exclusive except for read. Read/write locks are mutually exclusive.
How does ReentrantReadWriteLock implement read/write locks?
Class structure
Before looking at the source code, let’s take a look at the main structure of the ReentrantReadWriteLock class.
The classes in ReentrantReadWriteLock are divided into three parts:
ReentrantReadWriteLock implements the ReadWriteLock interface. This interface provides only two methods: readLock() and writeLock ().
(2) synchronizer, which contains a Sync inner class that inherits AQS, and its two subclasses FairSync and NonfairSync;
(3) Two inner classes, ReadLock and WriteLock, implement the Lock interface and have some locking features.
Source code analysis
The main properties
/ / read lock
private final ReentrantReadWriteLock.ReadLock readerLock;
/ / write locks
private final ReentrantReadWriteLock.WriteLock writerLock;
/ / synchronizer
final Sync sync;
Copy the codeMaintain read locks, write locks and synchronizers.
Main construction methods
// Default constructor
public ReentrantReadWriteLock(a) {
this(false);
}
// Whether to use the fair lock constructor
public ReentrantReadWriteLock(boolean fair) {
sync = fair ? new FairSync() : new NonfairSync();
readerLock = new ReadLock(this);
writerLock = new WriteLock(this);
}
Copy the codeIt provides two constructors. The default constructor uses an unfair lock pattern and initializes read and write locks in the constructor.
Methods to get read and write locks
public ReentrantReadWriteLock.WriteLock writeLock(a) { return writerLock; }
public ReentrantReadWriteLock.ReadLock readLock(a) { return readerLock; }
Copy the codeThe read and write locks in the property are private properties and are exposed through these two methods.
Below we mainly analyze the lock and unlock methods of read lock and write lock, and are based on unfair mode.
ReadLock.lock()
// ReentrantReadWriteLock.ReadLock.lock()
public void lock(a) {
sync.acquireShared(1);
}
// AbstractQueuedSynchronizer.acquireShared()
public final void acquireShared(int arg) {
// Try to acquire the shared lock (1 indicates success, -1 indicates failure)
if (tryAcquireShared(arg) < 0)
// If you fail, you may have to queue
doAcquireShared(arg);
}
// ReentrantReadWriteLock.Sync.tryAcquireShared()
protected final int tryAcquireShared(int unused) {
Thread current = Thread.currentThread();
// The value of the state variable
// In read-write lock mode, the higher 16 bits store the number of times a shared lock (read lock) was acquired, and the lower 16 bits store the number of times a mutex lock (write lock) was acquired
int c = getState();
// The number of mutex counts
// If another thread has acquired the write lock, return -1
if(exclusiveCount(c) ! =0&& getExclusiveOwnerThread() ! = current)return -1;
// The number of times the read lock was acquired
int r = sharedCount(c);
// There is no write lock at this time, try to update the value of state to obtain the read lock
// Does the reader need to queue (fair mode)
if(! readerShouldBlock() && r < MAX_COUNT && compareAndSetState(c, c + SHARED_UNIT)) {// Succeeded in obtaining the read lock
if (r == 0) {
// If no thread has acquired the read lock before
// Record the first reader as the current thread
firstReader = current;
// The number of times the first reader reenters is 1
firstReaderHoldCount = 1;
} else if (firstReader == current) {
// If a thread has acquired the read lock and the current thread is the first reader
// The reentrant count is increased by 1
firstReaderHoldCount++;
} else {
// If a thread has acquired the read lock and the current thread is not the first reader
// Retrieves the reentrant count saver from the cache
HoldCounter rh = cachedHoldCounter;
// If the cache does not attribute the current thread
// Fetch it from ThreadLocal
// readHolds themselves are ThreadLocal, which holds the HoldCounter
if (rh == null|| rh.tid ! = getThreadId(current))// rh is initialized when get() is used
cachedHoldCounter = rh = readHolds.get();
else if (rh.count == 0)
// If the degree of rh is 0, place it in ThreadLocal
readHolds.set(rh);
// The number of reentries is increased by 1 (the initial number is 0)
rh.count++;
}
// Successfully acquired the read lock, return 1
return 1;
}
// Use this method to try to acquire the read lock again (if another thread has acquired the write lock before, return -1 indicating failure)
return fullTryAcquireShared(current);
}
// AbstractQueuedSynchronizer.doAcquireShared()
private void doAcquireShared(int arg) {
// Enter the AQS queue
final Node node = addWaiter(Node.SHARED);
boolean failed = true;
try {
boolean interrupted = false;
for (;;) {
// The previous node of the current node
final Node p = node.predecessor();
// If the previous node is the head node (indicating the first queued node)
if (p == head) {
// Try again to acquire the read lock
int r = tryAcquireShared(arg);
// If successful
if (r >= 0) {
// The head node moves back and propagates
// Propagation wakes up successive read nodes
setHeadAndPropagate(node, r);
p.next = null; // help GC
if (interrupted)
selfInterrupt();
failed = false;
return; }}// No read lock was acquired, block and wait to be woken up
if (shouldParkAfterFailedAcquire(p, node) &&
parkAndCheckInterrupt())
interrupted = true; }}finally {
if(failed) cancelAcquire(node); }}// AbstractQueuedSynchronizer.setHeadAndPropagate()
private void setHeadAndPropagate(Node node, int propagate) {
// h is the old head node
Node h = head;
// Set the current node to the new head node
setHead(node);
// If the old or new head node is empty or its wait state is less than 0 (SIGNAL/PROPAGATE)
if (propagate > 0 || h == null || h.waitStatus < 0 ||
(h = head) == null || h.waitStatus < 0) {
// Need to propagate
// Remove the next node
Node s = node.next;
// If the next node is empty, or the node that needs to acquire the read lock
if (s == null || s.isShared())
// Wake up the next nodedoReleaseShared(); }}// AbstractQueuedSynchronizer.doReleaseShared()
// This method only wakes up one node
private void doReleaseShared(a) {
for (;;) {
Node h = head;
if(h ! =null&& h ! = tail) {int ws = h.waitStatus;
// If the state of the head node is SIGNAL, the next node needs to be woken up
if (ws == Node.SIGNAL) {
if(! compareAndSetWaitStatus(h, Node.SIGNAL,0))
continue; // loop to recheck cases
// Wake up the next node
unparkSuccessor(h);
}
else if (ws == 0 &&
// Change the state of the head node to PROPAGATE successfully to jump to the following if! compareAndSetWaitStatus(h,0, Node.PROPAGATE))
continue; // loop on failed CAS
}
// If the head does not change after waking up, the loop is broken
if (h == head) // loop if head changed
break; }}Copy the codeReentrantLock = fair lock = unfair lock = fair lock = fair lock = fair lock = fair lock = fair lock = fair lock = fair lock = fair lock = fair lock = fair lock = fair lock = fair lock = fair lock
Let’s look at the general logic:
(1) First try to acquire read lock;
(2) If successful, directly end;
(3) If this fails, enter the doAcquireShared() method;
(4) In doAcquireShared() method, a new node will be generated and entered into the AQS queue;
(5) If the head node is just the node before the current node, try again to acquire the lock;
(6) If successful, set the head node as a new node and propagate;
(7) Propagation is to wake up the next read node (if the next node is a read node);
(8) if the head node is not the previous node of the current node or (5) fails, the current thread is blocked waiting to be woken up;
(9) Wake up and go on (5) logic;
Where does the read node wake up continuously in the entire logic?
In the doAcquireShared() method, after A node A acquires the read lock, it wakes up the next node B, which acquires the read lock, and then B wakes up C. Instead of one node acquiring a read lock and waking up all subsequent read nodes at once.
ReadLock.unlock()
// java.util.concurrent.locks.ReentrantReadWriteLock.ReadLock.unlock
public void unlock(a) {
sync.releaseShared(1);
}
// java.util.concurrent.locks.AbstractQueuedSynchronizer.releaseShared
public final boolean releaseShared(int arg) {
// If the attempt succeeds, wake up the next node
if (tryReleaseShared(arg)) {
// This method actually wakes up the next node
doReleaseShared();
return true;
}
return false;
}
// java.util.concurrent.locks.ReentrantReadWriteLock.Sync.tryReleaseShared
protected final boolean tryReleaseShared(int unused) {
Thread current = Thread.currentThread();
if (firstReader == current) {
// If the first reader is the current thread
// Just subtract the number of times it reenters by 1
// Empty the first reader if it reaches 0
if (firstReaderHoldCount == 1)
firstReader = null;
else
firstReaderHoldCount--;
} else {
// If the first reader is not the current thread
// Again, reduce the number of times it reenters by 1
HoldCounter rh = cachedHoldCounter;
if (rh == null|| rh.tid ! = getThreadId(current)) rh = readHolds.get();int count = rh.count;
if (count <= 1) {
readHolds.remove();
if (count <= 0)
throw unmatchedUnlockException();
}
--rh.count;
}
for (;;) {
// The number of times the shared lock is acquired is reduced by 1
// Return true if the value is reduced to 0
int c = getState();
int nextc = c - SHARED_UNIT;
if (compareAndSetState(c, nextc))
return nextc == 0; }}// java.util.concurrent.locks.AbstractQueuedSynchronizer.doReleaseShared
// The behavior does not match the method name, but actually wakes up the next node
private void doReleaseShared(a) {
for (;;) {
Node h = head;
if(h ! =null&& h ! = tail) {int ws = h.waitStatus;
// If the state of the head node is SIGNAL, the next node needs to be woken up
if (ws == Node.SIGNAL) {
if(! compareAndSetWaitStatus(h, Node.SIGNAL,0))
continue; // loop to recheck cases
// Wake up the next node
unparkSuccessor(h);
}
else if (ws == 0 &&
// Change the state of the head node to PROPAGATE successfully to jump to the following if! compareAndSetWaitStatus(h,0, Node.PROPAGATE))
continue; // loop on failed CAS
}
// If the head does not change after waking up, the loop is broken
if (h == head) // loop if head changed
break; }}Copy the codeThe general unlocking process is as follows:
(1) Reduce the reentrant times of the current thread by 1;
(2) Subtract 1 from the total number of times the shared lock is acquired;
(3) If The Times of acquiring the shared lock is reduced to 0, it means that the shared lock is released completely, and then the next node is woken up;
As shown in the figure below, three nodes ABC have each obtained a shared lock, and the sequence of releasing the shared lock is ACB respectively. Then, when B finally releases the shared lock, tryReleaseShared() will return true, and then the next node D will be awakened.
WriteLock.lock()
// java.util.concurrent.locks.ReentrantReadWriteLock.WriteLock.lock()
public void lock(a) {
sync.acquire(1);
}
// java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire()
public final void acquire(int arg) {
// Try to get the lock first
If ReentrantLock fails, the ReentrantLock will be queued
if(! tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }// java.util.concurrent.locks.ReentrantReadWriteLock.Sync.tryAcquire()
protected final boolean tryAcquire(int acquires) {
Thread current = Thread.currentThread();
// The value of the state variable
int c = getState();
// The number of times the mutex was acquired
int w = exclusiveCount(c);
if(c ! =0) {
/ / if the c! If =0 and w==0, the number of times that the shared lock is obtained is not 0
// The whole meaning of this sentence is that
// If the number of times the shared lock is acquired is not 0, or another thread has acquired the mutex (write lock).
// Then return false, failed to acquire write lock
if (w == 0|| current ! = getExclusiveOwnerThread())return false;
// Overflow detection
if (w + exclusiveCount(acquires) > MAX_COUNT)
throw new Error("Maximum lock count exceeded");
// The current thread has already acquired the write lock
setState(c + acquires);
// Succeeded in obtaining the write lock
return true;
}
// If c is 0, try updating the value of state (writerShouldBlock() returns false)
// If the write lock fails, false is returned
// If successful, write lock was acquired, set yourself as possessor, and return true
if(writerShouldBlock() || ! compareAndSetState(c, c + acquires))return false;
setExclusiveOwnerThread(current);
return true;
}
// ReentrantLock failed to obtain the write lock
Copy the codeWrite lock acquisition process is as follows:
(1) Try to obtain the lock;
(2) If a reader owns the read lock, the attempt to acquire the write lock fails;
(3) If another thread owns the write lock, the attempt to acquire the write lock fails;
(4) If the current thread owns the write lock, the state value is increased by 1.
(5) If there is no thread holding the lock (state==0), the current thread tries to update the value of state. If it succeeds, the attempt to acquire the lock is successful; otherwise, it fails.
(6) After the attempt to obtain the lock fails, it enters the queue and waits to be woken up;
(7) The subsequent logic is consistent with ReentrantLock;
WriteLock.unlock()
// java.util.concurrent.locks.ReentrantReadWriteLock.WriteLock.unlock()
public void unlock(a) {
sync.release(1);
}
//java.util.concurrent.locks.AbstractQueuedSynchronizer.release()
public final boolean release(int arg) {
// If the attempt to release the lock is successful (fully release the lock)
// Just try to wake up the next node
if (tryRelease(arg)) {
Node h = head;
if(h ! =null&& h.waitStatus ! =0)
unparkSuccessor(h);
return true;
}
return false;
}
// java.util.concurrent.locks.ReentrantReadWriteLock.Sync.tryRelease()
protected final boolean tryRelease(int releases) {
// Throw an exception if the write lock is not owned by the current thread
if(! isHeldExclusively())throw new IllegalMonitorStateException();
// The value of the state variable is reduced by 1
int nextc = getState() - releases;
// Whether to release the lock completely
boolean free = exclusiveCount(nextc) == 0;
if (free)
setExclusiveOwnerThread(null);
// Set the value of the status variable
setState(nextc);
// Return true if the write lock is fully released
return free;
}
Copy the codeWrite lock release process is roughly as follows:
(1) First try to release the lock, that is, the value of the state variable state is reduced by 1;
(2) If the value is reduced to 0, the lock is released completely;
(3) The next waiting node is awakened only after the lock is released completely;
conclusion
(1) ReentrantReadWriteLock adopts the idea of read/write lock to improve the throughput of concurrency;
(2) Read locks use shared locks. Multiple read locks can be acquired together without affecting each other, that is, read locks are not mutually exclusive.
(3) Read/write, write read and write are mutually exclusive. The former possesses the lock, while the latter needs to queue up in the AQS queue.
(4) Multiple sequential reader threads are woken up one after the other, rather than all at once;
(5) The next writer thread will wake up only when all read locks are released completely;
(6) Only when the write lock is fully released will the next wait wake up, which may be the reader thread or the writer thread;
eggs
(1) What if the same program obtains read locks first and then write locks?
Analyzing the code in the figure above, in the tryAcquire() method, if the read lock is not acquired 0 times (c! = 0 &&w == 0), returns false, after which the outer method will block the current thread.
This can be verified by:
readLock.lock();
writeLock.lock();
writeLock.unlock();
readLock.unlock();
Copy the codeAfter running the program, the code stops at writelock.lock (); Of course, you can also hit a breakpoint to trace into it.
(2) What if the same program obtains the write lock first and then the read lock?
In the tryAcquireShared() method, the first red box is not returned because getExclusiveOwnerThread() is not satisfied! = current; The second red box indicates that the read lock was acquired if the atomic update was successful, and then the code at the third red box is executed to change its reentrant count to 1.
This can be verified by:
writeLock.lock();
readLock.lock();
readLock.unlock();
writeLock.unlock();
Copy the codeYou can track it with a breakpoint.
(3) Is it deadlocked?
Through the above two examples, we can feel that the same line program reading before writing is completely different from writing before reading. Why is it different?
First learns to write and read a thread holds the lock, other threads can still holds the read lock, if before other threads have read lock let oneself occupies a write lock, other threads can’t occupy read lock again, this program will be very difficult to achieve, logic is very strange, so, is designed to be as long as read a thread holds a lock, Other threads, including itself, can no longer acquire the write lock.
Write before read, after one thread holds the write lock, other threads cannot hold any lock, at this time, even if they hold a read lock, the program logic will not have any impact, so, a thread can hold the write lock is to hold the read lock, but this time other threads still cannot obtain the read lock.
If you think about the logic above, you will see that a thread that first owns the read lock and then owns the write lock has a major problem – the lock cannot be released or acquired. This thread owns the read lock, and then it blocks when it owns the write lock, and then it kills itself, and then it kills other threads, so it can’t release the lock, and other threads can’t get the lock.
Is this a deadlock? A deadlock is defined as thread A holding resources required by thread B, thread B holding resources required by thread A, and two threads waiting for each other to release resources. A classic example of A deadlock is as follows:
Object a = new Object();
Object b = new Object();
new Thread(()->{
synchronized (a) {
LockSupport.parkNanos(1000000);
synchronized (b) {
}
}
}).start();
new Thread(()->{
synchronized (b) {
synchronized (a) {
}
}
}).start();
Copy the codeSimple deadlocks can be seen with jStack:
"Thread-1":
at com.coolcoding.code.synchronize.ReentrantReadWriteLockTest.lambda$main$1(ReentrantReadWriteLockTest.java:40)
- waiting to lock <0x000000076baa9068> (a java.lang.Object)
- locked <0x000000076baa9078> (a java.lang.Object) at com.coolcoding.code.synchronize.ReentrantReadWriteLockTest? Lambda$2/1831932724.run(Unknown Source)
at java.lang.Thread.run(Thread.java:748)
"Thread-0":
at com.coolcoding.code.synchronize.ReentrantReadWriteLockTest.lambda$main$0(ReentrantReadWriteLockTest.java:32)
- waiting to lock <0x000000076baa9078> (a java.lang.Object)
- locked <0x000000076baa9068> (a java.lang.Object) at com.coolcoding.code.synchronize.ReentrantReadWriteLockTest? Lambda$1/1096979270.run(Unknown Source)
at java.lang.Thread.run(Thread.java:748)
Found 1 deadlock.
Copy the code(4) How to use ReenTrantreadWrite elock to implement an efficient and secure TreeMap?
class SafeTreeMap {
private final Map<String, Object> m = new TreeMap<String, Object>();
private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
private final Lock readLock = lock.readLock();
private final Lock writeLock = lock.writeLock();
public Object get(String key) {
readLock.lock();
try {
return m.get(key);
} finally{ readLock.unlock(); }}public Object put(String key, Object value) {
writeLock.lock();
try {
return m.put(key, value);
} finally{ writeLock.unlock(); }}}Copy the codeRecommended reading
-
ReentrantLock VS Synchronized Java series
-
ReentrantLock conditional lock conditional lock
-
ReentrantLock — Fair lock, unfair lock
-
AQS is the beginning of the Java Sync series
-
Deadknock Java Synchronization series write a Lock Lock yourself
-
Unsafe parsing of Java magic classes
-
JMM (Java Memory Model)
-
Volatile parsing of the Java Synchronization series
-
Synchronized parsing of the Java synchronization series
Welcome to pay attention to my public number “Tong Elder brother read source code”, view more source code series articles, with Tong elder brother tour the ocean of source code.
