Критична секція
Зміст
- 1 Загальні відомості
- 2 Апарат подій для роботи з критичними секціями
- 3 Порівняння критичних секцій та м'ютексів
- 4 Робота з критичними секціями у Windows
- 5 Приклад використання критичної секції
- 6 Задача виробник-споживач
- 7 Рішення задачі виробник-споживач
- 8 Псевдокод рішення задачі виробник-споживач
- 9 Проблема взаємних блокувань
Загальні відомості
Важливим поняттям синхронізації процесів є поняття "Критична секція" програми. Критична секція - це частина програми, в якій здійснюється доступ до даних, що розділяються. Щоб виключити ефект гонок по відношенню до деякого ресурсу, необхідно забезпечити, щоб в кожен момент в критичній секції, пов'язаній з цим ресурсом, знаходився максимум один процес. Цей прийом називають взаємним виключенням.
Простий спосіб забезпечити взаємне виключення - дозволити процесу, що знаходиться в критичній секції, забороняти всі переривання. Проте цей спосіб непридатний, оскільки небезпечно довіряти управління системою призначеному для користувача процесу; він може надовго зайняти процесор, а при краху процесу в критичній області крах потерпить вся система, тому що переривання ніколи не будуть дозволені.
Іншим способом є використання блокуючих змінних. З кожним ресурсом, що розділяється, зв'язується двійкова змінна, яка набуває значення 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);
Задача виробник-споживач
Потік-виробник створює об’єкти і поміщає їх у буфер. Операція розміщення об'єкта не є атомарною
Потік-споживач отримує об’єкти і видаляє їх з буфера. Операція видалення об'єкта не є атомарною
Буфер має фіксовану довжину N
Вимоги:
1. Коли виробник або споживач працює з буфером, усі інші потоки повинні чекати завершення цієї операції
2. Коли виробник має намір помістити об'єкт у буфер, а буфер повний, він має чекати, поки в буфері звільниться місце
3. Коли споживач має намір отримати об'єкт з буфера, а буфер порожній, він має чекати, поки в буфері з'явиться об'єкт
Рішення задачі виробник-споживач
1). Організуємо критичну секцію для роботи з буфером. Для цього використаємо двійковий семафор lock
2). Для організації очікування виробника впровадимо семафор empty, значення якого дорівнює кількості вільних місць у буфері
Виробник перед спробою додати об'єкт у буфер зменшує цей семафор, а якщо той дорівнював 0 – переходить у стан очікування Споживач після того, як забере об'єкт з буфера, збільшує цей семафор, при цьому, можливо, ініціюється пробудження виробника
3). Для організації очікування споживача впровадимо семафор full, значення якого дорівнює кількості зайнятих місць у буфері
Споживач перед спробою забрати об'єкт з буфера зменшує цей семафор, а якщо той дорівнював 0 – переходить у стан очікування Виробник після того, як додасть об'єкт до буфера, збільшує цей семафор, при цьому, можливо, ініціюється пробудження споживача
Псевдокод рішення задачі виробник-споживач
semaphore lock = 1, empty = n, full = 0; // на початку буфер порожній
void producer() {
while(1) { // працює постійно
item = produce_new_item(); // створюємо об'єкт
P(empty); // перевіряємо наявність місця
P(lock); // входимо у критичну секцію
add_to_buffer(item); // додаємо об'єкт до буфера
V(lock); // виходимо з критичної секції
V(full); // повідомляємо про новий об'єкт
}
}
void consumer() {
while(1) { // працює постійно
P(full); // перевіряємо наявність об'єкта
P(lock); // входимо у критичну секцію
item = get_from_buffer(); // забираємо об'єкт з буфера
V(lock); // виходимо з критичної секції
V(empty); // повідомляємо про вільне місце
consume_new_item(item); // споживаємо об'єкт
}
}
Проблема взаємних блокувань
Припустимо, у функції “виробник” ми поміняли місцями P(empty) і P(lock):
void producer() {
while(1) { // працює постійно
item = produce_new_item(); // створюємо об'єкт
P(lock); // входимо у критичну секцію
P(empty); // перевіряємо наявність місця
add_to_buffer(item); // додаємо об'єкт до буфера
V(lock); // виходимо з критичної секції
V(full); // повідомляємо про новий об'єкт
}
}
Перевірка умови з можливим очікуванням здійснюється всередині критичної секції. Можлива така послідовність дій:
1). Виробник входить у критичну секцію, закриваючи семафор lock
2). Виробник перевіряє семафор empty і очікує на ньому (буфер повний)
3). Споживач намагається ввійти у критичну секцію і блокується на семафорі lock
Така ситуація називається взаємне блокування або тупик (deadlock)
