Понимание коллекций concurrency и Collections.synchronized *

Вчера я узнал, что неправильно использовал коллекции с concurrency на протяжении многих-многих лет.

Всякий раз, когда я создаю коллекцию, к которой нужно обращаться более чем одним потоком, я обертываю ее в один из методов Collections.synchronized *. Затем, всякий раз, когда вы мутируете коллекцию, я также переношу ее в синхронизированный блок (я не знаю, почему я это делал, я, должно быть, подумал, что я его где-то читал).

Однако, прочитав API более внимательно, кажется, вам нужен синхронизированный блок при повторной сборке. В документах API (для карты):

Обязательно, чтобы пользователь вручную синхронизировал на возвращенной карте при повторении любого из своих представлений коллекции:

И вот небольшой пример:

List<O> list = Collections.synchronizedList(new ArrayList<O>());
...
synchronized(list) {
   for(O o: list) { ... }
}

Итак, учитывая это, у меня есть два вопроса:

Почему это даже необходимо? Единственное объяснение, о котором я могу думать, это использование итератора по умолчанию вместо управляемого поточно-безопасного итератора, но они могли бы создать потокобезопасный итератор и устранить этот беспорядок, правильно?
Что еще важнее, что это такое? Помещая итерацию в синхронизированный блок, вы предотвращаете одновременную итерацию нескольких потоков. Но другой поток может мутировать список при повторении так, как там работает синхронизированный блок? Не будет ли мутировать список где-нибудь еще с винта с итерацией, синхронизирован ли он или нет? Что мне не хватает?

Спасибо за помощь!

Ответ 1

Почему это даже необходимо? Единственное объяснение, о котором я могу думать, это они используют итератор по умолчанию вместо управляемой поточно-безопасной итератора, но они могли бы создать потокобезопасный итератор и зафиксировать этот беспорядок, правильно?

Итерация работает с одним элементом за раз. Чтобы Iterator был потокобезопасным, им нужно будет сделать копию коллекции. В противном случае любые изменения основного Collection повлияют на то, как вы выполняете итерацию с непредсказуемыми или undefined результатами.

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

Методы объекта, возвращаемого synchronizedList(List), работают путем синхронизации на экземпляре. Таким образом, ни один другой поток не может добавлять/удалять из того же List, пока вы находитесь внутри блока synchronized на List.

Ответ 2

Основной случай

Все методы объекта, возвращаемого Collections.synchronizedList(), синхронизируются с самим объектом списка. Всякий раз, когда метод вызывается из одного потока, каждый другой поток, вызывающий любой его метод, блокируется до завершения первого вызова.

Пока все хорошо.

Iterare necesse est

Но это не останавливает другой поток от изменения коллекции, когда вы между вызовами до next() на Iterator. И если это произойдет, ваш код завершится неудачей с помощью ConcurrentModificationException. Но если вы также выполняете итерацию в блоке synchronized, и вы синхронизируетесь на одном и том же объекте (т.е. Списке), это остановит другие потоки от вызова каких-либо методов мутаторов в списке, они должны ждать, пока ваши итерационные потоки не будут выпущены монитор для объекта списка. Ключ состоит в том, что методы мутатора synchronized относятся к тому же объекту, что и ваш блок итератора, это то, что их останавливает.

Мы еще не из леса...

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

List<Object> list = Collections.synchronizedList( ... );
...
if (!list.contains( "foo" )) {
   // there nothing stopping another thread from adding "foo" here itself, resulting in two copies existing in the list
   list.add( "foo" );
}
...
synchronized( list ) { //this block guarantees that "foo" will only be added once
  if (!list.contains( "foo" )) {
     list.add( "foo" );
  }
}

Итератор, защищенный потоками?

Что касается вопроса об потокобезопасном итераторе, то с ним действительно существует реализация списка, он называется CopyOnWriteArrayList. Это невероятно полезно, но, как указано в документе API, оно ограничено только несколькими вариантами использования, особенно когда ваш список модифицируется очень редко, но повторяется так часто (и по множеству потоков), что синхронизация итераций приведет к серьезная бутылочная горловина. Если вы используете его ненадлежащим образом, это может значительно ухудшить производительность вашего приложения, так как каждая модификация списка создает всю новую копию.

Ответ 3

Синхронизация по возвращенному списку необходима, поскольку внутренние операции синхронизируются в mutex, а этот мьютекс - this, то есть сама синхронизированная коллекция.

Здесь соответствующий код из Collections, конструкторы для SynchronizedCollection, корень иерархии синхронизированной коллекции.

    SynchronizedCollection(Collection<E> c) {
        if (c==null)
            throw new NullPointerException();
        this.c = c;
        mutex = this;
    }

(Существует еще один конструктор, который принимает мьютекс, используемый для инициализации синхронизированных коллекций "вид" из таких методов, как subList.)

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

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

Ответ 4

Sotirios Delimanolis ответил на ваш второй вопрос: "Что это значит?" эффективно. Я хотел усилить свой ответ на ваш первый вопрос:

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

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

1. Блокировка + Fail-fast

Это то, что предлагается документами API. Если вы заблокируете синхронизированный объект-оболочку при ее повторном выполнении (и остальная часть кода в системе написана правильно, так что метод обработки мутаций также проходит через объект с синхронизированной оболочкой), итерация гарантированно увидит согласованное представление содержимого коллекции. Каждый элемент будет проходить ровно один раз. Недостатком, конечно же, является то, что другим потокам не разрешается изменять или даже читать коллекцию во время ее повторения.

Вариант этого будет использовать блокировку чтения-записи для чтения, но не записи во время итерации. Однако сама итерация может мутировать коллекцию, поэтому это может испортить последовательность для читателей. Для этого вам придется написать свою собственную оболочку.

Неудача запускается, если блокировка не выполняется вокруг итерации, а кто-то другой изменяет коллекцию, или если блокировка выполнена, а кто-то нарушает политику блокировки. В этом случае, если итерация обнаруживает, что коллекция была мутирована из-под нее, она бросает ConcurrentModificationException.

2. Копирование при записи

Это стратегия, используемая CopyOnWriteArrayList среди других. Итератор на такой коллекции не требует блокировки, он всегда будет показывать согласованные результаты во время итератора, и он никогда не будет бросать ConcurrentModificationException. Однако записи всегда копируют весь массив, что может быть дорогостоящим. Возможно, что более важно, понятие согласованности изменяется. Содержимое коллекции могло бы измениться во время повторного ее повторения - точнее, в то время как вы повторяли моментальный снимок своего состояния в прошлом, поэтому любые решения, которые вы могли бы сделать теперь являются потенциально устаревшими.

3. Слабо согласованный

Эта стратегия используется ConcurrentLinkedDeque и аналогичными коллекциями. Спецификация содержит определение слабо согласованное. Этот подход также не требует блокировки, и итерация никогда не будет бросать ConcurrentModificationException. Но свойства консистенции крайне слабы. Например, вы можете попытаться скопировать содержимое ConcurrentLinkedDeque, выполнив итерацию по нему и добавив каждый найденный элемент к вновь созданному List. Но другие потоки могут изменять значение deque во время его повторения. В частности, если поток удаляет элемент "позади", где вы уже повторили, а затем добавляет элемент "впереди" того, где вы выполняете итерацию, итерация, вероятно, будет наблюдать как удаленный элемент, так и добавленный элемент. Таким образом, копия будет иметь "моментальный снимок", который никогда не существовал в любой момент времени. Я должен признать, что довольно слабое понятие последовательности.

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