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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Process deadlock.svg

Взає́мне блокува́ння (англ. Deadlock) — ситуація, коли кожен із групи процесів очікує на подію, яку може викликати лише інший процес з цієї групи.[1][2] Часто, така ситуація спостерігається в парадоксах типу «Курка або яйце». Також зустрічаються назви тупикова ситуація, тупик, клінч. В англомовній літературі ця ситуація має назву англ. deadlock (вимовляється як дедлок).

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

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

Взагалі кажучи, блокуванням (або зависанням) є така ситуація, коли не залежно від того, скільки сплине часу, жоден прехід із одного стану в інший відбутись не може.[3]

Умови виникнення взаємного блокування[ред.ред. код]

Було показано, що для виникнення ситуації взаємного блокування, необхідно виконання наступних чотирьох умов водночас:[4][5][6]

  1. Умова взаємного виключення (англ. mutual exclusion). Кожен ресурс в поточний момент або зайнятий рівно одним процесом або вільний. Тобто, ресурси знаходяться в режимі ексклюзивного користування.
  2. Умова утримання та очікування (англ. hold and wait). Процеси, що в поточний момент утримують отримані раніше ресурси, можуть робити запити на отримання нових ресурсів.
  3. Умова відсутності примусового звільнення ресурсів (англ. no preemption). Неможливо примусити процес звільнити раніше отримані ресурси. Процес, що володіє ресурсами, повинен сам їх звільняти.
  4. Умова циклічного очікування (англ. circular wait). Має існувати кільцева послідовність із двох або більше процесів, кожен із яких очікує на звільнення ресурса, що утримується наступним членом послідовності. Іншими словами, має існувати множина процесів \{P_0, P_1, \dots, P_n\}, так, що процес P_0 очікує на звільнення ресурів процесу P_1, P_1 очікує на P_2, …, P_{n-1} очікує на P_n, а P_n очікує на звільнення ресурсів процесом P_0.

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

Livelock[ред.ред. код]

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

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

Моделювання тупикових ситуацій[ред.ред. код]

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

Ситуації взаємного блокування можливо описати точніше з допомогою спеціального засобу — графу виділення ресурсів (англ. system resource-allocation graph). В цьому орієнтованому графі, множина вершин складається із двох підмножин — всіх активних процесів у системі (P = \{P_1, P_2, \dots, P_n\}) та існуючих типів ресурсів (R = \{R_1, R_2, \dots, R_m\}).[7][8][9]

Ребро від процесу P_i до ресурсу P_j позначається як P_i \to P_j; означає, що процес P_i подав запит на одну одиницю ресурсу типу R_j та очікує на цей ресурс (скорочено, ребро запиту). Ребро від ресурсу типу R_j до процесу P_i позначається як R_j \to P_i; означає, що одиницю ресурсу типу R_j було надано процесу P_i (скорочено, ребро виділення).

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

Маючи таке визначення графу виділення ресурсів, можна довести, що за умови відсутності циклів в графі жоден із процесів не потрапляє в тупик. За умови наявності циклу в графі, існує можливість для виникнення тупиків.[8]

Якщо кожен тип ресурсів має лише один екземпляр, то із наявності циклу випливає наявність тупика. Кожен процес в циклі потрапляє в тупик.[8]

Якщо є типи ресурсів з декількома екземплярами, то із наявності циклу наявність тупика не випливає. В цьому випадку наявність циклу є необхідною, але не достатньою умовою для виникнення тупиків.[8]

Мережі Петрі[ред.ред. код]

В мережах Петрі, тупиком називається така множина позицій, що кожен перехід, який на виході має одну із позицій тупика, використовує будь-яку позицію тупика в якості входу. Тобто, якщо всі позиції тупика в деякий момент спорожніють, то вся ця множина позицій залишиться порожньою назавжди. Жоден із переходів не може пересунути фішку в тупик, оскільки в тупику відсутні фішки, які б дозволили перехід, виходом якого є позиція з тупика.[10][11]

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

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

Обробка тупикових ситуацій[ред.ред. код]

Обробку та поводження із ситуаціями взаємного блокування можна умовно поділити на:[12]

  1. Нехтування проблемою взагалі (т. з. «страусиний алгоритм»).
  2. Виявлення та відновлення. Дозволити відбутися взаємному блокуванню, виявити його, та виконати деякі дії.
  3. Динамічне уникнення взаємного блокування шляхом правильного розподілу ресурсів.
  4. Запобігання шляхом невиконання однієї із чотирьох умов виникнення взаємного блокування.

Перший підхід використовується в більшості сучасних операційних систем: правильне поводження у ситуації взаємного блокування є відповідальністю розробника ПЗ.[13]

Запобігання[ред.ред. код]

Як було вказано вище, для виникнення ситуації взаємного блокування необхідне одночасне виконання чотирьох умов. Якщо хоча б одна з них не виконується, то ситуації взаємного блокування виникати не будуть.[14][15][16] Нижче наведено описання підходів до кожної з умов.

Взаємне виключення[ред.ред. код]

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

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

Утримання та очікування[ред.ред. код]

Для невиконання цієї умови, кожен раз, коли процес потребує нові ресурси, він повинен не утримувати інші ресурси. Можливі такі алгоритми:

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

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

Примусове звільнення ресурсів[ред.ред. код]

Для невиконання умови відсутності примусового звільнення ресурсів, можливі такі алгоритми:

  1. У випадках, коли процес запитує доступ до ресурсу, який не може бути одразу надано, він звільняє решту зайнятих ресурсів, і передає їх в чергу на запит. Роботу процеса буде відновлено після отримання доступу до всіх ресурсів у черзі (старі та нові ресурси).
  2. Спочатку перевірити можливість надання ресурсу, якщо можливість надати ресурс відсутня через використання його іншим процесом, що очікує на звільнення деяких інших ресурсів, то звільнити цей ресурс, і передати його процесу-замовнику. Якщо необхідний ресурс як недоступний, так і процес, що його використовує, не очікує на звільнення інших ресурсів, то перевести процес, що подав запит, в стан очікування. Під час очікування, деякі утримувані ним ресурси можуть бути звільнено через запити третіх процесів. Процес відновлює роботу після того, як отримає необхідні ресурси та ресурси, що були звільнені під час очікування.

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

Циклічне очікування[ред.ред. код]

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

Нехай R = \{ R_1, R_2, \dots, R_n \} — множина типів ресурсів. Ототожнимо з кожним з них ціле число, що дозволить порівнювати ресурси та встановлювати пріоритети (див. частково впорядкована множина).

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

Попри те, що встановлення та дотримання правильного порядку отримання доступу до ресурсів є відповідальністю розробника ПЗ, існють спеціалізовані інструменти для перевірки дотримання порядку та повідомлення про помилки. Одним з прикладів є програма witness, що працює на операційних системах сім'ї BSD.[17]

Уникнення[ред.ред. код]

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

Інструменти[ред.ред. код]

Відомі такі інструменти для роботи з клінчами в обчислювальних системах:

witness 
програма witness, що працює на операційних системах сімейства BSD, отримує інформацію про отримані локи та перевіряє на припустимість ці запити.[17]
SPIN 
система для верифікації моделей розподілених систем.[18]

Посилання[ред.ред. код]

  1. (Таненбаум 2002), глава 3 , стор. 188.
  2. (Abraham 2005), глава 7, стор. 246.
  3. (Bowman, Gomez) розділ 12.2
  4. (Coffman et al 1971)
  5. (Таненбаум 2002), стор. 188—189
  6. (Abraham 2005), розділ 7.2, стор. 247—249
  7. (Holt 1972)
  8. а б в г (Abraham 2005) розділ 7.2.2, стор. 249.
  9. (Таненбаум 2002), стор. 189—192
  10. а б (Hack 1972)
  11. (Питерсон 1984), розділ 7.4.3, стор. 202—203.
  12. (Таненбаум 2002), глава 3, стор. 192.
  13. (Abraham 2005), розділ 7.3, стор. 252.
  14. (Havender 1968)
  15. (Таненбаум 2002), стор. 206.
  16. (Abraham 2005), розділ 7.4, стор. 253.
  17. а б «FreeBSD 7.0: WITNESS(4) Manual page». 2008-07-24. Архів оригіналу за 2013-06-26. 
  18. http://www.spinroot.com/
  • Coffman, E. G., Elphick, M. J. and Shoshani, A.: «System Deadlocks», Computing Surveys, vol. 3, pp. 67—78, червень 1971.
  • Havender, J. W.: «Avoiding Deadlock in Multitasking Systems», IBM Systems Journal, vol. 7, pp. 74—84, 1968.
  • Holt, R. C.: «Some Deadlock Properties of Computer Systems», Computing Surveys, vol. 4, pp. 179—196, вересень 1972.
  • Hack M., Analysis of Production Schemata by Petri Nets, Master's thesis, Department of Electrical Engineering, Massachusetts Institute of Technology, лютий 1972.

Дивіться також[ред.ред. код]

Література[ред.ред. код]

  • Таненбаум Э. (2002). «глава 3». Современные Операционные Системы (вид. 2). СПб Питер. ISBN 5-318-00299-4. 
  • Питерсон Дж. (1984). Теория сетей Петри и моделирование систем. М. «Мир».  (пер. з англ.)
  • Abraham Silberschatz, Peter Baer Galvin, Greg Gagne (2005). «глава 7». Operating Systems Concepts (вид. 7). Wiley. ISBN 0-471-69466-5. 
  • Howard Bowman, Rodolfo Gomez (2006). Concurrency Theory. Springer. ISBN 978-1-85233-895-4. 
  • Ajay D. Kshemkalyani, Mukesh Singhal (2008). «Deadlock detection in distributed systems». Distributed Computing Principles, Algorithms, and Systems. Cambridge University Press. ISBN 978-0-511-39341-9. 


Комп'ютер Це незавершена стаття про комп'ютери.
Ви можете допомогти проекту, виправивши або дописавши її.