Мікхель-Скотт Безблокова Очередь

Чому блоки не завжди є відповіддю

Традиційний спосіб зробити структуру даних безпечною для одночасного використання полягає у захисті її за допомогою м’ютексу: потік повинен отримати блокування перед дотиком черги та звільнити його після завершення. Це легко зрозуміти, але має серйодну слабкість. Якщо поток, який зараз тримає блокування, призупинено, можливо, завдяки планувачу операційної системи, виключено з пам’яті або просто повільний, то всі інші потоки, які хочуть використовувати чергу, повинні чекати. У найгіршому випадку одна нещадна планувальна річ може зупинити весь систему, навіть якщо більшість потоків повністю здатні працювати. Це називається «конвойуванням блокувань», і це особливо стає проблемою в реальному часі, ядрах операційних систем та високопаралельних серверах, де важливий передбачуваний пропускна здатність. М’ютекс забезпечує лише те, що один потік може використовувати структуру даних у будь-який момент часу. М’ютекси не гарантують, що жоден потік не буде чекати на доступ до ресурсу. Замість цього, м’ютекси можуть призвести до того, що всі потоки будуть чекати, поки один з них звільнить блокування. Це може призвести до ситуації, коли система стає заблокованою та неефективною. Щоб уникнути цих проблем, можна використовувати lock-free алгоритм. Lock-free алгоритми не гарантують, що будь-який потік завершиться швидко, але вони гарантують, що загальна система завжди робить прогрес: в будь-який момент часу принаймні один потік серед тих, хто намагається оперувати з структурою, завершить свою операцію за кінцевою кількістю кроків. Жоден потік не може зупинити всю структуру просто тим, що його відключено в незручний момент. Це значно сильніша гарантія, ніж те, що забезпечує м’ютекс, і набагато легше досягти в практиці. Черга Майкла Скотта досягає цієї lock-free властивості шляхом заміни м’ютексу інструкцією compare-and-swap (CAS), яку підтримують безпосередньо в апаратному забезпеченні більшість сучасних процесорів. Compare-and-swap приймає пам'ятне місце, очікуване старе значення та бажане нове значення. Воно атомарно перевіряє, чи все ще містить пам’ятне місце очікуване значення, і якщо так, то замінює його на нове значення, повідомляючи про успіх. Якщо пам’ятне місце змінилося з моменту читання потоком, операція зазнає невдачі та повідомляє про це, залишаючи пам’ятне місце без змін. Ця одна інструкція стає будівельним блоком для всієї реалізації черги, оскільки вона дозволяє потоку спробувати оновити та негайно дізнатися, чи вдалося йому або потрібно повторити спробу.

Скелет зв’язаного списку з головним і хвостовим покажчиками

Мікхель-Скотт черга побудована на поодинокій зв’язаній списку вузлів, де кожен вузол містить значення даних та покажчик до наступного вузла. Два спільні покажчики визначають структуру: головний (head), який завжди посилається на сентинельний або фіктивний вузол перед першим реальним елементом, і хвостовий (tail), який посилається на останній вузол, що поточний відомий у списку. Використання постійного фіктивного вузла зпереди є свідомим дизайнерським рішенням. Це означає, що черга ніколи не є порожньою на рівні покажчиків, що усуває цілий клас спеціальних випадків обробки при переході від нуля до одного елемента, перехід, який надзвичайно легко зробити неправильно в одночасній коді. Операції видалення (dequeue) торкаються лише кінця списку. Потік, який хоче видалити елемент, читає поточний головний покажчик, дивиться на вузол відразу після нього, який містить фактичний перший елемент черги, копіює з нього значення та потім намагається виконати порівняння-і-заміну покажчика head вперед до цього вузла. Якщо операція порівняння-і-заміни успішна, старий фіктивний вузол виводиться, іноді буквально стаючи сміттям для подальшого збору, а вузол, який раніше містив перший елемент, стає новим фіктивним. Якщо вона невдала, інший потік вже видалив елемент, і операція повторюється, перечитуючи поточний головний покажчик. Операції додавання (enqueue) працюють на кінці списку, але тут дизайн стає більш тонким. Наївний підхід може спробувати виконати порівняння-і-заміну покажчика tail безпосередньо до нового вузла, але це було б неправильно, оскільки новий вузол також потрібно зв’язати з існуючою ланцюгом, оновлюючи покажчик next поточного останнього вузла. Два окремі спільні поля стану – поле next останнього вузла та сам покажчик tail – необхідно оновити разом, але порівняння-і-заміну можна виконати лише над одним словом пам’яті одночасно. Ця невідповідність між тим, що вимагає коректності – оновлення двох місць, і тим, що пропонують апаратні засоби – атомарне оновлення одного місця – є центральним інженерним викликом, який має вирішити алгоритм, і це тема наступного розділу.

Двохетапний танець переміщення хвостового елемента

Ось серцевина розумності алгоритму. Щоб додати новий вузол у чергу, потік спочатку читає поточний покажчик хвостового елемента і дивиться на наступне поле цього вузла. За нормальних, безперешкодних умов, це наступне поле має бути порожнім, що означає, що покажчик хвостового елемента справді вказує на останній вузол ланцюга. Потік потім намагається виконати порівняння та обмін (compare-and-swap) на цьому наступному полі, намагаючись встановити його з порожнього на те, щоб він вказував на новий вузол. Якщо це вдається, новий вузол тепер офіційно є частиною зв’язаного списку, доступним для відстеження шляхом наступних полів від голови. Але зверніть увагу: спільний покажчик хвостового елемента ще не оновлено. Він все ще вказує на вузол, який раніше був останнім. Потік, який нещодавно успішно зв’язав свій вузол у ланцюг, потім намагається виконати друге порівняння та обмін, цього разу на покажчик хвостового елемента, намагаючись перемістити його з попереднього останнього вузла до щойно вставленого вузла. Критично важливо, щоб цей другий крок не був успішним для того, щоб вважалося, що додавання було виконано. Як тільки перший порівняння та обмін зв’язав новий вузол у ланцюг, додавання фактично відбулося, оскільки будь-який потік, який переміщується по списку від голови, досягне його. Переміщення хвостового елемента є обліковими записами, які допомагають майбутнім додаванням швидко знаходити кінець списку, але воно не є точкою лінеаризації операції. Це розділення робить алгоритм стійким до того, що потік може застигнути між двома кроками. Уявіть собі, що потік успішно зв’язав свій вузол у ланцюг, але потім його призупиняє планувальник, щоб він не міг перемістити хвостовий елемент вперед. Покажчик хвостового елемента тепер застарілий на один вузол позаду реальності. Будь-який інший потік, який прийде для додавання, прочитає хвостовий елемент, подивиться на наступне поле хвостового елемента та виявить, що воно не порожнє, що означає, що хтось вже вставив вузол, який хвостовий елемент ще не обігнав. Замість того, щоб здатися, допомагаючий потік виконує порівняння та обмін, щоб перемістити покажчик хвостового елемента від імені заблокованого потоку, і лише тоді намагається знову вставити свій вузол. Цю техніку називають допомогою, і саме вона зберігає гарантію відсутності блокування: жоден потік ніколи не повинен чекати, поки заблокований потік прокинеться, оскільки будь-який інший активний потік може завершити роботу з очищення заблокованого потоку для нього.

Чому один порівняння та обмінювання не може зробити все

Важливо зупинитись на тому, чому двоступеневий підхід необхідний, а не просто неефективність, яку можна оптимізувати. Деякі архітектури процесорів пропонують порівняння та обмін даними для двох сусідніх слів одночасно, іноді це називають "compare-and-swap-two". В принципі, черга могла б використовувати це для одночасного оновлення покажчика наступного вузла останнього вузла та покажчика хвоста. Але алгоритм Майкхель-Скотт був розроблений для роботи з одним порівнянням та обміном, який доступний на практично всій основній платформі апаратного забезпечення, що робить його значно більш портативним, і двоступеневий підхід виявляється краще узагальнюється для інших безблокових структур, тому він залишається єдиним навчальним прикладом навіть там, де доступні ширші атомарні операції. Аргумент щодо правильності ґрунтується на визначенні точного моменту, який називається «лінеаризаційним пунктом», коли операція здається миттєвою з точки зору всіх інших потоків. Для додавання в чергу цей момент – успішне порівняння та обмін, яке пов’язує новий вузол ланцюжком шляхом оновлення поля «next» попереднього останнього вузла, а не пізніше порівняння та обмін, яке переміщує покажчик хвоста. Оскільки покажчик хвоста дозволено відставати від справжнього кінця списку на не більше ніж один вузол, кожна операція перевіряє це положення та виправляє його за потреби до того, як продовжить. Це повторюваний шаблон у безблоковому дизайні: замість того, щоб забороняти структурі коли-небудь перебувати в проміжному, трохи невідповідному стані, алгоритм визначає, який саме вигляд може мати цей стан, і дає кожному учаснику відповідальність за його виявлення та виправлення. Цей шаблон також пояснює, чому безблокові алгоритми відомі своєю складністю в розробці та навіть у перевірці вручну. Будь-яка зміна, яка здається нешкідливою спрощенням, така як пропуск перевірки поля «next» покажчика хвоста перед спробою вставити, може безшумно порушити інваріант, що покажчик хвоста ніколи не відстає на більше ніж один вузол позаду, пошкоджуючи чергу під певним переплетінням потоків. Формальні інструменти верифікації та моделі-перевірки часто використовуються в практиці для підтвердження того, що черги, як ця, є правильними за будь-яким можливим переплетінням потоків, оскільки людське інтуїтивне розуміння одночасного виконання не надійне на такому рівні деталізації.

Проблема ABA та звільнення пам’яті

Операція Compare-and-Swap має тонкий недолік, відомий як проблема ABA. Операція Compare-and-Swap перевіряє лише, чи потоково міститься в місці пам'яті очікуване значення, але не може знати, чи змінилося це значення і потім повернулося назад. Уявіть собі, що потік читає покажчик, очікуючи, що він все ще посилається на вузол A, його призупиняють, а поки він у стані призупинення, інші потоки витягують вузол A, звільняють його пам'ять і виділяють новий вузол, який випадково розміщується в тій самій адресі пам’яті та з’єднують його. Коли оригінальний потік прокидається і виконує операцію Compare-and-Swap, місце пам’яті все ще дорівнює адресі, яку він запам'ятав, тому обмін відбувається успішно, незважаючи на те, що фактична ідентичність вузла повністю змінилася під ним. Це може пошкодити структуру черги способами, які надзвичайно важко відтворити та відлагоджувати. Оригінальна стаття Майкла-Скотта вирішує це за допомогою техніки, яка передбачає додавання тегів або лічильників версій разом із кожним покажчиком, щоб навіть якщо адресу повторно використовують, супутні лічильники просуваються вперед, і операція Compare-and-Swap правильно не вдасться. Сучасні реалізації часто використовують різні стратегії для тісно пов'язаної проблеми звільнення пам’яті, вирішуючи, коли безпечно звільнити пам’ять вилученого вузла, враховуючи, що інший потік все ще може бути в процесі читання. Техніки, такі як покажчики небезпеки, де кожен потік публікує, які вузли він зараз використовує, щоб інші потоки знали, яких уникати звільнення, та епоха-засноване звільнення, де пам’ять звільняється лише після того, як усі потоки пройдуть точку синхронізації, є поширеними рішеннями у бібліотеках безблокового керування. Java ConcurrentLinkedQueue обходить багато з цих небезпек завдяки автоматизованому збиранню сміття віртуальною машиною Java: вузол ніколи не звільняється та його адресу повторно не використовують, поки будь-який потік має до нього посилання, що усуває найнебезпечніше проявлення проблеми ABA. Це одна з причин, чому алгоритм Майкла-Скотта знайшов комфортне місце в мовах програмування з керованою пам’яттю, незважаючи на те, що оригінальна стаття була написана з урахуванням ручного управління пам'яттю в безкерульових мовах, таких як C, де проблема ABA та безпека звільнення вимагають значно більш ретельного проектування.

Часті запитання

Що гарантує lock-free, якщо не швидкість операцій?

Lock-free означає, що в усіх потоках, які конкурують за структуру даних, система загалом завжди робить прогрес: принаймні один потік завершить свою операцію за фінітну кількість кроків, незалежно від того, що роблять інші потоки або як вони розгортаються. Це не гарантує, що будь-який конкретний потік закінчиться швидко чи взагалі, оскільки теоретично потік може назавжди програвати в гонках compare-and-swap, тоді як інші успішно завершують операції. Це слабше за wait-free, яке обмежує час виконання кожного окремого потоку, але значно сильніше за lock-based підхід, де зупинений потік, утримуючи замок, може зупинити всі інші.

Чому сторона dequeue простіша за сторону enqueue?

Dequeue потребує лише оновлення одного спільного покажчика, head, для видалення переднього вузла з логічної черги, що саме і призначений для виконання окремої операції compare-and-swap атомарно. Enqueue складніша, оскільки вставку вузла на кінець концептуально потребує оновлення двох речей одночасно: покажчик next попереднього останнього вузла, щоб фактично зв'язати новий вузол у ланцюгу, і покажчик tail, щоб продовжувати вказувати на справжній кінець списку. Оскільки один compare-and-swap може торкнутися лише однієї локації, enqueue потребує двокрокового підходу з допомогою, описаного в цій лабораторії, тоді як dequeue не потребує цього.

Що відбувається, якщо потік аварійно завершується або його вбивають посередині enqueue?

Якщо потік успішно зв'язує свій новий вузол у ланцюгу через перший compare-and-swap, але припиняє роботу до виконання другого compare-and-swap, що просуває покажчик tail, черга не буде пошкоджена. Покажчик tail просто залишиться на один вузол позаду справжнього кінця списку. Будь-який наступний потік, який намагатиметься enqueue, помітить цю затримку, коли перевірить поле next поточного вузла tail, просуне покажчик tail від імені померлого потоку та продовжить свій власний вставлення. Не потрібен жоден очисник або спеціальна логіка відновлення після аварії.

Чи є черга Майкла-Скотта строго FIFO за одночасного доступу?

Так, у сенсі, який має значення для лінійно-інтегрованої структури даних: існує чіткий момент лінеаризації для кожного enqueue та dequeue, а саме момент успішного виконання вирішального compare-and-swap, і порядок, в якому вузли стають доступними з голови, відповідає порядку цих моментів лінеаризації. Два enqueue, які перетинаються в реальному часі, все одно будуть узгоджено впорядковані кожним потоком, який пізніше читає чергу, що є точним формальним сенсом того, як структура поводиться як правильна FIFO черга, незважаючи на приховану одночасність.

Чому ConcurrentLinkedQueue у Java використовує цей алгоритм замість простого синхронізованого черги?

Синхронізована черга, підтримувана муттекс, змушує кожен потік, читачів і письменників, проходити через єдиний замок, що стає серйозною вузькою частиною при високій конкуренції від багатьох потоків. Алгоритм Майкла-Скотта дозволяє незалежним операціям enqueue та dequeue відбуватися паралельно з меншою конкуренцією, оскільки потоки стикаються лише тоді, коли вони випадково націлюються на один і той же покажчик в один і той же момент часу, а програшники повторюють замість блокування. Враховуючи роботу Java Virtual Machine з видаленням загроз ABA та управління пам'яттю, які турбують реалізацію керування пам’яттю вручну, це було чудово підходить для загального призначення високопродуктивної паралельної колекції.

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте The Michael-Scott Lock-Free Queue і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.

▶ Відкрити симуляцію The Michael-Scott Lock-Free Queue