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