用於無阻塞多線程同步的無鎖定，無等待和等待自由度算法

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）因爲從任務 調度器（被寄託）在端 檢查中斷的參考，如果不屬於 他再次重複執行該作業，其未完成作業 螺紋。

這是調度程序的任務。