Elettracompany.com

Компьютерный справочник
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Concurrent collections java

Параллельные классы коллекций

ConcurrentHashMap и CopyOnWriteArrayList предлагают потокобезопасность и улучшенную масштабируемость

Серия контента:

Этот контент является частью # из серии # статей: Теория и практика Java

Этот контент является частью серии: Теория и практика Java

Следите за выходом новых статей этой серии.

Первым ассоциативным классом коллекций, который появился библиотеке классов Java, был Hashtable , который являлся частью JDK 1.0. Hashtable предоставлял легкую в использовании, потокобезопасную реализацию ассоциативной map-таблицы и, конечно, был удобен. Однако потокобезопасность обошлась дорого — все методы в Hashtable были синхронизированы. В то время за синхронизацию без конкуренции приходилось расплачиваться производительностью. Преемник Hashtable , HashMap , появившийся как часть Collections framework в JDK 1.2, решал проблему потокобезопасности, предоставляя несинхронизированный базовый класс и синхронизированное обрамление, Collections.synchronizedMap . Разделение базовой функциональности и потокобезопасности в Collections.synchronizedMap позволило получить синхронизацию пользователям, которым она была нужна, а тем, кому она не нужна, не приходилось платить за неё цену.

Упрощённый подход к синхронизации, использованный и в Hashtable и в synchronizedMap , — синхронизация каждого метода с Hashtable или с синхронизированным объектом обрамления Map — имеет два основных недостатка. Он является препятствием для масштабируемости, потому что к хеш-таблице может одновременно обращаться только один поток. Одновременно с этим, недостаточно обеспечить настоящую безопасность потоков, при этом множество распространённых составных операций всё ещё требует дополнительной синхронизации. Хотя простые операции вроде get() и put() могут выполняться безопасно без дополнительной синхронизации, существуют несколько распространённых последовательностей операций, таких как iterate или put-if-absent, которые всё же нуждаются во внешней синхронизации, чтобы избежать конкуренции за данные.

Условная потокобезопасность

Синхронизированные обрамления коллекций synchronizedMap и synchronizedList иногда называют условно потокобезопасными — все операции в отдельности потокобезопасны, но последовательности операций, где управляющий поток зависит от результатов предыдущих операций, могут быть причиной конкуренции за данные. Первый отрывок в Листинге 1 демонстрирует распросранённую идиому put-if-absent (запись-если-пусто) — если элемент ещё не существует в Map -таблице, добавить его. К сожалению, как уже говорилось, у другого потока существует возможность вставить значение с повторяющимся ключом между моментами возврата из метода containsKey() и вызова метода put() . Если вы хотите гарантировать, что вставка выполняется строго один раз, вам необходимо заключить пару выражений в синхронизированный блок, который синхронизируется с Map m .

Другие примеры в Листинге 1 связаны с повторением. В первом примере результаты List.size() могли стать недействительными во время выполнения цикла, потому что другой поток мог удалить элементы из списка. Если ситуация сложилась неудачно, и элемент был удален другим потоком сразу же после начала последнего повторения цикла, то List.get() возвратит null и doSomething() скорее всего выбросит NullPointerException . Что вам можно сделать, чтобы избежать этого? Если другой поток может обращаться к List , в то время, когда вы выполняете его перебор, вы должны заблокировать весь List на время перебора, заключив его в блок synchronized , синхронизирующийся с List l . Это решает проблемы с конкуренцией за данные, но в дальнейшем скажется на параллелизме, поскольку блокировка всего List во время перебора может надолго заблокировать доступ к списку другим потокам.

В Collections framework были введены итераторы для обхода списка или другой коллекции, которые оптимизируют процесс перебора элементов коллекции. Однако итераторы, реализованные в классах коллекций java.util , часто подвержены сбоям, что означает, что если один поток изменяет коллекцию в то время, когда другой пропускает её через Iterator , очередной вызов Iterator.hasNext() или Iterator.next() выбросит ConcurrentModificationException . Как и с предыдущим примером, если вы хотите предотвратить ConcurrentModificationException , вам надо целиком блокировать List в то время, когда вы выполняете повторения, заключив его внутрь блока synchronized , который синхронизируется с List l . (В качестве альтернативы, вы можете вызвать List.toArray() и делать перебор в массиве без синхронизации, но это может быть дорого, если список достаточно большой.)

Листинг 1. Типичный случай конкуренции в синхронизированных map-таблицах

Ложное чувство уверенности

Условная безопасность потоков, обеспечиваемая synchronizedList и synchronizedMap представляет скрытую угрозу — разработчики полагают, что, раз эти коллекции синхронизированы, значит, они полностью потокобезопасны, и пренебрегают должной синхронизацией составных операций. В результате, хотя эти программы и работают при лёгкой нагрузке, но при серьёзной нагрузке они могут начать выкидывать NullPointerException или ConcurrentModificationException .

Проблемы масштабируемости

Масштабируемость показывает, как меняется пропускная способность приложения при увеличении рабочей нагрузки и доступных вычислительных ресурсов. Масштабируемая программа может выдержать пропорционально большую нагрузку при большем количестве процессоров, памяти или пропускной способности ввода/вывода. Блокировка ресурса общего пользования ради монопольного доступа представляет собой проблему для масштабируемости — она не позволяет другим потокам получить доступ к этому ресурсу даже при наличии простаивающих процессоров для планирования этих потоков. Для достижения масштабируемости мы должны исключить или сократить нашу зависимость от монопольных блокировок ресурсов.

Ещё большая проблема с синхронизированным обрамлением коллекций и ранними классами Hashtable и Vector состоит в том, что они синхронизируются с единственной блокировкой. Это означает, что одновременно только один поток может иметь доступ к коллекции, и если один поток находится в процессе чтения Map -таблицы, все остальные потоки, которые хотят прочитать из неё или записать в неё, вынуждены ждать. Наиболее распространённые операции с Map -таблицей, get() и put() , могут требовать больших вычислений, чем это может показаться, — при обходе хеш-бакета в поисках специфического значения ключа get() может потребоваться вызов Object.equals() для большого количества кандидатов. Если функция hashCode() , используемая классом ключа, не распределяет значения равномерно по всему ряду хэшей или же имеет большое количество коллизий хэша, отдельные цепочки бакетов могут оказаться намного длиннее других, а прохождение длинной цепочки хэшей и вызов equals() на определённом проценте его элементов могут быть слишком медленными. Проблема высокой стоимости get() и put() при таких условиях выражается не только в том, что доступ будет медленным, но и в том, что всем другим потокам блокируется доступ к Map -таблице пока происходит обход этой цепочки хэшей.

Тот факт, что get() в некоторых случаях может требовать значительного времени на выполнение, ещё больше усугубляется проблемой условной безопасности потоков, обсуждавшейся выше. Условия конкуренции, иллюстрируемые в Листинге 1, часто делают необходимым, чтобы единичная блокировка коллекции удерживалась гораздо большее время, чем требуется на выполнение единичной операции. Если вы собираетесь удерживать блокировку коллекции в течение всего перебора, то другие потоки могут замереть в ожидании блокировки коллекции на длительное время.

Пример: Простая кэш-память

Одно из наиболее распространённых применений для Map в серверных приложениях — реализация кэш-памяти. Серверные приложения могут кэшировать содержимое файлов, сгенерированные страницы, результаты запросов к базам данных, деревья DOM, ассоциированные с анализируемыми XML-файлами и многие другие типы данных. Основное назначение кэш-памяти — сокращение времени обслуживания и увеличение пропускной способности за счёт использования результатов предыдущего вычисления. Типичная особенность рабочей нагрузки кэш-памяти состоит в том, что попадания встречаются гораздо чаще, чем обновления, поэтому (в идеале) кэш-память обеспечивает очень хорошую производительность для get() . Кэш-память, тормозящая производительность приложения, даже хуже, чем полное отсутствие кэш-памяти.

Если вы использовали synchronizedMap для реализации кэш-памяти, вы вносите в ваше приложение потенциальную проблему масштабируемости. Одновременно только один поток может иметь доступ к Map , и это распространяется на все потоки, которые могут извлекать значение из Map -таблицы, равно как и на потоки, которые желают вставить новую пару (key, value) в map-таблицу.

Сокращение размеров блокировок

Один из подходов к улучшению параллелизма HashMap при сохранении потокобезопасности состоит в том, чтобы обходиться без единой блокировки всей таблицы и использовать блокировки для каждого бакета хэшей (или, в более общем случае, пула блокировок, где каждая блокировка защищает несколько бакетов). Это означает, что сразу несколько потоков могут обращаться к различным частям Map одновременно, без соперничества за единственную на всю коллекцию блокировку. Этот подход сразу же улучшает масштабируемость операций вставки, извлечения и удаления. К сожалению, такой параллелизм имеет свою цену — сложнее становится реализовывать методы, работающие с целой коллекцией, такие как size() или isEmpty() , потому что для этого может потребоваться получение сразу множества блокировок или появляется риск вернуть неточный результат. Тем не менее, для ситуаций вроде реализации кэш-памяти это представляет разумный компромисс — операции извлечения и вставки часты, тогда как операции size() и isEmpty() — значитель менее частые.

ConcurrentHashMap

Класс ConcurrentHashMap из util.concurrent (который также появится в пакете java.util.concurrent в JDK 1.5) — это потокобезопасная реализация Map , предоставляющая намного большую степень параллелизма, чем synchronizedMap . Сразу много операций чтения могут почти всегда выполняться параллельно, одновременные чтения и записи могут обычно выполняться параллельно, а сразу несколько одновременных записей могут зачастую выполняться параллельно. (Соответственный класс ConcurrentReaderHashMap предлагает аналогичный параллелизм для множественных операций чтений, но допускает лишь одну активную операцию записи.) ConcurrentHashMap спроектирован для оптимизации операций извлечения; на деле, успешные операции get() обычно успешно выполняются безо всяких блокировок. Достижение потокобезопасности без блокировок является сложным и требует глубокого понимания деталей Модели Памяти Java (Java Memory Model). Реализация ConcurrentHashMap и остальная часть util.concurrent были в значительной степени проанализированы экспертами по параллелизму на предмет корректности и безопасности потоков. Мы рассмотрим детали реализации ConcurrentHashMap в статье в следующем месяце.

Читать еще:  Восстановить данные с флешки которая не определяется

ConcurrentHashMap добивается более высокой степени параллелизма, слегка смягчая обещания, которые даются тем, кто её вызывает. Операция извлечения возвратит значение, вставленное самой последней завершившейся операцией вставки, а также может возвратить значение, добавленное операцией вставки, выполняемой в настоящее время (но она никогда не возвратит бессмыслицы). Итераторы , возвращаемые ConcurrentHashMap.iterator() возвратят каждый элемент не более одного раза и никогда не выкинут ConcurrentModificationException , но могут отображать или не отображать вставки или удаления, имевшие место со времени, когда итератор был сконструирован. Блокировки целой таблицы не требуются (да и невозможны) для обеспечения потокобезопасности при переборе коллекции. ConcurrentHashMap может использоваться для замены synchronizedMap или Hashtable в любом приложении, которое не основано на способности делать блокировку всей таблицы для предотвращения модификаций.

Данные компромиссы позволяют ConcurrentHashMap обеспечивать намного более высокую масштабируемость, чем Hashtable , не ставя под угрозу его эффективность для широкого множества распространённых случаев, таких как кэш-память с общим доступом.

Насколько лучше?

Таблица 1 приблизительно показывает отличия в масштабируемости между Hashtable и ConcurrentHashMap . При каждом запуске n потоков параллельно выполняли жёсткий цикл, в котором они извлекали произвольные значения ключа из Hashtable или из ConcurrentHashMap при 80 процентах неуспеха, выполняя операцию put() , и 1 проценте успешных извлечений при выполнении remove() . Тесты проводились на двухпроцессорной системе на базе Xeon под управлением системы Linux. Данные показывают время выполнения в миллисекундах для 10,000,000 итераций, приведённые к однопоточному случаю для ConcurrentHashMap . Вы можете видеть, что производительность ConcurrentHashMap остаётся масштабируемой до множества потоков, тогда как производительность Hashtable почти сразу падает при наличии конкуренции за блокировку.

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

Таблица 1. Масштабируемость Hashtable по сравнению с ConcurrentHashMap

Yuriy Tkach Blog

A blog on software engineering, programming technologies, application design, and just simple, but yet interesting life problems.

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 для хранения того, сколько праздников будет в каждом дне и каждом месяце.
  • В результате выполнения программы выведите наиболее и наименее “праздничный” день, а также количество праздников в каждом месяце.

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

Concurrent Collections in Java

The Java collection classes provides a wide range of classes and interfaces that makes our life simple and our code elegant.

However, most of these classes are not thread-safe and one must be careful while implementing them in a multi-threaded environment. Several new Collection classes are added in Java 5 and Java 6 specially concurrent alternatives of standard synchronized ArrayList, HashTable and synchronized HashMap collection classes.

Iterator fail-safe property work with the clone of underlying collection, hence it’s not affected by any modification in the collection. By design, all the collection classes in java.util package are fail-fast whereas collection classes in java.util.concurrent are fail-safe.
Fail-fast iterators throw ConcurrentModificationException whereas fail-safe iterator never throws ConcurrentModificationException

Here we discuss the most commonly used concurrent collections that are part of the java.util.concurrent package.

ConcurrentHashMap

ConcurrentHashMap provides a concurrent alternative of HashTable or Synchronized Map classes with aim to support higher level of concurrency by implementing fined grained locking. Multiple reader can access the Map concurrently while a portion of Map gets locked for write operation depends upon concurrency level of Map. ConcurrentHashMap provides better scalability than there synchronized counter part. Iterator of ConcurrentHashMap are fail-safe iterators which doesn’t throw ConcurrentModificationException thus eliminates another requirement of locking during iteration which result in further scalability and performance.

Here is a brilliant writeup explaining the difference between a HashMap and ConcurrentHashMap.

CopyOnWriteArrayList and CopyOnWriteArraySet

CopyOnWriteArrayList is a concurrent alternative of synchronized List. CopyOnWriteArrayList provides better concurrency than synchronized List by allowing multiple concurrent reader and replacing the whole list on write operation. Yes, write operation is costly on CopyOnWriteArrayList but it performs better when there are multiple reader and requirement of iteration is more than writing. Since CopyOnWriteArrayList Iterator also don’t throw ConcurrentModificationException it eliminates need to lock the collection during iteration. Remember both ConcurrentHashMap and CopyOnWriteArrayList doesn’t provides same level of locking as Synchronized Collection and achieves thread-safety by there locking and mutability strategy. So they perform better if requirements suits there nature. Similarly, CopyOnWriteArraySet is a concurrent replacement to Synchronized Set.

Читать еще:  Можно ли восстановить удаленные сообщения в вк

Here is a brilliant writeup explaining the difference between a ArrayList and CopyOnWriteArrayList.

BlockingQueue

BlockingQueue is also one of better known collection class in Java 5. BlockingQueue makes it easy to implement producer-consumer design pattern by providing inbuilt blocking support for put() and take() method. put() method will block if Queue is full while take() method will block if Queue is empty. Java 5 API provides two concrete implementation of BlockingQueue in form of ArrayBlockingQueue and LinkedBlockingQueue, both of them implement FIFO ordering of element. ArrayBlockingQueue is backed by Array and its bounded in nature while LinkedBlockingQueue is optionally bounded. Consider using BlockingQueue to solve producer Consumer problem in Java instead of writing your won wait-notify code. Java 5 also provides PriorityBlockingQueue, another implementation of BlockingQueue which is ordered on priority and useful if you want to process elements on order other than FIFO.

This concept is well explained in these set of tutorials by Jenkov : BlockingQueue , ArrayBlockingQueue , LinkedBlockingQueue and PriorityBlockingQueue.

Thanks. I will keep on adding more concurrent collections here.

ConcurrentSkipListSet в Java с примерами

Класс ConcurrentSkipListSet в Java является частью Java Collection Framework и реализует интерфейс Collection и класс AbstractSet . Он предоставляет масштабируемую и параллельную версию NavigableSet в Java . Реализация ConcurrentSkipListSet основана на ConcurrentSkipListMap. Элементы в ConcurrentSkipListSet сортируются по умолчанию в их естественном порядке.

Конструкторы в Java ConcurrentSkipListSet:

  • ConcurrentSkipListSet () : этот конструктор используется для создания пустого набора.
  • ConcurrentSkipListSet (Collection c) : этот конструктор используется для создания набора с элементами коллекции, переданными в качестве параметра.
  • ConcurrentSkipListSet (Comparator компаратор) : этот конструктор используется для создания нового пустого набора, который упорядочивает свои элементы в соответствии с указанным компаратором.
  • ConcurrentSkipListSet (SortedSet s) : этот конструктор используется для создания нового набора, содержащего те же элементы и использующего тот же порядок, что и указанный отсортированный набор.

Ниже приведен пример программы для иллюстрации ConcurrentSkipListSet в Java:

// Java-программа для демонстрации ConcurrentSkipListSet

public static void main(String[] args)

// Инициализация набора с использованием ConcurrentSkipListSet ()

set = new ConcurrentSkipListSet ();

// Добавление элементов в этот набор

// Инициализация набора с использованием

set1 = new ConcurrentSkipListSet (set);

Методы в Java ConcurrentSkipListSet:

  1. add (E e) : этот метод добавляет указанный элемент в этот набор, если он еще не существует.
  2. потолок (E e) : этот метод возвращает наименьший элемент в этом наборе, больший или равный данному элементу, или ноль, если такого элемента нет.
  3. clear () : этот метод удаляет все элементы из этого набора.
  4. clone () : этот метод возвращает поверхностную копию этого экземпляра ConcurrentSkipListSet.
  5. comptor (): этот метод возвращает компаратор, используемый для упорядочения элементов в этом наборе, или ноль, если этот набор использует естественное упорядочение своих элементов.
  6. Содержит (Object o) : этот метод возвращает true, если этот набор содержит указанный элемент.
  7. downndingIterator () : этот метод возвращает итератор для элементов этого набора в порядке убывания.
  8. downndingSet () : этот метод возвращает представление в обратном порядке элементов, содержащихся в этом наборе.
  9. equals (Object o) : этот метод сравнивает указанный объект с этим набором на равенство.
  10. first () : этот метод возвращает первый (самый низкий) элемент, находящийся в данный момент в этом наборе.
  11. floor (E e) : этот метод возвращает наибольший элемент в этом наборе, меньший или равный данному элементу, или ноль, если такого элемента нет.
  12. headSet (E toElement) : этот метод возвращает представление части этого набора, элементы которой строго меньше, чем toElement.
  13. headSet (E toElement, boolean inclusive) : этот метод возвращает представление части этого набора, элементы которой меньше (или равны, если inclusive is true) toElement.
  14. upper (E e) : этот метод возвращает наименьший элемент в этом наборе, строго превышающий заданный элемент, или ноль, если такого элемента нет.
  15. isEmpty () : этот метод возвращает true, если этот набор не содержит элементов.
  16. iterator () : этот метод возвращает итератор для элементов этого набора в порядке возрастания.
  17. last (): этот метод возвращает последний (самый высокий) элемент в настоящее время в этом наборе.
  18. lower (E e) : этот метод возвращает наибольший элемент в этом наборе строго меньше, чем данный элемент, или ноль, если такого элемента нет.
  19. pollFirst () : этот метод извлекает и удаляет первый (самый низкий) элемент или возвращает ноль, если этот набор пуст.
  20. pollLast () : этот метод извлекает и удаляет последний (самый высокий) элемент или возвращает ноль, если этот набор пуст.
  21. remove (Object o) : Этот метод удаляет указанный элемент из этого набора, если он присутствует.
  22. removeAll (Collection c) : этот метод удаляет из этого набора все его элементы, которые содержатся в указанной коллекции.
  23. size () : этот метод возвращает количество элементов в этом наборе.
  24. spliterator () : этот метод возвращает Spliterator над элементами этого набора.
  25. subSet (E fromElement, логическое значение fromInclusive, E toElement, логическое значение toInclusive) : этот метод возвращает представление части этого набора, элементы которого варьируются от fromElement до toElement.
  26. subSet (E fromElement, E toElement) : Этот метод возвращает представление части этого набора, элементы которого варьируются от fromElement, включительно, до toElement, эксклюзив.
  27. tailSet (E fromElement): этот метод возвращает представление части этого набора, элементы которой больше или равны fromElement.
  28. tailSet (E fromElement, boolean inclusive) : Этот метод возвращает представление части этого набора, элементы которой больше (или равны, если inclusive is true) fromElement.

// Java-программа для демонстрации ConcurrentSkipListSet

public static void main(String[] args)

// Инициализация набора с использованием ConcurrentSkipListSet ()

set = new ConcurrentSkipListSet ();

// Добавление элементов в этот набор

// используя метод add ()

// Печать самого высокого элемента набора

// используя метод last ()

System.out.println( «The highest element of the set: «

// Извлечение и удаление первого элемента набора

Java concurrency (multi-threading) — Tutorial

1. Concurrency

1.1. What is concurrency?

Concurrency is the ability to run several programs or several parts of a program in parallel. If a time consuming task can be performed asynchronously or in parallel, this improve the throughput and the interactivity of the program.

A modern computer has several CPU’s or several cores within one CPU. The ability to leverage these multi-cores can be the key for a successful high-volume application.

1.2. Process vs. threads

A process runs independently and isolated of other processes. It cannot directly access shared data in other processes. The resources of the process, e.g. memory and CPU time, are allocated to it via the operating system.

A thread is a so called lightweight process. It has its own call stack, but can access shared data of other threads in the same process. Every thread has its own memory cache. If a thread reads shared data it stores this data in its own memory cache. A thread can re-read the shared data.

A Java application runs by default in one process. Within a Java application you work with several threads to achieve parallel processing or asynchronous behavior.

2. Improvements and issues with concurrency

2.1. Limits of concurrency gains

Within a Java application you work with several threads to achieve parallel processing or asynchronous behavior. Concurrency promises to perform certain task faster as these tasks can be divided into subtasks and these subtasks can be executed in parallel. Of course the runtime is limited by parts of the task which can be performed in parallel.

The theoretical possible performance gain can be calculated by the following rule which is referred to as Amdahl’s Law.

If F is the percentage of the program which can not run in parallel and N is the number of processes, then the maximum performance gain is 1 / (F+ ((1-F)/n)).

2.2. Concurrency issues

Threads have their own call stack, but can also access shared data. Therefore you have two basic problems, visibility and access problems.

Читать еще:  Как зайти в восстановление системы windows 7

A visibility problem occurs if thread A reads shared data which is later changed by thread B and thread A is unaware of this change.

An access problem can occur if several thread access and change the same shared data at the same time.

Visibility and access problem can lead to

Liveness failure: The program does not react anymore due to problems in the concurrent access of data, e.g. deadlocks.

Safety failure: The program creates incorrect data.

3. Concurrency in Java

3.1. Processes and Threads

A Java program runs in its own process and by default in one thread. Java supports threads as part of the Java language via the Thread code. The Java application can create new threads via this class.

Java 1.5 also provides improved support for concurrency with the in the java.util.concurrent package.

3.2. Locks and thread synchronization

Java provides locks to protect certain parts of the code to be executed by several threads at the same time. The simplest way of locking a certain method or Java class is to define the method or class with the synchronized keyword.

The synchronized keyword in Java ensures:

that only a single thread can execute a block of code at the same time

that each thread entering a synchronized block of code sees the effects of all previous modifications that were guarded by the same lock

Synchronization is necessary for mutually exclusive access to blocks of and for reliable communication between threads.

You can use the synchronized keyword for the definition of a method. This would ensure that only one thread can enter this method at the same time. Another threads which is calling this method would wait until the first threads leaves this method.

You can also use the synchronized keyword to protect blocks of code within a method. This block is guarded by a key, which can be either a string or an object. This key is called the lock.

All code which is protected by the same lock can only be executed by one thread at the same time

For example the following datastructure will ensure that only one thread can access the inner block of the add() and next() methods.

3.3. Volatile

If a variable is declared with the volatile keyword then it is guaranteed that any thread that reads the field will see the most recently written value. The volatile keyword will not perform any mutual exclusive lock on the variable.

As of Java 5 write access to a volatile variable will also update non-volatile variables which were modified by the same thread. This can also be used to update values within a reference variable, e.g. for a volatile variable person. In this case you must use a temporary variable person and use the setter to initialize the variable and then assign the temporary variable to the final variable. This will then make the address changes of this variable and the values visible to other threads.

4. The Java memory model

4.1. Overview

The Java memory model describes the communication between the memory of the threads and the main memory of the application.

It defines the rules how changes in the memory done by threads are propagated to other threads.

The Java memory model also defines the situations in which a thread re-fresh its own memory from the main memory.

It also describes which operations are atomic and the ordering of the operations.

4.2. Atomic operation

An atomic operation is an operation which is performed as a single unit of work without the possibility of interference from other operations.

The Java language specification guarantees that reading or writing a variable is an atomic operation(unless the variable is of type long or double ). Operations variables of type long or double are only atomic if they declared with the volatile keyword.

Assume i is defined as int . The i++ (increment) operation it not an atomic operation in Java. This also applies for the other numeric types, e.g. long. etc).

The i++ operation first reads the value which is currently stored in i (atomic operations) and then it adds one to it (atomic operation). But between the read and the write the value of i might have changed.

Since Java 1.5 the java language provides atomic variables, e.g. AtomicInteger or AtomicLong which provide methods like getAndDecrement() , getAndIncrement() and getAndSet() which are atomic.

4.3. Memory updates in synchronized code

The Java memory model guarantees that each thread entering a synchronized block of code sees the effects of all previous modifications that were guarded by the same lock.

5. Immutability and Defensive Copies

5.1. Immutability

The simplest way to avoid problems with concurrency is to share only immutable data between threads. Immutable data is data which cannot changed.

To make a class immutable make

all its fields final

the class declared as final

the this reference is not allowed to escape during construction

Any fields which refer to mutable data objects are

have no setter method

they are never directly returned of otherwise exposed to a caller

if they are changed internally in the class this change is not visible and has no effect outside of the class

An immutable class may have some mutable data which is uses to manages its state but from the outside this class nor any attribute of this class can get changed.

For all mutable fields, e.g. Arrays, that are passed from the outside to the class during the construction phase, the class needs to make a defensive-copy of the elements to make sure that no other object from the outside still can change the data

5.2. Defensive Copies

You must protect your classes from calling code. Assume that calling code will do its best to change your data in a way you didn’t expect it. While this is especially true in case of immutable data it is also true for non-immutable data which you still not expect that this data is changed outside your class.

To protect your class against that you should copy data you receive and only return copies of data to calling code.

The following example creates a copy of a list (ArrayList) and returns only the copy of the list. This way the client of this class cannot remove elements from the list.

6. Threads in Java

The base means for concurrency are is the java.lang.Threads class. A Thread executes an object of type java.lang.Runnable .

Runnable is an interface with defines the run() method. This method is called by the Thread object and contains the work which should be done. Therefore the «Runnable» is the task to perform. The Thread is the worker who is doing this task.

The following demonstrates a task (Runnable) which counts the sum of a given range of numbers. Create a new Java project called de.vogella.concurrency.threads for the example code of this section.

The following example demonstrate the usage of the Thread and the Runnable class.

Using the Thread class directly has the following disadvantages.

Creating a new thread causes some performance overhead.

Too many threads can lead to reduced performance, as the CPU needs to switch between these threads.

You cannot easily control the number of threads, therefore you may run into out of memory errors due to too many threads.

The java.util.concurrent package offers improved support for concurrency compared to the direct usage of Threads . This package is described in the next section.

7. Threads pools with the Executor Framework

Thread pools manage a pool of worker threads. The thread pools contains a work queue which holds tasks waiting to get executed.

A thread pool can be described as a collection of Runnable objects.

Ссылка на основную публикацию
Adblock
detector