7. Алгоритм банкіра для одного та декількох видів ресурсів.
Алгоритм планування, який дозволяє уникати взаємоблокувань, був розроблений Дейкстрою і має назву алгоритму банкіра. Він представляє собою розширення алгоритму виявлення тупіків, який було розглянуто в питанні„Виявлення взаємоблокувань при наявності одного ресурсу кожного типу”. Модель алгоритму базується на прикладі роботи банкіра в малому місті, що має справу з групою клієнтів, яким він видав кредит. Алгоритм перевіряє, чи веде виконання кожного запиту до небезпечного стану. Якщо так, то запит відхиляється. Якщо задоволення запиту до ресурсу приводить до безпечного стану, ресурс надається процесу.
Алгоритм банкіра можна узагальнити для керування системою з декількома видами ресурсів. На рис 5.7 зображено дві матриці:
Рис.5.7. Алгоритм банкіра в системі з декількома типами ресурсів.
Матриця зліва показує, скільки ресурсів кожного виду займає в даний час кожен з п’яти процесів. Матриця справа показує кількість ресурсів, які потрібно добавити кожному процесу для успішного завершення. Ці матриці на рис.5.2 R i C. Як і у випадку одного виду ресурсів, процеси повинні точно визначати необхідну сумарну кількість ресурсів до початку роботи для того, щоб система могла розраховувати праву матрицю в кожен момент часу.
Алгоритм перевірки стану безпеки системи.
1.Шукаємо в матриці R рядок, що відповідає процесу, чиї незадоволені потреби ресурсів менші або дорівнюють вектору A. Якщо такого рядка не існує, то система попаде через деякий час в тупік.
2.Припустимо, що процес, рядок якого вибрали в пункті 1, запитує всі необхідні ресурси (гарантується, що це можливо) і закінчує роботу. Відмічаємо цей процес як завершений і добавляємо всі його ресурси до вектора A.
3.Повторяємо кроки 1 і 2 до тих пір, поки всі процеси будуть відмічені як завершені і стан в цьому випадку буде безпечним, або відбудеться взаємоблокування – тоді стан небезпечний.
Дейкстра вперше опублікував алгоритм банкіра в 1965 році. Але незважаючи на те, що він є в кожній книжці з операційних систем, фактично на практиці його не використовують, бо наперед не відомо скільки ресурсів буде потрібно процесам в майбутньому. Крім того, кількість процесів не фіксована, вона динамічно змінюється по мірі входження користувачів в систему і виходу з неї. А також, ресурси, про які вважалось, що вони доступні, можуть несподівано зникнути (наприклад, поломка).
- Лекція 1. Вступ до операційних систем.
- 1.Поняття про операційні системи та їх місце в загальній структурі комп’ютера.
- 2. Основні функції операційної системи : розширення можливостей комп’ютера та керування його ресурсами.
- 3. Історія операційних систем.
- Лекція 2. Структура операційної системи.
- Таблиця 2.1
- Екзоядро
- Модель клієнт-сервер
- Лекція 3. Концепція процесу
- Лекція 4. Потоки в операційних системах.
- 3. Міжпроцесна взаємодія.
- 4.Примітиви міжпроцесної взаємодії.
- 5.Семафори та їх використання.
- 6.Поняття м’ютекса.
- 7.Поняття моніторів.
- 8.Поняття про бар’єри.
- 9.Поняття про системи передачі повідомлень.
- Лекція 5. Взаємоблокування.
- 2.Умови та моделювання взаємоблокувань.
- 3.Виявлення та усунення взаємоблокувань.
- 4.Уникнення взаємоблокувань при наявності декількох ресурсів кожного типу.
- 6. Уникнення взаємоблокувань.
- 7. Алгоритм банкіра для одного та декількох видів ресурсів.
- 8. Уникнення взаємоблокувань шляхом порушення умов їх здійснення
- Лекція 6. Основні поняття керування пам’яттю.
- 1.Однозадачна система без підкачки на диск.
- 2.Багатозадачність з фіксованими розділами
- 3.Поняття про підкачку даних.
- 5.Віртуальна пам’ять. Основні поняття.
- 6.Віртуальна пам’ять. Сторінкова організація пам’яті.
- 7.Характеристика основних алгоритмів заміщення сторінок.
- Лекція 7. Принципи роботи апаратури введення-виведення.
- 1.Пристрої введення-виведення.
- 2.Переривання персональної кс.
- Лекція 8.
- Лекція 9.
- Лекція 10. Файли та їх властивості.
- 1.Поняття файлової системи.
- 2.Іменування файлів.
- 3.Структура файлу.
- 4.Типи файлів.
- 5.Доступ до файлів. Атрибути файла.
- 6.Файли, відображувані на адресній простір памяті.
- 7.Каталоги.
- Лекція 11. Реалізація файлової системи.
- 1.Структура файлової системи.
- 2.Реалізація файлів.
- 3.Реалізація каталогів.
- Лекція 12 Планування в системах з одним процесором.
- 1.Поняття про планування.
- 2.Типи планування процесора.
- 3.Планування вводу-виводу.
- Лекція 13. Критерії планування.
- 1.Критерії короткотривалого планування.
- 2.Використання пріоритетів.
- 3.Альтернтитвні стратегії планування
- Лекція 14. Стратегії планування.
- 1.Стратегія планування „першим прийшов – першим обслуговується”.
- 2.Стратегія”кругове планування” .
- 4.Вибір самого короткого процесу.
- 5.Стртегія найменшого часу, що залишився.
- 7.Зниження пріорітету.
- Лекція 15. Багатопроцесорне планування і планування реального часу.
- 1. Класифікація багатопроцесорних систем.
- 3.Задачі планування в багатопроцесорній системі.
- 4. Планування процесів.
- 5.Планування потоків.
- Лекція 16. Основні підходи до планування потоків.
- 1.Розділення навантаження.
- 2.Бригадне планування.
- 3.Призначення процесорів.
- 4.Динамічне планування.
- Лекція 17. Планування реального часу.
- Лекція 18.
- 4. Парадигми.
- 5. Реалізація операційної системи
- Лекція 19. Операційні системи типу unix.
- 1.Історичні відомості про операційні системи типу unix.
- 2.Загальна архітектура системи unix.
- 3.Сучасні системи unix.
- 4.Історія виникнення операційної системи Linux.
- 5.Модульна структура операційної системи Linux.
- 6.Традиційне планування unix.
- Лекція 20. Характеристики операційної системи Windows 2000.
- 1. Історія виникнення Windows.
- Лекція 21. Особливості архітектури Windows xp.
- 1. Основні компоненти Windows xp.