Принципи взаємного блокування

Взаємоблокування

Лекція №9

1. Принципи взаємного блокування

2. Умови виникнення взаємоблокування

3. Запобігання, виявлення та усунення взаємо блокування

3.1. Ігнорування проблеми тупиків

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

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

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

4. Механізми паралельних обчислень в UNIX

4.1. Взаємодія процесів

4.2. Колективна пам'ять

4.3. Семафори

4.4. Черги повідомлень

4.5. Програмні канали

4.6. Програмні гнізда (sockets)

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

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

Розглянемо приклад тупика. Нехай двом потокам (процесам), що виконується в режимі мультипрограмування, для виконання їхньої роботи потрібно два ресурси, наприклад, порт і диск. На малюнку 9.1 (а) показані фрагменти відповідних програм. І нехай після того, як потік А зайняв порт (встановив блокуючу змінну), він був перерваний. Управління отримав потік В, який спочатку зайняв диск, але при виконанні наступної команди був заблокований, оскільки порт виявився вже зайнятим потоком А. Управління знову отримав потік А, який у відповідності зі своєю програмою зробив спробу зайняти диск і був заблокований: диск вже розподілений потоку В. У такому положенні потоки А і В можуть знаходитися як завгодно довго.

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

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

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

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

Рис. 9.1. Виникнення взаємних блокувань при виконанні програми;

(Б) взаємне блокування (клінч); (в) черга до поділюваного диску;

(Г) незалежне використання ресурсів

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

Взаимоблокировки можуть відбутися в безлічі інших ситуацій крім запитів виділених пристроїв введення-виведення. У системах баз даних програма може виявитися вимушеної заблокувати кілька записів, щоб уникнути стану конкуренції. Якщо процес А блокує запис R1, процес В блокує запис R2, а потім кожен процес намагається заблокувати чужу запис, ми також опинимося в глухому куті. Таким чином, взаимоблокировки з'являються при роботі як з апаратними, так і з програмними ресурсами.

Проблема тупиків включає в себе наступні завдання:

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

- Розпізнавання тупиків;

- Відновлення системи після тупиків.

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

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

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

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

<== попередня сторінка	\|	наступна сторінка ==>
Справедливість	\|	Умови виникнення взаємоблокування

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

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