Вопрос1 Засоби взаємних виключень та синхронізації процесів

3.9.1. Програмний підхід

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

Лістинг 3.1.

boolean flag = false; /* змінна блокування */

/* Процесс 1 */ /* Процесс 2 */

while(flag); /*АКТИВНЕ ОЧІКУВАННЯ*/ while(flag);

flag = true; flag = true;

/* КРИТИЧНИЙ РОЗДІЛ */ /* КРИТИЧНИЙ РОЗДІЛ */

flag = false; flag = false;

/* РЕШТА КОДУ */ /* РЕШТА КОДУ */

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

На жаль, приведений приклад (ліст. 3.1.) непрацездатний. Причину знайти неважко — припустимо процес 1 виконав перевірку змінної flag, вийшов із циклу і був переведений диспетчером в стан готового до виконання не встигнувши виставити ознаку зайнятості критичного розділу. Далі продовжив виконуватись процес 2, який також виконує перевірку змінної блокування. Оскільки значення flag, все ще false, він входить в критичний розділ і теж переривається. Тепер перший процес, продовжуючи свою роботу, також опиниться в критичному розділі! Проблема виявляється в тому, що виконання процесу може бути перерване між перевіркою змінної блокування та її установкою. Задача виявилась зовсім не простою. Першим задовільне програмне рішення задачі взаємного виключення для двох процесів отримав Деккер (T. Dekker). Більш простій алгоритм був запропонований в 1981 р. Петерсоном (G.L. Peterson). Детальніше обидва алгоритми розглядаються в [2].

3.9.2. Апаратна підтримка

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

Лістинг 3.2.

/* БЕЗПЕЧНИЙ КОД */;

/* Заборона апаратних переривань */;

/* КРИТИЧНИЙ РОЗДІЛ */;

/* Дозвіл апаратних переривань */;

/* БЕЗПЕЧНИЙ КОД */;

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

Значно кращі результати дає використання спеціальних машинних команд. Усунути

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

Алгоритм операції перевірки і установки значення наприклад такий як на ліст. 3.3.

Лістинг 3.3.

boolean testset(int i){

if(i==0){

i=1;

return true;

}

else

return false;

}

Все це виглядає як одна машинна команда (т. зв. атомарна операція). У деталях реалізація команди testset на різних комп'ютерах може відрізнятися. Так, процесори сімейства Pentium мають команду CMPXCHG reg/mem,reg1 (порівняти і замінити), що використовує три операнди: операнд-джерело в регістрі reg1, операнд призначення в регістрі або в пам'яті reg/mem і акумулятор (регістр EAX). Якщо значення в приймачі і в акумуляторі рівні, операнд призначення замінюється на операнд-джерело. Інакше початкове значення операнда призначення завантажується в акумулятор.

На ліст. 3.4 приведений приклад реалізації взаємних виключень через спін-блокування з використанням інструкції перевірки і установки:

Лістинг 3.4.

const int n = /* кількість паралельних процесів */;

int bvar;

void P(int i){

while(1){

while(!testset(bvar)); /* АКТИВНЕ ОЧІКУВАННЯ */

/* Критичний розділ */;

bvar = 0;

/* Решта коду */;

}

void main(){

bvar = 0;

parbegin(P(1),P(2),...,P(n)); /* Стартуємо паралельні процеси */

}

Переваги підходу з використанням апаратної підтримки:

1. Застосовується до будь-якої кількості процесів як в одно-, так і в багатопроцесорних системах.

2. Простий, а тому легко перевіряється.

3. Може використовуватися для підтримки багатьох критичних розділів (для кожного з них виділяється власна змінна блокування).

Недоліки:

Використовується перечікування зайнятості. Тобто в очікуванні входу в критичний розділ процес продовжує споживати процесорний час.

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

Можливе взаємне блокування.

Можливість взаємного блокування пояснимо на такому прикладі. Нехай процес Р1

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

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

В ядрі Windows NT спін-блокування призначені в основному для захисту даних, доступ до яких проводиться на підвищених рівнях IRQL (Interrupt ReQuest Level – рівні запитів переривань). Для вирішення можливої проблеми інверсії пріоритетів потрібний механізм, що не дозволяє коду з деяким рівнем IRQL переривати код з нижчим рівнем IRQL в той момент, коли останній володіє спін-блокуванням. Таким механізмом є підвищення поточного рівня IRQL потоку у момент захоплення ним спін-блокування до деякого рівня, що асоціюється із даним спін-блокуванням, і відновлення колишнього IRQL потоку після його звільнення. Код, що працює на підвищеному рівні IRQL, не має права звертатися до ресурсу, захищеного спін-блокуванням у якого рівень IRQL нижчий, ніж у самого викликаючого коду.