doc/html/lockfree.html

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
   2 <html>
   3 <head>
   4 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   5 <title>Chapter&#160;22.&#160;Boost.Lockfree</title>
   6 <link rel="stylesheet" href="../../doc/src/boostbook.css" type="text/css">
   7 <meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
   8 <link rel="home" href="index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
   9 <link rel="up" href="libraries.html" title="Part&#160;I.&#160;The Boost C++ Libraries (BoostBook Subset)">
  10 <link rel="prev" href="boost_lexical_cast/performance.html" title="Performance">
  11 <link rel="next" href="lockfree/examples.html" title="Examples">
  12 </head>
  13 <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
  14 <table cellpadding="2" width="100%"><tr>
  15 <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../boost.png"></td>
  16 <td align="center"><a href="../../index.html">Home</a></td>
  17 <td align="center"><a href="../../libs/libraries.htm">Libraries</a></td>
  18 <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
  19 <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
  20 <td align="center"><a href="../../more/index.htm">More</a></td>
  21 </tr></table>
  22 <hr>
  23 <div class="spirit-nav">
  24 <a accesskey="p" href="boost_lexical_cast/performance.html"><img src="../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="libraries.html"><img src="../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="index.html"><img src="../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="lockfree/examples.html"><img src="../../doc/src/images/next.png" alt="Next"></a>
  25 </div>
  26 <div class="chapter">
  27 <div class="titlepage"><div>
  28 <div><h2 class="title">
  29 <a name="lockfree"></a>Chapter&#160;22.&#160;Boost.Lockfree</h2></div>
  30 <div><div class="author"><h3 class="author">
  31 <span class="firstname">Tim</span> <span class="surname">Blechmann</span>
  32 </h3></div></div>
  33 <div><p class="copyright">Copyright &#169; 2008-2011 Tim
  34       Blechmann</p></div>
  35 <div><div class="legalnotice">
  36 <a name="lockfree.legal"></a><p>
  37         Distributed under the Boost Software License, Version 1.0. (See accompanying
  38         file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
  39       </p>
  40 </div></div>
  41 </div></div>
  42 <div class="toc">
  43 <p><b>Table of Contents</b></p>
  44 <dl class="toc">
  45 <dt><span class="section"><a href="lockfree.html#lockfree.introduction___motivation">Introduction &amp;
  46     Motivation</a></span></dt>
  47 <dt><span class="section"><a href="lockfree/examples.html">Examples</a></span></dt>
  48 <dt><span class="section"><a href="lockfree/rationale.html">Rationale</a></span></dt>
  49 <dd><dl>
  50 <dt><span class="section"><a href="lockfree/rationale.html#lockfree.rationale.data_structures">Data Structures</a></span></dt>
  51 <dt><span class="section"><a href="lockfree/rationale.html#lockfree.rationale.memory_management">Memory Management</a></span></dt>
  52 <dt><span class="section"><a href="lockfree/rationale.html#lockfree.rationale.aba_prevention">ABA Prevention</a></span></dt>
  53 <dt><span class="section"><a href="lockfree/rationale.html#lockfree.rationale.interprocess_support">Interprocess
  54       Support</a></span></dt>
  55 </dl></dd>
  56 <dt><span class="section"><a href="lockfree/reference.html">Reference</a></span></dt>
  57 <dd><dl>
  58 <dt><span class="section"><a href="lockfree/reference.html#header.boost.lockfree.policies_hpp">Header &lt;boost/lockfree/policies.hpp&gt;</a></span></dt>
  59 <dt><span class="section"><a href="lockfree/reference.html#header.boost.lockfree.queue_hpp">Header &lt;boost/lockfree/queue.hpp&gt;</a></span></dt>
  60 <dt><span class="section"><a href="lockfree/reference.html#header.boost.lockfree.spsc_queue_hpp">Header &lt;boost/lockfree/spsc_queue.hpp&gt;</a></span></dt>
  61 <dt><span class="section"><a href="lockfree/reference.html#header.boost.lockfree.stack_hpp">Header &lt;boost/lockfree/stack.hpp&gt;</a></span></dt>
  62 </dl></dd>
  63 <dt><span class="section"><a href="lockfree/appendices.html">Appendices</a></span></dt>
  64 <dd><dl>
  65 <dt><span class="section"><a href="lockfree/appendices.html#lockfree.appendices.supported_platforms___compilers">Supported
  66       Platforms &amp; Compilers</a></span></dt>
  67 <dt><span class="section"><a href="lockfree/appendices.html#lockfree.appendices.future_developments">Future Developments</a></span></dt>
  68 <dt><span class="section"><a href="lockfree/appendices.html#lockfree.appendices.references">References</a></span></dt>
  69 </dl></dd>
  70 </dl>
  71 </div>
  72 <div class="section">
  73 <div class="titlepage"><div><div><h2 class="title" style="clear: both">
  74 <a name="lockfree.introduction___motivation"></a><a class="link" href="lockfree.html#lockfree.introduction___motivation" title="Introduction &amp; Motivation">Introduction &amp;
  75     Motivation</a>
  76 </h2></div></div></div>
  77 <h3>
  78 <a name="lockfree.introduction___motivation.h0"></a>
  79       <span class="phrase"><a name="lockfree.introduction___motivation.introduction__amp__terminology"></a></span><a class="link" href="lockfree.html#lockfree.introduction___motivation.introduction__amp__terminology">Introduction
  80       &amp; Terminology</a>
  81     </h3>
  82 <p>
  83       The term <span class="bold"><strong>non-blocking</strong></span> denotes concurrent data
  84       structures, which do not use traditional synchronization primitives like guards
  85       to ensure thread-safety. Maurice Herlihy and Nir Shavit (compare <a href="http://books.google.com/books?id=pFSwuqtJgxYC" target="_top">"The
  86       Art of Multiprocessor Programming"</a>) distinguish between 3 types
  87       of non-blocking data structures, each having different properties:
  88     </p>
  89 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
  90 <li class="listitem">
  91           data structures are <span class="bold"><strong>wait-free</strong></span>, if every
  92           concurrent operation is guaranteed to be finished in a finite number of
  93           steps. It is therefore possible to give worst-case guarantees for the number
  94           of operations.
  95         </li>
  96 <li class="listitem">
  97           data structures are <span class="bold"><strong>lock-free</strong></span>, if some
  98           concurrent operations are guaranteed to be finished in a finite number
  99           of steps. While it is in theory possible that some operations never make
 100           any progress, it is very unlikely to happen in practical applications.
 101         </li>
 102 <li class="listitem">
 103           data structures are <span class="bold"><strong>obstruction-free</strong></span>,
 104           if a concurrent operation is guaranteed to be finished in a finite number
 105           of steps, unless another concurrent operation interferes.
 106         </li>
 107 </ul></div>
 108 <p>
 109       Some data structures can only be implemented in a lock-free manner, if they
 110       are used under certain restrictions. The relevant aspects for the implementation
 111       of <code class="literal">boost.lockfree</code> are the number of producer and consumer
 112       threads. <span class="bold"><strong>Single-producer</strong></span> (<span class="bold"><strong>sp</strong></span>)
 113       or <span class="bold"><strong>multiple producer</strong></span> (<span class="bold"><strong>mp</strong></span>)
 114       means that only a single thread or multiple concurrent threads are allowed
 115       to add data to a data structure. <span class="bold"><strong>Single-consumer</strong></span>
 116       (<span class="bold"><strong>sc</strong></span>) or <span class="bold"><strong>Multiple-consumer</strong></span>
 117       (<span class="bold"><strong>mc</strong></span>) denote the equivalent for the removal
 118       of data from the data structure.
 119     </p>
 120 <h3>
 121 <a name="lockfree.introduction___motivation.h1"></a>
 122       <span class="phrase"><a name="lockfree.introduction___motivation.properties_of_non_blocking_data_structures"></a></span><a class="link" href="lockfree.html#lockfree.introduction___motivation.properties_of_non_blocking_data_structures">Properties
 123       of Non-Blocking Data Structures</a>
 124     </h3>
 125 <p>
 126       Non-blocking data structures do not rely on locks and mutexes to ensure thread-safety.
 127       The synchronization is done completely in user-space without any direct interaction
 128       with the operating system <a href="#ftn.lockfree.introduction___motivation.f0" class="footnote" name="lockfree.introduction___motivation.f0"><sup class="footnote">[8]</sup></a>. This implies that they are not prone to issues like priority inversion
 129       (a low-priority thread needs to wait for a high-priority thread).
 130     </p>
 131 <p>
 132       Instead of relying on guards, non-blocking data structures require <span class="bold"><strong>atomic operations</strong></span> (specific CPU instructions executed
 133       without interruption). This means that any thread either sees the state before
 134       or after the operation, but no intermediate state can be observed. Not all
 135       hardware supports the same set of atomic instructions. If it is not available
 136       in hardware, it can be emulated in software using guards. However this has
 137       the obvious drawback of losing the lock-free property.
 138     </p>
 139 <h3>
 140 <a name="lockfree.introduction___motivation.h2"></a>
 141       <span class="phrase"><a name="lockfree.introduction___motivation.performance_of_non_blocking_data_structures"></a></span><a class="link" href="lockfree.html#lockfree.introduction___motivation.performance_of_non_blocking_data_structures">Performance
 142       of Non-Blocking Data Structures</a>
 143     </h3>
 144 <p>
 145       When discussing the performance of non-blocking data structures, one has to
 146       distinguish between <span class="bold"><strong>amortized</strong></span> and <span class="bold"><strong>worst-case</strong></span> costs. The definition of 'lock-free' and
 147       'wait-free' only mention the upper bound of an operation. Therefore lock-free
 148       data structures are not necessarily the best choice for every use case. In
 149       order to maximise the throughput of an application one should consider high-performance
 150       concurrent data structures <a href="#ftn.lockfree.introduction___motivation.f1" class="footnote" name="lockfree.introduction___motivation.f1"><sup class="footnote">[9]</sup></a>.
 151     </p>
 152 <p>
 153       Lock-free data structures will be a better choice in order to optimize the
 154       latency of a system or to avoid priority inversion, which may be necessary
 155       in real-time applications. In general we advise to consider if lock-free data
 156       structures are necessary or if concurrent data structures are sufficient. In
 157       any case we advice to perform benchmarks with different data structures for
 158       a specific workload.
 159     </p>
 160 <h3>
 161 <a name="lockfree.introduction___motivation.h3"></a>
 162       <span class="phrase"><a name="lockfree.introduction___motivation.sources_of_blocking_behavior"></a></span><a class="link" href="lockfree.html#lockfree.introduction___motivation.sources_of_blocking_behavior">Sources
 163       of Blocking Behavior</a>
 164     </h3>
 165 <p>
 166       Apart from locks and mutexes (which we are not using in <code class="literal">boost.lockfree</code>
 167       anyway), there are three other aspects, that could violate lock-freedom:
 168     </p>
 169 <div class="variablelist">
 170 <p class="title"><b></b></p>
 171 <dl class="variablelist">
 172 <dt><span class="term">Atomic Operations</span></dt>
 173 <dd><p>
 174             Some architectures do not provide the necessary atomic operations in
 175             natively in hardware. If this is not the case, they are emulated in software
 176             using spinlocks, which by itself is blocking.
 177           </p></dd>
 178 <dt><span class="term">Memory Allocations</span></dt>
 179 <dd><p>
 180             Allocating memory from the operating system is not lock-free. This makes
 181             it impossible to implement true dynamically-sized non-blocking data structures.
 182             The node-based data structures of <code class="literal">boost.lockfree</code> use
 183             a memory pool to allocate the internal nodes. If this memory pool is
 184             exhausted, memory for new nodes has to be allocated from the operating
 185             system. However all data structures of <code class="literal">boost.lockfree</code>
 186             can be configured to avoid memory allocations (instead the specific calls
 187             will fail). This is especially useful for real-time systems that require
 188             lock-free memory allocations.
 189           </p></dd>
 190 <dt><span class="term">Exception Handling</span></dt>
 191 <dd><p>
 192             The C++ exception handling does not give any guarantees about its real-time
 193             behavior. We therefore do not encourage the use of exceptions and exception
 194             handling in lock-free code.
 195           </p></dd>
 196 </dl>
 197 </div>
 198 <h3>
 199 <a name="lockfree.introduction___motivation.h4"></a>
 200       <span class="phrase"><a name="lockfree.introduction___motivation.data_structures"></a></span><a class="link" href="lockfree.html#lockfree.introduction___motivation.data_structures">Data
 201       Structures</a>
 202     </h3>
 203 <p>
 204       <code class="literal">boost.lockfree</code> implements three lock-free data structures:
 205     </p>
 206 <div class="variablelist">
 207 <p class="title"><b></b></p>
 208 <dl class="variablelist">
 209 <dt><span class="term"><code class="computeroutput"><a class="link" href="boost/lockfree/queue.html" title="Class template queue">boost::lockfree::queue</a></code></span></dt>
 210 <dd><p>
 211             a lock-free multi-produced/multi-consumer queue
 212           </p></dd>
 213 <dt><span class="term"><code class="computeroutput"><a class="link" href="boost/lockfree/stack.html" title="Class template stack">boost::lockfree::stack</a></code></span></dt>
 214 <dd><p>
 215             a lock-free multi-produced/multi-consumer stack
 216           </p></dd>
 217 <dt><span class="term"><code class="computeroutput"><a class="link" href="boost/lockfree/spsc_queue.html" title="Class template spsc_queue">boost::lockfree::spsc_queue</a></code></span></dt>
 218 <dd><p>
 219             a wait-free single-producer/single-consumer queue (commonly known as
 220             ringbuffer)
 221           </p></dd>
 222 </dl>
 223 </div>
 224 <h4>
 225 <a name="lockfree.introduction___motivation.h5"></a>
 226       <span class="phrase"><a name="lockfree.introduction___motivation.data_structure_configuration"></a></span><a class="link" href="lockfree.html#lockfree.introduction___motivation.data_structure_configuration">Data
 227       Structure Configuration</a>
 228     </h4>
 229 <p>
 230       The data structures can be configured with <a href="../../libs/parameter/doc/html/index.html" target="_top">Boost.Parameter</a>-style
 231       templates:
 232     </p>
 233 <div class="variablelist">
 234 <p class="title"><b></b></p>
 235 <dl class="variablelist">
 236 <dt><span class="term"><code class="computeroutput"><a class="link" href="boost/lockfree/fixed_sized.html" title="Struct template fixed_sized">boost::lockfree::fixed_sized</a></code></span></dt>
 237 <dd><p>
 238             Configures the data structure as <span class="bold"><strong>fixed sized</strong></span>.
 239             The internal nodes are stored inside an array and they are addressed
 240             by array indexing. This limits the possible size of the queue to the
 241             number of elements that can be addressed by the index type (usually 2**16-2),
 242             but on platforms that lack double-width compare-and-exchange instructions,
 243             this is the best way to achieve lock-freedom.
 244           </p></dd>
 245 <dt><span class="term"><code class="computeroutput"><a class="link" href="boost/lockfree/capacity.html" title="Struct template capacity">boost::lockfree::capacity</a></code></span></dt>
 246 <dd><p>
 247             Sets the <span class="bold"><strong>capacity</strong></span> of a data structure
 248             at compile-time. This implies that a data structure is fixed-sized.
 249           </p></dd>
 250 <dt><span class="term"><code class="computeroutput"><a class="link" href="boost/lockfree/allocator.html" title="Struct template allocator">boost::lockfree::allocator</a></code></span></dt>
 251 <dd><p>
 252             Defines the allocator. <code class="literal">boost.lockfree</code> supports stateful
 253             allocator and is compatible with <a href="../../libs/interprocess/index.html" target="_top">Boost.Interprocess</a>
 254             allocators.
 255           </p></dd>
 256 </dl>
 257 </div>
 258 </div>
 259 <div class="footnotes">
 260 <br><hr style="width:100; text-align:left;margin-left: 0">
 261 <div id="ftn.lockfree.introduction___motivation.f0" class="footnote"><p><a href="#lockfree.introduction___motivation.f0" class="para"><sup class="para">[8] </sup></a>
 262         Spinlocks do not directly interact with the operating system either. However
 263         it is possible that the owning thread is preempted by the operating system,
 264         which violates the lock-free property.
 265       </p></div>
 266 <div id="ftn.lockfree.introduction___motivation.f1" class="footnote"><p><a href="#lockfree.introduction___motivation.f1" class="para"><sup class="para">[9] </sup></a>
 267         <a href="http://threadingbuildingblocks.org/" target="_top">Intel's Thread Building
 268         Blocks library</a> provides many efficient concurrent data structures,
 269         which are not necessarily lock-free.
 270       </p></div>
 271 </div>
 272 </div>
 273 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 274 <td align="left"><p><small>Last revised: December 10, 2019 at 00:26:27 GMT</small></p></td>
 275 <td align="right"><div class="copyright-footer"></div></td>
 276 </tr></table>
 277 <hr>
 278 <div class="spirit-nav">
 279 <a accesskey="p" href="boost_lexical_cast/performance.html"><img src="../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="libraries.html"><img src="../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="index.html"><img src="../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="lockfree/examples.html"><img src="../../doc/src/images/next.png" alt="Next"></a>
 280 </div>
 281 </body>
 282 </html>