[fpc-devel] LockFree Queue algorithm

[Florian Klaempfl]

DarekM schrieb:
> Martin Friebe pisze:
>> You will need to test it, but the following may also work
>>
>> procedure tFlQueue.push(const tm : tNodeQueue);
>> var
>>  newTemp,
>>  lastTail,
>>  newTail : integer;
>> begin
>>  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.
>>    
>> interlockedCompareExchange(pointer(temp),pointer(newTemp-fsize),pointer(newTemp));
>>
>>     newTemp := temp;
>>  end;
> newTemp:=interlockedIncrement(temp) mod fsize; // make sure we are
> always in range
>>  lastTail:=newTemp-1;
>>  if lastTail < 0 then lastTail := fsize -1;
>>  setObject(lastTail,tm); // you can remove the "mod" in setobject
>>  repeat
>>   
>> pointer(newTail):=interlockedCompareExchange(pointer(tail),pointer(newTemp),pointer(lastTail));
>>
>>  until (newTail=lastTail);
>> end;
>>
> It seems ok, but then we have 2 IF more.

An if is unimportant, more important is the number of locked operations,
especially on multi core systems they might eat hundreds of clock cycles.