如何僅通過compare_and_swap實現優先鎖定？

Question

鑑於只有比較和交換，我知道如何實現一個鎖。

然而，如何實現自旋鎖

1）的多個線程可以在其上阻斷，與此同時試圖鎖定 2），然後將螺紋是未封端（以及爲了獲取鎖）他們封鎖了嗎？

這有可能嗎？如果不是，我還需要其他哪些原語？

如果是這樣，我該怎麼做？

謝謝！

Answer 1

您將需要等待線程的列表。您需要以線程安全的方式添加和刪除列表中的項目。您將需要能夠睡眠未能獲取鎖定的線程。當鎖定可用時，您需要能夠喚醒1個線程。在linux中，你可以通過讓線程等待一個信號來完成睡眠和等待。

現在有一種懶惰的方式來做到這一點，你可能不需要關心喚醒線程。這裏是我們的跳過列表的僞代碼。這是我們做什麼來添加一個項目。

cFails = 0 
while (1) { 
    NewState = OldState = State; 
    if (cFails > 3 || OldState.Lock) { 
    sleep(); // not too sophisticated, because they cant be awoken 
    cFails = 0; 
    continue; 
    } 

    Look for item in skiplist 
    return item if we found it 

    // to add the item to the list we need to lock it 

    // ABA lock uses a version number 
    NewState.Lock=1; 
    NewState.nVer++; 
    if (!CAS(&State,OldState, NewState)) { 
    ++cFails; 
    continue; 
    } 

    // if the thread gets preempted right here, the lock is left on, and other threads 
    // spinning would waste their entire time slice. 

    // unlock 
    OldState = NewState; 
    NewState.Lock = 0; 
    NewState.nVer++; 
    CAS(&State, OldState,NewState); 
} 

我們希望跳過列表通常會找到該項目，並且很少需要添加它。即使有很多線程，我們也很少有比賽要添加。我們測試了這種情況，最糟糕的情況是大量的線程在一個列表中添加和搜索數百萬個項目。結果是我們很少看到線程無法獲得鎖定。因此，對於我們來說，預期情況下的高性能的簡單方法很有效。有一件壞事可能發生 - 一個線程被搶先持有鎖。那當cFails> 3捕獲這個並且睡覺等待的線程，所以我們不會浪費他們的時間百萬次無用的旋轉。因此cFails設置得足夠高，以至於它檢測到鎖的所有者未處於活動狀態。