Алгоритми керування ресурсами

Тупики

Семафори

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

- операція D(S) – це змінна S, яка збільшується на одиницю однією неподільною дією, тобто вибірка, інкремент, і запам’ятовування не можуть бути перервані і до S не має доступу іншим процесам під час виконання цієї операції.

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

Розглянемо використання семафорів на класичному прикладі взаємодії двох процесів, що виконуються в режимі мультипрограмування, один з яких пише дані в буферний пул, а другий зчитує їх з буферного пула. Нехай буферний пул складається з n-буферів, кожний з яких може містити один запис. Процес «письменник» повинен припинятись, коли всі буфери являються зайнятими, і активізуватися при звільненні хоча б одного буфера. Напроти, процес «читач» припиняється, коли всі буфери порожні і активізується появою хоча б одного з записів. Введемо 2 семафори: 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(e);

V(b);

ProcessRecord();

}

Розрізняють 2 види семафорів:

- двійкові, у яких S може приймати значення 0 та 1

- рахуючи, де S може приймати не негативні цілі значення.

Подібно операції «перевірити і установити», операція семафора є неподільними. Ділянки взаємовиключення по семафорі S обрамляються операціями P(S) i D(S).

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

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

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

РИСУНОК 3

І нехай після того як процес А зайняв принтер, установив блокуючи мінну, він був перерваний. Керування одержав процес В, який спочатку зайняв диск. Але при виконанні наступної команди був заблокований тому, що принтер виявився зайнятий процесом А. Керування знову одержав процес А, який у відповідності зі своєю програмою зробив спробу зайняти диск, і був заблокований. Диск уже розподілений процесу В. У такому положенні процеси А і В можуть перебувати безкінечно довго. Залежно від співвідношення швидкостей процесів, вони можуть або зовсім незалежно використовувати поділювані ресурси, або утворити черги до поділюваних ресурсів, або взаємно блокувати один одного. Тупикові ситуації треба відрізняти від простих черг, хоча і ті, і інші виникають при спільному використанні ресурсів.

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

Проблеми тупиків містять у собі наступні задачі:

- запобігання тупиків.

- розпізнавання тупиків.

- відновлення після тупиків.

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

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

Існують формальні програмно реалізовані методи розпізнавання тупиків засновані на веденні таблиць розподілу ресурсів і таблиць запитів до зайнятих ресурсів. Інший підхід до запобігання тупиків назив. динамічним і полягає в використанні певних правил при призначенні ресурсів процесам. Наприклад, ресурси можуть виділятися в певній послідовності загальній для всіх процесів. Якщо тупикова ситуація виникла, то не обов’язково знімати з виконання всі заблоковані процеси. Можна зняти тільки частину з них, при цьому звільняється ресурси, очікувані іншими процесами. Можна повернути деякі процеси в область свопінга. Можна робити відкат деяких процесів до контрольної точки, у якій запам’ятовується вся інформація, необхідна для відновлення виконання програми з даного місця. Контрольні точки розставляються в програмі в місцях після яких можливі виникнення тупика. Для того, щоб полегшити написання коректних програм у запропонований високорівнений засіб синхронізації, називаний монітором. Монітор – це набір процедур, змінних і структур даних. Процеси можуть викликати процедури монітора, але не мають доступу до внутрішніх даних монітора. Монітори мають важливу властивість, що робить їх корисними для досягнення взаємовиключення. Тільки 1 процес може бути активним по відношенню до монітора. Компілятор обробляє випадки процедур монітора особливим образом. Коли процес викликає процедуру монітора, то перші кілька інструкцій цієї процедури перевіряють чи неактивний який-небудь інший процес стосовно цього монітора. Якщо так, то визиваючий процес припиняється поки інший процес не звільнить монітор. Таким чином, виключення в коду декількох процесів в монітор реалізується не програмістом, а компілятором, що робить помилки менш імовірними.

У розподілених системах, що скл. з декількох процесорів, кожний з яких має власну ОЗУ, семафори і монітори виявляються непридатними. У таких системах синхронізація може бути реалізована тільки за допомогою обміну повідомленнями.

ЛЕКЦІЯ 3

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

ОС може прийняти, відкласти або проігнорувати запит на ресурс, що залежить від реалізованого в ОС алгоритму керування ресурсами. Існують також комбіновані способи формування запитів на ресурс з попереднім замовленням у пакетів завдань, або в програмі виконавчому запиті під час виконання програми.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Механізми синхронізації процесів	\|	Алгоритм запобігання тупиків

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.