Якщо запитуваний процесом ресурс недоступний, процес переходить в стан очікування. У разі якщо необхідний ресурс утримується іншим очікують процесом, то перший процес не зможе змінити свій стан. Така ситуація називається тупиком. Кажуть, що в мультипрограммной системі процес знаходиться в стані безвиході, якщо він очікує події, яке ніколи не станеться. Системна тупикова ситуація або зависання системи є наслідком того, що один або більше процесів знаходяться в стані безвиході. У 1971 р Коффман, Елфік і Шошанна сформулювали наступні чотири умови для виникнення тупиків:
1. Умова взаємовиключення. Кожен ресурс виділено в точності одному процесу або доступний. Процеси вимагають надання їм монопольного управління ресурсами, які їм виділяються.
2. Умова очікування ресурсів. Процеси утримують за собою ресурси, вже виділені їм, чекаючи в той же час виділення додаткових ресурсів (які при цьому зазвичай утримуються іншими процесами).
3. Умова неперераспределяемості. Ресурс, даний раніше, не може бути примусово забрано у процесу. Звільнено вони можуть бути тільки процесом, який їх утримує.
4. Умова кругового очікування. Існує кільцева ланцюг процесів, в якій кожен процес утримує за собою один або більше ресурсів, потрібних іншим процесам ланцюга.
Для тупика необхідне виконання всіх чотирьох умов.
Основні напрямки боротьби з тупиками. Проблема тупиків ініціювала багато цікавих досліджень в галузі інформатики. Очевидно, що умова циклічного очікування відрізняється від інших. Перші три умови формують правила, що існують в системі, тоді як четверта умова описує ситуацію, яка може скластися при певній несприятливою послідовності подій. Тому методи запобігання взаімоблокіровок орієнтовані головним чином на порушення перших трьох умов шляхом введення ряду обмежень на поведінку процесів і способи розподілу ресурсів. Методи виявлення та усунення менш консервативні і зводяться до пошуку і розриву циклу очікування ресурсів.
Отже, основні напрямки боротьби з тупиками: 1) Запобігання тупиків. 2) Обхід тупиків. 3) Виявлення тупиків. 4) Відновлення після тупиків
I) Запобігання тупиків за рахунок порушення умов виникнення тупиків. Якщо в системі відсутні виділені ресурси, тупиків не буде. Проте, ясно, що усуспільнення, наприклад, принтера, тобто, дозвіл двом процесам писати на один принтер в один і той же час приведе до хаосу. За рахунок організації спулінга одночасний друк для декількох процесів стає можливою. У цій моделі єдиний процес, реально взаємодіє з принтером - демон принтера. Таким чином, тупик для принтера усунутий. На жаль, не для всіх пристроїв може бути організований спулінг (таблиця процесів погано піддається Спулінг). Неприємним побічним наслідком може бути потенційна тупикова ситуація через конкуренцію за дисковий простір для спула-буфера. Проте, в тій чи іншій формі ця ідея застосовується часто.
Hарушеніе умови очікування додаткових ресурсів. Хавендер в 1968 році запропонував наступну стратегію: 1) Кожен процес має запитувати всі необхідні йому ресурси відразу, причому не може почати виконуватися до тих пір, поки всі вони не будуть йому надані. 2) Якщо ж процес, утримує певні ресурси і отримує відмову у виділенні йому додаткових ресурсів, то він повинен звільнити свої початкові ресурси і, при необхідності, запросити їх знову разом з додатковими.
Таким чином, один із способів - змусити всі процеси зажадати всі свої ресурси перед виконанням (все або нічого). Якщо система в змозі виділити процесу все необхідне, він може працювати до завершення. Якщо хоча б один з ресурсів зайнятий, процес буде чекати. Подібний підхід не надто привабливий і призводить до зниження ефективності роботи комп'ютера. Рідко буває, що все запитувані пристрої необхідні програмі одночасно. Можна, звичайно, розділити програму на кілька кроків і виділяти ресурси окремо для кожного кроку програми, але основна проблема якраз в тому, що багато процесів не знають, скільки ресурсів їм знадобиться до початку обчислень. Якщо така інформація є, то можна скористатися алгоритмом банкіра. Тим не менш, деякі пакетні мейнфрейми вимагають від користувачів перерахувати всі необхідні його програмі ресурси.
Порушення принципу неперераспределяемості. Згідно з другим принципом Хавендера можна відбирати ресурси у утримують їх процесів до завершення цих процесів. Якби це було завжди можливо, то можна було б домогтися невиконання третього умови виникнення тупиків. Якщо процес протягом деякого часу використовує певні ресурси, а потім звільняє ці ресурси, він втрачає всю роботу, виконану до теперішнього моменту. Все питання в ціні цього рішення, яка може бути занадто високою, якщо подібна ситуація виникає часто. Іншим недоліком даної схеми може бути дискримінація окремих процесів, у яких постійно відбирають ресурси.
Порушення умови кругового очікування. Циклічного очікування можна уникнути декількома шляхами. Один з них - діяти відповідно до правила, згідно з яким кожен процес може мати тільки один ресурс в кожен момент часу. Якщо потрібен другий ресурс - звільни перший. Очевидно, що для багатьох процесів це не прийнятно, наприклад, для тих, які роздруковують великі файли з стрічки на принтер. Інший спосіб - привласнити всім ресурсам унікальні номери і зажадати, щоб процеси запитували ресурси в порядку зростання номерів. Тоді круговий очікування виникнути не може.
Невеликий варіацією цього алгоритму буде нумерація в зростаючому порядку не ресурсів, а запитів процесу. Після останнього запиту і звільнення всіх ресурсів можна дозволити процесу знову здійснить перший запит. Очевидно, що неможливо визначити порядок, який задовольнить всіх.
II) Обхід тупиків. При запобіганні тупиків метою є забезпечення умов, що виключають можливість виникнення тупикових ситуацій. Система, надаючи ресурс в розпорядження процесу, повинна прийняти рішення, безпечно це чи ні. Виникає питання: чи є такий алгоритм, який допомагає завжди уникати глухих кутів і робити правильний вибір. Відповідь - так, ми можемо уникати глухих кутів, але тільки, якщо певна інформація відома заздалегідь. У даній секції ми розглянемо шляхи запобігання тупиків за рахунок ретельного розподілу ресурсів. Один з алгоритмів запобігання тупиків базується на концепції безпечних станів.
Алгоритм банкіра. Можна уникнути тупикової ситуації, якщо раціональним чином використовувати ресурси, дотримуючись певних правил. Найбільш відомий серед алгоритмів такого роду - алгоритм банкіра, запропонований Дейкстрой. Він, як би імітує дії банкіра, який, маючи в своєму розпорядженні певним джерелом капіталу, приймає позики і видає платежі. Припустимо, що у системи в наявності n пристроїв, наприклад стрічок. Суть алгоритму полягає в наступному: 1) ОС приймає запит від призначеного для користувача процесу, якщо його максимальна потреба не перевищує n. 2) Користувач гарантує, що якщо ОС в змозі задовольнити його запит, то всі пристрої будуть повернуті системі протягом кінцевого часу. 3) Поточний стан системи називається надійним, якщо ОС може забезпечити всім процесам їх виконання протягом кінцевого часу. 4) Відповідно до алгоритму банкіра виділення пристроїв можливо, тільки якщо стан системи залишається надійним.
III) Виявлення тупиків. Виявлення тупика це встановлення факту, що виникла тупикова ситуація і визначення процесів і ресурсів, залучених в цю ситуацію. Як правило, алгоритми виявлення застосовуються, коли виконані перші три необхідні умови виникнення тупикової ситуації. Потім перевіряється наявність режиму кругового очікування. При цьому активно використовуються вже згадувані графи розподілу ресурсів. Якщо граф можна редукувати на всі процеси, то тупика немає. Інакше, все нередуціруемие процеси представляють собою процеси залучені в тупикову ситуацію.
IV) Відновлення після тупиків. Припустимо, що алгоритм виявлення впорався зі своїм завданням і виявив тупик. Що далі. Один із шляхів - відновитися і змусити систему працювати далі. У даній секції ми обговоримо різні способи відновлення після тупиків. Систему, яка опинилася в глухому куті, можна вивести з нього, порушивши одне з умов його існування. При цьому можливо кілька процесів частково або повністю втратять результати виконаної роботи.
Складність відновлення обумовлена низкою факторів: 1) в більшості систем немає достатньо ефективних засобів для припинення процесу, виведення його з системи і відновлення згодом; 2) якщо навіть такі кошти є, то їх використання вимагає витрат і уваги оператора; 3) відновлення після серйозного тупика може зажадати багато роботи.
Відновлення за допомогою перерозподілу ресурсів. Один із способів відновлення - примусове виведення деякого процесу з системи для подальшого використання його ресурсів. Для визначення того, який процес виводити із системи часто потрібні зусилля оператора. У деяких випадках може виявитися можливим тимчасово забрати ресурс у його поточного власника і передати його іншому процесу. Наприклад, щоб відібрати лазерний принтер у процесу, який здійснює висновок на нього, оператор може зібрати вже надруковані паперу і скласти їх в стопку. Потім процес може бути припинений і принтер переданий іншому процесу. Після закінчення його роботи папір може бути повернута в принтер і перший процес поновлюється. Можливість забрати ресурс у процесу, дати його іншому процесу і потім повернути його назад без нанесення шкоди сильно залежить від природи ресурсу. Подібне відновлення часто важко, якщо не неможливо.
Поновлення за рішенням відкат назад. Це, по всій ймовірності, найефективніший спосіб припинення та поновлення. У ряді систем реалізовані засоби рестарту з контрольною точки (збереження стану системи в якийсь момент часу). Там де ці кошти не передбачені, їх повинні організувати розробники прикладних програм. Якщо проектувальники системи знають, що глухий кут імовірний, вони можуть періодично організовувати для процесів контрольні точки. Коли тупик виявлений, видно якісь ресурси залучені в цикл кругового очікування. Щоб здійснити відновлення, процес, який володіє таким ресурсам, повинен бути відкинутий до моменту часу, що передує його запитом на цей ресурс.
Поновлення за рішенням ліквідацію одного з процесів. Грубий, але найпростіший спосіб усунути глухий кут - вбити один або більше процесів. Наприклад, вбити процес, який в циклі. Тоді при удачі інші процеси зможуть виконуватися. Якщо це не допомагає, то можна ліквідувати ще один процес.
По можливості краще вбити той процес, який може бути без шкоди повернутий до початку (такі процеси називаються Ідемпотентний), наприклад, компіляція. З іншого боку процес, який змінює вміст бази даних, не завжди може бути коректно запущений повторно.