Lock-Free, Wait-Free and Wait-freedom algorithms for non-blocking multi-thread synchronization.
- by GJ
In multi thread programming we can find different terms for data transfer synchronization between two or more threads/tasks.
When exactly we can say that some algorithem is:
1)Lock-Free
2)Wait-Free
3)Wait-Freedom
I understand what means Lock-free but when we can say that some synchronization algorithm is Wait-Free or Wait-Freedom?
I have made some code (ring buffer) for multi-thread synchronization and it use Lock-Free methods but:
1) Algorithm predicts maximum execution time of this routine.
2) Therad which call this routine at beginning set unique reference, what mean that is inside of this routine.
3) Other threads which are calling the same routine check this reference and if is set than count the CPU tick count (measure time) of first involved thread. If that time is to long interrupt the current work of involved thread and overrides him job.
4) Thread which not finished job because was interrupted from task scheduler (is reposed) at the end check the reference if not belongs to him repeat the job again.
So this algorithm is not really Lock-free but there is no memory lock in use, and other involved threads can wait (or not) certain time before overide the job of reposed thread.
Added RingBuffer.InsertLeft function:
function TgjRingBuffer.InsertLeft(const link: pointer): integer;
var
AtStartReference: cardinal;
CPUTimeStamp : int64;
CurrentLeft : pointer;
CurrentReference: cardinal;
NewLeft : PReferencedPtr;
Reference : cardinal;
label
TryAgain;
begin
Reference := GetThreadId + 1; //Reference.bit0 := 1
with rbRingBuffer^ do begin
TryAgain:
//Set Left.Reference with respect to all other cores :)
CPUTimeStamp := GetCPUTimeStamp + LoopTicks;
AtStartReference := Left.Reference OR 1; //Reference.bit0 := 1
repeat
CurrentReference := Left.Reference;
until (CurrentReference AND 1 = 0)or (GetCPUTimeStamp - CPUTimeStamp > 0);
//No threads present in ring buffer or current thread timeout
if ((CurrentReference AND 1 <> 0) and (AtStartReference <> CurrentReference)) or
not CAS32(CurrentReference, Reference, Left.Reference) then
goto TryAgain;
//Calculate RingBuffer NewLeft address
CurrentLeft := Left.Link;
NewLeft := pointer(cardinal(CurrentLeft) - SizeOf(TReferencedPtr));
if cardinal(NewLeft) < cardinal(@Buffer) then
NewLeft := EndBuffer;
//Calcolate distance
result := integer(Right.Link) - Integer(NewLeft);
//Check buffer full
if result = 0 then //Clear Reference if task still own reference
if CAS32(Reference, 0, Left.Reference) then
Exit else
goto TryAgain;
//Set NewLeft.Reference
NewLeft^.Reference := Reference;
SFence;
//Try to set link and try to exchange NewLeft and clear Reference if task own reference
if (Reference <> Left.Reference) or
not CAS64(NewLeft^.Link, Reference, link, Reference, NewLeft^) or
not CAS64(CurrentLeft, Reference, NewLeft, 0, Left) then
goto TryAgain;
//Calcolate result
if result < 0 then
result := Length - integer(cardinal(not Result) div SizeOf(TReferencedPtr)) else
result := cardinal(result) div SizeOf(TReferencedPtr);
end; //with
end; { TgjRingBuffer.InsertLeft }
RingBuffer unit you can find here: RingBuffer, CAS functions: FockFreePrimitives, and test program: RingBufferFlowTest
Thanks in advance, GJ
