【 Memory model and atomic operation 】
One of the important features in C++11 is the new multithreaded aware memory model. In order for C++ to be flexible enough to be used without having to use a lower-level language than C++, it was necessary to allow C++ to be closer to the machine. Atomic types and operations are intended to allow this, providing the capability to perform low-level synchronous operations that can typically be reduced to one or two CPU instructions.
5.1 Memory Model Basics
The memory model has two aspects:
Basic structure: How data is placed in memory.
Concurrency aspect: The structural aspect is important for concurrency, especially for low-level atomic operations.
In C++, it’s all about objects and memory locations.
5.1.1 Objects and Memory Locations
All data in C++ is made up of objects. This is not to say that you can create a new class derived from int (primitive type), nor does it mean that primitive types have member functions. Objects are defined as “storage areas” in the C++ standard, although it assigns attributes (such as type and life cycle) to these objects. Regardless of type, objects are stored in one or more memory locations. Each such memory location is either an object (or child object) of scalar type or a sequence of adjacent bitfields. If you use bitfields, it is important to note that even though adjacent bitfields are different objects, they still count as the same memory location.
- Each variable is an object that contains members of other objects.
- Each object occupies at least one memory location.
- Variables of basic types such as int or char have exactly one memory location, regardless of size, even if they are adjacent or part of an array.
- Adjacent bitfields are part of the same memory.
Note: a “bitfield” divides the binary bits in a byte into several distinct regions and states the number of bits in each region. Each domain has a domain name that allows you to operate by domain name in the program. This allows several different objects to be represented as a binary field of one byte. Bit-segment members must be declared as int, unsigned Int, or signed int (short char long).
5.1.2 Objects, memory locations, and concurrency
If two threads access different memory locations, there is no problem, but once they access the same memory location, there is a high possibility of contention. To avoid contention conditions, there must be a mandatory order between the two threads’ accesses. One way to ensure a certain order is to use mutex. Another approach is to use atomic operations on the same or other memory locations to impose an order between the accesses of the two threads. If more than two threads access a memory location, each pair of accesses must have an explicit order.
If two accesses to the same memory location from separate threads are not ordered, one or both of the accesses are not atomic, and one or both are write operations, then this is data contention and leads to undefined behavior. So we can use atomic operations to access competing memory locations to avoid uncertain behavior. But that doesn’t stop the competition itself — the memory location that the atomic operation touches is still undefined in the first place, but it brings the program back to the realm of determined behavior.
5.1.3 Change sequence
Every object in a C++ program has a certain modification order. It consists of all writes to the object from all threads in the program, starting with the initialization of the object. In most cases, the order varies from run to run, but it must be consistent across all threads in the system for any given program execution. If atomic types are not used, it is the developer’s responsibility to ensure that there is enough synchronization to ensure that threads agree on the order in which each variable should be modified. If different threads see different sequential values of a variable, there will be data contention and undefined behavior. If atomic operations are used, the compiler is responsible for ensuring that these synchronizations are in place.
5.2 atomic operations and types in C++
5.2.1 Standard atomic types
Standard atomic types are defined in the
header, and standard atomic types almost always have an is_lock_free() member function that lets the user decide whether an operation on a given type is done directly with the atomic instruction (xIiss_lock_free () returns true), Or by using a lock inside the compiler and library (x.is_lock_free() returns false). The only type that does not provide an IS_lock_free () member function is STD ::atomic_flag. This type is a very simple Boolean identifier, and operations on this type are required to be lockless.
The remaining atomic types are all accessed through STD :: Atomic <> class template specialization and have more complete functionality, but may not be lockless. On most platforms, we consider atomic variants of built-in types (e.g., STD ::atomic
and STD: Atomic
) to be truly unlocked, but not required.
In addition to using STD :: Atomic <> directly, you can use a set of names in the table below. These alternative types may refer to the corresponding STD :: Atomic <> specialization or may be the base class of that specialization, and mixing within a program may result in non-portability.
| Atom type | Corresponding specialized |
|---|---|
atomic_bool |
std::atomic<bool> |
atomic_char |
std::atomic<char> |
atomic_schar |
std::atomic<signed char> |
atomic_uchar |
std::atomic<unsigned char> |
atomic_int |
std::atomic<int> |
atomic_uint |
std::atomic<unsigned> |
atomic_short |
std::atomic<short> |
atomic_ushort |
std::atomic<unsigned short> |
atomic_long |
std::atomic<long> |
atomic_ulong |
std::atomic<unsigned long> |
atomic_llong |
std::atomic<long long> |
atomic_char16_t |
std::atomic<char16_t> |
atomic_char32_t |
std::atomic<char32_t> |
atomic_wchar_t |
std::atomic<wchar_t> |
Similarly, the C++ standard library provides a set of typedefs for atomic types, corresponding to nonatomic library typedefs like STD ::size_t. (Most are prefixed with atomic_).
Traditionally, standard atomic types are non-copiable and non-assignable because they do not have copy constructors and copy assignment operators. But they do support assignment from the corresponding built-in type and implicit conversion assignment, as do the direct load() store() member functions, exchange() compare_exchange_weak(), and compare_exchange_strong(). Them in appropriate places also supports compound assignment operator: + =, = =, *, | =, etc., in view of the specialized integer and a pointer, also support the + + and -.
However, the STD :: Atomic <> class template is not just a set of specializations, it is also a master template. Can be used to create an atomic variant of a user-defined type. Because it is a generic class template, operations are limited to load() store() (assigning values to and from user-defined types), exchange() compare_exchange_weak(), and compare_exchange_strong(). The optional order of the three types of operations will be illustrated below:
- ** Store ** operations: can include memory_ORDER_RELAXED, memory_ORDER_RELEASE, or memory_order_seq_CST orders.
- ** Load ** operations: can include memory_ORDER_RELAXED, MEMORy_ORDER_CONSUME, memory_ORDER_acquire, or memory_order_SEq_CST orders.
- ** read-modify-write ** operation, Can include memory_ORDER_relaxed, memory_ORDER_CONSUME, memory_ORDER_ACQUIRE, MEMORY_ORDER_RELEASE, memorY_ORDER_ACq_rel, or Memory_order_seq_cst order.
The default order for all operations is memory_ORDER_seq_cst.
5.2.2 Operations on STD ::atomic_flag
STD ::atomic_flag is the simplest standard atom type and represents a Boolean flag. Objects of this type can be in one of two states: set or clear. Objects of this type must be initialized to a clear state using ATOMIC_FLAG_INIT (), as you will see in the code below. This is the only atomic type that requires special handling for initialization, and it is also the only type that is guaranteed to be unlocked. Objects of this type have a state store duration, so static initialization is guaranteed, meaning there is no problem with the order of initialization, which is always initialized on the first operation of the identity.
Once an identity has been initialized, there are only three things you can do with it: destroy, clean, or set it up, as you’ll see in an example.
- Implement spinlocks using STD ::atomic_flag
#include <iostream>
#include <atomic>
#include <thread>
#include <mutex>
class spinlock_mutex
{
std::atomic_flag flag;
public:
// The constructor is initialized
spinlock_mutex() :flag(ATOMIC_FLAG_INIT) { }
// Spin lock lock
void lock(a)
{ // Trying to set up a non-blocking loop here will cause some degree of busyness etc
while (flag.test_and_set(std::memory_order_acquire));
// test_AND_set is a read modify write operation that requires the STD ::memory_order_acquire order
Memory_order_seq_cst by default
}
/ / unlock
void unlock(a)
{
// Clearly mark clear as a storage operation that cannot have STD ::memory_order_acquire
// or the memory_order_ACq_rel order, which can be given a memory_order_RELEASE or the default order.
flag.clear(std::memory_order_release); }};// Test the function body
int main(int argc, const char** argv) {
spinlock_mutex m;
std::thread t1([&]{
m.lock();
std::cout << "---------------------t1 get the mutex.------------------\n" << std::endl;
std::this_thread::sleep_for(std::chrono::milliseconds(5000));
m.unlock();
std::cout << "+++++++++++++++t1 sleep 5s and release mutex++++++++++++\n" << std::endl;
});
std::thread t2([&]{
std::this_thread::sleep_for(std::chrono::milliseconds(1000));
std::cout << "t2 try get mutex----------------------------------------\n" << std::endl;
m.lock();
std::cout << "---------------------t2 get the mutex.------------------\n" << std::endl;
std::this_thread::sleep_for(std::chrono::milliseconds(3000));
m.unlock();
std::cout << "+++++++++++++++t2 sleep 3s and release mutex++++++++++++\n" << std::endl;
});
t1.join(a); t2.join(a);return 0;
}
/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * the results: ---------------------t1 get the mutex.------------------ t2 try get mutex---------------------------------------- +++++++++++++++t1 sleep 5s and release mutex++++++++++++ ---------------------t2 get the mutex.------------------ +++++++++++++++t2 sleep 3s and release mutex++++++++++++ **************************************************************/
Copy the codeHowever, the biggest problem with this type is that it does not provide unmodified query operations, so it cannot be used as a general Boolean identifier in the generous case, and in some cases can cause serious busy, etc., which is not reasonable, so it is not recommended.
5.2.3 requires based onstd::atomic<bool>The operation of the
STD :: Atomic
is a more fully functional Boolean flag than STD ::atomic_flag. Although it is still non-copy-constructed and copy-assigned, it can be constructed from a non-atomic bool, as well as assigned from a non-atomic bool to an instance of STD :: Atomic
. Several operations on Boolean atomic types are provided below:
Load: no modification query.
Store: Sets the state T or F.
Exchange: read-modify-write, write new state and return old state.
Here is a program to demonstrate usage:
#include <sstream>
#include <locale>
#include <iostream>
#include <atomic>
#include <thread>
#include <mutex>
int main(int argc, const char** argv) {
//bool Atomic type
std::atomic<bool> flag;
T1 / / thread
std::thread t1([&]{
flag = false; // construct from a non-atomic bool
std::cout << "t1 set flag = FALSE by = operator.\n";
std::this_thread::sleep_for(std::chrono::milliseconds(3000));
flag.store(true); // Set the value with store()
std::cout << "t1 set flag = TRUE by store().\n";
std::this_thread::sleep_for(std::chrono::milliseconds(3000));
// Set the value with exchange() and keep the old value
bool old_flag = flag.exchange(false, std::memory_order_acq_rel);
std::cout << "t1 set flag = FALSE by exchange().\n";
std::cout << "t1::old_flag = " << std::boolalpha << old_flag << std::endl;
});
std::thread t2([&]{
std::this_thread::sleep_for(std::chrono::milliseconds(1000));
for (size_t i = 0; i < 5; i++)
{ // Use load without modifying query
if (flag.load(std::memory_order_acquire))
{
std::cout << "t2 read flag is TURE by load().\n";
}
else
{
std::cout << "t2 read flag is FALSE by load().\n";
}
std::this_thread::sleep_for(std::chrono::milliseconds(3000)); }});
t1.join(a); t2.join(a);return 0;
}
/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * the results: t1 set flag = FALSE by = operator. t2 read flag is FALSE by load(). t1 set flag = TRUE by store(). t2 read flag is TURE by load(). t1 set flag = FALSE by exchange(). t1::old_flag = true t2 read flag is FALSE by load(). t2 read flag is FALSE by load(). t2 read flag is FALSE by load(). ************************************************/
Copy the codeIn addition to the above basic functions, there is another operation called ** “compare/exchange” **, which comes in the form of compare_exchange_weak() and compare_exchange_strong() member functions.
Usage: Compares the atomic variable with the supplied expected value (the first argument), if the two are equal, updates the atomic type object to the expected value (the second argument), and returns true; If not, the expected value (the first argument) is updated to the actual value of the atomic variable and returns false. Let’s take a simple example
bool flag;
int exp =0;
std::atomic<int> data;
data = 0;
// update data == exp so data will be updated to 2 with flag set to true
flag = data.compare_exchange_strong(exp, 2);
Data =2, exp=0, flag=true
//------------------------------------------------------------
bool flag;
int exp =1;
std::atomic<int> data;
data = 0;
// Compare updates to data! = exp so exp will be updated to 0 with flag set to false
flag = data.compare_exchange_strong(exp, 2);
Data =0, exp=0, flag=false
Copy the codeNote that compare_exchange_weak may fail and return false for actual equality (for a variety of reasons, such as physical storage problems, comparison logic problems, or function execution failures (forced cutting out the execution sequence)). Unlike compare_exchange_weak, the strong version of the compare-and-exchange operation does not allow false for false failure, that is, false only if the value of the comparison operation is different, thereby eliminating the dependency on loops to some extent. However, on some platforms, compare_exchange_weak performs better if the algorithm itself requires a loop operation to check. My research here is not very in-depth, and I will make up for it later.
5.2.4 std::atomic<T*>Pointer arithmetic operations
Fetch_add (), fetch_sub(), +=, -=, ++, –; fetch_add(); fetch_sub(); Fetch_add (), fetch_sub(), +=, and -=. The following code explains the differences between them.
int a[100];
std::atomic<int*> p = a;
// here p moves 2 bits to the third element, but returns the original value of p, that is, x to the array header
//fetch_add(); It is acceptable to have any memory sequence, and memory_ORDER_SEq_CST is accepted by default
int* x = p.fetch_add(2);
/// p moves 2 bits to the third element, but the return value is the current value of p, i.e. x points to the third element
int* x = (p+=2);
//fetch_sub() and -= do the same
Copy the code5.2.5 Operation of standard atomic integers
In addition to the usual set of operations (load(), store(), exchange(), compare_exchange_weak(), and compare_exchange_strong()), Atomic integers like STD ::atomic
or STD :: Atomic
also have a fairly broad set of operations available: Fetch_xor fetch_for fetch_sub fetch_add () () () () the operation of the composite form (+ =, =, & =, | = and ^ =), prefix/suffix from increasing and prefix/suffix from minus (+ + x, x++, – x, x). This is not a complete set of compound assignments that can be performed on ordinary integers. The division, multiplication, and displacement operators are missing. Since atomic integer values are usually used as counters or bitmasks, this is not a particularly noticeable loss. This can be done by using compare_exchange_weak() in a loop, if desired.
5.2.6 std::atomic<>Initial class template
In addition to standard atomic types, the existence of primary templates allows the user to create an atomic variant of a user-defined type. However, if a user-defined type is used in a primitive template, the type must meet the following criteria:
The user-defined type UDT uses STD :: Atomic, which must have a trivial copy-assignment operator. This means that the type must not have any virtual functions or virtual base classes, and must use copy assignment operators generated by the compiler.
Each base class and non-static data member of a user-defined type must have a trivial copy-assignment operator. This essentially allows the compiler to use memcpy() or an equivalent operation for assignment, since there is no user-written code to run.
Finally, the type must be bitwise comparable. This comes with the assignment requirement that you not only have to be able to copy objects of type UDT using memcpy(), but you also have to be able to compare instances for equality using memcmp().
In general, the compiler cannot generate lockless code for STD :: Atomic
, so it must use an internal lock for all operations. If user-provided copy-assignment or comparison operators are allowed, this would require passing a reference to protected data as an argument to a user-provided function, thus violating the rule (Pointers or references to protected data cannot be passed externally). Finally, these restrictions increase the chances that the compiler will be able to exploit atomic instructions directly for STD :: Atomic
(and thus make a particular instance lock-free) because it can treat user-defined types as a set of raw bytes.
Note: Although you can use STD ::atomic
or STD ::atomic
, because the built-in floating-point types do satisfy the criteria used with memcpy and memcMP, But this behavior can be surprising in the case of compare_exchange_strong. If the stored value has a different representation, an incorrect result may be returned even if the old stored value is equal to the comparison value. There are floating point atomic types that have no arithmetic operations.
In addition, STD :: Atomic <> initial class templates do not allow classes to create arrays containing: counters, identifiers, Pointers, or even simple data elements.
5.2.7 Free functions of atomic operations
The simple understanding of the free function of atomic operation is to realize the function of member function with non-member function. Generally, the function of this free function is exactly the same as that of member function. In order to be compatible with C, the parameter receives pointer of atomic variable instead of reference. The specific usage and details are not described here.
5.3 Synchronizing operations and Forcing sequence
5.3.1 synchronizes – with relationships
A synchronization-with relationship is something that you can only get between operations on an atomic type. If a data structure contains atomic types and operations on the data structure perform legitimate atomic operations internally, operations on the data structure (such as mutex locking) may provide this relationship, but fundamentally the synchronized-with relationship only comes from operations on the atomic type.
If thread A stores A value and thread B reads it, there is A synchronization-with relationship between the storage in thread A and the loading in thread B.
5.3.2 happens-before relations
The happens-before relationship is the basic building block of the order of actions in a program, specifying which actions will see the results of other actions. For A single thread, if one operation A precedes another operation B, then A must be limited to B, and A must be finished when B is executed. However, if the operation occurs in the same statement, there is generally no happens-before relationship, for example:
#include <iostream>
void foo(int a, int b)
{
std::cout << a << "," << b << std::endl;
}
int get_num(a)
{
static int i = 0;
return i++;
}
int main (int argc, char** argv)
{ // the get_num() call is unordered, either "1,2" or "2,1"
foo(get_num(), get_num());
}
Copy the codeSometimes operations within a single statement are ordered, such as using the built-in comma operator or using the result of one expression as an argument to another. Happens-before relationships enforce orders, such as that an operation must happen after an operation. The simplest example is reading and writing data. Generally speaking, passing data requires that the read must come after the write.
5.3.3 Memory sequence of atomic operations
There are six ordering options that can be applied to operations on atomic types, representing three models: ** Consistent ** order, acquisition-release order, and relaxed ** order:
Memory_order_relaxed loose
Memory_order_consume get – release
Memory_order_acquire acquired – Released
Memory_order_relesae gained – released
Memory_order_acq_rel gets – released
Memory_order_seq_cst is in the same order
These different memory ordering models may have different costs on different CPU architectures. For example, in based on by processor rather than making changes is to effectively control the visibility of the operation on the architecture of system (people speaking is processor independent handling most of the operations and not visible to the user), the order of the same order relative to the order or loose order being released – and – release order relative to loose order may require additional synchronization instructions. If these systems have many, many processors, these additional synchronization instructions can take up significant time and reduce the overall performance of the system. On the other hand, to ensure atomicity, cpus using x86 or x86-64 architectures (such as Interl and AMD processors common in desktop PCS) do not require additional instructions for fetch-release sorting beyond what is needed, and even for load operations, sequential sequential ordering does not require any special processing. Although there is a little extra cost in storage.
Different memory ordering models allow gurus to leverage finer order relationships to improve performance, which is advantageous when allowing default consistent ordering in less critical cases.
Sequential order
The default order is named sequential consistent order because it means that the behavior of the program is consistent with a simple sequential worldview. If the operations on all instances of atomic types are sequential, a multithreaded program behaves as if all those operations were executed in a particular order by a single thread. This is by far the easiest memory order to understand, which is why it’s worth it as the default. All threads must see operations in the same order, eliminate inconsistencies, and verify that your code behaves as expected in other programs. This also means that operations cannot be rearranged. If your code has one operation in one thread before another, the order must be visible to all other threads.
From the point of view of synchronization, a sequential store is synchronous with a sequential load of the same variable that reads the store. This provides a sequential constraint for two (or more) thread operations, but sequential consistency is more powerful than this. In systems that use sequential sequential atomic operations, all sequential sequential atomic operations completed after loading must also occur after storage in other threads. Ease of understanding, however, comes at a cost. On a weakly sequential machine with many processors, it can lead to significant performance penalties, because the overall order of operations must be consistent with that between processes, potentially requiring intensive (and expensive) synchronization between processors. That said, some processor architectures (such as the common x86 and x86-64 architectures) offer relatively inexpensive sequential consistency, so if you are concerned about the performance impact of using sequential consistency, you need to check the documentation of the target processor architecture you are using.
#include <iostream>
#include <atomic>
#include <thread>
#include <assert.h>
std::atomic<bool> x, y;
std::atomic<int> z;
void write_x(a)
{
x.store(true, std::memory_order_seq_cst);
}
void write_y(a)
{
y.store(true, std::memory_order_seq_cst);
}
void read_x_then_y(a)
{
while(! x.load(std::memory_order_seq_cst))
{
if (y.load(std::memory_order_seq_cst)) { ++z; }}}void read_y_then_x(a)
{
while(! y.load(std::memory_order_seq_cst))
{
if (x.load(std::memory_order_seq_cst)) { ++z; }}}int main(int argc, const char** argv) {
x = false;
y = false;
z = 0;
std::thread a(write_x);
std::thread b(write_y);
std::thread c(read_x_then_y);
std::thread d(read_y_then_x);
a.join(a); b.join(a); c.join(a); d.join(a);assert(z.load() != 0);
std::cout << "/* message */" << std::endl;
return 0;
}
// There are two possible scenarios for this code execution
/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * the first one: a: 05 _04. CPP: 58: int main (int, const char * *) : an Assertion ` z.l oad ()! = 0' Aborted (core dumped) /* message */* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /Copy the codeThe book says that Z is never equal to 0 by any means, but based on my tests on the virtual machine, z is likely to be zero (6 out of 7 times out of 10). The book makes sense because STD :: memory_order_seq_Cst enforces order, It also creates a separate complete order for all memory operations that have this label, in the order we saw. Load must occur before store. I don’t know what the book says anyway, given my results, but what does consistent order mean? If the load must occur before the store, then either thread C or thread D will enter the while loop, and at least one thread will enter the if to modify z, so it must see /* message */. But obviously my test results are not like this, there is a high probability that x and y will be stored when c and D threads are not loaded.
So this paragraph to me whole can’t, hope big guy give directions.
Loose the order
Operations performed in loose order on atomic types do not participate in the synchronization-with relationship. For a single thread there is no change, but for multithreading there is almost no requirement for the order of the other threads. The only requirement is that access to a single atomic variable from the same thread cannot be rearranged, and once a given thread has seen a particular value of the atomic variable, subsequent reads from that thread cannot get the earlier value of that variable. The order in which each variable is modified is the only thing shared between threads using memory_ORDER_RELAXED without additional synchronization.
#include <iostream>
#include <atomic>
#include <thread>
#include <assert.h>
std::atomic<bool> x, y;
std::atomic<int> z;
void write_x_then_y(a)
{
x.store(true, std::memory_order_relaxed);
y.store(true, std::memory_order_relaxed);
}
void read_y_then_x(a)
{
while(! y.load(std::memory_order_relaxed))
{
if (x.load(std::memory_order_relaxed)) { ++z; }}}int main(int argc, const char** argv) {
x = false;
y = false;
z = 0;
std::thread a(write_x_then_y);
std::thread b(read_y_then_x);
a.join(a); b.join(a);assert(z.load() != 0);
return 0;
}
Copy the codeThis time assert does trigger (but so do those in the same order), so I’m not sure if the features described in the book are correct. An operation on an atomic type is performed in a free sequence, without any synchronization, requiring only atomicity for the operation. For example, in A thread, write A first, then B. But the order observed in A multicore processor might be to write B first, then A. Free memory order can be freely reordered for different variables.
Acquisition-release sequence
- memory_order_acquire
With the atomic operation of memory_ORDER_ACQUIRE, no read or write operation of the current thread can be reordered before this operation. For example, A line reads A, then B, then C, then D with the memeorY_ORDER_acquire operation. In multi-core processors, the order D can only be before C, and D can not be read first and C can not be read last. However, it is possible for A or B to be rearranged after C. Memory_order_acquire is used to get data and is placed at the beginning of the read operation.
- memory_order_release
With an atomic operation of memory_order_RELEASE, no read or write operation of the current thread can be rearranged after this operation. For example, A line writes A, then B, then C, then D with memeory_order_release. In A multicore processor, the order AB can only be observed before C, and C cannot be followed by A or B. However, it is possible for D to be rearranged before C.
Memory_order_release is used to publish data and is placed at the end of a write operation.
“Get” and “release” are usually paired to synchronize threads.
- memory_order_acq_rel
Memory_order_acq_rel A read-change-write operation with this memory order is both a get load and a release operation. No operation can be rearranged from this operation to this operation, and no operation can be rearranged from this operation to this operation.
- memory_order_consume
Memory_order_consume only ensures that the object it identifies is stored ahead of those operations that need to load the object.
summary
This sequence is true and I am confused… I don’t know if it’s something in the book or something in the environment I’m compiling, but it just doesn’t work. Hope to have big guy to help answer the question, thank you!
I’ll tell you what. I’m not going to use too much depth here.