C++ concurrent programming practice – 03. Shared data

Article directory

  • Share data
    • Shared data issues
    • Use mutex
      • Protect shared data
      • Conditional competition between interfaces
      • Deadlock and its solution
      • std::unique_lock – flexible lock
      • Passing of mutexes in different domains
      • Lock granularity
    • Ways to protect shared data
      • Initialization process to protect shared data
      • Protect data structures that are updated infrequently
      • Nested lock

Share data

Shared data issues

The problem between threads is that modifying shared data will destroy **invariants**. A node in a doubly linked list can be regarded as an invariant (node value and left and right pointers). When deleting a doubly linked list, you need to modify the left and right nodes of the node respectively, and then delete the original node. During the deletion process, it is not certain whether other threads can access it. There may be threads that access the node that was just deleted. This is a common error in parallelism: race condition.

A race condition in concurrency depends on the execution order of more than one thread, with each thread rushing to complete its own task. A conditional race occurs when an invariant is violated.

Data race: A special condition race that modifies an independent object concurrently. Data race is the cause of undefined behavior.

Race conditions are usually time-sensitive, so the error often disappears completely when the program is run in debug mode, which affects the execution time of the program. When the program is running, its occurrence probability is low, difficult to find and difficult to reproduce. We will use a large number of complex operations to avoid vicious condition competition. Here are some ways to avoid it:

  • Use some kind of protection mechanism for the data structure to ensure that only the modifying thread can see the intermediate state of the invariant. From the perspective of other accessing threads, the modification has either been completed or has not yet started.
  • When modifying data structures and invariants, the modified structure must be able to complete a series of indivisible changes to ensure the state of each invariant, that is, lock-free programming.
  • Use transactions to handle updates to data structures. Some data and reads are stored in the transaction log, and then the previous operations are merged and then committed. This is called “software transactional memory” (STM), but there is no direct support for STM in C++, only a technical specification.

Use mutex

Mutex is the most common mechanism for protecting data in C++, but code also needs to be arranged to protect the correctness of the data and avoid conditional competition between interfaces. But it can cause deadlocks or protect data too much/too little.

Instantiate std::mutex and use member functions lock() to lock and unlock() to unlock. However, it is recommended to use RAII template classes to unlock during destruction, such as std::lock_guard and the enhanced data protection mechanism std::scoped_lock in C++17.

std::mutex some_mutex;
void f(int value){
    std::lock_guard<std::mutex> guard(some_mutex);
    //A new feature has been added in C++17, called template class parameter deduction, and its template parameter list can be omitted
    std::lock_guard guard(some_mutex);
    //C++17 new mechanism std::scoped_lock
    std::scoped_lock guard(some_mutex);
}

In most cases, mutexes are usually placed in the same class as the data that needs to be protected, rather than being defined as global variables. The mutex and the data that need to be protected are defined as private members in the class, which will make the code clearer and make it easier to know when to lock the mutex. When one of the member functions returns a pointer or reference that protects the data, the data will also be destroyed. A pointer or reference with access capability can access (and possibly modify) the protected data without being restricted by a mutex lock. This requires careful design of the interface to ensure that the mutex can lock data access and leave no backdoors.

Protect shared data

The data is safe as long as no member function returns a pointer or reference to the protected data to its caller, either through a return value or as an output parameter. At the same time, it is also important to check whether the member function is called through a pointer or reference.

By treating data protection as a runtime parameter, data security cannot be guaranteed:

class some_data{
    int a;
    std::string b;
public:
    void do_something();
};

class data_wrapper{
private:
    some_data data;
    std::mutex m;
public:
    template<typename Function> void process_data(Function func){
        std::lock_guard<std::mutex> l(m);
        func(data); // 1 Pass "protected" data to user function
    }
};
some_data* unprotected;
void malicious_function(some_data & protected_data){
    unprotected= & amp;protected_data;
}
data_wrapper x;
void foo(){
    x.process_data(malicious_function); // 2 Pass a malicious function
unprotected->do_something(); // 3 Access protected data without protection
}

There is no protection at all, just marking all accessible data structure code as mutually exclusive. From an optimistic point of view, there is still a way: Never pass pointers or references to protected data outside the scope of the mutex.

Conditional competition between interfaces

Multi-threaded access to stack, there is competition between different interfaces:

stack<int> s;
if (! s.empty()){
int const value = s.top(); // 2
s.pop(); // 3
do_something(value);
}

Because between calling empty() and calling top(), there may be a pop() call from another thread and delete the last an element. This is a classic conditional competition. A mutex is used to protect the data inside the stack, but it still cannot prevent the occurrence of conditional competition. This is the inherent problem of the interface.

Solutions (each has its own drawbacks):

  1. Pass in a reference

    Pass the reference of the variable as a parameter into the pop() function to obtain the “pop value”:

    std::vector<int> result;
some_stack.pop(result);

    Disadvantages: An instance of the type on the stack needs to be constructed to receive the target value. Not cost-effective in terms of time and resources; the parameters of the constructor may not be available at that time; the type needs to be assignable (the assignment operation may not be supported).

  2. No exception-throwing copy constructor or move constructor

    A useful option is to limit the use of the thread-safe stack and allow the stack to safely return the required value without throwing an exception. Safe but not reliable.

    std::is_nothrow_copy_constructible and std::is_nothrow_move_constructible make the two functions not throw exceptions but limited. Among user-defined types, there are types that have copy constructors or move constructors that do not throw exceptions, and those that have copy constructors that throw exceptions, but there are more types that do not have move constructors .

  3. Returns a pointer to the popped value

    The advantage is free copying and no exceptions. The disadvantage is that returning a pointer requires managing the memory allocation of the object. std::shared_ptr is a good choice.

  4. “Plan 1 + Plan 2” or “Plan 1 + Plan 3”

Implementation of Option 1 + Option 3:

#include <exception>
#include <memory>
#include <mutex>
#include <stack>
struct empty_stack: std::exception{
const char* what() const throw(){return "empty stack!";};
};
template<typename T>
class threadsafe_stack{
private:
std::stack<T> data;
mutable std::mutex m;
public:
threadsafe_stack() : data(std::stack<T>()){}
threadsafe_stack(const threadsafe_stack & amp; other){
std::lock_guard<std::mutex> lock(other.m);
data = other.data; // 1 execution copy in the constructor body
}
threadsafe_stack & amp; operator=(const threadsafe_stack & amp;) = delete;
void push(T new_value){
std::lock_guard<std::mutex> lock(m);
data.push(new_value);
}
std::shared_ptr<T> pop(){
std::lock_guard<std::mutex> lock(m);
 if(data.empty()) throw empty_stack(); // Before calling pop, check whether the stack is empty
        //Allocate the return value before modifying the stack
 std::shared_ptr<T> const res(std::make_shared<T>(data.top()));
data.pop();
return res;
}
void pop(T & amp; value){
std::lock_guard<std::mutex> lock(m);
if(data.empty()) throw empty_stack();
value=data.top();
data.pop();
}
bool empty() const{
std::lock_guard<std::mutex> lock(m);
return data.empty();
}
};

The granularity of the surface lock in the stack discussion is too small, and vicious condition competition has occurred.

If the lock granularity is too large, it will also reduce operating efficiency.

Using multiple mutexes to protect all data, fine-grained locks are also problematic. The mutex protects an instance of an independent class. The next stage of the lock state is either to leave the locked area and return the locked area to the user, or to have an independent mutex to protect all instances of this class, which is not good.

Deadlock and its solution

That is, let the two mutexes be locked in the same order. std::lockCan lock multiple (more than two) mutexes at one time without the risk of deadlock. This method cannot acquire one of the locks and relies on the developer’s experience.

#include<mutex>
class some_big_object;
void swap(some_big_object & amp; lhs,some_big_object & amp; rhs);
class X{
private:
some_big_object some_detail;
std::mutex m;//Does not support multiple locks, std::recursive_mutex supports it
public:
X(some_big_object const & sd):some_detail(sd){}
friend void swap(X & amp; lhs, X & amp; rhs){
if( & amp;lhs== & amp;rhs) return;
        std::lock(lhs.m,rhs.m);//An exception is thrown when acquiring the second lock, and the first lock will be automatically released
        //Hand over lock management rights
        std::lock_guard<std::mutex> lock_a(lhs.m,std::adopt_lock);
        std::lock_guard<std::mutex> lock_b(rhs.m,std::adopt_lock);
        swap(lhs.some_detail,rhs.some_detail);
        //C++17 provides std::scoped_lock<>, which supports locking during mutex construction
        if( & amp;lhs== & amp;rhs) return;
        std::scoped_lock guard(lhs.m,rhs.m);//Automatically derive template parameters
        swap(lhs.some_detail,rhs.some_detail);
    }
};

Usually deadlocks cannot be foreseen.

Deadlock can occur when two thread std::thread objects call join() on each other.

Recommendations for avoiding deadlocks:

  • Avoid nested locks

    A thread only holds one lock, and multiple locks are locked using std::lock.

  • Avoid calling external code while holding lock

    An external program may acquire a lock causing a deadlock.

  • Acquire locks using a fixed order

    If you must acquire more than one lock and std::lock cannot be used, acquire the locks in a fixed order as shown in the code above.

    Taking linked list deletion as an example (…->A->B->C->…), deleting the linked list sequentially locks ABC. If another thread locks B, the original thread will automatically unlock if it cannot lock. If another thread locks CBA sequentially, the two threads will cause a deadlock.

  • Use hierarchical_mutex (not part of the standard library)

    The application needs to be layered and all mutexes on a given layer identified. When code attempts to lock a mutex and a lower layer already holds the lock, the lock is not allowed. You can check whether the locking operation can be performed at runtime through the number of layers corresponding to each mutex and the mutex used by each thread.

    When multiple mutexes are on the same level, they cannot hold multiple locks at the same time, so the “hand-to-hand” solution requires each mutex to be on a chain, and each mutex is larger than the previous one. One has a lower level value, which is not possible in some cases.

  • Extending beyond locks

    Deadlocks can occur not only between locks, but also in synchronized constructions. If you are waiting for a thread to end, you should determine the level of the thread, so that a thread only needs to wait for threads with a lower level than it to end. A simple method can be used to determine whether the added thread is started in the same function.

std::lock() and std::lock_guard form simple locks and cover most cases. If you need more flexibility, you can use the std::unique_lock template provided by the standard library.

std::unique_lock–flexible lock

std::unique_lock instances are not always associated with the mutex data type. You can pass std::adopt_lock as the second parameter into the constructor to manage the mutex. You can also pass std::defer_lock as the second parameter to indicate that the mutex should remain unlocked. You can let the std::unique_lock object (not a mutex) be obtained by lock(), or pass the std::unique_lock object to std::lock(). std::unique_lock takes up more space and is slightly slower than std::lock_guard.

Use the flag in the std::unique_lock instance to determine whether the instance owns a specific mutex. The flag can be queried through the owns_lock() member variable. Only if there is a flag can it be unlock(). Unless you want to transfer ownership of std::unique_lock or need a more flexible lock, it is best to use std::lock_guard or std in C++17 ::scoped_lock.

Transfer of mutexes in different domains

A std::unique_lock instance does not have a mutex associated with itself, and mutex ownership can be transferred between different instances through move operations. std::unique_lock is a movable but non-assignable type.

The function get_lock() locks the mutex, then prepares the data and returns the lock calling function:

std::unique_lock<std::mutex> get_lock(){
    extern std::mutex some_mutex;
    std::unique_lock<std::mutex> lk(some_mutex);
    prepare_data();
    return lk; //The compiler is responsible for moving the constructor
}
void process_data(){
    //Depends on the function whose return type is std::unique_lock, here is get_lock()
    std::unique_lock<std::mutex> lk(get_lock());//Transfer ownership of unique_lock
    do_something();
}

The flexibility of std::unique_lock also allows instances to relinquish held locks before being destroyed. This is very important for the performance of the application, because increasing the time the lock is held will lead to performance degradation, and other threads will wait for the lock to be released to avoid overrun operations.

Lock granularity

Lock granularity is a hand-waving term used to describe the amount of data protected by a lock. A fine-grained lock can protect a smaller amount of data, and a coarse-grained lock can protect a larger amount of data. Locks are not only able to lock data of appropriate granularity, but also control the lock holding time and which operations can hold the lock while executing. In general, try to reduce the time the lock is held to the minimum possible.

void get_and_process_data(){
    std::unique_lock<std::mutex> my_lock(the_mutex);
    some_class data_to_process=get_next_data_chunk();
    my_lock.unlock(); //Do not let the locked mutex pass the call of the process() function
    result_type result=process(data_to_process);
    my_lock.lock(); //In order to write data, lock the mutex again
    write_result(data_to_process,result);
}

If the holding time is insufficient, the results may not be guaranteed to be valid:

class Y{
private:
    int some_detail;
    mutable std::mutex m;
    int get_detail() const{
        std::lock_guard<std::mutex> lock_a(m);
        return some_detail;
    }
public:
    Y(int sd):some_detail(sd){}
    friend bool operator==(Y const & amp; lhs, Y const & amp; rhs){
        if( & amp;lhs== & amp;rhs) return true;
        int const lhs_value=lhs.get_detail(); //Fine-grained lock
        int const rhs_value=rhs.get_detail(); //Fine-grained lock
        return lhs_value==rhs_value; //It is unlocked at this time, and the value of some_detail may have changed.
    }
};

Sometimes it may not be possible to find a suitable level of granularity because not all accesses to data structures require the same level of protection. In this example, you need to find a suitable mechanism to replace std::mutex.

How to protect shared data

Mutexes are a general-purpose mechanism, but they are not the only way to protect shared data. Locking a mutex after data initialization is purely to protect its initialization process, which will have unnecessary impact on performance. For these reasons, the C++ standard provides a mechanism to purely protect the initialization process of shared data.

Initialization process of protecting shared data

Lazy initialization – Every operation needs to first check the source to know whether the data has been initialized, and then decide whether the data needs to be initialized before using it.

The C++ standard library provides std::once_flag and std::call_once to handle this situation. Just use the std::call_once function. At the end of std::call_once, you can safely know that the pointer has been initialized by other threads and consume more resources. Small.

std::shared_ptr<some_resource> resource_ptr;
std::once_flag resource_flag; // 1
void init_resource(){
    resource_ptr.reset(new some_resource);
}
void foo(){
    std::call_once(resource_flag,init_resource); // A complete initialization can be performed
    resource_ptr->do_something();
}

std::call_once() can be used for lazy initialization of class members.

class X{
private:
    connection_info connection_details;
    connection_handle connection;
    std::once_flag connection_init_flag;
void open_connection(){
     connection=connection_manager.open(connection_details);
}
public:
    X(connection_info const & amp; connection_details_):
    connection_details(connection_details_){}
    void send_data(data_packet const & amp; data){//Initialization (need to pass in additional this pointer)
        std::call_once(connection_init_flag, & amp;X::open_connection,this);
        connection.send_data(data);
    }
    data_packet receive_data(){//Initialization (need to pass in additional this pointer)
        std::call_once(connection_init_flag, & amp;X::open_connection,this);
        return connection.receive_data();
    }
};

Instances of std::mutex and std::once_flag cannot be copied and moved. You need to explicitly define corresponding member functions to operate on these class members.

Static variables are initialized after they are declared. For functions called by multiple threads, this means that there is a conditional race (rushing to define this variable). In the C++11 standard, these problems are solved: initialization and definition occur entirely in one thread, and no other thread can process the initialization before it is completed, and conditional competition terminates in the initialization phase, so that it is faster than later It will be better to deal with it.

Alternatives to std::call_once:

class my_class;
my_class & get_my_class_instance(){
    static my_class instance; // Thread-safe initialization process
    return instance;
}

Protect infrequently updated data structures

A different kind of mutex is needed here. This mutex is often called a “reader-writer lock” because it allows two different ways of use: exclusive access by one “writer” thread and shared access, allowing multiple Concurrent access by “reader” threads.

  • The C++17 standard library provides two types of mutexes: std::shared_mutex and std::shared_timed_mutex.
    • std::shared_timed_mutex supports more operation methods.
    • std::shared_mutex has higher performance advantages.
  • C++14 only provides std::shared_timed_mutex.
  • No mutex type is provided in C++11, but mutexes from the Boost library are available.

Locking can be done with std::lock_guard and std::unique_lock. Use std::shared_lock to gain access.

In order to resolve a domain name to its associated IP address, a DNS entry table is stored in the cache:

#include <map>
#include <string>
#include <mutex>
#include <shared_mutex>
class dns_entry;
class dns_cache{
    std::map<std::string,dns_entry> entries;
    mutable std::shared_mutex entry_mutex;
public:
    dns_entry find_entry(std::string const & amp; domain) const{
        std::shared_lock<std::shared_mutex> lk(entry_mutex);//Protect sharing and read-only
        std::map<std::string,dns_entry>::const_iterator const it=
 entries.find(domain);
        return (it==entries.end())?dns_entry():it->second;
    }
    void update_or_add_entry(std::string const & amp; domain, dns_entry const & amp; dns_details){
        std::lock_guard<std::shared_mutex> lk(entry_mutex);//Exclusive access rights
        entries[domain]=dns_details;
    }
};

Nested lock

The C++ standard library provides the std::recursive_mutex class. Except that it can be locked multiple times on a single instance of the same thread, other functions are the same as std::mutex. **The number of times you lock it, the number of times you need to unlock it! **Of course, using RAII class templates can handle it for you (std::lock_guard and std::unique_lock).

Nested locks are generally used on classes that can be accessed concurrently (a member function calls another member function), so a mutex is used to protect its member data. But this method is too hasty and unreasonable, and the invariants of the corresponding class will usually be destroyed. A better way is to extract a function as a private member of the class. This private member function will not lock the mutex (the lock must be obtained before calling).