В 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. Докато Thread A все още е в блока synchronized, Thread B чете своята локална стойност от global в стека и се опитва да влезе в блока synchronized. Тъй като Thread A в момента е в блоковете на Thread 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 да остане неизменна... за щастие има Collections.unmodifiableSet, който можете да използвате, за да наложите това. Като пример, вероятно трябва да направите нещо като следното...

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, обмисляли ли сте да използвате ConcurrentHashMap? Те гарантират, че използването на for цикъл, както сте направили във вашия пример, ще бъде последователно.

По подобен начин итераторите и изброяванията връщат елементи, отразяващи състоянието на хеш-таблицата в някакъв момент при или след създаването на итератора/изброяването.

Вътрешно, Iterator се използва за подобрено for над Iterable.

Можете да създадете Set от това, като използвате Collections.newSetFromMap като следното:

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 и обратно, списъкът за пропускане може да ви даде едно без друго.

С вашето текущо решение, за читателите, съдържанието на картата винаги е вътрешно съгласувано. Четенето може да бъде сигурно, че има A за всяко B. Може да е сигурно, че методът 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 може да е подходящо, но все пак ще имате записи, блокиращи четения.

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

Разбира се, налични са и едновременни колекции.