Re: cross platform 64bit lock free FIFO?
Jon Watte <[email protected]> Mon, 21 Aug 2006 10:29:13 -0700
| Newsgroups | gmane.games.devel.general |
|---|---|
| Message-ID | <[email protected]> |
--===============1942752371== Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit <!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%[email protected]" type="cite"> <pre wrap="">On Wed, 09 Aug 2006 09:26:20 -0700, Jon Watte <a class="moz-txt-link-rfc2396E" href="mailto:[email protected]"><[email protected]></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%[email protected]" type="cite"> <pre wrap="">Other than that this code is really only useful for a single provider & 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%[email protected]" type="cite"> <pre wrap="">I'd also add code to optionally block on the failure cases (read-empty & 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> / h+<br> <br> </body> </html> --===============1942752371== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline ------------------------------------------------------------------------- Using Tomcat but need to do more? Need to support web services, security? Get stuff done quickly with pre-integrated technology to make your job easier Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642 --===============1942752371== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ Gamedevlists-general mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/gamedevlists-general Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=557 --===============1942752371==--