[fpc-devel] LockFree Queue algorithm
fpc at mfriebe.de
Sun Jan 27 16:49:54 CET 2008
You will need to test it, but the following may also work
procedure tFlQueue.push(const tm : tNodeQueue);
newTail : integer;
newTemp := temp;
while newTemp >= fsize begin
// if it is true, every thread is going to attempt to fix it, before
doing the increment.
// this means no thread will increase the value
// => one thread will to succeed (since the only reason "temp NE
newTemp" is that temp has been decreased)
// newTemp is bigger than fsize, so the result can not become negative.
newTemp := temp;
newTemp:=interlockedIncrement(temp) mod fsize; // make sure we are
always in range
if lastTail < 0 then lastTail := fsize -1;
setObject(lastTail,tm); // you can remove the "mod" in setobject
The "repeat" at the end does still work. In order to set "tail" to "0"
(newTemp=0) => "tail" must first get "9" (as lastTail will be 9).
Only flaw is, if fsize is close enough to the upper data tpye boundary,
and enough threads do InterLockedInvrement, (after all having
simultaneously passed the repeat at the start), then you can still run
over the boundary.
However this can only happen if you have more threads, than
(upperBoundary - fsize).
So you can specify, that it is save up to this amount of parallel threads
IMHO the unit should have a warning (in the comments) that there it is
the users responsibility *not* to store more elements than fsize. There
is no check, and you will loose data, if you try to do so.
But as I said, no warranty that this will work, I haven't done any
> Martin Friebe pisze:
>> What about a long running (eg daemon) application?
>> If temp/tail hits the upper boundary of Integer?
>> (If I understand it correctly)
>> I don't know if interlockedIncrement gives a boundary error, but if not,
>> it still fails.
>> - With currently integer, it gets a negative value, once crossing
>> 0x7fffffff, and SetObject will attempt to read/write out-of-bounds
>> - Assuming temp/tail being unsigned: it will go from 0xffffffff to 0.
>> "0xffffffff mod fsize" may return a value greater 0, "0x00 mod fsize"
>> will be zero. You make an unexpected jump within the list.
> Thats right.
> But I can avoid this.
> 1. make length of tab equal power of two
> 2. use longword instead of integer
> 3.instead MOD use result:=tab[lp and fmask];
> and fmask:=$F or $FF or $FFF
> Thanks to find bug.
> fpc-devel maillist - fpc-devel at lists.freepascal.org
More information about the fpc-devel