Channels ▼
RSS

C/C++

Lock-Free Queues

Source Code Accompanies This Article. Download It Now.


Final Considerations

The single-threaded code below shows the value of the list.size() when Producing/ Consuming elements:

 
LockFreeQueue<int> q;   // list.size() == 1
q.Produce(1);    // list.size() == 2
int i;
q.Consume(i);  // list.size() == still 2!;
               // Consume() doesn't modify the list
q.Produce(i);    // list.size() == 2 again;

The size of the queue is 1 if Produce() was never called and greater than 1 if any element was produced.

No matter how many times Consume() is called, the list's size will stay constant. It is Produce() that is increasing the size (by 1); and if there were consumed elements, it will also delete them from the queue. In a way, Produce() acts as a simple garbage collector. The whole thread safety comes from the fact that specific data is modified from single threads only. The synchronization between threads is done using iterators (or pointers, whichever has atomic read/write operation on your machine). Also consider this code:

 
usleep(1000);    // sleep 1 microsecond

On the face of it, this line of code makes a thread sleep for 1 microsecond, and then continue. In reality, 1 microsecond is just a lower bound to the duration of the call.

The man page for usleep() says, "The usleep() function suspends execution of the calling process for (at least) usec microseconds. The sleep may be lengthened slightly by any system activity or by the time spent processing the call or by the granularity of system timers," or if you use the nanosleep() function. "Therefore, nanosleep() always pauses for at least the specified time; however, it can take up to 10 ms longer than specified until the process becomes runnable again."

So if the process is not scheduled under a real-time policy, there's no guarantee when your thread will be running again. I've done some tests and (to my surprise) there are situations when code such as:

 
cond.timed_wait(lock, x);    // x = e.g. 1 millisecond

will actually wait for more than 1 second.

Acknowledgments

Many thanks to Andrei Alexandrescu who took the time to review this article. Also, thanks to Radu Duta for making useful corrections.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video