The riddle of atomic data transfer from process A to process B (cont'd)

[Omer Zak]

After I posed the riddle, more than a week ago, several people
contributed suggestions and points of view.

- Shachar Shemesh suggested to implement a queue without locks.
- Moish amended it with a suggestion to use a circular queue.
- Baruch Siach suggested to try the userspace RCU library
(http://lttng.org/urcu).
- Ori Berger suggested a scheme utilizing a counter, a shadow value and
a shadow counter.  In a personal e-mail message, he made additional
suggestions (such as having a look into http://www.concurrencykit.org/).
- Guy Keren requested that the riddle be defined more precisely.
- Also Ehud Karni contributed to the discussion.

I found the RCU information to be fascinating.  It validated my gut
feeling that it is possible to utilize special cases of
inter-process/thread information transfer to optimize the communication
method.  Once the communication method is optimized, it is possible to
avoid a lot of process/thread synchronization overhead.

As requested by Guy Keren, I'll restate the riddle.

>>> Riddle restatement <<<

System
------
Given an embedded system with real time processes.  The system may have
multiple processors (or multiple cores in the same processor) and it may
be possible to execute instructions and memory accesses out of order.

Processes
---------
One process (process M - measurement) monitors some quantity (say,
temperature) and makes measured values of the quantity available for
another process (process A - action).
Process A retrieves the measured quantity (such as temperature) once in
a while and takes some action accordingly (such as turning a heater on
or off).

Goal
----
Devise a low-overhead mechanism for synchronizing between processes M
and A to ensure that process A gets only consistent data from process M.
Neither process shall be starved by the synchronization mechanism.

Compromises
-----------
Process M is activated periodically.  However, if the system is loaded,
it may skip some activations of M.  Same - with process A.
It is OK for process A's action to take place some time after the
temperature has reached the threshold value/s for that action.
It is OK for process A to skip some measurements and/or use a slightly
out of date measurement value.  It is also OK for process A to read more
than once a single measurement made by process M.

Therefore, it is not logically necessary to have a queue which stores
all measurements made by process M for making them available, one by
one, to process A.

On the other hand, the data structure describing a measurement is
several bytes long, so memory accesses, needed to update it, would not
be atomic the way a one-byte long value (or 32-bit long value in a
32-bit system) can be updated atomically (all at once).

All real data transfer is in one direction only (from process M to
process A).

Desired tradeoffs
-----------------
The system has several pairs of measurement processes (like process M
above) and action processes (like process A above), hence it is
desirable to make any synchronization as lightweight as possible.

It is also desirable to have an upper bound for the memory consumption
of any queues or lists the implementation needs.

It is not desirable (but harmless) to use memory barriers.

>>> End of riddle restatement <<<

It is probable that the theory, described in
http://en.wikipedia.org/wiki/Concurrent_data_structure, would be
relevant to the riddle.
A paradigm, which could be useful, is described in
http://en.wikipedia.org/wiki/Software_transactional_memory.

--- Omer