• Главная
    • /
  • Блог
    • /
  • Теорія і практика Java: Введення в неблокірующіх алгоритми

Теорія і практика Java: Введення в неблокірующіх алгоритми

  1. Серія контенту:
  2. Цей контент є частиною серії: Теорія і практика Java
  3. неблокуючий лічильник
  4. Лістинг 1. Потокозащіщенний лічильник, який використовує синхронізацію
  5. Лістинг 2. Неблокуючий лічильник, який використовує CAS
  6. неблокуючий стек
  7. Лістинг 3. Неблокуючий стек, який використовує алгоритм Трайбер (Treiber)
  8. Неблокуючий зв'язний список
  9. Лістинг 4. Вставка в неблокірующіх алгоритмі черзі Майкла-Скотта
  10. Малюнок 1. Черга з двома елементами в статичному стані
  11. Малюнок 2. Черга в проміжному стані під час операції вставки після додавання елемента, але перед оновленням...
  12. Малюнок 3. Черга знову знаходиться в статичному стані після поновлення покажчика на "хвіст" черги
  13. резюме
  14. Ресурси для скачування

Теорія і практика Java

Дивіться, блоків немає!

Серія контенту:

Цей контент є частиною # з серії # статей: Теорія і практика Java

https://www.ibm.com/developerworks/ru/views/global/libraryview.jsp?series_title_by=Теория+и+практика+java

Слідкуйте за виходом нових статей цієї серії.

Цей контент є частиною серії: Теорія і практика Java

Слідкуйте за виходом нових статей цієї серії.

Коли до розділяється змінної звертаються кілька потоків, всі вони повинні використовувати синхронізацію, в іншому випадку може виникнути нехороша ситуація. Головним засобом синхронізації в мові програмування Java є ключове слово synchronized (цей спосіб синхронізації відомий також під назвою внутрішня блокування (intrinsic locking)), яке забезпечує взаємне виключення і гарантує, що дії одного потоку, що виконує блок synchronized, видимі для інших потоків, які будуть виконувати блок synchronized, захищений цієї ж блокуванням. При правильному застосуванні внутрішня блокування дозволяє зробити наші програми потокозащіщеннимі, але вона може бути великовагової операцією при використанні для захисту маленьких ділянок коду, коли потоки часто змагаються за блокування.

У статті " Going atomic "Ми розглянули атомарні змінні (atomic variable), які надають атомарні операції читання-зміна-запис для безпечного зміни поділюваних змінних без блокувань. Атомарні змінні аналогічні по семантиці використання пам'яті змінним volatile, але оскільки вони також можуть змінюватися автоматично, їх можна використовувати в якості бази для вільних від блокувань паралельних алгоритмів.

неблокуючий лічильник

Counter в лістингу 1 є потокозащіщенним, але необхідність використання блокувань дратує деяких розробників, тому що вони знижують продуктивність. Однак блокування необхідна, оскільки инкрементирование, хоча і виглядає однією операцією, є скороченим записом трьох окремих операцій: витяг значення, додавання одиниці і запис значення. Синхронізація необхідна також в методі getValue для гарантії того, що викликають цей метод потоки бачать найновіше значення. Просте ігнорування необхідності блокування не є хорошою стратегією, хоча багато розробників продовжують переконувати себе в допустимості такого підходу.

При одночасному запиті декількома потоками однієї і тієї ж блокування один виграє і захоплює блокування, інші чекають своєї черги. JVM зазвичай реалізують блокування шляхом зупинки блокується потоку і подальшого його продовження. Отримується перемикання контексту може викликати суттєві затримки в порівнянні з невеликою кількістю команд, захищених блокуванням.

Лістинг 1. Потокозащіщенний лічильник, який використовує синхронізацію
public final class Counter {private long value = 0; public synchronized long getValue () {return value; } Public synchronized long increment () {return ++ value; }}

Клас NonblockingCounter в лістингу 2 демонструє один з найпростіших неблокірующіх алгоритмів: лічильник AtomicInteger, що використовує метод compareAndSet () (CAS). Метод compareAndSet () означає "Оновити змінну цим новим значенням, але відмовити, якщо інший потік змінив значення після мого останнього перегляду" (див. В статті " Going atomic "Докладне пояснення атомарних змінних і функції порівняти-і-встановити).

Лістинг 2. Неблокуючий лічильник, який використовує CAS
public class NonblockingCounter {private AtomicInteger value; public int getValue () {return value.get (); } Public int increment () {int v; do {v = value.get (); while (! value.compareAndSet (v, v + 1)); return v + 1; }}

Класи атомарних змінних називаються атомарними, тому що вони надають дрібномодульні атомарні поновлення чисел і об'єктних посилань, але вони також атомарний і в тому сенсі, що є основними будівельними блоками для неблокірующіх алгоритмів. Неблокірующіх алгоритми є предметом вивчення вже більше 20 років, але стали можливими в мові програмування Java тільки з появою Java 5.0.

Сучасні процесори мають спеціальні інструкції для атомарного поновлення поділюваних даних, які можуть виявити втручання інших потоків, і compareAndSet () використовує їх замість блокування. Якщо все що нам потрібно - це інкрементіровать лічильник, AtomicInteger пропонує методи для инкрементирования, але вони засновані на compareAndSet (), наприклад, NonblockingCounter.increment ().

Неблокірующіх версія має деякі переваги в продуктивності по відношенню до версії, заснованої на блокування. Вона виконує синхронізацію на більш низькому рівні модульності (конкретне місце в пам'яті), використовуючи апаратний примітив замість фрагмента коду блокування JVM. Ті, хто програв потоки можуть виконати повторну спробу негайно, без зупинки і продовження. Менша модульність зменшує шанс виникнення змагання, а можливість повторення спроби без зупинки і продовження зменшує вартість змагання.

NonblockingCounter - це, можливо, простий приклад, але він демонструє основну характеристику всіх неблокірующіх алгоритмів - певний крок алгоритму виконується гіпотетично, з усвідомленням того, що він повинен бути виконаний повторно, якщо операція CAS закінчилася невдало. Неблокірующіх алгоритми часто називають оптимістичними, тому що вони виконуються з припущенням про те, що не буде конфліктних ситуацій. Якщо така ситуація виникає, вони повертаються на крок назад і повторюють дію. У разі з лічильником гіпотетичним кроком є ​​операція инкрементирования - вона витягує і додає одиницю до старого значенням в надії на те, що воно не зміниться за час обчислення оновленого значення. Якщо це не так, вона повинна повторно отримати значення і знову виконати инкрементирование.

неблокуючий стек

Менш тривіальний приклад неблокуючим алгоритму ConcurrentStack приведений в лістингу 3. Операції push () і pop () в ConcurrentStack подібні за структурою операції increment () в NonblockingCounter. Вони гіпотетично виконують певну роботу і сподіваються на те, що передбачувані припущення не будуть порушені, коли прийде час "підтвердити" роботу. Метод push () переглядає поточний верхній елемент, створює новий елемент, який треба помістити в стек, і, потім, якщо самий верхній елемент не був змінений з часу останнього перегляду, поміщає новий елемент в стек. Якщо CAS завершується невдало - значить інший потік змінив стек, тому процес виконується знову.

Лістинг 3. Неблокуючий стек, який використовує алгоритм Трайбер (Treiber)
public class ConcurrentStack <E> {AtomicReference <Node <E >> head = new AtomicReference <Node <E >> (); public void push (E item) {Node <E> newHead = new Node <E> (item); Node <E> oldHead; do {oldHead = head.get (); newHead.next = oldHead; } While (! Head.compareAndSet (oldHead, newHead)); } Public E pop () {Node <E> oldHead; Node <E> newHead; do {oldHead = head.get (); if (oldHead == null) return null; newHead = oldHead.next; } While (! Head.compareAndSet (oldHead, newHead)); return oldHead.item; } Static class Node <E> {final E item; Node <E> next; public Node (E item) {this.item = item; }}}

аналіз продуктивності

При слабкої або середньої конкуренції неблокірующіх алгоритми перевершують по продуктивності блокують, оскільки найбільшу частину часу CAS витрачає на першу спробу, і при виникненні змагання час витрачається не на зупинку потоку і перемикання контексту, а тільки на кілька ітерацій циклу. Незадоволена операція CAS менш затратна, ніж незадоволений запит на блокування (це твердження має бути істинним тому, що незадоволений запит на блокування включає в себе CAS плюс додаткову обробку), і незадоволена операція CAS має меншу затримку.

В умовах жорсткої конкуренції (коли безліч потоків звертаються до одного місця в пам'яті) засновані на блокування алгоритми починають пропонувати кращу продуктивність, ніж неблокірующіх, оскільки при блокуванні потоку він припиняє спроби достукатися до ресурсу і терпляче чекає своєї черги, зменшуючи конкуренцію. Однак конкуренція такого високого рівня - це незвичайна ситуація, оскільки основну частину часу потоки чергують локальні обчислення з операціями, які вимагають поділюваних даних, даючи іншим потокам шанс використовувати ці колективні дані. Високий рівень конкуренції вказує також на те, що потрібно подумати про зміну вашого алгоритму в сторону меншого використання поділюваних даних. Граф в статті " Going atomic "Трохи збивав з пантелику, оскільки аналізована програма мала настільки нереалістично високу конкуренцію, що здавалося, ніби блокування мають перевагу навіть для невеликого числа потоків.

Неблокуючий зв'язний список

Розглянуті приклади (лічильник і стек) є дуже простими неблокірующіх алгоритмами і легко реалізуються, якщо ви вловили схему використання CAS в циклі. Для більш складних структур даних неблокірующіх алгоритми набагато ускладнюються в порівнянні з цими прикладами, оскільки зміна зв'язного списку, дерева або хеш-таблиці може вимагати зміни більше одного покажчика. CAS дозволяє атомарні умовні поновлення одного покажчика, але не двох. Тому, для створення неблокірующіх зв'язного списку, дерева або хеш-таблиці ми повинні знайти спосіб зміни декількох покажчиків за допомогою CAS, що не залишає структуру даних в суперечливому стані.

Операція вставки елемента в хвіст зв'язного списку зазвичай включає в себе оновлення двох покажчиків: покажчика "хвіст", який завжди посилається на останній елемент списку, і покажчика "наступний" попереднього останнього елемента, що посилається на новий вставляється елемент. Оскільки потрібно оновити два покажчика, необхідні дві операції CAS. Оновлення двох покажчиків в різних операціях CAS призводить до виникнення двох потенційних проблем, які потрібно враховувати: що станеться, якщо перша CAS виконається нормально, а друга невдало, і що станеться, якщо інший потік спробує звернутися до списку між першою і другою операціями CAS.

"Трюк" при створенні неблокірующіх алгоритмів для не тривіальне структур даних полягає в гарантуванні постійного несуперечливого стану структури даних навіть під час між початком зміни даних потоком і його завершенням, а також в гарантуванні того, щоб інші потоки могли не тільки знати, завершив чи перший потік своє оновлення або все ще перебуває в середині цієї операції, але також і те, які операції могли б знадобитися для завершення оновлення, якщо перший потік кудись пішов. Якщо потік почав роботу зі структурою даних, що знаходиться в середині операції поновлення, він може "допомогти" вже виконує оновлення потоку завершити оновлення і потім виконати свою власну операцію. Коли перший потік збереться спробувати завершити своє власне оновлення, він дізнається, що ця робота більше не потрібна і поверне управління, оскільки CAS виявить втручання (в даному випадку конструктивне втручання) допомагає потоку.

Ця вимога "допоможи сусідові" необхідно для того, щоб зробити структуру даних захищеної від невдач конкретних потоків. Якщо потік виявить, що структура даних знаходиться на середині операції поновлення іншим потоком, і просто чекатиме завершення цієї операції, то він може очікувати вічно в разі, якщо цей інший потік завершився аварійно. Навіть при відсутності аварій такий підхід мав би низьку продуктивність, оскільки новий набув чинності потік повинен був би витрачати процесорний час, в тому числі на перемикання контексту, або чекати певний час, що навіть ще гірше.

LinkedQueue в лістингу 4 демонструє операцію вставки для неблокуючим алгоритму черги Майкла-Скотта (Michael-Scott), реалізованого ConcurrentLinkedQueue:

Лістинг 4. Вставка в неблокірующіх алгоритмі черзі Майкла-Скотта
public class LinkedQueue <E> {private static class Node <E> {final E item; final AtomicReference <Node <E >> next; Node (E item, Node <E> next) {this.item = item; this.next = new AtomicReference <Node <E >> (next); }} Private AtomicReference <Node <E >> head = new AtomicReference <Node <E >> (new Node <E> (null, null)); private AtomicReference <Node <E >> tail = head; public boolean put (E item) {Node <E> newNode = new Node <E> (item, null); while (true) {Node <E> curTail = tail.get (); Node <E> residue = curTail.next.get (); if (curTail == tail.get ()) {if (residue == null) / * A * / {if (curTail.next.compareAndSet (null, newNode)) / * C * / {tail.compareAndSet (curTail, newNode) / * D * /; return true; }} Else {tail.compareAndSet (curTail, residue) / * B * /; }}}}}

Як і в багатьох алгоритмах черзі, порожня чергу складається з одного фіктивного елементу. Покажчик "голови" черги завжди посилається на фіктивний елемент; Покажчик "хвоста" черги завжди вказує або на останній елемент, або на другий від кінця елемент. На малюнку 1 зображена чергу з двома елементами в нормальних умовах:

Малюнок 1. Черга з двома елементами в статичному стані

Як показано в лістингу 4 , Вставка елемента вимагає поновлення двох покажчиків, обидва з яких виробляються операціями CAS: зв'язування нового елемента з поточним останнім елементом черги (C) і перемикання покажчика "хвоста" черги на новий останній елемент. Якщо перша операція завершується невдало - стан черги не зміниться, і потік буде продовжувати спроби вставки елемента. Після вдалого виконання цього кроку вважається, що операція вставки мала місце, і інші потоки можуть побачити зміна. Все ще потрібно перемикання покажчика "хвоста" черги на новий елемент, але ця операція може розглядатися як свого роду "зачистка", оскільки будь-який потік, який приступає до роботи з чергою, може сказати, чи потрібна така зачистка, і знає, як її виконати .

Черга завжди знаходиться в одному з двох станів: нормальному, або статичному (малюнки 1 і 3 ), Або проміжному ( малюнок 2 ). Черга знаходиться в статичному стані перед операцією вставки і після успішної другої операції CAS (D); вона знаходиться в проміжному стані після успішної першої операції CAS (C). У статичному стані поле next елемента, на який вказує "хвіст" черги, завжди одно null; в проміжному стані - НІКОЛИ НЕ МАЄ null. Будь потік може побачити, в якому стані знаходиться чергу, порівнявши значення tail.next з null. У цьому полягає суть дозволу потокам допомагати іншим потокам "завершувати" свої операції.

Малюнок 2. Черга в проміжному стані під час операції вставки після додавання елемента, але перед оновленням покажчика на "хвіст" черги

Операція вставки спочатку перевіряє, чи знаходиться чергу в проміжному стані перед спробою вставки нового елемента (A), як показано в лістингу 4 . Якщо це так, значить якийсь інший потік повинен знаходитися в середині операції вставки елемента між кроками (C) і (D). Замість очікування завершення іншого потоку поточний потік може "допомогти" завершити операцію за нього за допомогою переміщення вперед покажчика на "хвіст" черги (B). Він продовжує перевірку покажчика "хвоста" черги і пересуває його при необхідності до тих пір, поки черга не перейде в статичний стан, після чого він може почати свою власну операцію вставки.

Перша операція CAS (C) може завершитися невдало, оскільки два потоки можуть конкурувати за доступ до поточного останнього елемента черги; в цій ситуації не виконується ніяких змін, і цей потік знову читає покажчик "хвоста" черги і намагається виконати операцію. Якщо невдало завершується друга операція CAS (D), вставляють потік може не намагатися виконати її повторно, оскільки другий потік завершив цю операцію на кроці (B)!

Малюнок 3. Черга знову знаходиться в статичному стані після поновлення покажчика на "хвіст" черги

Неблокірующіх алгоритми в дії

Якщо ви заглибитися в нетрі JVM і OS, то виявите неблокірующіх алгоритми повсюдно. Складальник сміття використовує їх для прискорення паралельних операцій складання сміття; планувальник використовує їх для ефективного планування потоків і процесів і для реалізації внутрішньої блокування. В Mustang (Java 6.0) заснований на блокування алгоритм SynchronousQueue замінений новою неблокірующіх версією. Мало хто розробники використовують SynchronousQueue безпосередньо, але вона застосовується в якості робочої черги для пулів потоків, створених фабрикою Executors.newCachedThreadPool (). Тести продуктивності пулу кеш потоків показують приблизно трикратне збільшення швидкості роботи в порівнянні з поточною реалізацією. Плануються і подальші поліпшення в наступній за Mustang версії під кодовою назвою Dolphin.

резюме

Неблокірующіх алгоритми більш СКЛАДНІ в порівнянні з Заснований на Блокування. Розробка неблокірующіх алгоритмів - це Досить спеціалізована галузь, и может буті Надзвичайно Важко довести їх коректність. Однак багато поліпшень продуктивності паралельних процесів в версіях Java має місце при використанні неблокірующіх алгоритмів, і, оскільки продуктивність паралельних операцій стає все більш важливою, очікуйте побачити ще більше неблокірующіх алгоритмів в майбутніх версіях платформи Java.

Ресурси для скачування

Схожі теми

  • Оригінал статті " Java theory and practice: Introduction to nonblocking algorithms ".
  • " Going atomic "(DeveloperWorks, Brian Goetz, листопад 2004): Описує атомарні класи змінних, додані в Java 5.0 і операцію порівняння-і-заміна (CAS).
  • " Масштабуються синхронні черзі "(ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, William N. Scherer III, Doug Lea, and Michael L. Scott, березень 2006): Описує створення і переваги по продуктивності нової реалізації SynchronousQueue в Java 6.
  • " Прості, швидкі і практичні неблокірующіх і блокують паралельні черги "(Maged M. Michael і Michael L. Scott, Symposium on Principles of Distributed Computing, 1996): Подробиці створення неблокірующіх однозв'язної черзі, розглянутої в лістингу 4 даної статті.
  • " Паралельність Java на практиці "(Addison-Wesley Professional, Brian Goetz, Tim Peierls, Joshua Bloch, Joseph Bowbeer, David Holmes і Doug Lea, червень 2006 року): Керівництво" how-to "по розробці паралельних програм на мові Java, в тому числі, створення і компоновка потокозащіщенних класів і програм, рішення проблем живучості, управління продуктивністю і тестування паралельних додатків.
  • JDK 5.0 Update 6 : Отримайте останнє оновлення JDK 5.0.

Підпішіть мене на ПОВІДОМЛЕННЯ до коментарів

Jsp?