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

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

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

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

Іншим способом є використання блокуючих змінних. З кожним ресурсом, що розділяється, зв'язується двійкова змінна, яка набуває значення 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 розуміються всі атомарні операції, що не входять в критичну секцію.