Голодание в неблокирующих подходах - PullRequest
Новая
       4

Голодание в неблокирующих подходах

2 голосов
/ 28 января 2012

Я уже некоторое время читаю о неблокирующих подходах. Вот фрагмент кода для так называемого счетчика без блокировки. 

public class CasCounter {
private SimulatedCAS value;

public int getValue() {
    return value.get();
}

public int increment() {
    int v;
    do {
        v = value.get();
    }
    while (v != value.compareAndSwap(v, v + 1));
    return v + 1;
}

}

Мне просто интересно об этом цикле: 

do {
    v = value.get();
}
while (v != value.compareAndSwap(v, v + 1));

Люди говорят:

Так что он пытается снова и снова, пока все другие потоки, пытающиеся изменить значение, не сделают это. Это блокировка свободна, так как блокировка не используется, но не блокировка свободна, поскольку может потребоваться повторить попытку (что редко) более одного раза (очень редко).

Мой вопрос:

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

Ответы [ 2 ]

2 голосов
/ 29 января 2012

Цикл может быть бесконечным (так как он может вызвать голодание для вашего потока), но вероятность этого события очень мала. Для того, чтобы вы могли голодать, вам нужен какой-то другой поток, преуспевающий в изменении значения, которое вы хотите обновить между чтением и вашим хранилищем, и чтобы это происходило неоднократно.

Можно было бы написать код для запуска голодания, но для реальных программ это вряд ли произойдет.

Сравнение и своп обычно используются, когда вы не думаете, что у вас будут конфликты записи очень часто. Допустим, при обновлении существует 50% -ная вероятность «промаха», тогда 25% -ная вероятность того, что вы пропустите два цикла, и менее 0,1% вероятности того, что ни одно обновление не будет выполнено в 10 циклах. Для примеров из реальной жизни 50% -ый процент пропусков очень высок (в основном, ничего не делая, кроме обновления), и, поскольку процент пропусков уменьшается, скажем, 1%, тогда риск неуспеха в двух попытках составляет всего 0,01% и в пытается 0,0001%.

Использование похоже на следующую проблему

Установите переменную a равной 0, и два потока обновят ее с a = a + 1 миллион раз каждый одновременно. В конце можно получить любой ответ между 1000000 (каждое другое обновление было потеряно из-за перезаписи) и 2000000 (обновление не было перезаписано).

Чем ближе к 2000000, тем выше вероятность того, что использование CAS будет работать, поскольку это означает, что довольно часто CAS будет видеть ожидаемое значение и сможет устанавливать новое значение.

2 голосов
/ 28 января 2012

Редактировать : Я думаю, что теперь у меня есть удовлетворительный ответ. Меня немного смутило «v! = CompareAndSwap». В реальном коде CAS возвращает true, если значение равно сравниваемому выражению. Таким образом, даже если первый поток прерван между get и CAS, второй поток выполнит успешную замену и выйдет из метода, поэтому первый поток сможет выполнить CAS.

Конечно, возможно, что если два потока будут вызывать этот метод бесконечное число раз, один из них вообще не получит возможность запустить CAS, особенно если он имеет более низкий приоритет, но это один из риски несправедливой блокировки (однако вероятность очень низкая). Как я уже сказал, механизм очереди сможет решить эту проблему.

Извините за первоначальные неверные предположения.

...