First, memory model

The cache

Because there is a large gap between CPU execution speed and memory data read and write speed, the CPU often containsThe cacheStructure.When a program is running, it copies the data needed for an operation from main memory to the CPU’s cache. Then the CPU can read and write data directly from its cache when performing a calculation. When the operation is complete, the data in the cache is refreshed to main memory.

Cache inconsistency problem

Execute the following code:

int i = 0;
i = i + 1;
Copy the code

When executing this statement, the thread reads the value I = 0 from main memory and copies it to the cache. The CPU increments I by one, writes the data to the cache, and writes the latest value of I from the cache to main memory.

This may happen: initially, two threads read the value of I and store it in their respective CPUS ‘caches, then thread 1 increments it and writes the latest value of I, 1, to memory. Thread 2’s cache will still have the value of I at 0, so after adding 1, I will be 1, and then thread 2 will write the value of I to memory.

That is, if a variable is cached across multiple cpus (in the case of multithreading), there may be cache inconsistencies.

Cache inconsistency resolution

There are generally two solutions:

  • The bus lock

Because the CPU communicates with other components through the bus, locking the bus prevents other cpus from accessing other components (such as memory) so that only one CPU can use the variable’s memory.

  • Cache consistency protocol

Because other cpus are unable to access memory during the bus lock, this leads to inefficiency. Hence the cache consistency protocol. The best known is Intel’s MESI protocol, which ensures that copies of shared variables used in each cache are consistent. The core ideas of MESI protocol are: When a CPU writes data, if it finds that the variable is a shared variable, that is, a copy of the variable exists in other cpus, it sends a signal to inform other cpus to set the cache line of the variable to invalid state. Therefore, when other cpus need to read the variable, they find that the cache line of the variable is invalid. Then it will re-read from memory.

Second, thread safety

The reasons causing

From the previous analysis, thread safety issues can arise in concurrent programming (multithreaded programming) :

  • Multiple threads are manipulating shared data.

  • There are multiple threads of code that operate on shared data.

  • When one thread executes multiple pieces of code that manipulate shared data, other threads participate.

The core concept of concurrency

Three core concepts: atomicity, visibility, and orderliness.

  • Atomicity: Similar to the concept of atomicity in database transactions, an operation (which may contain more than one child operation) either executes at all (effective) or does not execute at all (ineffective).

Lock and synchronize (synchronized methods and synchronized code blocks), CAS (CPU-level CAS instruction CMPXCHG).

  • Visibility: When multiple threads concurrently access a shared variable, changes made to the shared variable by one thread are immediately visible to other threads.

The volatile keyword ensures visibility.

  • Sequentiality: The order in which a program is executed is the order in which the code is executed. Because the processor may optimize the input code to improve the efficiency of the program, it does not guarantee that the execution sequence of each statement in the program is the same as that in the code, but it will ensure that the final execution result of the program is the same as the result of the code execution sequence – that isInstruction reordering.

Volatile ensures sequence in some ways, but it can also be guaranteed through synchronized and locking.

The structure of Java object headers

Java objects can be used as locks in concurrent programming. The lock actually exists in the Java object header. If the object is an array, the virtual machine stores the object header with three Word widths, and if the object is not an array, the virtual machine stores the object header with two Word widths. In a 64-bit VM, a word width equals eight bytes, or 64bit.

The Mark Word in the Java object header stores the object’s HashCode, generational age, and lock marker bits by default. The default Mark Word storage structure for 32-bit JVMS is as follows:

25 bit | – | | 4 bit | biased locking sign bit (1 -) | lock sign bit (2 -) | | : : | : | : | : | : | | | unlocked state the object’s hashCode generational age | | object | | 01

64-bit JVMS have the following storage structure:

The lock state

25bit

31bit

1bit

4bit

1bit

2bit

 
< / td > < td > < / td > < td > < p > < span lang = "EN - US" > cms_free < / span > < / p > < / td > < td > < p > < span > generational age < span Lang = "EN - US" > < / span > < / span > < / p > < / td > < td colspan = "2" > < p > < span > biased locking < span lang = "EN - US" > < / span > < / span > < / p > < / td > < td > < p > < span > lock flag bit < span lang = "EN - US" > < / span > < / span > < / p > < / td >Copy the code

unlocked

unused

hashCode

 
</td>
<td>

</td>
<td>

</td>
<td colspan="2">
<p><span lang="EN-US">01</span></p>
</td>
Copy the code

Biased locking

ThreadID(54bit) Epoch(2bit)

 
</td>
<td>

</td>
<td>
<p><span lang="EN-US">1</span></p>
</td>
<td colspan="2">
<p><span lang="EN-US">01</span></p>
</td>
Copy the code

The data stored in Mark Word changes as the lock flag bit changes during runtime.

Now that you understand the concepts, let’s look at how Java ensures security in concurrent programming.

Four, synchronized

usage

  • Decorates synchronized code blocks

Encapsulate thread code for multiple operations that share data. When a thread executes these codes, other threads cannot participate in the operation. The current thread must complete the code before other threads can participate in the computation.

synchronized(object) {code that needs to be synchronized; }Copy the code
  • Modify the synchronization function (method)
The modifiersynchronizedReturn value method name (){}Copy the code

  • Pertaining to a static method that applies to the entire static method and to all objects of the class.

  • Pertaining to a class whose scope is the parenthesized portion of synchronized, and whose main objects are all objects of that class.

There are three main functions of synchronized:

(1) ensure that threads are mutually exclusive access synchronization code (2) ensure that changes to shared variables are visible in a timely manner (3) effectively solve the reordering problem.

Lock object

  • For synchronous methods, the lock is currentInstance objects.
  • For statically synchronized methods, the lock is for the current objectClass object.
  • For synchronous method blocks, the lock issynchonizedObjects configured in parentheses.

Realize the principle of

Two instructions are added to the compiled bytecode to synchronize the code.

Monitorenter:

Each object has a monitor lock. The monitor is locked when it is occupied, and the thread attempts to acquire ownership of the Monitor when it executes the Monitorenter instruction as follows:

  • ifmonitorIf the number of entries is 0, the thread entersmonitor, and then set the number of entries to 1, the thread ismonitorOwner of.
  • If the thread already owns itmonitor, just re-enter, then entermonitorPlus 1.
  • If another thread is already occupiedmonitor, the thread enters the blocking state untilmonitorIs 0, then try again to obtainmonitorOwnership of.

Monitorexit:

The thread executing monitorexit must be the owner of the monitor to which objectref corresponds. When the instruction is executed, the number of monitor entries decreases by 1. If the number of monitor entries decreases by 1, the thread exits the monitor and is no longer the owner of the monitor. Other threads blocked by the monitor can try to take ownership of the monitor.

Synchronized semantics are implemented through a monitor object, and methods such as Wait /notify also rely on monitor objects, which is why methods such as wait/notify can only be called in synchronized blocks or methods. Otherwise would be thrown Java. Lang. The cause of the exception IllegalMonitorStateException.

Advantages and disadvantages

Benefits: Solves thread safety issues.

Disadvantages: Relatively low efficiency, because outside the synchronization thread will determine the synchronization lock. Acquiring and releasing locks imposes performance costs.

Compiler optimizations for synchronized

Java6 introduced “biased locking” and “lightweight locking” to reduce the performance cost of acquiring and releasing locks, so there are four lock states in Java6: no-lock, biased locking, lightweight locking, and heavyweight locking, which escalate as the race progresses. Locks can be upgraded but not degraded.

  • Biased locks: In most cases locks are not only not contested by multiple threads, but are always acquired multiple times by the same thread. The purpose of biased locking is to eliminate the overhead of thread lock reentrant (CAS) after a thread has acquired the lock (the thread’s ID is recorded in the object’s Mark Wod), seemingly favoring the thread.

  • Lightweight locks (CAS) : Lightweight locks are upgraded from biased locks. Biased locks work when one thread enters a synchronized block and are upgraded to lightweight locks when the second thread joins the lock contention. The intent of lightweight locks is to try to update MarkWord to a pointer to LockRecord via CAS without multithreading competition, reducing the performance cost of system mutex with heavyweight locks.

  • Heavyweight lock: The VIRTUAL machine uses CAS to try to update the MarkWord to a pointer to a LockRecord. If the update succeeds, the thread owns the lock. If this fails, the MarkWord is checked to see if it points to the current thread’s stack frame. If it does, the current thread already owns the lock. If not, the lock is preempted by another thread and expands to a heavyweight lock.

The lock status corresponds to the Mark Word

Take the 32-bit JVM as an example:

The lock state

25 bit

4bit

1bit

2bit

23bit

2bit

Bias lock

Lock flag bit

Lightweight lock

Pointer to the lock record in the stack

00

Heavyweight lock

A pointer to a mutex (heavyweight lock)

10

The GC tag

empty

11

Biased locking

threadID

Epoch

Age of object generation

1

01

Five, the volatile

volatileIs a Java keyword used to modify shared variables (member variables of a class, static member variables of a class).

The modified variable contains two levels of semantics:

  • Guaranteed visibility

Instead of writing variables to the cache, threads flush the values directly back to main memory. At the same time, when other threads read the shared variable, they retrieve the value from main memory instead of using the value in the current cache. (Hence the performance penalty). Note: Operations written to main memory are not guaranteed atomicity.

  • Disallow command reordering

Disallowing instruction reorder has two meanings:

1) When a program performs a read or write to a volatile variable, all changes to the preceding operation must have occurred and the result must be visible to subsequent operations; The operation behind it has certainly not taken place; 2) During instruction optimization, statements that access volatile variables must not be executed after them, nor must statements that access volatile variables be executed before them.

** A look at the assembly code generated with and without volatile shows that the lock prefix is added to volatile.

Sixth, the Lock

Application scenarios

If a code block is modified by synchronized, when a thread acquires the lock and executes the block, the other threads must wait until the thread that acquires the lock releases the lock. The thread that acquires the lock releases the lock only in two cases:

  • The thread that acquires the lock completes the block of code and then releases the lock.
  • When thread execution is abnormal, the JVM causes the thread to release the lock automatically.

If the thread that acquired the lock is blocked because it is waiting for an IO or for some other reason (such as calling the sleep method) but does not release the lock, it will make the program inefficient.

Therefore, there needs to be a mechanism to allow waiting threads to pass without waiting indefinitely (such as waiting for a certain amount of time or being able to respond to interrupts)LockYou can do that.

Source code analysis

Lock-related interfaces and classes are locatedJ.U.Cthejava.util.concurrent.locksUnder the bag.

(1)The Lock interface

public interface Lock {
    void lock(a);
    void lockInterruptibly(a) throws InterruptedException;
    boolean tryLock(a);
    boolean tryLock(long time, TimeUnit unit) throws InterruptedException;
    void unlock(a);
    Condition newCondition(a);
}
Copy the code
  • Acquiring a lock

Lock () : obtains the lock and waits if the lock is temporarily used. TryLock (): Fetch lock with a return value. Note that the return type is Boolean, false if the lock was occupied when it was acquired, true otherwise. TryLock (long time, TimeUnit unit) : A time period is guaranteed to wait parameter time compared to tryLock(). LockInterruptibly () : When the lock is acquired using this method, the thread can respond to interrupts, the wait state of the interrupted thread, if the thread is waiting to acquire the lock. Thus, when two threads attempt to acquire A lock using lock.lockinterruptibly () at the same time, calling threadb.interrupt () on threadB interrupts the wait if thread A has acquired the lock while threadB is waiting.

Note: Once a thread has acquired the lock, it is not interrupted by the interrupt() method. This is because, as I explained in an earlier article, calling interrupt() alone cannot interrupt a running thread, only a blocking thread. Therefore, when a lock is obtained using the lockInterruptibly() method, if it is not obtained, the interrupt can be responded to only by waiting. Synchronized means that a thread that is waiting for a lock cannot be interrupted.

  • Release the lock

Unlock (): Releases the lock.

(2)Already the class

ReentrantLock stands for “ReentrantLock”. Already is the only class that implements the Lock interface, and provided more already method, based on AQS (AbstractQueuedSynchronizer).

ConcurrentHashMap does not adopt synchronized control, but ReentrantLock.

  • A constructor

Reentrantlocks are classified into fair and unfair locks, and can be specified using constructors:

public ReentrantLock(a) {
    sync = new NonfairSync();
}
public ReentrantLock(boolean fair) {
    sync = fair ? new FairSync() : new NonfairSync();
}
Copy the code
  • Acquiring a lock
public void lock(a) {
    sync.lock();
}
Copy the code

Sync is an abstract inner class:

abstract static class Sync extends AbstractQueuedSynchronizer {
    private static final long serialVersionUID = -5179523762034025860L;
    abstract void lock();
Copy the code

Its lock() method uses the constructed FairSync object, the sync implementation class.

public ReentrantLock(a) {
    sync = new NonfairSync();
}
// Delete some methods
static final class NonfairSync extends Sync {
    final void lock(a) {
        if (compareAndSetState(0.1))
            setExclusiveOwnerThread(Thread.currentThread());
        else
            acquire(1);
    }
    protected final boolean tryAcquire(int acquires) {
        returnnonfairTryAcquire(acquires); }}Copy the code

CompareAndSetState is a method of AQS, which is based on CAS operations.

public final void acquire(int arg) {
    if(! tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }Copy the code

Try to acquire the lock further (calling a final method inherited from sync) :

final boolean nonfairTryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        if (compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true; }}else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0) // overflow
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    return false;
}
Copy the code

The first step is to determine whether the state in AQS is equal to 0, which means that no other thread has acquired the lock, so the current thread can try to acquire the lock. If state is greater than 0, it indicates that the lock has been acquired, and it is necessary to determine whether the thread that acquired the lock is the current thread (ReentrantLock supports reentrant). If yes, state + 1 is required and the value is updated.

If tryAcquire(ARG) fails to acquire the lock, you need to write the current thread to the queue with addWaiter(Node.exclusive). Before writing, wrap the current thread as a Node object (addWaiter(Node.exclusive)).

To:

public final void acquire(int arg) {
    if(! tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }Copy the code
  • Release the lock
The release process for fair and unfair locks is the same:public void unlock(a) {
    sync.release(1);
}

public final boolean release(int arg) {
    if (tryRelease(arg)) {
        Node h = head;
        if(h ! =null&& h.waitStatus ! =0)
        	   // Wake up the suspended thread
            unparkSuccessor(h);
        return true;
    }
    return false;
}

// Try to release the lock
protected final boolean tryRelease(int releases) {
    int c = getState() - releases;
    if(Thread.currentThread() ! = getExclusiveOwnerThread())throw new IllegalMonitorStateException();
    boolean free = false;
    if (c == 0) {
        free = true;
        setExclusiveOwnerThread(null);
    }
    setState(c);
    return free;
}        
Copy the code

(3)ReadWriteLock interfacewithReentrantReadWriteLock class

  • define
public interface ReadWriteLock {
    Lock readLock(a);
    Lock writeLock(a);
}
Copy the code

In ReentrantLock, synchronization between threads is mutually exclusive, both for read and write operations. However, in some scenarios, read operations can be performed in parallel, and only the write operations are mutually exclusive. This situation can also be resolved using ReentrantLock, but there is a performance loss. ReadWriteLock is designed to solve this problem.

  • Implementation – ReentrantReadWriteLock class

In ReentrantReadWriteLock, read and write locks are defined respectively. Similar to ReentrantLock, Sync is used to implement read and write locks. Sync is implemented in fair and unfair ways. ReentrantReadWriteLock is defined as follows:

static final int SHARED_SHIFT     = 16;
  static final int SHARED_UNIT    = (1 << SHARED_SHIFT);
  static final int MAX_COUNT      = (1 << SHARED_SHIFT) - 1;
  static final int EXCLUSIVE_MASK = (1 << SHARED_SHIFT) - 1;

  // Get the number of lock read times
  static int sharedCount(int c)    { return c >>> SHARED_SHIFT; }
  // Get the number of write lock holds
  static int exclusiveCount(int c) { return c & EXCLUSIVE_MASK; }
  
  // The id of the thread and the number of read locks acquired by the corresponding thread
  static final class HoldCounter {
    int count = 0;
    // Use id, not reference, to avoid garbage retention
    final long tid = Thread.currentThread().getId();
  }
  
  // The thread variable holds the thread and the number of reads and writes acquired in the thread
  static final class ThreadLocalHoldCounter extends ThreadLocal<HoldCounter> {
    public HoldCounter initialValue(a) {
      return newHoldCounter(); }}private transient ThreadLocalHoldCounter readHolds;
  // Cache the last thread to acquire the read lock
  private transient HoldCounter cachedHoldCounter;
  // Save the first thread to acquire the read lock
  private transient Thread firstReader = null;  
  private transient int firstReaderHoldCount; 

Copy the code

There are two static inner classes: ReadLock() and WriteLock(), both of which implement the Lock interface.

Get read lock:

  • If no thread holds the write lock, the read lock is successfully obtained.
  • If another thread holds the write lock, the read lock fails to be acquired.
  • If the local thread holds the write lock and no other thread is waiting for the write lock, the lock is successfully obtained.
  • If the current thread holds a write lock and there are other threads waiting for the write lock, the read lock is successfully obtained if the current thread already holds the read lock. If no read lock exists, the read lock fails to be obtained.

Get write lock:

  • Check whether any thread holds a lock, including the read lock and the write lock. If yes, go to Step 2. If no, go to Step 3
  • If the write lock is empty (if there is a lock in step 1, there is a thread holding the read lock), or if there is a thread holding the write lock, failure is returned. If the number of write locks is greater than MAX_COUNT, failure is returned. Otherwise, update state and return true
  • Return false if the write lock is blocked or the CAS fails, otherwise set the thread holding the write lock to local and return true
  • Check by writerShouldBlock write lock block
final boolean writerShouldBlock(a) {
    return hasQueuedPredecessors();
  }
// Check whether it is blocked
public final boolean hasQueuedPredecessors(a) {
    Node t = tail;
    Node h = head;
    Node s;
    returnh ! = t && ((s = h.next) ==null|| s.thread ! = Thread.currentThread()); }Copy the code

Seven, comparison,

The Lock and synchronized

Synchronized is implemented at the JVM level, while Lock is implemented at the JDK level. Lock needs to Lock and release, which is more complex than synchronized, but Lock can do more fine-grained locking, support access to timeout, access to interrupt, which is not synchronized. The main implementation of Lock is ReentrantLock, ReadLock and WriteLock. Read sharing, write mutually exclusive, read and write mutually exclusive.

  • Lock is an interface, while synchronized is a Java keyword and synchronized is a built-in language implementation.

  • Synchronized will automatically release the lock occupied by the thread when an exception occurs, so it will not lead to deadlock. UnLock (); unLock(); unLock(); unLock();

  • Lock causes the thread waiting for the Lock to respond to the interrupt, whereas synchronized does not. With synchronized, the waiting thread waits forever and cannot respond to the interrupt.

  • Lock can tell if a Lock has been acquired successfully, whereas synchronized cannot.

  • Lock improves the efficiency of read operations by multiple threads.

　　

  • A Lock implementation is different from synchronized, which is aPessimistic locking, its courage is very small, it is afraid of someone and it eat, so it every time before eating to shut up. The Lock layer is CASOptimistic lockingThe embodiment of, it does not matter, others robbed it to eat, it to take the food, so it is very optimistic. The bottom layer is mainly dependent onvolatileandCASOperation implemented.

Synchronized and volatile

  • Volatile essentially tells the JVM that the value of the current variable in the register (working memory) is indeterminate and needs to be read from main memory;

  • Synchronized locks the current variable so that only the current thread can access it and other threads are blocked.

  • Volatile can only be used at the variable level; Synchronized can be used at the variable, method, and class levels

  • Volatile only enables change visibility of variables, not atomicity. Synchronized can guarantee the change visibility and atomicity of variables

  • Volatile does not block threads; Synchronized can cause threads to block.

  • Volatile variables are not optimized by the compiler; Variables of the synchronized tag can be optimized by the compiler

Deadlock problem

There are four necessary conditions for deadlocks, one of which can be broken to remove the deadlock.

Four essential conditions:

  • Mutual exclusion conditions

A resource can only be used by one process at a time.

  • Request and hold conditions

When a thread is blocked by requesting a resource, it holds on to the acquired resource.

  • Non-deprivation condition

Threads that have acquired resources cannot be forcibly taken away until they are used up.

  • Cyclic waiting condition

Several threads form a head – to – end circular waiting resource relationship.

Deadlock example

When synchronization is nested, two threads are locked with each other and neither thread is released, resulting in a deadlock. For example, create two strings (A and B), and create two threads (A and B), and let each thread use synchronized lock string (A locks A, then locks B; If A locks A, and B locks B, a cannot lock B, and B cannot lock A, then the deadlock occurs.

public class DeadLock {
    public static String obj1 = "obj1";
    public static String obj2 = "obj2";
    public static void main(String[] args){
        Thread a = new Thread(new Lock1());
        Thread b = new Thread(newLock2()); a.start(); b.start(); }}class Lock1 implements Runnable{
    @Override
    public void run(a){
        try{
            System.out.println("Lock1 running");
            while(true) {synchronized(DeadLock.obj1){
                    System.out.println("Lock1 lock obj1");
                    Thread.sleep(3000);After fetching obj1, wait for Lock2 to have enough time to lock obj2
                    synchronized(DeadLock.obj2){
                        System.out.println("Lock1 lock obj2"); }}}}catch(Exception e){ e.printStackTrace(); }}}class Lock2 implements Runnable{
    @Override
    public void run(a){
        try{
            System.out.println("Lock2 running");
            while(true) {synchronized(DeadLock.obj2){
                    System.out.println("Lock2 lock obj2");
                    Thread.sleep(3000);
                    synchronized(DeadLock.obj1){
                        System.out.println("Lock2 lock obj1"); }}}}catch(Exception e){ e.printStackTrace(); }}}Copy the code

The concept of lock

There are two main types of locks implemented in Java: internal lockssynchronized(monitor lock built into the object) and display lockjava.util.concurrent.locks.Lock.

  • Reentrant lock

A recursive function in the same thread still has the code to acquire the lock, but it is not affected. All synchronized methods in the object do not need to acquire the lock again. Synchronized and Lock are both reentrant.

  • Interruptible lock

Synchronized is not a breakable Lock, whereas Lock is a breakable Lock.

  • Fair lock

The lock is obtained according to the waiting time of the thread waiting for the lock. If the waiting time is long, the thread has the priority to obtain the lock. Synchronized is an unfair lock; For ReentrantLock and ReentrantReadWriteLock, it is an unfair lock by default, but can be set to a fair lock.

  • Read-write lock

The reading and writing of resources are divided into two parts. The reading can be read by multiple threads, and the writing must be synchronized. ReadWriteLock is a read/write lock. It is an interface. ReentrantReadWriteLock implements this interface.

  • spinlocks

The thread is told to execute a meaningless loop and then re-compete for the lock. If the loop does not continue, the thread will remain in the running state for the duration of the loop. However, jVM-based thread scheduling allows time slices, so other threads still have the opportunity to apply for and release the lock. Spin locks save the time and space (queue maintenance, etc.) overhead of blocking locks, but long spins become “busy wait”, which is obviously inferior to blocking locks. Therefore, the number of spins is generally controlled within a range, such as 10,100, etc., beyond which the spin lock will be upgraded to a blocking lock.

  • An exclusive lock

Synchronized is a pessimistic lock, and synchronized is an exclusive lock that causes all other threads requiring the lock to suspend until the thread holding the lock releases it.

  • Optimistic locking

Leave the lock unlocked each time, assuming no conflicts to complete an operation, and retry until it succeeds if it fails because of conflicts.

  • Pessimistic locking

Cause all other threads requiring locks to hang, waiting for the thread holding the lock to release the lock.

About JUC

The following file contains two subpackages: Atomic and Lock, and the closure-queue under Concurrent and executors.

Refer to the link

  • Java concurrent programming: Volatile keyword resolution

  • Synchronized in Java SE1.6

  • Java concurrent programming: Lock

  • The underlying implementation of Java concurrency mechanisms

  • Java deadlock

  • In-depth understanding of the JVM

  • Meet the Lock and AbstractQueuedSynchronizer (AQS)