并发bug 之 数据竞争 Data Race
- 不同的线程同时访问同一段内存，且至少有一个是写
- 为处理Data Race,我们需要一个互斥的协议，而peterson这种纯软的算法，太难了。故 我们应当使用(互斥)锁 消灭datarace
ThreadSanitizer原理
- 不同线程对一块共享内存操作 且至少有一个是写。对这些动作的执行顺序进行排序，若检验出无法排序的（即排序结果不唯一），则error
- 学习自jyy
Data Race
概述
起因：不上锁不就没有死锁了吗？
概念：不同的线程同时访问同一段内存，且至少有一个是写。
两个内存访问在 “赛跑”，“跑赢” 的操作先执行。
- 因此我们不知道执行后的状态到底是什么，是否是我们想要的状态。
- 如peterson-barrier.c: 内存访问都在赛跑
- 对于peterson算法，我们回想，如何留下最少的 fence，依然保证算法正确？很难的。
解决
- Peterson 算法告诉大家：
- 你们写不对无锁的并发程序
- 所以事情反而简单了
- 解决：
- 用互斥锁保护好共享数据，消灭一切数据竞争
- 以下代码概括了你们遇到数据竞争的大部分情况
- bug 几乎都是这两种情况的变种
1
2
3
4
5
6// 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++; }
- bug 几乎都是这两种情况的变种
其他类型的并发bug
回顾我们实现并发控制的工具
- 互斥锁 (lock/unlock) - 原子性
- 条件变量 (wait/signal) - 同步
忘记上锁——原子性违反 (Atomicity Violation, AV)
忘记同步——顺序违反 (Order Violation, OV)
Empirical study: 在 105 个并发 bug 中 (non-deadlock/deadlock)
- MySQL (14/9), Apache (13/4), Mozilla (41/16), OpenOffice (6/2)
- 97% 的非死锁并发 bug 都是 AV 或 OV。
原子性违反(AV)
- ABA
- 我以为一段代码没啥事呢，但被人强势插入了
- 我以为一段代码没啥事呢，但被人强势插入了
顺序违反 (OV)
- BA
- 怎么就没按我预想的顺序来呢？
- 例子： concurrent use after free
- 例子： concurrent use after free
- 怎么就没按我预想的顺序来呢？
bug排查
Lockdep 运行时死锁检查
ThreadSanitizer: 运行时的数据竞争检查
- 检验dataRace ; 为所有事件建立 happens-before 关系图
- 对于发生在不同线程且至少有一个是写的 x,y检查
- 会有不能排队的事件 检验出来
