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

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