Неблокуючий алгоритм

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Неблокуючий алгоритм (англ. Non-blocking algorithm) — підхід в паралельному програмуванні на симетрично-багатопроцесорних системах, що проповідує відмову від традиційних примітивів блокування, таких, як семафори, м'ютекси і події. Розділення доступу між потоками відбувається за рахунок атомарних операцій і спеціальних, розроблених під конкретну задачу, механізмів блокування.

Перевага неблокуючих алгоритмів — в кращій масштабованості за кількістю процесорів. До того ж, якщо ОС перерве один з потоків фонового завдання, інші, як мінімум, виконають свою роботу, не простоюючи. Як максимум — візьмуть невиконану роботу на себе.

Мотивація[ред.ред. код]

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

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

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

На відміну від алгоритмів блокування, без блокування алгоритми не страждають від цих недоліків, а крім того безпечні для використання в обробниках переривань.

Три рівня неблокуючої синхронізації[ред.ред. код]

Від найслабшого до найсильнішого:

Без перешкод (англ. obstruction-free)

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

Без блокувань (англ. lock-free)

Для алгоритмів без блокувань гарантується системний прогрес принаймні одного потоку. Наприклад, потік, що виконує операцію «порівняння з обміном» в циклі, теоретично може виконуватися нескінченно, але кожна ітерація означає, що якийсь інший потік здійснив прогрес, тобто система в цілому здійснює прогрес.

Без очікувань (англ. wait-free)

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

Причини і вигоди[ред.ред. код]

При створення багатопоточних додатків часто виникає необхідність організувати спільний доступ до загального ресурсу. Традиційний підхід дозволяє надати послідовний доступ за допомогою такого механізму синхронізації, як блокування. Примітиви синхронізації, такі як м'ютекси, семафори і критичні секції, дозволяють написати ділянку коду, який гарантовано не буде виконуватися одночасно при зверненні з паралельних потоків — одночасний доступ до ділянки загальною пам'яті може призвести до пошкодження вмісту. Спроба одного з потоків отримати блокування, яка вже зайнята іншим потоком, призводить до призупинення виконання першого потоку до моменту звільнення блокування по другому потоці.

Простий м'ютекс реалізується за допомогою так званого spinlock 'а - порожнього циклу з атомарними операціями. Складніші примітиви, що вибудовують потоки в чергу, влаштовані за допомогою витратної операції, що іменується "перемикання контексту", і того ж spinlock 'а в ядрі (KiDispatcherLock в Windows), який захищає чергу з пріоритетами. Коли навантаження на примітиви синхронізації невелике (наприклад, паралельна робота потоку обробки даних і призначеного для користувача інтерфейсу програми), витрати від порожніх циклів і перемикань невеликі.

Але коли потрібно було обробляти великі масиви даних на багатоядерних процесорах, з'явилися специфічні проблеми: на кожен елемент масиву м'ютекс не встановиш. Якщо ж синхронізувати інформацію великими блоками (наприклад, один м'ютекс на 10 000 елементів), потоки проводять надто багато часу в очікуванні свого м'ютекса. До того ж звичайний персональний комп'ютер з ОС загального призначення, зайнятий, окрім розрахунків, закачуванням інформації з інтернету, обробкою подій від миші і промальовуванням вікон інших програм, може призупиняти потоки на невизначений час.Неблокуючі алгоритми гарантують, що такі зупинки одного з потоків не приведуть до простою інших.Особливо важлива відсутність простоїв, якщо один з потоків виконує високопріоритетне завдання або завдання реального часу.

Неблокуюча синхронізація дозволяє повністю позбутися від взаємних блокувань. Втім, в неблокуючих алгоритмах є свої помилки — зациклення (livelock) і «гонки».

Реалізація[ред.ред. код]

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

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

  • послідовний доступ для всіх операцій читання і/або запису циклічний буфер, черга
  • читання-копіювання-відновлення (RCU) з єдиним письменником і будь-якою кількістю читачів. (Читачі отримують доступ до даних без очікування блокування; програмісти зазвичай працюють без блокувань, до тих пір поки не знадобиться звільнити пам'ять).

Посилання[ред.ред. код]