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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Алгоритм[ред.ред. код]

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

Ресурси[ред.ред. код]

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

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

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

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

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

Обмеження[ред.ред. код]

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

Примітки[ред.ред. код]

  1. E. W. Dijkstra "EWD108: Een algorithme ter voorkoming van de dodelijke omarming" (датською; Алгоритм для запобігання смертельних обіймів)
  2. Bic, Lubomir F.; Shaw, Alan C. (2003). Operating System Principles. Prentice Hall. ISBN 0-13-026611-6. 
  3. Concurrency

Подальше читання[ред.ред. код]

Посилання[ред.ред. код]