OSTEP [并发] Chapt. 32 - 并发bugs

分类:Operating System, 发布于:2019-04-15 20:49:29, 更新于:2019-04-19 00:09:40。 评论

违反原子性导致的bug (Atomicity-Violation Bugs)

在MySQL中的一个简单的bug实例:

// Thread 1
if (thd->proc_info) {
  // ...
  fputs(thd->proc_info, ...);
  // ...
}

// Thread 2
thd->proc_info = NULL;

当线程1的if判断通过后,线程2横空出世,打断了1的执行并且把proc_info设置为NULL。线程1恢复执行后对NULL解引用,产生访问违例。

更加正式的违反原子性操作的定义是:

"The desired serializability among multiple memory accesses is violated (i.e. a code region is intended to be atomic, but the atomicity is not enforced during execution)."

原本期望多个相关的内存访问是串联的(all or none),但却没有满足。

解决此类bug的方法简单暴力:上锁。

违反执行顺序导致的bug (Order-Violation Bugs)

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

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

运行期望:线程2成功读取当前线程信息。

实际情况:线程2抢断了线程1先执行,导致线程1的赋值没有完成,此时线程2读取了错误的值(或者对NULL解引用然后boom)。

更加正式的顺序违反的定义是:

"The desired order between two (groups of) memory accesses is flipped (i.e., A should always be executed before B, but the order is not enforced during execution)."

两个(或多个)内存访问之间期望的关系被反转了。

解决bug的方法依然简单粗暴:使用条件变量强制线程进行同步。

研究事实:以上两种bug占据了非死锁bug的97%。但还有更多的bug需要深入理解程序的行为或代码、数据结构的重新设计(reorganization)才能解决。

死锁bug (Deadlock Bugs)

为什么会出现死锁?

首先,大型代码框架中,不同组件之间的依赖关系很复杂。上锁的策略必须仔细设计才能防止因为循环依赖导致死锁(例如OS中虚存VM依赖于文件系统FS,FS反过来也依赖于VM)。

其次,软件设计封闭性的特征容易导致死锁。设计软件时,我们设计接口而隐藏内部实现,但这容易导致问题:如Java中的向量有一个AddAll()方法,调用v1.AddAll(v2)时会取得v1v2的锁,但如果此时刚好有线程调用v2.AddAll(v1),就会造成死锁。

导致死锁的四个条件

  • 互斥:线程获得对所需资源的互斥控制权(如上锁);
  • 请求与保持(hold-and-wait):线程申请新的资源时已经持有部分资源(如已经上锁,还要再上一把);
  • 没有抢占(no preemption):无法抢夺线程已经拥有的资源(如强制解锁);
  • 循环等待(circular wait):存在一个试图获得别的线程所拥有的资源的循环链。

如果以上四个条件中任意一条不满足,死锁就不可能发生。因此阻止以上条件成立就是解决死锁的方法。

循环等待

最有效的防止死锁的条件就是永远不要出现循环等待。最直接的方法是提供一个获得所有锁的全序关系)(total ordering)。

在复杂系统中,不可能只有两把锁,此时可以提供所有锁获得顺序的偏序关系(partial ordering)。

即使有了锁的顺序关系,垃圾程序员(原文:sloppy programmer)依然可以忽视上锁要求,轻松制造死锁。解决死锁需要对代码框架的深入理解以及各种程序是如何执行的。一个小小的失误原子弹,都可以导致死锁(原文:"D" word,指deadlock而不是damned)。

编程指南:强制用地址来决定获得锁的顺序

当一个程序必须获得两把(或者更多)锁的时候,可以将锁的地址进行排序,然后按顺序上锁。

(怎么听着像是TCAS的设计)

请求与保持

防止一段程序已经有了锁还要更多(吃着碗里的看着锅里的)的有效方法是给上锁过程再上个锁,把整个上锁变成原子过程:

pthread_mutex_lock(prevention); // begin lock acquisition
pthread_mutex_lock(L1);
pthread_mutex_lock(L2);
// ...
pthread_mutex_unlock(preciton); // end of critical section

这样所有锁都能同时上、同时解。不管什么上锁顺序都OK。

然而,这个解决方案还是有问题的:很多锁并不是一次就要上完。调用某个接口(封闭的,不知道里面在干嘛)的时候,可能只需要给该对象上一把锁,后面发生内存读取的时候再上另外的锁就好了。一次性把锁上完会造成效率低下。

强制抢占

pthread_mutex_trylock()函数要么获得锁并返回成功,或者报错提示锁已经被占用。在后一种情况中,你可以再试一次(主动放弃自己已有的锁,解开阻塞),然后再次尝试获得想要拥有的锁。

top:
  pthread_mutex_lock(L1);
  if (pthread_mutex_trylock(L2) != 0) {
    pthread_mutex_unlock(L1); // give up
    goto top;                 // try again
  }

然而,此做法会导致一个新问题:活锁(livelock)。假设线程2和线程1一样,在获得第二个锁失败的时候主动放弃自己已有的锁,那么就有机会两个线程互相推让,谁也上不了锁。

解决活锁问题的方案:添加一个随机的延迟。避免两个线程相互抢锁又因为同时抢锁谁也没抢到。

然而(第二个然而),此做法在锁多的时候还会产生新的问题:假设我们还有一个锁L0,上面的代码在企图获得L1的时候已经获得了L0,那么如果抢夺L2失败,就必须同时放弃L0和L1;在获得L2后又必须记得把L0上回去。又或者,在获得L1之后分了块内存空间,如果抢夺L2失败也必须把内存空间还回去。这样会使得程序变得复杂,但在部分情况下(如Java的Vector)非常有效。

这个“抢占”方案其实并根本没有抢占,而是用一种和平的方式把自己的资源让出去了。

互斥

从代码中删除互斥性的主要想法是:利用强大的硬件指令,构造访问时不需要显式(explicit)上锁的数据结构。

例如:CompareAndSwap方法会不断尝试获取旧数据、设置新数据,直到成功为止。

给链表插入新元素的无锁代码如下:

void insert(int value) {
  node_t *n = malloc(sizeof(node_t));
  assert(n != NULL);
  n->value = value;
  do {
    n->next = head;
  } while (CompareAndSwap(&head, n->next, n) == 0);
}

如果另一个线程也修改了head,那么当前进程的修改就会失败,继续循环直到成功为止。

利用调度避免死锁

假设线程T1和T2都要上L1和L2两把锁,那么智能的CPU就可以判断:如果这两个线程不同时运行,就不可能出现死锁。因此,CPU可以将这两个进程排在同一个处理器上运行,从而避免同时运行的出现。

检测死锁

最终解决方案是允许死锁偶尔发生,但一旦OS检测到死锁,就要采取操作(最常见的:关机/重启)恢复执行。

评论