При участии Тима Перлса, Джошуа Блоха, Джозева Боубира, Дэвида Холмса и Дага Ли Параллельное программирование в java на
 Скачать 4.97 Mb.
|
|
5.2.2 Дополнительные атомарные операции интерфейса Map Поскольку класс ConcurrentHashMap не может быть заблокирован для монопольного доступа, мы не можем использовать блокировку на стороне клиента для создания новых атомарных операций, таких как положить-если-отсутствует, как мы сделали для класса Vector в разделе 4.4.1. Вместо этого, ряд общих составных операций, таких как положить-если-отсутствует, удалить-если-равно и заменить-если-равно реализованы как атомарные операции и определены в интерфейсе ConcurrentMap , приведённом в листинге 5.7. public interface ConcurrentMap // Insert into map only if no value is mapped from K V putIfAbsent(K key, V value); // Remove only if K is mapped to V 65 Или в случае, если вы полагаетесь на побочные эффекты от синхронизации синхронизированной реализации интерфейса Map boolean remove(K key, V value); // Replace value only if K is mapped to oldValue boolean replace(K key, V oldValue, V newValue); // Replace value only if K is mapped to some value V replace(K key, V newValue); } Листинг 5.7 Интерфейс ConcurrentMap Если вы найдёте для себя возможным добавить такую функциональность в существующую синхронизированную реализацию интерфейса Map , это, вероятно, будет признаком того, что вместо нее следует рассмотреть возможность использования интерфейса ConcurrentMap 5.2.3 Класс CopyOnWriteArrayList Класс CopyOnWriteArrayList является параллельной заменой для синхронизированной реализации интерфейса List , предлагает лучшую степень параллелизма в распространенных ситуациях и устраняет необходимость использования блокировки или копирования коллекции в процессе итерирования. (Аналогичным образом, класс CopyOnWriteArraySet является параллельной заменой синхронизированной реализации интерфейса Set .) Коллекции типа “скопировать-при-записи” (copy-on-write) обеспечивают потокобезопасность благодаря тому, что при правильной публикации фактически неизменяемого объекта дальнейшая синхронизация при доступе к нему не требуется. Они реализуют изменяемость, создавая и публикуя новую копию коллекции при каждом ее изменении. Итераторы для коллекций “скопировать-при- записи” сохраняют ссылку на резервный массив, который был текущим на момент начала итерации, и так как он никогда не изменяется, им необходима только краткая синхронизация, чтобы обеспечить видимость содержимого массива. В результате несколько потоков могут выполнять итерирование коллекции без влияния друг на друга или влияния потоков, желающих изменить коллекцию. Итераторы, возвращаемые коллекциями типа “скопировать-при-записи”, не возбуждают исключение ConcurrentModificationException и возвращают элементы точно такими же, какими они были на момент создания итератора, независимо от последующих изменений. Очевидно, что копирование резервного массива при каждом изменении коллекции сопряжено с определенными затратами, особенно если коллекция велика; коллекции типа “скопировать-при-записи” целесообразно использовать только тогда, когда итерация используется гораздо чаще, чем модификация. Этот критерий точно описывает принцип работы многих систем уведомления о событиях: для доставки уведомления требуется итерация по списку зарегистрированных слушателей и вызов каждого из них, и, в большинстве случаев, регистрация или отмена регистрации слушателя событий происходит гораздо реже, чем получение уведомления о событии. (См. [CPJ 2.4.4] для получения дополнительной информации о шаблоне “скопировать-при-записи”.) 5.3 Блокирующие очереди и шаблон производитель- потребитель Блокирующие очереди предоставляют блокирующие методы put и take, а также их эквиваленты с ограничением времени offer и poll . Если очередь заполнена, выполнение метода put блокируется до тех пор, пока в очереди не появится свободное место; если очередь пуста, метод take блокируется, до того момента, пока не появится доступный элемент. Очереди могут быть ограниченными или неограниченными; неограниченные очереди никогда не заполняются, поэтому метод put в неограниченной очереди никогда не блокируется. Блокирующие очереди поддерживают шаблон проектирования “производитель- потребитель” (producer-consumer). Модель “производитель-потребитель” отделяет идентификацию работы, которая должна быть выполнена, от выполнения этой работы, помещая элементы работы в список “сделать это” (to do) для последующей обработки, вместо того, чтобы обрабатывать их сразу, по мере идентификации. Шаблон “производитель-потребитель” упрощает разработку, так как удаляет код зависимостей между классами производителя и потребителя, и упрощает управление нагрузкой путем разделения активностей, которые могут производить или потреблять данные с различной или переменной скоростью. В схеме ‘производитель-потребитель’, построенной вокруг блокирующей очереди, производители помещают данные в очередь по мере их поступления, а потребители извлекают данные из очереди, когда они готовы предпринять соответствующие действия. Производителям не нужно ничего знать об идентичности или количестве потребителей, или даже о том, являются ли они единственным производителем - всё, что им нужно сделать, это поместить элементы данных в очередь. Точно так же потребители не должны знать, кто является производителем или откуда взялась работа. Класс BlockingQueue упрощает реализацию дизайна “производитель-потребитель” с любым количеством производителей и потребителей. Одним из наиболее распространенных дизайнов реализации шаблона “производитель-потребитель” является пул потоков в сочетании с рабочей очередью; этот шаблон воплощен в фреймворке выполнения задач Executor , что является темой глав 6 и 8. Разделение труда для двух человек, моющих посуду, является знакомым примером дизайна ‘производителя-потребителя”: один человек моет посуду и помещает её в стойку для посуды, а другой человек извлекает посуду из стойки и сушит её. В этом случае стойка с тарелками действует как блокирующая очередь; если в стойке нет посуды, потребитель ждет, пока они появится, чтобы высушить её, и если стойка заполняется, производитель должен прекратить мойку, до того момента, пока в шкафу не освободится место. Эта аналогия распространяется на несколько производителей (хотя это может привести к конкуренции за доступ к мойке) и нескольких потребителей; каждый рабочий (worker) взаимодействует только с посудой. Никто не должен знать, сколько производителей или потребителей существует, или кто создал полученный элемент работы. Ярлыки “производитель” и “потребитель” относительны; активность, которая выступает в качестве потребителя в одном контексте, может выступать в качестве производителя в другом. Сушка посуды “потребляет” чистую влажную посуду и “производит” чистую сухую посуду. Третий человек, желающий помочь, может убирать сухую посуду, и в этом случае сушильщик будет выступать и как потребитель, как и производитель, и теперь есть две общие рабочие очереди (каждая из которых может блокировать работу сушильщика от продолжения.) Блокирующие очереди упрощают кодирование потребителей, так как принимают блоки до тех пор, пока данные доступны. Если производители генерируют работу не достаточно быстро, чтобы занять потребителей, потребители просто ждут, пока не станет доступно больше работы. Иногда это вполне приемлемо (как в серверном приложении, когда ни один клиент не обращается к службе), а иногда это указывает на то, что отношение потоков-производителей к потокам-потребителям должно быть скорректировано для достижения лучшего использования ресурсов (как в веб-сканере или другом приложении, в котором работа фактически бесконечна). Если производители последовательно генерируют работу быстрее, чем потребители могут ее обработать, это в конечном итоге приведёт к тому, что у приложения закончится память, потому что рабочие элементы будут добавляться в очередь без ограничений. Опять же, блокирующая природа метода put значительно упрощает кодирование производителей; если мы используем ограниченную очередь, то, когда очередь заполняет блок производителей, потребителям предоставляется время нагнать их, потому что заблокированный производитель больше не может генерировать элементы работы. Блокирующие очереди также предоставляют метод offer , который возвращает статус сбоя, если элемент не может быть помещён в очередь. Это позволяет создавать более гибкие политики для работы с перегрузкой, такие как сброс нагрузки, сериализация избыточных рабочих элементов и запись их на диск, уменьшение числа потоков производителя или регулирование работы производителей каким-либо другим способом. Ограниченные очереди являются мощным инструментом управления ресурсами для создания надежных приложений: они делают вашу программу более устойчивой к перегрузке, регулируя работу активностей, рискующих произвести больше работы, чем может быть обработано. В то время как шаблон “производитель-потребитель” позволяет отделить код производителя и потребителя друг от друга, их поведение по-прежнему косвенно связано через общую рабочую очередь. Представляется заманчивым предположить, что потребители всегда будут следить за тем, чтобы вам не нужно было размещать какие-либо ограничения на размер рабочих очередей, но это рецепт для последующего перепроектирования вашей системы. Стройте управление ресурсами в своем дизайне, заблаговременно используя блокирующие очереди - намного проще это сделать сначала, чем позже модифицировать его. Блокирующие очереди упрощают дело в ряде ситуаций, но если блокирующие очереди не вписываются в ваш дизайн, вы можете создавать другие блокирующие структуры данных, используя класс Semaphore (см. раздел 5.5.3 ). Библиотека классов содержит несколько реализаций интерфейса BlockingQueue . Классы LinkedBlockingQueue и ArrayBlockingQueue являются очередями FIFO, аналогичными классам LinkedList и ArrayList , но с лучшей параллельной производительностью, чем синхронизированные реализации интерфейса List Класс PriorityBlockingQueue является очередью с приоритетом, которая полезна в случае, когда вы хотите обработать элементы в порядке, отличном от FIFO. Как и другие сортированные коллекции, PriorityBlockingQueue может сравнивать элементы в соответствии с их естественным порядком (если они реализуют интерфейс Comparable ) или с помощью интерфейса Comparator Последняя реализация интерфейса BlockingQueue , класс SynchronousQueue , на самом деле не очередь вообще, в том смысле, что он не поддерживает пространство для хранения элементов в очереди. Вместо этого он поддерживает список потоков в очереди, ожидающих постановки в очередь или удаления элемента из очереди. По аналогии с мытьём посуды, это подобно тому, что шкафа для посуды нет, вместо этого, вымытая посуда вручается непосредственно следующему свободному сушильщику. Хотя это может показаться странным способом реализации очереди, он уменьшает задержку, связанную с перемещением данных от производителя к потребителю, поскольку элемент работы может быть передан непосредственно. (В традиционной очереди операции постановки в очередь и изъятия из очереди должны выполняться последовательно, прежде чем можно будет передать единицу работы.) Прямая передача также возвращает производителю больше информации о состоянии задачи; когда передача принята, он знает, что потребитель взял на себя ответственность за нее, а не просто позволяет ей находиться где-то в очереди - это очень похоже на разницу между тем, чтобы передать документ коллеге напрямую или просто положить его в её почтовый ящик и надеяться, что она получит его в ближайшее время. Поскольку класс SynchronousQueue не имеет емкости хранения, методы put и take будут блокироваться, за исключением ситуации, когда другой поток уже ожидает участия в передаче. Синхронные очереди, как правило, подходят только тогда, когда есть достаточное количество потребителей, которые почти всегда будут готовы принять передачу. 5.3.1 Пример: поиск в компьютере Одним из типов программ, поддающихся декомпозиции на производителей и потребителей, является агент, который сканирует локальные диски на наличие документов и индексирует их для последующего поиска, подобно Google Desktop или службе Windows Indexing. В классе DiskCrawler в листинге 5.8, показана задача-производитель, которая ищет иерархию файлов удовлетворяющих критерию индексации и помещает их имена в рабочую очередь; класс Indexer в листинге 5.8 демонстрирует пример задачи-потребителя, которая принимает имена файлов из очереди и индексирует их. public class FileCrawler implements Runnable { private final BlockingQueue } catch (InterruptedException e) { Thread.currentThread().interrupt(); } } private void crawl(File root) throws InterruptedException { File[] entries = root.listFiles(fileFilter); if (entries != null) { for (File entry : entries) if (entry.isDirectory()) crawl(entry); else if (!alreadyIndexed(entry)) fileQueue.put(entry); } } } public class Indexer implements Runnable { private final BlockingQueue } public void run() { try { while (true) indexFile(queue.take()); } catch (InterruptedException e) { Thread.currentThread().interrupt(); } } } Листинг 5.8 Задачи производителя и потребителя в приложении поиска на компьютере Шаблон “производитель-потребитель” предлагает дружественный к потокам способ декомпозиции проблемы поиска в компьютере в более простые компоненты. Факторинг 66 сканера файлов и индексирования в отдельные активности порождает лучше читаемый и повторно используемый код, чем в том случае, если бы действие было монолитным и выполняло обе операции; каждая из активностей отвечает за выполнение только одной задачи, и блокирующая очередь берёт на себя всё управление потоками, таким образом, код каждой активности становится проще и яснее. Шаблон “производитель-потребитель” также включает несколько преимуществ в повышении производительности. Производители и потребители могут выполняться одновременно; если один ограничен операциями ввода/вывода, а другой ограничен центральным процессором, одновременное выполнение улучшает общую пропускную способность, по сравнению с последовательным выполнением. Если активности производителя и потребителя параллелизуются в разной степени, их тесная связь снижает параллелизируемость по сравнению с менее параллелизуемыми активностями. В листинге 5.9 запускается несколько сканеров и индексаторов, каждый в своем потоке. Как и написано, потоки потребителя никогда не завершаются, что предотвращает завершение программы; мы рассмотрим несколько методов 66 В математике факторизация или факторинг — это декомпозиция объекта (например, числа, полинома или матрицы) в произведение других объектов или факторов, которые, будучи перемноженными, дают исходный объект. решения этой проблемы в главе 7. Хотя в этом примере используются явно управляемые потоки, многие проекты вида “производитель-потребитель” могут быть выражены с помощью фреймворка выполнения задач Executor , который сам использует шаблон “производитель-потребитель”. public static void startIndexing(File[] roots) { BlockingQueue FileFilter filter = new FileFilter() { public boolean accept(File file) { return true; } }; for (File root : roots) new Thread(new FileCrawler(queue, filter, root)).start(); for (int i = 0; i < N_CONSUMERS; i++) new Thread(new Indexer(queue)).start(); } Листинг 5.9 Запуск поиска в компьютере 5.3.2 Последовательное ограничение потока Все реализации блокирующих очередей в пакете java.util.concurrent содержат достаточную внутреннюю синхронизацию для безопасной публикации объектов от потока-производителя к потоку-потребителю. Для изменяемых объектов шаблон “производитель-потребитель” и блокирующие очереди облегчают последовательное ограничение потоков, в целях передачи прав владения на объекты от производителей к потребителям. Объект, ограниченный потоком, принадлежит исключительно одному потоку, но это право собственности может быть “передано” путем безопасной публикации, когда только один поток получит доступ к нему и гарантирует, что публикующий поток не получит доступ к объекту после передачи. Безопасная публикация гарантирует, что состояние объекта будет видно новому владельцу, и поскольку исходный владелец больше не будет к нему прикасаться, теперь объект будет ограничен новым потоком. Новый владелец может изменять его свободно, так как имеет к нему эксклюзивный доступ. Пулы объектов используют последовательное ограничение потока, “одалживая” объект запрашивающему потоку. Пока пул содержит достаточно внутренней синхронизации для безопасной публикации объекта пула, и пока клиенты сами не опубликуют объект пула или не будут использовать его после возвращения в пул, право владения может безопасно передаваться из потока в поток. Можно также использовать другие механизмы публикации для передачи права собственности на изменяемый объект, но необходимо убедиться, что только один поток получает передаваемый объект. Блокирующие очереди упрощают этот процесс; затратив немного больше усилий, тоже самое можно сделать с помощью атомарного метода remove класса ConcurrentMap или метода compareAndSet класса AtomicReference 5.3.3 Двусторонние очереди и кража работы В Java 6 также было добавлено еще два типа коллекций: интерфейсы Deque (произносится как «дек») и BlockingDeque , которые расширяют интерфейсы Queue и BlockingQueue . Интерфейс Deque - это двусторонняя очередь, которая позволяет эффективно вставлять и удалять элементы, как с головы, так и с хвоста. Реализации включают классы ArrayDeque и LinkedBlockingDeque Подобно тому, как блокирующие очереди “одалживают” себя с помощью шаблона “производитель-потребитель”, двусторонние очереди “одалживают” себя подобным образом, с помощью шаблона называемого “кражей работы” (work stealing). В дизайне “производитель-потребитель” используется одна общая рабочая очередь для всех потребителей; в дизайне “кража работы” у каждого потребителя есть своя собственная двусторонняя очередь. Если потребитель исчерпывает работу в своей собственной двусторонней очереди, он может “украсть” работу с хвоста чужой двусторонней очереди. “Кража работы” может быть более масштабируемой, чем традиционный дизайн “производитель- потребитель”, поскольку работники не конкурируют за общую рабочую очередь; большую часть времени они получают доступ только к своей собственной двусторонней очереди, уменьшая конкуренцию. Когда один работник должен получить доступ к очереди другого работника, он делает это с хвоста, а не с головы, что еще больше уменьшает конкуренцию. “Кража работы” хорошо подходит для проблем, в которых потребители также являются производителями - когда выполнение единицы работы, возможно, приведет к идентификации большего количества работы. Например, обработка страницы в веб-сканере обычно приводит к идентификации новых страниц для обхода. Аналогичным образом, многие алгоритмы исследования графов, например, такой как пометка кучи (heap) во время сборки мусора, могут быть эффективно распараллелены с помощью “кражи работы”. Когда работник определяет новую единицу работы, он помещает ее в конец своей собственной двусторонней очереди (или, в качестве альтернативы, в дизайне “совместного использования работы” (work sharing), перекидывает на другого работника); когда его двусторонняя очередь пустеет, он ищет работу в конце чужой двусторонней очереди, гарантируя таким образом, что каждый работник будет занят. |