Згідно з визначенням з / 7 /, тупик - це стан, в якому «деякі процеси заблоковані в результаті таких запитів на ресурси, які ніколи не можуть бути задоволені, якщо не будуть вжиті надзвичайні системні заходи».
Як це накажете розуміти?
Перш за все, давайте відзначимо, що процесу, чинному в поодинці, не під силу загнати пристойну ОС в тупик. Вимоги процесу не будуть задоволені, тільки якщо вони перевищують те, що є у системи. Скажімо, процес вимагає 500 Мб оперативної пам'яті, коли у системи є всього-256 Мб. Ну, так у цьому випадку процес буде не блокований, а нещадно убитий системою.
Інша річ, якщо в справі замішані два або більше процесів. Згідно з іншим визначенням, даним у / 2 /, «Група процесів перебуває в тупиковій ситуації, якщо кожен процес з групи очікує події, яка може викликати тільки інший процес з тієї ж групи».
Розглянемо такий приклад. Нехай кожен з процесів A і B збирається працювати з двома файлами, F1 і F2, причому не має наміру розділяти ці файли з іншим процесом. Програми ж процесів злегка розрізняються, а саме:
| Процесс A: | Процесс B: |
| . . . Открыть(F1); Открыть(F2); (работа процесса A с файлами); Закрыть(F1); Закрыть(F2); . . . | . . . Открыть(F2); Открыть(F1); (работа процесса B с файлами); Закрыть(F1); Закрыть(F2); . . . |
У цій ситуації все може пройти благополучно. Нехай, наприклад, процес A встигне відкрити обидва файли до того моменту, коли процес B спробує відкрити F2. Ця спроба не увінчається успіхом: процес B або буде заблокований до звільнення файлів, або отримає повідомлення про помилку при відкритті файлу і, якщо процес розумний, через якийсь час спробує ще раз. Зрештою обидва процеси отримають необхідні ресурси (в даному випадку відкриті файли), хоча і не обидва відразу.
Зовсім інше буде справа, якщо A встигне відкрити тільки F1, після чого B відкриє F2. Тут-то і вийде тупик. Процес A хоче відкрити файл F2, але не зможе цього зробити раніше, ніж B закриє цей файл. Але B не закриє F2 до того, як зуміє відкрити файл F1, який зайнятий процесом A. Кожен з процесів
захопив один з ресурсів і не збирається його віддавати раніше, ніж отримає інший. Ситуація «двох баранів на мосту».
Підкреслимо: безвихідь - це не просто блокування процесу, коли необхідний йому ресурс зайнятий. Зайнятий - ну і що, з часом, авось, звільниться. Тупик - це взаємне блокування, з якої немає виходу.
Ще приклад. Нехай в системі є 100 Мб пам'яті, доступної для процесів. Процес A при своєму старті займає 40 Мб, але пізніше на короткий час вимагає ще 30 Мб, після чого завершується, звільняючи всю пам'ять. Процес B поводиться точно таким же чином.
Кожен з процесів окремо не вимагає у системи нічого неможливого. У той же час зрозуміло: якщо обидва процеси зуміють стартувати і почати паралельну роботу, то жоден з них ніколи не одержить додаткові 30 Мб. Тупик.
Зовсім грубий приклад. Процес A на якомусь етапі роботи чекає повідомлення від процесу B, після чого збирається послати у відповідь повідомлення. У той же час процес B чекає повідомлення від A, щоб потім відповісти на нього. Тупик неминучий. В даному випадку, на відміну від попередніх, виникнення тупика пов'язано з явною помилкою в логіці програми.
Чи може допомогти в боротьбі з тупиками використання семафорів та інших подібних засобів? Навряд чи, хіба що в рідкісних випадках. Семафор - це, скоріше, додаткове гальмо для процесу. Річ корисна, але не сприяюча просуванню.
Всі відомі способи боротьби з тупиками можна розділити на три групи:
· Виключення можливості тупиків шляхом аналізу вихідного тексту програм;
· Запобігання виникнення тупиків при роботі ОС;
· Ліквідація виникли тупиків.
Що стосується аналізу тексту - це, безумовно, потрібна річ, хоча й непроста. Визначити по тексту програм процесів, чи можуть вони зайти в глухий кут - складне завдання. До того ж, якщо і можуть, то зовсім не обов'язково зайдуть, все може залежати від конкретних вихідних даних і від тимчасових співвідношень. Але головне - для аналізу вихідного тексту програм потрібно мати у своєму розпорядженні цей текст. Чи реально це? Тільки в деяких ситуаціях. Наприклад, при розробці вбудованої системи вихідні тексти всіх прикладних програм звичайно доступні розробникові ОС. Звичайно, в цьому випадку аналіз на можливість тупиків просто необхідний. Інший приклад - розробка складного многопроцессного додатки, коли розробник повинен хоча б виявити можливість взаємного блокування між «своїми» процесами.
Якщо тексти недоступні, то можна спробувати запобігати тупики вже в ході роботи програм, відстежуючи їх запити на ресурси і блокуючи або припиняючи ті процеси, які, очевидно, «лізуть в тупик».
Самий грубий з подібних підходів полягає в тому, що кожен процес повинен захоплювати всі необхідні йому ресурси відразу, при старті, після чого він може або утримувати ресурси протягом усього часу роботи, або звільняти ресурси, які більше не потрібні. Такий підхід, безумовно, в корені виключає можливість тупиків. На жаль, на практиці він майже виключає і многозадачную
роботу: багато ресурси необхідні для роботи більшості процесів (наприклад, диски, принтер, системні файли), тому поки один процес утримує всі ресурси, інші не зможуть навіть стартувати.
Трохи краще алгоритм нумерованих ресурсів. Він полягає в тому, що всі ресурси, наявні в системі, нумеруються цілими числами в довільному порядку (хоча, ймовірно, для підвищення ефективності найкраще пронумерувати їх у порядку зростання дефіцитності ресурсу). Далі застосовується просте правило: запит процесу на виділення йому ресурсу з номером K задовольняється тільки в тому випадку, якщо процес в даний момент не володіє ніяким іншим ресурсом з номером N ³ K. Іншими словами, запит ресурсів слід виконувати тільки в порядку зростання номерів. Неважко показати, що це правило є достатньою умовою відсутності тупиків. Але ця умова занадто обмежує, воно відсікає багато ситуацій, коли безвихідь насправді не виник би.
Найбільш витончений алгоритм банкіра, запропонований тим же Дейкстри. У ньому передбачається, що кожен процес при старті повинен оголосити системі, на які ресурси і в якій максимальній кількості він може в майбутньому претендувати. Далі, вводиться поняття безпечного (щодо тупиків) стану системи. Поточний стан, в якому є набір процесів, кожний з яких володіє деякими ресурсами, вважається безпечним, якщо наявних вільних ресурсів достатньо для того, щоб ОС змогла в певній послідовності задовольнити максимальні запити кожного процесу.
Це визначення простіше зрозуміти, якщо розглянути, як перевіряється безпечність заданого стану. Відповідно до алгоритму, серед наявних процесів шукається такий, чиї максимальні заявлені запити система може задовольнити, використовуючи наявні вільні ресурси. Якщо хоча б один такий процес знайдений, то він викреслюється із загального списку і всі ресурси, які він уже встиг зайняти, вважаються вільними (тобто вважається, що система змогла завершити цей процес). Далі, при збільшилися вільних ресурсах, шукається наступний процес, чиї запити система може задовольнити, і т.д. Якщо в результаті вдається викреслити всі процеси, то аналізоване стан системи є безпечним.
Сам же алгоритм банкіра можна тепер сформулювати дуже просто: будь-який запит процесу на виділення йому додаткових ресурсів повинен задовольнятися тільки в тому випадку, якщо стан, в який перейде система після цього виділення, буде безпечним.
Назва алгоритму навіяно, мабуть, чином обережного банкіра, який видає кредит тільки в тому випадку, якщо після цього зможе виконати всі свої зобов'язання навіть у найгіршому випадку. Явно не російський банкір.
Хоча даний алгоритм красивий і логічний, у нього є, щонайменше, два недоліки. По-перше, в сучасних ОС не прийнято вимагати від процесів, щоб ті заздалегідь оголошували свої майбутні потреби в ресурсах. По-друге, виконувати перевірку безпеки стану при кожному запиті будь-якого з процесів - занадто трудомістке задоволення.
Розглянемо, нарешті, третій підхід - ліквідацію вже виниклих тупиків, без спроб запобігти їх виникненню. У книзі / 2 / цей підхід названий «алгоритмом страуса».
Тут, перш за все, виникає питання: як переконатися, що система дійсно в тупику? Зовнішньою ознакою цього є тривала відсутність будь-якої активності двох або більше процесів. Але це недостовірний ознака, процеси могли просто надовго замислитися над яким-небудь трудомістким обчисленням. Є алгоритми, які аналізують поточний стан процесів і ресурсів, наявність заблокованих запитів, і на цій основі ставлять діагноз тупика. В принципі, такий алгоритм міг би
бути вбудований в ОС. Однак у літературі немає відомостей про те, щоб це було здійснено на практиці. Звичайно покладаються на вольове рішення оператора або адміністратора системи.
Але нехай навіть точно відомо, що тупик є. Як можна його усунути? Як «розтягнути баранів з моста»? Як правило, для цього застосовується радикальне рішення: примусово припинити один із тупикових процесів (скинути одного барана в річку). Якщо не допомогло - втопити наступного барана. І т.д.
У літературі розглядаються і більш гуманні, але складні способи. В принципі, можна регулярно запам'ятовувати стан всіх або тільки найбільш відповідальних процесів в певних контрольних точках або через певні періоди часу. Тоді, замість повного припинення процесу, його можна повернути до однієї з останніх контрольних точок і притримати там, поки інший баран не перейде через річку.
Завершуючи розгляд проблеми тупиків, слід визнати, що в даний час її практичне значення значно менше, ніж хотілося б теоретикам. По-перше, зовсім не легко загнати в глухий кут сучасну ОС, яка працює на комп'ютері з величезними ресурсами. У прикладі ми розглянули тупик, що виник через 100 Мб пам'яті, але якщо врахувати ще кілька гігабайт, які можна використовувати у файлі підкачки, то запити процесів повинні бути вже дуже великі, щоб привести до глухого кута. А, скажімо, такий пристрій, як принтер, в сучасних ОС взагалі не може стати причиною глухого кута, тому система не віддає його у володіння ні одному процесу навіть на час.
По-друге, хоча тупик в принципі залишається можливим, користувач навряд чи навіть помітить його. Швидше, він скаже «Знову Windows зависла!» І перезавантажить систему.
Запобігання тупиків залишається дійсно важливим, наприклад, при розробці вбудованої системи, яка повинна тривалий час безвідмовно працювати без втручання людини.