Preface

Java Concurrent Programming Series Extra ChapterC A S (Compare and swap), the article style is still full of pictures and texts, easy to understand , allowing readers to have a crazy confrontation with the interviewer.

C A Sis an indispensable basic knowledge of concurrent programming.C A Sis also a frequent test site during interviews, soC A Sis a must-know. Definitely, this article will give readers an in-depth understanding ofC A S.

Outline

##C A S Basic Concept

C A S(compareAndSwap)Also called comparison exchange, it is a lock-free atomic algorithm. It is mapped to the operating system as acmpxchghardware assembly instruction (guaranteed atomicity). Its function is to makeC P UUpdate the memory value to the new value, but there is a condition. The memory value must be the same as the expected value, and theC A Soperation does not require switching between user mode and kernel mode. Read and write memory directly in user mode (means no blocking/thread context switching).

It contains3parametersC A S (V, E, N),Vrepresents the memory value to be updated,Erepresents Expected value,Nrepresents the new value. When theVvalue is equal to theEvalue, theVvalue will be updated toNvalue, if theVvalue is different from theEvalue, no update is performed. This is aC A Soperation.

Simply put,C A Srequires you to give an additional expected value, that is, what you think this variable should look like now, if the variable is not you As you can imagine, it means that it has been modified by someone else. You only need to re-read it, set a new expected value, and try to modify it again.

How C A S ensures atomicity

Atomicity refers to the characteristic that one or more operations are not interrupted during the execution ofC P U, either execution, Otherwise, it cannot be executed halfway (One or a series of operations that cannot be interrupted).

In order to ensure the atomicity ofC A S,C P Uprovides the following two methods

• Bus lock
• Cache Lock

Bus Lock

The bus (B U S) is the method of transmitting data between computer components, which meansC P UConnecting and transmitting data with other components is accomplished by the bus, such asC P Ureading and writing memory.

Bus lockmeans thatC P Uuses a bus lock. The so-called bus lock is the ## provided byC P U#LOCK# signal, whenC P Uoutputs theLOCK# signal on the bus, otherC P U's bus requests will be blocked.

Cache Lock

C P Uis designed with the idea of narrowing the locking range. Cache line locking (A cache line is the smallest unit ofC P Ucache storage).

The so-calledcache lockrefers toC P Ulocking thecache line. When the shared variables in the cache line are written back to the memory, otherC P Uwill sense whether the shared variable has changed through the bus sniffing mechanism. If it changes, it will invalidate its corresponding shared variable cache line and read the latest data from the memory again. Cache locking is based on the cache consistency mechanism. Implemented, because the cache consistency mechanism will prevent more than twoC P Ufrom modifying the same shared variable at the same time (ModernC P Ubasically supports and uses the cache locking mechanism) .

Problems with C A S

C A Sand locks both solve the atomicity problem. Compared with locks, there is no blocking, thread context switching, or death. Lock, soC A Shas better performance than lock, butC A Salso has shortcomings.

C A S’s questions are as follows

• Can only guarantee the atomic operation of a shared variable
• The spin time is too long (built on the spin lock Based on)
• ABAQuestion

Only one shared variable can be guaranteed to be atomically operated

C A Scan only target one Shared variables are used. If there are multiple shared variables, you can only use locks. Of course, if you have a way to integrate multiple variables into one variable, it is also good to useC A S, such asstate in read-write locks. The high and low bits of.

Spin time too long

When a thread acquires a lock If it fails, it will not block and suspend, but try to obtain again after a period of time until it succeeds. This cyclic acquisition mechanism is called spin lock (spinlock).

The advantage of spin lock is that the thread holding the lock releases the lock in a short time, and those threads waiting for the lock competition do not need to enter the blocking state (No need for thread context switching/No need for user mode and kernel State switching), they only need to wait (spin), and can obtain it after the thread holding the lock releases the lock, thus avoiding the consumption of switching between user mode and kernel mode.

The disadvantages of spin locks are obvious. Threads hold locks for a long time, and threads waiting for competing locks keep spinning, that is, the CPU keeps idling, and resources are wasted in meaningless places, so spin is generally restricted. frequency.

Finally, let’s talk about the implementation of spin lock. The implementation of spin lock can be based onC A S. First define thelockValueobject default value1,1means the lock resource is free,0means the lock resource is occupied, the code is as follows

public class SpinLock { //lockValue 默认值1 private AtomicInteger lockValue = new AtomicInteger(1); //自旋获取锁 public void lock(){ // 循环检测尝试获取锁 while (!tryLock()){ // 空转 } } //获取锁 public boolean tryLock(){ // 期望值1，更新值0，更新成功返回true，更新失败返回false return lockValue.compareAndSet(1,0); } //释放锁 public void unLock(){ if(!lockValue.compareAndSet(1,0)){ throw new RuntimeException("释放锁失败"); } } }

ThelockValuevariable of typeAtomicIntegeris defined above.AtomicIntegeris implemented byJavabased onC A SIntegerAtomic operation class also defines 3 functionslock, tryLock, unLock

tryLock function-get lock

• Expected value 1, updated value 0
• ##C A SUpdate
• If the expected value is equal to the lockValuevalue, thelockValuevalue is updated to0andtrue# is returned ##, otherwise execute the following logic
• If the expected value is not equal to the
  lockValue value, no update will be made andfalse# will be returned
  ##unLock function-release lock
• Expected value0, updated value1
• #C A SUpdate
• If the expected value is equal to the lockValuevalue, thelockValuevalue is updated to1, returntrue, otherwise execute the following logic
• If the expected value is not equal to the lockValuevalue , does not make any updates, returnsfalse
lock function - spin to acquire lock
• Execute thetryLockfunction and returntrueto stop, otherwise it will keep looping



##As can be seen from the above picture, only the

tryLocksuccessful thread (updateslockValueto0), the code block will be executed. Other threadstryLockspin and wait forlockValueto be updated to1,tryLocksuccessful thread ExecuteunLock(updatelockValueto1), and the spinning thread willtryLocksuccessfully.

ABA Question

C A SNeeds Check Whether the memory value to be updated has been modified, if not, it will be updated. However, there is a situation where if a value was originallyA, it becameB, and then became # again. ##A, whenC A Sis checked, it will be found that it has not been modified.

Assume there are two threads, thread1reads the memory valueA, thread1uses up the time slice, switches to thread2, thread2also read the memory valueA, modified it to theBvalue, and then restored theBvalue to # The ##Avalue, simply put, the modification sequence isA->B->A, and then thread1resumes running, and it finds that the memory value is stillA, and then perform theC A Soperation. This is the famousABAproblem, but it seems that there is no problem.

It’s just a simple data structure, so there really won’t be any problems. If it’s a complex data structure, there may be problems (UsingAtomicReferencecan useC A SOn the object), taking the linked list data structure as an example, two threads delete the head node throughC A S, assuming that the linked list now hasA->Bnodes



• Thread 1Delete Anode, Bnode becomes the head node and is about to be executed# When ##C A S(A,A,B) , the time slice is used up, switch to thread2
• thread
  2 DeleteA and B nodes
• thread
  2 and addC and A nodes, and the linked list node becomesA- >C
• Thread
  1 Reacquire the time slice and executeC A S(A,A,B)
• Lost
  C Node

It is also very simple to solve theA B Aproblem. Just add the version number, and add1every time it changes, that is,A —> B — > A, becomes1A —> 2B —> 3A,AtomicStampedRdferenceis provided inJavato implement this solution (As long as you askC A Sin the interview, you will definitely askABA, you must understand this).