美文网首页
资源竞争与死锁检测

资源竞争与死锁检测

作者: 码农苍耳 | 来源:发表于2018-04-15 22:45 被阅读273次

多线程编程一直是一个非常难的话题,而资源竞争和死锁问题则是比较常见的多线程问题,这里我们来看看如何检测这些问题。

LLVM

其实llvm项目自身就有这两者的检测方法。而在xcode中也集成了该功能,要使用也非常简单,选中Thread Sanitizer,并且重新编译运行即可。

image

那么接下来我们来看看使用情况以及他们是如何实现的。

Data Race

数据竞争是我们非常容易犯的一个错误,而且出现问题了也非常难解决。因为出现的概率并不高,而且出现了问题也不会直接表现出来,而可能是通过其他方式表现出来。

首先我们来看一个非常简单的数据竞争问题:

char g_char;

- (void)viewDidLoad {
    [super viewDidLoad];
    
    dispatch_async(dispatch_get_global_queue(0, 0), ^{
        [self setCharB];
    });
    [self setCharA];
}

- (void)setCharA {
    g_char = 'a';
}

- (void)setCharB {
    g_char = 'b';
}

虽然更新一个字节这种操作非常简单,但依然需要在这里加上锁,如果没有加上则会报告如下错误:

==================
WARNING: ThreadSanitizer: data race (pid=62345)
  Write of size 1 at 0x0001032e0f10 by thread T2:
    #0 -[ViewController setCharB] ViewController.m:35 (MallocTest:x86_64+0x100001499)
    #1 __29-[ViewController viewDidLoad]_block_invoke ViewController.m:26 (MallocTest:x86_64+0x1000013da)
    #2 __tsan::invoke_and_release_block(void*) <null>:2136816 (libclang_rt.tsan_iossim_dynamic.dylib:x86_64+0x622bb)
    #3 _dispatch_client_callout <null>:2136816 (libdispatch.dylib:x86_64+0x3847)

  Previous write of size 1 at 0x0001032e0f10 by main thread:
    #0 -[ViewController setCharA] ViewController.m:32 (MallocTest:x86_64+0x100001472)
    #1 -[ViewController viewDidLoad] ViewController.m:28 (MallocTest:x86_64+0x100001381)
    #2 -[UIViewController loadViewIfRequired] <null>:2136816 (UIKit:x86_64+0x1ce190)
    #3 start <null>:2136816 (libdyld.dylib:x86_64+0x1954)

  Location is global 'g_char' at 0x0001032e0f10 (MallocTest+0x000100003f10)

  Thread T2 (tid=1422519, running) is a GCD worker thread

SUMMARY: ThreadSanitizer: data race ViewController.m:35 in -[ViewController setCharB]
==================

同时在左边的导航栏里会显示如下结果:

image

那么LLVM是怎么实现的呢?

资源竞争的检测其实分为两部分,一部分是编译期的处理,另一部分是运行期的监控。

编译期,编译器会在数据访问的时候插入一段代码,来告诉检测器具体的数据访问情况。这个效果可以看具体的汇编:

-[ViewController setCharA]:
    0x106bd4448 <+0>:  pushq  %rbp
    0x106bd4449 <+1>:  movq   %rsp, %rbp
    0x106bd444c <+4>:  movq   0x8(%rbp), %rdi
    0x106bd4450 <+8>:  callq  0x106bd4798               ; symbol stub for: __tsan_func_entry
    0x106bd4455 <+13>: leaq   0x2afc(%rip), %rdi        ; g_char
    0x106bd445c <+20>: callq  0x106bd47bc               ; symbol stub for: __tsan_write1
    0x106bd4461 <+25>: movb   $0x61, 0x2af0(%rip)       ; lock + 63
    0x106bd4468 <+32>: callq  0x106bd479e               ; symbol stub for: __tsan_func_exit
    0x106bd446d <+37>: popq   %rbp
    0x106bd446e <+38>: retq   

运行期的监控则是靠动态库来导入的(在早期是依赖于静态库)。

可以看到,需要做到在编译期插入代码,不禁会想已经编译好的二进制该怎么办?这里我们来看两个例子:

CoreFoundation`-[__NSArrayM addObject:]:
    ...
    0x10e5b0d82 <+18>: leaq   0x3a3fa7(%rip), %rax      ; __cf_tsanWriteFunction
    ...

在NSMutableArray的代码中,我们发现有一个方法很可疑__cf_tsanWriteFunction,这个方法似乎就是上面的__tsan_write1方法的objc版。同时这个方法在真机上是没有的。

pthread_mutex_lock(&lock)在该模式下实际对应的方法是libclang_rt.tsan_iossim_dynamic.dylib wrap_pthread_mutex_lock,同时dispatch_sync对应的方法是libclang_rt.tsan_iossim_dynamic.dylib wrap_dispatch_sync,可以知道他们都来源于一个非标准的动态库,这也就是说明在该模式下,系统会给我们链接一个已经编译好的,插入相应代码的动态库。这也代表着如果你引用了第三方二进制库,不一定能够检测出其中的竞争问题。

这里还需要检测到线程的状态,则是使用了pthread的一个公开接口:

typedef void (*pthread_introspection_hook_t)(unsigned int event, pthread_t thread, void *addr, size_t size);

enum {
  PTHREAD_INTROSPECTION_THREAD_CREATE = 1,
  PTHREAD_INTROSPECTION_THREAD_START,
  PTHREAD_INTROSPECTION_THREAD_TERMINATE,
  PTHREAD_INTROSPECTION_THREAD_DESTROY,
};

pthread_introspection_hook_install(pthread_introspection_hook);
算法

这个的检测算法较为复杂,这里简单的来描述一下。

  • 首先每一个数据根据其内存地址与访问线程id都会有一个对应的内存区块来保存其访问数据,一般是8 bytes映射为1 bytes,所以这里的内存分配器也是需要进行相应的修改。
  • 将当前状态和已保存的数据进行比较。
  • 如果是非同一个线程,并且已保存的数据访问时间是在当前访问时间之后。
  • 那么认为这是一次资源竞争。

Dead lock

死锁的检测相对比较简单了,他并不需要编译期的介入,而是纯运行时的检测。不过遗憾的是xcode上并没有集成,可能是觉得死锁本身就会严重阻碍程序运行,容易被察觉吧。

主要需要做的是hook掉所有锁相关的api,掌管willLockdidLock的消息,LLVM提供默认hook了pthread的相关接口。

每次加锁之前都会产生一个锁-线程的匹配,加锁之后释放该锁-线程的匹配。

如果A锁被某线程持有,同时B锁也被该线程持有,那么就形成了A=>B的一个关联,如果这样的关联形成了一个环,那么就说明产生了死锁。该方法可以利用邻接二维矩阵来实现高效的查找。

如果恢复产生的死锁问题呢?这里我没有找到更好的办法,只能做以下两种处理:

  • 杀死某个非主线程的线程,这样能够解除死锁,但会引起资源泄露和逻辑缺失的问题。
  • 直接返回,可能会引起资源竞争的问题。

参考

The "Double-Checked Locking is Broken" Declaration
Finding races and memory errors with compiler instrumentation.
ThreadSanitizerAlgorithm
llvm-compiler-rt
valgrind

相关文章

  • 资源竞争与死锁检测

    多线程编程一直是一个非常难的话题,而资源竞争和死锁问题则是比较常见的多线程问题,这里我们来看看如何检测这些问题。 ...

  • 操作系统笔记01——死锁

    目录 必要条件 处理方法鸵鸟策略死锁检测与死锁恢复1.每种类型一个资源的死锁检测2.每种类型多个资源的死锁检测3....

  • [现代操作系统]--死锁

    table of content 死锁定义 死锁建模-- 资源分配图 处理死锁鸵鸟算法检测并恢复死锁检测死锁恢复利...

  • MySQL死锁、资源竞争死锁

    什么是MySQL死锁: 什么是资源竞争死锁: 比如连接池 ShardingSphere文档中写到关于 数据库连接的...

  • 死锁

    1.死锁原因 1)资源竞争 2)进程推进顺序非法(互相占有彼此需要的资源,同时请求对方占有的资源) 所谓死锁,通常...

  • 死锁的四个必要条件

    一. 什么是死锁? 二. 死锁产生的原因? 1.因竞争资源发生死锁 现象:系统中供多个进程共享的资源的数目不足以满...

  • 死锁理论知识补充

    目录 1.死锁的定义与例子2.死锁的原因3.破题 定义: 死锁的一个比较专业的定义是:一组互相竞争资源的线程因互相...

  • 操作系统(二)进程管理 2.4 死锁

    2.4 死锁 2.4.1 死锁的概念 2.4.1.1 死锁的定义 在并发环境下,各进程因竞争资源而造成的一种互相等...

  • 2019-11-07

    今天学习了死锁的检测与解除

  • 9.3 死锁检测与解除

    当系统为进程分配资源时,若未采取任何限制性措施,则系统应该提供检测和解除死锁的手段。 资源分配图 系统死锁,可利用...

网友评论

      本文标题:资源竞争与死锁检测

      本文链接:https://www.haomeiwen.com/subject/elwjkftx.html