[fpc-devel] LockFree Queue algorithm

[DarekM]

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.
And the same should repeat with pop


>
> 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
Because we cant change size of queue in run, we have to make it so big 
that always will be enough.
For me it should be ten time bigger, than observe maximum (1000 its only 
4 kB of ram).

>
>
>
> 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.
Ok, Ive write warning in source


And i've upload new version  of program.


Darek