Основні напрямки боротьби з тупиками
У зв'язку з проблемою тупиків були виконано багато цікавих досліджень в галузі інформатики та операційних систем.
Основні напрямки боротьби з тупиками:
1) Ігнорувати цю проблему
2) Виявлення тупиків
3) Відновлення після тупиків
4) Запобігання тупиків за рахунок ретельного виділення ресурсів або порушення одного з умов виникнення тупиків.
Найпростіший підхід - ігнорувати проблему тупиків. Підхід Unix полягає в тому, щоб ігнорувати дану проблему в припущенні, що більшість користувачів віддадуть перевагу випадковий тупик безглуздим правилами змушують їх мати один процес, один відкритий файл і т.п. Тут стикаємося з небажаним вибором між строгістю і зручністю.
Виявлення тупика - це встановлення факту, що виникла тупикова ситуація і визначення процесів і ресурсів, залучених в цю ситуацію. Як правило, алгоритми виявлення застосовуються, коли виконані перші три необхідні умови виникнення тупикової ситуації. Потім перевіряється наявність режиму кругового очікування. При цьому активно використовуються вже згадувані графи розподілу ресурсів.
Розглянемо модельну ситуацію:
· Процес A утримує ресурс R і очікує ресурс S.
· Процес B претендує на ресурс T.
· Процес C претендує на ресурс S.
· Процес D утримує ресурс U і очікує ресурси S і T.
· Процес E утримує ресурс T і очікує ресурс V.
· Процес F утримує ресурс W і очікує ресурс S.
· Процес G утримує ресурс V і очікує ресурс U.
Щоб визначити чи є дана ситуація тупиковою, і якщо так, то які процеси в ній беруть участь, можна сконструювати граф ресурсів (рис.8.2). З рис.8.2 видно, що є цикл, що моделює умова кругового очікування, і процеси D, E, G в тупиковій ситуації
Малюнок 8.2 (а) Граф ресурсів. (Б) Цикл, витягнутий з графа (a).
Візуально легко виявити наявність тупика, але потрібні також формальні алгоритми, реалізовані на комп'ютері. Одним з таких алгоритмів є редукція графа. Якщо запити ресурсів для деякого процесу можуть бути задоволені, тобто тупикової ситуації немає, то граф можна редукувати на цей процес. Редукція графа на процес зображується винятком стрілок, що йдуть до цього процесу від ресурсів і стрілок до ресурсів від цього процесу.