1. Non-blocking algorithm
Non-blocking algorithms are concurrent algorithms that can safely spawn their threads not through lock spawns, but through low-level hardware-native forms of atomicity - such as compares and swaps. Non-blocking algorithms are extremely difficult to design and implement, but they can provide better throughput and better defense against survival problems such as deadlock and priority inversion. Use low-level atomic machine instructions to replace locks, such as compare-and-swap (CAS).
2. Pessimistic technology
Exclusive locking is a pessimistic technique. It assumes that the worst case scenario occurs (if the lock is not locked, other threads will destroy the object state), and even if the worst case scenario does not occur, the object state is still protected by a lock.
3. Optimistic technology
Dependency conflict monitoring. Update first. If a conflict occurs during monitoring, give up the update and try again, otherwise the update is successful. Now processors have atomic read-modify-write instructions, such as compare-and-swap (CAS, compare-and- swap).
4.CAS operation
CAS has 3 operands, the memory value V, the old expected value A, and the new value to be modified B. If and only if the expected value A and the memory value V are the same, modify the memory value V to B, otherwise do nothing. The typical usage pattern of CAS is: first read A from V, and calculate the new value B based on A, and then use CAS to atomically change the value in V from A to B (as long as no thread changes the value of V during this period) value to another value).
Listing 3. Code illustrating the behavior (but not performance) of compare-and-swap Copy the code below:
public class SimulatedCAS {
private int value;
public synchronized int getValue() { return value; }
public synchronized int compareAndSwap(int expectedValue, int newValue) {
int oldValue = value;
if (value == expectedValue)
value = newValue;
return oldValue;
}
}
Listing 4. Use compare and exchange to implement counter copy code. The code is as follows:
public class CasCounter {
private SimulatedCAS value;
public int getValue() {
return value.getValue();
}
public int increment() {
int oldValue = value.getValue();
while (value.compareAndSwap(oldValue, oldValue + 1) != oldValue)
oldValue = value.getValue();
return oldValue + 1;
}
}
5. Atomic variables
Atomic variables support atomic update operations without lock protection, and the underlying layer is implemented using CAS. There are 12 atomic variables in total, which can be divided into 4 groups: scalar class, updater class, array class and composite variable class. The most commonly used atomic variables are scalar classes: AtomicInteger, AtomicLong, AtomicBoolean, and AtomicReference. CAS is supported on all types.
6. Performance comparison: locks and atomic variables
Under low-to-medium contention, atomic variables can provide high scalability, and the performance of atomic variables exceeds that of locks; under high-intensity contention, locks can more effectively avoid contention, and the performance of locks will exceed the performance of atomic variables. . But in a more realistic practical situation, the performance of atomic variables will exceed the performance of locks.