7. Алгоритм банкіра для одного та декількох видів ресурсів.

Алгоритм планування, який дозволяє уникати взаємоблокувань, був розроблений Дейкстрою і має назву алгоритму банкіра. Він представляє собою розширення алгоритму виявлення тупіків, який було розглянуто в питанні„Виявлення взаємоблокувань при наявності одного ресурсу кожного типу”. Модель алгоритму базується на прикладі роботи банкіра в малому місті, що має справу з групою клієнтів, яким він видав кредит. Алгоритм перевіряє, чи веде виконання кожного запиту до небезпечного стану. Якщо так, то запит відхиляється. Якщо задоволення запиту до ресурсу приводить до безпечного стану, ресурс надається процесу.

Алгоритм банкіра можна узагальнити для керування системою з декількома видами ресурсів. На рис 5.7 зображено дві матриці:

Рис.5.7. Алгоритм банкіра в системі з декількома типами ресурсів.

Матриця зліва показує, скільки ресурсів кожного виду займає в даний час кожен з п’яти процесів. Матриця справа показує кількість ресурсів, які потрібно добавити кожному процесу для успішного завершення. Ці матриці на рис.5.2 R i C. Як і у випадку одного виду ресурсів, процеси повинні точно визначати необхідну сумарну кількість ресурсів до початку роботи для того, щоб система могла розраховувати праву матрицю в кожен момент часу.

Алгоритм перевірки стану безпеки системи.

1.Шукаємо в матриці R рядок, що відповідає процесу, чиї незадоволені потреби ресурсів менші або дорівнюють вектору A. Якщо такого рядка не існує, то система попаде через деякий час в тупік.

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

3.Повторяємо кроки 1 і 2 до тих пір, поки всі процеси будуть відмічені як завершені і стан в цьому випадку буде безпечним, або відбудеться взаємоблокування – тоді стан небезпечний.

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