multithreading - 基于静态状态的回收与基于时代的回收

Question

我正在研究非垃圾收集环境(如 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 ，它说:

The fact that QSBR is application-dependent is the fundamental difference between QSBR and EBR. EBR, by definition, detects grace periods at the library level. QSBR, by contrast, requires that the application report quiescent states to the QSBR library. As we show in Section 5.2, this gives QSBR a significant performance advantage over

User-space RCU project 的文档，它使用了 QSBR 的变体，也说了类似的话:

However, each thread must periodically invoke rcu_quiescent_state(), just as in the kernel, where schedule() must be invoked periodically. Each thread that is to execute RCU read-side critical sections must also invoke rcu_register_thread() after thread creation and rcu_unregister_thread() before thread exit. These requirements clearly put a stringent constraint on the overall application design that, for example, prohibit the use of QSBR RCU in most library code, but in return, QSBR provides unmatched performance.

我很难理解为什么会出现这样的问题。我在这里收集到的是，对于 QSBR，应用程序需要指示它何时进入静止状态。但我不明白为什么这在图书馆层面如此难以做到？

提供栈和队列等数据结构的无锁库难道不能简单地表明它在每个操作完成后进入静止状态吗？为什么有所有关于 QSBR 的警告表明它在库代码中使用起来比在应用程序代码中不容易使用？

Answer 1

在 QSBR 中，quiescent_state() 可以在调用线程不持有共享对象引用的任意位置调用。另一方面，在 EBR 中，线程必须访问由 enter_critical_section() 和 exit_critical_section 注释的临界区内的共享对象。

这种差异带来的是:

1. QSBR 可以胜过 EBR，因为它可以用于不太频繁的同步。是的，正如您所说，QSBR 可以与 EBR 类似的方式使用，但这并不能提供 QSBR 声称的效率。

2. 在复杂的应用程序中，识别静止状态可能很困难。这就是为什么 RCU 使用等基于静态的技术主要限于存在自然静态的特定环境(例如 Linux 内核中的上下文切换)。