如何鎖定免費哈希表實際工作

Question

我通過http://preshing.com/20130529/a-lock-free-linear-search/ 和https://code.google.com/p/nbds/

去我不明白如何這些哈希表是鎖費。我的意思是如果我們有一個hashtable getItem和setItem兩個方法。這是我的功能

function increment2(key): 
    val = hashtable.getItem(key) + 2 
    hashtable.setItem(val) 

現在，這個功能在2個線程運行，現在如果我不hashtable.getItem（鍵）的這個函數值使用鎖可提高2或4 我很迷茫有人可以幫助我理解

Answer 1

當談及併發容器，我們通常意味着單個操作，此容器定義，是原子。在你的情況下，hashtable.getItem(key)和hashtable.setItem(key, val)是原子操作。例如。如果.getItem()與.setItem()同時執行，那麼它將返回新值或舊值，但不是它們的混合。

但併發容器不garantee，這序列兩個或兩個以上的操作是原子。如果用戶需要操作順序的原子屬性，他不應該從容器的實現期望這個屬性，而是用手來實現這個屬性。在你的情況下，如果你需要increment2函數是原子，你需要自己實現這個屬性。

基於鎖的併發容器通常可以很容易地修改爲，以使某些操作序列爲原子。

另一方面，無鎖併發容器幾乎不能延長使操作序列爲原子。無鎖算法在這種情況下非常脆弱。