Могу ли я в Java полагаться на то, что присвоение ссылки является атомарным, для реализации копирования при записи?

Вместо того, чтобы пытаться развернуть собственное решение, почему бы не использовать ConcurrentHashMap в качестве вашего набора и просто установить все значения на какое-то стандартное значение? (Подойдет константа типа Boolean.TRUE.)

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

Обновление. Вир предложил использовать Collections.newSetFromMap, чтобы превратить ConcurrentHashMap в Set. Поскольку метод принимает Map<E,Boolean>, я предполагаю, что он делает то же самое с установкой всех значений Boolean.TRUE за кулисами.

Обновление: обращение к примеру с плакатом

Вероятно, именно этим я и займусь, но мне все еще любопытно, как мое минималистское решение может потерпеть неудачу. - Майлз Хэмпсон

Ваше минималистичное решение отлично подойдет, если немного подправить его. Меня беспокоит, что, хотя сейчас он минимален, в будущем он может стать более сложным. Трудно вспомнить все условия, которые вы принимаете при создании чего-то поточно-ориентированного, особенно если вы возвращаетесь к коду через несколько недель / месяцев / лет, чтобы внести, казалось бы, незначительную настройку. Если ConcurrentHashMap делает все, что вам нужно, с достаточной производительностью, почему бы вместо этого не использовать его? Все неприятные детали параллелизма скрыты, и даже через 6 месяцев вам будет сложно все испортить!

Вам понадобится хотя бы одна настройка, прежде чем ваше текущее решение заработает. Как уже указывалось, вам, вероятно, следует добавить модификатор volatile к объявлению global. Не знаю, есть ли у вас опыт работы с C / C ++, но я был очень удивлен, когда узнал, что семантика volatile в Java на самом деле намного сложнее, чем в C < / а>. Если вы планируете много заниматься параллельным программированием на Java, было бы неплохо ознакомиться с основами модель памяти Java. Если вы не сделаете ссылку на global ссылкой на volatile, тогда возможно, что ни один поток никогда не увидит никаких изменений значения global, пока они не попытаются обновить его, после чего ввод блока synchronized очистит локальный кеш и получит обновленное эталонное значение.

Однако даже после добавления volatile остается огромная проблема. Вот сценарий проблемы с двумя потоками:

1. Начнем с пустого набора, или global={}. Потоки A и B имеют это значение в своей локальной кэшированной памяти потока.
2. Поток A получает блокировку synchronized на global и начинает обновление, создавая копию global и добавляя новый ключ в набор.
3. Пока поток A все еще находится внутри блока synchronized, поток B считывает свое локальное значение global в стек и пытается войти в блок synchronized. Поскольку поток A в настоящее время находится внутри блоков монитора, поток B.
4. Поток A завершает обновление, устанавливая ссылку и выходя из монитора, в результате чего получается global={1}.
5. Поток B теперь может войти в монитор и сделать копию набора global={1}.
6. Поток A решает сделать другое обновление, читает свою локальную global ссылку и пытается войти в блок synchronized. Поскольку поток B в настоящее время удерживает блокировку {}, блокировка {1} отсутствует и поток A успешно входит в монитор!
7. Тема A также делает копию {1} для обновления.

Теперь потоки A и B находятся внутри блока synchronized, и у них есть идентичные копии набора global={1}. Это означает, что одно из их обновлений будет потеряно! Эта ситуация вызвана тем фактом, что вы синхронизируете объект, хранящийся в ссылке, которую вы обновляете в своем блоке synchronized. Вы всегда должны быть очень осторожны с тем, какие объекты вы используете для синхронизации. Вы можете решить эту проблему, добавив новую переменную, которая будет действовать как блокировка:

private volatile Collection global = new HashSet(); // start threading after this
private final Object globalLock = new Object(); // final reference used for synchronization

void allUpdatesGoThroughHere(Object exampleOperand) {
  // My hypothesis is that this prevents operations in the block being re-ordered
  synchronized(globalLock) {
    Collection copy = new HashSet(global);
    copy.remove(exampleOperand);
    // Given my hypothesis, we should have a fully constructed object here. So a 
    // reader will either get the old or the new Collection, but never an 
    // inconsistent one.
    global = copy;    
  }
}

Эта ошибка была настолько коварной, что ни один из других ответов еще не исправил ее. Именно такие сумасшедшие детали параллелизма заставляют меня рекомендовать использовать что-то из уже отлаженной библиотеки java.util.concurrent вместо того, чтобы пытаться собрать что-то самостоятельно. Я думаю, что приведенное выше решение сработает, но как легко было бы снова облажаться? Это было бы намного проще:

private final Set<Object> global = Collections.newSetFromMap(new ConcurrentHashMap<Object,Boolean>());

Поскольку ссылка - final, вам не нужно беспокоиться о потоках, использующих устаревшие ссылки, а поскольку ConcurrentHashMap обрабатывает все неприятные проблемы с моделью памяти внутренне, вам не нужно беспокоиться обо всех неприятных деталях мониторов и барьеров памяти!

Согласно соответствующему руководству по Java,

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

• Чтение и запись являются атомарными для ссылочных переменных и для большинства примитивных переменных (всех типов, кроме long и double).
• Чтение и запись являются атомарными для всех переменных, объявленных volatile (включая long и double переменные).

Это подтверждается Разделом §17.7 Закона Спецификация языка Java

Запись и чтение ссылок всегда атомарны, независимо от того, реализованы ли они как 32-битные или 64-битные значения.

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

Если вы используете неявную блокировку через synchronized при любом доступе к global, тогда вы можете добиться здесь некоторой согласованности памяти ... но, возможно, лучше использовать альтернативный подход.

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

private volatile Collection global = Collections.unmodifiableSet(new HashSet());

... это или с помощью AtomicReference,

private AtomicReference<Collection> global = new AtomicReference<>(Collections.unmodifiableSet(new HashSet()));

Затем вы также можете использовать Collections.unmodifiableSet для ваших измененных копий.

// ... All reads are done through a reference copy like:
// Collection copy = global;
// for (Object elm: copy) {...
// so the global reference being updated half way through should have no impact

Вы должны знать, что создание копии здесь излишне, поскольку внутри for (Object elm : global) создается Iterator следующим образом ...

final Iterator it = global.iterator();
while (it.hasNext()) {
  Object elm = it.next();
}

Следовательно, невозможно переключиться на совершенно другое значение для global во время чтения.

Помимо всего этого, я согласен с мнение, выраженное DaoWen ... есть ли причина, по которой вы размещаете здесь свою собственную структуру данных, когда может быть альтернатива, доступная в java.util.concurrent? Я подумал, что, возможно, вы имеете дело со старой Java, поскольку вы используете необработанные типы, но спросить не повредит.

Семантику коллекции копирования при записи можно найти в CopyOnWriteArrayList или его двоюродный брат CopyOnWriteArraySet (который реализует Set с использованием первого).

Также предложенный DaoWen, рассматривали ли вы возможность использования _ 25_? Они гарантируют, что использование цикла for, как вы это сделали в своем примере, будет согласованным.

Точно так же итераторы и перечисления возвращают элементы, отражающие состояние хэш-таблицы в какой-то момент во время или после создания итератора / перечисления.

Внутри Iterator используется для улучшения for по сравнению с Iterable.

Вы можете создать Set из этого, используя _ 31_ следующим образом:

final Set<E> safeSet = Collections.newSetFromMap(new ConcurrentHashMap<E, Boolean>());
...
/* guaranteed to reflect the state of the set at read-time */
for (final E elem : safeSet) {
  ...
}

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

ConcurrentSkipListSet может помочь вам здесь. Это может избавить вас от всех ваших проблем с многопоточностью.

Однако он медленнее, чем HashSet (обычно - HashSets и SkipLists / Trees трудно сравнивать). Если вы делаете много чтений для каждой записи, то, что у вас есть, будет быстрее. Что еще более важно, если вы обновляете более одной записи за раз, ваши чтения могут увидеть противоречивые результаты. Если вы ожидаете, что всякий раз, когда есть запись A, есть запись B, и наоборот, список пропусков может дать вам одну без другой.

С вашим текущим решением для читателей содержимое карты всегда внутренне согласовано. При чтении можно быть уверенным, что для каждого B есть A. Можно быть уверенным, что метод size() дает точное количество элементов, которые будут возвращены итератором. Две итерации вернут одни и те же элементы в том же порядке.

Другими словами, allUpdatesGoThroughHere и ConcurrentSkipListSet - два хороших решения двух разных проблем.

Можете ли вы использовать метод Collections.synchronizedSet? Из HashSet Javadoc http://docs.oracle.com/javase/6/docs/api/java/util/HashSet.html

Set s = Collections.synchronizedSet(new HashSet(...));

Замените synchronized на global volatile, и все будет в порядке с копированием при записи.

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

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

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

Другой подход к проблеме публикации - использовать семантику конечного поля для создания объекта, который (теоретически) безопасен для небезопасной публикации.

Конечно, существуют и параллельные коллекции.