Поява операційних систем і їх функції. | Класифікація операційних систем. | Диспетчеризація задач з використанням динамічних пріоритетів. | Сегментна, сторінкова і сегментно-сторінкова організація пам'яті. | Кешування операцій введення-виведення при роботі з накопичувачами на магнітних дисках. |

загрузка...
загрузка...
На головну

Методи боротьби з тупиками

  1. I. Неекспериментальні методи
  2. II. Арени. Методи отримання.
  3. II. Основні методи збору соціологічної інформації, їх коротка характеристика.
  4. II. експериментальні методи
  5. II. МЕТОДИ ДЕРЖАВНОГО УПРАВЛІННЯ.
  6. IV. Методи дослідження виконавчої та пізнавальної діяльності
  7. IV. Методи опитування в соціологічному дослідженні.

36. Поняття тупикової ситуації при виконанні паралельних обчислювальних процесів

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

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

? Ця ситуація називається тупиком, Дедлок, або клінчем.

Ресурси системи поділяють на два класи:

- Повторно використовувані (Reusable Resource, RR), або системні (System Resource, SR), ресурси;

- Споживані, або витрачаються, ресурси (Consumable Resource, CR).

? Системні ресурси (SR) - кінцеве безліч ідентичних одиниць деякого виду ресурсів, що володіють властивостями:

- Число одиниць ресурсу в системі незмінно;

- Кожна одиниця ресурсу або доступна, або виділена одному і тільки одному процесу;

- Процес може звільнити одиницю ресурсу (зробити її доступною), тільки якщо він раніше отримав цю одиницю.

? Особливості витрачених ресурсів (CR):

- Число доступних одиниць деякого ресурсу типу CR змінюється в міру того, як виконуються процесами вони витрачаються (купуються) і звільняються (виробляються);

- Процес «споживач» зменшує число одиниць ресурсу, спочатку запитуючи і потім прибрати (споживаючи) одну або більше одиниць.

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

? У графічній формі процеси і ресурси представляються квадратами і кружками відповідно. Кожен гурток містить деяку кількість маркерів (фішок) відповідно до існуючого кількістю одиниць цього ресурсу.

? Дуга з «процесу» на «ресурс» означає запит однієї одиниці цього ресурсу. Дуга з «ресурсу» на «процес» - виділення ресурсу процесу.

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

? Задоволення запиту Пр1 призведе до тупикової ситуації: Пр1 не зможе продовжитися до тих пір, поки Пр2 не звільнить одиницю ресурсу R1, а процес Пр2 не зможе продовжитися до тих пір, поки Пр1 не звільнить одиницю R2.

37. Приклади тупикових ситуацій і причини їх виникнення

? Приклад тупика на ресурсах типу CR? Нехай є три процесу Пр1, Пр2 і ПРЗ, які виробляють повідомлення Ml, M2 і МЗ, відповідно. Ці повідомлення є ресурси типу CR. Нехай процес Пр1 є споживачем повідомлення МОЗ, процес Пр2 повинен отримати повідомлення Ml, а ПРЗ - повідомлення М2 від процесу Пр2. Таким чином, кожен з цих трьох процесів є і постачальником, і споживачем одночасно, і разом вони утворюють кільцеву систему (рис. 7.2) передачі повідомлень через поштові скриньки (ПМ).

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

Приклад тупика на ресурсах типу CR і SR

? Нехай процес Пр1 повинен обмінятися повідомленнями з процесом Пр2 і кожен з них запитує ресурс R, причому Пр1 вимагає три одиниці цього ресурсу для своєї роботи, а Пр2 - дві одиниці і тільки на час обробки повідомлення. Всього ж є тільки чотири одиниці ресурсу R. Запит і звільнення ресурсу можна реалізувати через відповідний монітор з процедурами запиту N одиниць ресурсу R, і звільнення (повернення) N одиниць ресурсу R. Обмін повідомленнями здійснюється через поштову скриньку MB.

? Ці два процеси завжди будуть потрапляти в стан безвиході. Процес Пр2, виконуючись першим, спочатку буде очікувати повідомлення від процесу Пр1, потім буде заблокований при запиті ресурсу R, частина якого вже віддана процесу Пр1.

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

? Глухого кута можна уникнути лише за умови, що на час очікування відповіді від Пр2 процес Пр1 віддасть хоча б одну з одиниць ресурсу R, якими він володіє.

? В даному прикладі, як і в попередньому, причиною глухого кута є помилки програмування.

Приклад тупика на ресурсах типу SR - не розглядаємо, але можливий.

? Для виникнення тупикової ситуації необхідне одночасне виконання таких чотирьох умов:

? взаємного виключення, при якому процеси здійснюють монопольний доступ до ресурсів;

? очікування, при якому процес, що запросив ресурс, чекає до тих пір, поки запит не буде задоволений, при цьому утримуючи раніше отримані ресурси;

? відсутність перерозподілу, при якому ресурси не можна відібрати у процесу, якщо вони йому вже виділені;

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

38. Методи боротьби з тупиками

? Боротьба з тупиковими ситуаціями ґрунтується на одній з трьох стратегій:

? запобігання глухого кута;

? обхід тупика;

? розпізнавання тупика з подальшим відновленням.

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

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

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

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

? Умова відсутності перерозподілу можна виключити, дозволяючи ОС віднімати у процесу ресурси. Для цього в ОС повинен бути передбачений механізм запам'ятовування стану процесу з метою подальшого відновлення ходу обчислень.

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

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

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

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

? Класичне рішення цього завдання запропоновано Дейкстрой і відомо як алгоритм банкіра.

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

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

39. Виявлення тупика

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

Виявлення тупика за допомогою редукції графа повторно використовуваних ресурсів:

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

? Граф повторно використовуваних ресурсів непріводімие, якщо він не може бути скорочений жодним процесом.

? Граф ресурсів типу SR є повністю скорочуваним, якщо існує послідовність скорочень, яка видаляє всі дуги графа.

Лемма: для ресурсів типу SR порядок скорочень дуг графа повторно використовуваних ресурсів несуттєвий; всі послідовності ведуть до одного і того ж непріводімие графу.

Теорема про тупику: Стан S є стан безвиході тоді і тільки тоді, коли граф повторно використовуваних ресурсів в стані S не є повністю скорочуваним.

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

Другий наслідок: якщо S є стан безвиході (по ресурсах типу SR), то принаймні два процеси зайшли в глухий кут у S.

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

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

Методи виявлення тупика за наявністю замкнутого ланцюжка запитів

? Перша теорема: цикл в графі повторно використовуваних ресурсів є необхідною умовою тупика.

? Друга теорема: тупик може бути викликаний тільки при запиті, який не задоволений негайно. Т. Є. перевірка на тупиковий стан може бути виконана більш ефективно, якщо вона проводиться безперервно (в міру розвитку процесів).

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

? Третя теорема: якщо стан системи фіксоване (всі процеси, що мають запити, задоволені), то наявність вузла в відповідному графі повторно використовуваних ресурсів - достатня умова тупика.

? Четверта теорема: граф повторно використовуваних ресурсів з одиничною ємністю вказує на стан безвиході тоді і тільки тоді, коли він містить цикл.

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

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

Методи відновлення:

? примусовий перезапуск системи з втратою інформації про всі процеси, що існували до перезапуску;

? примусове завершення процесів, що знаходяться в глухому куті;

? примусове послідовне завершення процесів, що знаходяться в глухому куті, з подальшим викликом алгоритму розпізнавання після кожного завершення до зникнення тупика;

? перезапуск процесів, що знаходяться в глухому куті, з деякою контрольної точки;

? перерозподіл ресурсів з подальшим послідовним перезапуском процесів, що знаходяться в глухому куті.


 



Файлова система NTFS | Інтерфейси операційних систем
загрузка...
© um.co.ua - учбові матеріали та реферати