C++ Concurrency in Action (3) - Sharing data between threads

C++ Concurrency in Action 3

Problems with sharing data between threads

在同一进程中,线程间的数据共享,不仅仅是便捷,还可能造成问题。

线程间共享数据的问题,全都可以归结到修改数据的顺序。

  • 如果所有数据都是只读的,那么不会有任何问题。
  • 如果一个或多个线程修改它们之间共享的数据,现在的问题可能就会出现。

Invariant(不变条件):关于某个特定的数据结构,始终为真的与君。

但是在多个线程修改共享数据时,invariant会被broken。

Race conditions

并发中最常见的导致问题的原因。出现在两个或多个线程的执行结果依赖于相对的执行顺序。在某些情况下,race condition是无害的,但是如果race condition使得broken invariant,这将会导致问题。C++标准定义了一种特别的race condition - data race(由于并发的修改同一个对象),data race将会导致undefined behavior。

problematic race condition常常出现在完成一个操作需要修改两处或多处不同的数据。在一个线程正在修改数据,另一个可能在未修改完的时候就访问数据。

由于race condition是timing sensitive的,因此在debug的时候,debugger会影响程序的timing,问题就不会再现。

Avoiding problematic race conditions

  • 用某种保护机制来包装数据结构。

只有实际进行修改的线程才能看到invariants are broken的中间状态。

  • 修改数据结构和invariants的设计,使得修改在一系列隐形的changes下完成,每个change可以保证invariants。

这一般指的就是lock-free。

  • 将对数据结构的update作为transaction。

这就是software transactional memory(STM)。

Protecting shared data with mutexes

mutex(mutual exclusion):synchronization primitive。线程库保证一旦某个线程已经lock了某个mutex,其他所有尝试lock同一个mutex的线程,都必须等到那个成功lock这个mutex的线程unlock它。

这可以保证每个线程看到的都是self-consistent view的共享数据,避免broken invariant。

但mutex不是silver bullet!

Using mutexes in C++

通过构造std::mutex的实例来创建一个mutex。

不推荐直接调用std::mutex的成员函数,尤其是unlock()。因为你必须在每段代码执行的尾部,包括异常中,都要记得unlock。std::lock_guardRAII的方式来对mutex提供支持,在构造的时候lock,析构的时候unlock。

用类来封装。

Structuring code for protecting shared data

如果类的成员函数返回了指向受保护数据的指针或引用,那岂不就是开了后门?

那么是不是禁止返回指向受保护数据的指针或引用就ok了?

还有一个没有考虑到的就是,不要向那些不在你控制下的被调用函数,传入指向受保护数据的指针或引用。

Don't pass pointers and references to protected data outside the scope of the lock, whether by returning them from a function, storing them in externally visible memory, or passing them as arguments to user-supplied functions.

Spotting race conditions inherent in interfaces

考虑一个双向链表,如果要使得一个删除操作是线程安全的,那么要必须保证避免并发的访问三个结点(要删除的和两边的)。但这并不足以避免race condition,到目前为止,只能采用避免并发的访问整个list。

看下面的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
template<typename T,typename Container=std::deque<T> >
class stack {
public:
...
bool empty() const;
size_t size() const;
T& top();
T const& top() const;
void push(T const&);
void push(T&&);
void pop();
void swap(stack&&);
};

就算让top()返回copy,而不是reference,这个接口还是有race conditions。这并不是基于mutex的实现独有的问题,基于lock-free的实现也会有,这是接口设计的问题。

上例中,empty()top()是不可靠的,因为在调用empty()size()的线程使用它们返回的值之前,stack可能已经被其他线程改变了(可能已经empty),这时再去top(),stack已经不是调用empty()size()时候的stack了。而在stack内使用mutex仅仅只能保证同一时刻,只有一个线程运行stack的成员函数,而这并不能解决这样的问题。

还有一个类似的问题是,top()pop()之间,stack也有可能被修改。

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

或许你觉得可以合并top()pop(),但是std::stack这样分开设计不是没有理由的,简单来说,如果分开了,在return的时候,系统资源不足,copy构造函数失败,造成已经pop了,但是元素丢失(因为没有return成功)。

但是,比较头疼的是,要消除race condition就是要避免这样的分开设计(lock的粒度太小,mutex不能保护整个操作),进而避免上例中,不同线程的interleave。

解法1:PASS IN A REFERENCE

缺陷:

  • 不实用,构造一个实例需要额外的时间或资源。
  • 不总是可用,构造函数所需要的参数不是时时可以获得的。
  • 需要类型可赋值,但是赋值不总是可用的,尤其是自定义的类型。

解法2:REQUIRE A NO-THROW COPY CONSTRUCTOR OR MOVE CONSTRUCTOR

There's only an exception safety problem with a value-returning pop() if the return by value can throw an exception.

缺陷:

  • 限制只让那些有不抛出异常的构造函数或move构造函数的的类型使用stack,虽然可行,但是不通用。

解法3:RETURN A POINTER TO THE POPPED ITEM

优势:

  • pointer可以被自由的copy,而不抛出异常。

缺陷:

  • 普通的方式需要管理分配给对象的内存,内存管理的开销可能还大于return by value。

如果要使用,std::shared_ptr值得考虑,可以避免很多newdelete

解法 4:PROVIDE BOTH OPTION 1 AND EITHER OPTION 2 OR 3

万金油,糅合1,2或1,3,要用什么,给用户自己选择。

EXAMPLE DEFINITION OF A THREAD-SAFE STACK

  • 在接口中没有race condition,并糅合了1、3;
  • 不可赋值,可copy(假设元素可copy);
  • stack为空时,pop()抛出异常,但是stack仍然可以工作;
  • 简化的操作,使得数据得到了更好的控制,可以保证在每个操作中,mutex都是locked;
  • std::stack进行了包装;
  • 可以加入copy的支持,只要copy的时候lock mutex即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <exception>
#include <memory>
#include <mutex>
#include <stack>
struct empty_stack: std::exception {
const char* what() const throw();
};
template<typename T>
class threadsafe_stack {
private:
std::stack<T> data;
mutable std::mutex m;
public:
threadsafe_stack(){}
threadsafe_stack(const threadsafe_stack& other) {
std::lock_guard<std::mutex> lock(other.m);
data=other.data;
}
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() {
std::lock_guard<std::mutex> lock(m);
if(data.empty()) throw empty_stack();
std::shared_ptr<T> const res(std::make_shared<T>(data.top()));
data.pop();
return res;
}
void pop(T& 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();
}
};

为什么m是mutable?

empty()后跟const,说明empty()不能修改类的成员,除非成员被设置为mutable。

Granularity

细粒度(fine-grained)锁会导致保护不完全,锁的粒度太大会导致并发失去意义。

有时细粒度锁意味着需要多个mutex,而这可能会导致deadlock。

Deadlock:the problem and a solution

如果有两个mutex,那么总是以同样的顺序lock mutex就不会死锁 了。但是有时以同样的顺序lock mutex并不能满足需求。

std::lock:可以一次性锁住两个或多个mutex,而不会deadlock。但是如果分别获得lock,它并不能保证不死锁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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);
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);
}
};

上例中有这么几个要注意的地方:

为什么要检查是否是不同的实例?

std::lock做了这么一个事情:

Locks the given Lockable objects lock1, lock2, ..., lockn using a deadlock avoidance algorithm to avoid deadlock. The objects are locked by an unspecified series of calls to lock, try_lock, unlock. If a call to lock or unlock results in an exception, unlock is called for any locked objects before rethrowing.

换句话说,作为参数的几个mutex都会被an unspecified series of calls to lock, try_lock, unlock一遍。

要注意的是,必须是Lockable objects

对于已经在外部lock的lockables,deadlock是无法保证不发生的。

如果某个mutex是locked,deadlock是不能够保证会避免的。

std::adopt_lock是什么鬼?

constexpr(常量表达式),tag type used to specify locking strategy 。其中std::adopt_lock:assume the calling thread already has ownership of the mutex。也就是说告诉std::lock_guard,给你的mutex已经锁上了,你就不要再lock一次了。

下面是std::lock_guard的构造函数的定义:

1
2
3
4
5
explicit lock_guard(mutex_type& __m) : _M_device(__m)
{ _M_device.lock(); }

lock_guard(mutex_type& __m, adopt_lock_t) : _M_device(__m)
{ } // calling thread owns mutex

可以很明确的看出使用了adopt_lock_t后,std::lock_guard并没有去lock。

会不会抛出异常?什么地方会?抛出会怎样?

比较可能会,如果抛出,函数就退出了,不会进行swap; std::lock可能会(确切的说是,std::lock内部lock lhs.mrhs.m的时候可能会,接着异常会传出std::lock),如果抛出,函数就退出了,不会进行swap; 构造lock_guard不会,标准规定的。

std::lock不万能,如果分别获得lock,它并不能保证不deadlock。

Further guidelines for avoiding deadlock

deadlock不仅仅出现在有lock的时候,也不局限于两个线程。

避免deadlock的方法可以归结为:不要等待一个可能等待你的线程。

下面的准则能检查并消除,有其他线程等待你的可能性。

AVOID NESTED LOCKS

如果需要多个lock,用std::lock

AVOID CALLING USER-SUPPLIED CODE WHILE HOLDING A LOCK

用户提供的代码可能会请求另一个lock,进而违反上一个准则。

ACQUIRE LOCKS IN A FIXED ORDER

如果要获取两个或更多的lock,并且不能使用std::lock一次性获取,次优的方案是在每个线程中以同样的顺序获取。the key is to define the order in a way that's consistent between threads.

USE A LOCK HIERARCHY

lock hierarchy提供了一种方法,可以在运行时检查是否遵循lock oerding。如果一段代码已经获得了低层的lock,那么它不允许获得高层的lock。本质上就是为了保证获取lock的顺序。但是这种lock的机制,要求chain中每个mutex的hierarchy value都比前一个低,可能在某些情况下并不实用。

下面是一个hierarchical mutex的例子,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class hierarchical_mutex {
std::mutex internal_mutex;
unsigned long const hierarchy_value;
unsigned long previous_hierarchy_value;
static thread_local unsigned long this_thread_hierarchy_value;

void check_for_hierarchy_violation() {
if (this_thread_hierarchy_value <= hierarchy_value) {
throw std::logic_error("mutex hierarchy violated");
}
}

void update_hierarchy_value() {
previous_hierarchy_value = this_thread_hierarchy_value;
this_thread_hierarchy_value = hierarchy_value;
}

public:
explicit hierarchical_mutex(unsigned long value) :
hierarchy_value(value),
previous_hierarchy_value(0) {}

void lock() {
check_for_hierarchy_violation();
internal_mutex.lock();
update_hierarchy_value();
}

void unlock() {
this_thread_hierarchy_value = previous_hierarchy_value;
internal_mutex.unlock();
}

bool try_lock() {
check_for_hierarchy_violation();
if (!internal_mutex.try_lock())
return false;
update_hierarchy_value();
return true;
}
};

thread_local unsigned long hierarchical_mutex::this_thread_hierarchy_value(ULONG_MAX);

有这么几个要注意的地方:

thread_local

这个是这段代码的关键。thread_local变量允许你在每个线程中都有一个独立的实例。在namespace的变量、类的static data member和局部变量都可以被声明为thread_local,并且拥有thread storage duration。

{ %blockquote% } When thread_local is applied to a variable of block scope, the storage-class-specifier static is implied if it does not appear explicitly. { %endblockquote% }

因此上例中,

1
static thread_local unsigned long this_thread_hierarchy_value;

等价于

1
thread_local unsigned long this_thread_hierarchy_value;

又因为,C++规定const静态类成员可以直接初始化,其他非const的静态类成员需要在类声明以外初始化,所以有最后的初始化。

一个线程有多个mutex的情况下,thread_local变量是共享的?

是的,因为它属于类,而不是某个对象。

三个value会不会在多个线程并发时,出现interleaving修改?

不会,修改是在internal mutex的lock和unlock之间。

hierarchy mutex本质上说的还是lock的order,其目的就是为了避免多个线程中出现wait cycle,hierarchy mutex是把这种order强制化了。

Flexible locking with std::unique_lock

std::unique_lock提供了比std::lock_guard更多的灵活度(构造函数的可传入:std::defer_lockstd::try_to_lockstd::adopt_lock),并且不总是拥有mutex的ownership(locked)。但这两者是有代价的,std::unique_lock要占用更多的空间,并且稍微慢一点点,这个可以用源码看出来:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    ...
unique_lock(mutex_type& __m, defer_lock_t) noexcept
: _M_device(&__m), _M_owns(false)
{ }
unique_lock(mutex_type& __m, try_to_lock_t)
: _M_device(&__m), _M_owns(_M_device->try_lock())
{ }
unique_lock(mutex_type& __m, adopt_lock_t)
: _M_device(&__m), _M_owns(true)
{
// XXX calling thread owns mutex
}
...
private:
mutex_type* _M_device;
bool _M_owns; // XXX use atomic_bool
};

std::unique_lock需要flag,_M_owns来存储mutex的ownership,在unlock、析构等时候,需要根据flag来判断是否要forward to_M_device的成员函数来做实际的工作。flag可以通过std::unique_lockowns_lock()来获得。

std::unique_lock还允许在实例销毁前释放lock,这样就可以在明确知道不再需要lock的时候,进行release,而不必等到销毁时,避免了其他线程额外的等待。

一般来说推荐使用std::lock_gurad,但是如果需要额外的灵活度,那就用std::unique_lock,例如:

  • 延迟锁
  • Transfer ownership of lock

Transferring mutex ownership between scopes

Because std::unique_lock instances don't have to own their associated mutexes, the ownership of a mutex can be transferred between instances by moving the instances around.

std::unique_lock是movable,但不是copyable的。

其中一个应用是返回一个lock,来transfer ownership给调用函数。

1
2
3
4
5
6
7
8
9
10
std::unique_lock<std::mutex> get_lock() {
extern std::mutex some_mutex;
std::unique_lock<std::mutex> lk(some_mutex);
prepare_data();
return lk;
}
void process_data() {
std::unique_lock<std::mutex> lk(get_lock());
do_something();
}

Locking at an appropriate granularity

lock的粒度是用来描述被一个锁保护的数据的数量。

如果可能,只有在真正访问共享数据的时候才lock a mutex。

一般来说,不要在拥有锁的时候做耗时的工作,尤其是等待其他的lock(就算知道不会deadlock),或者文件I/O(除非真的是需要保护文件的访问)。

std::unique_lock很适合用于这样的情况,因为你可以在不需要访问共享数据的时候unlock(),需要的时候再lcok()

关于lock的粒度和拥有锁的时长

  1. 如果只有一个mutex来保护整个数据结构,那么不仅仅很可能会出现更多的竞争,而且减少了lock被held的时间。
  2. 对于同一个mutex,如果获得lock以后进行的操作越多,那么lock就会被held越长。

找到一个合适的粒度,不仅仅要看锁住的数据的数量,还要看lock被获得的时长和获得lock的时候做了什么操作。In general, a lock should be held for only the minimum possible time needed to perform the required operations.

还有一个问题就是,由于改变了lock的方式,可能会导致代码语义上的改变,有时这样的改变会导致错误。

Alternative facilities for protecting shared data

在特殊情况下,有一些比mutex更合适的方式来保护共享数据。

Protecting shared data during initialization

有时候可能共享数据在创建以后就是只读的,因此只需要在创建的时候进行保护。但是如果使用mutex,仅仅在初始化的时候保护,这是不必要的,并且还会带来不必要的性能损失。

Double-Checked Locking

最早接触DCL是在设计模式里,单例模式提到过。这个看似高效的方法之所以被骂,就是因为CPU乱序执行可能会导致线程访问没有初始化的对象。

在这里也是类似的,也会带来问题。

1
2
3
4
5
6
7
8
9
void undefined_behaviour_with_double_checked_locking() {
if(!resource_ptr) {
std::lock_guard<std::mutex> lk(resource_mutex);
if(!resource_ptr) {
resource_ptr.reset(new some_resource);
}
}
resource_ptr->do_something();
}

这种类型的race condition叫做data race,是undefined behavior。

lazy initialization with std::once_flagstd::call_once

std::call_once通常比显式使用mutex会有更低的开销,尤其是当初始化已经完成的时候。

1
2
3
4
5
6
7
8
9
std::shared_ptr<some_resource> resource_ptr;
std::once_flag resource_flag;
void init_resource() {
resource_ptr.reset(new some_resource);
}
void foo() {
std::call_once(resource_flag,init_resource);
resource_ptr->do_something();
}

当初始化函数是带有函数调用操作符的类的实例的时候,std::call_once也支持像std::threadstd::bind()的用法。

要注意的是,如果类的成员含有不能copy或move的,那么要为它们定义特殊成员函数。

static

C++11中,规范了在多线程的情况下初始化static变量。初始化被定义为只发生在一个线程上,直到初始化完成其他线程才能继续。

这可以作为std::call_once的替代。

Protecting rarely updated data structures

用mutex来保护较少更新的数据结构不合适,当没有进行更新的时候,它消除了并发读的可能。

reader-writer mutex

允许:

  1. 互斥的写或共享;
  2. 并发的的读。

C++标准库没有提供这种锁,这里使用的是boost库。这种锁不是万能的,它的性能依赖于处理器的数量和读写线程相对的工作负载。

boot::shared_mutex

由boost提供。

Recursive locking

可以在同一个线程中从同一个std::recursive_lock的实例获得多次lock。在其他线程获得lock前,当前线程lock()了多少次,就必须unlock()多少次。

但是并不建议使用std::recursive_lock,当持有lock的时候,invariant很可能是broke的。继续lock,意味着要在invariant broken的情况下做操作。

Reference

  1. Is this an exception safe implementation of swap(multithread)?
  2. Are C++11 thread_local variables automatically static?
  3. C++ concepts: Lockable
  4. 双重检查锁定与延迟初始化
  5. C++ Concurrency in Action