preface

Java concurrent programming series, C A S (Compare and swap), the article style is still illustrated, easy to understand, let readers can also be crazy with the interviewer line.

As an essential basic knowledge of concurrent programming, C A S is also A high frequency examination point during the interview, so it is necessary to know and must know, this article will take readers to in-depth understanding of C A S.

The outline

C A S Basic concepts

C A S (compareAndSwap), also called comparison swap, is A lock-free atom algorithm, mapped to the operating system is A CMPXCHG hardware assembly instruction (ensure atomism), its function is to let C P U update the memory value to the new value, but on the condition that the memory value must be the same as the expected value, And C A S operation does not need to switch between user mode and kernel mode, and directly reads and writes memory in user mode (meaning that there is no blocking/thread context switch).

It contains three parameters C A S (V, E, N). V represents the memory value to be updated, E represents the expected value, and N represents the new value. When V is equal to E, the V value will be updated to N.

In short, C, A, S requires you to give an additional expected value, which is what you think the variable should look like now. If the variable is not what you think it should be, it has been changed by someone else. You just read it back, set the new expected value, and try again.

How does C A S guarantee atomicity

Atomicity refers to the property that one or more operations cannot be interrupted during execution, either by execution, or by execution, not halfway (one or a series of operations that cannot be interrupted).

To ensure the atomicity of C, A, and S, C, P, and U provide the following two methods

  • The bus lock
  • Cache lock

The bus lock

Bus (B U S) is the data transmission mode between computer components, that is to say, C P U and other components are connected to transmit data, is completed by bus, such as C P U read and write memory.

Bus lock refers to the use of the bus lock, the so-called bus lock is the use of the LOCK# signal provided by the bus, when the output of the LOCK# signal on the bus, other bus requests will be blocked.

Cache lock

Although the bus locking mode ensures atomicity, it will cause a lot of blocking and increase the performance overhead of the system during the locking period. Therefore, in order to improve the performance, the idea of reducing the locking range is designed to cache line locking (cache line is the smallest unit of CACHE storage).

Cache lock refers to C U P to lock the cache line, when the cache line in the Shared variables back to writes to the memory, other C P U through the bus mechanism of sniffing sense whether the Shared variables change, if change, let oneself corresponding Shared variables cache line failure, to read the latest data from the memory, Cache locking is implemented based on the cache consistency mechanism, which prevents more than two caches from modifying the same shared variable at the same time (modern Caches almost all support and use cache locking).

C, A, and S

C A S and locks solve the atomicity problem, compared with locks, there is no blocking, thread context you switch, deadlock, so C A S has better performance than locks, but C A S also has disadvantages.

C, A, and S are the following

  • Atomic operations of only one shared variable are guaranteed
  • Spin time too long (based on spin locks)
  • ABAThe problem

Only one shared variable atomic operation is guaranteed

C A S can only be used for one shared variable. If you have multiple shared variables, you can only use locks. Of course, if you have A way to consolidate multiple variables into one variable, you can also use C A S, such as reading and writing the high and low state bits in the lock.

Spin time is too long

When a thread fails to acquire a lock, it does not block and suspend, but tries to acquire it again at intervals until it succeeds. This mechanism is called spinlock.

Spinlocks benefit is that thread holding the lock lock is released in a short time, those who wait for competition where the thread does not lock into the blocking state (without thread context switch/without user mode and kernel mode switch), they just need to wait for a while (spin), wait until after the thread holding the lock release lock can obtain, thus avoiding the user mode and kernel mode switching cost.

The disadvantages of spin locking are obvious. Threads hold the lock for a long time, and the threads waiting for the competing lock keep spinning. In other words, the CPU keeps idling and resources are wasted in a meaningless way, so the number of spins is generally limited.

Finally, the implementation of spin lock can be realized based on C A S. First, define the default value of lockValue object 1,1 represents the lock resource is idle, 0 represents the lock resource is occupied, the code is as follows

public class SpinLock {
    
    //lockValue The default value is 1
    private AtomicInteger lockValue = new AtomicInteger(1);
    
    // Spin the lock
    public void lock(a){

        // Cyclic detection attempts to acquire the lock
        while(! tryLock()){/ / idling}}/ / acquiring a lock
    public boolean tryLock(a){
        // Expected value 1, update value 0, return true on success, false on failure
        return lockValue.compareAndSet(1.0);
    }
    
    / / releases the lock
    public void unLock(a){
        if(! lockValue.compareAndSet(1.0)) {throw new RuntimeException("Lock release failed"); }}}Copy the code

AtomicInteger is an Integer atomic operation class implemented by Java. It also defines three functions lock, tryLock, unLock

TryLock function – gets the lock

  • Expected value 1, updated value 0
  • C A Supdate
  • If the expected value islockValueIf the values are equal, thenlockValueValue is updated to0To return totrueOtherwise, perform the following logic
  • If the expected value islockValueValues are not equal, do not do any updates, returnfalse

UnLock function – Releases the lock

  • expectations0, update the value1
  • C A Supdate
  • If the expected value islockValueIf the values are equal, thenlockValueValue is updated to1To return totrueOtherwise, perform the following logic
  • If the expected value islockValueValues are not equal, do not do any updates, returnfalse

Lock function – spin to get lock

  • performtryLockFunction, returnstrueStop, otherwise the loop continues

If a thread tryLock succeeds, it will execute the block. If a thread tryLock succeeds, it will execute the block. If a thread tryLock succeeds, it will execute the block. A spin thread is tryLock successful.

ABA problem

C A S needs to check whether the memory value to be updated has been changed, and if not, it will be updated. However, there is A case where A value that was originally A changes to B, and then to A, is not changed when C A S checks.

If two threads, thread 1 read into memory value A, thread 1 time slices are used up, switch to the second thread, thread 2 also reads the memory value of A, and change it into B value, to A value and B value reduction, and simply said, modify the order is A – > B – > A, then thread 1 resumed, it found that memory value or A, then execute C A S operation, This is the famous ABA problem, but there seems to be nothing wrong with it.

If it is A simple data structure, there will be no problem. If it is A complex data structure, there may be A problem (AtomicReference can use C A S on the object). Take the linked list data structure as an example, two threads delete the head node through C A S

  • thread1deleteANode,BThe node becomes the head node and is about to executeC A S(A,A,B)When the time slice runs out, switch to the thread2
  • thread2deleteA and Bnode
  • thread2joinC, A,Node, the list node becomesA->C
  • thread1Retrieve the time slice and executeC A S(A,A,B)
  • The loss ofCnode

Add one to your version number (A – > B – > A) and add one to your version number (A – > B – > A) to your AtomicStampedRdference (1A – > 2B – > 3A). You must ask ABA, this must understand).

Lao ke Lao ke

C A S ends here, of course, the subsequent will have Atomic series of articles, with C A S bedding, the back of the Atomic is also very simple, there are other benefits to inform to readers, star of the public, A reader feedback tomorrow, send cool displays A sweepstakes, also didn’t pay attention to the friends, You can pay attention in advance, welcome to participate, ten thousand won ~

Good historical articles recommended

  • Can process, thread and coroutine be confused? A penny for you to know!
  • What is thread safety? This article will give you insight
  • Small white also can understand the Java memory model
  • Nanny Level teaching, 22 images uncover ThreadLocal

About me

Here is A star, a Java program ape who loves technology. The public account “program ape A Star” will regularly share the operating system, computer network, Java, distributed, database and other high-quality original articles. 2021, grow together with you on the road of Be Better! .

Thank you very much for your little brothers and sisters to see here, the original is not easy, the article can be helpful to pay attention to, point a like, share and comment, are support (don’t want white whoring)!

May you and I both go where we want to go. See you in the next article