Как заблокировать свободный Hashtable на самом деле работает

Question

Я прошел через http://preshing.com/20130529/a-lock-free-linear-search/ и https://code.google.com/p/nbds/

Я не могу понять, как любой из этих Hashtable является платой за замком. Я имею в виду, если у нас есть два метода для hashtable getItem и setItem. И это моя функция

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

Теперь эта функция работает в 2-х потоков, теперь, если я не использую блокировку в этой функции значения hashtable.getItem (ключ) может быть увеличена на 2 или 4. I я очень смущен, может кто-то помочь мне в понимании

Answer 1

Когда говорить о параллельных контейнеров, мы обычно подразумеваем, что одну операцию, определенные для этого контейнера, атомная. В вашем случае hashtable.getItem(key) и hashtable.setItem(key, val) являются атома операций. Например. если .getItem() выполняется одновременно с .setItem(), то оно будет возвращать либо новое значение, либо старое значение, но не их сочетание.

Но одновременно контейнер не гарантирует, что последовательность из двух или более своих операций атомная. Если пользователю требуется атомное свойство для последовательности операций, он не должен ожидать этого свойства от реализации контейнера, но реализовать это свойство руками. В вашем случае, если вам нужна функция increment2, которая должна быть атома, вам необходимо реализовать это свойство самостоятельно.

Локальные параллельные контейнеры обычно могут быть легко модифицированы, чтобы сделать некоторую последовательность операций атомарной.

С другой стороны, блокировочные параллельные контейнеры вряд ли могут быть расширены, чтобы последовательность операций была атомарной. Алгоритмы без блокировки очень хрупкие в этом смысле.