Quiescent State Based Reclamation vs Epoch Based Reclamation

Question

I'm studying the various types of memory reclamation strategies for lock-free data structures in a non-garbage collected environment (like C or C++).

In my experiments, I've implemented a few of these strategies successfully - specifically, both Quiescent State Based Reclamation (QSBR) and Epoch Based Reclamation (EBR).

My question concerns one of the key differences between these two strategies.

Firstly, I'm aware of how both QSBR and EBR work, and have successfully implemented both of these strategies. QSBR and EBR are in fact very similar. Both of them are deferred reclamation strategies - meaning, they avoid race conditions when deallocating memory by simply deferring the actual deallocation until it can be proven that it is safe to deallocate the memory. With both QSBR and EBR this is achieved using a global "epoch counter", and then various thread-local epoch counters for each participating threads.

The main difference between QSBR and EBR is that with QSBR, you basically indicate when a thread does not have any references to any shared data. With EBR, you indicate when a thread does have a reference to shared data. So, in practice, code that uses EBR ends up looking more like a traditional mutex lock/unlock critical section, like:

enter_critical_section();

/* do some cool lock-free stuff */

exit_critical_section();

...whereas, with QSBR, it's more like:

/* do some cool lock-free stuff */

quiescent_state(); // this thread is done using shared data

So they're very similar. However, one key thing I don't really understand is how all the literature indicates that in practice, QSBR has one major disadvantage: it requires application level support, meaning that it isn't really suitable for use in a generic library.

This is mentioned in countless journal articles or library documentation, such as for example in http://www.cs.toronto.edu/~tomhart/papers/tomhart_thesis.pdf, it says:

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

The docs for the User-space RCU project, which uses a variation of QSBR, also says something similar:

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.

I'm having difficulty understanding why this is such a problem. What I gather here is that with QSBR, the application needs to indicate when it enters a quiescent state. But I fail to understand why this is so hard to do at the library level?

Couldn't a lock-free library that provides data structures such as stacks and queues simply indicate that it is entering a quiescent state after each operation completes? Why are there all these caveats about QSBR that indicate it is somehow not easy to use in library code as opposed to application code?

Answer 1

In QSBR quiescent_state() can be called at an arbitrary place where the calling thread holds no references to shared objects. On the other hand, in EBR a thread must access shared objects within critical section annotated by enter_critical_section() and exit_critical_section.

What this difference impiles is:

1. QSBR can outperform EBR because it can be used with less frequent synchronization. Yes, as you said, QSBR can be used in the similar way with EBR, but that does not provide the efficiency QSBR claims.

2. In a complex application, identifying quiescent state can be hard. This is why quiescent-based techniques such as RCU usage is mainly restricted to specific environment where there is a natural quiecent state (e.g. context switch in Linux kernel).