Common lock strategies
The lock strategies mentioned here are not limited to Java, C++, Python, databases, operating systems… As long as locks are involved, the following lock strategies can be applied
Optimistic locking vs pessimistic locking
The implementer of the lock predicts whether the probability of the next lock conflict (lock competition, two threads lock an object, resulting in blocking and waiting) is high or low, and based on the probability of this conflict, what to do next
~~ These are not two specific locks, but “two types of locks”.
Pessimistic lock: Predictive lock competition is not very fierce.
Optimistic locking: Predicts that lock competition will be fierce.
Generally speaking, pessimistic locks generally do more work and are less efficient, while optimistic locks do less work and are more efficient. But this is not absolute.
The only difference between pessimistic locking and optimistic locking is mainly based on the conclusion of predicting the intensity of lock competition.
Lightweight lock vs heavyweight lock
Lightweight lock: The process of locking and unlocking is faster and more efficient.
Heavyweight lock: The process of locking and unlocking is slower and more efficient.
An optimistic lock is likely to be a lightweight lock, and a pessimistic lock is likely to be a heavyweight lock.
In most cases, optimistic locking is also a lightweight lock.
In most cases, a pessimistic lock is also a heavyweight lock.
Spin lock vs pending wait lock
Spin lock is a typical implementation of lightweight lock.
Suspended wait locks are a typical implementation of heavyweight locks.
Mutex lock vs read-write lock
Mutex lock
synchronized, is a mutex lock
synchronized has only two operations:
1. Enter the code block and lock it
2. Out of the code block, unlock
Locking is just locking, there is no more detailed distinction
Read-write lock
~~ Read-write locks can separate read and write locks.
Read-write lock:
1. Lock the read
2. Lock write
3. Unlock
Note: If multiple threads read the same variable, there will be no thread safety issues!!!
In read-write lock, the agreement is:
1. There will be no lock competition between read locks. There will be no blocking wait, it will not affect the speed of the program, and the code will execute quickly.
2. There is lock competition between write lock and write lock, which slows down the speed, but ensures accuracy.
3. There is also lock competition between read locks and write locks, which slows down the speed but ensures accuracy.
Note:
1. Do not lock unless necessary.
2. Read-write locks are more suitable for situations where one writes and many reads.
3. When multiple threads read the same variable concurrently, there is no thread safety issue, and there is no need for locking control.
4. In many development scenarios, read operations are very frequent, much higher than the frequency of write operations.
5. The Java standard library also provides specific implementations of read-write locks (two classes, read lock class and write lock class).
Fair lock vs unfair lock
Fairness is defined here as “first come, first served”
Fair lock: When the goddess breaks up, the earliest licking dog in the waiting queue will take the position.
Unfair lock: All rain and dew are stained.
Note: The operating system and Java synchronized are both “unfair locks” natively. The locking control of the operating system itself depends on the thread scheduling order. This scheduling order is random and does not take into account how long the thread waits for the lock. Already.
If you want to achieve fair locking, you must introduce additional things on this basis (introducing a queue to let these locked threads queue up).
Reentrant lock vs non-reentrant lock
Non-reentrant lock: A thread locks a lock twice in a row, resulting in a deadlock.
Reentrant lock: A thread can lock a lock multiple times without deadlock.
Note: System-native locks, C++ standard library locks, Python standard library locks…are not reentrant locks!
synchronized is a “reentrant lock”. (When locking, it will be judged to see if the thread currently trying to apply for the lock is already the owner of the lock. If so, it will be released directly)
synchronized lock
Regarding the above six groups of lock strategies, which kind of synchronized lock does it belong to?
synchronized is both a pessimistic lock and an optimistic lock ~~ synchronized will adapt itself according to the intensity of the current lock competition.
It is both a lightweight lock and a heavyweight lock ~~ Synchronized defaults to a lightweight lock. If the current lock competition is found to be fierce, it will be converted into a heavyweight lock.
The lightweight lock part here in synchronized is implemented based on the spin lock method, and the heavyweight lock part here in synchronized is implemented based on the suspend waiting lock method.
synchronized is not a read-write lock.
synchronized is an unfair lock.
synchronized is a reentrant lock.
Summary: The six lock strategies mentioned above can be regarded as “adjectives for locks”.
CAS
CAS ~~ stands for Compare and swap, literally meaning: “Compare and swap”
A CAS involves the following operations:
We assume that the original data V in the memory, the old expected value A, and the new value B that needs to be modified.
1. Compare A and V for equality. (Compare)
2. If the comparison is equal, write B to V. (exchange)
3. Return whether the operation is successful
The most special thing here is that the above-mentioned CAS process is not implemented through a piece of code, but through a CPU instruction => CAS operation is atomic ~~ can avoid thread safety issues to a certain extent
Therefore, in addition to locking, there is a new direction to solve the thread safety problem.
Summary: CAS can be understood as a special instruction provided by the CPU. Through this instruction, thread safety issues can be handled to a certain extent.
CAS pseudocode
Note: The code written below is not atomic. The real CAS is completed by an atomic hardware instruction. This pseudo code is only to assist in understanding the workflow of CAS.
CAS application scenarios
1. Implement atomic classes (classes provided in the Java standard library)
The standard library provides the
java.util.concurrent.atomicpackage, and the classes in it are all implemented in this way. A typical example is theAtomicIntegerclass, in whichgetAndIncrementis equivalent to thei + +operation.
import java.util.concurrent.atomic.AtomicInteger;
/**
* Created with IntelliJ IDEA.
* Description:
* User: fly(Dream Chaser)
* Date: 2023-10-09
* Time: 10:49
*/
public class ThreadDemo28 {<!-- -->
public static void main(String[] args) throws InterruptedException {<!-- -->
// These atomic classes implement operations such as self-increment and self-decrement based on CAS. At this time, such operations do not require locking and are thread-safe.
AtomicInteger count = new AtomicInteger(0);
// Use atomic classes to solve thread safety issues
Thread t1 = new Thread(() -> {<!-- -->
for (int i = 0; i < 5_0000; i + + ) {<!-- -->
// Because java does not support operator overloading, you can only use ordinary methods to express increment and decrement.
count.getAndIncrement();// count + +
//count.incrementAndGet(); => + + count
//count.getAndDecrement(); => count--
//count.decrementAndGet(); => -- count
}
});
Thread t2 = new Thread(() -> {<!-- -->
for (int i = 0; i < 5_0000; i + + ) {<!-- -->
count.getAndIncrement();
}
});
t1.start();
t2.start();
t1.join();
t2.join();
System.out.println(count.get());
}
}
Pseudocode implementationAtomicInteger
2. Implement spin lock
Spin lock pseudocode
Note: CAS belongs to the “special method”, synchronized belongs to the “general method” -> can be used in various scenarios (wide impact)
Typical questions in CAS: ABA questions
The running core of CAS checks whether value and oldValue are consistent. If they are consistent, it is considered that the value has not been modified in the middle, so there is no problem in the next exchange operation. of.
It’s consistent here, maybe it hasn’t been changed. Or maybe it was changed, but restored?!
If the value of value is set to A, CAS determines that value is A. At this time, it may be that value is always A, or it may be that value was originally A, was changed to B, and then restored to A…
The ABA problem is equivalent to buying a mobile phone. The mobile phone you buy may be a new phone or a refurbished phone.
Refurbished machine: Second-hand, it has been recycled by the seller and has undergone some refurbishment operations (replacing the casing and repackaging).
In most cases, ABA will not have much impact on the code/logic, but some “extreme cases” may also have an impact.
example:
The probability of the above scenario is very low!!! On the one hand, it just so happened that Funny clicked a few more times, resulting in multiple deduction actions. On the other hand, just in this very limited time, someone transferred the same amount. .
Solution
In response to the current problem, the solution adopted is to add a version number. Imagine that the initial version number is 1, and each time the version number is modified, it is +1. Then when performing CAS, it is not based on the amount, but on the version number. .At this time, if the version number has not changed, it must not have changed (the version number can only increase, not decrease).