<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Hi Michael,<div><br></div><div><b>wait-free</b> algorithms are very hard to implement practically (thus hard to find).</div><div>A friend of mine tell me that even the Oracle database uses lock-free data structures.</div><div><div>That's why people tend to fallback to <b>lock-free</b> data structures.</div></div><div><br></div><div>Here's the best and only pointer I found on the subject:</div><div><a href="http://www.1024cores.net/home/lock-free-algorithms/introduction">http://www.1024cores.net/home/lock-free-algorithms/introduction</a></div><div><br></div><div>Unfortunately, the described <b>wait-freedom</b> is useless for me as I'm looking for a concrete</div><div>example (eg. linked lists, hash tables or anything else).</div><div><br></div><div>Regards</div><div>Zabrane</div><div><br></div><div><div><div>On Nov 12, 2011, at 11:47 AM, Michael Truog wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">
<meta content="text/html; charset=ISO-8859-1" http-equiv="Content-Type">
<div bgcolor="#ffffff" text="#000000">
I think this is just confusion over the terms, see this link:<br>
<a class="moz-txt-link-freetext" href="http://stackoverflow.com/questions/4211180/examples-illustration-of-wait-free-and-lock-free-algorithms">http://stackoverflow.com/questions/4211180/examples-illustration-of-wait-free-and-lock-free-algorithms</a><br>
<br>
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.<br>
<br>
On 11/12/2011 12:41 AM, Zabrane Mickael wrote:
<blockquote cite="mid:717196E6-348D-4696-9AC6-07836BF046BD@gmail.com" type="cite">
<meta http-equiv="Context-Type" content="text/html;
charset=us-ascii">
Hi Michael,
<div><br>
</div>
<div>Thanks for the link. As I said before, <b>lock-free</b> algorithms
are</div>
<div>pretty simple to find and understand (practically speaking).</div>
<div><br>
</div>
<div>But that's not the case for <b>wait-free</b>. There's no
technical doc explaining</div>
<div>them.</div>
<div><br>
</div>
<div>Anyone else, need help?</div>
<div><br>
</div>
<div>
<div><span>
<div>Regards,</div>
<div>Zabrane</div>
<div><br>
</div>
</span></div>
<div>
<div>On Nov 12, 2011, at 6:17 AM, Michael Truog wrote:</div>
<br>
<blockquote type="cite">
<div> There is an attempt to get some lockfree algorithms
into boost here:<br>
<a moz-do-not-send="true" href="http://tim.klingt.org/git?p=boost_lockfree.git;a=summary">http://tim.klingt.org/git?p=boost_lockfree.git;a=summary</a><br>
<br>
I am not sure if the code is usable yet, but there are
files for: fifo, ringbuffer, and stack.<br>
<br>
<br>
On 11/11/2011 09:05 AM, Zabrane Mickael wrote:
<blockquote cite="mid:E877C97E-E5F5-48FD-9E55-509552782118@gmail.com" type="cite"> Hi guys,
<div><br>
</div>
<div>Does anyone know tutorials, tech docs, examples (in
C if possible)</div>
<div>about <b>wait-free algorithms</b> (<a moz-do-not-send="true" href="http://en.wikipedia.org/wiki/Non-blocking_algorithm#Wait-freedom">http://en.wikipedia.org/wiki/Non-blocking_algorithm#Wait-freedom</a>) ?</div>
<div><br>
</div>
<div>After several weeks of research, I found 0 concrete
example. Very strange!</div>
<div><br>
</div>
<div>I'm only interested in <b>practical</b> <b>wait-free
implementations</b>, not the theory behind nor <b>lock-free</b>
algo.</div>
<div><br>
</div>
<div>Thousand thanks for sharing knowledge/pointers on
that subject.</div>
<div><br>
</div>
<div>
<div>
<div>Regards,</div>
<div>Zabrane</div>
</div>
<br>
</div>
<pre>
_______________________________________________
erlang-questions mailing list
<a moz-do-not-send="true" href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a>
<a moz-do-not-send="true" href="http://erlang.org/mailman/listinfo/erlang-questions">http://erlang.org/mailman/listinfo/erlang-questions</a>
</pre>
</blockquote>
<br>
</div>
</blockquote>
</div>
<br>
</div>
</blockquote>
<br>
</div>
</blockquote></div><br><div>
<div><br></div></div></div></body></html>