[操作系统]12. 并发 Bug 分类

[supergem3000]

12. 真实世界的并发 Bug (jyywiki.cn)

死锁

出现线程“互相等待”的情况。 AA-Deadlock 最简单的情况

lock(&lk);
// lk = LOCKED;
lock(&lk);
// while (xchg(&lk, LOCKED) == LOCKED);

ABBA-Deadlock 哲学家吃饭问题

死锁产生的四个必要条件

阅读材料：System Deadlocks | ACM Computing Surveys

1. Mutual-exclusion 互斥条件：一个资源只能被一个线程拥有。
2. Wait-for 请求与保持条件：一个线程请求资源被阻塞时，不释放已获得的资源。
3. No-preemption 不可剥夺条件：资源被使用完之前不能被强行抢夺。
4. Circular-chain 循环等待条件：若干线程之间形成一种头尾相接的循环等待资源关系。 打破任何一个条件即可避免死锁。但是打破条件并不容易，打破1、2、3条件都会破坏互斥的含义。消除循环等待是通常的做法。

   数据竞争

   不同的线程同时访问同一内存，且至少有一个是写。 C/C++: data race is undefined behavior Memory model - cppreference.com 之前课程资料写的示例Peterson算法，其实存在ub，在x86上正确不代表在其他平台正确。

锁的存在消灭了数据竞争。面对数据竞争：只要记得用锁保护好共享数据，消灭一切数据竞争。 数据竞争举例:

// Case #1: 上错了锁
void thread1() { spin_lock(&lk1); sum++; spin_unlock(&lk1); }
void thread2() { spin_lock(&lk2); sum++; spin_unlock(&lk2); }

// Case #2: 忘记上锁
void thread1() { spin_lock(&lk1); sum++; spin_unlock(&lk1); }
void thread2() { sum++; }

原子性和顺序违反

人类是sequential creature，用sequential方式理解并发：

• 程序分成若干块，每一块看起来没有被打断（原子）
• 具有逻辑先后的块被正确同步 互斥锁（lock/unlock）实现原子性：忘记上锁——原子性违反（Atomicity Violation，AV） 条件变量/信号量（wait/signal）实现先后顺序同步：忘记同步——顺序违反（Order Violation，OV）

原子性违反 “ABA”：以为一段代码没啥事，但是被人强势插入了。如山寨支付宝问题。 顺序违反 “BA”：没按照预想的顺序来。如use after free。