Article directory
- Common lock strategies
-
- Optimistic locking VS pessimistic locking
- Read-write lock VS ordinary mutex lock
- Heavyweight lock VS lightweight lock
- Spin lock VS suspend wait lock
- Fair lock VS unfair lock
- Reentrant lock VS non-reentrant lock
- CAS
-
- What is CAS?
- Use of CAS
- ABA issues with CAS
- deadlock
Common lock strategies
Optimistic locking VS pessimistic locking
Optimistic locking and pessimistic locking describe two different locking attitudes.
Optimistic locking: The probability of predicting lock conflicts is low, so the work can be simpler.
Pessimistic lock: The probability of predicting lock conflicts is high, so the work is a little more complicated.
For example: You have to go for an interview tomorrow:
Optimistic approach: go to bed early and get up early, and attend the interview process on time.
Pessimistic approach: Stay up late at night to review, book a flight home, get up early the next morning to prepare, and arrive at the company some time in advance before attending the interview.
Read-write lock VS ordinary mutex lock
Ordinary mutex lock: Just like synchronized, when two threads compete for the same lock, someone will have to block and wait.
Read-write lock: divided into read lock and write lock
There will be no competition between read locks and read locks. It’s okay for multiple threads to read a variable at the same time.
There will be competition between write locks and write locks. Just like an ordinary mutex lock, there is “lock competition” and blocking waiting occurs.
Competition will also occur between read locks and write locks. Just like an ordinary mutex lock, there is “lock competition” and blocking waiting occurs.
Note: In an actual environment, the frequency of reading is much greater than the frequency of writing. Adding read-write locks will reduce “lock competition” and optimize execution efficiency.
Heavyweight lock VS lightweight lock
Heavyweight lock: The cost of locking and unlocking is relatively high. It is a typical logic to enter the kernel state from user mode, and the overhead is relatively large.
Lightweight lock: The overhead of locking and unlocking is relatively small. It is a typical pure user mode logic with low overhead.
Note:
- Optimistic locking and pessimistic locking are considered from a process perspective: they value how much work is done during the locking and unlocking process.
- Heavyweight locks and lightweight locks are considered from the perspective of results: focusing on the time consumed in the locking and unlocking process.
- Usually, optimistic locks are lightweight locks, and pessimistic locks are heavyweight locks.
Spin lock VS suspend waiting lock
Spin lock: If acquisition of the lock fails, immediately try to acquire the lock again, looping infinitely until the lock is acquired.
Advantages: First: CPU resources are not released; Second: if other threads release the lock, this thread can immediately acquire the lock.
Disadvantages: If other threads hold the lock for a long time, CPU resources will be wasted.
Suspend waiting for lock: If the lock acquisition fails, it will enter the blocking waiting state and try to acquire the lock again after a period of time.
Advantages: CPU resources will be released during the blocking waiting phase.
Disadvantages: The lock cannot be obtained in time.
Fair lock VS unfair lock
Premise: The order in which three threads request to acquire the lock: t1, t2, t3
Fair lock: First come, first served. t1 acquires the lock first, then t2 acquires the lock, and finally t3 acquires the lock.
Unfair lock: random scheduling. Who can obtain the lock first among t1, t2 and t3 is random.
Reentrant lock VS non-reentrant lock
Reentrant lock: The same thread locks the same lock twice in a row without deadlock.
Non-reentrant lock: If the same thread locks the same lock twice in a row, it will deadlock.
Summarize:
For synchronized
- Both optimistic locking and pessimistic locking
- It is both a lightweight lock and a heavyweight lock
- The optimistic lock part is implemented based on spin lock; the pessimistic lock part is implemented based on suspend waiting lock.
- It’s a normal mutex lock, not a read-write lock.
- Right and wrong lock
- is a reentrant lock
Note:
synchronized is adaptive. When initially used, optimistic locks, lightweight locks, and spin locks are used; if the current “lock competition” is not fierce, the original state will remain unchanged. If the “lock competition” is fierce, it will automatically upgrade to pessimistic lock, heavyweight lock, or pending lock.
CAS
What is CAS?
CAS (Compare And Swap): Compare and swap.
That is: compare a certain value in memory with the value in CPU register A. If the two values are the same, exchange the value in register B with the value in memory. If different, no operation is performed.
Advantages: This operation is completed through a single command. So it is thread-safe and efficient.
Usage of CAS
- Implementing atomic classes
//Atomic class is mostly used for counting
//count.getAndIncrement = count + +
//count.incrementAndGer = + + count
//count.getAndDecrement = count--
//count.decrementAndGer = --count
public static void main(String[] args) {<!-- -->
AtomicInteger count = new AtomicInteger();
Thread thread = new Thread(() -> {<!-- -->
for (int i = 0; i < 50000; i + + ){<!-- -->
//equivalent to count + +;
count.getAndIncrement();
}
});
Thread thread1 = new Thread(() -> {<!-- -->
for (int i = 0; i < 50000; i + + ){<!-- -->
//Equivalent to count + + ;
count.getAndIncrement();
}
});
thread.start();
thread1.start();
try {<!-- -->
thread.join();
thread1.join();
} catch (InterruptedException e) {<!-- -->
e.printStackTrace();
}
System.out.println(count.get());
}
- Implement spin lock
CAS’s ABA problem
When comparing in CAS, when the values in the main memory and register A are the same, we cannot judge whether the value in the main memory has not changed, or whether it has changed and then changed back.
Prerequisite: The user’s deposit is 1,000 yuan
Solution:
In addition, create a memory (register C) to record changes in data in the memory. for example:
- Save the number of modifications to the main memory, which only increases but does not decrease.
- Save the version number of the main memory, which only increases but does not decrease.
- Save the last modification time. It only increases but does not decrease.
During each comparison, simultaneously compare the data read in register A and register C to see whether it is consistent with the data in the main memory.
Deadlock
Deadlock: After a thread adds a lock, it cannot release the lock.
Scenario 1: One thread, one lock, and the thread locks twice in a row.
Solution: Use reentrant locks, such as: synchronized
Scenario 2: Two threads, two locks.
Solution: Think carefully when designing
//Deadlock case
public static void main(String[] args) {<!-- -->
Object locker1 = new Object();
Object locker2 = new Object();
Thread thread1 = new Thread(() -> {<!-- -->
synchronized (locker1){<!-- -->
System.out.println("In locker1, acquire the lock on locker1");
try {<!-- -->
Thread.sleep(1000);
} catch (InterruptedException e) {<!-- -->
e.printStackTrace();
}
synchronized (locker2){<!-- -->
System.out.println("In locker1, acquire the lock on locker2");
}
}
});
Thread thread2 = new Thread(() -> {<!-- -->
synchronized (locker2){<!-- -->
System.out.println("In locker2, acquire the lock on locker2");
try {<!-- -->
Thread.sleep(1000);
} catch (InterruptedException e) {<!-- -->
e.printStackTrace();
}
synchronized (locker1){<!-- -->
System.out.println("In locker2, acquire the lock on locker1");
}
}
});
thread1.start();
thread2.start();
}
}
Scenario 3: Multiple threads and multiple locks. “The Dining Philosophers Problem”
Solution: 1. Agree on which lock must be taken first and then which lock 2. “Banker’s Algorithm”
Summarize:
Necessary conditions for deadlock:
- Mutually exclusive use. Lock A is occupied by thread 1, and thread 2 cannot use it.
- Not preemptible. Lock A is occupied by thread 1, and thread 2 cannot seize lock A unless thread 1 actively releases it.
- Request and hold. There are multiple locks. After thread 1 gets lock A, it does not want to release lock A, but also wants to get another lock B.
- Waiting cycle. Thread 1 waits for thread 2 to release the lock, and thread 2 waits for thread 1 to release the lock.
Corresponding solution:
- The basic characteristics of locks cannot be solved.
- The basic characteristics of locks cannot be solved.
- Pay attention to yourself when writing code, it is not universal.
- By agreeing on the locking sequence, you can avoid circular waiting. For example: number the lock.