非阻塞多线程同步的无锁、无等待和等待自由算法

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

(我回答这个问题的前提是，这是一个家庭作业问题，如果不是，请提供更多有关问题的细节)

你应该开始阅读维基百科关于非阻塞同步的文章。这提供了一些良好的背景信息和您提到的术语的一些定义。

Answer 2

我要做这件事，尽管没有经过正式的训练，也不在乎作业是否是作业，因为op问的是确定“什么算法”对我来说是“什么算法”(如海报所描述的那样)是涉及执行元组的“无等待状态”编程--这正是系统编程必须解决的问题--

1. 1)算法预测该程序的最大执行时间。

必须确定数据集的大小以及应用于数据集的数据结构的"O“。这可能涉及“退化的案例”(一个人没有计划的事情)，在意想不到的时刻破坏。因此，如果没有更多的细节，人们会选择一种很好的“一般案例”方法，这种方法已经知道了失败的模式，并将在没有“周末被毁”的情况下恢复，罗伯特·塞奇威克( Robert Sedgewick )的作品是我能够取得任何进展的最先进的作品--该作品写得非常清楚，解决了你提出的问题。

1. 2)线程--在开始时调用这个例程--设置了唯一的引用，这意味着这个例程的内部。

这里有一些语言障碍，但我要猜你要问的是，代码执行路径(指令序列)从对它的数据集的“唯一”“引用”开始--因此，唯一的引用就意味着--所以我们只是在标准字典中重新阅读它的定义。(无意陈腐，这正是我在这里看到的)

1. 3)调用相同例程的其他线程，检查此引用，如果设置超过计数，则检查第一个涉及的线程的CPU刻度计数(度量时间)。如果这段时间是长时间中断当前涉及线程的工作，并重写他的作业。

参考计数。好好研究-继续阅读和编码。算了吧。中断过期的线程完成是充满了看不见的失败模式。老实说，真正的调度(线程或进程)只有在为适应该任务而设计的硬件中才能正确完成。您的“程序集优化”职位的工作水平，这是可以做到的。我建议研究"AVL“零页算法。在某个时刻，执行调度的处理器和指令序列--根据问题的定义--需要对某个值->进行独占锁定--一般情况下，不需要两个线程试图获得两个要锁定的项，而不受另一个指令指针的干扰。

这可能是一种挑战，尤其是当非程序员对导致灾难的编程商店->拥有权威的时候。

1. 4)由于任务调度程序中断而未完成作业的线程，最后检查引用是否属于他，再次重复作业。

这是调度程序的任务。