Головна

Методи обходу тупиків

  1.  Event-менеджмент - поняття, основні методи.
  2.  I група Організаційно-стимулюючі методи
  3.  I. Об'єкти, методи і завдання інженерної геології
  4.  I. ПРЕДМЕТ, МЕТОДИ І СТРУКТУРА ЮРИДИЧНОЇ ПСИХОЛОГІЇ
  5.  II. МЕТОДИ (МЕТОДИКИ) Патопсихологическое дослідження МЕТОДИКИ ДЛЯ ДОСЛІДЖЕННЯ УВАГИ І сенсомоторної реакції
  6.  II. Методи аналізу травматизму
  7.  II. Структурні і персональні методи управління організаційними конфліктами.

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

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

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

Запобігання тупика "в останній момент" можливо в тому випадку, коли відома максимальна потреба у всіх ресурсах апріорі для кожного процесу.

Максимальна потреба в ресурсах для будь-якого процесу є найбільше число одиниць кожного ресурсу, в яких коли-небудь буде потребувати процес. Ці потреби в системі можна уявити числами Cij (I = 1,2, ..., n, j = 1,2, ..., m), де Cij представляє максимальну потребу процесу pi в ресурсі Rj.

Для кожного процесу pi і ресурсу Rj в системі має виконуватися додаткове обмеження на запити

| (Pi, Rj) | + | (Rj, pi) | ? Cij ? cj,

де cj - Ємність ресурсу.

Граф потреб для стану S визначається як граф повторно використовуваних ресурсів стану S, доповнений дугами запитів на nij одиниць ресурсу Rj для процесу pi, де

nij = Cij - (| (Pi, Rj) | + | (Rj, pi) |).

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

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

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

Наступна теорема є основою для реалізації його для вирішення описаної тупика:

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

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

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

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

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

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

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

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

Нехай для кожного споживаного ресурсу Rj відомо непорожня множина процесів - його виробників - p P (Rj) I p і непорожня множина процесів-споживачів цього ресурсу p C (Rj) I p. процес pi може запросити й придбати ресурс Rj, Тільки якщо pi I p C (Rj). процес pi може звільнити ресурс Rj, Тільки якщо pi I p P (Rj).

У кожній такій системі існує стан, зване станом з обмеженнями на вимоги, яке визначається наступним чином:

? процес pi має виданий запит на одиницю ресурсу Rj тоді і тільки тоді, коли pi I p C (Rj);

? у всіх споживаних ресурсів в системі немає доступних одиниць (тобто всі вершини, що представляють ці ресурси в графі ПР мають нульові позначки).

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

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

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




 Л. Н. Лядова |  Теоретичні основи операційних систем |  визначення процесу |  поняття ресурсу |  Віртуальний процесор |  Віртуальний процесор |  Черга процесів Завершення або блокування |  Переривання активного процесу і перерозподіл процесора |  Класифікація процесів |  Класифікація ресурсів |

© 2016-2022  um.co.ua - учбові матеріали та реферати