Channels ▼
RSS

Embedded Systems

Lock-free Interprocess Communication


Algorithm Two (Light Pipe)

This communication model also involves two processes: Reader and Writer. Writer is writing data into shared memory and the Reader process is reading consistent data from shared memory. The shared memory is aligned by processor word and initially is filled with zeros. Data is written by the Writer process to shared memory word by word, starting from word number 0. Data must contain only non-zero words (later I'll show how to lessen this requirement). Before writing a non-zero word to some address, the Writer process reads a word from this address and checks that its value is zero. If the read word is zero-valued then data can be written, otherwise the Writer process must wait. Suppose there are N words in the shared memory. After writing word number N-1, the first process starts writing word number 0. Here is some pseudocode for Writer process:

int i = 0;
while( true ) {
	while( SharedMemory[i] != 0 ) {
		DoSomethingUseful();	// Or just wait or spin
	}
	SharedMemory[i] = GetDataToPassToAnotherProcess();
	i = (i+1) mod N;
}

The second process (Reader) is reading words from shared memory starting from word number 0. When this process reads a zero-value word from shared memory, it waits, and then reads data again and again until it reads a non-zero word. This is a signal that new data has arrived. After reading a non-zero word, the Reader process writes a zero-valued word in its place. Then it processes the most recently read non-zero word and moves to the next word. After reading word number N-1, the process starts reading word number 0. Here is some pseudo code for Reader process:

int i = 0;
while( true ) {
	word theWord;
	while( (theWord = SharedMemory[i]) == 0 ) {
		DoSomethingUseful();	// Or just wait or spin
	}
	SharedMemory[i] = 0;
	ProcessDataReceivedFromTheFirstProcess(theWord);
	i = (i+1) mod N;
}

In other words, processes are sending messages to each other that are one processor word long. The first process (Writer) sends non-zero information messages; the second process (Reader) reads them and writes zero-valued messages in their place as confirmation that non-zero messages are read. Since processor words are passed between different processor cache levels and main memory atomically, we can be sure that communication will be consistent.

Figures 1, 2 and 3 explain the algorithm and data migration between different processor caches.

Figure 1: Initial state (cache not considered).

Figure 2: Writer is writing non-zero words (shown in black) into shared memory, and reader is reading non-zero words from shared memory and replacing them with zero-valued words (shown in white). Cache is not considered.

If the processes (or threads) are run on different processors, then the messages are delivered by cache synchronization hardware asynchronously and without any intervention. This can lead to higher performance.

Figure 3: Data migration between different cache memory on different processors. Some words have not been delivered from one cache to another.


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