[erlang-questions] Wait-Free practical algorithms in C?

[Zabrane Mickael]

Hi Michael,

wait-free algorithms are very hard to implement practically (thus hard to find).
A friend of mine tell me that even the Oracle database uses lock-free data structures.
That's why people tend to fallback to lock-free data structures.

Here's the best and only pointer I found on the subject:
http://www.1024cores.net/home/lock-free-algorithms/introduction

Unfortunately, the described  wait-freedom is useless for me as I'm looking for a concrete
example (eg. linked lists, hash tables or anything else).

Regards
Zabrane

On Nov 12, 2011, at 11:47 AM, Michael Truog wrote:

> I think this is just confusion over the terms, see this link:
> http://stackoverflow.com/questions/4211180/examples-illustration-of-wait-free-and-lock-free-algorithms
> 
> I believe that when the top comment says "lock-free/wait-free programs are typically implemented without locks, using low-level     primitives such as CAS instructions." at the end, they are mainly talking about wait-free programs.  I think it makes sense to look at CAS and LL/SC usage in data structures to find examples that can make wait-free programs or algorithms, since all the data structures that wait-free programs or algorithms use should be lock-free.
> 
> On 11/12/2011 12:41 AM, Zabrane Mickael wrote:
>> 
>> Hi Michael,
>> 
>> Thanks for the link. As I said before, lock-free algorithms are
>> pretty simple to find and understand (practically speaking).
>> 
>> But that's not the case for wait-free. There's no technical doc explaining
>> them.
>> 
>> Anyone else, need help?
>> 
>> Regards,
>> Zabrane
>> 
>> On Nov 12, 2011, at 6:17 AM, Michael Truog wrote:
>> 
>>> There is an attempt to get some lockfree algorithms into boost here:
>>> http://tim.klingt.org/git?p=boost_lockfree.git;a=summary
>>> 
>>> I am not sure if the code is usable yet, but there are files for: fifo, ringbuffer, and stack.
>>> 
>>> 
>>> On 11/11/2011 09:05 AM, Zabrane Mickael wrote:
>>>> 
>>>> Hi guys,
>>>> 
>>>> Does anyone know tutorials, tech docs, examples (in C if possible)
>>>> about wait-free algorithms (http://en.wikipedia.org/wiki/Non-blocking_algorithm#Wait-freedom) ?
>>>> 
>>>> After several weeks of research, I found 0 concrete example. Very strange!
>>>> 
>>>> I'm only interested in practical wait-free implementations, not the theory behind nor lock-free algo.
>>>> 
>>>> Thousand thanks  for sharing knowledge/pointers on that subject.
>>>> 
>>>> Regards,
>>>> Zabrane
>>>> 
>>>>   
>>>> _______________________________________________
>>>> erlang-questions mailing list
>>>> erlang-questions@REDACTED
>>>> http://erlang.org/mailman/listinfo/erlang-questions
>>> 
>> 
> 


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20111112/fee77876/attachment.htm>