Andrey,

Thanks a lot for your response, it gives me some confidence! :)
Also, I'll take a good look at that reference.

I found this list because I was looking for a place to pose this
question, but I'm actually quite interested in these types of data
structures since I do a lot of real-time programming. I'll hang
around on the list and see if I can contribute.

cheers,
Steve



On Fri, Sep 26, 2008 at 4:23 AM, Andrey Brito <aembrito@...> wrote:
>
> Hello Stephen,
>
> if this review you've got were right, there wouldn't exist lock-free
> algorithms, as the bases for lock-freedom are compare-and-swap and
> test-and-set. :-)
>
> But on the other hand, using test-and-set (or swap), doesn't guarantee that
> an algorithm is lock-free (e.g., TAS is used to implement locks). I would
> say something like: an algorithm is lock-free when a thread that stops can
> never prevent others to make progress (e.g., because it locked something,
> but did not released the lock).
>
> Anyway, there are a couple of papers from Keir Fraser dealing with
> lock-freedom, I am sure you can find a good formal definition with a
> reference to insert it in your paper.
>
> Good luck with your system,
>
> Andrey
>
>
>
> ----- Mensagem original ----
> De: Stephen Sinclair <radarsat1@...>
> Para: liblf-dev@yahoogroups.com
> Enviadas: Sexta-feira, 26 de Setembro de 2008 5:38:21
> Assunto: [liblf-dev] question on lock-free message passing, is it possible?
>
> 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
>
> ________________________________
> Novos endereços, o Yahoo! que você conhece. Crie um email novo com a sua
> cara @ymail.com ou @rocketmail.com.