Lock-free double ended queue (bounded)

Just a small snippet – as a title says - lock-free double ended, bounded queue in C++. Original version can be be found in Herlihy’s book, but it’s in Java. It’s not very general, it has been created specifically to be used in my work-stealing thread pool. Basically, each thread adds tasks to the bottom of it’s own pool and tries to steal from top of other threads’ pools when low on tasks. I went with bounded version, mainly because it’s much simpler and more effective. Cool thing is, that slower interlocked operations are only executed when there’s a danger of “collision” between thieves and queue owner, in majority of cases, it’ll take fast path. One thing I don’t like is that multiple threads touch both bottom and top indices, so it’s hard to avoid false sharing . Thanks to nice folks at comp.programming.threads for help/suggestions. I tested it with Relacy Race Detector and it seems OK, but with pre-C++0X it’s always iffy, so don’t hesitate to report problems. (CAS2 is 64-bit CAS version mentioned here, in case you wonder). Queue code download.

Old comments

John W. Ratcliff 2009-01-05 20:35:42

So…this code doesn’t build by itself. It has dependencies on ‘core/Atomic.h’ and ‘thread/CAS.h’
Where are the dependencies located?
Thanks,
John

John W. Ratcliff 2009-01-05 20:42:08

Same question as before, where is the source for the dependencies? Do you have a small demo app for completeness?
Thanks,
John
FYI, my small console demo app is located at: http://www.amillionpixels.us/JobSwarm.zip and a full featured graphics app at http://www.amillionpixels.us/ThreadFrac_1.0.exe

admin 2009-01-06 20:56:12

Source can be found in my recent package for Mandelbrot (msinilo.pl/download/rdethread.zip). I plan to release sample app, but it’ll take some time to clean it up, I’m in rather frantic period right now.

double ended queue 2010-03-27 06:35:55

[…] ended queue Lock free double ended queue | .mischief.mayhem.soap.Source code for lock-free double ended queue in C++. … Just a small snippet as a title says […]