preface

Recently, WE used CAS to solve concurrency problems in new projects, such as currency recharge and consumption, gift competition for MEDALS, etc., so take notes and talk about CAS to learn from each other.

Optimistic lock, pessimistic lock:

So when we talk about CAS, let’s talk about optimistic locks, pessimistic locks.

Pessimistic lock: every time to take data, very pessimistic, feel that will be modified by others, so when taking data will lock. In short, a shared resource is used by only one thread at a time, and the other threads block until the first thread is used up and then transfer the resource to another thread. Synchronized and ReentranLock are the embodiment of pessimistic lock thoughts.

Optimistic lock: Every time you go to fetch data, you are optimistic that it will not be modified. So it’s not locked every time, but when it’s updated, it looks to see if someone else has updated the data in the meantime, and if there is an update, it gets it again, and it makes a judgment, and it keeps repeating until it gets the data that hasn’t been modified. CAS(Compare and Swap) is an implementation of optimistic locking.

CAS algorithm:

CAS involves three operands

1. Memory address V to be read or written

2. The expected original value A for comparison

3. New value B to be written

If the value V of the memory location matches the expected original value A, the processor automatically updates the location value to the new value B. CAS idea: when updating, the value of position V is considered equal to the value of A. If it is equal, it is considered that it has not been changed by other threads and can be updated to the value of B. Otherwise, it is assumed that it has been modified by another thread, does not update to the value of B, and returns the latest value of the current position V.

In JDK source code, CAS idea is embodied:

Decompiling the Unsafe class (with the Java Decompiler tool)

Service scenarios and CAS applications:

Suppose that multiple people A,B,C, etc. give gifts to D, and the one who gives the most total value can become the guardian crown of D, and D has only one guardian crown. If they give gifts to D at the same time, the value of gifts exceeds each other, that is, there is a concurrency problem.

Solution: Refer to the principle of optimistic locking

  • Set the number of optimistic lock attempts after an optimistic lock failure n times
  • Start with the old guardian, the old greatest value giver.
  • If the current old guardian is not empty, construct the current giver as the new guardian.
  • Compare the gift value of the new guardian with the old one and try updating the database.
  • If the old maximum gift value changes when an update is found, drop the update, exit the loop, and try again (n–).
  • If the current old guardian is empty, it indicates that there is no previous guardian, and the new guardian is directly inserted into the table.
  • If the insert fails, the data was changed during the insert, indicating that a new record has preempted the daemons.
  • So, try (n–) again until you run out of times n.

Preemption daemon flowchart:

Code implementation:

Some problems with CAS:

1. The problem of ABA,

In A concurrent environment, if the initial condition is A, the data will be modified if A is found. But even though we’re looking at A, maybe A goes to B, and B goes back to A. At this point, A has changed from A. Even if the data is successfully modified, there may be problems.

2. The CPU overhead

Spin CAS, if executed in a loop that never succeeds, can impose a very high execution overhead on the CPU. So in the preemption daemon example above, the number of attempts is set to n to avoid a loop