Atomic operation CAS

Reference:

https://zhuanlan.zhihu.com/p/400817892

https://www.bilibili.com/read/cv10686883/

https://blog.csdn.net/www_dong/article/details/119920236

https://blog.csdn.net/niu91/article/details/116308436

https://blog.csdn.net/CringKong/article/details/79966161

1, atomic operation

Atomic operation, an operation that will not be interrupted by the thread scheduling mechanism.Once the operation starts, it runs to the end without any context switches in between.

Typical atomic operations are (atomic operations require hardware support)

Load / Store: read and write memory

Test and Set: For bool variables, if true, return true, if false, set the variable to true and return false.

Clear: Set the bool variable to false.

Exchange: Sets the value at the specified location to the incoming value and returns its old value.

Compare and Swap: Compares the value at the specified position with the expected value, assigning the new value if they are equal, and setting the expected value to itself if they are not equal.Returns whether the setting is successful.

Fetch And series of addition, subtraction, multiplication and division: perform addition, subtraction, multiplication and division on the value at the specified position using the incoming parameters, and return the old value.

2. Race Conditon

int i = 0;i++;mov eax,dword ptr [i] // load i into the eax registeradd eax,1 // add one to the value in eaxmov dword ptr [i],eax // assign the value in eax to the address of i 

There are three steps at the assembly level: read-modify-write.Thread 1 has not written to the memory after modification. Thread 2 gets the CPU and starts to execute. The modified value will be the value that thread 1 has not written to the memory. There is a thread safety problem.

4, thread safety

There are usually the following ways to solve thread safety:

1. Use atomic operations.

2. Lock: pessimistic lock or optimistic lock (no lock)

1, atomic_int num; num++;

In msvc, the atomic_int type proposed by C++11, in the num++ operation, the bottom layer calls the atomic increment function _InterlockedIncrement provided by windows.

2. Pessimistic lock

mutex is a use of pessimistic locking.Assuming concurrency violations will occur, block any operations that might violate data integrity.

3, optimistic lock

Assuming that there will be no concurrency conflicts, each time an operation is completed without locking but assuming there is no conflict, and only checks whether data integrity is violated when the operation is submitted.

CAS (Compare And Swap) operation is a atomic instruction of the CPU, so there is no thread safety problem.

CAS(addr,old,new)

Explanation: Only compare what addr stores with old, and if it is equal to old, assign new to addr.

C++ can be implemented as follows:

bool compare_and_swap(int* pAddr, int nExpected, int nNew) {if (*pAddr == nExpected) {*pAddr = nNew;return true;}elsereturn false;}

The underlying implementation of different compilers is different, but the algorithm idea is the same.

GCC's CAS, the atomic operation of CAS is supported in GCC4.1+.

1) bool __sync_bool_compare_and_swap (type *ptr, type oldval, type newval, ...)2) type __sync_val_compare_and_swap (type *ptr, type oldval, type newval, ...)

CAS in C++11, the atomic class functions in STL in C++11 allow you to cross-platform.

template< class T > bool atomic_compare_exchange_weak( std::atomic* obj,T* expected, T desired );template< class T > bool atomic_compare_exchange_weak( volatile std::atomic* obj,T* expected, T desired );

CAS for Windows

InterlockedCompareExchange ( __inoutLONGvolatile *Target,__inLONGExchange,__inLONGComperand);

Problems with CAS: ABA.

Solution: Double CAS, that is, you can add a version number.

Things like status registers, I/O operations mapped to memory addresses, and variables that involve hardware operations need to be volatile because every operation on them has its meaningstrong>，

In the case of concurrency, multi-threading and multi-tasking should use atomic weight and memory order, or directly add mutualExclusive locks to ensure atomicity and ordering of shared area operations.

So in fact, volatile and atomic are used in different scenarios, and they can even be used superimposed.For example:

 volatile std::atomic value;

This formula means that all operations on value are atomic,