Re: [GD-General] cross platform 64bit lock free FIFO?

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
  <meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
<br>
<br>
George Warner wrote:
<blockquote cite="midC10F2F07.2E4BD%25g...@ap..." type="cite">
  <pre wrap="">On Wed, 09 Aug 2006 09:26:20 -0700, Jon Watte <a class="moz-txt-link-rfc2396E" href="mailto:hp...@mi...">&lt;hp...@mi...&gt;</a> wrote:
  </pre>
  <blockquote type="cite">
    <pre wrap="">Here is the implementation, an all its simplicity:

// Lock-free FIFO by Jon Watte.
// Size must be power of 2.
    </pre>
  </blockquote>
  <pre wrap=""><!---->
This restriction could be removed by using a modulus operation instead of
the AND. (Probably a safe assumption that this restriction was done as a
compromise to speed (Not necessary on PPC)). At the least I'd add an assert
to verify that Size is a power of 2.
  </pre>
</blockquote>
<br>
Actually, in the case where you've put enough elements through that the
counter wraps, you cannot safely use a modulus. You have to use a power
of two for that case to work. Been there, done that, once burned, ...
:-)<br>
<br>
<blockquote cite="midC10F2F07.2E4BD%25g...@ap..." type="cite">
  <pre wrap="">Other than that this code is really only useful for a single provider &amp;
consumer. There's a race condition between the full/empty tests and the
tail/head increments that wouldn't work with multiple writers/readers.
  </pre>
</blockquote>
<br>
Yes, that's the whole point. If you need multiple readers or multiple
writers, then you need locking unless you have larger-than-machine-word
atomic operations. Luckily, in 95% of the cases where you have a need
for a lock-free FIFO, you have exactly one reader and one writer.<br>
<br>
<blockquote cite="midC10F2F07.2E4BD%25g...@ap..." type="cite">
  <pre wrap="">I'd also add code to optionally block on the failure cases (read-empty &amp;
write-full) and when a thread is blocked signal a wakeup when the failure
case is invalidated (queue goes non-empty when a reader is blocked or queue
goes non-full when a writer is blocked).
  </pre>
</blockquote>
<br>
Then it's not a lock-free FIFO. You might as well go with a standard
FIFO instead, which is a different beast.<br>
<br>
Cheers,<br>
<br>
&nbsp;&nbsp;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; / h+<br>
<br>
</body>
</html>