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

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

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

Мотивація

Докладніше: Блокування (програмування)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Посилання