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

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

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

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

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
} 

[3]

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

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
   • Жоден процес не може отримати достатньо ресурсів і завершитись, тобто цей стан небезпечний, відмова в запиті

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