Блокування

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

acquire_lock (lock)

//критична секція

release_lock (lock)

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

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

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

int lock = 0;

void acquire lock (int lock) {

// якщо блокування немає (lock==0), запровадити його (lock=1)

//і вийти – ми ввійшли у критичну секцію

//інакше чекати, поки блокування не знімуть

while (lock!=0); // (1)

lock=1; // (2);

}

void release_lock (int lock) {

//

lock = 0;

}

Головна проблема цієї реалізації полягає в тому, що перевірка значення змінної блокування (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) можна реалізувати так:

void acquire_lock(int lock) {

// якщо блокування немає (lock==0), запровадити його (lock=1)

// і вийти – ми ввійшли у критичну секцію

// інакше чекати, поки блокування не знімуть, і не міняти lock

while (TSL(lock)!=0);

}

void release_lock (int lock) {

//зняти блокування

lock=0;

}

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

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

int lockguard=0; // блокування для критичних секцій усередині

// acquire_lock і release_lock

void acquire_lock(int lock) {

// перевірити, чи безпечно виконувати цю дію

while (TSL(lockguard)!=0);

// якщо блокування запроваджене – призупинити потік

if (lock==1) sleep();

// інакше заблокувати й увійти у критичну секцію

else lock = 1;

// дає можливість іншим потокам виконувати цю дію

// цей код повинен виконуватися завжди у разі завершення операції

lockguard = 0;

}

void release_lock(int lock) {

// перевірити на безпеку виконання цієї дії

while (TSL(lockguard)!=0);

// розбудити один із призупинених потоків, якщо вони є

if (waiting_threads()) wakeup(some_thread);

// якщо призупинені потоки відсутні – зняти блокування

else lock = 0;

// дає можливість іншим потокам виконувати цю дію

// цей код повинен виконуватися завжди у разі завершення операції

lockguard = 0;

}

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

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

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

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

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

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

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

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

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

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

5.3. Базові механізми синхронізації потоків

Механізмами синхронізації є засоби операційної системи, які допомагають розв’язувати основне завдання синхронізації – забезпечувати координацію потоків, котрі працюють зі спільно використовуваними даними. Якщо такі засоби – це мінімальні блоки для побудови багапотокових програм, їх називають синхронізаційними примітивами.

Синхронізаційні механізми поділяють на такі основні категорії:

· універсальні, низького рівня, які можна використовувати різними способами (семафори);

· прості, низького рівня, кожен з яких пристосований до розв’язання тільки однієї задачі (м’ютекси та умовні змінні);

· універсальні високого рівня, виражені через прості; до цієї групи належить концепція монітора, яка може бути виражена через м’ютекси та умовні змінні;

· високого рівня, пристосовані до розв’язання конкретної синхронізаційної задачі (блокування читання-записування і бар’єри).

Розглянемо різні механізми і дамо оцінку перевагам, які має кожен з них, а також можливі їхні недоліки.

Для подальшої ілюстрації матеріалу візьмемо класичний приклад, який демонструє необхідність синхронізації – задачу виробників-споживачів (producer-consumer problem) або задачу обмеженого буфера (bounded buffer).

Формулювання задачі просте. Припустимо, що в нас є потоки-виробники і потоки-споживачі. Виробник створює об’єкти, споживач їх отримує. Завданням є так синхронізувати їхню роботу, щоб споживач не міг намагатися отримувати ще не створені об’єкти, а виробник не міг зробити більше об’єктів, ніж зможе отримати споживач.

Для синхронізації потоків помістимо між виробником і споживачем буфер фіксованої довжини n. Виробник може поміщати об’єкти у буфер,споживач – забирати їх звідти. Якщо споживач забирає об’єкт, його вилучають із буфера. Необхідно забезпечити кілька вимог.

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

Дата добавления: 2014-01-05