Тема 10. Тупик.

Вступ

Припустимо, що декілька процесів конкурують за володіння деяким скінченним числом ресурсів. Якщо запрошуваний процесом ресурс недоступний, процес переходить в стан чекання. У випадку якщо необхідний ресурс утримується іншим процесом, що чекає, то перший процес не зможе змінити свій стан. Така ситуація називається тупиком. Говорять, що в мультипрограмній системі процес знаходиться в стані тупика, дедлока (deadlock) або клінчу, якщо він чекає події, яка ніколи не відбудеться. Системна тупикова ситуація або зависання системи є наслідком того, що один або більше процесів знаходяться в стані тупика. Розглянемо приклад. Припустимо, що два процеси здійснюють вивід (output) із файлу на принтер. Один з них встигнув монополізувати файл і претендує на принтер, а інший навпаки. Після цього обидва процеси виявляються заблокованими в очікуванні другого ресурсу.
Тупик також може мати місце в ситуаціях, що не вимагають виділених ресурсів. Наприклад, в системах управління базами даних процеси можуть локалізувати записи, щоб уникнути гонок. В цьому випадку може вийти так, що один з процесів заблокував записи, потрібні іншому процесу і навпаки. Тупик може мати місце, як на апаратних, так і на програмних ресурсах.

Концепція ресурсу

Одна з основних функцій ОС здійснювати розподіл ресурсів між процесами, тобто бути менеджером ресурсів. Як пристрої, так і дані можуть бути ресурсами. Деякі види ресурсів допускають розподіл між процесами, тобто є пристроями, що розділяються. Наприклад, пам'ять, процесор, диски колективно використовуються процесами. Інші – ні, тобто є виділеними, наприклад, стример. Найчастіше тупик пов'язано з виділеними ресурсами, тобто тупик виникає, коли процесу дається ексклюзивний (винятковий) доступ до пристроїв, файлів і інших ресурсів. Послідовність подій, потрібних для використання ресурсу така: 1. опитати (request) ресурс 2. використати (use) ресурс 3. звільнити (release) ресурс. Якщо ресурсу немає в наявності, коли він потрібний, то процес змушений чекати. У деяких ОС процес автоматично блокується (переводиться в стан призупинений), коли дістає відмову на запит до ресурсу і прокидається (переводиться в стан готовність), коли ресурс виявляється в наявності. У інших системах відмова супроводжується поверненням помилки і вже завдання процесу вирішити: чекати чи спробувати здійснити запит знову. Ми вважаємо, що коли запит відхилено, процес переходить в стан чекання. Природа запиту сильно залежить від ОС. У деяких системах є системний виклик request для прямого запиту на ресурс. В інших – єдині ресурси, про які ОС знає – спеціальні файли, які тільки один процес має право відкривати за раз. Це робиться звичайним викликом open. Якщо файл вже використовується, то процес блокується, поки ресурс не звільниться.

Умови виникнення тупика

У 1971 р. Коффман, Элфік і Шошані сформулювали наступні чотири умови для виникнення тупика. 1. Умова взаємовиключення (Mutual exclusion). Кожен ресурс виділено (або доступно) в точності одному процесу. Процеси вимагають надання їм монопольного управління ресурсами, які їм виділяються. 2. Умова чекання ресурсів (Hold and wait). Процеси утримують за собою ресурси, вже виділені їм, чекаючи в той же час виділення додаткових ресурсів (які при цьому зазвичай утримуються іншими процесами). 3. Умова нерозподіленості (No preemtion). Ресурс, наданий раніше, не може бути примусово забраний у процесу. Звільнені ресурси можуть бути тільки процесом, який їх утримує. 4. Умова кругового очікування (чекання (Circular wait). Існує кільцевий ланцюг процесів, в якому кожен процес утримує за собою один або більш за ресурси, потрібні іншим процесам ланцюга. Для тупика необхідне виконання всіх чотирьох умов. Зазвичай тупик моделюється прямим графом, на зразок того, що зображений на мал. 1, що складається з вузлів двох видів: прямокутників процесів і еліпсів ресурсів. Стрілки, направлені від ресурсу до процесу, показують, що ресурс виділений даному процесу.

Основні напрями боротьби з тупиком

У зв'язку з проблемою тупика були виконано багато цікавих досліджень в області інформатики і операційних систем. Основні напрями боротьби з тупиком: 1. Ігнорувати дану проблему 2. Виявлення тупика 3. Відновлення після тупика 4. Запобігання тупика за рахунок ретельного виділення ресурсів або порушення одного з умов виникнення тупика.

Алгоритм страуса

Найпростіший підхід – ігнорувати проблему тупика. Різні люди реагують на подібну стратегію по-різному. Математики знаходять її неприйнятною і стверджують, що тупиків треба запобігати за всяку ціну. Інженери ставлять питання: як часто виникає дана проблема і як часто система висне з інших причин? Якщо тупик зустрічається раз в п'ять років, але аварійний останов системи із-за відмов обладнання, помилок компіляторів або ОС відбувається раз на місяць, більшість інженерів не будуть пожертвувати продуктивністю або зручністю, щоб ліквідовувати тупик. Наприклад, ОС Linux, що має в ядрі низку масивів фіксованої розмірності, потенційно страждає від тупика, навіть якщо вони не виявлені. Наприклад, сумарне число процесів в системі визначається розмірністю таблиці процесів. Якщо таблиця заповнена, хоча ймовірність цього дуже мала, але така ситуація можлива, то для програми, яка робить виклик fork, резонно почекати якийсь час і спробувати здійснити цей виклик знов. Максимальне число відкритих файлів аналогічним чином обмежене розміром таблиці індексних вузлів. Фактично будь-яка таблиця в ОС – скінченний ресурс. Підхід Linux полягає в тому, щоб ігнорувати дану проблему в припущенні, що більшість користувачів віддадуть перевагу випадковому тупику над безглуздими правилами, що примушують їх мати один процес, один відкритий файл і т.п. ... Таким чином, ми стикаємося з небажаним вибором між суворістю і зручністю. Важко знайти рішення яке влаштовує всіх.

Виявлення тупика

Виявлення тупика – це встановлення факту, що виникла тупикова ситуація і визначення процесів і ресурсів, залучених в цю ситуацію. Як правило, алгоритми виявлення застосовуються, коли виконані перші три необхідні умови виникнення тупикової ситуації. Потім перевіряється наявність режиму кругового очікування. При цьому активно використовуються графи розподілу ресурсів, мал. 1. Розглянемо модельну ситуацію: • Процес A утримує ресурс R і чекає ресурс S. • Процес B претендує на ресурс T. • Процес C претендує на ресурс S. • Процес D утримує ресурс U і чекає ресурси S і T. • Процес E утримує ресурс T і чекає ресурс V. • Процес F утримує ресурс W і чекає ресурс S. • Процес G утримує ресурс V і чекає ресурс U. Питання полягає в тому, чи є дана ситуація тупиковою, і якщо так, то які процеси в ній беруть участь.
Для відповіді на це питання можна сконструювати граф ресурсів, як показано на мал. 7.2. З малюнка видно, що є цикл, що моделює умову кругового очікування, і процеси D,E,G в тупиковій ситуації Візуально легко виявити наявність тупика, але потрібні також формальні алгоритми, що реалізовуються на комп'ютері.

Відновлення після тупика

Припустимо, що алгоритм виявлення справився з своїм завданням і виявив тупик. Один з шляхів – відновитися і примусити систему працювати далі. Систему, що попала в тупик, можна вивести з нього, порушивши одну з умов його існування. При цьому можливі декілька процесів частково або повністю втратять результати виконаної роботи. Складність відновлення обумовлена рядом факторів • у більшості систем немає достатньо ефективних засобів для припинення процесу, виведення його з системи і відновлення (поновлення) згодом; • якщо навіть такі засоби є, то їх використання вимагає уваги оператора; • відновлення після серйозної тупика може вимагати багато роботи.

Відновлення за допомогою перерозподілу ресурсів

Один із способів відновлення – примусове виведення деякого процесу з системи для подальшого використання його ресурсів. В деяких випадках може виявитися можливим тимчасово забрати ресурс у його поточного власника і передати його іншому процесу.

Відновлення через відкат назад

Це, ймовірно, найефективніший спосіб припинення і відновлення. У ряді систем реалізовані засоби рестарту з контрольної точки (збереження стану системи в якийсь момент часу). Там де ці засоби не передбачені, їх повинні організувати розробники прикладних програм. Якщо проектувальники системи знають, що тупик вірогідний, вони можуть періодично організовувати для процесів контрольні точки. Коли тупик виявлено, видно які ресурси залучені в цикл кругового чекання. Щоб здійснити відновлення, процес, який володіє таким ресурсам, повинен бути відкинутий на момент часу до запиту на цей ресурс.

Відновлення через ліквідацію одного з процесів

Грубий, але простий спосіб усунути тупик – убити один або більш процесів. Наприклад, убити процес, який в циклі. Тоді за умови успіху решта процесів зможе виконуватися. Якщо це не допомагає, то можна ліквідовувати ще один процес. По можливості краще убити той процес, який може бути без проблем повернено до початку (такі процеси називаються ідемпотентними), наприклад, компіляція. З іншого боку процес, який змінює вміст бази даних, не завжди може бути коректно запущений повторно.

Способи запобігання тупика шляхом ретельного розподілу ресурсів.

При запобіганні тупика основною метою є забезпечення умов, що виключають можливість виникнення тупикових ситуацій. Система, надаючи ресурс в розпорядження процесу, повинна ухвалити рішення, безпечно це чи ні. Виникає питання: чи є такий алгоритм, який допомагає завжди уникати тупика і робити правильний вибір. Один з алгоритмів запобігання тупика базується на концепції безпечних станів.

Запобігання тупика і алгоритм банкіра.

Можна уникнути тупикової ситуації, якщо раціональним чином використовувати ресурси, дотримуючись певних правил. Найбільш відомий серед алгоритмів такого роду – алгоритм банкіра, запропонований Дейкстрой. Він, як би імітує дії банкіра, який, маючи в своєму розпорядженні певне джерело капіталу, приймає позики і видає платежі. Припустимо, що у системи в наявності n пристроїв. Суть алгоритму полягає в наступному. • ОС приймає запит від призначеного для користувача процесу, якщо його максимальна потреба не перевищує n. • Користувач гарантує, що якщо ОС в змозі задовольнити його запит, то всі пристрої будуть повернені системі протягом скінченого часу. • Поточний стан системи називається надійним, якщо ОС може забезпечити всім процесам їх виконання протягом скінченого часу. • Відповідно до алгоритму банкіра виділення пристроїв можливе, тільки якщо стан системи залишається надійним. Розглянемо приклад надійного стану для системи з трьома користувачами і 12-ма пристроями, де 10 пристроїв задіяно, а 2 є в наявності. Нехай поточна ситуація така: Даний стан надійний. Наступні дії системи можуть бути такі. Спочатку задовольнити запити другого користувача, потім дочекатися, коли він виконає свою роботу і звільнить свої 6 пристроїв. Потім можна обслужити решту користувачів. Тобто, система задовольняє тільки ті запити, які залишають її в надійному стані і відхиляє інші. Термін ненадійний стан не припускає, що обов'язково виникне тупик. Він лише говорить про те, що у разі несприятливої послідовності подій система може зайти в тупик.

Недоліки алгоритму банкіра

В алгоритмі банкіра наявні серйозні недоліки, із-за яких розробник може вибрати інший підхід для вирішення проблеми тупика: • Алгоритм банкіра виходить з фіксованої кількості ресурсів. • Він вимагає, щоб число працюючих користувачів залишалося постійним • Даний алгоритм вимагає, щоб розподільник гарантовано задовольняв запити за кінцевий період часу. Очевидно, що для реальних систем потрібні конкретніші гарантії. • Алгоритм вимагає, щоб клієнти гарантовано повертали ресурси. Знову таки в реальних системах потрібні, набагато конкретніші гарантії. • Потрібно, щоб користувачі наперед (заздалегідь) вказали свої максимальні потреби в ресурсах. При динамічному розподілі ресурсів важко оцінити максимальні потреби користувачів. Розглянемо інші способи запобігання тупика.

Запобігання тупика за рахунок порушення умов виникнення тупика

Як же може реальна система уникнути тупика, якщо відсутня інформація про майбутні запити? Для відповіді на це питання повернемося до чотирьох умов розділу 7.3. Якщо ми зможемо організувати роботу системи так, що, принаймні, одна з цих умов не задоволена, тупик не можливий.

Порушення умови взаємовиключення

Якщо в системі відсутні виділені ресурси, тупика не буде. Проте, ясно, що, наприклад, дозвіл двом процесам писати на один принтер в один і той же час приведе до хаосу. За рахунок організації спулінгу одночасний друк для декількох процесів стає можливим. У цій моделі єдиний процес, що реально взаємодіє з принтером, – демон принтера. Таким чином, тупик для принтера усунено. На жаль, не для всіх пристроїв може бути організований спулінг (таблиця процесів погано піддається спулінгу). Неприємним побічним наслідоком може бути потенційна тупикова ситуація із-за конкуренції за дисковий простір для спул-буфера. Проте, в тій або іншій формі ця ідея застосовується часто.

Порушення умови чекання додаткових ресурсів

Хавендер в 1968 р. запропонував наступну стратегію. • Кожен процес повинен опитувати всі потрібні йому ресурси відразу, причому не може виконуватися до тих пір, поки всі вони не будуть йому надані. • Якщо ж процес, утримує певні ресурси і дістає відмову у виділенні йому додаткових ресурсів, то він повинен звільнити свої первинні ресурси і, при необхідності, опитати їх знову разом з додатковими. Таким чином, один із способів – примусити всі процеси перевіряти всі свої ресурси перед виконанням (все або нічого). Якщо система в змозі виділити процесу все необхідне, він може працювати до завершення. Якщо хоч би один з ресурсів зайнятий, процес чекатиме. Подібний підхід не дуже привабливий і призводить до зниження ефективності роботи комп'ютера. Рідко буває, що всі опитані пристрої знадобляться програмі одночасно. Можна, звичайно, розділити програму на декілька кроків і виділяти ресурси окремо для кожного кроку програми, але основна проблема якраз в тому, що багато процесів не знають, скільки ресурсів їм знадобиться до початку роботи. Якщо така інформація є, то можна скористатися алгоритмом банкіра. Проте, деякі пакетні мейнфрейми вимагають від користувачів перерахувати всі необхідні його програмі ресурси.

Порушення принципу нерозподільності.

Відповідно до другого принципу Хавендера можна відбирати ресурси утримуючих їх процесів до завершення цих процесів. Якби це було завжди можливо, то можна було б добитися невиконання третьої умови виникнення тупика. З проблемою відняття ресурсів в утримуючих їх процесів ми стикалися в 7.7.1. Якщо процес протягом деякого часу використовує певні ресурси, а потім звільняє ці ресурси, він втрачає всю роботу, виконану до теперішнього моменту. Все питання в ціні даного рішення, яка може бути занадто високою, якщо подібна ситуація виникає часто. Іншим недоліком даної схеми може бути дискримінація окремих процесів, у яких постійно відбирають ресурси.