Thursday, September 19, 2013

Многопоточные коллекции в Java

Начиная с версии Java 5 в пакете java.util.concurrent появились реализации коллекций для эффективной работы в многопоточных приложения. Эти коллекции используют различные неблокирующие алгоритмы для достижения высокой скорости чтения/записи значений. Синхронизированный доступ происходит крайне редко и в целом не влияет на производительность. Почти. В зависимости от реализации. :) Рассмотрению таких коллекций посвящен данный урок.

Со списками все просто: единственная существующая concurrent реализация - это CopyOnWriteArrayList. Из названия можно догадаться, как она работает - при изменении создается новая копия списка и, соответственно, происходит блокировка. При чтении блокировок нет. Следовательно, при частых операциях записи или удаления элементов работать будет медленнее, чем даже Collections.synchronizedList(), в котором блокируются все операции, но при этом нет копирования списка. На данном уроке Вы сможете на практике увидеть скороть и медлительность работы этой реализации. Вы напишите мультипоточное приложение, которое определит время чтения/записи значений в разные конкурентные списки.

Учитывая особенности работы CopyOnWriteArrayList, имеет смысл выбирать данную реализацию, только если Вам действительно необходим индексный доступ к элементам, либо в коллекции возможно хранение дубликатов. Данное утверждение справедливо не только к мультипоточным реализациям, а к любым спискам вообще. Если же элементы в коллекции уникальны, и Вам достаточно последовательного доступа, тогда вполне подойдет Set.

Concurrent реализаций интерфейса Set существует две. Первая - это CopyOnWriteArraySet. Свойства такие же, как и у аналогичного списка. Вторая реализация - это ConcurrentSkipListSet. Последняя основана на интересной структуре данных  - слоёный список (SkipList). Подробнее на русском языке Вы можете прочитать на algolist.ru и википедии. Я скажу лишь, что она представляет собой связный список, где вставка и удаление элементов происходит достаточно быстро. Такая структура данных также хорошо подходит для неблокирующего доступа несколькими потоками, ведь, например, для вставки достаточно заблокировать изменение двух соседних элементов в связном списке. В дополнении ко всему, набор ConcurrentSkipListSet хранит значения в отсортированном виде, реализуя интерфейс NavigableSet. При этом, конечно, не стоит забывать о Comparator-е, который будет сравнивать элементы, или интерфейсе Comparable, который они могут реализовывать.

Для использования Map в многопоточной среде существуют два класса - ConcurrentSkipListMap и ConcurrentHashMap. Первая реализация подобна аналогичной для Set. Вторая подобна HashMap, где все пространство значений разбито на независимые области, каждая из которых представляет собой хеш-таблицу. При вставке элемента блокируется только одна область, позволяя параллельные чтение/запись в другие области. Используя этот класс, необходимо помнить о занимаемой памяти, так как для эффектиной работы с несколькими потоками, количество и размеры этих областей быстро растут. Еще одним полезным свойством обоих этих Map есть то, что они реализуют интерфейс ConcurrentMap. В нем представлены методы на основе неблокирующих алгоритмов, позволяющие безопасным образом выполнять проверку и изменение значений в рамках одной атомарной операции. Подобным образом работают атомарные переменные, такие как AtomicInteger и др. Подробнее о них я рассказывал на втором уроке из курса Advanced Java Concurrency.

В качестве домашнего задания для данного урока предлагаю добавить немного “параллелизма” в приложение, написанное для предыдущих уроков:

  • Во-первых, добавьте параллельную загрузку всех праздников в отсортированный Set. Прочитав файл с помощью org.apache.commons.io.FileUtils.readLines(file, encoding), передайте различные области списка нескольким потокам, которые будут парсить праздники и добавлять их в Set.
  • Во-вторых, одновременно с загрузкой и парсингом праздников выполните подсчет количества праздников для каждого дня и каждого месяца. Для этого используйте отдельные Map для хранения того, сколько праздников будет в каждом дне и каждом месяце.
  • В результате выполнения программы выведите наиболее и наименее “праздничный” день, а также количество праздников в каждом месяце.

Ну и, конечно, видео данной урока:

Post a Comment