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

17

Полное оговорка: это не домашняя работа, но я отметил ее как таковую, потому что это скорее упражнение самообучения, а не «работа».

Предположим, я хочу написать простой поточно-безопасный модульный счетчик в 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 / block.

К сожалению, сам «алгоритм» не совсем «работает», потому что, когда tick обертывает Integer.MAX_VALUE , next() может вернуть неправильное значение в зависимости от modulo 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() , получающей внеочередные значения, например:

  1. Thread1 вызывает next()
  2. Thread2 вызывает next()
  3. Thread2 завершает tick.getAndIncrement() , возвращает x
  4. Thread1 завершает tick.getAndIncrement() , возвращает y = x + 1 (mod M)

Здесь, запрещая описанную проблему обертывания, x и y , действительно, являются двумя правильными значениями, возвращаемыми для этих двух вызовов next() , но в зависимости от того, как счетчик поведение указано, можно утверждать, что они не в порядке. То есть мы теперь имеем (Thread1, y) и (Thread2, x) , но, возможно, действительно нужно указать, что (Thread1, x) и (Thread2, y) - это «правильное» поведение.

Таким образом, некоторым определением слов AtomicModularCounter является потокобезопасным , но не фактически atomic .

Итак, вопросы:

  • Правильно ли мой анализ? Если нет, укажите, пожалуйста, какие-либо ошибки.
  • Является ли последнее последнее утверждение выше, используя правильную терминологию? Если нет, что такое правильное утверждение?
  • Если проблемы, упомянутые выше, реальны, то как бы вы это исправили?
  • Можете ли вы исправить это, не используя synchronized , используя атомарность AtomicInteger ?
  • Как бы вы написали его таким образом, что tick сам контролируется диапазоном по модулю и даже не получает возможность обернуть более Integer.MAX_VALUE ?
    • Мы можем предположить, что M по крайней мере на порядок меньше Integer.MAX_VALUE при необходимости

Приложение

Вот аналог List проблемы «не по порядку».

  • Thread1 вызывает add(first)
  • Thread2 вызывает add(second)

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

Если это «потокобезопасный», то что это? То есть, если мы укажем, что в приведенном выше сценарии first всегда должно быть до second , что называется этим свойством параллелизма? (Я назвал это «атомарность», но я не уверен, что это правильная терминология).

Для чего это стоит, каково поведение Collections.synchronizedList в отношении этого нестандартного аспекта?

    
задан polygenelubricants 07.08.2010 в 10:50
источник
  • Интересный вопрос. Это дает мне дежавю;) –  BalusC 08.08.2010 в 16:19

4 ответа

7

Насколько я вижу, вам просто нужен вариант метода getAndIncrement ()

public final int getAndIncrement(int modulo) {
    for (;;) {
        int current = atomicInteger.get();
        int next = (current + 1) % modulo;
        if (atomicInteger.compareAndSet(current, next))
            return current;
    }
}
    
ответ дан Peter Lawrey 07.08.2010 в 18:06
  • Ничего себе, похоже, что это сработает. Ого, могут ли другие люди прокомментировать? Вау. –  polygenelubricants 08.08.2010 в 16:23
  • Что касается комментария, вам нужно остановить wow'ing, и да, это почти так же хорошо, как и получается, если вы хотите избежать блокировки. Для неблокирующей реализации CAS (или эквивалент) является краеугольным камнем, чтобы это произошло. (Если для создания CAS'ов очень просто создать целый объект, то AtomicIntegerFieldUpdater и его друзья - это путь, но только если накладные расходы памяти действительно важны, так как это чудеса загромождают код :)) , –  Dimitris Andreou 09.08.2010 в 19:34
  • Кстати, следует отметить, что это будет ужасно выполняться, если есть много частых авторов. Я знаю, что это не было в целях вашего вопроса, просто сказать, для наших читателей дома. –  Dimitris Andreou 09.08.2010 в 19:38
  • @ Dimtris, хороший вклад, однако, если у вас много частых авторов, у вас есть серьезная проблема, потому что это означает, что у вас много потоков, называющих это, а не ничего полезного с генерируемым числом. –  Peter Lawrey 09.08.2010 в 20:47
  • @Peter, как правило, я согласен, но это может быть полезным комментарием. Например, невообразимо, что кто-то может подумать, что полезно обернуть CHM и сделать, для каждого обновления (которое быстро), пользовательский подсчет какого-то рода в какой-либо другой переменной (s) (скажем, подсчитывает get и puts) , –  Dimitris Andreou 09.08.2010 в 21:36
Показать остальные комментарии
5

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

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

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

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

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

EDIT: Я просто подумал о том, как избежать проблем с упаковкой во всех реалистичных сценариях:

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

    long tmp;
    while ((tmp = tick.get()) > SAFETY_VALUE))
    {
        long newValue = tmp - SAFETY_VALUE;
        tick.compareAndSet(tmp, newValue);
    }
    

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

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

    
ответ дан Jon Skeet 07.08.2010 в 10:59
  • Да, очевидно, AtomicLong считалось, но поскольку это «домашнее задание», я хотел бы извлечь уроки из этого упражнения настолько, насколько я могу, вместо того, чтобы придумывать практическое, но не образовательное «решение»: ) –  polygenelubricants 07.08.2010 в 11:01
  • @polygenelubricants: Отредактировано слегка сумасшедшей схемой. –  Jon Skeet 07.08.2010 в 11:10
  • @ Jon: Ох, поверьте, я мысленно экспериментировал с различными сумасшедшими схемами вроде этого (то, что вы точно назвали «циклом сокращения»). Это и есть начало предположения о том, что модуль по крайней мере на порядок меньше Integer.MAX_VALUE. В конце концов я никогда не мог убедить себя, что они воздушно-воздушные. В этот момент может быть лучше просто использовать явно синхронизированный код и вместо этого работать с volatile int. –  polygenelubricants 07.08.2010 в 11:25
  • @polygenelubricants: Я думаю, что в этом случае (особенно с использованием AtomicLong) было бы абсолютно нормально, в любом случае это даже немного разумно. Даже со многими потоками, когда вы нажмете ограничение безопасности, вам придется иметь новые потоки, которые все еще пытаются просто получить следующее значение достаточно быстро, чтобы заблокировать всех, кто пытается его уменьшить. В основном я был бы достаточно счастлив, чтобы это было безопасно. Если у вас есть много потоков, ваш компьютер все равно взорвется :) –  Jon Skeet 07.08.2010 в 11:43
  • Был недавний вопрос SO о том, сколько времени потребуется для увеличения продолжительности переполнения. Ответ был более чем на всю жизнь, предполагая современное оборудование. –  Stephen C 07.08.2010 в 13:16
Показать остальные комментарии
1

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

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

  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 получает второе, хотя оба потока работают одновременно и могут быть запланированы произвольно через 1 или более процессоров.

Следовательно, любое упорядочение должно быть наложено на все этапы 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, может быть интересной.

    
ответ дан djna 07.08.2010 в 11:06
  • Не могли бы вы обратиться к аналогии List? Я повторю здесь более подробно: если Thread1 вызывает add (first), и до того, как он сможет завершить, Thread2 вызывает add (second), является ли он потокобезопасным, если второй идет до первого, пока оба гарантированно будут успешно добавлены? –  polygenelubricants 07.08.2010 в 11:23
  • Отредактировано для решения этого вопроса. –  djna 07.08.2010 в 11:52
1

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

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

  

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

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

  

Теперь, если у нас есть список   обновляется успешно с двумя элементами   добавлено, но второе - прежде,   который находится в конце, заключается в том, что «поток   безопасный "?

Если thread1 ввел набор записей объекта mutex (в случае Collections.synchronizedList () самого списка) перед thread2, гарантируется, что first позиционируется впереди, чем second в списке после обновления. Это связано с тем, что ключевое слово synchronized использует справедливую блокировку. Тот, кто сидит впереди очереди, сначала начинает делать вещи. Яркие замки могут быть довольно дорогими, и вы также можете иметь несанкционированные блокировки в java (с помощью утилиты java.util.concurrent). Если вы сделаете это, тогда нет такой гарантии.

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

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

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

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

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

int hash = 0;

int hashCode(){
    int hash = this.hash;
    if(hash==0){
        hash = this.hash = calcHash();
    }
    return hash;
 }
    
ответ дан Enno Shioji 07.08.2010 в 11:49