preface

In the multithreaded environment, many classes we use everyday have thread safety problems, such as ArrayList, HashSet and HashMap. How should we deal with the thread problem in the multithreaded environment? What is the CAS algorithm? Is there any other way to achieve thread safety other than synchronized? Optimistic lock? Pessimistic lock?

Synchronization container

For these collection classes often used in daily development, the JUC toolkit provides us with thread safe classes to replace these classes.

• ArrayList -- > copyonwritearraylist -- write copy list
• HashSet -- > copyonwritearrayset -- write copy set
• HashMap -- > concurrenthashmap -- piecewise lock mapping

CopyOnWriteArrayList

The bottom layer of CopyOnWriteArrayList avoids the concurrency problem in multi-threaded environment by operating "copy".

When a thread operates on the list, it will first add a lock, then copy the value of the current object, re create a new object with length + 1, and then point the reference address to the new ArrayList

add() method source code

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

CopyOnWriteArraySet

It is similar to CopyOnWriteArrayList, except that the data structure of the underlying data is different

Source code

private boolean addIfAbsent(E e, Object[] snapshot) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] current = getArray();
        int len = current.length;
        if (snapshot != current) {
            // Optimize for lost race to another addXXX operation
            int common = Math.min(snapshot.length, len);
            for (int i = 0; i < common; i++)
                if (current[i] != snapshot[i] && eq(e, current[i]))
                    return false;
            if (indexOf(e, current, common, len) >= 0)
                    return false;
        }
        Object[] newElements = Arrays.copyOf(current, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

ConcurrentHashMap

Code example

public class ConcurrentHashMapSample {
    public static int users = 100;//Number of concurrent access users simulated at the same time
    public static int downTotal = 50000; //Total number of real downloads by users
    public static ConcurrentHashMap count = new ConcurrentHashMap() ;//Counter

    public static void main(String[] args) {
        ExecutorService executorService  = Executors.newCachedThreadPool();
        final Semaphore semaphore = new Semaphore(users);
        for(int i = 0 ; i < downTotal ; i++){
            final Integer index = i;
            executorService.execute(()->{
                //Simulate concurrent access and download of N users through multithreading
                try {
                    semaphore.acquire();
                    count.put(index, index);
                    semaphore.release();
                } catch (Exception e) {
                    e.printStackTrace();
                }
            });
        }
        try {
            Thread.sleep(3000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        executorService.shutdown();//Turn off scheduling service
        System.out.println("Total downloads:" + count.size());
    }
}

The underlying layer of ConcurrentHashMap divides the original data into a small segment with a length of 2 to the nth power, and then locks it in segments. Multiple threads process it at the same time, which also improves some efficiency under the condition of ensuring safety.

extend

Atomicity

Atomicity means that an operation or multiple operations are either executed completely and the execution process will not be interrupted by any factor, or they will not be executed at all.

Atomic package

• Atomic package is another Java package specially designed for thread safety under JUC, which contains multiple atomic operation classes
• Atomic common classes
  • AtomicInteger
  • AtomicIntergerArray
  • AtomicBoolean
  • AtomicLong
  • AtomicLongArray

The synchronized keyword ensures the safe accumulation of downloads under multithreading. Here, you can use Atomic atomic classes to complete the optimization through a more lightweight method.

Optimize code

public static AtomicInteger count = new AtomicInteger() ;//Counter
...
//Thread unsafe
public static void add(){
    count.getAndIncrement(); //count++
}

CAS algorithm

Pessimistic lock

• Lock is the simplest way to do concurrency, and of course, its cost is the highest. An exclusive lock is a pessimistic lock, and synchronized is an exclusive lock. It assumes the worst case and is executed only when it is ensured that other threads will not cause interference. It will cause all other threads that need a lock to hang and wait for the thread holding the lock to release the lock.

Optimistic lock

• The so-called optimistic lock is to complete an operation without locking each time, assuming that there is no conflict. If the conflict fails, try again until it succeeds. CAS (Compare And Swap) is a well-known lock free algorithm.

Application scenario of Atomic

Although the thread safety mechanism based on CAS is very good and efficient, it should be said that not all thread safety can be implemented in this way. This is only suitable for some requirements with small granularity, such as counters, which are effective. Otherwise, there will be no lock.