Механізми синхронізації процесів

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

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

Семафор

Семафор - це захищена змінна, значення якої можна опитувати і змінювати тільки за допомогою операції

ініціалізація_семафора та двох спеціальних операцій P і V:

• операція P над семафором S записується як P (S) і виконується за правилами:

якщо S> 0 то S: = S-1 інакше (очікувати на S);

• операція V над семафором S записується як V (S) і виконується за правилами:

якщо (один або більше процесів очікують на S) то (дозволити одному з процесів продовжити роботу) інакше S: = S +1.

Розрізняють два види семафорів: двійкові семафори, у яких S може приймати значення 0 і 1, і вважають семафори, де S може приймати невід'ємні цілі значення.

Подібно операції проверіть_і_установіть, операції ініціалізація_семафора, P (S) і V (S) є неподільними.

Ділянки взаимоисключения по семафору S обрамляются операціями P (S) і V (S). Якщо одночасно декілька процесів спробують виконати операцію P (S), то тільки одному з них буде дозволено це зробити, а іншим доведеться чекати.

Семафори і операції над ними можуть бути реалізовані як програмно (рис. 3.5), так і апаратно. при програмноїреалізації вони розміщуються в тій частині ядра операційної системи, де здійснюється управління зміною станів процесів.
Узагальнююче засіб синхронізації процесів запропонував Дейкстра, який ввів два нових примітиву. В абстрактній формі ці примітиви, що позначаються P і V, оперують над цілими невід'ємними змінними, званими семафорами. Нехай S такий семафор. Операції визначаються наступним чином:
V (S): мінлива S збільшується на 1 одним неподільним дією; вибірка, інкремент та запам'ятовування не можуть бути перервані, і до S немає доступу іншим процесам під час виконання цієї операції.
P (S): зменшення S на 1, якщо це можливо. Якщо S = 0, то неможливо зменшити S і залишитися в області цілих невід'ємних значень, в цьому випадку процес, що викликає P-операцію, чекає, поки це зменшення стане можливим. Успішна перевірка і зменшення також є неподільною операцією.

Рис. 2.5. Реалізація критичної секції з використанням системних функцій WAIT (D) і POST (D)
В окремому випадку, коли семафор S може приймати тільки значення 0 і 1, він перетворюється на блокуючу змінну. Операція P містить в собі потенційну можливість переходу процесу, який її виконує, в стан очікування, в той час як V-операція може за деяких обставин активізувати інший процес, призупинений операцією P (порівняйте ці операції з системними функціями WAIT і POST).
Розглянемо використання семафорів на класичному прикладі взаємодії двох процесів, що виконуються в режимі мультипрограмування, один з яких пише дані в буферний пул, а інший зчитує їх з буферного пула. Нехай буферний пул складається з N буферів, кожний з яких може містити один запис. Процес "письменник" повинен припинятися, коли всі буфери опиняються зайнятими, і активізуватися при звільненні хоча б одного буфера. Навпаки, процес "читач" припиняється, коли всі буфери порожні, і активізується при появі хоч би одного запису.
Введемо два семафора: e - число порожніх буферів і f - число заповнених буферів. Припустимо, що запис у буфер і зчитування з буфера є критичними секціями (як у прикладі з принт-сервером на початку цього розділу). Введемо також двійковий семафор b, який використовується для забезпечення взаємного виключення. Тоді процеси можуть бути описані в такий спосіб:
/ / Глобальні змінні
# Define N 256
int e = N, f = 0, b = 1;
void Writer ()
while (1)
PrepareNextRecord (); / * підготовка нового запису * /
P (e) / * Зменшити число вільних буферів, якщо вони є * /
/ * У противному випадку - чекати, поки вони звільняться * /
P (b) / * Вхід в критичну секцію * /
AddToBuffer (); / * Додати новий запис у буфер * /
V (b) / * Вихід з критичної секції * /
V (f) / * Збільшити число зайнятих буферів * /
void Reader ()
while (1)
P (f) / * Зменшити число зайнятих буферів, якщо вони є * /
/ * У противному разі чекати, поки вони з'являться * /
P (b) / * Вхід в критичну секцію * /
GetFromBuffer (); / * Взяти запис з буфера * /
V (b) / * Вихід з критичної секції * /
V (e) / * Збільшити число вільних буферів * /
ProcessRecord (); / * Опрацювати запис * /
Тупики
Наведений вище приклад допоможе нам проілюструвати ще одну проблему синхронізації - взаємні блокування, звані також дедлок (deadlocks), клінчами (clinch) або тупиками. Якщо переставити місцями операції P (e) і P (b) у програмі "письменника", то при деякому збігу обставин ці два процеси можуть взаємно заблокувати один одного. Дійсно, нехай "письменник" першим увійде в критичну секцію та виявить відсутність вільних буферів; він почне чекати, коли "читач" візьме чергову запис з буфера, але "читач" не зможе цього зробити, тому що для цього необхідно увійти в критичну секцію, вхід до якої заблоковано процесом "письменником".
Розглянемо ще один приклад глухого кута. Нехай двох процесів, що виконується в режимі мультипрограмування, для виконання їхньої роботи потрібно два ресурси, наприклад, принтер і диск. На малюнку 2.6, а показані фрагменти відповідних програм. І нехай після того, як процес А зайняв принтер (встановив блокує змінну), він був перерваний. Управління отримав процес В, який спочатку зайняв диск, але при виконанні наступної команди був заблокований, так як принтер виявився вже зайнятим процесом А. Управління знову отримав процес А, який у відповідності зі своєю програмою зробив спробу зайняти диск і був заблокований: диск вже розподілено процесу В. У такому положенні процеси А і В можуть знаходитися як завгодно довго.
У залежності від співвідношення швидкостей процесів, вони можуть або цілком незалежно використовувати колективні ресурси (г), або утворювати черги до ресурсів (в), або взаємно блокувати один одного (б). Тупикові ситуації треба відрізняти від простих черг, хоча і ті й інші виникають при спільному використанні ресурсів і зовні виглядають схоже: процес призупиняється і чекає звільнення ресурсу. Однак чергу - це нормальне явище, невід'ємною ознакою високого коефіцієнта використання ресурсів при випадковому надходженні запитів. Вона виникає тоді, коли ресурс недоступний в даний момент, але через деякий час він звільняється, і процес продовжує своє виконання. Тупик ж, що видно з його назви, є до певної міри нерозв'язною ситуацією.
У розглянутих прикладах глухий кут був утворений двома процесами, але взаємно блокувати один одного можуть і більше число процесів.
Проблема тупиків включає в себе наступні завдання:
- Запобігання тупиків,
- Розпізнавання тупиків,
- Відновлення системи після тупиків.

Рис. 2.6. (A) фрагменти програм А і В, які поділяють принтер і диск; (б) взаємне блокування (клінч); (в) чергу до разделяемому диску; (г) незалежне використання ресурсів
Тупики можуть бути запобігти на стадії написання програм, тобто програми повинні бути написані таким чином, щоб глухий кут не міг виникнути ні при якому співвідношенні взаємних швидкостей процесів. Так, якщо б у попередньому прикладі процес А і процес У запитували ресурси в однаковій послідовності, то глухий кут був би в принципі неможливий. Другий підхід до запобігання тупиків називається динамічним і полягає у використанні певних правил при призначенні ресурсів процесам, наприклад, ресурси можуть виділятися в певній послідовності, загальною для всіх процесів.
У деяких випадках, коли тупикова ситуація утворена багатьма процесами, що використовують багато ресурсів, розпізнавання глухого кута є нетривіальним завданням. Існують формальні, програмно-реалізовані методи розпізнавання тупиків, засновані на веденні таблиць розподілу ресурсів і таблиць запитів до зайнятих ресурсів. Аналіз цих таблиць дозволяє виявити взаємні блокування.
Якщо ж тупикова ситуація виникла, то не обов'язково знімати з виконання всі заблоковані процеси. Можна зняти тільки частину з них, при цьому звільняються ресурси, очікувані іншими процесами, можна повернути деякі процеси в область свопінгу, можна зробити "відкат" деяких процесів до так званої контрольної точки, в якій запам'ятовується вся інформація, необхідна для відновлення виконання програми з даного місця. Контрольні точки розставляються в програмі в місцях, після яких можливе виникнення безвиході.
З усього вищесказаного ясно, що використовувати семафори потрібно дуже обережно, тому що одна незначна помилка може призвести до зупинки системи. Для того, щоб полегшити написання коректних програм, було запропоновано високорівневий засіб синхронізації, зване монітором. Монітор - це набір процедур, змінних і структур даних. Процеси можуть викликати процедури монітора, але не мають доступу до внутрішніх даних монітора. Монітори мають важливе властивість, яка робить їх корисними для досягнення взаємного виключення: тільки один процес може бути активним по відношенню до монітора. Компілятор обробляє виклики процедур монітора особливим чином. Зазвичай, коли процес викликає процедуру монітора, то перші кілька інструкцій цієї процедури перевіряють, не активний може який-небудь інший процес по відношенню до цього монітора. Якщо так, то зухвалий процес припиняється, поки інший процес не звільнить монітор. Таким чином, виключення входу декількох процесів в монітор реалізується не програмістом, а компілятором, що робить помилки менш імовірними.

МОНІТОРИ

Монітор - це механізм організації паралелізму, який містить як дані, так і процедури, необхідні для

реалізації динамічного розподілу конкретного загального ресурсу або групи загальних ресурсів.

Щоб забезпечити виділення потрібного йому ресурсу, процес повинен звернутися до конкретної процедури монітора.Необхідність входу в монітор в різні моменти часу може виникати у багатьох процесів. Однак вхід до монітору знаходиться під жорстким контролем: тут здійснюється взаємовиключає процесів, так що в кожен момент часу тільки одному процесу дозволяється увійти в монітор. Процесам, які хочуть увійти в монітор, коли він зайнятий,доводиться чекати, причому режимом очікування автоматично керує сам монітор.Якщо процес звертається до деякої процедурі монітора і виявляється, що відповідний ресурс вже зайнятий, то ця процедура монітора видає процесу команду WAIT (ЧЕКАТИ). Процес, який отримав таку команду, переводиться в режим очікування поза монітора.З часом процес, який займав потрібний ресурс, звільняє його, звертаючись для цього до монітора. Відповідна процедура монітора може просто прийняти повідомлення про повернення ресурсу, а потім чекати, поки не надійде запит від іншого процесу, якому буде потрібно цей ресурс. Однак може виявитися, що вже є процеси, які очікують звільнення даного ресурсу. У цьому випадку монітор виконує примітив оповіщення SIGNAL, щоб один з очікуючих процесів міг зайняти даний ресурс і покинути чергу до монітора. Якщо процес сигналізує про звільнення ресурсу і в цей час немає процесів, що очікують цей ресурс, то подібне сповіщення не викликає ніяких інших дій, крім того, що монітор знову вносить ресурс в список вільних.