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=UTF-8"> 5<title>Chapter 22. 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 I. 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 22. 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 © 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 & 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 <boost/lockfree/policies.hpp></a></span></dt> 59<dt><span class="section"><a href="lockfree/reference.html#header.boost.lockfree.queue_hpp">Header <boost/lockfree/queue.hpp></a></span></dt> 60<dt><span class="section"><a href="lockfree/reference.html#header.boost.lockfree.spsc_queue_hpp">Header <boost/lockfree/spsc_queue.hpp></a></span></dt> 61<dt><span class="section"><a href="lockfree/reference.html#header.boost.lockfree.stack_hpp">Header <boost/lockfree/stack.hpp></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 & 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 & Motivation">Introduction & 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 & 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-producer/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-producer/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: August 11, 2020 at 15:03:13 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> 283
