4

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

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

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

4

2 回答 2

1

我会努力解决这个问题，虽然没有经过正式培训并且真的不在乎它是否是作业，因为操作要求的是确定“什么算法”对我来说（作为海报框架工作）是“无等待状态”编程涉及执行元组 - 正是系统编程必须解决的那种事情

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

必须确定数据集大小以及应用于数据集的数据结构的“O”。这可能涉及在意想不到的时刻造成严重破坏的“退化案例”（人们没有计划的事情）。因此，在没有更多细节的情况下，人们会选择一种好的“一般情况”方法，该方法已知故障模式，并且不会“破坏周末”而恢复罗伯特塞奇威克的工作是我能够取得任何进展的最先进的工作 - 工作非常清楚书面解决您提出的问题。

  1. 2）一开始调用该例程的线程设置唯一引用，即在该例程内部是什么意思。

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

  1. 3) 调用同一例程的其他线程检查此引用，如果设置为计数第一个涉及的线程的 CPU 滴答计数（测量时间）。如果那个时间是长时间中断所涉及线程的当前工作并覆盖他的工作。

引用计数。好好研究 - 继续阅读和编码。解决它。中断一个过期的线程完成充满了看不见的失败模式。说实话，真正的调度（线程或进程）只有在旨在适应该任务的硬件中才能正确完成。您的“装配优化”帖子的工作水平可以做到这一点。我建议研究“AVL”零页算法。在某些时候，处理器和执行调度的指令序列将 - 根据问题的定义 - 需要获得对某个值的排他锁定 -> 通常的技巧是不要让两个线程尝试获得两个要锁定的项目在不受另一个指令指针干扰的情况下。

这可能具有挑战性，尤其是当非程序员对编程商店拥有权限时 -> 这会一次又一次地导致灾难。

  1. 4）由于任务调度程序中断（被重新放置）而未完成工作的线程最后检查引用是否不属于他，再次重复工作。

这是调度程序的任务。

于 2009-10-24T20:56:47.243 回答
1

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

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

于 2009-09-21T09:20:16.710 回答