Lock-free, wait-free and wait-freedom for non-blocking multi-threaded synchronization

Question

In multi-threaded programming, we can find different terms for synchronizing data transfer between two or more threads / tasks.

When can we say that some kind of algorithm:

1)Lock-Free 2)Wait-Free 3)Wait-Freedom 

I understand what Lock-free means, but when can we say that some sort of Wait-Free or Wait-Freedom synchronization algorithm? I made a code (ring buffer) for multi-threaded synchronization and uses Lock-Free methods, but:

• The algorithm predicts the maximum execution time for this procedure.
• Thread, which calls this procedure at the start, sets up a unique link (inside this procedure).
• Other threads that call the same procedure check this link, and if it is installed, then count the number of CPU samples (measurement time) of the first thread involved. If this time, you need to interrupt the current operation of the involved thread for a long time and cancels its operation.
• A topic that did not finish the task because it was interrupted from the task scheduler (fit) at the end of the link check, if it does not belong to him, repeat the task again.

Thus, this algorithm is actually not free from blocking, but memory locks are not used, and other involved threads may wait (or not) a certain time before overriding the task of the associated 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 } 

Here you can find RingBuffer : RingBuffer , CAS functions: FockFreePrimitives and test program: RingBufferFlowTest

Answer 1

(I answer this question on the assumption that this is a homework question, if not please provide more detailed information about the problem you are experiencing)

You should start reading the Wikipedia article Non-Blocking Sync . This provides some good background information and some definitions of the terms you mention.

Answer 2

I will work on this, although not formally prepared, and in fact it doesn’t matter if this is homework, as what op sets is the definition of “what algorithm” is for me (since the poster is working on the frame) "no" state ", including executable tuples - exactly what system programming should address each other

• 1) The algorithm predicts the maximum execution time of this procedure.

You must determine the size of the data set, as well as the "O" data structure that is applied to the data set. This may include “degenerative cases” (things that no one planned) that destroy chaos in unnamed moments. Thus, without further details, you choose a good "common cause" approach that has well-known failure modes and will recover without a "weekend breakdown". Robert Sedgwick has the most advanced work in which I can make any progress - the work is very clearly writing the targeted questions that you ask.

2. 2) The topic that calls this procedure at the beginning of a set of unique links, which means that inside this procedure.

Some language barriers are here, but I'm going to guess what you are asking is that the code execution path (sequence of instructions) starts with a "unique" link to the dataset - so a unique link means exactly that - so we just re-read the definition this in the standard dictionary. (not the intention to be commonplace, this is what I see here)

3. 3) Other topics that cause the same routine are checked by this link, and if it is set, than the counter, the count of the number of processors (measurement time) first turned on the stream. If this time consists in a prolonged interruption of the current work of the involved topic and redefines its work.

Reference counting. Well-studied - just keep reading and coding. Work it out. Interruption of expired stream termination is fraught with invisible failure modes. To be true, the implementation of real planning (threads or processes) is performed only on hardware designed to solve this problem. Your post "assembly optimization" works at a level where this can be done. I suggest exploring the "AVL" zero page algorithm. At some point, the processor and the sequence of instructions that carry out the planning, by definition of the problem, should receive an exclusive lock on some value → the trick should not have two threads at all, trying to get two elements to lock without the intervention of another instruction pointer.

This can be tricky, especially when non-programmers have authority over the programming store →, which has led to disaster again and again.

4. 4) A topic that did not finish the work because the scheduler was interrupted from the task (placed) at the end, check the link if it does not belong to him to repeat the work again.

This is the task of the planner.