Тупики і близька до них проблема нескінченного відкладання - важливі фактори, які повинні враховувати розробники ОС.
Tупік (deadlock) - це така ситуація в мультипрограммной системі, коли процес очікує деякого події, яке ніколи не станеться. Системна тупикова ситуація, або "зависання" системи - це ситуація, коли один або більше процесів виявляються в стані безвиході.
Розглянемо простий приклад тупика при розподілі ресурсів.
В ОС тупики в більшості випадків виникають при конкуренції процесів за виділення ресурсів послідовного доступу, які в кожен момент часу відводяться тільки одному користувачеві.
На графі розподілу ресурсів показана тупикова ситуація, в якій кожен процес утримує ресурс, запитуваний іншим процесом, причому жоден з процесів не хоче звільнити належний йому ресурс.
Ресурс 1 виділений Процесс_Y запитує
процессу_Х Ресурс 1 ресурс 1
Процесс_Х запитує Ресурс 2 виділений
ресурс 2 Ресурс 2 процессу_ Y
Мал. 5 Граф розподілу ресурсів
Такий стан кругового очікування характерно для систем в тупиковому стані.
Системи спулінга (введення-виведення з буферизацією) часто виявляються схильні до тупикам (самостійно навести приклади таких ситуацій).
Близька до проблеми виникнення тупиків - проблема нескінченного відкладання, коли надання запитуваного ресурсу деякого процесу буде відкладатися на невизначений термін, в той час, як система буде приділяти увагу іншим процесам. Нагадаємо, що при розробці ОС необхідно передбачати справедливий, а також ефективне управління процесами, що знаходяться в стані очікування. У деяких системах нескінченне відкладання запобігає завдяки тому, що пріоритет процесу збільшується в міру того, як він очікує виділення потрібного йому ресурсу. Це називається старінням процеса.
Необхідні умови виникнення тупиків
Необхідні умови наявності тупика можуть бути сформульовані наступним чином 1 0.
Умова взаємовиключення - коли процеси вимагають надання їм права монопольного управління ресурсами, які їм виділяються.
Умова очікування ресурсів - коли процеси утримують за собою ресурси, вже виділені їм, чекаючи в той же час виділення додаткових ресурсів.
Умова неперераспределяемості - коли ресурси не можна відібрати у процесів, що утримують їх, поки ці ресурси не будуть використані для завершення роботи.
Умова кругового очікування - коли існує кільцева ланцюг процесів, в якій кожен процес утримує за собою один або більше ресурсів, потрібних наступного процесу.
Боротьба з виникненням тупиків може вестися за чотирма основними напрямком: запобігання тупиків; обхід тупиків; виявлення тупиків; відновлення після тупиків.
Стратегії запобігання тупиків
При запобіганні тупиків метою є забезпечення умов, що виключають можливість виникнення тупикових ситуацій. Часто такий підхід веде до нераціонального використання ресурсів, але, тим не менш, досить часто використовується розробниками ОС.
Хавендер 1 + 1 у своїй роботі показав, що виникнення тупика неможливо, якщо порушено хоча б одне із зазначених вище чотирьох необхідних умов, і запропонував наступну стратегію запобігання тупиків.
Кожен процес має запитувати всі необхідні йому ресурси відразу, причому не може почати виконання до тих пір, поки всі вони не будуть йому надані. Зауважимо, що такий стратегічний принцип веде в ряді випадків до зниження ефективності системи.
Якщо процес, що утримує певні ресурси, отримує відмову в задоволенні запиту на додаткові ресурси, цей процес повинен звільнити свої початкові ресурси і при необхідності запросити їх знову разом з додатковими ресурсами. Цей принцип запобігає виникненню умови неперераспределяемості. Одним із серйозних недоліків цієї стратегії є можливість нескінченного відкладання.
Введення лінійної впорядкованості за типами ресурсів для всіх процесів - іншими словами, якщо процесу виділені ресурси даного типу, в подальшому він може запросити тільки ресурси більш далеких один по одному типів. Цей принцип Хавендера виключає коловий очікування, однак, негативно позначається на можливості користувача вільно і легко писати прикладні програми, тобто призводить до порушення дружності ОС.