Полное выражение об отказе от ответственности: это не настоящая домашняя работа, но я отметил ее как таковую, потому что это скорее упражнение самообучения, а не "работа".
Скажем, я хочу написать простой поточно-безопасный модульный счетчик в Java. То есть, если modulo M равно 3, то счетчик должен проходить через 0, 1, 2, 0, 1, 2, … ad infinitum.
Здесь одна попытка:
import java.util.concurrent.atomic.AtomicInteger;
public class AtomicModularCounter {
private final AtomicInteger tick = new AtomicInteger();
private final int M;
public AtomicModularCounter(int M) {
this.M = M;
}
public int next() {
return modulo(tick.getAndIncrement(), M);
}
private final static int modulo(int v, int M) {
return ((v % M) + M) % M;
}
}
Мой анализ (который может быть неисправен) этого кода заключается в том, что, поскольку он использует AtomicInteger, он вполне потокобезопасен даже без каких-либо явных synchronized метод/блок.
К сожалению, сам "алгоритм" не совсем "работает", потому что когда tick обтекает Integer.MAX_VALUE, next() может возвращать неправильное значение в зависимости от модуля M. То есть:
System.out.println(Integer.MAX_VALUE + 1 == Integer.MIN_VALUE); // true
System.out.println(modulo(Integer.MAX_VALUE, 3)); // 1
System.out.println(modulo(Integer.MIN_VALUE, 3)); // 1
То есть, два вызова next() возвращают 1, 1, когда обложка по модулю равна 3 и tick.
Также может возникнуть проблема с next() получением значений вне порядка, например:
- Thread1 вызывает
next() - Thread2 вызывает
next() - Thread2 завершает
tick.getAndIncrement(), возвращает x - Thread1 завершает
tick.getAndIncrement(), возвращает y = x + 1 (mod M)
Здесь, запрещая описанную проблему обертывания, x и y действительно являются двумя правильными значениями, возвращаемыми для этих двух вызовов next(), но в зависимости от того, как указано поведение счетчика, можно утверждать, что они из заказ. То есть у нас есть (Thread1, y) и (Thread2, x), но, возможно, действительно нужно указать, что (Thread1, x) и (Thread2, y) являются "правильными" поведением.
Таким образом, некоторым определением слов AtomicModularCounter является потокобезопасным, но не фактически атомарным.
Итак, вопросы:
- Правильно ли мой анализ? Если нет, укажите, пожалуйста, какие-либо ошибки.
- Является ли последнее последнее утверждение выше, используя правильную терминологию? Если нет, что такое правильное утверждение?
- Если проблемы, упомянутые выше, реальны, то как бы вы это исправили?
- Можете ли вы исправить это, не используя
synchronized, используя атомарностьAtomicInteger? - Как бы вы пишете его так, что
tickсам управляется диапазоном по модулю и даже не получает возможность обертывания поверхInteger.MAX_VALUE?- Мы можем предположить, что
Mпо крайней мере на порядок меньшеInteger.MAX_VALUE, если необходимо
- Мы можем предположить, что
Приложение
Здесь a List аналог проблемы "не по порядку".
- Thread1 вызывает
add(first) - Thread2 вызывает
add(second)
Теперь, если список обновлен успешно с двумя добавленными элементами, но second предшествует first, который находится в конце, является ли это "потокобезопасным"?
Если это "потокобезопасный", то что это? То есть, если мы укажем, что в вышеприведенном сценарии first всегда должен быть до second, что называется этим свойством concurrency? (Я назвал это "атомарность", но я не уверен, что это правильная терминология).
Для чего это стоит, каково поведение Collections.synchronizedList в отношении этого нестандартного аспекта?
