Multi-threaded concurrent questions, the basic interview must ask.

Most of you know about Synchronized and Lock. Some of you can talk about volatile and sending packets. The good ones can talk about the principles of Synchronized and volatile and the data structures used in sending packets. For example, the principle of ConcurrentHashMap.

This article will summarize the various processing methods of multi-threaded concurrency, hoping to help you.

First, why there are concurrent problems with multi-threading

Why is there a concurrency problem when multiple threads are accessing the same variable at the same time?

  1. The Java memory model specifies that all variables are stored in main memory and that each thread has its own working memory.

  2. The working memory of a thread holds a main memory copy of variables used by the thread. All operations on variables must be performed in the working memory of the thread instead of reading or writing directly to the main memory.

  3. When a thread accesses a variable, it copies the variable from main memory to working memory. Writes to the variable are not immediately synchronized to main memory.

  4. Different threads cannot directly access variables in each other’s working memory, and the transfer of variables between threads requires data synchronization between their own working memory and main memory.

Ii. Java Memory Model (JMM)

The Java Memory Model (JMM) is used to synchronize data between working memory (local memory) and main memory. It specifies how and when to synchronize data, as shown in the following figure.

Three, concurrency three elements

Atomicity: In an operation, the CPU may not pause and then schedule, i.e., the operation will either complete or not be executed without interruption.

Visibility: When multiple threads access the same variable and one thread changes the value of the variable, other threads can immediately see the changed value.

Orderliness: The order in which a program is executed is the order in which the code is executed.

What can be done to solve the concurrency problem? (key)

The following describes how to solve concurrency problems in different scenarios.

A volatile,

1.1 volatile features

Guaranteed visibility, not guaranteed atomicity.

1. When a volatile variable is written, the JVM forces variables from local memory to be flushed to main memory.

2. This write operation invalidates caches in other threads. Other threads read from main memory. Volatile writes are visible to other threads in real time.

Instruction reordering prohibition Instruction reordering is a method by which compilers and processors order instructions to optimize program performance, subject to certain rules:

1. Instructions with dependencies will not be reordered, for example, a = 1. b = a; A and B are dependent and will not be reordered.

2. The execution result in a single thread cannot be affected. For example: a = 1; b=2; C =a+b, the first two operations can be reordered, but c=a+b can’t be reordered, because we want to get 3.

1.2 Application Scenarios

Volatile Is used to modify a variable where only one thread writes and all other threads read.

1.3 Why is volatile used for singleton double locking?

public class TestInstance {private static volatile TestInstance mInstance; public static TestInstance getInstance(){ //1 if (mInstance == null){ //2 synchronized (TestInstance.class){ //3 if (mInstance == null){ //4 mInstance = new TestInstance(); //5 } } } return mInstance; }Copy the code

If volatile is not used, concurrency can be problematic. Thread A executes comment 5 new TestInstance() in the following steps:

  1. Allocate memory

  2. Initialize an object

  3. MInstance points to memory

At this time, if the instruction is rearranged, the execution sequence is 132. At the third execution, thread B just comes in and executes comment 2. At this time, judge that mInstance is not empty and directly use an uninitialized object. Therefore, the volatile keyword is used to disable instruction reordering.

1.4 principle of volatile

Volatile is implemented in the JVM using memory barriers that provide three functions:

  1. It ensures that instruction reordering does not place subsequent instructions in front of the memory barrier, nor does it place previous instructions behind the barrier; That is, by the time the memory barrier instruction is executed, all operations in front of it have been completed;

  2. It forces cached changes to be written to main memory immediately

  3. A write invalidates cached rows in other cpus, after which reads from other threads are read from main memory.

1.5 Limitations of Volatile

Volatile only guarantees visibility, not atomic writes visible to other threads, but it does not solve the problem of multiple threads writing simultaneously.

Second, the Synchronized

2.1 Synchronized Usage scenario

Multiple threads write a variable at the same time.

For example, if there are 100 tickets remaining and Windows A and B each sell one ticket at the same time, it is problematic if the remaining variable volatile is used.

The remaining tickets obtained by window A are 100, and the remaining tickets obtained by window B are also 100. When A sells A ticket, it becomes 99 and is refreshed back to main memory. At the same time, B sells A ticket, becomes 99 and is refreshed back to main memory, resulting in the remaining tickets in main memory is 99 instead of 98.

The limitation of volatile is that multiple threads write simultaneously, in which case Synchronized can be used.

Synchronized guarantees that only one thread can execute a method or block of code at a time.

2.2 principle of Synchronized

public class SynchronizedTest {public static void main(String[] args) { synchronized (SynchronizedTest.class) { System.out.println("123"); } method(); }private static void method() {}}Copy the code

Compile this code using the javac command and then use the Java p-v synchronizedtest. class command to view the bytecode

public static void main(java.lang.String[]); descriptor: ([Ljava/lang/String;)Vflags: ACC_PUBLIC, ACC_STATICCode: stack=2, locals=3, args_size=1 0: ldc #2 // class com/lanshifu/opengldemo/test/SynchronizedTest 2: dup 3: astore_1 4: monitorenter 5: getstatic #3 // Field java/lang/System.out:Ljava/io/PrintStream; 8: ldc #4 // String 123 10: invokevirtual #5 // Method java/io/PrintStream.println:(Ljava/lang/String;)V 13: aload_1 14: monitorexit 15: goto 23 18: astore_2 19: aload_1 20: monitorexit 21: aload_2 22: athrow 23: invokestatic #6 // Method method:()V 26: returnCopy the code

You can see 4: Monitorenter and 14: Monitorexit, with printed statements in the middle.

When a synchronized block is executed, the Monitorenter directive is executed, the code in the synchronized block is executed, and the Monitorexit directive is executed on exiting the synchronized block.

The key to Synchronized synchronization is that the monitor of the object must be acquired, and the thread can proceed only after obtaining the monitor; otherwise, it will enter the synchronization queue, and the thread state will change to BLOCK, and only one thread can obtain the monitor at the same time. When monitorexit is called, a thread in the queue exits to fetch monitor. For details:

https://www.jianshu.com/p/d53bf830fa09

Each object has a counter, which is incremented by one when the thread acquires the lock and decrement by one when the lock is released, so as long as the lock’s counter is greater than zero, other threads can only wait to access it.

2.3 Upgrading a Synchronized lock

Synchronized may be known as heavyweight locking, but Java1.6 has made various optimizations to Synchronized that make it less heavy in some cases. Biased locking and lightweight locking were introduced in Java1.6 to reduce the performance cost of acquiring and releasing locks.

Biased locks: In most cases, locks are not only not contested by multiple threads, but are always acquired multiple times by the same thread. Biased locks are introduced to make it cheaper for threads to acquire locks.

When thread A accesses A block of code with A synchronized lock, the id of the current thread is stored in the object header, and the subsequent entry and exit of the block of code with A synchronized lock do not need to re-lock and release the lock.

Lightweight lock: In the biased lock case, if thread B also accesses the synchronized block and the thread ID of the comparison object header is different, it will upgrade to lightweight lock and acquire the lightweight lock by means of spin.

Heavyweight lock: If thread A and thread B access the synchronized code BLOCK at the same time, the lightweight lock is upgraded to the heavyweight lock. If thread A acquires the heavyweight lock, thread B has to wait and enter the BLOCK state.

2.4 Synchronized shortcomings

  1. You cannot set the lock timeout period

  2. Locks cannot be released by code

  3. Prone to deadlocks

Third, already

ReentranLock addresses the drawbacks of Synchronized: you can’t set lock timeouts or release locks through code.

Where there are multiple Condition variables and highly competitive locks, ReentrantLock is more appropriate. ReentrantLock also provides Condition, which is more flexible for thread waits and wakes. A ReentrantLock can have multiple Condition instances, so it is more extensible.

3.1 Use of ReentrantLock

The lock and unlock

ReentrantLock reentrantLock = new ReentrantLock(); System.out.println("reentrantLock->lock"); reentrantLock.lock(); Try {system.out. println(" Sleep 2 seconds...") ); Thread.sleep(2000); } catch (InterruptedException e) { e.printStackTrace(); }finally { reentrantLock.unlock(); System.out.println("reentrantLock->unlock"); }Copy the code

Implement a timed lock request: tryLock

public static void main(String[] args) { ReentrantLock reentrantLock = new ReentrantLock(); Thread thread1 = new Thread_tryLock(reentrantLock); thread1.setName("thread1"); thread1.start(); Thread thread2 = new Thread_tryLock(reentrantLock); thread2.setName("thread2"); thread2.start(); }static class Thread_tryLock extends Thread { ReentrantLock reentrantLock; public Thread_tryLock(ReentrantLock reentrantLock) { this.reentrantLock = reentrantLock; } @Override public void run() { try { System.out.println("try lock:" + Thread.currentThread().getName()); boolean tryLock = reentrantLock.tryLock(3, TimeUnit.SECONDS); if (tryLock) { System.out.println("try lock success :" + Thread.currentThread().getName()); System.out.println(" + thread.currentThread ().getName()); Thread.sleep(5000); System.out.println(" "+ thread.currentThread ().getName()); } else {system.out.println ("try lock timeout :" + thread.currentThread ().getName()); } } catch (InterruptedException e) { e.printStackTrace(); } finally { System.out.println("unlock:" + Thread.currentThread().getName()); reentrantLock.unlock(); }}}Copy the code

Logs printed:

Try lock: thread1Try lock:thread2try lock success :thread2 Thread2try lock timeout: thread1unlock: thread1Exception thread in "thread1" Java. Lang. IllegalMonitorStateException ats java.util.concurrent.locks.ReentrantLock$Sync.tryRelease(ReentrantLock.java:151) at java.util.concurrent.locks.AbstractQueuedSynchronizer.release(AbstractQueuedSynchronizer.java:1261) at java.util.concurrent.locks.ReentrantLock.unlock(ReentrantLock.java:457) at Com. Lanshifu. Demo_module. Test. Lock. ReentranLockTest $Thread_tryLock. Run (60) ReentranLockTest. Java: wake up: thread2unlock: thread2Copy the code

TrtLock, as demonstrated above, sets the wait time for obtaining the lock, and returns a failure after 3 seconds. You can see the result in the log. The exception occurred because Thread1 failed to acquire the lock and should not have called unlock.

3.2 Condition Condition

public static void main(String[] args) { Thread_Condition thread_condition = new Thread_Condition(); Thread_condition.setname (" the thread that tests the Condition "); thread_condition.start(); try { Thread.sleep(2000); } catch (InterruptedException e) { e.printStackTrace(); } thread_condition.singal(); }static class Thread_Condition extends Thread { @Override public void run() { await(); } private ReentrantLock lock = new ReentrantLock(); public Condition condition = lock.newCondition(); public void await() { try { System.out.println("lock"); lock.lock(); System.out.println(thread.currentThread ().getName() + ": I am waiting for a notification..." ); condition.await(); //await and signal correspond to //condition.await(2, timeunit.seconds); System.out.println(thread.currentThread ().getName() + ": >>>"); } catch (Exception e) { e.printStackTrace(); } finally { System.out.println("unlock"); lock.unlock(); } } public void singal() { try { System.out.println("lock"); lock.lock(); System.out.println(" I want to notify the waiting thread, condition.signal()"); condition.signal(); //await and signal correspond to thread.sleep (1000); } catch (InterruptedException e) { e.printStackTrace(); } finally { System.out.println("unlock"); lock.unlock(); }}}Copy the code

Run Print Logs

Lock tests the Condition thread: I'm waiting for a notification... Lock I want to notify the waiting thread, conditional.signal () UNLOCK tests the thread of condition: once notified, I continue >>> UNLOCKCopy the code

The above demonstrates the use of await and signal in Condition, with lock first.

3.3 Fair lock and Unfair Lock

The ReentrantLock constructor passes true for a fair lock.

A fair lock means that locks are acquired by threads in the order in which they are locked, i.e., first come, first served. Non-fair lock is a kind of lock preemption mechanism. The lock is acquired randomly, which may cause some threads to uniformly fail to get the lock, so it is unfair.

3.4 ReentrantLock

  1. ReentrantLock Uses lock and unlock to acquire and release locks

  2. Unlock is placed in finally so that a normal run or exception releases the lock

  3. Before you can use the await and signal methods of condition, you must call the Lock method to get the object monitor

Four, and the package

From the above analysis, using locks is obviously inefficient in the case of severe concurrency, because only one thread can acquire the lock at a time, and the other threads have to wait.

Java provides and packages to solve this problem. Here are some common data structures used in and packages.

4.1 ConcurrentHashMap

We all know that HashMap is a thread-unsafe data structure. HashTable is thread-safe based on HashMap, with get and PUT methods and Synchronized modification, but it is replaced by ConcurrentHashMap in the case of high concurrency.

By default, there are 16 buckets in ConcurrentHashMap. The get and PUT operations first calculate the hashcode of the key, and then interpolate with 16 to one of the 16 buckets, and then ReentrantLock each bucket. Inside the bucket is the HashMap structure (array plus list, if the list becomes too long, it becomes a red-black tree).

Therefore, a maximum of 16 threads can be accessed simultaneously.

4.2 LinkBlockingQueue

A linked list structured blocking queue that internally uses multiple ReentrantLocks

/** Lock held by take, poll, etc */private final ReentrantLock takeLock = new ReentrantLock(); /** Wait queue for waiting takes */private final Condition notEmpty = takeLock.newCondition(); /** Lock held by put, offer, etc */private final ReentrantLock putLock = new ReentrantLock(); /** Wait queue for waiting puts */private final Condition notFull = putLock.newCondition(); private void signalNotEmpty() { final ReentrantLock takeLock = this.takeLock; takeLock.lock(); try { notEmpty.signal(); } finally { takeLock.unlock(); }}/** * Signals a waiting put. Called only from take/poll.*/private void signalNotFull() { final ReentrantLock putLock =  this.putLock; putLock.lock(); try { notFull.signal(); } finally { putLock.unlock(); }}Copy the code

LinkBlockingQueue = LinkBlockingQueue = LinkBlockingQueue

1. Get data from the queue, notempty.await () is called if there is no data in the queue; Enter the wait.

Notempty.signal () is called when data is put into the queue; , notifies the consumer that the wait in 1 ends and the wake continues.

Notfull.signal () is called when data is fetched from the queue. , notifying the producer to continue production.

4. Call notfull.await () if the number in the queue reaches the maximum value while putting data into the queue. , waiting for the consumer to consume, i.e. waiting for 3 to fetch the data and issue notfull.signal (); Only then can the producer continue to produce.

LinkBlockingQueue is a typical producer-consumer pattern, without going into the source code details.

4.3 Atomic Operation Class: AtomicInteger

Internal CAS (Compare and Swap) is used to ensure atomicity

Take an example of an increment of int

AtomicInteger atomicInteger = new AtomicInteger(0); atomicInteger.incrementAndGet(); / / since the increaseCopy the code

Look at the source code

/** * Atomically increments by one the current value. * * @return the updated value */ public final int incrementAndGet() {   return U.getAndAddInt(this, VALUE, 1) + 1;  }Copy the code

U is Unsafe, look at Unsafe#getAndAddInt

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 code

Atomicity is guaranteed by compareAndSwapInt.

Five, the summary

Multithreaded concurrency:

  1. Volatile is used when only one thread is writing and all other threads are reading

  2. Synchronized is not a heavyweight lock at the beginning. When the concurrency is not serious, such as when only one thread accesses, Synchronized is biased lock. When multiple threads access, but not simultaneously, the lock is upgraded to a lightweight lock; Upgrade to a heavyweight lock when multiple threads are accessing simultaneously. So Synchronized is ok in situations where concurrency is not too severe. Synchronized has limitations, such as the inability to set lock timeouts and release locks through code.

  3. ReentranLock can be released by code, and lock timeout can be set.

  4. Synchronized and ReentranLock are inefficient under high concurrency, because only one thread can enter a Synchronized code block at a time. If many threads access the block at the same time, all other threads are waiting for the lock. You can use and dispatch data structures such as ConcurrentHashMap, LinkBlockingQueue, and atomic data structures such as AtomicInteger.

When the interview according to the above summary of this train of thought answer basically ok. In addition to ConcurrentHashMap, we also need to understand the principles of other commonly used data structures, such as HashMap, HashTable, TreeMap principle, ArrayList, LinkedList comparison. Look at the source code yourself or some blogs.

About multi-threaded concurrency is summarized here, if it is to deal with the interview according to the ideas of this article should be no big problem to prepare.

Recent Articles:

  • Summary of an advanced Android interview for a program yuan

  • Get rid of all your anxiety with these 3 tips

  • The most beautiful custom View tutorial, do not accept refutation!

Question of the day:

And send packets to support multi-line collections are there?

Exclusive upgrade community: I Finally Figured it out