Channels ▼
RSS

Embedded Systems

Lock-free Interprocess Communication


Algorithm Four (Read-optimized Registry)

A common problem is implementing a "registry" optimized for reads, but allowing updates. A standard implementation would be to use std::map and putting locks (critical sections for Windows) around any modifications or reads to/from this map.

Another implementation inspired by the above lock-free technique combines the standard technique of using mutexes and light pipes described above. The algorithm involves a main copy of registry data (one instance of class Registry) and views (or subscribers) of this registry (many instances of class RegistryView) which have local copies of registry data. (See Figure 5.)

Figure 5: Multiple subscribers to an instance of Registry.

Light pipes (KeyValuePipe instances) are used to send updates from the main copy of data to every local copy asynchronously. Every update is applied to the main copy of data at first and then this update is coded and written to every pipe which eventually leads to the update of every local copy of data.

Every subscriber, before reading from its local copy of data, checks for updates which come from the Registry. If some data is found in the pipe then this data is applied to the local copy and then the read operation is performed from the local updated copy of data.

Since updates are rare, the most common scenario is that no updates are found in the pipe. In this case the check is eventually just one read from the pipe's buffer and positive comparing the result to zero.

The standard technique is used only in two cases:

  1. When a process needs to write data to the registry. Since writes are considered rare events, then using mutexes should not decrease performance much.
  2. When there is a subscriber which reads from the registry more rarely than the registry is updated. This will lead to a situation where the light pipe to this subscriber overflows with data. In this case, a Reset command is written to this pipe as the last command to notify the subscriber that all changes should be ignored and the subscriber must get the main copy of data from the Registry and set it to the local copy. Using mutexes in this case also will not decrease overall performance much.

It should be clearly understood that the above mechanism allows every reader to achieve almost the same speed of reading updated data as the speed of reads from the local copy by introducing some latency between data updates of the main copy and updates of the local copies. It is normal that the local copy is slightly behind the main copy of data for a short period of time. On the other hand, all changes to the local copy are consistent and the sequence of changes is guaranteed to be the same as for the main copy. In many cases, this behaviour is sufficient. Examples could be implementations of different routing tables which are repeatedly read and relatively rarely updated. For them, some latency and asynchrony in data updates do not play a vital role as well, but consistency is important.


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