在MCS算法中鎖定

我想爲我的應用程序之一在C++中實現排隊鎖定。我打算通過算法從以下紙張： http://www.google.co.in/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCUQFjAA&url=http%3A%2F%2Fwww.cs.rice.edu%2F~johnmc%2Fpapers%2Ftocs91.pdf&ei=HpRfUKCZFsfWrQfpgIGACQ&usg=AFQjCNF_QamPWhJrq5dSjJjFjO7W3WzJ5Q&sig2=3TU1vo_aAYbM2fmLxeiZ0A 在MCS算法中鎖定

type qnode = record 
next : ^qnode 
locked : Boolean 

type lock = ^qnode 

// parameter I, below, points to a qnode record allocated 
// (in an enclosing scope) in shared memory locally-accessible 
// to the invoking processor 

procedure acquire_lock (L : ^lock, I : ^qnode) 
    I->next := nil 
    predecessor : ^qnode := fetch_and_store (L, I) 
    if predecessor != nil // queue was non-empty 
    I->locked := true 
    predecessor->next := I ---A 
    repeat while I->locked // spin ---C 

procedure release_lock (L : ^lock, I: ^qnode) 
if I->next = nil // no known successor 
    if compare_and_swap (L, I, nil) // compare_and_swap returns true iff it swapped 
    return 

    repeat while I->next = nil // spin --B 
I->next->locked := false ---D

甲& B被存取（predecessor->下一個I- &>下一個），並還包含c & d（鎖定變量）相同的變量，但他們在訪問前沒有被鎖定。我在這裏錯過了什麼嗎？

來源

2012-09-23 KodeWarrior

確實，這些併發訪問可以競爭，但算法被設計爲容忍這種情況。

B處的旋轉實際上是爲了防止與A的比賽。在D處，我們需要I->next爲非零。 I->next（在這裏稱爲predecessor->next）被A設置爲非零。正如你注意到的那樣，這可能會競爭，所以在B有一個旋轉循環等待另一個線程將I->next設置爲有效的東西。

讓我們來看看C & D. repeat while I->locked這一行是鎖的實際「旋轉」部分;如果嘗試獲取鎖的線程必須等待另一個線程釋放它，它將在此循環中旋轉。如果釋放鎖的線程在獲取線程到達repeat while I->locked之前將I->next->locked設置爲false，則循環將永遠不會啓動。

來源

2013-05-03 16:06:07

在MCS算法中鎖定

回答

相關問題