При участии Тима Перлса, Джошуа Блоха, Джозева Боубира, Дэвида Холмса и Дага Ли Параллельное программирование в java на
 Скачать 4.97 Mb.
|
|
Глава 5 Строительные блоки В предыдущей главе были рассмотрены несколько методов построения потокобезопасных классов, в том числе делегирование обеспечения потокобезопасности существующим потокобезопасным классам. В тех случаях, когда это целесообразно, делегирование является одной из наиболее эффективных стратегий создания потокобезопасных классов: просто позвольте существующим потокобезопасным классам управлять всем состоянием. Библиотеки платформы включают в себя богатый набор параллельных строительных блоков, такие как потокобезопасные коллекции и разнообразные синхронизаторы, которые могут координировать потоки управления взаимодействующих потоков. В этой главе рассматриваются наиболее полезные параллельные строительные блоки, особенно те, которые представлены в Java 5.0 и Java 6, и некоторые шаблоны их использования способствующие структурированию параллельных приложений. 5.1 Синхронизированные коллекции Классы синхронизированных коллекций включают в себя Vector и Hashtable , часть оригинального JDK, а также их “двоюродных братьев”, добавленных в JDK 1.2 и синхронизированные классы-обёртки, создаваемые фабричными методами Collections.synchronizedXxx . Эти классы обеспечивают потокобезопасность, инкапсулируя свое состояние и синхронизируя каждый открытый метод, чтобы одновременно только один поток мог получить доступ к состоянию коллекции. 5.1.1 Проблемы с синхронизированными коллекциями Синхронизированные коллекции потокобезопасны, но иногда для защиты составных действий может потребоваться Дополнительная блокировка на стороне клиента. В общем случае, составные действия для коллекций включают в себя итерацию (многократную выборку элементов, пока коллекция не будет исчерпана), навигацию (поиск следующего элемента после текущего в соответствии с некоторым порядком) и условные операции, такие как положить-если- отсутствует (проверка, имеет ли объект Map сопоставление для ключа K, если нет, добавление сопоставления (K, V)). С синхронизированной коллекцией эти составные действия по-прежнему технически потокобезопасны, даже без блокировки на стороне клиента, но они могут вести себя не так, как можно было бы ожидать, когда другие потоки могут одновременно изменять коллекцию. В листинге 5.1 показаны два метода, оперирующие классом Vector , getLast и deleteLast , оба из которых представляют собой последовательностями проверить-затем-выполнить. Каждый вызывает метод size для определения размера массива и использует полученное значение для извлечения или удаления последнего элемента. public static Object getLast(Vector list) { int lastIndex = list.size() - 1; return list.get(lastIndex); } public static void deleteLast(Vector list) { int lastIndex = list.size() - 1; list.remove(lastIndex); } Листинг 5.1 Составные действия над классом Vector , которые могут привести к запутанным результатам. Эти методы кажутся безобидными, и в некотором смысле так и есть - они не могут повредить объект Vector , независимо от того, сколько потоков одновременно вызывает их. Но у вызвавшего эти методы может сложиться другое мнение. Если поток A вызывает метод getLast объекта Vector с десятью элементами, а поток B вызывает метод deleteLast у того же объекта Vector , и операции чередуются, как показано на рисунке 5.1, метод getLast бросит исключение ArrayIndexOutOfBoundsException . Между вызовом метода size и последующим вызовом метода get в методе getLast , размер объекта Vector уменьшился, и индекс, вычисленный на первом шаге, стал неправильным. Рисунок 5.1 Чередование вызовов методов getLast и deleteLast , приводит к генерации исключения ArrayIndexOutOfBoundsException Такое поведение полностью соответствует спецификации класса Vector - бросается исключение, если запрашивается несуществующий элемент. Это не тот результат, которого ожидал получить вызывающий объект от вызова метода getLast , даже на фоне параллельной модификации, если принять, что объект Vector не был пуст с самого начала. Поскольку синхронизированные коллекции фиксируются в политике синхронизации, которая поддерживает блокировку на стороне клиента 62 , можно создавать новые операции, которые являются атомарными по отношению к другим операциям коллекций, при условии, что нам известно, какую блокировку использовать. Синхронизированные классы коллекций защищают каждый метод с помощью блокировки на самом синхронизированном объекте коллекции. Захватив блокировку коллекции, мы можем сделать методы getLast и deleteLast атомарными, гарантируя, что размер объекта Vector не изменится между вызовами методов size и get , как показано в листинге 5.2. public static Object getLast(Vector list) { synchronized (list) { int lastIndex = list.size() - 1; return list.get(lastIndex); } } 62 Это задокументировано только в Javadoc версии Java 5.0, как пример корректной идиомы итерации. size → 10 get(9) boom size → 10 remove(9) A B public static void deleteLast(Vector list) { synchronized (list) { int lastIndex = list.size() - 1; list.remove(lastIndex); } } Листинг 5.2 Составные действия над классом Vector с использованием блокировки со стороны клиента Риск того, что размер списка может измениться между вызовом size и соответствующим вызовом get , также присутствует при переборе элементов объекта Vector , как показано в листинге 5.3. for (int i = 0; i < vector.size(); i++) doSomething(vector.get(i)); Листинг 5.3 Итерация, которая может бросить исключение ArrayIndexOutOfBoundsException Эта идиома итерации основывается на вере в то, что другие потоки не изменят объект Vector между вызовами методов size и get . В однопоточной среде это предположение вполне допустимо, но когда другие потоки могут параллельно изменять объект Vector , это может привести к проблемам. Так же, как с методом getLast , если другой поток удаляет элемент, в то время как вы перебираете элементы объекта Vector , и операции чередуются неудачно, эта идиома итерации бросает исключение ArrayIndexOutOfBoundsException Хотя итерация в листинге 5.3 может выдать исключение, это не означает, что класс Vector не является потокобезопасным. Состояние класса Vector остается действительным, и исключение фактически соответствует его спецификации. Тем не менее, что-то столь же обыденное, как извлечение последнего элемента или итерация, бросает исключение, что явно нежелательно. Проблема ненадежной итерации может быть вновь решена путем блокировки на стороне клиента, при некоторых дополнительных затратах на масштабируемость. Удерживая блокировку объекта Vector на протяжении всей итерации, как показано в листинге 5.4, мы не допускаем изменения объекта Vector другими потоками во время итерации. К сожалению, в течение этого времени мы также препятствуем другим потокам в получении доступа к нему, что ухудшает параллелизм. synchronized (vector) { for (int i = 0; i < vector.size(); i++) doSomething(vector.get(i)); } Листинг 5.4 Итерация, с блокировкой на стороне клиента 5.1.2 Итераторы и ConcurrentModificationException Мы используем класс Vector во многих наших примерах для большей наглядности, несмотря на то, что он считается “наследованным” (legacy) классом коллекций. Но более “современные” классы коллекций не устраняют проблему с составными действиями. Стандартный способ итерирования объекта Collection заключается в явном использовании объекта Iterator или неявном, с использованием синтаксиса цикла for-each, представленного в Java 5.0, но использование итераторов не устраняет необходимость в использовании блокировки коллекций во время итерации, если другие потоки могут параллельно изменять их. Итераторы, возвращаемые синхронизированными коллекциями, не предназначены для работы в режиме параллельной модификации, они быстро падают (fail-fast) с ошибкой - это означает, что если они обнаруживают, что коллекция изменилась с начала итерации, они бросают исключение ConcurrentModificationException Эти быстро падающие с ошибкой итераторы не предназначены для надежной защиты - они спроектированы на основе принципа “добросовестных усилий” (good-faith-effort) для перехвата ошибок параллелизма и, таким образом, действуют только как индикаторы раннего предупреждения о проблемах параллелизма. Они реализуются путем связывания счетчика изменений с коллекцией: если счетчик изменений модифицируется во время итерации, методы hasNext или next бросают исключение ConcurrentModificationException Однако эта проверка выполняется без синхронизации, поэтому существует риск увидеть устаревшее значение счетчика изменений и, следовательно, итератор может не узнать, что изменение было сделано. Это следствие специально принятого компромисса, для снижения влияния кода обнаружения параллельных изменений на производительность. 63 В листинге 5.5 иллюстрируется процесс итерирования коллекции с помощью синтаксиса цикла for-each. Внутренне javac генерирует код, который использует класс Iterator , повторно вызывающий методы hasNext и next для итерирования объекта List . Как и при итерировании класса Vector , способ предотвращения возникновения исключения ConcurrentModificationException заключается в том, чтобы удерживать на коллекции блокировку до полного завершения процесса итерации. List = Collections.synchronizedList(new ArrayList // May throw ConcurrentModificationException for (Widget w : widgetList) doSomething(w); Листинг 5.5 Итерирование объекта List с помощью класса Iterator Однако существует несколько причин, по которым блокировка коллекции во время итерации может быть нежелательной. Другие потоки, которым требуется доступ к коллекции, блокируются до завершения итерации; если коллекция большая или задача, выполняемая для каждого элемента, является длительной, потоки будут вынуждены долго ждать. Кроме того, если коллекция заблокирована, как показано в листинге 5.4, вызывается функция doSomething с блокировкой, которая является фактором риска возникновения взаимоблокировки (см. главу 10 ). Даже при отсутствии риска голодания или взаимоблокировки, блокировка коллекций на значительные периоды времени ухудшает масштабируемость приложений. Чем дольше удерживается блокировка, тем больше вероятность того, что она будет оспорена, и если множество потоков заблокировано в ожидании освобождения блокировки, будет страдать пропускная способность и эффективность использования ЦП (см. главу 11 ). Альтернативой блокировке коллекции во время итерации является клонирование коллекции и итерирования копии. Поскольку клон ограничен 63 Исключение ConcurrentModificationException также может возникать и в однопоточном коде; это происходит, когда объекты удаляются из коллекции напрямую, а не с использованием метода Iterator.remove потоком, никакой другой поток не сможет изменить его во время итерации, таким образом, исключается возможность возбуждения исключения ConcurrentModificationException . (Коллекция по-прежнему должна быть заблокирована во время самой операции клонирования.) Клонирование коллекции оказывает очевидное влияние на производительность; является ли это выгодным компромиссом, зависит от многих факторов, включая размер коллекции, объем работы для каждого элемента, относительную частоту итераций по сравнению с другими операциями коллекции, а также требования к отзывчивости и пропускной способности. 5.1.3 Скрытые итераторы Хотя блокировка может предотвращать возникновение исключения ConcurrentModificationException , необходимо помнить об использовании блокировки везде, где может выполняться итерирование совместно используемой коллекции. Проще сказать, чем сделать, поскольку итераторы иногда скрыты, как в классе HiddenIterator из листинга 5.6. В классе HiddenIterator нет явной итерации, но код, выделенный жирным шрифтом, использует итерацию. Конкатенация строк преобразуется компилятором в вызов StringBuilder append(Object) , который, в свою очередь, вызывает метод коллекции toString - и реализация toString в стандартных коллекциях итерирует коллекцию и вызывает toString на каждом элементе, чтобы сформировать хорошо отформатированное представление содержимого коллекции. Метод addTenThings может бросить исключение ConcurrentModificationException , потому что коллекция итерируется при вызове метода toString , в процессе подготовки отладочного сообщения. Конечно, реальная проблема заключается в том, что класс HiddenIterator не является потокобезопасным; блокировка класса HiddenIterator должна захватываться перед использованием переменной set в вызове println , но код отладки и журналирования обычно пренебрегает этим. Настоящий урок здесь в том, что чем больше расстояние между состоянием и синхронизацией, которая его защищает, тем больше вероятность того, что кто-то забудет согласованно использовать синхронизацию при доступе к этому состоянию. Если бы класс HiddenIterator обернул класс HashSet с помощью synchronizedSet , инкапсулируя синхронизацию, такая ошибка бы не возникла. Подобно тому, как инкапсуляция состояния объекта упрощает сохранение его инвариантов, инкапсуляция его синхронизации упрощает реализацию политики синхронизации. public class HiddenIterator { @GuardedBy("this") private final Set public void addTenThings() { Random r = new Random(); for (int i = 0; i < 10; i++) add(r.nextInt()); System.out.println("DEBUG: added ten elements to " + set); } } Листинг 5.6 Итерация скрытая внутри конкатенации строк. Не делайте так. Итерация также косвенно вызывается методами коллекции hashCode и equals , которые могут вызываться, если коллекция используется как элемент или ключ другой коллекции. Аналогично, методы containsAll , removeAll и keepAll , а также конструкторы, которые принимают коллекции в качестве аргументов, также выполняют итерацию коллекции. Все эти косвенные применения итераций могут приводить к возбуждению исключения ConcurrentModificationException 5.2 Параллельные коллекции В Java 5.0 синхронизированные коллекции были улучшены, путём ввода нескольких классов параллельных коллекций. Синхронизированные коллекции обеспечивают потокобезопасность путем сериализации всех обращений к состоянию коллекции. Цена такого подхода – низкая степень параллелизма; когда несколько потоков конкурируют за блокировку всей коллекции, страдает пропускная способность. Параллельные коллекции, с другой стороны, предназначены для одновременного доступа из нескольких потоков. В Java 5.0 добавлен класс ConcurrentHashMap , в качестве замены для синхронизированных основанных на хэше реализаций интерфейса Map , и класс CopyOnWriteArrayList , в качестве замены для синхронизированных реализаций интерфейса List , в случаях, когда обход элементов является доминирующей операцией. Новый интерфейс ConcurrentMap добавляет поддержку общих составных действий, таких как положить-если-отсутствует, замена и удаление по условию. Замена синхронизированных коллекций параллельными коллекциями может предложить значительное улучшение масштабируемости с небольшим риском. В Java 5.0 также было добавлено два новых типа коллекции, Queue и BlockingQueue . Класс Queue предназначен для временного хранения набора элементов в ожидании обработки. Предлагается несколько реализаций, в том числе класс ConcurrentLinkedQueue , традиционная очередь FIFO, класс PriorityQueue , (не параллельная) приоритетная упорядоченная очередь. Операции очередей не блокируются; если очередь пуста, операция извлечения возвращает значение null . Хотя вы можете имитировать поведение класса Queue с помощью интерфейса List - фактически, класс LinkedList также является реализацией очереди - классы Queue были добавлены, из-за того, что устранение требований произвольного доступа интерфейса List допускает более эффективные параллельные реализации. Класс BlockingQueue расширяет класс Queue , добавляя блокировки операциям вставки и извлечения данных. Если очередь пуста, извлечение данных блокируется до тех пор, пока элемент не будет доступен, и если очередь заполнена (для ограниченных очередей), вставка блокируются до того момента, пока не появится свободное место. Блокирующие очереди чрезвычайно полезны в шаблоне производитель-потребитель (producer-consumer) и более подробно рассматриваются в разделе 5.3. Также как класс ConcurrentHashMap является параллельной заменой для синхронизированного основанного на хэше класса Map , Java 6 добавляет классы ConcurrentSkipListMap и ConcurrentSkipListSet , которые выступают в качестве параллельной замены для синхронизированных классов SortedMap или SortedSet (например, классов TreeMap или TreeSet , обёрнутых с помощью метода synchronizedMap ). 5.2.1 Класс ConcurrentHashMap Синхронизированные классы коллекций удерживают блокировку во время выполнения каждой операции. Некоторые операции, такие как HashMap.get или List.contains , могут требовать больше работы, чем предполагалось изначально: перемещение хэш-корзины (hash bucket) или поиск конкретного объекта в списке влечёт за собой вызов метода equals (который сам по себе может вызывать значительное количество вычислений) для нескольких объектов-кандидатов. Если метод hashCode, в коллекции, основанной на хэше, плохо распределяет хэш- значения, элементы могут быть неравномерно распределены между корзинами; в вырожденном случае, плохая хеш-функция превратит хэш-таблицу в связанный список. Обход длинного списка и вызов метода equals для некоторых или всех элементов может занять много времени, и в течение этого времени ни один другой поток не может получить доступ к коллекции. Класс ConcurrentHashMap – это основанная на хэше реализация интерфейса Map , подобная классу HashMap , но использующая совершенно другую стратегию блокировки, которая обеспечивает лучшую параллельность и масштабируемость. Вместо синхронизации каждого метода на общей блокировке, с ограничением доступа одним потоком за раз, он использует более детализированный механизм блокировки, называемый чередуемой блокировкой (см. раздел 11.4.3 ), позволяющий обеспечить большую степень совместного доступа. Множество потоков-читателей может произвольно и параллельно получать доступ к переменной map 64 , читатели могут получать доступ к переменной map одновременно с писателями, и ограниченное число писателей может параллельно изменять переменную map Результатом является гораздо более высокая пропускная способность при параллельном доступе с небольшим снижением производительности при однопоточном доступе. Класс ConcurrentHashMap , наряду с другими параллельными коллекциями, далее улучшает синхронизированные классы коллекций, предоставляя итераторы, которые не бросают исключение ConcurrentModificationException , таким образом, устраняя необходимость в блокировке коллекции во время итерирования. Итераторы, возвращаемые классом ConcurrentHashMap , слабо согласованы (weakly consistent), в отличие от итераторов, быстро падающих с ошибкой, возвращаемых синхронизированными коллекциями. Слабо согласованныйитератор может допускать параллельную модификацию, обход элементов так, как они 64 В контексте – переменная map является экземпляром класса ConcurrentHashMap. существовали на момент построения итератора, и может (но не гарантируется) отражать изменения в коллекции после построения итератора. Как и со всеми прочими улучшениями, пришлось пойти на несколько компромиссов. Семантика методов, оперирующих всем классом Map , таких как size и isEmpty , была немного ослаблена, чтобы отразить параллельный характер коллекции. Поскольку результат вызова метода size может быть устаревшим к моменту его вычисления, фактически выполняется только оценка, поэтому метод size может возвращать вместо точного подсчета аппроксимированное значение. Хотя на первый взгляд это может вызывать беспокойство, на самом деле такие методы, как size и isEmpty , гораздо менее полезны в параллельных средах, поскольку эти величины являются изменяющимися значениями. Таким образом, требования к этим операциям были ослаблены, чтобы обеспечить оптимизацию производительности для наиболее важных операций, в первую очередь get , put , containsKey и remove Одна особенность, предлагаемая синхронизированными реализациями интерфейса Map , но не предлагаемая классом ConcurrentHashMap , - это возможность блокировки переменной map для монопольного доступа. С помощью класса Hashtable и метода synchronizedMap захват блокировки объекта Map предотвращает доступ к нему любого другого потока. Это может быть необходимо в нестандартных случаях, таких как атомарное добавление нескольких отображений или итерирование объекта Map несколько раз и необходимость видеть одни и те же элементы в одном и том же порядке. В целом, это разумный компромисс: ожидается, что параллельные коллекции будут постоянно изменять свое содержимое. Поскольку он имеет так много преимуществ и так мало недостатков по сравнению с классом Hashtable или методом synchronizedMap , замена синхронизированных реализаций Map на класс ConcurrentHashMap в большинстве случаев приводит к улучшению масштабируемости. Класс ConcurrentHashMap не подходит для полной замены только в том случае, если приложению необходимо заблокировать переменную map для монопольного доступа 65 |