Sil*_*ler 10 algorithm multithreading memory-management thread-safety lock-free
我正在研究非垃圾收集环境(如C或C++)中无锁数据结构的各种类型的内存回收策略.
在我的实验中,我成功地实施了一些这样的策略 - 特别是基于静态状态的回收(QSBR)和基于纪元的回收(EBR).
我的问题涉及这两种策略之间的主要区别之一.
首先,我知道QSBR和EBR如何工作,并成功实施了这两种策略.QSBR和EBR实际上非常相似.它们都是延迟回收策略 - 意思是,它们在通过简单地推迟实际释放来释放内存时避免竞争条件,直到可以证明释放内存是安全的.对于QSBR和EBR,这是使用全局"纪元计数器",然后是每个参与线程的各种线程本地纪元计数器来实现的.
QSBR和EBR之间的主要区别在于,使用QSBR,您基本上可以指示线程何时没有任何对任何共享数据的引用.随着EBR,你表明当一个线程确实有对共享数据的参考.因此,在实践中,使用EBR的代码最终看起来更像传统的互斥锁定/解锁关键部分,如:
enter_critical_section();
/* do some cool lock-free stuff */
exit_critical_section();
...而对于QSBR,它更像是:
/* do some cool lock-free stuff */
quiescent_state(); // this thread is done using shared data
所以他们非常相似.但是,我不太了解的一个关键问题是所有文献都表明在实践中,QSBR有一个主要缺点:它需要应用程序级支持,这意味着它不适合在通用库中使用.
这在无数期刊文章或图书馆文献中都有提及,例如在http://www.cs.toronto.edu/~tomhart/papers/tomhart_thesis.pdf中,它说:
QSBR与应用有关的事实是QSBR和EBR之间的根本区别.根据定义,EBR可以检测库级别的宽限期.相比之下,QSBR要求应用程序向QSBR库报告静止状态.正如我们在5.2节中所示,这使QSBR具有显着的性能优势
用户空间RCU项目的文档使用了QSBR的变体,也说了类似的东西:
但是,每个线程必须定期调用rcu_quiescent_state(),就像在内核中一样,必须定期调用schedule().执行RCU读取端关键部分的每个线程还必须在线程创建之后调用rcu_register_thread(),并在线程退出之前调用rcu_unregister_thread().这些要求显然严格限制了整个应用程序设计,例如,禁止在大多数库代码中使用QSBR RCU,但作为回报,QSBR提供了无与伦比的性能.
我很难理解为什么会出现这样的问题.我在这里收集的是,使用QSBR,应用程序需要指示它何时进入静止状态.但我不明白为什么在图书馆层面这么难？
提供堆栈和队列等数据结构的无锁库是否只能表明它在每次操作完成后进入静止状态？为什么有关于QSBR的所有这些警告表明它在库代码中以某种方式不易使用而不是应用程序代码？
在 QSBR 中，quiescent_state()可以在调用线程不持有共享对象引用的任意位置调用。另一方面，在 EBR 中，线程必须enter_critical_section()访问由和注释的临界区中的共享对象exit_critical_section。
这种差异带来的后果是：
QSBR 的性能优于 EBR，因为它可以在不太频繁的同步情况下使用。是的，正如您所说，QSBR 可以以与 EBR 类似的方式使用，但这并不能提供 QSBR 声称的效率。
在复杂的应用中，识别静态状态可能很困难。这就是为什么基于静态的技术（例如 RCU 使用）主要限于存在自然静态状态的特定环境（例如 Linux 内核中的上下文切换）。