Hello everyone, I am Java not confused (WX public account of the same name). In this first installment of this column, I’ll introduce you to caching in computer systems, the role of the volatile modifier in each of the three concurrency problems, and finally the use of CAS. Hope you found this article useful!

The cache

In computer systems, there is a mismatch between the speed at which the CPU core can process data and the speed at which it can read data from memory, and caching is introduced to address the huge difference.

When the kernel reads data, it first reads it from the cache. If there is no data in the cache, it reads it from the memory. After reading, the data is stored in the cache.

According to the principle of time locality, cached data may be referenced many times in the future, so using caching can improve the speed at which the kernel reads data.

Temporal locality: A memory location that has been referenced once will be referenced many times in the future. Spatial locality: If the location of a memory is referred to, the location near it will also be referred to in the future.

The principle of spatial locality is also used here. When the kernel reads data, it does not read only the required data. Instead, it reads the surrounding data into the cache, which is called the cache line.

A cache line is the smallest unit of data exchanged between the cache and memory. The size is an integer power of 2. The default value of a cache line in Linux is 64 bytes.

We can verify the existence of cached lines with code:

int[][] array = new int[64 * 1024][1024]; long startTime1=System.currentTimeMillis(); For (int I = 0; i < 64 * 1024; i ++) for(int j = 0; j < 1024; j ++) array[i][j] ++; long endTime1=System.currentTimeMillis(); System.out.println(" program run time: "+(endtime1-starttime1)+"ms"); Long startTime2= system.currentTimemillis (); For (int I = 0; i < 1024; i ++) for(int j = 0; j < 64 * 1024; j ++) array[j][i] ++; long endTime2=System.currentTimeMillis(); System.out.println(" program run time: "+(endtime2-starttime2)+"ms");Copy the code

Horizontal traversal is much faster than vertical traversal because of the presence of cached lines. The result of my computer is as follows:

Program running time: 176ms Program running time: 2513msCopy the code
Three levels of cache

The larger the cache capacity is, the more data is stored, but the slower the search speed is.

The smaller the cache, the less data you store, but the faster you find it.

To improve the performance of the cache, a level 3 cache is introduced between the kernel and memory. Close to the kernel cache, small capacity, fast speed; A cache that is close to the memory has a large capacity and slow speed.

From the kernel to the memory are L1 cache, L2 cache and L3 cache respectively.

L1 and L2 caches are kernel-specific caches, with one CPU sharing one L3 cache.

Take my computer as an example: L1 cache: 256K, L2 cache: 1MB, L3 cache: 6MB.

From L1 to L3, the cache gets bigger and the hit ratio gets better, but so does the latency of reading the cache.

Three Concurrent problems

The existence of multi-core cpus and caches, each kernel reads the same data into the cache, when one kernel modifies the cached data, it is not directly synchronized to memory, and other kernels cannot know that the data has changed, leading to concurrency problems.

Let’s look at the three concurrency problems and discuss how volatile relates to them.

atomic

Refers to the indivisibility of a transaction in which all or none of the operations of a transaction are executed without interruption.

The reads and writes of volatile modified variables are atomic. The read-and-write compound operation is not atomic, so volatile does not guarantee atomicity. The following two pieces of code are equivalent:

public class ThreadSafeInteger {
    private int value;

    public synchronized int get(a) {
        return value;
    }
    public synchronized  void set(int value) {
        this.value = value; }}public class ThreadSafeInteger {

    private volatile int value;

    public int get(a) {
        return value;
    }

    public void set(int value) {
        this.value = value; }}Copy the code
visibility

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

The main thread and thread01 thread read the running variable, respectively. The main thread makes changes to the RUNNING variable, but the Thread01 thread is not visible.

public class Visibleness {
  private boolean running = true;

  void func(a) {
    System.out.println("Thread start...");
    while (running){}
    System.out.println("The thread end...");
  }

  public static void main(String[] args) throws InterruptedException {
    System.out.println("The main start...");
    Visibleness object = new Visibleness();
    new Thread(object::func,"thread01").start();
    Thread.sleep(2 * 1000);
    object.running = false;
    System.out.println("The main end..."); }}/ / output:The main start... Thread start... The main end...Copy the code

In the code above, CORE0 and CORE1 read RUNNING into the cache and use the RUNNING variable. Core0 cache is not written to main memory, so core1 is not visible.

Think about it, why doesn’t core1 just write to main memory? The main reason is performance. If the kernel is constantly reading and writing to Main memory, there is no point in caching.

Running is volatile, core0 is running, core1 is written to main memory, and running is volatile.

The main start... Thread start... The main end... Thread the end...Copy the code

Thus, volatile variables are visible.

order

The processor reorders our code to make it more efficient. For example, if the following statement is executed, the sequence of two statements does not affect the normal running of the program.

boolean inited = true; User user; user = new User(); // statement 1 inited = true; / / 2Copy the code

However, in a multi-threaded environment, if other threads rely on these two statements, this can cause some problems. If the processor executes statement 2 before user is initialized, it will cause an exception.

while (! inited) { Thread.sleep(2 * 1000); } user.getId();Copy the code

Volatile variable that prevents processor-specific reorder operations by inserting a memory barrier.

Live to learn to use

As we mentioned earlier, the minimum unit of exchange between cache and memory is the cache row. When a cache row is cached by multiple kernels, one kernel changes the volatile modified data in the cache row and notifies the other kernels to change the cached row. If data in cached rows is frequently modified, performance deteriorates dramatically, which is known as the pseudo-sharing problem.

In JDK7, there is a queue collection class LinkedTransferQueue. When volatile variables are used, the performance is optimized by appending bytes. This ensures that only one variable exists in a cache line, which greatly improves performance.

CAS

Pessimistic Lock, as the name implies, refers to the pessimism about data being modified by outsiders, including other current transactions of the system, as well as transactions from external systems. Every time a thread changes data, it assumes that another thread will change it, so it locks the data before taking it, and any other thread must wait for the thread to release the lock. Synchronized is a type of pessimistic lock, also known as an exclusive lock. Optimistic Lock, as the name implies, it believes that data will not cause conflicts in general, so when data is submitted for update, it will detect whether data conflicts, if found, will fail and retry until success, can be called spin.

The CAS process

The main mechanism used for optimistic locking is CAS. CAS is Compare and swap. CAS has three operands: memory value V, old expected value A, and new value B. The processing process is as follows:

  • 1. First get the value A in memory
  • 2. A becomes B after increment or other calculation
  • 3. Compare whether V and A in the current memory are the same, then B replaces A AtomicLong increment in this way:
public final long incrementAndGet() { for (;;) { long current = get(); // (1) long next = current + 1; // (2) if (compareAndSet(current, next)) } } public final boolean compareAndSet(long expect, long update) { return unsafe.compareAndSwapLong(this, valueOffset, expect, update); }Copy the code

If the current value is 1, then thread A and thread B both execute (3) at the same time and their next is 2, current=1.

If thread A executes (3) first, this is an atomic operation that updates the slot value to 2 and returns 1. If true, incrementAndGet returns 2.

Thread B executes (3) because current=1 and the actual value of the variable is 2, so if the value is false, the loop continues, and if no other thread increments the variable, thread B updates the variable to 3 and exits.

This uses an infinite loop for polling checks using CAS, which wastes CPU resources to a certain extent, but avoids thread context switching and scheduling compared to locking.

ABA problem

Thread 1 gets the current memory value as: A, and the other threads change the memory value to B, and then to A. At this point, A in memory is no longer the A obtained by thread 1, and this problem is called the ABA problem.

1. ABA problems that have no impact can not be treated

2. The version number can be added for those with influence. The version number can be modified every time the data is modified, and the version number can be compared when the ratio is compared.

Volatile Refers to a variable that is atomically read or written to a shared variable. But assignment from one variable to another is nonatomic. Thus volatile can be combined with CAS to implement atomic operations.

conclusion

After reading this article, you must be wondering how volatile implements visibility. How is order implemented for volatile? Why is CAS an atomic operation? I also want you to think about how the kernel communicates with other kernels after modifying data. In the second article of this column, I’ll give you a brief overview of volatile and CAS.

If my article is helpful to you, please like and forward it for me. If you have any questions about the article, please let me know in the comment section. Thanks!