Race Condition(竞争)指多线程同时访问一个资源时,由于访问顺序不同,导致的结果不同。这种并发性bug经常难以复现,又被称为海森bug(测不准)。Eraser,用于检测这种情况。翻译过程中附带重构。
总结一下,这个Eraser就是用一个迭代的方式,维护每次内存被访问时,使用锁的交集。如果交集为空,那么说明没有锁能保证每次访问时都被使用,因此就可能发生Data Race。一个亮点在于,Eraser可以直接通过机器码插入到源程序,而无需插入源代码中。
原作: ACM Transactions on Computer Systems, Vol. 15, No. 4, November 1997 引用: http://cseweb.ucsd.edu/~savage/papers/Tocs97.pdf 译者:朝闻君
多线程编程复杂容易出错,很容易造成data race,却难以定位。
Eraser,可以在基于锁的程序中通过监控共享内存的引用,核查锁的行为一致性,动态检测出data race。并且Eraser可以对二进制机器码修改,直接插入原程序。
关键词:二进制机器码修改,多线程,竞争检测。
初始算法
如果不同线程在用不同的锁保护同一个共享变量,那么就有可能有两个线程同时访问一个共享变量。
强制共享变量必须被一组特定的锁保护。Eraser监控每次读写,来观测程序是否遵循这个规范。
由于Eraser没有办法知道锁的目的,因此必须根据历史来获取锁的保护关系。
对于每个共享变量v,Eraser维护一个候选锁集合C(v),其中存放所有保护过v的锁。
Lockset Refinement
初始版本
变量初始化时,C(v)为所有可能的锁的集合。
变量被访问时,C(v)<- C(v)
当前线程的锁的集合。
显然,这个集合只会变小或者维持稳定。
终态:
所有的线程用一致的锁保护同一个资源(不动点)=> Refined
C(v)为空 => Inconsistent
检测到v没有被正确保护
改进规则
上面的规则太过于严格,有三种情况不会发生Race Condition,同时又违背了上面的规则。
初始化/只读
如果没有其他线程能引用时,那么没有必要把其他线程锁住。对于新分配的数据既是如此。
为了避免错误的警告,Eraser将候选集的refinement延迟到初始化完成之后再进行。然而确认初始化是否完成很困难,因此这个时间又被延迟到共享变量被第二个线程初次访问时。
如果共享变量始终仅由一个线程读写,那么refinement就始终不执行。
此外,对于只读对象,同样没有必要保护。通过只警告那些被多个线程写的共享变量,可以提供这样的支持。
完成上面逻辑的状态机
憨憨们可能会在初始化完成前就让其他线程访问,那属于自己作死,与Eraser无关。
读写锁
如果因为写而更新,则只保留那些处于写mode的锁。
这样读锁就会被筛去,因为他们事实上无法保护data race。
Eraser实现在Alpha处理器上的Digital Unix OS中,使用ATOM [Srivastava and Eustace 1994]二进制修改系统。
Eraser将没有修改的二进制代码作为输入,产生功能一致的新的二进制代码,但是其中插入了Eraser runtime。
监测每个全局/堆上的load/store来维护C(v)(通过地址和栈指针的关系)
监测每次锁的acquire/release的调用以及线程的创建/终结,来维护线程持有的锁。
监测每个内存分配,来初始化C(v),每个word都有可能成为共享变量。(这么麻烦,主要是因为在对二进制,而不是源代码做修改)
维护通过寄存器而不是栈指针所能访问的栈地址的集合。
race发生时,Eraser log到文件中,并报告行号,栈帧的traceback,线程ID,内存地址,访问方式,PC/RSP的值等等,从而定位问题代码。如果还不能发现,那么让Eraser log每次访问。
边界条件
存在一些误报,因为Eraser以标准C/C++的内存分配/lock作为监控对象。因此使用一些特殊的注解,可以让Eraser忽略这些误报
Memory Reuse
私有的内存分配器无法被监控
EraserReuse(address, size)
Primary Lock
私有的锁无法被监控
EraserReadLock(lock)
EraserReadUnlock(lock)
EraserWriteLock(lock)
EraserWriteUnlock(lock)
Begin Races
程序前编译器插入的代码,出了Data Race但是不会导致程序受影响。
EraserIgnoreOn( )
EraserIgnoreOff( )
性能
作者发现一般的开销来自于ATOM中每次监控都需要进行一次函数调用,但是升级到1996版本就能内联了。因此他直接认为性能没有很大影响,并且也不是程序主要的目的所在。
检测OS的问题很困难。
Systems that integrate thread and interrupt processing [Kleiman and Eykholt 1995] may have less trouble with this problem.