1. 应对 Bug 的方法

<aside> 📖 基本思路：自我否定

始终假设自己的代码是错的

</aside>

<aside> 📖 Bug 多的根本原因：编程语言的缺陷

软件是需求 (规约) 在计算机数字世界的投影。

编程语言只管 “翻译” 代码，不管和实际需求 (规约) 是否匹配

</aside>

<aside> 📖 解决方法：防御性编程

把程序需要的条件用 assert 表示出来，即根据现实需求定义自己的规约。

assert 的逻辑本身也可能犯错，但 assert 和代码本身加起来是对逻辑正确性的双重保障。

jyy: 在面试时很有用

</aside>

2. 并发Bug：死锁 Deadlock

<aside> 📖 死锁 Deadlock

A deadlock is a state in which each member of a group is waiting for another member, including itself, to take action.

</aside>

<aside> 📖 死锁产生的四个必要条件 (Edward G. Coffman, 1971)

• 互斥：一个资源每次只能被一个进程使用
• 请求与保持：一个进程请求资阻塞时，不释放已获得的资源
• 不剥夺：进程已获得的资源不能强行剥夺
• 循环等待：若干进程之间形成头尾相接的循环等待资源关系 </aside>

2.1 AA-Deadlock

假设你的 spinlock 不小心发生了中断

• 在不该打开中断的时候开了中断
• 在不该切换的时候执行了 yield()

<aside> 📖 避免死锁

利用防御性编程检测，及早报告，及早修复

</aside>

void os_run() {
  spin_lock(&list_lock);
  spin_lock(&xxx);
  spin_unlock(&xxx); // ---------+
}                          //    |
                           //    |
void on_interrupt() {      //    |
  spin_lock(&list_lock);   // <--+
  spin_unlock(&list_lock);
}

2.2 ABBA-Deadlock

上锁的顺序很重要

• swap 本身看起来没有问题
• swap(1, 2); swap(2, 3), swap(3, 1) → 死锁
• 哲学家吃饭问题

<aside> 📖 避免死锁 Lock Ordering

任意时刻系统中的锁都是有限的

严格按照固定的顺序获得所有锁 (lock ordering; 消除 “循环等待”)

“在任意时刻总是有获得 “最靠后” 锁的可以继续执行”

</aside>

void swap(int i, int j) {
  spin_lock(&lock[i]);
  spin_lock(&lock[j]);
  arr[i] = NULL;
  arr[j] = arr[i];
  spin_unlock(&lock[j]);
  spin_unlock(&lock[i]);
}

3. 并发Bug：数据竞争 Data Race

<aside> 📖 数据竞争

不同的线程同时访问同一段内存，且至少有一个是写。

</aside>

<aside> 📖 问题

不上锁就不会产生死锁问题，但数据竞争问题会随之产生

</aside>

<aside> 📖 解决方案

无锁的并发程序（Peterson算法）对于大型项目难以实现

因此最好的方法是用互斥锁保护好共享数据，消灭一切数据竞争

但也会有其他问题：

// 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++; }

</aside>

4. 更多类型的并发 Bug