The riddle of atomic data transfer from process A to process B

[guy keren]

Omer,

you did not specify the timing constraints you have, so the very basic
thing mechanism is to use a posix semaphore for mutual exclusion access
to this memory.

this will work both on single-core and multi-core systems.

note that disabling interrupts is not possible from user space - so it
is not clear to me if the code of process A and process M works in
kernel space, or in user space.

using wait-free algorithms (which are not really free from waiting) is
relevant only if you're afraid that:

1. one of the processes may crash while it holds the semaphore locked
(though this can be solved, e.g. by using flock on a file instead of a
posix semaphore - if the process crashes, the file handle is closed and
the lock is removed by the kernel - although there are cases in which a
process crashes but gets stuck inside the exit code due to a bug in some
kernel driver it uses - which will result a deadlock).

2. the time of taking and releasing a lock is longer then process A or M
is allowed to block.

3. the measurement needs to be in a unit smaller then the pre-emption
time-slice - in which case any solution that might cause a reschedule is
not acceptable. but then - you said these are real-time processes (i.e.
having real-time priority?) which could mitigate that.

so i say - define your requirements more precisely, if you want to be
able to choose a good solution.

--guy

On Wed, 2011-04-13 at 16:07 +0300, Omer Zak wrote:
> I have a riddle for you.
> 
> Given a system with real time processes.
> 
> One process (process M) monitors some quantity (say, temperature) and
> makes measured values of the quantity available for another process
> (process A).
> Process A retrieves the measured temperature once in a while and takes
> some action accordingly.
> 
> The circumstances are such that it is OK for process A's action to take
> place few seconds after the temperature has reached the corresponding
> threshold value.  However, process A is activated more frequently than
> that.
> 
> It is desirable to allow the system to occasionally skip an invocation
> of process M and/or process A if it is overloaded with other processing
> needs.  So the design should not force process A to be activated after
> each activation of process M or to activate process M before each
> invocation of process A.
> 
> The system has several such processes, so it is desirable to have an
> inter-process mechanism having the absolute minimum overhead for
> unidirectional data transfers from measuring processes (like process M)
> to action taking processes (such as process A).
> 
> One approach is to exploit the fact that information transfer from M to
> A is in one direction only, and that no harm occurs if process A reads
> the same value more than once.  In this case, it is possible to use a
> shared memory area.
> Process M will write to the shared memory area at its pleasure and
> process A will read from it, without coordination with process M.
> 
> There is one problem, however.  If the value in question is multi-byte
> one, then we need to assure that writes and reads to the shared memory
> area are atomic, so that it'll never happen that process A reads a
> partially-modified value.
> 
> If the value being transferred is a single-byte value, then there is no
> problem.  In systems with 32-bit memory subsystems and 32-bit data
> paths, aligned 4-byte word writes are atomic as well.
> 
> However, if one desires to pass, say, an 8-byte value (such as a
> timestamp), then one needs to have some locking mechanism.
> 
> In systems based upon one single-core processor, it is possible to solve
> the problem by turning off interrupts before each write/read to the
> shared memory area, and restoring their previous state afterwards.
> 
> The riddle:
> 1. If the operating system being used is Linux, what other mechanisms
> (besides turning off interrupts) are available to single-processor
> systems to accomplish this?
> 2. If the system has a multi-core processor or several processors, which
> low overhead synchronization method can be used to accomplish this?
> 
> --- Omer
> 
>