Анотація: В лекції розглядаються питання взаімоблокіровок, тупикових ситуацій і "зависання" системи
У попередніх лекціях ми розглядали способи синхронізації процесів, які дозволяють процесам успішно кооперуватися. Однак в деяких випадках можуть виникнути непередбачені труднощі. Припустимо, що кілька процесів конкурують за володіння кінцевим числом ресурсів. Якщо запитуваний процесом ресурс недоступний, ОС переводить даний процес в стан очікування. У разі коли необхідний ресурс утримується іншим очікують процесом, перший процес не зможе змінити свій стан. Така ситуація називається тупиком (deadlock). Кажуть, що в мультипрограммной системі процес знаходиться в стані безвиході. якщо він очікує події, яке ніколи не станеться. Системна тупикова ситуація. або "зависання системи", є наслідком того, що один або більше процесів знаходяться в стані безвиході. Іноді подібні ситуації називають взаімоблокіровка. У загальному випадку проблема тупиків ефективного рішення не має.
Розглянемо приклад. Припустимо, що два процеси здійснюють висновок з стрічки на принтер. Один з них встиг монополізувати стрічку і претендує на принтер, а інший навпаки. Після цього обидва процеси виявляються заблокованими в очікуванні другого ресурсу (див. Рис. 7.1).
Мал. 7.1. Приклад тупикової ситуації
Визначення. Безліч процесів знаходиться в тупиковій ситуації. якщо кожен процес з безлічі очікує події, яке може викликати тільки інший процес даної множини. Так як всі процеси чогось очікують, то жоден з них не зможе ініціювати подія, яке розбудило б іншого члена безлічі і, отже, всі процеси будуть спати разом.
Вище наведено приклад взаимоблокировки. виникає при роботі з так званими виділеними пристроями. Тупики. однак, можуть мати місце і в інших ситуаціях. Hапример, в системах управління базами даних записи можуть бути локалізовані процесами, щоб уникнути стану гонок (див. Лекцію 5 "Алгоритми синхронізації"). В цьому випадку може вийти так, що один з процесів заблокував записи, необхідні іншому процесу, і навпаки. Таким чином, тупики можуть мати місце як на апаратних, так і на програмних ресурсах.
Тупики також можуть бути викликані помилками програмування. Наприклад, процес може марно чекати відкриття семафора, тому що в некоректно написаному додатку цю операцію забули передбачити. Іншою причиною нескінченного очікування може бути дискримінаційна політика по відношенню до деяких процесів. Однак найчастіше подія, якого чекає процес в тупиковій ситуації. - звільнення ресурсу. тому в подальшому будуть розглянуті методи боротьби з тупиками ресурсного типу.
Ресурсами можуть бути як пристрої, так і дані. Hекоторое ресурси допускають поділ між процесами, тобто є розділяються ресурсами. Наприклад, пам'ять. процесор. диски колективно використовуються процесами. Інші не допускають поділу, тобто є виділеними. наприклад стрічкопротяжного пристрій. До взаімоблокіровке може привести використання як виділених, так і поділюваних ресурсів. Наприклад, читання з розділяється диска може одночасно здійснюватися декількома процесами, тоді як запис передбачає винятковий доступ до даних на диску. Можна вважати, що частина диска, куди відбувається запис. виділена конкретного процесу. Тому в подальшому ми будемо виходити з припущення, що тупики пов'язані з виділеними ресурсами. тобто тупики виникають, коли процесу надається ексклюзивний доступ до пристроїв, файлів та інших ресурсів.
Традиційна послідовність подій при роботі з ресурсом складається із запиту, використання і звільнення ресурсу. Тип запиту залежить від природи ресурсу і від ОС. Запит може бути явним, наприклад спеціальний виклик request, або неявним - open для відкриття файлу. Зазвичай, якщо ресурс зайнятий і запит відхилено, запитувач процес переходить в стан очікування.
Далі в даній лекції будуть розглядатися питання виявлення, запобігання, обходу тупиків і відновлення після тупиків. Як правило, боротьба з тупиками - дуже дорогий захід. Проте для ряду систем, наприклад для систем реального часу, іншого виходу немає.
Умови виникнення тупиків
Умови виникнення тупиків були сформульовані Коффманом, Елфік і Шошанна в 1970 р
- Умова взаємовиключення (Mutual exclusion). Одночасно використовувати ресурс може тільки один процес.
- Умова очікування ресурсів (Hold and wait). Процеси утримують ресурси. вже виділені їм, і можуть запитувати інші ресурси.
- Умова неперераспределяемості (No preemtion). Ресурс. виділений раніше, не може бути примусово забрано у процесу. Звільнено вони можуть бути тільки процесом, який їх утримує.
- Умова кругового очікування (Circular wait). Існує кільцева ланцюг процесів, в якій кожен процес чекає доступу до ресурсу. утримуваного іншим процесом ланцюга.
Для освіти глухого кута необхідним і достатнім є виконання всіх чотирьох умов.
Зазвичай тупик моделюється циклом в графі, що складається з вузлів двох видів: прямокутників - процесів і еліпсів - ресурсів. зразок того, що зображений на рис. 7.1. Стрілки, спрямовані від ресурсу до процесу, показують, що ресурс виділено даному процесу. Стрілки, спрямовані від процесу до ресурсу. означають, що процес запитує даний ресурс.
Основні напрямки боротьби з тупиками
Проблема тупиків ініціювала багато цікавих досліджень в галузі інформатики. Очевидно, що умова циклічного очікування відрізняється від інших. Перші три умови формують правила, що існують в системі, тоді як четверта умова описує ситуацію, яка може скластися при певній несприятливою послідовності подій. Тому методи запобігання взаімоблокіровок орієнтовані головним чином на порушення перших трьох умов шляхом введення ряду обмежень на поведінку процесів і способи розподілу ресурсів. Методи виявлення та усунення менш консервативні і зводяться до пошуку і розриву циклу очікування ресурсів.
Отже, основні напрямки боротьби з тупиками:
- Ігнорування проблеми в цілому
- запобігання тупиків
- виявлення тупиків
- Відновлення після тупиків
Ігнорування проблеми тупиків
Найпростіший підхід - не помічати проблему тупиків. Для того щоб прийняти таке рішення, необхідно оцінити ймовірність виникнення взаимоблокировки і порівняти її з імовірністю збитку від інших відмов апаратного і програмного забезпечення. Проектувальники зазвичай не бажають жертвувати продуктивністю системи або зручністю користувачів для впровадження складних і дорогих засобів боротьби з тупиками.
Будь-яка ОС, що має в ядрі ряд масивів фіксованої розмірності, потенційно потерпає від тупиків. навіть якщо вони не виявлені. Таблиця відкритих файлів, таблиця процесів. фактично кожна таблиця є обмеженими ресурсами. Заповнення всіх записів таблиці процесів може привести до того, що черговий запит на створення процесу може бути відхилений. При несприятливому збігу обставин кілька процесів можуть видати такий запит одночасно і опинитися в глухому куті. Чи слід відмовлятися від виклику CreateProcess, щоб вирішити цю проблему?
Підхід більшості популярних ОС (Unix, Windows і ін.) Полягає в тому, щоб ігнорувати дану проблему в припущенні, що малоймовірний випадковий тупик краще, ніж безглузді правила, що змушують користувачів обмежувати число процесів, відкритих файлів і т. П. Стикаючись з небажаним вибором між строгістю і зручністю, важко знайти рішення, яке влаштовувало б усіх.