27. Тупіки. Визначення та умови виникнення тупіків.

Тупики також можуть бути викликані помилками програмування. Наприклад, процес може дарма чекати

відкриття семафора, тому що в некоректно написаному додатку цю операцію забули передбачити. Іншою причиною

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

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

Умови виникнення тупиків були сформульовані Коффманом, Элфиком і Шошани в 1970 р.

1. Умова взаємовиключення (Mutual exclusion). Одночасно використати ресурс може тільки один

процес.

2. Умова очікування ресурсів (Hold and wait). Процеси втримують ресурси, уже виділені їм, і

можуть запитувати інші ресурси.

3. Умова неперерозділеності (No preemtion). Ресурс, виділений раніше, не може бути примусово

забраний у процесу. Звільнено вони можуть бути тільки процесом, що їх утримує.

4. Умова кругового очікування (Circular wait). Існує кільцевий ланцюг процесів, у якій кожен

процес чекає доступу до ресурсу, утримуваному іншим процесом ланцюга.

28. Основні напрямки боротьби з тупиками та ігнорування проблеми тупиків

Проблема тупиків ініціювала багато цікавих досліджень в області інформатики. Очевидно, що умова циклічного

очікування відрізняється від інших. Перші три умови формують правила, що існують у системі, тоді як четверта умова

описує ситуацію, що може зложитися при певній несприятливій послідовності подій. Тому методи запобігання

взаємоблокувань орієнтовані головним чином на порушення перших трьох умов шляхом введення ряду обмежень на

поводження процесів і способи розподілу ресурсів. Методи виявлення й усунення менш консервативні й зводяться до

пошуку й розриву циклу очікування ресурсів.

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

· Ігнорування проблеми в цілому

· Запобігання тупиків

· Виявлення тупиків

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

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

Ціль запобігання тупиків - забезпечити умови, що виключають можливість виникнення тупикових ситуацій.

Більшість методів пов'язане із запобіганням однієї з умов виникнення взаємоблокування.

Система, надаючи ресурс у розпорядження процесу, повинна прийняти рішення, безпечно це чи ні. Виникає

питання: є чи такий алгоритм, що допомагає завжди уникати тупиків і робити правильний вибір. Відповідь - так, ми

можемо уникати тупиків, але тільки якщо певна інформація відома заздалегідь.

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

Можна уникнути взаємоблокування, якщо розподіляти ресурси, дотримуючись певних правил. Серед такого

роду алгоритмів найбільш відомий алгоритм банкіра, запропонований Дейкстрою, що базується на так званих безпечних або надійних станах (safe state). Безпечний стан - це такий стан, для якого є принаймні одна послідовність подій, що неприведе до взаємоблокуванню. Модель алгоритму заснована на діях банкіра, що, маючи в наявності капітал, видає кредити