The introduction
After learning about ReentrantLock, Semaphore, and CountDownLatch in the previous articles, there is one more important aQs-based concurrency utility class in the J.U.C package: ReentrantReadWriteLock. Read and write lock in Java interview process is a frequent topic, he involves more knowledge points, resulting in many people can not thoroughly understand him. Here are some common interview questions:
- The difference between ReentrantReadWriteLock and ReentrantLock?
- Can you implement a simple cache management with ReenTrantreadWrite Ock?
- Can you implement a simple read-write lock yourself?
- Will ReentrantReadWriteLock go hungry? If it happens, is there a better solution?
Can you all answer the questions above? If you can answer all of these questions well, then this article may not be of much help to you. If not, don’t worry, let’s analyze and answer the above questions one by one.
1. What is the difference between ReentrantReadWriteLock and ReentrantLock?
ReentrantLock is an exclusive lock. ReentrantReadWriteLock is a read-write lock. Which brings us to the next question: Are read and write locks in ReentrantReadWriteLock exclusive or shared, respectively? What was their relationship like? To understand these two issues thoroughly, it is best to analyze the source code.
1.1 ReentrantReadWriteLock Describes how to implement read and write locks in treadWritelock
ReadLock () and writeLock() are called when ReentrantReadWriteLock reads and writes locks.
public ReentrantReadWriteLock.WriteLock writeLock() { return writerLock; }
public ReentrantReadWriteLock.ReadLock readLock() { return readerLock; }
Copy the codeYou can see that two static inner classes, WriteLock and ReadLock, are used to implement locks as follows:
public static class ReadLock implements Lock, java.io.Serializable {
public void lock() { sync.acquireShared(1); // share} public voidunlock() { sync.releaseShared(1); }} public static class WriteLock implements Lock, java.io.Serializable {public voidlock() { sync.acquire(1); Private} public voidunlock() { sync.release(1); / / exclusive}} the abstract static class Sync extends AbstractQueuedSynchronizer {}Copy the codeSee here found ReentrantReadWriteLock and already a similarities and differences, the same is to use the same key to realize AbstractQueuedSynchronizer, ReentrantReadWriteLock uses two separate locks to implement AQS, and WriteLock, like ReentrantLock, uses an exclusive lock. ReadLock, like Semaphore, uses shared locks. An exclusive lock controls whether or not a thread owns the lock through the 0 and 1 states of the state variable, while a shared lock controls multiple thread access through the 0 or non-0 state variable. In this code, ReadLock and WriteLock use the same AQS. How does ReentrantReadWriteLock manage read and write locks?
1.2 ReadLock and WriteLock share variables
A read/write lock is defined as a resource that can be accessed by multiple reader threads or by one writer thread, but cannot be accessed by both the reader and writer threads.
It is easy to think of two different variables to control read and write: +1 for read locks and +1 for write variables. However, AQS does not add additional variables to ReadLock and WriteLock, and does so through a state. So how do you do that? Take a look at this code: 1. However, AQS does not add additional variables to ReadLock and WriteLock, and does so through a state. So how do you do that? Take a look at the following code:
static final int SHARED_SHIFT = 16;
static final int SHARED_UNIT = (1 << SHARED_SHIFT);
static final int MAX_COUNT = (1 << SHARED_SHIFT) - 1;
static final int EXCLUSIVE_MASK = (1 << SHARED_SHIFT) - 1;
/** Returns the number of shared holds represented in count */
static int sharedCount(int c) { return c >>> SHARED_SHIFT; }
/** Returns the number of exclusive holds represented in count */
static int exclusiveCount(int c) { return c & EXCLUSIVE_MASK; }
Copy the codeThis code is in Sync static inner class. There are two key methods sharedCount and exclusiveCount. SharedCount is the number of shared locks, and exclusiveCount is the number of exclusive locks. The shared lock is obtained by a 16-bit right shift on the C image, and the exclusive lock is obtained by a 16-bit 1 and operation. For example, if there are three read locks and one write lock, state is 0000 0000 0000 0011 0000 0000 0001. By moving 16 bits to the right (c >>> SHARED_SHIFT), recline the 3 in base 10, with 0000 0000 0000 1111 1111 1111 1111 and operation (c & EXCLUSIVE_MASK), obtain 1 in base 10. After understanding several methods, you can see why read/write sharing is implemented through a state.
There is also a problem with this, because the 16-bit maximum 1 represents 65535, so read and write locks can obtain up to 65535.
1.3 Differences between WriteLock and ReentrantLock
As mentioned above, WriteLock is also an exclusive lock, so how is it different from ReentrantLock? The biggest difference is that WriteLock not only needs to consider whether other write locks are occupied, but also needs to consider whether other read locks are occupied, whereas ReentrantLock only needs to consider whether it is occupied. Take a look at the WriteLock lock source code:
public void lock() {
sync.acquire(1);
}
public final void acquire(int arg) {
if(! TryAcquire (arG) && // Try to acquire the EXCLUSIVE lock acquireQueued(addWaiter(Node.exclusive), arg)) } protected final boolean tryAcquire(int acquires) { Thread current = Thread.currentThread(); int c = getState(); State int w = exclusiveCount(c); // Get the number of write locksif(c ! = 0) {// have a read lock or write lock.ifc ! = 0 and w == 0thenshared count ! = 0)if(w == 0 || current ! GetExclusiveOwnerThread ()) // The write lock is 0, or the thread holding the write lock is not the current threadreturn false;
if (w + exclusiveCount(acquires) > MAX_COUNT)
throw new Error("Maximum lock count exceeded");
// Reentrant acquire
setState(c + acquires); // The current thread holds the write lock, and +acquires will doreturn true;
}
if(writerShouldBlock() || ! CompareAndSetState (c, c + acquires)) // Failed to obtain the lock because the CAS operation is preempted in multi-threaded cases. If the CAS succeeds, the lock is successfully obtainedreturn false;
setExclusiveOwnerThread(current);
return true;
}
Copy the codeDoes this code look familiar? This is similar to the code used in ReentrantLock, except that the ‘exclusiveCount’ method is called to determine whether a write lock exists, and c! = 0 and w == 0 determine whether a read lock exists. AcquireQueued and addWaiter will not be explained in detail, but you can check out the previous ReentrantLock article. By now you should know the difference between ReentrantReadWriteLock and ReentrantLock.
1.4 Differences between ReadLock and Semaphore lock acquisition
WriteLock is an exclusive lock acquisition mode, and ReentrantLock is an exclusive lock acquisition mode. Take a look at the source code below:
protected final int tryAcquireShared(int unused) {
Thread current = Thread.currentThread();
int c = getState();
if(exclusiveCount(c) ! = 0 && getExclusiveOwnerThread() ! = current) // If the write lock is not equal to 0, verify that the current write lock attempts to acquire the read lockreturn- 1; int r = sharedCount(c); // Get the number of read locksif(! ReaderShouldBlock () &&r < MAX_COUNT &&compareAndSetState (c, C + SHARED_UNIT)) {// the CAS operation attempts to set the read lockif(r == 0) {// The first thread to acquire the lock for the first time, firstReader = current; firstReaderHoldCount = 1; }else if(firstReader == current) {// the current thread is the first to acquire the read lock firstReaderHoldCount++; }else{// The current thread is not the first thread to acquire the read lock, put in the thread local variable 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;
}
returnfullTryAcquireShared(current); } to decideCopy the codeThe process of trying to acquire a read lock in the above code is similar to the process of acquiring a write lock, except that the read lock can be acquired as long as it is not occupied by the write lock and does not exceed the maximum number of accesses. The write lock needs to consider whether the read lock is occupied or not. In the above code, firstReader, firstReaderHoldCount, and cachedHoldCounter all serve readHolds (ThreadLocalHoldCounter). You can obtain the number of times the current thread holds the lock. We added an Int variable to ThreadLocal to count The Times, which can be understood by their implementation:
Static final Class ThreadLocalHoldCounter extends ThreadLocal<HoldCounter> {//ThreadLocal ß public HoldCounterinitialValue() {
returnnew HoldCounter(); } } static final class HoldCounter { int count = 0; Use ID, not reference, to avoid garbage Retention final long tid = getThreadId(thread.currentThread ()); // Current thread ID}Copy the code2. Can you implement a simple cache with ReentrantReadWriteLock?
Let’s first analyze the functions that a simple cache needs to meet. In order to achieve simplicity, we do not consider complex factors such as cache expiration policy.
- Caching provides two main functions: read and write.
- If there is data in the cache, the data is returned immediately.
- If no data exists in the cache, obtain the data from other sources and write the data to the cache at the same time.
- While writing to the cache, to prevent other threads from retrieving data that does not exist in the cache at the same time, other reader threads need to block. Here we use ReentrantReadWriteLock to implement the above functionality:
public static void ReentrantReadWriteLockCacheSystem() {// Cache size is set to 4 for simplicity. Map<String, String> cacheMap = new HashMap<>(4); ReentrantReadWriteLockreadWriteLock = new ReentrantReadWriteLock();
for(int i = 0; i < 20; Final String Key = string.valueof (I % 4); Thread thread = new Thread(newRunnable() {
@Override
public void run() {try {//① Obtain read lock when reading cachereadWriteLock.readLock().lock(); String valueStr = cachemap. get(key); // The cache value does not existif(valueStr == null) {//③ Try to obtain the write lock after releasing the read lockreadWriteLock.readLock().unlock(); Try {//④ get write lock to write nonexistent key,readWriteLock.writeLock().lock();
valueStr = cacheMap.get(key);
if (valueStr == null) {
valueStr = key + " --- value"; cacheMap.put(key, valueStr); // Write system.out.println (thread.currentThread ().getName() +" --------- put "+ valueStr); } // ⑥ lock degradation, to avoid being preempted by other writer threads to update the value again, to ensure the atomicity of this operationreadWriteLock.readLock().lock();
System.out.println(Thread.currentThread().getName() + " --------- get new " + valueStr);
} finally {
readWriteLock.writeLock().unlock(); //⑤ release write lock}}else {
System.out.println(Thread.currentThread().getName() + " ------ get cache value");
}
} finally {
readWriteLock.readLock().unlock(); }}}, string.valueof (I)); thread.start(); }}Copy the codeFirst, the thread attempts to acquire the data by acquiring the read lock (1). If there is a value, the thread reads and releases the read lock (2). If no value exists, the acquired read lock ③ is first released, and then the acquired write lock ④ is attempted. After acquiring the write lock, check the value again, because there may be other write locks that have updated the value, then just read and release the write lock ⑤. (6) This step of lock degradation is to directly preempt the read lock, so as to avoid being preempted by other writer threads when acquiring the read lock again after the release of the write lock, so as to ensure the atomicity of the read data. Then perform ⑤ release the write lock and ② release the read lock.
After the command is executed, the following output is displayed. The output may vary each time:
//1 --------- put 1 --- value //1 --------- get new 1 --- value //0 --------- put 0 --- value //0 --------- get new 0 --- value //9 ------ get cache value //4 ------ get cache value //2 --------- put 2 --- value //2 --------- get new 2 --- value //11 --------- put 3 --- value //11 --------- get new 3 --- value //5 ------ get cache value //13 ------ get cache value //6 ------ get cache value //8 ------ get cache value //7 ------ get cache value //3 --------- get new 3 --- value //10 ------ get cache value //12 ------ get cache value //14 ------ get cache value //15 ------ get cache value //16 ------ get cache value //17 ------ get cache value //18 ------ get cache value //19 ------ get cache valueCopy the code3. Can you implement a simple read/write lock yourself?
After the initial analysis and use of the read-write lock principle above, can you now implement a simple read-write lock yourself? Here is a step-by-step process for implementing a simple read/write lock, which you can do yourself.
- 1 Define a read/write lock share variable state
- 2 State The higher 16 bits are the number of read locks, and the lower 16 bits are the number of write locks. Try to emulate the implementation of ReentrantReadWriteLock
- 3 Check whether there is a write lock when obtaining a read lock. If there is a write lock, wait for it. If there is no read lock, increase the number of read locks by 1
- 4 The number of read locks released is reduced by 1, notifying all waiting threads
- 5 When obtaining a write lock, check whether both the read lock and the write lock exist. If yes, wait for it. If no, increase the number of write locks by 1
- 6 Release write lock number minus 1, notify all waiting threads I give the implementation code as follows:
public class MyReadWriteLock { private int state = 0; Define a read/write lock share variable state //2. State 16 bits high is the number of read locks private intGetReadCount() {
returnstate >>> 16; } //2. The lower 16 bits are the number of write locksGetWriteCount() {
returnstate & ((1 << 16) - 1); Public synchronized void lockRead() throws InterruptedException{public synchronized void lockRead() throws InterruptedException{while (GetWriteCount() > 0) {
wait(a); } System.out.println("lockRead ---" + Thread.currentThread().getName());
state = state + (1 << 16);
}
//4. 释放读锁数量减1，通知所有等待线程
public synchronized void unlockRead() { state = state - ((1 << 16)); notifyAll(); } //5. Check whether both the read lock and the write lock exist when obtaining a write lock. If yes, wait.while (GetReadCount() > 0 || GetWriteCount() > 0) {
wait(a); } System.out.println("lockWriters ---" + Thread.currentThread().getName());
state++;
}
//6. 释放写锁数量减1，通知所有等待线程
public synchronized void unlockWriters(){ state--; notifyAll(); }}Copy the code4. Will write hunger occur with read/write locks? If it happens, is there a better solution?
In the read/write process, write operations have priority. Do not wait for write operations because too many read operations are performed. As a result, data cannot be updated and write hunger occurs. Now let’s think about the simple read-write lock we implemented above. Can we do this? The answer is obvious: notifyAll does not guarantee write precedence when both reader and reader threads are waiting. So how can we improve that in this case?
Here I do this by adding an intermediate variable that logs a write request before acquiring the write lock, so that notifyAll checks whether a write request exists first and gives the write operation priority if it does. The code is as follows:
public class MyReadWriteLock { private int state = 0; State private int writeRequest = 0; // Record the number of write requests //2. State Indicates the number of read locksGetReadCount() {
returnstate >>> 16; } //2. The lower 16 bits are the number of write locksGetWriteCount() {
returnstate & ((1 << 16) - 1); } //3. Check whether there is a write lock before acquiring the read lock. Public synchronized void lockRead() throws InterruptedException{// Write is preempted if the number of write locks is greater than 0 or the number of write requests is greater than 0while (GetWriteCount() > 0 || writeRequest > 0) {
wait(a); } System.out.println("lockRead ---" + Thread.currentThread().getName());
state = state + (1 << 16);
}
//4. 释放读锁数量减1，通知所有等待线程
public synchronized void unlockRead() { state = state - ((1 << 16)); notifyAll(); } //5. Check whether both the read lock and the write lock exist when obtaining the write lock. Public synchronized void lockWriters() throws InterruptedException{writeRequest++; // Write request +1while (GetReadCount() > 0 || GetWriteCount() > 0) {
wait(a); } writeRequest--; 1 system.out.println ("lockWriters ---" + Thread.currentThread().getName());
state++;
}
//6. 释放写锁数量减1，通知所有等待线程
public synchronized void unlockWriters(){ state--; notifyAll(); }}Copy the codeCan you test the above code to see if the write request is executed first? Now let’s put this into the context of ReentrantReadWriteLock. It’s clear that treadwritelock also has write request hunger, because write requests are queued, both fair and unfair. There is no guarantee that the write lock will be acquired, so as long as the read lock is occupied, write hunger will occur. So doesn’t the JDK offer any good solutions to this problem? There is, of course, an improved read/write lock added to JDK8 called StampedLock, which will be covered in more detail in the next article.