Написание потокобезопасного модульного счетчика на Java

Относительно проблемы атомарности: я не верю, что сам Counter может обеспечивать поведение, гарантирующее семантику, которую вы подразумеваете.

Я думаю, что у нас есть поток, выполняющий некоторую работу

  A - get some stuff (for example receive a message)
  B - prepare to call Counter
  C - Enter Counter <=== counter code is now in control
  D - Increment
  E - return from Counter <==== just about to leave counter's control
  F - application continues

Посредничество, которое вы ищете, касается упорядочивания идентификаторов «полезной нагрузки», установленного в A.

Например, два потока каждый читают сообщение - один читает X, другой читает Y. Вы хотите убедиться, что X получает первое приращение счетчика, Y получает второе, даже если два потока работают одновременно и могут быть запланированы произвольно для одного или нескольких процессоров.

Следовательно, любое упорядочение должно быть наложено на все шаги A-F и обеспечено некоторым счетчиком параллелизма вне счетчика. Например:

pre-A - Get a lock on Counter (or other lock)
  A - get some stuff (for example receive a message)
  B - prepare to call Counter
  C - Enter Counter <=== counter code is now in control
  D - Increment
  E - return from Counter <==== just about to leave counter's control
  F - application continues
post- F - release lock

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

По вопросу о Списке. Потоковую безопасность следует рассматривать с точки зрения гарантий интерфейса. Абсолютно минимальное требование: список должен быть устойчивым к одновременному доступу из нескольких потоков. Например, мы могли бы представить себе небезопасный список, который может зайти в тупик или оставить список неправильно связанным, так что любая итерация будет зацикливаться навсегда. Следующее требование - мы должны указать поведение при одновременном доступе двух потоков.Случаев много, вот несколько

a). Two threads attempt to add
b). One thread adds item with key "X", another attempts to delete the item with key "X"
C). One thread is iterating while a second thread is adding

При условии, что реализация имеет четко определенное поведение, в каждом случае она потокобезопасна. Интересный вопрос - какое поведение удобно.

Мы можем просто синхронизировать список и, следовательно, легко дать понятное поведение для a и b. Однако за это приходится расплачиваться за счет параллелизма. И я утверждаю, что это не имело никакого значения, так как вам все еще нужно синхронизировать на каком-то более высоком уровне, чтобы получить полезную семантику. Так что у меня была бы спецификация интерфейса, в которой говорилось: «Добавление происходит в любом порядке».

Что касается итерации - это сложная проблема, посмотрите, что обещают коллекции Java: не много!

Эта статья , в которой обсуждаются коллекции Java, может быть интересной.

Я бы сказал, что кроме упаковки все в порядке. Когда два вызова метода фактически одновременны, вы не можете гарантировать, что произойдет раньше.

Код по-прежнему атомарен, потому что, что бы на самом деле ни случилось первым, они вообще не могут мешать друг другу.

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

Если вызов next () имел какой-либо другой побочный эффект - например, он напечатал «Начиная с потока (идентификатор потока)» и , затем вернул следующее значение, тогда оно не было бы атомарным; у вас будет заметная разница в поведении. Как бы то ни было, я думаю, ты в порядке.

Одна вещь, о которой следует подумать относительно упаковки: вы можете сделать счетчик намного дольше перед упаковкой, если вы используете AtomicLong :)

РЕДАКТИРОВАТЬ: Я только что придумал изящный способ чтобы избежать проблемы упаковки во всех реалистичных сценариях:

• Определите какое-нибудь большое число M * 100000 (или что-то еще). Он должен быть достаточно большим, чтобы не попадать в него слишком часто (так как это снизит производительность), но достаточно маленьким, чтобы можно было ожидать, что цикл «исправления», приведенный ниже, будет эффективен до того, как слишком много потоков добавятся к отметке, чтобы вызвать его сворачивать.

• Когда вы получаете значение с помощью getAndIncrement () , проверьте, больше ли оно этого числа. Если это так, войдите в «цикл сокращения», который будет выглядеть примерно так:

   long tmp;
  а ((tmp = tick.get ())> БЕЗОПАСНОЕ_ЗНАЧЕНИЕ))
  {
  long newValue = tmp - SAFETY_VALUE;
  tick.compareAndSet (tmp, newValue);
  }
  

В основном это говорит: «Нам нужно вернуть значение обратно в безопасный диапазон, уменьшив несколько кратных значений модуля» (чтобы это не изменило значение модуля M). Он делает это в плотном цикле, в основном определяя, каким должно быть новое значение, но вносит изменения только в том случае, если ничто другое не изменило значение между ними.

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

Атомарный (насколько я понимаю) относится к тому факту, что промежуточное состояние не наблюдается извне. atomicInteger.incrementAndGet () является атомарным, а return this.intField ++; нет, в том смысле, что в первом случае вы не можете наблюдать состояние, в котором целое число было увеличено , но еще не возвращен.

Что касается безопасности потоков , авторы Java Concurrency in Practice дают одно определение в своей книге:

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

(Мое личное мнение следует)

Теперь, если у нас есть список успешно обновлен двумя элементами добавлено, но второе идет раньше первого, который находится в конце, это эта "нить" safe "?

Если поток1 вошел в набор записей объекта мьютекса (в случае Collections.synchronizedList () - сам список) до потока2, то гарантируется, что first расположен впереди, чем второй в списке после обновления. Это связано с тем, что ключевое слово synchronized использует справедливую блокировку. Тот, кто находится впереди очереди, должен делать что-то первым.Справедливые блокировки могут быть довольно дорогими, и вы также можете иметь несправедливые блокировки в java (с помощью утилит java.util.concurrent). Если бы вы так поступили, то такой гарантии нет.

Однако платформа java не является платформой для вычислений в реальном времени, поэтому вы не можете предсказать, сколько времени требуется для выполнения части кода. Это означает, что если вы хотите, чтобы первый опережал второй , вам необходимо явно обеспечить это в java. Обеспечить это за счет «контроля времени» звонка невозможно.

Итак, что здесь потокобезопасно или небезопасно? Я думаю, это просто зависит от того, что нужно сделать. Если вам просто нужно избежать повреждения списка, и не имеет значения, является ли первый первым или вторым первым в списке, чтобы приложение работало правильно, то просто избегайте повреждения достаточно, чтобы установить потокобезопасность. Если нет, значит, это не так.

Итак, я думаю, что потокобезопасность не может быть определена без конкретной функциональности, которую мы пытаемся достичь.

Знаменитый String.hashCode () не использует какой-либо особый «механизм синхронизации», предусмотренный в java, но он по-прежнему является потокобезопасным, поскольку его можно безопасно использовать в своем собственном приложении. не беспокоясь о синхронизации и т. д.

Известный трюк с String.hashCode ():

int hash = 0;

int hashCode(){
    int hash = this.hash;
    if(hash==0){
        hash = this.hash = calcHash();
    }
    return hash;
 }