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

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

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

Мотивація

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

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

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

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

Три рівні синхронізації без блокування

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

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

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

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

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

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

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

Причини та переваги

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

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

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

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

Впровадження

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

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

• послідовний доступ для всіх операцій читання і/або запису, циклічний буфер, черга

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