[gameprogrammer] Re: Single producer consumer

On Thursday 09 February 2006 18:21, Kevin Jenkins wrote:
> We're having a debate at work right now as to if you can write a 
> thread-safe single producer consumer class without critical section 
> locks.  I claim you can, while another programmer claims you cannot.

You most certainly can, and it's been done countless times before. :-)

In fact, you can build on this basic idea and create non-blocking 
multiple-reader and/or multiple-writer constructs of various kinds - 
though you usually don't want to, because at some point it's just 
cleaner and more efficient to use the (hardware specific) OS provided 
mechanisms. (And, this stuff gets tricky very fast, once you go 
beyond single-reader, single-writer.)

"sfifo" is an old one I've written and used (and am still using) in 
various environments including DOS real mode (ISR<->main loop 
communication), RT-Linux/x86 kernel space, Win32, Linux/x86 and Mac 
OS X/PPC;
        http://olofson.net/mixed.html

(However, note that it uses integer indices instead of pointers! More 
on that below.)


> This is what I use:
> 
> http://www.rakkar.org/sourcecode/SingleProducerConsumer.h.txt

(Can't be arsed to analyze it carefully right now, lazy bastard me, 
but anyway: ;-)


> What I do is have two pointers - a write pointer and a read pointer. 
> They cannot cross each other.  Each pointer is only modified by one 
> thread.  Both threads compare these pointers using the == operator.

This should be ok, as long as you're certain that reading and writing 
of pointers are atomic operations.

They usually are - but there are a some weird SMP systems where the 
maximum guaranteed atomic memory access is 3 bytes! (Some OSes 
running on Sparc32 CPUs.) You can't safely use pointers on those, 
except maybe with some alignment tricks to keep the "dynamic" part 
within three bytes. Anything that is at most 3 bytes should be fine 
even there.

There should be a #define atomic_t typedef in atomic.h on POSIX 
compliant platforms. I believe most platforms has something like that 
somewhere - or you'll just have to find out some other way and deal 
with it explicitly. (If you're into portable code, that is. If not, 
all you really have to know is what's safe on your target platform.)


> There are a few articles on google claiming correctly you cannot use
> a single shared pointer or index where both threads modify that
> variable, but none use my approach where I have two variables and
> each is only updated by its own thread.

Strange. Google is not with you today, apparently. ;-)

I have seen plenty of CS papers and other info (and code) on this 
subject in various places, though I don't have any direct links 
handy. Try "lock free fifo" or something.


//David Olofson - Programmer, Composer, Open Source Advocate

.-------  http://olofson.net - Games, SDL examples  -------.
|        http://zeespace.net - 2.5D rendering engine       |
|       http://audiality.org - Music/audio engine          |
|     http://eel.olofson.net - Real time scripting         |
'--  http://www.reologica.se - Rheology instrumentation  --'


---------------------
To unsubscribe go to http://gameprogrammer.com/mailinglist.html

Other related posts: