Channels ▼
RSS

Embedded Systems

Lock-free Interprocess Communication


Alexander is currently working as a Senior Software Engineer for Computer Associates, and can be contacted for the purposes of this article at lock-free@hotmail.com.


Some time ago I was interested in finding a type of interprocess (interthread) communication which would require minimal preconditions on the platform and not require a set of special processor commands. This article describes lock-free interprocess communication which does not require any special processor commands, and the only precondition for successful interprocess communication is knowledge of processor word length.

Many recipes for lock-free interprocess communication require special atomic processor commands. In this article, I propose a communication type that requires only atomic writing of processor word from processor cache into main memory and atomic processor word reading from main memory into the processor register or processor cache. To the best of my knowledge, all platforms satisfy these requirements if the address in memory is properly aligned. Later in the article, I'll discuss performance issues related to cache trashing.

Based on this communication mechanism, I implement a registry which allows updates but at the same time allows a linear increase in reading performance by increasing the number of processors. Some performance testing results are presented for single- as well as multi-processor systems. This testing shows that on some platforms, lock-free algorithms outperform standard techniques by 30 or more times (>=3000%).

In this article, I'll present four algorithms. Algorithm one demonstrates the main idea. Algorithm two (light pipe) is mostly a low level communication primitive to pass data between two processes, but is interesting to some extent in and of itself. Algorithm three takes into account cache line length to increase the performance of algorithm two. Algorithm four is an implementation of a registry optimised for reads. Algorithm four uses algorithm three (cache line optimised light pipe) as a communication primitive.


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