在多線程編程中,我們可以找到兩個或多個線程/任務之間數據傳輸同步的不同術語。用於無阻塞多線程同步的無鎖定,無等待和等待自由度算法
當正是我們可以說,一些算法是:
1)Lock-Free
2)Wait-Free
3)Wait-Freedom
我明白了什麼是指無鎖的,但是當我們可以說,一些同步算法是無等待還是等待,自由? 我已經取得了一些代碼(環形緩衝區)爲多線程同步,並使用無鎖的方法,但是:
- 算法預測該程序的最長執行時間。
- 在開始時調用此例程的線程設置唯一引用(在此例程內部)。
- 正在調用相同例程的其他線程檢查此引用,並且它是否設置爲比計算第一個涉及線程的CPU滴答計數(度量時間)。如果那段時間很長時間會中斷當前涉及的線程的工作並且會覆蓋他的工作。
- 由於任務調度程序中斷而未完成作業的線程(放置在最後)如果不屬於他,請檢查參考是否重複該作業。
所以這個算法不是真正的無鎖,但沒有使用內存鎖,其他相關的線程可以等待(或不)一定的時間才能覆蓋重置線程的工作。
新增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
這看起來像一個家庭作業問題。如果是的話,你應該標記它的功課。人們會幫助你,但沒有給你完整的答案,所以你可以爲自己學習一些東西。如果這不是一個家庭作業問題,你應該描述你正在嘗試做什麼以及哪個部分有問題。 – 2009-09-21 08:56:49
謝謝西蒙。我已經記下了更多的細節。 – 2009-09-21 09:45:18
那麼,有什麼問題呢? – Seb 2009-10-24 13:05:20