Алгоритм банкіра

Алгоритм банкіра — алгоритм, винайдений Едсгером Дейкстрою, який призначений для уникнення взаємних блокувань під час розподілу ресурсів. Він досліджує можливий розвиток подій шляхом відтворення розподілу заздалегідь визначеної кількості ресурсів, і тоді робить перевірку на безпечність стану з метою дослідження на можливі умови взаємних блокувань для всіх інших очікуючих активностей, перед прийняттям рішення чи можна дозволити подальший розподіл.

Алгоритм було винайдено під час розробки операційної системи THE і спершу описано в EWD108. Назва подібна до того, як банкіри звітують про обмеження ліквідності.

Алгоритм

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

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

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

Ресурси

Для роботи алгоритму банкіра потрібно знати три речі:

• Скільки кожного ресурсу може запитати процес
• Скільки кожного ресурсу кожний процес утримує на поточний момент
• Скільки кожного ресурсу доступно в системі на поточний момент

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

1. запит ≤ заявка (максимум), інакше встановлюється помилка через запит процесом ресурсів більше попередньо заявленої ним кількості.
2. запит ≤ доступно, інакше процес очікує доки ресурси звільняться.

Приклади ресурсів, що відстежуються у справжніх системах це пам'ять, семафори та інтерфейси доступу.

Приклад

Розглянемо систему, що розрізняє чотири типи ресурсів (A, B, C і D). Наступний приклад показує як можуть бути розподілені ресурси. Зауважте, що цей приклад показує систему в момент перед тим, як надходить новий запит на ресурси. Типи та кількість ресурсів абстрактні. Справжні системи матимуть справу зі значно більшою кількістю ресурсів.

Доступні ресурси в системі: A B C D 3 1 1 2 

Процеси (наразі розподілені ресурси): A B C D P1 1 2 2 1 P2 1 0 3 3 P3 1 1 1 0 

Процеси (заявки на ресурси): A B C D P1 3 3 2 2 P2 1 2 3 4 P3 1 1 5 0 

Безпечні та небезпечні стани

Стан у попередньому прикладі вважається безпечним, якщо можливо для всіх процесів завершити свою роботу. Через те, що система не може знати, коли процеси завершать свою роботу і скільки саме ресурсів буде ними запитано, система вважає, що всі процеси колись запитають максимальну заявлену ними кількість ресурсів і завершаться невдовзі потому. Це розумне припущення в більшості випадків, бо система не надто опікується як довго кожний процес виконується (у будь-якому випадку не з погляду уникнення взаємних блокувань). Якщо процес завершується так і не запитавши заявленої кількості ресурсів, це тільки полегшує роботу системи.

При цьому припущенні алгоритм визначає стан як безпечний шляхом пошуку можливого набору запитів процесів, який дозволить кожному процесу отримати заявлену кількість ресурсів і тоді завершитись (із поверненням ресурсів системі). Будь-який стан, в якому такого набору не існує, є небезпечним.

Псевдокод

function bankers_algorithm(set of processes P, currently available resources A) { while (P not empty) { boolean found = false for each (process p in P) { Cp = current_resource_allocation_for_process(p) Mp = maximum_resource_requirement_for_process(p) if (Mp − Cp ≤ A) { // p може отримати все, що йому потрібно. // Припустимо він зробив це, завершився і вивільнив ресурси назад в систему. A = A + Cp remove_element_from_set(p, P) found = true } } } if (not found) { return UNSAFE } return SAFE } 

Приклад

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

1. P1 отримує 2 A, 1 B і 1 D додаткових, досягнув своєї заявки
   • Тепер система має 1 A, жодного B, 1 C і 1 D доступних ресурсів
2. P1 завершується, повернув 3 A, 3 B, 2 C і 2 D ресурсів в систему
   • Тепер система має 4 A, 3 B, 3 C і 3 D доступних ресурсів
3. P2 отримує 2 B і 1 D додаткових ресурсів, тоді завершується, повернувши ресурси
   • Тепер система має 5 A, 3 B, 6 C і 6 D ресурсів
4. P3 отримує 4 C і завершується
   • Тепер система має всі свої ресурси: 6 A, 4 B, 7 C і 6 D
5. Через те, що всі процеси мали змогу завершитись, цей стан був безпечним

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

Для прикладу небезпечного стану, уявіть що станеться якщо процес 2 на початку утримує на 1 ресурс B більше.

Запити

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

1. Чи може бути запит виконано?
   • Якщо ні, запит неможливий і відповіддю буде відмова або переміщення запиту до списку очікування
2. Припустимо можливість виконати запит є
3. Чи безпечний новий стан?
   • Якщо так, тоді виконуємо запит
   • Якщо ні, або відмовляємо, або переміщуємо до списку очікування

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

Приклад

Продовжимо попередній приклад, припустимо процес 3 запитав 2 одиниці ресурсу C.

1. Доступного ресурсу C недостатньо для виконання запиту
2. Відмовлено

З іншого боку, уявімо, що процес 3 запросив 1 одиницю ресурсу C.

1. В такому випадку достатньо ресурсів для задоволення цього запиту
2. Припустимо запит задоволено
   • Новий стан системи:

 Доступні системні ресурси A B C D Вільно 3 1 0 2 

 Процеси (наразі розподілені ресурси): A B C D P1 1 2 2 1 P2 1 0 3 3 P3 1 1 2 0 

 Процеси (заявки на ресурси): A B C D P1 3 3 2 2 P2 1 2 3 4 P3 1 1 5 0 

1. Визначення безпечність цього стану
   1. P1 може отримати 2 A, 1 B і 1 D і завершитись
   2. Тоді, P2 може отримати 2 B і 1 D і завершитись
   3. Насамкінець, P3 може отримати 3 C і завершитись
   4. Таким чином, новий стан безпечний
2. Через це задовольняємо запит

Наостанок, припустимо що процес 2 запитав 1 одиницю ресурсу B.

1. Маємо достатньо ресурсів
2. Припустимо, що ми задовольнили запит, новий стан буде:

 Доступні системні ресурси A B C D Вільно 3 0 1 2 

 Процеси (наразі розподілені ресурси): A B C D P1 1 2 2 1 P2 1 1 3 3 P3 1 1 1 0 Процеси (заявки на ресурси): A B C D P1 3 3 2 2 P2 1 2 3 4 P3 1 1 5 0 

1. Чи безпечний це стан?
   • P1 не може отримати достатньо ресурсу B
   • P2 не може отримати достатньо ресурсу B
   • P3 не може отримати достатньо ресурсу C
   • Жоден процес не може отримати достатньо ресурсів і завершитись, тобто цей стан небезпечний, відмова в запиті

Зауважте, що в цьому прикладі жоден процес не зміг завершитись. Можливий стан коли частина процесів можуть завершитись, а частина ні, це все ще небезпечний стан.

Обмеження

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

Примітки

1. E. W. Dijkstra "EWD108: Een algorithme ter voorkoming van de dodelijke omarming [ 14 травня 2011 у Wayback Machine.]" (данською; Алгоритм для запобігання смертельних обіймів)
2. Bic, Lubomir F.; Shaw, Alan C. (2003). Operating System Principles. Prentice Hall. ISBN .^{[недоступне посилання]}
3. (PDF). Архів оригіналу (PDF) за 6 січня 2014. Процитовано 22 вересня 2010.

Подальше читання

• "" by Silberschatz, Galvin, and Gagne (pages 259-261 of the 7th edition)
• "EWD623: The mathematics behind the Banker’s Algorithm [ 8 червня 2011 у Wayback Machine.]" (1977) by E. W. Dijkstra, published as pages 308–312 of Edsger W. Dijkstra, Selected Writings on Computing: A Personal Perspective, Springer-Verlag, 1982.

Посилання

• Deadlock Recovery, Avoidance and Prevention [ 31 серпня 2010 у Wayback Machine.]