Попередні заявки і алгоритм банкіра

Ієрархічне виділення.

Всі класи ресурсів розбиваються по рівнях з номерами від 1 до N, кожен рівень містить тільки один клас. Процес має право запрошувати ресурси тільки з класів з вищими номерами, ніж у тих, якими він вже володіє. Ця стратегія також запобігає виникненню тупиків. У кожен момент часу в системі один або декілька процесів мають клас закріплених за ними ресурсів вище, ніж у інших. Ці процеси, що володіють ресурсами високого рівня, можуть безперешкодно виконуватися і завершитися без блокування. Отже, в кожен момент часу є хоч би один здібний до виконання процес. Якщо не поступатимуть нові процеси, то всі процеси, вже наявні в системі, врешті-решт завершаться - тупик відсутня. Хоча в ієрархічній стратегії процес обмежений в послідовності запитів і можлива ситуація, в якій він повинен утримувати за собою ресурс більш тривалий час, ніж це дійсно необхідно, ця стратегія дозволяє досягти непоганої ефективності, особливо при правильному розподілі ресурсів по рівнях. Доцільно вищі рівні призначати дефіцитнішими і дорожчими ресурсам; як правило, і використання таких ресурсів є більш швидкоплинним. Ієрархічну стратегію застосовує, наприклад, OS/390 стосовно деяких системних структур даних.

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

Ця стратегія названа так тому, що дії ОС нагадують дії банкіра, що видає позики клієнтам, саме на такому прикладі ця стратегія була розглянута в першоджерелі [7]. Застосування цієї стратегії вимагає, щоб процес передав ОС "попередню заявку" (advanced claim) і в ній вказав максимальний об'єм ресурсів, який йому знадобиться. В ході виконання процес може в довільному порядку запрашивать/освобождать ресурси, не виходячи, проте, за межі заявленого об'єму. Ситуація в системі називається такою, що реалізовується, якщо

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

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

• перший процес може нормально завершитися навіть, якщо він повністю вибере ресурси по своїй заявці;
• другий процес може нормально завершитися навіть, якщо він повністю вибере ресурси по своїй заявці, за умови, що завершиться перший процес і звільнить утримувані ним ресурси;
• i-й процес може нормально завершитися навіть, якщо він повністю вибере ресурси по своїй заявці, за умови, що завершиться i-1-й процес і звільнить утримувані ним ресурси.

Інакше ситуація називається небезпечною.

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

Приклад представлений на Малюнку 5.3.: хай у ОС є всього 12 ресурсів одного класу і на даний момент виконуються три процеси - P1, P2 і P3, їх заявки складають 12, 4 і 8 ресурсів відповідно. На даний момент часу процесу P1 виділено 4 ресурси, процесу P2 - 2, процесу P3 - 4 - Ріс.5.3.а. У резерві ОС залишаються, таким чином, 2 ресурси. Ситуація Ріс.5.3.а є безпечною. ОС може виділити два ресурси, що залишилися, процесу P2, і цей процес, повністю отримавши по своїй заявці, може завершиться, тоді системний резерв збільшиться до 4 ресурсів. Цей резерв ОС віддасть процесу P3, він, завершившись, передасть в резерв ОС 8 ресурсів, які буде досить для задоволення заявки процесу P1. Ситуація стане небезпечною, якщо ОС виділить ресурс якому-небудь іншому процесу, окрім P2 - см.Рис.5.3.б. У цій ситуації ОС за рахунок свого резерву не може повністю задовольнити жодну заявку.

а) безпечна б) небезпечна Ріс.5.3. Аналіз ситуації

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

1. Створити список, елементами якого є процеси з їх ресурсами і заявками.
2. Якщо список порожній, - встановити прапор безпечної ситуації і перейти до п. 7.
3. Знайти в списку процес, заявка якого може бути задоволена з системного резерву.
4. Якщо такий процес не знайдений, - встановити прапор небезпечної ситуації і перейти до п.7.
5. Видалити знайдений процес із списку і передати ті ресурси, якими він володів в системний резерв.
6. Перейти до п.2.
7. Закінчити перевірку.

Дата добавления: 2014-12-23