Novices can also compete with BAT interviewers: CAS

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 S is an indispensable basic knowledge of concurrent programming. C A S is also a frequent test site during interviews, so C A S is a must-know. Definitely, this article will give readers an in-depth understanding of C 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 a cmpxchg hardware assembly instruction (guaranteed atomicity). Its function is to make C 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 the C A S operation 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 contains 3 parameters C A S (V, E, N) , V represents the memory value to be updated, E represents Expected value, N represents the new value. When the V value is equal to the E value, the V value will be updated to N value, if the V value is different from the E value, no update is performed. This is a C A S operation.

Simply put, C A S requires 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 of C 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 of C A S, C P U provides 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 means C P UConnecting and transmitting data with other components is accomplished by the bus, such as C P U reading and writing memory.

Bus lock means that C P U uses a bus lock. The so-called bus lock is the ## provided by C P U #LOCK# signal, when C P U outputs the LOCK# signal on the bus, other C P U's bus requests will be blocked.

Cache Lock

Although the bus locking method ensures atomicity, it will cause a lot of blocking during the locking period and increase the performance overhead of the system. Therefore, in order to improve performance, modern

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

The so-called cache lock refers to C P U locking the cache line. When the shared variables in the cache line are written back to the memory, other C P U will 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 two C P U from modifying the same shared variable at the same time (Modern C P U basically supports and uses the cache locking mechanism) .

Problems with C A S

C A S and locks both solve the atomicity problem. Compared with locks, there is no blocking, thread context switching, or death. Lock, so C A S has better performance than lock, but C A S also 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 S can 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 use C A S, such as state 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 on C A S. First define the lockValue object default value 1, 1 means the lock resource is free, 0 means 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("释放锁失败");
        }
    }

}

The lockValue variable of type AtomicInteger is defined above. AtomicInteger is implemented by Java based on C A S IntegerAtomic 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 lockValue value, the lockValue value is updated to 0 and true# is returned ##, otherwise execute the following logic
• If the expected value is not equal to the
  lockValue value, no update will be made and false# will be returned
  ##unLock function-release lock
• Expected value0, updated value1
• #C A SUpdate
• If the expected value is equal to the lockValue value, the lockValue value is updated to 1, return true, otherwise execute the following logic
• If the expected value is not equal to the lockValue value , does not make any updates, returns false
lock function - spin to acquire lock
• Execute the tryLock function and return true to stop, otherwise it will keep looping



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

tryLock successful thread (updates lockValue to 0), the code block will be executed. Other threads tryLock spin and wait for lockValue to be updated to 1, tryLock successful thread Execute unLock (update lockValue to 1), and the spinning thread will tryLock successfully.

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 originally A, it became B, and then became # again. ##A, when C A S is checked, it will be found that it has not been modified.

Assume there are two threads, thread 1 reads the memory value A, thread 1 uses up the time slice, switches to thread 2, thread 2 also read the memory value A, modified it to the B value, and then restored the B value to # The ##A value, simply put, the modification sequence is A->B->A, and then thread 1 resumes running, and it finds that the memory value is still A, and then perform the C A S operation. This is the famous ABA problem, 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 (Using AtomicReference can use C A S On the object), taking the linked list data structure as an example, two threads delete the head node through C A S, assuming that the linked list now has A->B nodes



• Thread1Delete A node, B node 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 Delete A and B nodes
• thread
  2 and add C and A nodes, and the linked list node becomes A- >C
• Thread
  1Reacquire the time slice and executeC A S(A,A,B)
• Lost
  CNode

It is also very simple to solve the A B A problem. Just add the version number, and add 1 every time it changes, that is, A —> B — > A, becomes 1A —> 2B —> 3A, AtomicStampedRdference is provided in Java to implement this solution ( As long as you ask C A S in the interview, you will definitely ask ABA, you must understand this ).

The above is the detailed content of Novices can also compete with BAT interviewers: CAS. For more information, please follow other related articles on the PHP Chinese website!