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

Загальні відомості

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

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

Іншим способом є використання блокуючих змінних. З кожним ресурсом, що розділяється, зв'язується двійкова змінна, яка набуває значення 1, якщо ресурс вільний (тобто жоден процес не знаходиться в даний момент в критичній секції, пов'язаній з даним процесом), і значення 0, якщо ресурс зайнятий. На малюнку 2.4 показаний фрагмент алгоритму процесу, що використовує для реалізації взаємного виключення доступу до ресурсу D, що розділяється, блокуючу змінну F(D). Перед входом в критичну секцію процес перевіряє, чи вільний ресурс D. Якщо він зайнятий, то перевірка циклічно повторюється, якщо вільний, то значення змінної F(D) встановлюється в 0, і процес входить в критичну секцію. Після того, як процес виконає всі дії з ресурсом D, що розділяється, значення змінної F(D) знову встановлюється рівним 1.

Якщо всі процеси написані з використанням вищеописаних угод, то взаємне виключення гарантується. Слід відмітити, що операція перевірки і установки блокуючої змінної повинна бути неподільною. Пояснимо це. Хай в результаті перевірки змінної процес визначив, що ресурс вільний, але відразу після цього, не встигнувши встановити змінну в 0, був перерваний. За час його припинення інший процес зайняв ресурс, увійшов до своєї критичної секції, але також був перерваний, не завершивши роботи з ресурсом, що розділяється. Коли управління було повернене першому процесу, він, вважаючи ресурс вільним, встановила ознака зайнятості і почав виконувати свою критичну секцію. Таким чином був порушений принцип взаємного виключення, що потенційно може привести до небажаних наслідків. Щоб уникнути таких ситуацій в системі команд машини бажано мати єдину команду "перевірка-установка", або ж реалізовувати системними засобами відповідні програмні примітиви, які б забороняли переривання впродовж всієї операції перевірки і установки.

Реалізація критичних секцій з використанням блокуючих змінних має істотний недолік: протягом часу, коли один процес знаходиться в критичній секції, інший процес, якому потрібний той же ресурс, виконуватиме рутинні дії з опиту блокуючої змінної, марно витрачаючи процесорний час. Для усунення таких ситуацій може бути використаний так званий апарат подій. За допомогою цього засобу можуть вирішуватися не тільки проблеми взаємного виключення, але і більш загальні завдання синхронізації процесів. У різних операційних системах апарат подій реалізується по своєму, але у будь-якому випадку використовуються системні функції аналогічного призначення, які умовно назвемо WAIT(x) і POST(x), де x - ідентифікатор деякої події. Функція WAIT(D) переводить активний процес в стан ОЧІКУВАННЯ і робить відмітку в його дескрипторі про те, що процес чекає події D. Процес, який в цей час використовує ресурс D, після виходу з критичної секції виконує системну функцію POST(D), внаслідок чого операційна система проглядає чергу чекаючих процесів і переводить процес, чекаючий події D, в стан ГОТОВНІСТЬ.

Узагальнювальний засіб синхронізації процесів запропонував Дейкстра, який ввів два нові примітиви. У абстрактній формі ці примітиви, P, що позначаються, і V, оперують над цілими ненегативними змінними, званими семафорами. Хай S такий семафор. Операції визначаються таким чином:

V(S): змінна S збільшується на 1 однією неподільною дією; вибірка, інкремент і запам'ятовування не можуть бути перервані, і до S немає доступу іншим процесам під час виконання цієї операції.

P(S): зменшення S на 1, якщо це можливо. Якщо S=0, то неможливо зменшити S і залишитися в області цілих ненегативних значень, в цьому випадку процес, що викликає P-операцию, чекає, поки це зменшення стане можливим. Успішна перевірка і зменшення також є неподільною операцією.

У окремому випадку, коли семафор S може набувати тільки значень 0 і 1, він перетворюється на блокуючу змінну. Операція P містить в собі потенційну можливість переходу процесу, який її виконує, в стан очікування, тоді як V-операция може при деяких обставинах активізувати інший процес, припинений операцією P (порівняєте ці операції з системними функціями WAIT і POST).

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

Розглянемо використання простішої ідеї для вирішення проблеми змагань.

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

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

//початок критичної секції

total_amount=total_amount+new_amount;

//кінець критичної секції

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

Розглянемо властивості, які повинна мати критична секція.

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

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

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

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

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

Апарат подій для роботи з критичними секціями

• Функція WAIT(D) переводить потік у стан очікування події звільнення ресурсу D

• Функція POST(D) викликається після звільнення ресурсу D і переводить усі потоки, що його очікують, у стан готовності (планувальник обере один з них на виконання)

• У POSIX – виклики sleep() і wakeup()

• Проблема: накладні витрати ОС на здійснення викликів можуть перевищити економію (іноді активне очікування раціональніше)

Порівняння критичних секцій та м'ютексів

Критична секція у значній мірі виконує ті ж завдання, що і м'ютекс.

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

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

Робота з критичними секціями у Windows

Для роботи з критичними секціями використовують Windows API.

Перед використання критичної секції її слід ініціалізувати за допомогою процедури InitializeCriticalSection. Її опис мовою C:

void WINAPI InitializeCriticalSection(
__out  LPCRITICAL_SECTION lpCriticalSection
);

Опис мовою Delphi:

procedure InitializeCriticalSection(
 var lpCriticalSection: TRTLCriticalSection
);

Перед входом у код критичної секції потік повинен викликати функцію EnterCriticalSection. Її опис мовою C:

void WINAPI EnterCriticalSection(
__inout  LPCRITICAL_SECTION lpCriticalSection
);

Опис мовою Delphi:

procedure EnterCriticalSection(
 var lpCriticalSection: TRTLCriticalSection
);

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

Відразу після закінчення роботи зі спільним ресурсом потік повинен звільнити об’єкт критичної секції викликом процедури LeaveCriticalSection. Її опис мовою C:

void WINAPI LeaveCriticalSection(
__inout  LPCRITICAL_SECTION lpCriticalSection
);

Опис мовою Delphi:

procedure LeaveCriticalSection(
 var lpCriticalSection: TRTLCriticalSection
);

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

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

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

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

BOOL WINAPI TryEnterCriticalSection(
__inout  LPCRITICAL_SECTION lpCriticalSection
);

Опис функції на Delphi:

function TryEnterCriticalSection(
 var lpCriticalSection: TRTLCriticalSection
): BOOL;  

У момент виклику вона перевіряє, чи критична секція захоплена якимось іншим потоком. Якщо так– функція повертає false, у протилежному випадку вона захоплює критичну секцію та повертає true.

Після завершення роботи з критичною секцією вона повинна бути вивільнена викликом процедури DeleteCriticalSection. Опис на C:

void WINAPI DeleteCriticalSection(
__inout  LPCRITICAL_SECTION lpCriticalSection
);

Опис на Delphi:

procedure DeleteCriticalSection(
 var lpCriticalSection: TRTLCriticalSection
);  

Приклад використання критичної секції

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

// Оголошення критичної секції
var ICriSec : TRTLCriticalSection;
...................................
// Ініціалізація - до запуску першого потоку
InitializeCriticalSection(ICriSec);
...................................
// Функція потоку
function ThreadFunc(Ptr: Pointer): LongInt;
var I : integer;
begin
for I := 1 to 1000000 do begin
  // Якийсь код
  EnterCriticalSection(ICriSec);
  Inc(A);
  LeaveCriticalSection(ICriSec);
  // Якийсь код
end;
end;
....................................
// Знищення об'єкта критичної секції
DeleteCriticalSection(ICriSec);

Задача

Розглянемо приклад, в якому псевдопаралельні взаємодіючі процеси представлені діями різних студентів:

Час	Студент 1	Студент 2	Студент 3
17-05	Приходить в кімнату
17-07	Знаходить, що хліба немає
17-09	Йде в магазин
17-11		Приходить в кімнату
17-13		Знаходить, що хліба немає
17-15		Йде в магазин
17-17			Приходить в кімнату
17-19			Знаходить, що хліба немає
17-21			Йде в магазин
17-23	Приходить в магазин
17-25	Купує 2 батони на всіх
17-27	Йде з магазина
17-29		Приходить в магазин
17-31		Купує 2 батони на всіх
17-33		Йде з магазина
17-35			Приходить в магазин
17-37			Купує 2 батони на всіх
17-39			Йде з магазина
17-41	Повертається в кімнату
17-43
17-45
17-47		Повертається в кімнату
17-49
17-51
17-53			Повертається в кімнату

Тут критична ділянка для кожного процесу — від операції "Знаходить, що хліба немає" до операції "Повертається в кімнату" включно. В результаті відсутності взаємовиключення ми з ситуації "Немає хліба" потрапляємо в ситуацію "Дуже Багато хліба". Якби ця критична ділянка виконувалася як атомарна операція — "Дістає 2 батони хліба", то проблема утворення надлишків була б знята.

Час	Студент 1	Студент 2	Студент 3
17-05	Приходить в кімнату
17-07	Дістає два батони хліба
17-09		Приходить в кімнату
17-11			Приходить в кімнату

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

Отже, для вирішення задачі необхідно, щоб у тому випадку, коли процес знаходиться в своїй критичній ділянці, інші процеси не могли увійти до своїх критичних ділянок. Ми бачимо, що критична ділянка повинна супроводжуватися прологом (entry section) — "закрити двері зсередини на засув" — і епілогом (exit section) — "відсунути засув", які не мають відношення до активності одиночного процесу. Під час виконання прологу процес повинен одержати дозвіл на вхід в критичну ділянку, а під час виконання епілогу — повідомити інші процеси, що він покинув критичну секцію.

У загальному випадку структура процесу, що бере участь у взаємодії, може бути представлена таким чином:

while (some condition) {
       entry section
             critical section
       exit section
             remainder section
}

Тут під remainder section розуміються всі атомарні операції, що не входять в критичну секцію.

---

3.3.1. Вимоги що пред'являються до алгоритмів Організація взаємовиключення для критичних ділянок дозволить уникнути виникнення race condition, але не є достатньою для правильної і ефективної паралельної роботи кооперативних процесів. 57Сформулюємо п'ять умов, які повинні виконуватися для програмного алгоритму організації взаємодії процесів, що мають критичні ділянки, якщо вони можуть проходити їх в довільному порядку: 1. Задача повинна бути вирішена чисто програмним способом на звичайній машині, що не має спеціальних команд взаємовиключення. При цьому передбачається, що основні інструкції мови програмування (такі примітивні інструкції як load, store, test) є атомарними операціями. 2. Не повинно існувати ніяких припущень про відносні швидкості процесів, що виконуються, або число процесорів, на яких вони виконуються. 3. Якщо процес P1 виконується в своїй критичній ділянці, то не існує ніяких інших процесів, які виконуються в своїх відповідних критичних секціях. Ця умова одержала назву умови взаємовиключення (mutual exclusion). 4. Процеси, які знаходяться поза своїми критичними ділянками і не збираються входити в них, не можуть перешкоджати іншим процесам входити в їх власні критичні ділянки. Якщо немає процесів в критичних секціях, і є процеси, що хочуть ввійти до них, то тільки ті процеси, які не виконуються в remainder section, повинні ухвалювати рішення про те, який процес увійде до своєї критичної секції. Таке рішення не повинно ухвалюватися нескінченно довго. Ця умова одержала назву умови прогресу (progress). 5. Не повинно виникати нескінченне очікування для входу процесу в свою критичну ділянку. Від того моменту, коли процес запросив дозвіл на вхід в критичну секцію, і до того моменту, коли він (процес) цей дозвіл одержав, інші процеси можуть пройти через свої критичні ділянки лише 58обмежене число раз. Ця умова одержала назву умови обмеженого очікування (bound waiting). 3.3.2. Заборона переривань Найпростішим рішенням поставленої задачі є наступна організація прологу і епілогу: while (some condition) { заборонити всі переривання critical section дозволити всі переривання remainder section } Оскільки, вихід процесу із стану виконання без його завершення здійснюється по перериванню, то усередині критичної секції ніхто не може втрутитися в його роботу. Проте таке рішення може призвести до серйозних наслідків, оскільки дає право процесу користувача дозволяти і забороняти переривання у всій обчислювальній системі. Допустимо, що в результаті помилки або злого наміру користувач заборонив переривання в системі і зациклив або завершив свій процес. Без перезавантаження системи в такій ситуації не обійтися. Проте, заборона і дозвіл переривань часто застосовуються як пролог і епілог до критичних секцій усередині самої операційної системи, наприклад, при оновленні вмісту PCB. 3.3.3. Змінна-замок Як наступна спроба рішення задачі для користувацьких процесів розглянемо іншу пропозицію. Візьмемо деяку змінну, доступну всім процесам, і покладемо її початкове значення рівним 0. Процес може увійти до критичної секції тільки тоді, коли значення цієї змінної-замку рівне 0, одночасно змінюючи її значення на 1 — закриваючи замок. При виході з критичної секції процес скидає її значення в 0 — замок відкривається (як у випадку з покупкою хліба студентами в розділі 5.2.). 59shared int lock = 0; while (some condition) { while(lock); lock = 1; critical section lock = 0; remainder section } На жаль, уважне вивчення показує, що таке рішення, не задовольняє умові взаємовиключення, оскільки дія while(lock); lock = 1; не є атомарним. Допустимо, що процес P0 протестував значення змінної lock і ухвалив рішення рухатися далі. У цей момент, ще до привласнення змінної lock значення 1, планувальник передав управління процесу P1. Він теж вивчає вміст змінної lock і теж ухвалює рішення увійти до критичної ділянки. Ми одержуємо два процеси одночасно виконуючих свої критичні секції. 3.3.4. Строге чергування Спробуємо вирішити задачу спочатку для двох процесів. Черговий підхід також використовуватиме загальну для них обох змінну з початковим значенням 0. Тільки тепер вона виконуватиме не роль замку для критичної ділянки, а явно указувати, хто може наступним увійти до нього. Для i-го процесу це виглядає так: shared int turn = 0; while (some condition) { while(turn != i); critical section turn = 1-i; remainder section } Легко бачити, що взаємовиключення гарантується, процеси входять в критичну секцію строго по черзі: P0, P1, P0, P1, P0, ... Але наш алгоритм не 60задовольняє умові прогресу. Наприклад, якщо значення turn рівне 1 і процес P0 готовий увійти до критичної ділянки, він не може зробити цього, навіть якщо процес P1 знаходиться в remainder section. 3.3.5. Прапори готовності Недолік попереднього алгоритму полягає у тому, що процеси нічого не знають про стан один одного у нинішній момент часу. Спробуємо виправити цю ситуацію. Хай два наші процеси мають масив прапорів готовності входу процесів, що розділяється, в критичну ділянку shared int ready[2]= {0, 0}; Коли i-й процес готовий увійти до критичної секції, він привласнює елементу масиву ready[i] значення рівне 1. Після виходу з критичної секції він, природно, скидає це значення в 0. Процес не входить в критичну секцію, якщо інший процес вже готовий до входу в критичну секцію або знаходиться в ній. while (some condition) { ready[i]= 1; while(ready[1-i]); critical section ready[i]= 0; remainder section } Одержаний алгоритм забезпечує взаємовиключення , дозволяє процесу, готовому до входу в критичну ділянку, увійти до нього відразу після завершення епілогу в іншому процесі, але все одно порушує умову прогресу. Хай процеси практично одночасно підійшли до виконання прологу. Після виконання привласнення ready[0]=1 планувальник передав процесор від процесу 0 процесу 1, який також виконав привласнення ready[1]=1. Після ці обидва процеси нескінченно довго чекають один одного на вході в критичну секцію. Виникає ситуація, яку прийнято називати тупиковою (deadlock). 3.3.6. Алгоритм Петерсона Перше рішення проблеми, задовольняюче всім вимогам і яке використовує ідеї раніше розглянутих алгоритмів, було запропоноване данським 61математиком Деккером (Dekker). У 1981 році Петерсон (Peterson) запропонував своє вирішення. Хай обидва процеси мають доступ до масиву прапорів готовності і до змінної черговості. shared int ready[2]= {0, 0}; shared int turn; while (some condition) { ready[i]= 1; turn =1- i; while(ready[1-i]&& turn == 1-i); critical section ready[i]= 0; remainder section } При виконанні прологу критичної секції процес Pi заявляє про свою готовність виконати критичну ділянку і одночасно пропонує іншому процесу приступити до його виконання. Якщо обидва процеси підійшли до прологу практично одночасно, то вони обидва оголосять про свою готовність і запропонують виконуватися один одному. При цьому одна з пропозицій завжди послідує після іншого. Тим самим роботу в критичній ділянці продовжить процес, якому була зроблена остання пропозиція.