Series index

Concurrent series: Thread locking

  1. Why does CountDownlatch guarantee execution order?

  2. Why can Concurrent Containers achieve efficient concurrency?

  3. ReentrientLock: The Correct Use of lock posture

New series: Android11 system source code analysis

  1. How to download Android source code for Mac environment?

  2. Android11 Source code analysis: How does the application start?

  3. Android11 source code analysis: How to start the Activity?

  4. Android11 source code analysis: Service startup process analysis

  5. Android11 source code analysis: Static broadcast is how to receive notifications?

  6. Binder cross-process Implementation (In process of creation)

  7. How do plug-in activities start?

  8. Android11 source code analysis: why in the end will BE stuck UI?

  9. How does SurfaceFlinger distribute vsync signals? (In process of creation)

Classic series: Android10 system startup process

  1. Source code download and compilation

  2. Overview of the Android system startup process

  3. Init process source parsing

  4. Zygote process source code analysis

  5. SystemServer source code parsing

preface

The previous article introduced the use and principle of CountdownLatch. In concurrency, in addition to multi-threaded collaboration, we also need to consider how to achieve efficient concurrency

Today, from a source code perspective, let’s talk about how concurrency can be efficiently implemented in concurrent containers

Next, the body begins!

whyHashtableInefficient concurrency?

Before we talk about efficient concurrency, let’s talk about hashMaps and Hashtables

A Hashmap is an important data structure for implementing hash tables. It can be used to store key-value pair information and quickly find a value based on the hash

The two most important functions are PUT () and get(), and both Key and Value can be specified by the stereotype

The put() function hashes the key value and calls putVal() to store the data, which is stored internally by array + linked list + red-black tree

Where, the array is used to store the corresponding Node

to store the key-value pair information. After the hash conflict occurs, the open chain method will be used to solve the hash conflict problem. Here, the corresponding Node is the implementation of the linked list. If the repeated hash value is greater than 8, it will be treed and processed using a red-black tree to reduce the time complexity of the query (O(nlog(n)), but at the cost of taking up extra space).
,v>

In common use, the probability of hash conflicts occurring more than 8 times is 1 in 10 million. Therefore, in general, no tree will occur

At initialization, resize () is called to assign an initial size of 1>>2, which is 16, and a maximum size of 1>>30, which is about 1 billion

If the size of subsequent PUT data is insufficient, it is doubled (oldVal>>1) and a new array is created to move the data

See the comments in the code below for the logic

static final int MAXIMUM_CAPACITY = 1 << 30; Static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; Final Node<K,V>[] resize() {Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && OldCap >= DEFAULT_INITIAL_CAPACITY) // The initial size is 16 newThr = oldThr << 1; // Double threshold // double threshold // double threshold A threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // Create a new array table = newTab; if (oldTab ! = null) { for (int j = 0; j < oldCap; ++j) {// Move the array to the new array Node<K,V> e; if ((e = oldTab[j]) ! OldTab [j] = null; If (e.next == null) newTab[e.hash & (newcap-1)] = e; if (e.next == null) Else if (e instanceof TreeNode) // If TreeNode is used for storage, ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); Else {// preserve order // If there is a list structure, you need to iterate over the list to complete the list move operation //... }}}} return newTab; }Copy the code

To synchronize data with Hahstable, you need to protect data and share data that is operated on by multiple threads in PUT () and GET ()

The implementation of HahshTable synchronizes the two functions directly with synchornize, but because of the granularity of the lock and the time consuming nature of the PUT operation, this class has long been deprecated, hence the efficient concurrent container CurrentHashMap

CurrentHashMapWhat optimization was done?

Let’s start with the java7 version of CurrentHashMap

Concurrency optimization in Java version 7

In Java7, use Segment lock to perform concurrent operations on data, including Segment lock on data, Segment itself is a subclass object of ReentrantLock, and the logic is basically consistent with Hashmap when the data put operation is performed on each seinterface. Again, arrays are used to store key-value pairs, and in case of hash conflicts, zips are used to maintain them with linked lists

When CurrentHashmap is initialized, you can specify the number of segments, that is, the concurrency. If the value is not specified or exceeds the maximum value (DEFAULT_CONCURRENCY_LEVEL) 16, the CurrentHashmap is initialized to 16 segments and maintained using an array

The initialization code is as follows

public ConcurrentHashMap(int initialCapacity, float loadFactor, Int concurrencyLevel) {// concurrencyLevel can set its concurrency (how many threads can be supported) //... Just the if (! (loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0) throw new IllegalArgumentException(); //segment is ReentrantLock. Segment<K,V> s0 = new Segment<K,V>(loadFactor, (int)(cap * loadFactor), (HashEntry<K,V>[])new HashEntry[cap]); [] ss = (Segment<K,V>[])new Segment[ssize]; // Create segment array}}Copy the code

Concurrency optimization in java8

CurrentHashMap has been further optimized for the java7 version of the Java8 version we are currently using

The specific optimization is to abandon the synchronization idea of Segment Segment lock and use CAS operation + Synchronize instead. The concurrency is increased from 16 threads to each data node supporting concurrent operation

In addition, on this basis, when hash conflicts occur, if the number of hash conflicts is less than 8, continue to use the linked list to solve the conflict problem; If the number of hash conflicts is greater than 8, it will be treified, reducing the time complexity from 0(n) to O(nlongn), but the disadvantage is that red-black trees also take up more memory space

summary

In java7, CurrentHashmap uses segments to Segment data and supports up to 16 concurrent operations

In Java8, CurrentHashmap uses CAS to perform concurrent operations on each HashEntry data, improving the concurrency. In addition, when the number of hash conflicts is greater than 8, the linked list will be treed to reduce the time complexity of search

CopyOnWriteArrayListHow is efficient concurrency achieved?

The main idea of CopyOnWriteArrayList is to copy while writing, separate read from write

During the add () operation, a copy of the original array is made, and the copied data is modified. After the modification is complete, it points to the original array to complete the data update

The specific code is as follows

public void add(int index, E element) { final ReentrantLock lock = this.lock; lock.lock(); Try {Object[] elements = getArray(); Int len = elements. Length; if (index > len || index < 0) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+len); Object[] newElements; Int numMoved = len-index; // Create a new array and copy the original array. if (numMoved == 0) newElements = Arrays.copyOf(elements, len + 1); else { newElements = new Object[len + 1]; System.arraycopy(elements, 0, newElements, 0, index); System.arraycopy(elements, index, newElements, index + 1, numMoved); } newElements[index] = element; // Add data to the copy array setArray(newElements); } finally {lock.unlock(); // Unlock the lock and ensure that the lock is released}}Copy the code

The advantage of this is that when we need to read, the array is immutable because each add() operation does not modify the original array directly. Therefore, when we fetch data from get(), we do not need to lock it

The following code

private E get(Object[] a, int index) {
        return (E) a[index];
    }
Copy the code

summary

CopyOnWriteArrayList realizes the lock free GET () operation through copy-on-write, read-write separation, so CopyOnWriteArrayList can achieve efficient concurrent operation under the scenario of read and write more than less

Ponder: What is the nature of efficient concurrency?

HashTable,CurrentHashMap and CopyOnWriteArrayList have been analyzed. Inefficient concurrency tends to simplify logic and use the same lock to protect data

Efficient concurrency

Either refine the granularity of the lock, such as segmenting the data with segmented locks, or use CAS operations (optimistic locks) to support atomicity per data update, or separate reads and writes (read-write locks are also the idea of read-write separation)

Or you can take advantage of the immutability of the data, and as long as the data is not changed, there is no concurrency problem

Afterword.

The second article in the concurrent series looked at concurrent containers, including pessimistic/optimistic locks, read/write locks, coarse-grained/fine-grained locks, and so on

In the next article, we will analyze the types of these locks from the perspective of source code, combined with relevant theories

I am relieved. See you next time!

If this article inspires you, please give it a thumbs up