multithreading - 用于非阻塞多线程同步的 Lock-Free、Wait-Free 和 Wait-freedom 算法

Question

在多线程编程中，我们可以找到两个或多个线程/任务之间的数据传输同步的不同术语。

什么时候我们可以说某个算法是:

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

我明白无锁是什么意思，但是什么时候我们可以说某些同步算法是无等待或无等待？我已经为多线程同步编写了一些代码(环形缓冲区)，它使用无锁方法，但是:

1. 算法预测该例程的最大执行时间。
2. 在开始时调用此例程的线程设置唯一引用(在此例程内部)。
3. 调用同一例程的其他线程会检查此引用，如果它已设置，则会计算第一个相关线程的 CPU 滴答计数(测量时间)。如果那个时间是长时间中断相关线程的当前工作并覆盖他的工作。
4. 由于任务调度程序中断(被重新安置)而尚未完成作业的线程，最后检查引用(如果不属于他)，然后再次重复作业。

因此，该算法并不是真正的无锁算法，但没有使用内存锁，并且其他涉及的线程可以在覆盖重新调用线程的作业之前等待(或不等待)一定时间。

添加了RingBuffer.InsertLeft函数:

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单元:RingBuffer ，CAS 功能:FockFreePrimitives ，测试程序:RingBufferFlowTest

Answer 1

(我回答这个问题的假设是这是一个家庭作业问题，如果不是，请提供您遇到的问题的更多详细信息)

您应该开始阅读关于 Non-blocking synchronization 的维基百科文章。这提供了一些很好的背景信息以及您提到的术语的一些定义。