Пожалуйста, объясните состояние гонки в этой идиоме «положи-если-отсутствует».

Рассмотрим следующий код и предположим, что список является синхронизированным списком.

List list = Collections.synchronizedList(new ArrayList());

if(!list.contains(element)){
       list.add(element)
}

Я знаю, что приведенный выше фрагмент кода должен синхронизироваться извне (защищенный замком), чтобы сделать его полностью потокобезопасным. При чем здесь состояние гонки?


java race-condition concurrency synchronization java.util.concurrent
person Inquisitive    schedule 29.06.2012    source источник

Ответы (5)


arrow_upward
2
arrow_downward

Представьте, что у вас есть два потока

A: if(!list.contains(element)){ // false
B: if(!list.contains(element)){ // false
A:     list.add(element) // add once
B:     list.add(element) // add a second time.

Конечно, самое простое решение — использовать Set. например

Set<E> set = Collections.newSetFromMap(new ConcurrentHashMap<E, Boolean>());

set.add(element);
person Peter Lawrey    schedule 29.06.2012
comment
у меня нет экземпляра Map. У меня есть экземпляр List. Однако ваш ответ правильно объясняет состояние гонки. Спасибо. - person Inquisitive; 29.06.2012
comment
Это набор, а не карта, которую вы бы использовали. Но если у вас есть список, вы должны заблокировать коллекцию извне, чтобы избежать этой проблемы. - person Peter Lawrey; 29.06.2012

arrow_upward
3
arrow_downward

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

Если бы contains и add были атомарными (синхронизированными) сами по себе, то, по крайней мере, между вызовами contains и add была бы одна четко определенная гонка.

person Marko Topolnik    schedule 29.06.2012
comment
они атомарны, так как список является синхронизированным. - person Qnan; 29.06.2012
comment
Я понимаю. Да, тогда гонка такая, как описано в последнем абзаце. Другой поток мог добавить ваш элемент, пока ваш поток находится в состоянии оценки contains и еще не вошел в add. - person Marko Topolnik; 29.06.2012
comment
На этом примере вы можете увидеть, насколько контрпродуктивно синхронизировать операции с одним списком. Это просто накладные расходы. - person Marko Topolnik; 29.06.2012
comment
да, я думаю, нельзя использовать синхронизированную коллекцию, если все вызовы к ней синхронизируются извне - person Qnan; 29.06.2012
comment
Все методы чтения/записи объекта должны быть синхронизированы, чтобы предотвратить проблему, которую я объяснил в своем ответе. Это верно, если вы сохраняете в файл или читаете/записываете в память (редактируете массив). - person Matt Westlake; 29.06.2012
comment
@MattWestlake Но, конечно, должны. Дело в том, что границы синхронизации почти всегда являются более грубыми, чем отдельные вызовы методов в списке. - person Marko Topolnik; 29.06.2012
comment
Так что я думаю, я смущен тем, что вопрос тогда. Мы все согласны с тем, что процесс чтения/записи должен быть внутри синхронизированного блока. - person Matt Westlake; 29.06.2012

arrow_upward
2
arrow_downward

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

person Qnan    schedule 29.06.2012
comment
Если они работают в разных потоках, то не будет ли элемент отличаться в разных потоках? Вы не собираетесь добавлять один и тот же элемент в каждый поток вашей программы, а если бы вы это сделали, безопасность потоков не устранила бы проблему. - person Matt Westlake; 29.06.2012
comment
если элементы обязательно разные, то вопроса не возникает, но это довольно странное требование. Обратите внимание, что разные экземпляры объектов A и B могут считаться одними и теми же при условии, что A.equals(B)==true. - person Qnan; 29.06.2012
comment
@MattWestlake Мы, конечно, не можем предполагать ничего подобного, и на самом деле в большинстве ситуаций было бы плохо предполагать это, поскольку факт может измениться в будущем и выявить ошибку. Если инвариант состоит в том, что список не содержит дубликатов, он должен быть явно применен. - person Marko Topolnik; 29.06.2012
comment
Если бы A и B были одинаковыми, то потокобезопасность гарантировала бы добавление записи только дважды (один раз из A и один раз из B). Состояние гонки по-прежнему A.read B.read A.write B.write равно только тому, что написал B. - person Matt Westlake; 29.06.2012
comment
@MattWestlake, это зависит от того, что вы подразумеваете под потокобезопасностью. Такое состояние гонки возможно даже при синхронизированной коллекции, как правильно указывает автор вопроса, поэтому требуется внешняя синхронизация, а это означает, что весь блок, который выполняет проверку и добавление, не может быть введен более чем одним потоком за раз. - person Qnan; 29.06.2012

arrow_upward
0
arrow_downward

Как я это вижу, возникает состояние гонки, если list.contains(element) дает false, и другой поток добавит элемент после этого, но до вызова add в первом потоке.

person JulianB    schedule 29.06.2012

arrow_upward
0
arrow_downward

Состояние гонки вступает в игру между получением списка и его повторным сохранением (при сохранении в пример файла).

Пример: файл содержит A

  • Поток 1 получает A
  • Тема 1 добавляет B к A
  • Тема 2 получает A
  • Тема 1 Сохраняет AB в файл
  • Тема 2 добавляет C к A
  • Тема 2 Сохраняет AC в файл

Считанный файл будет содержать AC, а рабочий поток 1 будет потерян.

person Matt Westlake    schedule 29.06.2012