Geek Answers Handbook

Sorting memory using spin_flag lock

I am trying to familiarize myself with the new C ++ 11 memory ordering concepts and believe that I had a pretty good understanding until I came across this spin lock implementation:

#include <atomic> namespace JayZ { namespace Tools { class SpinLock { private: std::atomic_flag spin_lock; public: inline SpinLock( void ) : atomic_flag( ATOMIC_FLAG_INIT ) {} inline void lock( void ) { while( spin_lock.test_and_set( std::memory_order_acquire ) ) ; } inline void unlock( void ) { lock.clear( std::memory_order_release ); } }; } }

This, for example, is equivalently mentioned in http://en.cppreference.com/w/cpp/atomic/atomic_flag
as well as in Concurrency in Action. I also found this somewhere here in SO.

But I just don’t understand why this would work! Imagine that thread 1 calls lock () and test_and_set () returns 0 because the old value -> thread 1 acquired a lock.
But then stream 2 goes and tries to do the same. Now, since there has not been a single “storage synchronization” (release, seq_cst_acq_rel), the stream of the 1st storage in spin_lock should be of a relaxed type.
But it follows from this that it cannot be synchronized by imao with thread 2 read by spin_lock. This should make it possible for thread 2 to read the value 0 from spin_lock and thus also acquire a lock.
Where is my mistake?

+4
source share
3 answers

Your mistake is to forget that spin_lock is atomic_flag , and therefore test_and_set is an atomic operation. memory_order_acquire and memory_order_release necessary to prevent read transitions before locking or writing from migration after unlocking. The lock itself is protected by atomicity, which always includes visibility.

+3
source

test_and_set operations with atomic flags are defined as read-modify-write operations that have special characteristics, one of which is:

Atomic read-modify-write operations should always read the last value (in the order of modification) written before the write associated with the read-modify-write operation. [n3337 § 29.3 / 12]

This is why fetch_add , for example, works, while simple load operations are not required to read the last value in modification order.

+1
source

For a given atomic variable, there exists a “modification order” for it. After thread 1 test_and_sets is a value from 0 to 1, it is not possible for thread 2 to see 0.

The memory order affects how all other memory addresses are synchronized. If one thread changes an atomic variable with memory order_release, then any thread that reads the same variable with memory_as_akir "sees" each memory, changes the first thread made before its release.

Acquisition and release is not related to the atom. This means that each thread that successfully blocks the spin lock "sees" changes in each thread that has previously blocked it.

Modification order is the key to blocking the algorithm. Both threads 1 and 2 try to make test_and_set on the same variable, therefore, according to the rules, one modification "occurs before" the other. Since test_and_set, which "occurs before", the other goes into "progress", at least one thread should always make progress. This is the definition of lockfree

+1
source

More articles:


All Articles