Preface:

The main content

• Problems caused by sharing data

• Protect data with mutex

• Alternatives to data protection

2.1 Problems Caused by Data Sharing

1. Condition competition

Suppose you go to the cinema to buy a ticket. If you go to a big movie theater and there are lots of cash registers, lots of people can buy tickets at the same time. When another checkout counter is selling tickets to the movie you want to see, your seat options depend on the seats you have reserved. When there are only a few seats left, that means it could be a race to see who gets the last ticket. This is an example of conditional competition: your seat (or your movie ticket) depends on the relative order of the two purchases.

The formation of race conditions in concurrency depends on the relative order of execution of more than one thread, each thread competing to complete its own task. In most cases, even if the order of execution is changed, the competition is healthy and the results are acceptable. For example, if you have two threads adding tasks to a processing queue at the same time, it doesn’t matter who comes first because the invariants provided by the system remain the same. Conditional competition occurs when invariants are destroyed, as in the case of bidirectional linked lists. Conditional competition for data in concurrency is usually expressed as malignant conditional competition, and we are not interested in benign conditional competition that does not cause problems. The C++ standard also defines the term data race, a special kind of conditional race: the concurrent modification of a single object, and data race is the cause of (terrible) undefined behavior.

Vicious conditional races typically occur when more than one block of data is modified, for example, two join Pointers (Figure 3.1). Because the operation accesses two separate blocks of data, separate instructions will modify the block, and the other thread may access the block while one thread is in progress. Because the probability of occurrence is too low, conditional competition is difficult to find, it is also difficult to reproduce. If the CPU instructions are continuously modified, the probability of the problem recur is quite low, even if the data structure is accessible to other concurrent threads. When the system load increases, the probability of recurrence of execution sequence problems increases with the increase of the number of executions. Such problems can only occur when the system load is high. Conditional races are usually time-sensitive, so they often disappear completely when programs run in debug mode because debug mode affects the program’s execution time (even if not much).

When you write multithreaded programs for a living, conditional competition is a nightmare. When we write software, we use a lot of complex operations to avoid vicious conditional competition.

2. Avoid vicious conditional competition

Here are a few ways to deal with vicious conditional contention, the simplest of which is to protect the data structure in such a way that only the thread making the modification can see the intermediate state when the invariant is corrupted. From the perspective of the other accessing threads, the modification is either complete or has not yet begun. The C++ standard library provides many similar mechanisms, which are described below.

Another option is to modify the design of data structures and invariants. The structure must be able to perform a series of indivisible changes, that is, to ensure that each invariant remains in a stable state. This is called lockless programming. However, it’s hard to get the right results this way. At this level, subtle differences in memory models and the ability of threads to access data can complicate the job.

Another way to handle condition contention is to use transactions to handle updates to data structures (” processing “here is like updating a database). Some of the required data and reads are stored in the transaction log, and the previous actions are combined into one step before committing. When the data structure has been modified by another thread, or the processing has been restarted, the commit cannot take place. This is called “software transaction memory.” In theoretical research, this is a very hot research area.

The most basic way to protect shared data structures is to use the mutex provided by the C++ standard library.

2.2 Using Mutex to Protect Shared Data

2.2.1 Using mutex

Protect lists with mutex

#include <list>
#include <mutex>
#include <algorithm>
std::list<int> some_list;    / / 1
std::mutex some_mutex;    / / 2
void add_to_list(int new_value)
{
  std::lock_guard<std::mutex> guard(some_mutex);    / / 3
  some_list.push_back(new_value);
}
bool list_contains(int value_to_find)
{
  std::lock_guard<std::mutex> guard(some_mutex);    / / 4
  return std::find(some_list.begin(),some_list.end(),value_to_find) ! = some_list.end(a); }Copy the code

2.2.2 Carefully organize code to protect shared data

Do not pass Pointers or references to protected data outside the mutex scope, either as a function return value, stored in external visible memory, or as a parameter to a user-supplied function.

Inadvertently passing a reference to protect data:

class some_data
{
  int a;
  std::string b;
public:
  void do_something(a);
};
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 Passes "protect" data to the user function}}; some_data* unprotected;void malicious_function(some_data& protected_data)
{
  unprotected=&protected_data;
}
data_wrapper x;
void foo(a)
{
  x.process_data(malicious_function);    // 2 Pass a malicious function
  unprotected->do_something(a);// 3 Access protected data without protection
}
Copy the code

The process_data example looks fine, STD ::lock_guard protects the data nicely, but calling the user-supplied function func① means foo can bypass the protection mechanism and pass malicious_function in, Call do_something() if the mutex is not locked.

The problem with this code is that it has no protection at all, just marks all accessible data structure code as mutually exclusive. Unprotected ->do_something() code in foo() is not marked as mutually exclusive. In this case, the C++ thread library does nothing to help, leaving it up to the programmer to protect the data with the proper mutex. On the bright side, there are ways to do this: Do not pass Pointers or references to protected data outside the mutex scope, either as a function return value, stored in external visible memory, or as a parameter to a user-supplied function.

2.2.3 Discovering condition Contention on an interface

Example: Building a stack similar to the STD ::stack structure (Listing 3.3) requires five operations on the STD ::stack, in addition to the constructor and swap() : Push () a new element onto the stack, pop() an element off the stack, top() looks at the top element, empty() determines whether the stack is empty, and size() knows how many elements there are in the stack. Even if you modify top() to return a copy rather than a reference (that is, following the guidelines of Section 3.2.2), the internal data is protected with a mutex, but this interface still has conditional contention. This problem does not only exist in interfaces based on mutex implementations, but in interfaces without locks, conditional contention can still occur. This is an interface problem, not an implementation problem.

template<typename T,typename Container=std::deque<T> >
class stack
{
public:
  explicit stack(const Container&);
  explicit stack(Container&& = Container());
  template <class Alloc> explicit stack(const Alloc&);
  template <class Alloc> stack(const Container&, const Alloc&);
  template <class Alloc> stack(Container&&, const Alloc&);
  template <class Alloc> stack(stack&&, const Alloc&);
  bool empty(a) const;
  size_t size(a) const;
  T& top(a);
  T const& top(a) const;
  void push(T const&);
  void push(T&&);
  void pop(a);
  void swap(stack&&);
};
Copy the code

Although empty() and size() may be correct when called and returned, their results are unreliable; When they return, other threads are free to access the stack, and may push() multiple new elements to the stack, or pop() some elements that are already on the stack. In this case, the previous results from empty() and size() are problematic.

Analyze what happens when conditional competition occurs:

(1) between calling empty() and calling top() (2) between calling top() and pop()

Let’s say there’s a stack

>. Vector is a dynamic container. When you copy a veTCor, the library allocates a lot of memory from the heap to make the copy. When the system is under heavy load or under severe resource constraints, this allocation will fail, so the vector copy constructor may throw a STD ::bad_alloc exception. This is more likely to happen when a vector contains a large number of elements. When the pop() function returns a “pop value” (that is, the value is removed from the stack), there is a potential problem: the value is returned to the calling function and the stack is changed; But what happens when a function is called to throw an exception while copying data? If that happens, the data to be ejected will be lost; It did move off the stack, but the copy failed! The designers of STD :: Stack split this operation into two parts: get the top element (top()), then remove it from the stack (pop()). In this way, the data in the stack remains intact, even if the element cannot be safely copied out. When the problem is insufficient heap space, the application may free up some memory and try again.

Solution:

The first option is to pass a reference to the variable as an argument into the pop() function to get the desired “pop value” :

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

Most of the time, this is fine, but there is a significant drawback: you need to construct an instance of the type on the stack to receive the target value. For some types, this is not practical because constructing an instance AD hoc is not cost-effective in terms of time and resources. This does not always work for other types, because the constructor requires parameters that are not necessarily available at this stage of the code. Finally, you need an assignable storage type, which is a major limitation: even if move constructs are supported, or even copy constructs (thus allowing the return of a value), many user-defined types may not support assignment operations.

Option 2: Copy constructor or move constructor without exception thrown

For pop() functions that return values, there are only “exception safety” concerns (an exception can be thrown when a value is returned). Many types have copy constructors that do not throw exceptions, and with the new standard’s support for “rvalue references” (see Appendix A, Section A.1), many types will have A move constructor that does not throw an exception even if they do the same thing as the copy constructor. A useful option is to limit the use of thread-safe stacks and allow the stack to safely return the desired value without throwing an exception.

It’s safe, but not reliable. Although it is possible to use the STD :: IS_NO_throw_copy_CONSTRUCtible and STD :: IS_NOthrow_move_constructible type features at compile time so that copy or move constructors do not throw exceptions, this approach is too limited. Among user-defined types, there are copy constructors or move constructors that do not throw exceptions, and there are often more copy constructors that do throw exceptions but do not move constructors (this may change as people get used to rvalue references in C++11). It would be unfortunate if these types could not be stored on a thread-safe stack.

Option 3: Return a pointer to the pop-up value

The third option is to return a pointer to the pop-up element rather than returning the value directly. Pointers have the advantage of being free to copy and not generating exceptions, so you can avoid the exception problem that Cargill mentioned. The downside is that returning a pointer requires management of the object’s memory allocation, which is much more expensive for simple data types (e.g., int) than returning a value directly. For interfaces that choose this scenario, using STD ::shared_ptr is a good choice; Not only are memory leaks avoided (because objects are destroyed when Pointers are destroyed in them), but the library has complete control over the allocation scheme, eliminating the need for new and DELETE operations. This optimization is important: because each object in the stack requires an independent memory allocation using New, this approach is quite expensive compared to the non-thread-safe version.

Option 4: “Option 1 + Option 2” or “Option 1 + Option 3”

For common code, flexibility should not be overlooked. It’s easy to go to option 1 when you’ve already chosen option 2 or 3. These options are presented to the user, allowing the user to choose the most appropriate and economical solution for them.

Define thread-safe stack:

#include <exception>
#include <memory>  // For std::shared_ptr<>
struct empty_stack: std::exception
{
  const char* what(a) const throw(a);
};
template<typename T>
class threadsafe_stack
{
public:
  threadsafe_stack(a);threadsafe_stack(const threadsafe_stack&);
  threadsafe_stack& operator= (const threadsafe_stack&) = delete; // The 1 assignment was removed
  void push(T new_value);
  std::shared_ptr<T> pop(a);
  void pop(T& value);
  bool empty(a) const;
};
Copy the code

#include <exception>
#include <memory>
#include <mutex>
#include <stack>
struct empty_stack: std::exception
{
  const char* what(a) const throw(a) {
    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& other)
  {
    std::lock_guard<std::mutex> lock(other.m);
    data = other.data; // 1 performs a copy in the constructor body
  }
  threadsafe_stack& operator= (const threadsafe_stack&) = delete;
  void push(T new_value)
  {
    std::lock_guard<std::mutex> lock(m);
    data.push(new_value);
  }
  std::shared_ptr<T> pop(a)
  {
    std::lock_guard<std::mutex> lock(m);
    if(data.empty()) throw empty_stack(a);// Check if the stack is empty before calling pop
    std::shared_ptr<T> const res(std::make_shared<T>(data.top())); // Allocate the return value before modifying the stack
    data.pop(a);return res;
  }
  void pop(T& value)
  {
    std::lock_guard<std::mutex> lock(m);
    if(data.empty()) throw empty_stack(a); value=data.top(a); data.pop(a); }bool empty(a) const
  {
    std::lock_guard<std::mutex> lock(m);
    return data.empty();
  }
};
Copy the code

2.2.4 Deadlock: Problem description and solution

The biggest problem with thread deadlocks: locking an operation with two or more mutex.

General advice: Keep two mutex locks in the same order: always lock mutex A before mutex B, and it never deadlocks. In some cases this is possible because different mutex is used in different places.

Special situations: when there are multiple mutex protect the same independent instance of a class, an operation on two different instances of the same class for the exchange of data operation, in order to guarantee the correctness of the data exchange operation, to avoid data is concurrent modification, and to ensure that every instance of the mutex locking themselves to protect the area. However, choosing a fixed order (for example, the first mutex provided by the instance as the first argument, and the second mutex provided as the second argument) can backfire: after the argument exchange, the program deadlocks again when two threads try to exchange data between the same two instances!

Lock multiple mutex at once with STD ::lock

// STD ::lock() needs to include the 
      
        header
      
class some_big_object;
void swap(some_big_object& lhs,some_big_object& rhs);
class X
{
private:
  some_big_object some_detail;
  std::mutex m;
public:
  X(some_big_object const& sd):some_detail(sd){}
  friend void swap(X& lhs, X& rhs)
  {
    if(&lhs==&rhs)
      return;
    std::lock(lhs.m,rhs.m); / / 1
    std::lock_guard<std::mutex> lock_a(lhs.m,std::adopt_lock); / / 2
    std::lock_guard<std::mutex> lock_b(rhs.m,std::adopt_lock); / / 3
    swap(lhs.some_detail,rhs.some_detail); }};Copy the code

First, check if the parameters are different instances, because the operation is trying to acquire a lock on a STD ::mutex object, so the result is unpredictable when it is acquired. STD ::lock() is then called to lock both mutex, and both STD :lock_guard instances have been created ②③. Providing the STD ::adopt_lock parameter, in addition to indicating that the STD :: LOCK_guard object can acquire the lock, also gives the lock to the STD ::lock_guard object to manage, without requiring the STD :: LOCK_guard object to build a new lock.

This ensures that, in most cases, the mutex is unlocked correctly when the function exits (the protection operation may throw an exception) and allows a simple “return” as a return. Also, be aware that an exception may be thrown when using STD ::lock to unlock lhs.m or rhS. m; In this case, exceptions propagate outside of STD :: Lock. When STD ::lock successfully acquires a lock on a mutex and tries to acquire another lock on another mutex, an exception is thrown and the first lock is automatically released with the exception, so STD ::lock either holds both locks or none.

2.2.5 Avoiding deadlocks

1. Avoid nested locks: a thread holds only one lock. If you need to acquire multiple locks, use STD ::lock.

2. Avoid calling user-provided code when holding a lock: You call user-provided code when holding a lock; If user code were to acquire a lock, it would violate the first guideline and cause a deadlock.

3. Obtain locks in a fixed order (optional)

2.2.6 STD ::unique_lock Flexible lock

Advantage:

1. Ownership of removable mutex
2. You can take ownership of the mutex, but not lock it
3. Lock any number of times to unlock

class some_big_object;
void swap(some_big_object& lhs,some_big_object& rhs);
class X
{
private:
  some_big_object some_detail;
  std::mutex m;
public:
  X(some_big_object const& sd):some_detail(sd){}
  friend void swap(X& lhs, X& rhs)
  {
    if(&lhs==&rhs)
      return;
    std::unique_lock<std::mutex> lock_a(lhs.m,std::defer_lock); / / 1
    std::unique_lock<std::mutex> lock_b(rhs.m,std::defer_lock); // 1 STD ::def_lock Leaves unlocked mutex
    std::lock(lock_a,lock_b); // mutex 2 is locked here
    swap(lhs.some_detail,rhs.some_detail); }};Copy the code

2.2.7 Transfer of mutex ownership in different domains

std::unique_lock<std::mutex> get_lock(a)
{
  extern std::mutex some_mutex;
  std::unique_lock<std::mutex> lk(some_mutex);
  prepare_data(a);return lk;  / / 1
}
void process_data(a)
{
  std::unique_lock<std::mutex> lk(get_lock());  / / 2
  do_something(a); }Copy the code

2.2.8 Lock Granularity

The granularity of the lock corresponds to the amount of data protected and the corresponding performance loss. (Use fine-grained locks whenever possible.)

The comparison operator locks one mutex at a time

class Y
{
private:
  int some_detail;
  mutable std::mutex m;
  int get_detail(a) const
  {
    std::lock_guard<std::mutex> lock_a(m);  / / 1
    return some_detail;
  }
public:
  Y(int sd):some_detail(sd){}
  friend bool operator==(Y const& lhs, Y const& rhs)
  {
    if(&lhs==&rhs)
      return true;
    int const lhs_value=lhs.get_detail(a);/ / 2
    int const rhs_value=rhs.get_detail(a);/ / 3
    return lhs_value==rhs_value;  / / 4}};Copy the code

2.3 Alternatives for protecting shared Data

2.3.1 Initialization process of Protecting Shared Data

Old: Double check lock

void undefined_behaviour_with_double_checked_locking(a)
{
  if(! resource_ptr)/ / 1
  {
    std::lock_guard<std::mutex> lk(resource_mutex);
    if(! resource_ptr)/ / 2
    {
      resource_ptr.reset(new some_resource);  / / 3
    }
  }
  resource_ptr->do_something(a);/ / 4
}
Copy the code

A new method:

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

class X
{
private:
  connection_info connection_details;
  connection_handle connection;
  std::once_flag connection_init_flag;
  void open_connection(a)
  {
    connection=connection_manager.open(connection_details);
  }
public:
  X(connection_info const& connection_details_):
      connection_details(connection_details_)
  {}
  void send_data(data_packet const& data)  / / 1
  {
    std::call_once(connection_init_flag,&X::open_connection,this);  / / 2
    connection.send_data(data);
  }
  data_packet receive_data(a)  / / 3
  {
    std::call_once(connection_init_flag,&X::open_connection,this);  / / 2
    return connection.receive_data();
  }
};

Copy the code

Alternatives to singletons:

class my_class;
my_class& get_my_class_instance(a)
{
  static my_class instance;  // Thread-safe initialization
  return instance;
}
Copy the code

2.3.2 Protect data structures that are rarely updated

#include <map>
#include <string>
#include <mutex>
#include <boost/thread/shared_mutex.hpp>
class dns_entry;
class dns_cache
{
  std::map<std::string,dns_entry> entries;
  mutable boost::shared_mutex entry_mutex;
public:
  dns_entry find_entry(std::string const& domain) const
  {
    boost::shared_lock<boost::shared_mutex> lk(entry_mutex);  / / 1
    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& domain,
                           dns_entry const& dns_details)
  {
    std::lock_guard<boost::shared_mutex> lk(entry_mutex);  / / 2entries[domain]=dns_details; }};Copy the code

Note: shared_mutex has been added to the standard library since c++14.

2.3.3 nested locks

When a thread has already acquired a STD ::mutex (already locked) and locks it again, the operation is an error, and continuing to attempt to do so results in undefined behavior. However, in some cases, it is possible for a thread to attempt to acquire the same mutex multiple times without releasing it once. This is possible because the C++ standard library provides the STD ::recursive_mutex class. The function is similar to STD :: Mutex, except that you can acquire multiple locks from a single instance of the same thread. Before a mutex can lock another thread, you must release all locks you have, so when you call lock() three times, you must also call unlock() three times. The correct use of STD ::lock_guard< STD ::recursive_mutex> and STD ::unique_lock< STD ::recursice_mutex> can help you handle these problems.

In most cases, when you need nested locks, you need to make changes to your design. Nested locks are typically used on classes that can be accessed concurrently, so their holding mutex protects their member data. Each public member function locks the mutex, completes its function, and then unlocks the mutex. However, sometimes a member function will call another member function, in which case the second member function will also attempt to lock the mutex, resulting in undefined behavior. The “workaround” solution would turn the mutex into a nested lock, the second member function would be successfully locked, and the function would continue to execute.

However, such use is not recommended because it is hasty and unreasonable. In particular, invariants of the corresponding class are usually being modified while the lock is being held. This means that the second member function needs to continue executing while the invariant is changing. A better way to do this is to extract a function as a private member of the class and have it called by all other member functions. This private member function does not lock the mutex (the lock must be acquired before calling it). Then you think carefully about the state of the data when you call the new function in this case.