Concurrent programming is an important means to improve the running efficiency and response speed of programs. Under the condition of multi-CPU, concurrent programming can make the hardware be used to a greater extent. Because the CPU will schedule the operation of multithreading at any time in the concurrent environment, the order of execution of each instruction in the thread is uncertain, and it is difficult to reproduce and locate problems. If developers understand how concurrency works, they can avoid concurrency problems by addressing them where they might be.
Concurrency knowledge system is very large, involving a series of knowledge points such as memory model, concurrent container, thread pool, etc. Excellent concurrent programs also have high requirements on performance and activity, so it is not easy to understand concurrency. To write a good concurrent program, not only need to understand the principle of concurrency, but also need engineering practice, great oaks grow from little acorns, let’s explore concurrent programming together.
First, atomicity, visibility and order
1.1 atomic
When it comes to concurrency, a classic example is to start two threads on a number loop +1 at the same time, as shown below. Both threads T1 and T2 will loop 10,000 times a++. Ideally, a should end up at 20,000, but after running it, a is always less than 20,000, and the result is different every time. Why?
public class Test {
public static int a = 0;
public static void main(String[] args) {
Runnable r = () -> {
for (int i = 0; i < 10000; i++) { a++; }}; Thread t1 =new Thread(r);
Thread t2 = new Thread(r);
t1.start();
t2.start();
try {
// The program itself is running on the main thread, so the main thread needs to wait for t1 and T2 to finish before fetching a
t1.join();
t2.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("a: "+ a); }}Copy the codeThere are two issues involved:
- One is atomicity. To clarify the definition of an atomic operation, an operation is called an atomic operation if it is either not performed or if it is completely performed without interruption. In the above procedure we are going to
a++As an atomic operation, which actually consists of multiple atomic operations and is not an atomic operation itself. - The second is visibility. If thread T1 changes the value of A, t2 may not be aware of it.
Visibility is covered in 1.2, but here we start with atomicity. A++ looks like an atomic operation, but in fact a++ requires 3 CPU instructions to be atomic.
Instruction 1: load variable A from memory to CPU register Instruction 2: change the value of register A to A +1 Instruction 3: write the result to memoryCopy the codeIn concurrent cases, thread switching may occur at the end of any CPU instruction. For example, when T1 and T2 are running together, the following situation may occur.
T1 thread reads a value of 0 t1 thread pairs the value in register +1 to get 1 ---------- thread switches ---------- T2 thread reads a value of 0 from memory T2 thread pairs the value in register +1 to get 1 T2 thread writes 1 to memory ---------- thread switch ---------- T1 thread writes 1 to memoryCopy the codeYou can see that in a concurrent environment, the value read from memory by a thread may not be the latest data, which explains why the results of the program are always less than 20000. To solve this problem, simply make a++ atomic, using the synchronized keyword to atomize a block of code, also known as a synchronized block, as shown below.
synchronized (Test.class) {
a++;
}
Copy the codeThe synchronized code block uses test. class as a mutex. Any thread must acquire the lock before entering the block. If it does not acquire the lock, it must wait for the thread that currently holds the lock to release the lock. The test. class lock is used to protect a shared variable that can only be accessed by one thread at a time.
If you add a shared variable b that has nothing to do with A, can you also use test.class to protect it? The answer is no, if the same lock is used to protect both of them, then the test. class lock must be obtained before either A or B is modified. As a result, access to A cannot access B at the same time, but the two variables are not related, but reduce operation efficiency.
However, B can be protected by another lock, and since any object in Java can be used as a lock, you can simply create a new final object to protect B, as shown below.
public class Test {
public static int b = 0;
public static final Object lock = new Object();
public static void main(String[] args) {
Runnable r = () -> {
for (int i = 0; i < 10000; i++) {
synchronized(lock) { b++; }}}; . }}Copy the code1.2 Visibility and CPU caching
The visibility problem is that when a thread changes a shared variable, another thread cannot perceive the change. This problem is caused by the CPU cache. To balance the gap between the CPU and the memory, the CPU introduces the cache cache as the middle layer. When the CPU reads data from the memory, it reads the data into the cache. Finally, write the data from the cache to memory at the right time, which is out of the developer’s control.
With a single-cpu CPU, the CPU has only one cache. Therefore, multiple threads operate on the same cache without visibility problems. In a multi-core CPU, where each CPU has a cache, it is possible for two threads to read and write from their own cache, causing visibility problems.
To illustrate the visibility problem, the child thread T1 will run until flag is true, but the main thread will change flag to false after 500ms. It looks like the child thread will only run for 500ms, but the reality is that the child thread will run forever. In other words, the main thread’s modification of the flag is invisible to the child threads.
public class Test {
private static boolean flag = true;
private static int i = 0;
public static void main(String[] args) throws InterruptedException {
Runnable r1 = () -> {
while (flag) {
i++;
}
System.out.println("Child thread terminated");
};
Thread t1 = new Thread(r1);
t1.start();
Thread.sleep(500);
flag = false;
System.out.println("End of Main Thread"); }}Copy the codeTo solve this problem, use the volatile keyword to modify the flag variable.
The volatile keyword indicates that a variable is volatile, making it visible in an abstract way. As a high-level language keyword, volatile shields the underlying hardware from inconsistencies. It may have different implementations in different environments, but as high-level language developers, we need only understand what volatile means at the abstract level.
As mentioned earlier, the CPU cache is written to memory at the appropriate time, so the main thread changes to the flag variable will be written to memory after some time, even if it is not volatile. So why does the child thread never feel the flag change?
It is reasonable to suspect that the child thread in the while(Flag) loop has been reading the flag variable from the CPU cache rather than retrieving it from memory. To test this guess, try adding some code to the while(flag) loop, as shown below.
public class Test {
private static boolean flag = true;
private static int i = 0;
public static void main(String[] args) throws InterruptedException {
Runnable r1 = () -> {
while (flag) {
i++;
try {
Thread.sleep(50);
System.out.println("...");
} catch (InterruptedException e) {
e.printStackTrace();
}
}
System.out.println("Child thread terminated");
};
Thread t1 = new Thread(r1);
t1.start();
Thread.sleep(500);
flag = false;
System.out.println("End of Main Thread"); }}Copy the codeAfter running, it is found that the child thread stops after running about 500ms, indicating that the child thread has obtained the value of Flag in the memory at a certain time, confirming our guess. This means that if volatile is not used, the cache and memory values will be synchronized, but the timing is uncertain, which is why many concurrency bugs are hard to trace.
At this point, you might wonder about the 1.1 example, where the synchronized keyword makes a++ atomicity, but does not use volatile to modify a, and if a is not visible, the result should be less than expected.
But the reality is that the program ends up with correct results, which are related to the Java Memory Model (JMM), which guarantees visibility of variables in atomic operations, as discussed in Section 2.
1.3 Orderliness and instruction rearrangement
Instruction reordering refers to the reordering of CPU instructions by the compiler in order to improve the efficiency of the program without affecting the results. Even if there are dependencies between instructions, the compiler ensures that the results are not affected.
In a single-threaded environment, reordering does not affect the results, but in a multi-threaded environment it is a hidden danger. For example, take the singleton pattern of double nulling, which has the following code. Suppose thread A and thread B run to the synchronized code block at the same time, thread A successfully obtains the lock and creates A Singleton. After thread A releases the lock, thread B preempts the lock and enters the synchronized code block. Then thread B finds that the Singleton has been initialized and exits. If there is no instruction reordering, there is really nothing wrong with this code.
public class Singleton {
private static Singleton sInstance;
public static Singleton getInstance(a) {
if (sInstance == null) {
synchronized(Singleton.class) {
if (sInstance == null)
sInstance = newSingleton(); }}returninstance; }}Copy the codeSInstance = new Singleton(), however, may be reordered. Normally, this code is executed in this order.
Instruction 1: Allocate a block of memory Instruction 2: initialize the Singleton object on memory Instruction 3: assign the memory address to the sInstance variableCopy the codeThe order in which the instructions are rearranged might look like this.
Instruction 1: Allocate a block of memory Instruction 2: assign the address of memory to the sInstance variable instruction 3: initialize the Singleton object on memoryCopy the codeIf thread A is suspended at instruction 2 and thread B enters the getInstance() method, it will return directly if it finds that sInstance is not empty at the first nullation. However, the memory pointed to by sInstance is not initialized at this time, and problems are likely to occur when accessing sInstance. Thus, the sInstance modifier volatile is required to prohibit the associated instruction reordering.
So is there an easier way to implement singletons? Naturally, there is, if a singleton object in the system will be used, in the class initialization time directly create a singleton instance object, regardless of concurrency, its implementation is as follows.
public class Singleton {
private static class Holder {
private static Singleton INSTANCE = new Singleton();
}
private Singleton(a) {}public static Singleton getInstance(a) {
return Holder.INSTANCE;
}
Copy the codeJava memory model
The Java Memory Model (JMM) addresses the problems of atomicity, visibility, and ordering in concurrent scenarios that can lead to unpredictable results. The Volatile and synchronized keywords are used for visibility and restricted reordering of shared variables. The synchronized keyword is used to implement atomicity of code blocks. The JMM provides six happens-before rules describing the role of these two keywords in order to provide guidance to developers.
Happens-before means that if A happens-before B, the result of A is visible to B in memory order. The specific rules for happens-before are as follows.
Happens-before Indicates the subsequent locking of the synchronized mutex. Happens-before indicates the subsequent read of the volatile variable The main thread calls the child thread’s start() method happens-before the child thread’s start() method ④ all happens-before other threads successfully join() the thread ⑤ The default initializer of the happens-before program for any object (⑥ happens-before) is transitive. If A happens-before B, B happens-before C, then A happens-before C
Looking back at 1.1, the use of the synchronized keyword in the code makes a++ atomicity and the A variable visible. This is because the mutex is unlocked happens-before, so that the next thread that holds the mutex knows what the previous thread did to A.
Mutex
Mutexes are used to guarantee atomicity of code blocks and are actually used to protect one or a series of shared variables from being accessed by only one thread at a time. When a thread enters a synchronized code block, the thread needs to acquire the lock of the synchronized code block and release the lock when it exits the synchronized code block. If a thread attempts to acquire a lock and finds that the lock is occupied, the thread is suspended until the lock is acquired.
Java provides implementations of synchronized and Lock mutexes. Synchronized is a Java keyword and a language feature, but it wasn’t very efficient before Java6. The Lock series, written by concurrency guru Doug Lea, added Java and packaged it in Java5.
3.1 synchronized
3.1.1 Basic Usage
Synchronized is used to modify methods or code blocks and implicitly implements locking/unlocking operations, automatically locking when a thread enters a method or code block and unlocking when it exits. The following is an example of its use.
public class Sample {
private static final Object lock = new Object();
// 1. Modify the code block
public void fun1(a) {
synchronized(lock) {
/ /...}}// 2. Modify non-static methods
public synchronized void fun2(a) {
/ /...
}
// 3. Modify static methods
public synchronized static void fun3(a) {
/ /...}}Copy the codeYou can see that synchronized only needs to specify mutexes when modifying code blocks, whereas mutexes are implicitly added by Java when modifying methods. When modifying a static method, the mutex is the class object of the current class, as in sample.class. When modifying a nonstatic method, the mutex is the current object instance.
3.1.2 Lock selection
The first thing you need to know is what objects are suitable for mutex. Since mutex is used to protect shared variables, the mutex should have the same lifetime as the shared variables it protects and cannot be assigned during execution.
Implicitly added locks follow this rule when synchronized modifies static methods. When synchronized modifies static methods, its lock is the class object of the current class, which is created at the start of the program and cannot be changed.
For example, the following program, staticList as a static variable, has the same lifetime as the mutex sample.class for the entire program.
public class Sample {
private static List<String> staticList = new ArrayList<>();
public synchronized static void addString(String s) { staticList.add(s); }}Copy the codeWhen synchronized modifies a nonstatic method, its lock is the current object this. Because non-static methods are used to operate on non-static members, such as the mList in the following example, and the life of a non-static member is the life of the current object this.
public class Sample {
private List<String> mList;
public Sample(a) {
mList = new ArrayList<>();
}
public synchronized void addString(String s) { mList.add(s); }}Copy the codeSynchronized static methods are mutually exclusive, because the mutex of a synchronized static method is the same object. If the resources to be protected are different among static methods, the running efficiency will only be affected. The same applies to synchronized modification of non-static methods.
The sample. class lock protects two different resources. How can I change it?
public class Sample {
private static List<String> staticList1 = new ArrayList<>();
private static List<String> staticList2 = new ArrayList<>();
public synchronized static void addString1(String s) {
staticList1.add(s);
}
public synchronized static void addString2(String s) { staticList2.add(s); }}Copy the codeIn general, a mutex should correspond to a protected resource one by one. The simplest way to do this is to treat the protected object itself as a mutex, as shown below.
public class Sample {
private static final List<String> staticList1 = new ArrayList<>();
private static final List<String> staticList2 = new ArrayList<>();
public static void addString1(String s) {
synchronized(staticList1) { staticList1.add(s); }}public static void addString2(String s) {
synchronized(staticList2) { staticList2.add(s); }}}Copy the codeYou can see that in the new example, we use final to modify staticList1 and staticList2. Why? This relates to the principle of locking a thread. When a program locks a thread, it actually writes the thread’S ID into the lock object, so the lock object should not be reassigned at runtime. If the lock is reassigned at run time (for example, staticList1 above points to a new object), it is equivalent to using multiple locks to protect a resource and cannot achieve mutual exclusion. Objects modified by final must be initialized and cannot be reassigned to qualify as locks.
3.1.3 Thread “wait-notification” mechanism
If the fun() operation condition canExecute() is not met, we might wait in a loop until canExecute() returns true before running the following logic.
public class Sample {
private boolean execute = false;
public void fun(a) throws InterruptedException {
while(! canExecute()) { Thread.sleep(10);
}
/ /...
}
private synchronized boolean canExecute(a) {
return execute;
}
public synchronized void setExecute(a) {
execute = true; }}Copy the codeThe problem is that threads sleep for a fixed amount of time. If the value is too large, the thread cannot start running as soon as the running condition is met. If this value is too small, the thread will constantly call the synchronous method canExecute() to determine the current state, wasting running resources. Is there a way to put a thread that does not meet the running condition into hibernation (in which the thread consumes no running resources) and start running as soon as the condition is met? This is the wait-notification mechanism of threads.
All Java objects have wait(), notify(), and notifyAll() methods, which are used by objects as mutex. Together with synchronized, they implement the “wait-notification” mechanism of threads. These three methods must be executed in a synchronized block. Here’s how these three methods work.
- Wait (): Used to sleep the current thread.Mutex can be called if the current run condition is not met
wait()Method gives up the mutex and goes to sleep. The thread is then queued up for the mutex until it is woken up by another thread. - Notify (): Wakes up a thread in the mutex wait queue.Can be called when the running condition of the thread in the waiting queue is met
notify()Method wakes up a thread in the wait queue randomly, and the awakened thread then fights for the mutex. - NotifyAll (): Wakes up all threads in the mutex wait queue.Due to the
notify()Method to wake up the thread is random, may not really meet the running conditions of the thread, so the actual development of the basic usenotifyAll(), let all the threads in the waiting queue compete for the mutex.
For a simple example, the code looks like this. Thread T1 runs tryExecute(), finds that mShouldExecute is false, and calls wait() to go to sleep. After t2 sleeps for 3 seconds, it sets mShouldExecute to true and calls notifyAll() to notify the threads in the waiting queue. After T1 wakes up, it finds that the running conditions are met and continues to execute.
public class Sample {
private boolean mShouldExecute = false;
public void tryExecute(a) throws InterruptedException {
synchronized (this) {
while(! mShouldExecute) { System.out.println("tryExecute wait..."); wait(); } realExecute(); }}private void realExecute(a) {
System.out.println("realExecute");
}
public void setExecute(a) {
synchronized (this) {
mShouldExecute = true; notifyAll(); }}public static void main(String[] args) {
Sample sample = new Sample();
Thread t1 = new Thread(() -> {
try {
sample.tryExecute();
} catch(InterruptedException e) { e.printStackTrace(); }}); Thread t2 =new Thread(() -> {
try {
Thread.sleep(3000);
sample.setExecute();
} catch(InterruptedException e) { e.printStackTrace(); }}); t1.start(); t2.start(); }}Copy the codeThe mutex in this program is the current object this, so we omit this when we call wait() and notifyAll(). We should write this.wait() and this.notifyall ().
The tryExecute() method uses the loop while (! MShouldExecute), this is because t1 does not immediately execute notifyAll() when thread T2 calls notifyAll(), but fights for mutex. It is possible that when a mutex is contested, the running condition is not satisfied, so you need to rejudge.
A thread “wait-notification” mechanism can be used to block a queue. A blocking queue is a producer-consumer data structure. When the queue is empty, all threads trying to fetch data will sleep until other threads wake them up after successfully adding data. When the queue is full, all threads that try to add data go to sleep until the thread that successfully fetched the data wakes them up.
public class BlockingQueue<T> {
private Queue<T> mQueue;
private int mCapacity;
public BlockingQueue(int capacity) {
mQueue = new ArrayDeque<>(capacity);
mCapacity = capacity;
}
/** * Attempts to add data to the queue and sleep the current thread if the queue is full */
public void offer(T t) throws InterruptedException {
synchronized (this) {
while(isQueueFull()) { wait(); } mQueue.offer(t); notifyAll(); }}/** * Attempts to fetch queue header data, if the queue is empty then sleep the current thread */
public T take(a) throws InterruptedException {
synchronized (this) {
while (isQueueEmpty()) {
wait();
}
T result = mQueue.poll();
notifyAll();
returnresult; }}/** * Check whether the queue is empty */
private boolean isQueueEmpty(a) {
return mQueue.isEmpty();
}
/** * Check whether the queue is full */
private boolean isQueueFull(a) {
returnmQueue.size() == mCapacity; }}Copy the code3.2 the Lock
Lock is used to address the drawbacks of synchronized in certain scenarios, where synchronized doesn’t work best, but Lock can easily be addressed.
- When a thread enters a synchronized modified method or block of code, it waits until the thread is finished executing or called
wait()Method to release the lock. If one thread is working on a time-consuming task, all other threads must wait for it to finish. - When synchronized is used to protect shared variables, only one thread can read or write at a time. But multiple reader threads do not conflict, if the reader threads are also mutually exclusive will affect the efficiency of the program. In this case, Lock provides a read-write Lock, ReadWriteLock.
- Called when synchronized is used to implement the wait-notification mechanism
notifyAll()Will wake up all blocked threads, cannot wake up specific threads. For example, in blocking queues in 3.1.3, if a thread executespoll()Method fetches the last data in the queue, and then only need to wake up those callsoffer(T t)The thread can, whilenotifyAll()Will wake up all threads if calledpoll()The thread of the method preempts the mutex, immediately discovers that the condition is not met, and goes to sleep again.
Lock itself is an interface. For different scenarios, Lock provides different implementation classes, as shown below.
The implementation of Lock should be able to detect the incorrect use of the Lock, such as the possibility of deadlocks or exceptions being thrown. The implementation of Lock must record the condition of the Lock and the exception type
void lock(a);
If the current thread is set to interrupted * before entering the method or during the lock acquisition process, InterruptedException is thrown and the interrupted status of the current thread is cleared */
void lockInterruptibly(a) throws InterruptedException;
/** * if the current Lock is available, get the Lock, otherwise return false ** A typical usage is as follows: ; * if (lock.tryLock()) { * try { * // manipulate protected state * } finally { * lock.unlock(); *} *} else {*/ / Alternate logic *}} */
boolean tryLock(a);
/** * Returns true if the thread has not been interrupted and the lock has been acquired within a given time * False */ if the thread has not acquired the lock after a given time
boolean tryLock(long time, TimeUnit unit) throws InterruptedException;
/** * release lock */
void unlock(a);
/** * returns a Condition variable bound to the current Lock, which is used to implement the waiting-notification mechanism for threads * threads blocked on a Condition can be woken up separately */
Condition newCondition(a);
Copy the codeLock, as an implementation of packet sending, is used differently from the synchronized keyword. Synchronized automatically locks/unlocks, and the JVM can ensure that the lock is released even if an exception occurs in a synchronized block of code. However, Lock cannot do this. When using Lock, you need to follow the following paradigm to ensure that the Lock is released when an exception is encountered, otherwise other threads will never get a chance to run.
public void fun(a) {
lock.lock();
try {
/ /...
} finally{ rtl.unlock(); }}Copy the code3.2.1 ReentrantLock
A reentrant lock means that a thread can acquire the same lock repeatedly, as shown in the following example. If a thread runs to fun1() and acquires the lock, calling fun2() will work fine without releasing the lock. Synchronized keyword is also reentrant lock, because its lock operation is essentially to write the id of the current thread in the object header of the Java object lock, indicating that the lock is occupied by the current thread, naturally reentrant.
public class Sample {
private Lock lock = new ReentrantLock();
public void fun1(a) {
lock.lock();
try {
fun2(); // fun2() also needs to get the lock
} finally{ lock.unlock(); }}public void fun2(a) {
lock.lock();
try {
/ /...
} finally{ lock.unlock(); }}Copy the codeWith the synchronized keyword, wait() and notifyAll() are used to implement the “wait-notification” mechanism for threads, and a blocking queue was implemented in 3.1.3. The problem with using wait() and notifyAll(), however, is that you can only wake up all dormant threads, not specific threads to execute based on current conditions.
The Lock interface has a method, Condition newCondition(), that creates a newCondition variable bound to the current Lock. A thread can be hibernated with the condition.await () method, and when the Condition is satisfied, the thread can be awakened with condition.signalall ().
Create two conditions. One Condition indicates that the queue is not satisfied. If the thread adds data and finds that the queue is full, then the queue is blocked. Wake up the thread blocking on this condition until data is queued; The other Condition indicates that the queue is not empty. If the thread finds the queue empty when it fetches data, it blocks on the Condition until it wakes up when data is enqueued.
public class BlockingQueue<T> {
final Lock lock = new ReentrantLock();
final Condition notFull = lock.newCondition(); // Condition: the queue is not satisfied
final Condition notEmpty = lock.newCondition(); // Condition: the queue is not empty
private Queue<T> mQueue;
private int mCapacity;
public BlockingQueue(int capacity) {
mQueue = new ArrayDeque<>(capacity);
mCapacity = capacity;
}
public void offer(T t) {
lock.lock();
try {
while (isQueueFull()) {
notFull.await();
}
mQueue.offer(t);
// After joining the queue, the notification can leave the queue
notEmpty.signalAll();
} catch (InterruptedException e) {
e.printStackTrace();
} finally{ lock.unlock(); }}private boolean isQueueFull(a) {
return mQueue.size() == mCapacity;
}
public T take(a) {
T result = null;
lock.lock();
try {
while (isQueueEmpty()) {
notEmpty.await();
}
result = mQueue.poll();
// After leaving the team, the notification can join the team
notFull.signalAll();
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
lock.unlock();
}
return result;
}
private boolean isQueueEmpty(a) {
return mQueue.size() == 0; }}Copy the code3.2.2 Read-write Lock ReadWriteLock
When the synchronized keyword is used to protect a shared variable, threads’ read operations are mutually exclusive, but multiple threads’ read operations do not cause concurrency problems. For read and write scenarios, Java provides a read and write lock, ReadWriteLock, which is an interface, as shown below.
public interface ReadWriteLock {
Lock readLock(a); // return to read lock
Lock writeLock(a); // return write lock
}
Copy the codeReadWriteLock is implemented as ReentrantReadWriteLock. As you can see from the name, this is a reentrant lock. When you call readLock() or writeLock() to obtain a read or writeLock, you return the internal variables readerLock and writerLock in ReentrantReadWriteLock, which are implementation classes for the Lock interface.
public class ReentrantReadWriteLock
implements ReadWriteLock.java.io.Serializable {
/** Inner class providing readlock */
private final ReentrantReadWriteLock.ReadLock readerLock;
/** Inner class providing writelock */
private final ReentrantReadWriteLock.WriteLock writerLock;
/** Performs all synchronization mechanics */
final Sync sync;
// Create an unfair lock by default
public ReentrantReadWriteLock(a) {
this(false);
}
public ReentrantReadWriteLock(boolean fair) {
sync = fair ? new FairSync() : new NonfairSync();
readerLock = new ReadLock(this);
writerLock = new WriteLock(this);
}
public ReentrantReadWriteLock.WriteLock writeLock(a) { return writerLock; }
public ReentrantReadWriteLock.ReadLock readLock(a) { returnreaderLock; }... }Copy the codeTake a look at ReadWriteLock’s features before using it:
- Read and write are mutually exclusive, read and write are mutually exclusive, and write and write are mutually exclusive. This means that a read lock can be held by multiple threads without a write lock.
- Read/write locks are only suitable for scenarios where there are too many reads and too few writes, such as data that is rarely modified but often searched (such as an entry). If writes are frequent, the data is held by an exclusive lock most of the time, and concurrency performance is not improved.
- The thread holding the read lock cannot acquire the write lock directly, but the thread holding the write lock can acquire the read lock. Other threads cannot acquire the read lock. In other words, a read lock cannot be upgraded to a write lock, and a write lock can be downgraded to a read lock.
- Both read and write locks implement the Lock interface, so they are both supported
tryLock()andlockInterruptibly()Methods. But only write locks support Condition; read locks do not support the use of Condition variables.
A simple example of using ReadWriteLock is as follows.
public class Sample<T> {
private ReadWriteLock readWriteLock = new ReentrantReadWriteLock();
private T mData;
public T read(a) {
readWriteLock.readLock().lock();
try {
return mData;
} finally{ readWriteLock.readLock().unlock(); }}public void write(T t) {
readWriteLock.writeLock().lock();
try {
mData = t;
} finally{ readWriteLock.writeLock().unlock(); }}}Copy the code3.2.3 StampedLock for Optimistic reading
StampedLock has three modes that support read/write functionality, and its state is composed of stamp version and the current mode. StampedLock’s method of obtaining the lock returns a stamp value, which is used to represent the current lock state. Stamp is required as a parameter when releasing and converting the lock. If it does not match the lock state, it will fail. StampedLock supports three modes: write, read, and optimistic read.
- Write mode, similar to write lock write lock. Thread calls
StampedLock.writeLock()After exclusive access to the data, the method returns a stamp indicating the lock status, calledStampedLock.unlockWrite(stamp)This stamp is required for unlocking.
The tryWriteLock() and tryWriteLock() methods also return stamp, which returns 0 on failure to acquire the lock. A read lock cannot be acquired while the lock is in write mode, and all optimistic read validations fail. 2. Read mode, which is similar to read/write lock. Stampedlock. readLock() is invoked by the thread to read the stampedlock. readLock(). Multiple threads can read the stampedlock. readLock() simultaneously. UnlockRead (stamp) is used to unlock stampedLock. unlockRead(stamp). 3. Optimistic read mode. This mode is a weakened version of read lock and does not require lock acquisition. The idea of optimistic reading is to assume that the data has not been modified during reading. Optimistic read avoids lock contention and improves throughput, but its correctness cannot be guaranteed. Therefore, after reading results, it is necessary to verify whether any thread acquired the write lock during optimistic read. Call StampedLock. Tryooptimisticread (after) optimism can be read, write mode returns nonzero if the current is not in the stamp, optimistic after reading calls validate (stamp) determine whether the result is effective.
The use of StampedLock depends on knowledge of the data, objects, and methods it protects, and should not be used for methods that cannot tolerate potential inconsistencies if the results of optimistic reads are not validated. StampedLock is not reentrant, so threads that acquire locks should not call other methods that attempt to acquire locks.
The Point class has three methods: move(…) Method describes the general flow of write mode. DistanceFromOrigin () describes the flow of optimistic read mode. If optimistic read data fails, a read lock is obtained for read operation. moveIfAtOrigin(…) StampedLock upgrade describes the lock upgrade of StampedLock. In normal development, the lock upgrade should be used carefully.
public class Point {
private double x, y;
private final StampedLock sl = new StampedLock();
/ / write locks
void move(double deltaX, double deltaY) {
long stamp = sl.writeLock();
try {
x += deltaX;
y += deltaY;
} finally{ sl.unlockWrite(stamp); }}/ / optimistic reading
double distanceFromOrigin(a) {
long stamp = sl.tryOptimisticRead();
double currentX = x, currentY = y;
if(! sl.validate(stamp)) {// If the data is out of date, the read lock is acquired
stamp = sl.readLock();
try {
currentX = x;
currentY = y;
} finally{ sl.unlockRead(stamp); }}return Math.sqrt(currentX * currentX + currentY * currentY);
}
// Update the lock
void moveIfAtOrigin(double newX, double newY) {
long stamp = sl.readLock();
try {
while (x == 0.0 && y == 0.0) {
long ws = sl.tryConvertToWriteLock(stamp);
if(ws ! =0L) {
// The updated stamp value needs to be updated
stamp = ws;
x = newX;
y = newY;
break;
} else{ sl.unlockRead(stamp); stamp = sl.writeLock(); }}}finally{ sl.unlock(stamp); }}}Copy the codeThread-safe variables
Mutex is used to protect shared variables, but there is no need to protect a variable if it cannot be accessed by multiple threads at the same time, such as local variables within a method. According to the Java Virtual Machine specification, each thread contains three blocks of memory: program counter, virtual machine stack, and local method area. The virtual machine stack is used to store method calls of the thread. When a method is called, the thread pushes a stack frame into the virtual machine stack. When this method is called, the corresponding stack frame is ejected from the virtual machine stack, and the local variable table is stored in the stack frame.
In most Java virtual machine implementations, the virtual machine stack size is fixed, and only a few JVMS have virtual machine stacks that are scalable. With a fixed stack size, if you make a recursive call that is too deep, you can generate StackOverflow exceptions because the virtual stack does not have enough room to store a stack frame.
Of course, shared variables are not necessarily thread-unsafe. Here are three thread-safe variables that can be implemented in different ways.
4.1 Immutable variables
Reading and writing shared variables can be problematic in concurrent environments, but read-only without writing has no concurrency problems. If a shared variable does not change after initialization, it is a thread-safe variable. We know that variables modified by the final keyword must be initialized and will not change after initialization. Are shared variables modified by the final keyword thread-safe? Let’s take two examples.
To start with, the class has two shared variables of type String and int that are initialized in the constructor and cannot be changed, so they are thread-safe.
public class Sample {
private final String mString;
private final int mInt;
public Sample(String s, int i) {
mString = s;
mInt = i;
}
public String getString(a) {
return mString;
}
public int getInt(a) {
returnmInt; }}Copy the codeIn the second example, although the Sample modifies mTest as final, final only means that the memory address of the mTest object is immutable and the value in the object is mutable. Therefore, after the variable mTest is obtained from getTest(), String and int in mTest can be reassigned. The String and int variables in the Test class are not final, so Sample is not thread-safe.
public class Sample {
private final Test mTest;
public Sample(Test test) {
this.mTest = test;
}
public Test getTest(a) {
return mTest;
}
static class Test {
public String s;
public inti; }}Copy the codeIf you want the objects of a class to be immutable, all properties of the class should be final, and if a property is not of a primitive type, the class should also have all properties final.
Note that the String type is immutable, and instead of modifying the original String, a new String is generated when the subString() or replace() methods of String are called. But StringBuilder and StringBuffer are mutable, and the append() method is called on the original object.
4.2 Atomic class Variables
Synchronized was our solution to a++ atomicity in 1.1, but locking/unlocking operations and thread switching were costly. But there is a type of variable called atomic class variable, whose methods are themselves atomic operations, which are supported by CPU instructions, so it is very efficient.
4.2.1 Basic variable atomic class
AtomicBoolean, AtomicInteger, AtomicLong correspond to the primitive Boolean, Integer, and Long. These three atomic classes share the following methods:
// Expect updates to update only if the current atomic variable value is expected, returning true on success and false on failure
boolean compareAndSet(expect, update);
// Update the atomic variable to newValue and return the previous value
boolean/int/long getAndSet(newValue);
// Updates the atomic variable's value to newValue, but is not necessarily immediately visible to other threads
void lazySet(newValue);
Copy the codeOf course, AtomicInteger and AtomicLong have other methods, which usually come in pairs, such as getAndIncrement() and incrementAndGet(). Both methods are incremented, with the only difference being whether they return the pre-update or post-update value. If the 1.1 example were implemented using an atomic class, it would only be necessary to change a to the atomic variable a = new new AtomicInteger(0) and a++ to a.getandincrement () to get the correct result.
GetAndAdd () does the same thing but returns the value before the update
int/long addAndGet(int delta);
Prev and x are computed by IntBinaryOperator. The IntBinaryOperator method must have no side effects
int/long accumulateAndGet(x, IntBinaryOperator);
// IntUnaryOperator evaluates prev to a new value. IntUnaryOperator's method must have no side effects
int/long updateAndGet(IntUnaryOperator updateFunction);
Copy the codeThe atomic class implements atomicity through the CPU-supplied CAS instruction, which itself has atomicity. CAS stands for Compare And Swap. This instruction compares the value of a shared variable with the expected value, And updates the value of the shared variable only when the two values are equal. The atomic compareAndSet(Expect, Update) method is native compareAndSwapXXX(…). Method.
CAS+ spin is a great tool for concurrent programming, and is widely used in Java and packet sending. “spin” is essentially trying the CAS operation through a loop until it succeeds. For example, AtomicInteger’s getAndAdd(delta) method, which actually calls the getAndAddInt(Object var1, Long Var2, int var4) method in Unsafe, as shown below. Because the value of the atomic class may be modified by another thread before the CAS instruction is performed, you need to loop through the current value of the atomic variable and call compareAndSwapInt(…) Until you succeed.
public final int getAndAddInt(Object var1, long var2, int var4) {
int var5;
do {
var5 = this.getIntVolatile(var1, var2);
} while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
return var5;
}
Copy the code4.2.2 Atomic Array classes
The array atom classes include AtomicIntegerArray, AtomicLongArray, and AtomicReferenceArray, all of which have similar methods. Take the AtomicIntegerArray as an example. It has two constructors, one passing in the array length, where all the values in the array are initialized to 0, and the other constructor passing in an int array directly.
public AtomicIntegerArray(int length) {
array = new int[length];
}
public AtomicIntegerArray(int[] array) {
// Visibility guaranteed by final field guarantees
this.array = array.clone();
}
Copy the codeThe AtomicIntegerArray method is used with an array subscript I, as opposed to an AtomicInteger method. AtomicLongArray similarly. AtomicReferenceArray is an array of atomic references, which will be explained in 4.2.3. When using the atomic array class, you only need to add subscripts.
boolean compareAndSet(int i, int expect, int update);
int getAndAdd(int i, int delta);
int getAndIncrement(int i); .Copy the code4.2.3 Atomic reference classes
The reference atom class is an AtomicReference, so does it encapsulate the change reference operation as an atomic operation? Of course not! Because changing a reference is atomic, assigning a reference takes only one instruction, and it is not interrupted by the CPU. This can also be seen from AtomicReference’s set(V newValue) method, which simply assigns values to references.
public final void set(V newValue) {
value = newValue;
}
Copy the codeThe value of AtomicReference therefore lies in its CAS directive, which prevents other threads from tampering with the value of the reference.
boolean compareAndSet(V expect, V update);
Copy the codeUsing AtomicReference to note if there is an ABA problem, first explain what is an ABA problem. When we used AtomicInteger previously, we treated the value of the atomic class as its state. When we called compareAndSet(A, update), as long as the value of the atomic class was equal to A, it was considered that the atomic class had not been modified, but this judgment was A danger. If the T1 thread changes the value from A to B and then from B to A before calling compareAndSet(A, update), the atomic class’s state has changed, even though its value has not changed. The T1 thread then executes CAS if it finds the value unchanged, but the change in the state of the atomic class causes some unexpected errors.
The Wikipedia CAS entry [Ref. 2] describes a possible ABA problem without a stack lock. To explain stackless, if you need to implement a stack that supports concurrency, what are the ways you can do it? The obvious way to do this is to lock the pop() and push() methods, which is crude and error-free, but inefficient. A better approach is to use CAS+ spin, which does not require locking. Data structures implemented through CAS+ spin are also referred to as lockless structures.
For example, the data structure of non-locked stack is linked list, and a pointer head points to the top of the stack. The push and pop operations of the stack depend on HEAD. When head points to null, the stack is empty.
To ensure atomicity when threads operate on head, head needs to be defined as AtomicReference AtomicReference
, with no stack locking code shown below.
Here’s how CAS+ spin works, using the push operation as an example. As shown in the push() method below, after creating pushNode, push pushNode.next to head, and CAS to point head to pushNode. However, the head may be modified before CAS is executed, so if CAS fails, reassign to pushNode and try the CAS again until it succeeds.
public class ConcurrentStack {
private AtomicReference<StackNode> headReference;
public ConcurrentStack(a) {
headReference = new AtomicReference<>(null);
}
public void push(Integer i) {
StackNode pushNode = new StackNode(i);
while (true) {
StackNode head = headReference.get();
pushNode.next = head;
// Other threads may have changed the value of head here
if (headReference.compareAndSet(head, pushNode)) {
break; }}}public StackNode pop(a) {
while (true) {
StackNode head = headReference.get();
if (head == null) {
return null;
}
StackNode newHead = head.next;
// Other threads may have changed the value of head here
if (headReference.compareAndSet(head, newHead)) {
returnhead; }}}private static class StackNode {
public int value;
public StackNode next;
public StackNode(Integer i) { value = i; }}}Copy the codeUnder what circumstances does an ABA problem occur without a stack lock? Suppose the current stack looks like this.
At this point, the T1 thread calls pop(), but the thread is suspended before CAS is executed, stopping at the comment for the pop() method above. Head points to StackNode4 and newHead points to StackNode3.
However, the T2 thread calls pop() twice to get StackNode4 and StackNode3 off the stack, and then creates another node with a value of 4, StackNode4*, and pushes it onto the stack. As you can see, StackNode4 and StackNode3 are floating off the stack, but stacknode3. next still points to StackNode2. The temporary variable head in the T1 thread points to StackNode4 and the temporary variable newHead points to StackNode3.
If, for some reason, the address of StackNode4* is the same as the head in the T1 thread (StackNode4), then the T1 thread will get the time slice and assume that the head has not changed and will execute CAS, even though the stack structure is different from before T1 was suspended. The stack is shown below after T1 execution, which is not consistent with expectations.
The question is, can the address of StackNode4* be the same as StackNode4? To put it another way, can the new object have the same address as the previous object? Of course it’s possible! There are mainly the following two situations:
① This class uses the free element mode. All objects with the same value are actually one. However, StackNode cannot use the free mode because the next value of each node is different. Class 2 uses object cache pool. Take StackNode as an example. The nodes that are pop are cached and new nodes need to be obtained from the cache pool first.
Now that we understand the causes of ABA problems, we simulate them in code. Since this scenario is difficult to simulate, we chose to delay the head in the pop() method of the stack to ensure that other threads can modify the head before CAS, and the ConcurrentStack looks like this.
public class ConcurrentStack {omit other code......public StackNode pop(long t) {
while (true) {
StackNode head = headReference.get();
if (head == null) {
return null;
}
StackNode newHead = head.next;
try {
Thread.sleep(t);
} catch (InterruptedException e) {
e.printStackTrace();
}
if (headReference.compareAndSet(head, newHead)) {
returnhead; }}}}Copy the codeThen modify the StackNode class, cache the recovered StackNode object through ConcurrentHashMap, and obtain the StackNode object using the obtain(Integer I) method.
public class StackNode {
public int value;
public StackNode next;
private static ConcurrentHashMap<Integer, StackNode> mCache = new ConcurrentHashMap<>();
public static StackNode obtain(Integer i) {
StackNode stackNode = mCache.remove(i);
if (stackNode == null) {
stackNode = new StackNode(i);
}
return stackNode;
}
public static void recycle(StackNode stackNode) {
mCache.putIfAbsent(stackNode.value, stackNode);
}
private StackNode(Integer i) { value = i; }}Copy the codeThen run the following code test and you will find that the result without locking is not as expected. The comments in the code describe the process of each step in detail and will not be repeated.
public class Main {
public static void main(String[] args) throws InterruptedException {
ConcurrentStack concurrentStack = new ConcurrentStack();
StackNode3->StackNode2->StackNode1->StackNode0
for (int i = 0; i < 5; i++) {
concurrentStack.push(i);
}
// Enable popThread, sleep for a while before CAS, and let another thread modify the stack
Thread popThread = new Thread(() -> {
concurrentStack.pop(1000);
});
// Open abaThread, pop StackNode4 and StackNode3, and recycle StackNode4
// Push StackNode4, normally stack 4->2->1->0
// When popThread continues to execute CAS after sleep, the stack header is StackNode4
// So popThread assigns the headReference to the StackNode3 that has been popped
StackNode3. Next refers to StackNode2, and the stack is 3->2->1->0
Thread abaThread = new Thread(() -> {
StackNode.recycle(concurrentStack.pop(0));
concurrentStack.pop(0);
concurrentStack.push(4);
});
popThread.start();
Thread.sleep(500);
abaThread.start();
popThread.join();
// Check the stack result
StackNode s;
System.out.print("Current stack is:");
while ((s = concurrentStack.pop(0)) != null) {
System.out.print(s.value + "- >"); }}}Copy the codeTo solve this problem, AtomicStampedReference is provided in the package, which records the current version of an atom class through stamp and updates the version each time it is modified.
4.3 ThreadLocal
ThreadLocal, also known as thread-local variables, stores a variable for each thread. Each call to threadlocal-set (value) or threadlocal-get () operates on variables corresponding to the current thread, so ThreadLocal is thread-safe.
4.3.1 Basic Usage
Java provides an example of setting an ID for each thread through ThreadLocal, as shown below.
public class ThreadId {
// Set the thread ID by atomic variable
private static final AtomicInteger nextId = new AtomicInteger(0);
// Override the initialValue() method of ThreadLocal to initialize variables corresponding to each thread
private static final ThreadLocal<Integer> threadId = new ThreadLocal<Integer>() {
@Override
protected Integer initialValue(a) {
returnnextId.getAndIncrement(); }};// Returns the current thread's unique ID, assigning it if necessary
public static int get(a) {
returnthreadId.get(); }}Copy the codeWhen it was new ThreadLocal rewrote the initialValue () method, the effect of this method is that if a thread calls a ThreadLocal. The get () found that the value is null, it invokes the initialValue () to initialize the thread corresponding variables.
public T get(a) {
Thread t = Thread.currentThread();
ThreadLocalMap map = getMap(t);
if(map ! =null) {
ThreadLocalMap.Entry e = map.getEntry(this);
if(e ! =null) {
T result = (T)e.value;
returnresult; }}return setInitialValue();
}
private T setInitialValue(a) {
T value = initialValue();
Thread t = Thread.currentThread();
ThreadLocalMap map = getMap(t);
if(map ! =null)
map.set(this, value);
else
createMap(t, value);
return value;
}
Copy the codeThreadLocal also provides a static constructor withInitial(Supplier
supplier), also used to set an initial value for each thread of ThreadLocal.
ThreadLocal<Integer> threadId = ThreadLocal.withInitial(new Supplier<Integer>() {
@Override
public Integer get(a) {
returnnextId.getAndIncrement(); }});Copy the codeThreadLocal.withInitial(…) The SuppliedThreadLocal object is returned, which inherits ThreadLocal and overwrites the initialValue() method, essentially the same as the first initialization method.
static final class SuppliedThreadLocal<T> extends ThreadLocal<T> {
private final Supplier<? extends T> supplier;
SuppliedThreadLocal(Supplier<? extends T> supplier) {
this.supplier = Objects.requireNonNull(supplier);
}
@Override
protected T initialValue(a) {
returnsupplier.get(); }}Copy the code4.3.2 Implementation principle of ThreadLocal
In ThreadLocal, threads and data have a one-to-one relationship, which is reminiscent of a Map. Intuitively, it seems that ThreadLocal maintains a Map with a Key for a thread and a Value for data. This would of course also implement ThreadLocal, but in this implementation, ThreadLocal becomes the holder of Thread data and holds references to Thread, which is prone to memory leaks.
In Java implementations, threads are the data holders and ThreadLocal is the manager of thread-local variables. Thread holds a Map of type ThreadLocalMap that holds local variables for that Thread.
public class Thread {... ThreadLocal.ThreadLocalMap threadLocals =null; . }Copy the codeThreadLocalMap is an internal class of ThreadLocal. It is a Map specifically designed to maintain thread-local variables. Its Key is a weak reference to ThreadLocal and its Value is data. The question is, why implement a special Map to maintain thread-local variables? Isn’t a native HashMap sufficient? Let’s examine the source code for ThreadLocalMap with some questions.
Member variables and constructors ThreadLocalMap hold all entities through Entry[] table. The entity Entry inherits a weak reference to ThreadLocal, and the value in the Entry holds the variables associated with the ThreadLocal by the current thread. We know that when an object has only weak references to it, it is collected by GC. Thus ThreadLocal itself does not leak memory.
static class ThreadLocalMap {
static class Entry extends WeakReference<ThreadLocal<? >>{
/** The value associated with this ThreadLocal. */Object value; Entry(ThreadLocal<? > k, Object v) {super(k); value = v; }}private static final int INITIAL_CAPACITY = 16; // The initial capacity must be a multiple of 2
private Entry[] table; / / the Hash table
private int size = 0; // Number of current entries in the Hash table
private int threshold; // size Expand the capacity when this number is reached
// Calculates the next index based on capacity
private static int nextIndex(int i, int len) {
return ((i + 1 < len) ? i + 1 : 0);
}
// Calculate the last index based on the capacity
private static int prevIndex(int i, int len) {
return ((i - 1> =0)? i -1 : len - 1);
}
ThreadLocalMap is lazily loaded only when the thread needs to save local variables
// Create a new ThreadLocalMap and pass in the constructor the key and value of the first variable.ThreadLocalMap(ThreadLocal<? > firstKey, Object firstValue) { table =new Entry[INITIAL_CAPACITY];
int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
table[i] = new Entry(firstKey, firstValue);
size = 1; setThreshold(INITIAL_CAPACITY); }... }Copy the codeThreadLocalMap (key, value); if ThreadLocalMap (key, value) does not exist, create a new one.
public void set(T value) {
Thread t = Thread.currentThread();
ThreadLocalMap map = getMap(t);
if(map ! =null)
map.set(this, value);
else
createMap(t, value);
}
Copy the codeLet’s look at how ThreadLocalMap stores the data, using linear probing to resolve Hash collisions. When saving an Entry, calculate the hash value of the key first, and then run index = hash & (len-1) to get the location for saving the Entry. If table[index] is empty, save the Entry in this position. If table[index] is not empty, hash conflict occurs and the index is moved backwards until table[index+n] (n=1,2,3…). Is empty. When using linear probing, its efficiency drops dramatically if there are many Hash conflicts.
ThreadLocalMap set (ThreadLocal
key, Object value), which describes the overall logic of adding data when using linear probes.
private void set(ThreadLocal
key, Object value) {
Entry[] tab = table;
int len = tab.length;
int i = key.threadLocalHashCode & (len-1);
// Start at position I and iterate backwards until table[I] is empty
for(Entry e = tab[i]; e ! =null; e = tab[i = nextIndex(i, len)]) { ThreadLocal<? > k = e.get();// If the current key already exists, save the new value
if (k == key) {
e.value = value;
return;
}
// If the key is null, ThreadLocal has been collected by GC
// We need to replace the previously expired data with new data
if (k == null) {
// The replaceStaleEntry() method does a lot of work, which is examined in detail below
replaceStaleEntry(key, value, i);
return; }}// The table[I] is empty and the same key or expired key is not found
// Create a new Entry to place in the current position
tab[i] = new Entry(key, value);
int sz = ++size;
// If the number reaches the threshold, expand the capacity and hash again
if(! cleanSomeSlots(i, sz) && sz >= threshold) rehash(); }Copy the codeNext, look at the replaceStaleEntry(Key, Value, staleSlot) method, which is used to put the data to be inserted into the appropriate place and clean up expired keys and values in the Hash table.
private void replaceStaleEntry(ThreadLocal<? > key, Object value,int staleSlot) {
Entry[] tab = table;
int len = tab.length;
Entry e;
// Walk forward to find the position where the most recent Entry is not empty but the key is reclaimed
int slotToExpunge = staleSlot;
for (inti = prevIndex(staleSlot, len); (e = tab[i]) ! =null; i = prevIndex(i, len))
if (e.get() == null)
slotToExpunge = i;
// Start from the position below staleSlot and traverse backwards
for (inti = nextIndex(staleSlot, len); (e = tab[i]) ! =null; i = nextIndex(i, len)) { ThreadLocal<? > k = e.get();// If an Entry with the current key is found
// It needs to be swapped with the Entry in the staleSlot position to ensure Hash order
if (k == key) {
e.value = value;
tab[i] = tab[staleSlot];
tab[staleSlot] = e;
// slotToExpunge == staleSlot Indicates that no expired key is found during forward traversal
if (slotToExpunge == staleSlot)
slotToExpunge = i;
cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
return;
}
// slotToExpunge == staleSlot Indicates that no expired key is found during forward traversal
SlotToExpunge = slotToExpunge = slotToExpunge = slotToExpunge
// The staleSlot position itself does not need to be cleared because it is where the newly inserted data is placed
if (k == null && slotToExpunge == staleSlot)
slotToExpunge = i;
}
// If the current key does not exist, create a new Entry and place it in the staleSlot position
tab[staleSlot].value = null;
tab[staleSlot] = new Entry(key, value);
// slotToExpunge ! = staleSlot: Expired keys exist and need to be cleared
if(slotToExpunge ! = staleSlot) cleanSomeSlots(expungeStaleEntry(slotToExpunge), len); }Copy the codeThis section uses an example to analyze the running process of the replaceStaleEntry(key, value, staleSlot) method. Assume that index = key % 10 is used to calculate the location of the data. If threadLocalmap.set (key, value) is used to insert a key of 13, the index of which should be 3, and the key is found to be out of date. The replaceStaleEntry(key, value, staleSlot) method is called.
The first step is to find the position where the most recent Entry is not empty but the key is out of date. In this example, this is the position where index is 1, so slotToExpunge is 1.
Then it traverses backwards and tries to find the position where key is equal to 13, and finds that Table [4] meets the conditions. Then it exchanges table[4] with data table[3] at staleSlot position, and the results are as follows. The significance of exchange here is to maintain the characteristics of the linear detection method. If the exchange is not done, the data in Table [3] will be cleared later, which does not meet the law of the linear detection method. Because if the data with key 13 is searched later, it will be found empty when it locates in Table [3], but the data with key 13 is actually in table[4].
If the replaceStaleEntry(key, value, staleSlot) method cannot find a place where the key is equal to the data to be inserted, the data to be inserted is stored in the staleSlot location. After data is saved to a proper location, expungeStaleEntry(slotToExpunge) is called to delete expired data from the Hash table.
private int expungeStaleEntry(int staleSlot) {
Entry[] tab = table;
int len = tab.length;
// Clear the data in the staleSlot location
tab[staleSlot].value = null;
tab[staleSlot] = null;
size--;
// Iterate backwards, rehash the data at each position until Entry is null
Entry e;
int i;
for(i = nextIndex(staleSlot, len); (e = tab[i]) ! =null; i = nextIndex(i, len)) { ThreadLocal<? > k = e.get();if (k == null) {
e.value = null;
tab[i] = null;
size--;
} else {
int h = k.threadLocalHashCode & (len - 1);
if(h ! = i) { tab[i] =null;
while(tab[h] ! =null) h = nextIndex(h, len); tab[h] = e; }}}return i;
}
Copy the codeThe getEntry(key) method of ThreadLocalMap is called directly.
private Entry getEntry(ThreadLocal
key) {
int i = key.threadLocalHashCode & (table.length - 1);
Entry e = table[i];
if(e ! =null && e.get() == key)
return e;
else
return getEntryAfterMiss(key, i, e);
}
Copy the codeIf the direct key directly hits the first data, return it, otherwise call the getEntryAfterMiss() method. The linear detection method is followed to find the corresponding Entry within the method. When the outdated data is found, the expungeStaleEntry() method is called to clean up until the corresponding key Entry is found or empty data is traversed.
private Entry getEntryAfterMiss(ThreadLocal<? > key,int i, Entry e) {
Entry[] tab = table;
int len = tab.length;
while(e ! =null) { ThreadLocal<? > k = e.get();if (k == key)
return e;
if (k == null)
expungeStaleEntry(i);
else
i = nextIndex(i, len);
e = tab[i];
}
return null;
}
Copy the code4.3.3 Preventing ThreadLocal Memory Leaks
A ThreadLocalMap internally uses weak references to a ThreadLocal. When a ThreadLocal is reclaimed, data in the map becomes obsolete, and entries and values are left in the map, causing memory leaks. While it may be cleaned up the next time ThreadLocalMap adds or deletes data, it may also remain in the map.
Remove (), which will eventually call the remove of ThreadLocalMap (ThreadLocal
key) method to clear the corresponding Entry.
private void remove(ThreadLocal
key) {
Entry[] tab = table;
int len = tab.length;
int i = key.threadLocalHashCode & (len-1);
for(Entry e = tab[i]; e ! =null; e = tab[i = nextIndex(i, len)]) {
if (e.get() == key) {
e.clear();
expungeStaleEntry(i);
return; }}}Copy the codeBecause the nuggets have a word limit, so it is divided into two parts.