Bits and pieces of things are not always remembered for a long time, just learning other people’s articles is just the residue left by others after chewing. I accidentally found this daily interview question, and I thought that if I just thought about it simply, I would not only have little effect, but even I might be too lazy to think about the difficult questions and could not stick to them. So write down every thought, understanding, and other people’s insights. Not only deepen your understanding, but also motivate yourself to stick to it.

Before introducing synchronization in multithreading, let’s take a look at concurrent programming.

Concurrent programming

Why concurrent programming exists

  • Resource utilization: the execution of the program is nothing more than the OPERATION of the CPU for each instruction. The CPU processing speed for instructions is very fast. If it is serial, for example, the speed of IO operation is far less than that of CPU operation, so the CPU will have a lot of idle time and waste CPU resources.
  • Time: Sometimes multiple tasks are unrelated to each other and can be done concurrently with sufficient resources. Serial results can only prolong the time to complete the overall task, reduce efficiency.
  • Fairness: Applying for tasks that need to be done at the same time, and randomly executing them in serial will break the fairness between tasks. Concurrent operations enable tasks to be executed at the same time and obtain the same resources, ensuring fairness.

Pitfalls of concurrent programming

  • Security: The security pitfalls of concurrent programming are well known. Different worker threads working on the same resource at the same time produce dirty data. A typical example is the bank transfer problem. When A transfers to B’s account and B transfers to A’s account at the same time, the two working threads operate the balance at the same time, which will inevitably lead to the situation that the account cannot be posted after the operation.
  • Overhead: In the case of a single CPU, the concurrent operation is achieved by the CPU frequently switching threads. The switching of threads involves the operation of saving and updating register data, which requires a certain amount of overhead. In the case of high concurrency, you need to consider whether the resource and time savings of concurrent operations can compensate for the overhead between thread switches.
  • Complexity: Resources used by a single thread can be retrieved from the corresponding stack, register, and memory in the process, and executed without intersecting with other threads. Multithreaded programming is bound to involve the communication between threads, data synchronization and other problems, a set of concurrent mechanism is very complicated to design.

Three elements of concurrent programming

  • Atomicity: One or more operations, all or none of which can be performed without interruption by any factor. Assignment and reading of primitive data types in Java are atomic operations.
  • Visibility: When multiple threads access the same variable, one thread changes the variable, and the other threads update the value synchronously.
  • Orderliness: that is, the order in which the program is executed is the order in which the code is executed. This is because when the processor executes the program, in order to optimize the execution efficiency of the program, the code will be reordered to varying degrees of instruction. Of course, this reordering will not change the final result of the program, because the code with data dependence will not be reordered. So the next line of code needs the data from the last line of code. Instruction reordering is fine in a single thread, but can be problematic in multiple threads.
/ / thread 1:
context = loadContext();   //语句1
inited = true;             //语句2

 / / thread 2:
while(! inited ){ sleep() } doSomethingwithconfig(context);Copy the code

Statements 1 and 2 in thread 1 have no data laziness and inited is only a marker variable, so instruction reordering may occur in these two statements. When statement 2 is executed before statement 1, which is when thread 2 is started, and init is true, thread 2 thinks the initialization is complete, and statement 1 is not executed, which causes problems.

Therefore, ensuring atomicity, visibility and order in concurrent programming is the basic element of synchronization

Synchronous operation

volatile

Volatile is a Java keyword. Once a shared variable (a member variable of a class, a static variable) is modified by volatile, it has two meanings

  • When one thread updates the value of this variable, it is visible to other threads. The update operation here refers to writing to the working memory.
  • Disallow instruction reordering. Code before volatile is not reordered after volatile. By the time the program executes a volatile variable, all previous code must have been executed and all subsequent code must not have been executed.

This guarantees visibility and order, but volatile does not guarantee visibility. Take a look at the code below

public class Main {
    private volatile static int test = 0;
    private volatile static int count = 10;
    
    public static void main(String[] args) {
        for(int i=0; i<10; i++){ Main mm =new Main();
            new Thread(new Runnable() {
                @Override
                public void run(a) {
                    for(int j=0; j<10000; j++){ mm.increase(); } count--; } }).start(); }while (count > 0) {}// All threads have finished executing
        System.out.println("The final data is" + test);
    }

    private void increase(a){test++;}
}
Copy the code

And when you run it, you’ll see that it’s less than 100,000 each time. That’s because the test++ operation, which is not atomic, has nothing to do with the test variable itself.

Test ++ reads the value of test, increments the value of test, and writes the value to the working memory after three atomic operations. When thread 1 completes the first two steps, thread 2 begins to read the value of the test variable. When thread 1 completes the first three steps, thread 2 has already read the value of the test variable, so the two threads actually add the value of test only once.

Thus, volatile only performs simple synchronization operations, such as the labeled variables mentioned above

volatile boolean inited = false;
/ / thread 1:
context = loadContext();   //语句1
inited = true;             //语句2

 / / thread 2:
while(! inited ){ sleep() } doSomethingwithconfig(context);Copy the code

Singleton pattern in concurrent programming

class Singleton {
    private volatile static Singleton instance = null;
    private Singleton(a) {}
    public static Singleton getInstance(a) {
        if (instance == null) {
            synchronized (Singleton.class) {
                if (instance == null)
                    instance = newSingleton(); }}returninstance; }}Copy the code

Instance =new Singleton() is reordered by the synchronized keyword, but there are three atomic operations in this step

  • Allocate memory for instance
  • Call the construct parameter to initialize a member variable
  • The instance object is pointed to the allocated memory space where the second and third steps are reordered. There is no data dependence between the two steps. If the third step is executed before the second (instance is already non-null), another thread finds that instance is not null and uses it, and the second variable initialization operation has not yet been performed, an error will occur.

synchronized

Synchronized is also a keyword in Java. It realizes synchronization through the lock mechanism. To execute the code, it must acquire the lock. Only the thread that obtains the lock object can execute the locked code, and other threads can only block without obtaining the lock. There are object locks and class locks. Synchronization comes in two forms: synchronized code blocks and synchronized methods

  • Object locking: Applies only to one instance of the class in different threads. If multiple objects of the same class are in different threads, this does not affect the locking.
  • Class lock: For all instances of the class.

Synchronized code block

Object lock

class Test{
    public void testMethod(a){
        synchronized(this) {... }}}Copy the code

Kind of lock

class Test{
    public void testMethod(a){
        synchronized(Test.class){ ... }}}Copy the code

Object locking. The o stands for any object or array, and whoever owns the object can execute the block code

class Test{
    public void testMethod(a){
        synchronized(o){ ... }}}Copy the code

Synchronized methods

Kind of lock

class Test{
    public synchronized static void testMethod(a){... }}Copy the code

Object lock

class Test{
    public synchronized void testMethod(a){... }}Copy the code

ReentrantLock

ReentrantLock is a class that synchronizes in much the same way as synchronized.

Basic usage

ReentrantLock lock = new ReentrantLock(); // The argument defaults to false, unfair lock. lock.lock();// If the resource is locked by another resource, it waits for the lock to be released
try {
    / / operation
} finally {
    lock.unlock();  / / releases the lock
}
Copy the code

ReentrantLock Explicitly obtains and releases a lock using lock and UNLOCK methods, which is different from synchronized implicitly obtaining a lock. When the thread reaches lock.lock(), it attempts to acquire the lock, executes if it gets it, and blocks if it doesn’t. The unlock() method releases the lock held by the current thread. An exception may occur if there is no lock to release.

Explicit lock acquisition is more difficult than implicit automatic lock acquisition, but there are many more controllable situations. We can interrupt lock acquisition, delay lock acquisition, and so on.

Fair lock

When many threads are in the queue waiting for a lock, the CPU picks a random thread to acquire the lock. In this case, starvation occurs, where the lower priority thread is constantly preempted by the higher priority thread, so that the lock is not acquired for a long time. This is an unfair lock. RenntrantLock can use fair locking, where CPU scheduling acquires locks in the order in which threads wait to avoid starvation. However, execution is inefficient because an ordered queue needs to be maintained. Synchronized is an unfair lock.

ReentrantLock lock = new ReentrantLock(true);
Copy the code

Indicate what lock to use by passing a Boolean object when creating the object. Default is false unfair lock.

Synchronized compared to reentrantLock

  • ReentrantLock implements the Lock interface, which is a class, and synchronized is the Java keyword, which is the built-in language implementation
  • Synchron releases the lock automatically when an exception occurs, causing almost no deadlocks. ReentrantLock requires a manual release of the lock (unLock), so release the lock in the finally block when used.
  • ReentrantLock interrupts lock acquisition, that is, continues until the lock is acquired, whereas synchronized does not and blocks.
  • A lock can be used to determine whether a lock is successfully obtained, whereas synchronized cannot

As you can see, ReentrantLock implements many more advanced functions, but with a little more complexity. In terms of performance, the performance of ReentrantLock and ReentrantLock is similar when the competition is not intense, but when the competition is intense, i.e. there are a large number of threads waiting to acquire the lock, the performance is better. The specific use depends on the situation.

Synchronized performance was very poor before jdk1.6, but synchronized performance has been optimized after jdk1.6, and is not much different from ReentrantLock performance. The official also said that synchronized is more supported, and there is room for optimization in the future. Therefore, synchronized is recommended when all requirements can be met.

CAS atomic operation

Optimistic and pessimistic locks:

The CPU schedules threads by allocating time slices to different threads. The time slice switching is also the thread switching. It needs to clear registers and cache data, and it takes a certain amount of time to load the data needed by the thread after switching. When a thread is blocked, notify and notifyAll are used to wake it up. If thread 1 is trying to acquire the lock, it fails to acquire it and suspends. The lock is released, thread 1 is woken up, attempts to acquire the lock, and is again preempted by another thread. Thread 1 continues to suspend, and the thread that acquired the lock takes only a short time. In this way, thread 1 repeatedly suspends and wakes up. Thread 1 thinks that if other threads acquire the lock, they will update the resources in the lock, so it keeps waiting. This is called pessimistic lock. An exclusive lock like synchronized is a pessimistic lock.

Optimistic locks do not lock, first of all, it will think that other threads will not update the resource before it changes the resource, it will try to use the resource inside the lock for its own operation, if the modified data conflict, will abandon the previous operation. And so on until the operation succeeds.

CAS is an optimistic lock concept with three operands — old memory value (C), expected old value (A), and new value (B). The new value is updated if and only if the old memory value is the same as the expected result of the old memory value. Or you just keep trying. Java Java. Util. Concurrent. Atomic package related classes is the realization of the CAS.

The name of the class instructions
AtomicBoolean Boolean values that can be updated atomically.
AtomicInteger An int value that can be updated atomically.
AtomicIntegerArray An int array whose elements can be updated atomically.
AtomicIntegerFieldUpdater Reflection – based utility that makes atomic updates to specified volatile int fields of specified classes.
AtomicLong A long value that can be updated atomically.
AtomicLongArray An array of Longs whose elements can be updated atomically.
AtomicLongFieldUpdater Reflection-based utility that makes atomic updates to specified volatile long fields of specified classes.
AtomicMarkableReference AtomicMarkableReference maintains object references with tag bits that can be updated atomically.
AtomicReference An object reference that can be updated atomically.
AtomicReferenceArray An array of object references whose elements can be updated atomically.
AtomicReferenceFieldUpdater Reflection – based utility that makes atomic updates to specified volatile fields of specified classes.
AtomicStampedReference AtomicStampedReference Maintains object references with integer “flags” that can be updated atomically.

This non-blocking algorithm, which does not require locks, is superior to the blocking algorithm in performance. The following is generally used to implement the synchronization operation of increasing i++

public class Test {
    public AtomicInteger i;
    public void add(a) { i.getAndIncrement(); }}Copy the code

The problem of the CAS

  • ABA problem. When A value changes from A to B to A, its value actually changes, but CAS doesn’t recognize it. The idea is to prefix variables with version numbers, 1A-2b-3a. Since Java1.5, the JDK atomic package has provided a class AtomicStampedReference to address ABA issues. The compareAndSet method of this class first checks whether the current reference is equal to the expected reference, and whether the current flag is equal to the expected flag, and if all are equal, sets the reference and flag values to the given updated value atomically.
  • If the CAS operation is not successful for a long time, the CPU costs a lot.