Re: Totally Safe lock-free FIFO for arbitrary-sized items.

Hmm, I have one more question regarding your implementation: You put  
barrier() after the increments, because otherwise get() might think that  
the FIFO is empty, when it's not, and put() might think that the FIFO is  
full, when it's not. I believe that putting in these memory barriers won't  
solve the problem, because what if the threads get switched after the  
increment, but before executing the barrier()?? Even using  
interlocked_increment won't help, because only one thread is changing the  
value, and again, what if the thread switch occurs after the store and  
before the increment?

Of course, none of this really matters, because it should not result in  
corrupt data in any way, I just think that those barriers are unnecessary.



Andras

On Wed, 09 Aug 2006 14:10:50 -0600, Jon Watte <[email protected]>  
wrote:

>
> And, to confuse things even more, if you have strict aliasing options
> turned on, the compiler may even decide to re-order the stores. Thus,
> the Totally Safe lock-free FIFO for arbitrary-sized items looks like  
> this:
>
> /* Lock-free FIFO by Jon Watte.
>  * Stored can be a type of any size.
>  * Size must be power of 2.
>  * This FIFO is correct on systems with strongly consistent
>  * caches (such as Intel). It may require write barriers on
>  * systems with weakly consistent caches. Insert such a
>  * barrier in the inline function barrier() if that's the case.
>  */
> template<typename Stored, size_t Size>
> class LockFreeFifo {
>   public:
>     LockFreeFifo() { head = 0; tail = 0; }
>
>     /* Get an item from the FIFO.
>      * Return true if an item was there and was copied,
>      * false if the FIFO is empty.
>      */
>     bool get(Stored & out) {
>       if (head - tail > 0) {
>         out = fifo_[tail & (Size-1)];
>         ++tail;
>         barrier(); /* make sure writer knows FIFO isn't full */
>         return true;
>       }
>       return false;
>     }
>
>     /* Put an item into the FIFO.
>      * Return true if it fit and was copied,
>      * false if the FIFO is full.
>      */
>     bool put(Stored & in) {
>       if (head - tail < Size) {
>         fifo_[head & (Size-1)] = in;
>         barrier(); /* make sure FIFO is updated before head */
>         ++head;
>         barrier(); /* make sure reader can find the new item */
>         return true;
>       }
>       return false;
>     }
>
>   private:
>
>     inline void barrier() {
>       /* If your platform has a weakly consistent cache (i e,
>        * not Intel) then you need to insert a barrier instruction
>        * (such as EIEIO on PPC) here.
>        */
> #warning "Use the intrinsic specific to your platform, if needed."
>     }
>
>     /* Make these volatile, to avoid strict type aliasing analysis to  
> allow
>      * the compiler to re-order stores.
>      */
>     volatile unsigned int head;
>     volatile unsigned int tail;
>     volatile Stored fifo_[Size];
> };
>
>
>
> Jon Watte wrote:
>> Note that the problem is with weakly _consistent_ cahces, not just
>> weakly ordered -- i e, if cache line A can flush before cache line B, it
>> doesn't matter, as long as the mutliple CPUs implement cache snooping to
>> stay consistent (which is the case on Intel). On PPC, you may end up
>> wanting to use the cache line reservations with a spin loop.

-------------------------------------------------------------------------
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
_______________________________________________
Gamedevlists-general mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/gamedevlists-general
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=557