explorer

万丈高楼平地起,勿在浮沙筑高台

0%

[What]Common Concurrency Problems

整理在并发编程时,经常会遇到的一些问题。

非死锁 BUG

违反原子性 BUG

所谓的违反原子性 BUG,其实就是没有对临界区进行互斥处理。

1
2
3
4
5
6
7
Thread 1::
if (thd->proc_info) {
fputs(thd->proc_info, ...);
}

Thread 2::
thd->proc_info = NULL;

如上面这段代码,假设线程 2 在线程 1 进入 if 判断后但在执行 fputs 之前执行,就会 出现 fputs 操作空指针的问题。

解决办法就是将这段临界区进行加锁:

1
2
3
4
5
6
7
8
9
10
11
12
13
pthread_mutex_t proc_info_lock = PTHREAD_MUTEX_INITIALIZER;

Thread 1::
pthread_mutex_lock(&proc_info_lock);
if (thd->proc_info) {
fputs(thd->proc_info, ...);
}
pthread_mutex_unlock(&proc_info_lock);

Thread 2::
pthread_mutex_lock(&proc_info_lock);
thd->proc_info = NULL;
pthread_mutex_unlock(&proc_info_lock);

违反顺序 BUG

1
2
3
4
5
6
7
8
9
Thread 1::
void init() {
mThread = PR_CreateThread(mMain, ...);
}

Thread 2::
void mMain(...) {
mState = mThread->State;
}

如上面这段代码,线程 2 必须要等待线程 1 为 mThread 赋值后,才能正常使用。

为了完成这种顺序同步,需要使用条件变量或信号量:

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
pthread_mutex_t mtLock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t mtCond = PTHREAD_COND_INITIALIZER;
int mtInit = 0;

Thread 1::
void init() {
...
mThread = PR_CreateThread(mMain, ...);

// signal that the thread has been created...
pthread_mutex_lock(&mtLock);
mtInit = 1;
pthread_cond_signal(&mtCond);
pthread_mutex_unlock(&mtLock);
...
}

Thread 2::
void mMain(...) {
...
// wait for the thread to be initialized...
pthread_mutex_lock(&mtLock);
while (mtInit == 0)
pthread_cond_wait(&mtCond, &mtLock);
pthread_mutex_unlock(&mtLock);

mState = mThread->State;
...
}

死锁 BUG

死锁发生的原因

死锁的发生,需要同时具备以下 4 个条件:

  1. 互斥:多个线程会访问一个或多个共有资源,同一时刻只能其中一个访问
  2. 保持锁和等待锁:当一个线程获取到一个资源锁的同时,又在等待另外一个资源的锁
  3. 不可抢占:锁不能从持有它的线程强制释放
  4. 环形等待:一个线程获得的锁被另一个线程所需要,但另一个线程需要的锁也被当前线 程直接或间接的需要

以上 4 个条件,只要其中一个不满足,便不会形成死锁。

避免死锁

环形等待

避免环形等待的本质在于是要规定好锁的获取顺序。

简单的情况,比如当代码中只有两个锁时,那么可以规定无论哪个线程获取锁时,都是统一 的先后顺序。

复杂的情况,比如像哲学家就餐问题,如果使用统一的顺序就会造成死锁,这种情况下就要 规定锁的获取顺序。甚至需要规定好几个不同的顺序。

保持锁和等待锁

当一个线程需要先后获取多个锁时,可以再用一个锁包裹,以让获取锁的操作原子性:

1
2
3
4
5
pthread_mutex_lock(prevention); // begin acquisition
pthread_mutex_lock(L1);
pthread_mutex_lock(L2);
...
pthread_mutex_unlock(prevention); // end

不过这种方式有以下缺陷:

  1. 很多时候代码都是层层封装,上层应用并不能使用一个锁来很好的包裹
  2. 假设获取多个锁之间有很多其他操作,如果最外层再用一个锁包裹,则会降低进行的并 发度

不可抢占

不可抢占指的是一个线程已经获取了一个锁,但在获取另一个锁的时候由于无法获取到而睡 眠了,那么它已经获取的那个锁便无法释放。

那么,一个简单的解决办法是使用 trylock 获取另一个锁,无法获取便退出:

1
2
3
4
5
6
top:
pthread_mutex_lock(L1);
if (pthread_mutex_trylock(L2) != 0) {
pthread_mutex_unlock(L1);
goto top;
}

而另一个线程则使用相反的顺序:

  • 如果使用相同的顺序,则可能造成另一个线程睡眠等待 L1,但这似乎也没什么不对?
1
2
3
4
5
6
top:
pthread_mutex_lock(L2);
if (pthread_mutex_trylock(L1) != 0) {
pthread_mutex_unlock(L2);
goto top;
}

这种方式也会有一些缺陷:

  1. 假设两个线程正好同步了,都在同时获取各自的锁然后又释放,那么它们就会陷入 livelock,无限循环。
    • 解决办法是在中间插入随机的延迟,而打破这种同步
  2. 实际的应用场景会比较复杂,在 goto 时还需要释放一些资源以避免重复申请

互斥

避免互斥是个令人头痛的问题,如果能够尽量减少锁的使用量,便能大大降低死锁的概率。

假设硬件可以原子的完成以下操作:

1
2
3
4
5
6
7
int CompareAndSwap(int *address, int expected, int new) {
if (*address == expected) {
*address = new;
return 1; // success
}
return 0; // failure
}

那么假设我们要增加一个变量的值,就可以使用下面这种方式来完成,而无需使用锁:

1
2
3
4
5
6
void AtomicIncrement(int *value, int amount) {
do {
int old = *value;
//当 value 的值没有被改变(没有其他线程在操作),那么就改变该变量
} while (CompareAndSwap(value, old, old + amount) == 0);
}

假设一个更为复杂的场景:在链表的头部插入一个节点

1
2
3
4
5
6
7
void insert(int value) {
node_t *n = malloc(sizeof(node_t));
assert(n != NULL);
n->value = value;
n->next = head;
head = n;
}

按照加锁的方式来完成:

1
2
3
4
5
6
7
8
9
void insert(int value) {
node_t *n = malloc(sizeof(node_t));
assert(n != NULL);
n->value = value;
pthread_mutex_lock(listlock);
n->next = head;
head = n;
pthread_mutex_unlock(listlock);
}

使用不加锁的方式:

1
2
3
4
5
6
7
8
void insert(int value) {
node_t *n = malloc(sizeof(node_t));
assert(n != NULL);
n->value = value;
do {
n->next = head;
//确保 head 当前没有被改变的时候再继续下一步
} while (CompareAndSwap(&head, n->next, n) == 0);

基于调度的方式避免死锁

假设有 4 个线程,它们是否获取锁 1 和 锁 2 的方式如下:

  线程 1 线程 2 线程3 线程 4
锁1 获取 获取 不获取 不获取
锁2 获取 获取 获取 不获取

可以看到:只有线程 1 和线程 2 会同时获取两个锁,那么只要不让它们有机会同时运行, 那就可以避免死锁。

比如将线程 1 和线程 2 绑定在同一个逻辑 CPU 上,并且它们具有相同的优先级。

Last Updated 2020-08-20 四 17:38.
Render by hexo-renderer-org with Emacs 26.3 (Org mode 9.3.7)