1. Several important concepts about high concurrency
1.1 Synchronous and asynchronous
First of all, the synchronization and asynchronous mentioned here refer to function/method call aspects.
Obviously, a synchronous call will wait for the method to return, and an asynchronous call will return instantly, but an asynchronous call will return instantly does not mean that your task has been completed. It will set up a thread in the background to continue the task.
1.2 Concurrency and parallelism
Concurrency and parallelism are similar in external appearance. As shown in the figure, parallelism is when two tasks are performed simultaneously, while concurrency is to do one task at a time and then switch to another task. Therefore, a single CPU cannot be parallel, it can only be concurrency.
1.3 Critical Zone
The critical area is used to represent a public resource or shared data. It can be used by multiple threads, but only one thread can use it at a time. Once the critical area resource is occupied, other threads must wait if they want to use this resource.
1.4 Blocking and non-blocking
Blocking and non-blocking usually describe the mutual influence between multiple threads. For example, if a thread occupies the critical area resource, then all other threads that need this resource must wait in this critical area, and waiting will cause the thread to hang. This is blocking. At this time, if the thread that occupies the resource is unwilling to release the resource, then all other threads blocking in this critical area cannot work.
Non-blocking allows multiple threads to enter the critical zone at the same time
Therefore, the performance of blocking is generally not very good. According to general statistics, if a thread is suspended at the operating system level and has made a context switch, it usually takes 80,000 time cycles to do this.
1.5 Deadlock, hunger, live lock
The so-called deadlock refers to a blockage caused by competing resources or communicating with each other during the execution process of two or more processes. Without external forces, they will not be able to advance. At this time, the system is called deadlocked or the system has a deadlock. These processes that are always waiting for each other are called deadlock processes. Just like the cars in the picture below want to move forward, but no one can move forward.
However, although deadlock is a bad phenomenon, it is a static problem. Once a deadlock occurs, the process is stuck and the CPU occupancy rate is also 0. It will not occupy the CPU, it will be called out. Relatively speaking, it is relatively easy to discover and analyze.
Corresponding to the deadlock is the live lock.
Live lock means that things 1 can use resources, but it allows other things to use resources first; things 2 can use resources, but it also allows other things to use resources first, so both have been humble and cannot use resources.
For example, it’s like you meet someone on the street, who happens to be walking in the opposite direction of you and meet you head-on, you all want to let each other go. You moved to the left, and he moved to the left, but the two of them still couldn't go there. At this time, you move to the right and he moves to the right, and continue in this way.
When a thread obtains a resource, it finds that other threads also think of this resource because they have not obtained all the resources, so in order to avoid deadlocking, they give up all the resources they hold. If another thread does the same thing, they need the same resources, such as A holds a resource, B holds b resource, and after giving up the resource, A obtains b resource, and B obtains a resource, and this is repeated, a live lock occurs.
Live locks are harder to detect than deadlocks, because live locks are a dynamic process.
Hunger means that one or more threads cannot obtain the required resources for various reasons, which makes them unable to execute.
1.6 Concurrency Level
Concurrency levels: blocking and non-blocking (non-blocking is divided into barrier-free, lock-free, and wait-free)
1.6.1 Blocking
When one thread enters the critical section, other threads must wait
1.6.2 Accessibility
Compared with non-blocking scheduling, blocking scheduling is a pessimistic strategy, which believes that modifying data together is likely to make the data bad. Instead of blocking scheduling, it is an optimistic strategy, which believes that modifying data may not necessarily make the data bad. However, it is a strategy of wide entry and strict exit. When it finds that a process has data competition and conflicts in the critical area, the barrier-free scheduling method will roll back the data.
In this barrier-free scheduling method, all threads are equivalent to taking a snapshot of a system. They'll keep trying to take the snapshots until they are valid.
1.6.3 Lockless
It's accessible
Ensure that there is a thread that can win
Compared with accessibility, accessibility does not guarantee that operations can be completed when there is competition, because if it finds conflicts in each operation, it will keep trying. If the threads in the critical area interfere with each other, it will cause all threads to get stuck in the critical area, and then the system performance will have a great impact.
Lockless adds a new condition to ensure that one thread can win each competition, which solves the problem of barrier-freeness. At least it ensures that all threads execute smoothly.
The following code is a typical lock-free calculation code in Java
Lockless is common in Java
while (!atomicVar.compareAndSet(localVar, localVar+1)) { localVar = atomicVar.get(); }1.6.4 No waiting
Lockless
All threads must be completed within a limited step
No hunger
First of all, the premise of no waiting is on the basis of lock-free. Lock-free only ensures that there must be entry and exit in the critical area. However, if the priority of entry is very high, then some threads with low priority in the critical area may be hungry and cannot leave the critical area. Then there is no waiting to solve this problem, which ensures that all threads must be completed within a limited step, and naturally there is no hunger.
No waiting is the highest level of parallelism, which can enable this system to reach the optimal state.
Typical cases without waiting:
If there are only read threads and no thread threads, then this must be without waiting.
If there are both read threads and write threads, and before each write thread, copy the data and then modify the copy instead of modifying the original data, because there is no conflict in the modification of the copy, then the modification process is also without waiting. The final synchronization is only to overwrite the written data.
Since the waiting-free requirement is relatively high and it is difficult to implement, lock-free will be used more widely.
2. Two important laws on parallelism
Both laws are related to acceleration ratio
2.1 Amdahl's Law
Define the calculation formula and theoretical upper limit of the acceleration ratio after parallelization of serial systems
Acceleration ratio definition: Acceleration ratio = System time consumed before optimization / System time consumed after optimization
For example:
Acceleration ratio = System time consumed before optimization / System time consumed after optimization = 500/400=1.25
This theorem shows that increasing the number of CPU processors does not necessarily play an effective role in increasing the proportion of parallel modules in the system. Only by reasonably increasing the number of parallel processors can the maximum acceleration ratio be obtained with the smallest investment.
2.2 Gustafson's Law
Explain the relationship between the number of processors, serial ratio and acceleration ratio
Then the acceleration ratio = nF(n-1) //The derivation process is omitted
As long as there is sufficient parallelization, the acceleration ratio is proportional to the number of CPUs.