用于无阻塞多线程同步的无锁定，无等待和等待自由度算法

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的维基百科文章。这提供了一些很好的背景信息和您提到的术语的一些定义。

Answer 2

我要去做这件事，虽然没有经过正式的训练，并且真的不关心它是否是家庭作业，因为正如我所要求的那样，确定“对我来说什么算法”（作为海报框架工作）是“不”等待状态”规划涉及执行的元组 - 正是这种东西系统编程必须解决除其他外

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

必须确定数据集大小以及应用于数据集的数据结构的“O”。这可能涉及在未预料到的时刻破坏浩劫的“堕落案件”（一个没有计划的事情）。因此，如果没有进一步的细节，人们会选择一种很好的“一般情况下”的方法，该方法已知失效模式，并且在没有“周末损毁”的情况下恢复。Robert Sedgewick拥有我能够取得进展的最先进的工作 - 工作非常清晰书面处理你问的那类问题。

2）螺纹，其在 调用这个例程开始设置唯一的参考，什么 意味着是该例程的内部。

此间有语言障碍，但我要猜你问的是一个代码执行路径（指令序列）与“独特”的“参考”给它的数据集开始 - 因此，唯一的参考这意味着 - 所以我们只是重新阅读标准字典中的定义。 （无意图是老生常谈，这正是我在这里看到的）

3）呼吁 相同例行检查这个 参考，如果设定比count 其他线程首先涉及线程的CPU滴答计数（测量时间）为 。如果当时 是要中断当前的 涉及线程的工作，并且 会覆盖他的工作。

引用计数。好好研究 - 只要继续阅读和编码。解决它。中断过期的线程完成充满了看不见的失败模式。要做到真实，做（线程或进程的）实际调度只能在适合该任务的硬件中正确执行。你的“装配优化”的帖子在可以完成这个工作的级别上工作。我建议研究“AVL”零页算法。在某个时刻，处理器和执行调度的指令序列将 - 根据问题的定义 - 需要获得对某个值的独占锁定 - >通常的诀窍不是让两个线程试图获得两个项目来锁定没有来自另一个指令指针的干扰。

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

4）因为从任务 调度器（被寄托）在端 检查中断的参考，如果不属于 他再次重复执行该作业，其未完成作业 螺纹。

这是调度程序的任务。