Lock-Free, Wait-Free and Wait-freedom algorithms for non-blocking multi-thread synchronization.

Question

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 algorithm 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

Answer 1

(I'm answering this question based on the assumption that it is a homework question, if it's not please provide some more details of the problem you are having)

You should begin be reading the wikipedia article on Non-blocking synchronization. This provides some good background information and some definitions of the terms you mention.

Answer 2

I'm gonna work on this, though not formally trained and really don't care if it is homework as what op asks is determining "what algorithm" which for me ( as the poster frames the work ) is "no wait state" programming involving execution tuples - exactly the sort of thing that systems programming has to address inter-alia

1. 1) Algorithm predicts maximum execution time of this routine.

One has to determine the dataset size and as well the "O" of the data structure applied to the dataset. That can involve "degenerate cases" ( things one did not plan for ) that wreck havoc at un-anticipated moments. Thus, without further details, one chooses a good "general case" approach that has known failure modes and will recover without a "weekend ruined" Robert Sedgewick has the most advanced work I am able to gain any progress with - the work is very clearly written addressing the sort of questions you ask.

1. 2) Thread which call this routine at beginning set unique reference, what mean that is inside of this routine.

Some language barriers here but I am going to guess what you are asking is that a code execution path ( sequence of instructions ) starts with a "unique" "reference" to it's dataset - thus, a unique reference means exactly that - so we just re-read the definition of that in a standard dictionary. ( no intent to be trite, that's just what I see here )

1. 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.

Reference counting. Well studied - just keep reading and coding. Work it out. Interrupting an overdue thread completion is fraught with unseen failure modes. To be truthful, doing real scheduling ( of threads or process ) is only done correctly in hardware that is designed to accommodate that task. Your "assembly optimization" post works at a level where this can be done. I suggest study of the "AVL" Zero-Page algorithm. At some point, the processor and the sequence of instructions doing the scheduling will - by the definition of the problem - need to obtain exclusive locking on some value -> the trick in general is not to have two threads attempting to obtain two items to lock on without interference from another instruction pointer.

This can be challenging, especially so when non-programmers have authority over the programming shop -> that has led to disaster again and again.

1. 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.

This is the task of the scheduler.