Hello,

This seemed like an appropriate place for this question.

This is quite random, but I am emailing because I was wondering if I
could get your opinion on a problem I am facing. I have been
developing real-time simulation (VR) software. I don't currently know
any professors who are experts on this issue so I
am looking for an outside opinion. I'll just pose the question and
you can ignore me if you like. :)

This software is multi-threaded, and I'm trying to take advantage of
asynchronous threads as much as possible by running several
simultaneous simulations (one doing graphics, one doing haptics, one
doing physics) and while I'm currently using a slow method of
communication between my threads so as to avoid locking my data
structures (which would force synchroneity), I'm looking to improve it
by taking advantage of shared memory for message passing. Each thread
is considered soft real-time so they cannot block.

My plan is to do this using the test-and-set atomic operation (using
the HP atomic_ops library). I have implemented the basic mechanism.
Without describing everything in detail, basically message slots in a
buffer are marked as in-use or not, as well as empty or non-empty,
using test-and-set. The threads step through the queue looking for
unused slots. The write operation then looks for empty slots and
'allocates' them, using test-and-swap. The read operation marks a
slot as in-use before checking the message, then marking it empty
after acting.

Anyways, I have received some criticism: "the authors claim that
shared memory message-passing implementations using atomic
test-and-set are 'lock-free'. This seems self-contradictory, as the
whole purpose of test-and-set ops are to implement locks efficiently
and robustly."

So, my question is, is this criticism correct? I never claimed that
all message-passing implementations were lock free, only that I was
developing a lock free message passing implementation. But I don't
know if this person knows something I don't, and it's anonymous so I
can't ask them.

I think that I've successfully implemented a message passing system
which is free of locks, taking advantage of the fact that my threads
are free to be asynchronous and so don't need to wait on each other
but can just place messages in the queue. The atomic operations are
simple, but sufficient to ensure that slots are not simultaneously
used by multiple threads. Certainly my code doesn't implement any
spinlocks or use pthread mutexes. Can I honestly say that I have
implemented a lock free implementation, or is there something hidden
in the atomic_ops library that does something contradicting my claim?

Also, do you have any knowledge of other lock-free message passing
implementations, making use of atomic ops or not?

Thanks for any help you can offer. By the way, somewhat more
on-topic, in the code I am talking about the message passing stuff is
being implemented as a separate library and is GPL. It's available
and seems to work okay, but I'll publish the URL when it's more ready.
One issue I've had is that writing unit tests for the code is quite
difficult since I don't know what to check for to see if any errors
occurred. (Other than a segfault of course.)


Steve