4.Уникнення взаємоблокувань при наявності декількох ресурсів кожного типу.
Якщо в системі існує декілька екземплярів деяких з ресурсів, для виявлення взаємоблокувань необхідний інший метод. Розглянемо алгоритм, що базується на матрицях, який виявляє тупіки серед n процесів, від P1 до Pn. Нехай m – це число класів ресурсів, причому в системі E1 - ресурсів класу 1, E2 – ресурсів класу 2 і, в загальному, Ei –ресурсів класу i (де 1≤i≤m). E – вектор існуючих ресурсів. Він передає загальну кількість наявних екземплярів кожного ресурсу.
Далі потрібно два масиви: C – матриця поточного розподілу і R – матриця запитів. I-ий рядок в матриці C показує, скільки представників кожного класу ресурсів в даний момент використовує процес Pi. Таким чином, Cij – кількість екземплярів ресурсу j, яке займає процес i. Аналогічно Rij – кількість екземплярів ресурсу j, які хоче отримати процес Pi. Ці чотири структури показано на рис.5.3.
Рис.5.3. Чотири структури даних, необхідних для алгоритму виявлення тупіків
Іншими словами, якщо додати всі екземпляри ресурсу j, надані процесам і доступні в даний момент, то в результаті ми отримаємо існуючу в системі кількість екземплярів цього класу ресурсів.
Алгоритм виявлення взаємоблокувань базується на порівнянні векторів. Визначимо, що для двох векторів A і B відношення A≤B означає, що кожен елемент вектору A менше або дорівнює відповідному елементу вектора B. Математично запис буде таким: A≤B тоді і тільки тоді, коли Ai≤Bi для 1≤i≤m.
Після завершення алгоритму відомо, що будь-який немаркований процес знаходиться в тупіковій ситуації.
Кроки алгоритму виявлення тупіків:
Шукаємо немаркований процес Pi, для якого i-ий рядок матриці R менше вектора A або дорівнює йому.
Якщо такий процес знайдено, добавляємо i-ий рядок матриці C до вектора A, маркуємо процес і повертаємося до кроку 1.
Якщо таких процесів не існує, то робота алгоритму закінчується.
Завершення алгоритму означає, що всі немарковані процеси, якщо такі є, попали в тупік.
На першому кроці алгоритм шукає процес, який може допрацювати до кінця. Такий процес характеризується тим, що всі необхідні для нього ресурси повинні знаходитися серед доступних в даний момент ресурсів. Тоді вибраний процес пропрацює до свого завершення і після цього поверне ресурси, які він займав, в загальний фонд доступних ресурсів. Потім процес маркується як закінчений. Оскільки алгоритм не є детермінованим (процеси можна переглядати в довільному порядку), то результат завжди однаковий.
Розглянемо приклад (рис.5.4)
Рис.5.4. Приклад використання алгоритму виявлення тупіків.
Тут є три процеси і чотири класи ресурсів. Працюючи з алгоритмом виявлення взаємоблокувань, ми шукаємо процес, чий запит ресурсів може бути задоволений в даній системі. Тільки третій процес може отримати все потрібне, тому він працює, закінчується і повертає всі свої ресурси, даючи A=(2 2 2 0). З цього моменту може виконуватись процес 2, по завершенні повертаючи свої ресурси в систему. Ми отримаємо А=(4 2 2 1)
Після цього працює процес, що залишився. В цій системі не виникає взаємоблокувань.
Вихід із взаємоблокування.
Після виявлення взаємоблокування успішно і знаходження тупіка необхідні методи для відновлення і отримання працюючої системи.
- Відновлення за допомогою примусового вивантаження ресурсу
- Відновлення через відкат
Якщо розробники системи і машинні оператори знають про те, що є ймовірність появи взаємоблокувань, вони можуть організувати роботу так, щоб процеси періодично створювали контрольні точки (це означає, що стан процесу записується в файл, в результаті чого в подальшому процес може бути відновлений з цього файлу). Для більшої ефективності нова контрольна точка повинна записуватись не поверх старої, а в новий файл, так що під час виконання процесу утворюється ціла послідовність контрольних точок.
Відновлення шляхом знищення процесів
Найпростіший спосіб виходу з ситуації взаємоблокування полягає в знищенні одного або декількох процесів. Можна знищити процес, що знаходиться у циклі взаємоблокування. Якщо перше видалення не допомагає, то процедуру можна повторювати, поки цикл знову не буде розірваним.
Також використовують підхід при якому вибирають процес, що не знаходиться в циклі, але такий чиї ресурси потрібні іншим процесам в циклі.
Існує підхід, за яким найкраще знищувати процеси, які можна легко знову запустити.
- Лекція 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.