Способи запобігання тупиків

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

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

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

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

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

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

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

Розглянемо приклад надійного стану для системи з 3 користувачами і 11 пристроями, де 9 пристроїв задіяно, а 2 є в резерві. Нехай поточна ситуація така:

Пользователи	Максимальная потребность в ресурсах	Выделено ресурсов
Первый
Второй
Третий

Рис. 9.3. Приклад надійного стану для системи з 3 користувачами і 11 пристроями

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

Термін ненадійне стан не припускає, що обов'язково виникнуть тупики. Він лише говорить про те, що у разі несприятливої послідовності подій система може зайти в глухий кут.

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

1. Число користувачів і число ресурсів фіксовано.

2. Число працюючих користувачів має залишатися постійним.

3. Алгоритм вимагає, щоб клієнти гарантовано повертали ресурси.

4. Повинні бути заздалегідь вказані максимальні вимоги процесів до ресурсів. Найчастіше дана інформація відсутня.

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

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

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

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

Порушення умови очікування додаткових ресурсів. Умови очікування ресурсів можна уникнути, зажадавши виконання стратегії двофазного захоплення.

У першій фазі процес повинен запитувати всі необхідні йому ресурси відразу. До тих пір поки вони не надані, процес не може продовжувати виконання.

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

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

Таким чином, один із способів - змусити всі процеси зажадати потрібні їм ресурси перед виконанням ("все або нічого"). Якщо система в змозі виділити процесу все необхідне, він може працювати до завершення. Якщо хоча б один з ресурсів зайнятий, процес буде чекати.

Дане рішення застосовується в пакетних мейнфреймах (mainframe), які вимагають від користувачів перерахувати всі необхідні його програмі ресурси. Іншим прикладом може служити механізм двофазної локалізації записів в СУБД. Проте в цілому подібний підхід не надто привабливий і призводить до неефективного використання комп'ютера. Як вже зазначалося, перелік майбутніх запитів до ресурсів рідко вдається спрогнозувати. Якщо така інформація є, то можна скористатися алгоритмом банкіра. Зауважимо також, що описуваний підхід суперечить парадигмі модульності в програмуванні, оскільки додаток повинен знати про передбачувані запитах до ресурсів в усіх модулях.

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

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

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

Порушення умови кругового очікування. Важко запропонувати розумну стратегію, щоб уникнути останнього умови з розділу "Умови виникнення тупиків" - циклічного очікування.

Один зі способів - порядок ресурси. Наприклад, можна привласнити всіх ресурсів унікальні номери і вимагати, щоб процеси запитували ресурси в порядку їх зростання. Тоді круговий очікування виникнути не може. Наприклад, якщо процес запросив ресурс R1, то далі він може запитати тільки ресурси, такі згідно із зазначеним впорядкування за R1. Якби в прикладі, наведеному на рис. 9.1, потоки А і В замовляли ресурси в однаковому порядку (порт, диск), то взаимоблокировки можна було б уникнути. Очевидно, що практично неможливо знайти порядок, який задовольнить всіх.

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

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

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
	\|	Акустичні засоби\|кошти\| захисту

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.011 сек.