title: Quiescent State Based Reclamation vs Epoch Based Reclamation
body: <p>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++).</p>
  
  <p>In my experiments, I've implemented a few of these strategies successfully - specifically, both <strong>Quiescent State Based Reclamation</strong> (QSBR) and <strong>Epoch Based Reclamation</strong> (EBR).</p>
  
  <p>My question concerns one of the key differences between these two strategies.</p>
  
  <p>Firstly, I'm aware of how both <strong>QSBR</strong> and <strong>EBR</strong> work, and have successfully implemented both of these strategies.  QSBR and EBR are in fact very similar.  Both of them are <em>deferred reclamation</em> strategies - meaning, they avoid race conditions when deallocating memory by simply <em>deferring</em> 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.</p>
  
  <p>The main difference between QSBR and EBR is that with QSBR, you basically indicate when a thread does <em>not</em> have any references to any shared data.  With EBR, you indicate when a thread <em>does</em> 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:</p>
  
  <pre><code>enter_critical_section();
  
  /* do some cool lock-free stuff */
  
  exit_critical_section();
  </code></pre>
  
  <p>...whereas, with QSBR, it's more like:</p>
  
  <pre><code>/* do some cool lock-free stuff */
  
  quiescent_state(); // this thread is done using shared data
  </code></pre>
  
  <p><br>
  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 <em>application level</em> support, meaning that it isn't really suitable for use in a generic library.</p>
  
  <p>This is mentioned in countless journal articles or library documentation, such as for example in <a href="http://www.cs.toronto.edu/~tomhart/papers/tomhart_thesis.pdf">http://www.cs.toronto.edu/~tomhart/papers/tomhart_thesis.pdf</a>, it says:</p>
  
  <blockquote>
    <p>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</p>
  </blockquote>
  
  <p>The docs for the <a href="https://lwn.net/Articles/573424/#Using%20URCU">User-space RCU project</a>, which uses a variation of QSBR, also says something similar:</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>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 <em>why</em> this is so hard to do at the library level?</p>
  
  <p>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?</p>