5.2.2. Критичні секції та блокування Поняття критичної секції

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

Звідси випливає, що розв’язанням проблеми змагання є перетворення фрагмента коду, який спричиняє проблему, в атомарну операцію, тобто в таку, котра гарантовано виконуватиметься цілковито без втручання інших потоків. Такий фрагмент коду називають критичною секцією (critical section):

Тепер, коли два потоки візьмуться виконувати код критичної секції одночасно, той з них, що почав першим, виконає весь її код цілком до того, як другий почне своє виконання (другий потік чекатиме, поки перший не закінчить виконання коду критичної секції). У результаті підсумку гарантовано матимемо в нашій програмі послідовність подій за варіантом 2, і змагання не відбудеться ніколи. Розглянемо властивості, які повинна мати критична секція.

♦ Взаємного виключення (mutual exclusion): у конкретний момент часу код критичної секції може виконувати тільки один потік.

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

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

Залишається відповісти на далеко не просте запитання: «Як нам змусити систему сприймати кілька операцій як одну атомарну операцію?»

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

Блокування

Раціональнішим розв’язанням є використання блокувань (locks). Блокування -- це механізм, який не дозволяє більш як одному потокові виконувати код критичної секції. Використання блокування зводиться до двох дій: запровадження (заблокування, функція acquire_lock( )) і зняття блокування (розблокування, функція release_lock( )). У разі заблокування перевіряють, чи не було воно вже зроблене іншим потоком, і якщо це так, цей потік переходить у стан очікування, інакше вій запроваджує блокування і входить у критичну секцію. Після виходу із критичної секції потік знімає блокування.

Так реалізовують властивість взаємного виключення, звідси походить інша назва для блокування — м’ютекс (mutex, скорочення від mutual exclusion). А втім, частіше ця назва позначає конкретний механізм ОС, що реалізує блокування, у такому смислі вона буде використана й у цій книзі.

Проблеми із реалізацією блокувань

Розглянемо наївну реалізацію критичної секції із використанням змінних блокування. З кожною критичною секцією пов’язують цілочислову змінну, якій присвоюють одиницю під час заблокування і нуль — після розблокування. Ось який приблизно має вигляд код такої реалізації:

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

Апаратна підтримка блокувань

Є низка алгоритмів, які дають можливість коректно реалізувати блокування, спираючись на атомарність звичайних операцій записування в пам’ять і читання з пам’яті. До них належать алгоритми Деккера і Петерсона та алгоритм булочної (bakery algorithm). Ми обмежимося тими алгоритмами, які спираються на наявну апаратну підтримку. Розглянемо, як виглядає така апаратна підтримка і що можна реалізувати па її основі.

Для організації блокування и архітектурі ІА-32 може бути використана спеціальна інструкція процесора, яку називають «перевірити і заблокувати» (Test & Set Lock, TSL). Параметром цієї інструкції є деяка адреса в пам’яті (наприклад, яка визначає місцезнаходження змінної блокування). Розглянемо, що відбувається під час виконання цієї інструкції (для простоти вважатимемо, що в пам’яті, з якою працює ця інструкція, може зберігатися тільки 0 або 1, при цьому 1 означає «блокування є», 0 — «блокування відсутнє»).

1. Зчитуються дані, які перебувають у цей момент у пам’яті (поточний стан змінної блокування).

2. У пам’ять записують значення 1 (запроваджують блокування, якщо цього не було зроблено раніше, інакше значення змінної блокування не міняють).

3. Зчитані на кроці 1 дані повертає операція. Якщо блокування до початку виконання цієї інструкції не було запроваджене, операція поверне 0, у противному разі — 1.

Усі три кроки інструкції TSL виконуються як одна атомарна операція, це має гарантувати апаратне забезпечення.

Програмно-апаратна реалізація блокувань

Заблокування і розблокування із використанням інструкції TSL (тут буде використано псевдокод, у якому TSL(lock) відповідатиме виконанню операції TSL над ділянкою пам’яті, що відповідає змінній lock) можна реалізувати так:

Головним недоліком описаної технології є те, що потік повинен постійно перевіряти в циклі, чи не зняли блокування. Таку ситуацію називають активним очікуванням (busy waiting), а таке блокування — спін-блокуваниям (spinlock). Використання циклу під час активного очікування завантажує процесор і допустиме тільки упродовж короткого часу (це справедливо для однопроцесорних систем, у багатопроцесорних використання спін-блокувань може бути виправдане тому, що під час виконання циклу активного очікування одним процесором інші можуть продовжувати свою роботу).

Альтернативою активному очікуванню є операція призупинення потоку (thread blocking, sleep). При цьому потік за умови блокування негайно або через якийсь час переходить зі стану виконання у стан очікування, передаючи процесор іншому потокові. Для того щоб реалізувати критичну секцію за допомогою цієї операції, потрібно доповнити її операцією виведення потоку зі стану очікування (поновленням потоку, wakeup). Робота із критичною секцією в цьому разі буде мати такий вигляд:

Виділимо деякі особливості цього алгоритму.

♦ Інструкцію TSL використовують тільки для забезпечення атомарності виконання операцій acquire lock і reieasejock (для перевірки безпеки цих операцій використовують змінну lockguard). У результаті потік перебуватиме у стані активного очікування не довше, ніж потрібно іншим потокам для виконання цих операцій.

♦ За наявності блокування потік буде призупинено. На практиці зазвичай із блокуванням 1оск пов’язують чергу очікування, в яку й буде поміщено цей потік.

♦ У разі спроби розблокування, якщо відповідна черга очікування непорожня, виконання одного із призупинених потоків буде продовжене і блокування не зняте. Реальне розблокування відбудеться тільки тоді, коли черга очікування порожня.

♦ ІІсевдокод неповністю відображає ту ситуацію, що змінній lockguard після виходу з acquire Jock і reieasejock повинне бути присвоєне значення 0 завжди (навіть під час перемикання контексту). У противному разі інші потоки не змогли б виконувати ці операції.

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

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

Механізми синхронізації ОС

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

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