6. Уникнення взаємоблокувань.

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

Алгоритми, що розглядатимуться далі використовують інформацію з рис. 5.4. В будь-який момент часу існує поточний стан, складений з величин E, A, C i R. Говорять, що стан безпечний, якщо він не знаходиться в тупіку і існує деякий порядок планування, при якому кожен процес може працювати до завершення, навіть якщо всі процеси навколо негайно захочуть отримати свою максимальну кількість ресурсів. Розглянемо приклад з одним ресурсом (рис. 5.5).

На рис. 5.5(а) дано стан, в якому процес А займає 3 екземпляри ресурсу, але йому потрібно буде 9 екземплярів. Процес В в даний момент зайняв 2 екземпляри, але в майбутньому йому потрібно буде 4. Процес С володіє двома, але може вимагати ще п’ять. В системі є всього 10 екземплярів даного ресурсу, 7 з них уже розподілено, 3 поки що вільні.

Рис. 5.5 Демонстрація того, що стан а є безпечним.

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

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

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

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

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

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

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

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

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

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

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