www.wikidata.uk-ua.nina.az

Взаємне блокування Взає мне блокува ння англ Deadlock ситуація коли кожен із групи процесів очікує на подію яку може вик

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

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

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

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

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

Умови виникнення взаємного блокування Редагувати

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

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

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

Livelock Редагувати

Динамічне взаємне блокування чи livelock — це коли стани процесів постійно змінюється один відносно одного — але все одно вони «у безвихідному циклі», що не робить ніякої корисної роботи.

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

Моделювання тупикових ситуацій Редагувати

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

Ситуації взаємного блокування можливо описати точніше з допомогою спеціального засобу — графу виділення ресурсів (англ. system resource-allocation graph). В цьому орієнтованому графі, множина вершин складається із двох підмножин — всіх активних процесів у системі () та існуючих типів ресурсів ().

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

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

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

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

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

Мережі Петрі Редагувати

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

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

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

Обробка тупикових ситуацій Редагувати

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

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

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

Запобігання Редагувати

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

Взаємне виключення Редагувати

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

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

Утримання та очікування Редагувати

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

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

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

Примусове звільнення ресурсів Редагувати

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

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

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

Циклічне очікування Редагувати

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

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

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

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

Уникнення Редагувати

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

Інструменти Редагувати

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

Примітки Редагувати

  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. 24 липня 2008. Архів оригіналу за 25 червня 2013. Процитовано 24 липня 2008. 
  18. . Архів оригіналу за 25 квітня 2009. Процитовано 17 квітня 2009. 
  • 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. 

Див. також Редагувати


Це незавершена стаття про інформаційні технології.
Ви можете допомогти проєкту, виправивши або дописавши її.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Vzaye mne blokuva nnya angl Deadlock situaciya koli kozhen iz grupi procesiv ochikuye na podiyu yaku mozhe viklikati lishe inshij proces z ciyeyi grupi 1 2 Chasto taka situaciya sposterigayetsya v paradoksah tipu Kurka chi yajce Takozh zustrichayutsya nazvi tupikova situaciya tupik klinch V anglomovnij literaturi cya situaciya maye nazvu angl deadlock vimovlyayetsya yak dedlok U galuzi informacijnih tehnologij vzayemnim blokuvannyam nazivayut situaciyu koli dva abo bilshe procesiv chekayut poki inshij ne zvilnit pevnij resurs abo koli bilshe nizh dva procesi chekayut na zvilnennya resursiv u zamknenomu lancyugu Yak priklad shozhoyi situaciyi mozhna navesti dvoh cholovikiv sho kreslyat shemi mayuchi lishe odnu linijku ta odin olivec Yaksho odin z cholovikiv vizme linijku a inshij olivec mizh nimi vinikaye situaciya vzayemnogo blokuvannya koli dlya togo abi zvilniti linijku treba olivec a dlya zvilnennya olivcya treba linijka Vzagali kazhuchi blokuvannyam abo zavisannyam ye taka situaciya koli ne zalezhno vid togo skilki spline chasu zhoden prehid iz odnogo stanu v inshij vidbutis ne mozhe 3 Zmist 1 Umovi viniknennya vzayemnogo blokuvannya 2 Livelock 3 Modelyuvannya tupikovih situacij 3 1 Merezhi Petri 4 Obrobka tupikovih situacij 4 1 Zapobigannya 4 1 1 Vzayemne viklyuchennya 4 1 2 Utrimannya ta ochikuvannya 4 1 3 Primusove zvilnennya resursiv 4 1 4 Ciklichne ochikuvannya 4 2 Uniknennya 5 Instrumenti 6 Primitki 7 Literatura 8 Div takozhUmovi viniknennya vzayemnogo blokuvannya RedaguvatiBulo pokazano sho dlya viniknennya situaciyi vzayemnogo blokuvannya neobhidno vikonannya nastupnih chotiroh umov vodnochas 4 5 6 Umova vzayemnogo viklyuchennya angl mutual exclusion Kozhen resurs v potochnij moment abo zajnyatij rivno odnim procesom abo vilnij Tobto resursi znahodyatsya v rezhimi eksklyuzivnogo koristuvannya Umova utrimannya ta ochikuvannya angl hold and wait Procesi sho v potochnij moment utrimuyut otrimani ranishe resursi mozhut robiti zapiti na otrimannya novih resursiv Umova vidsutnosti primusovogo zvilnennya resursiv angl no preemption Nemozhlivo primusiti proces zvilniti ranishe otrimani resursi Proces sho volodiye resursami povinen sam yih zvilnyati Umova ciklichnogo ochikuvannya angl circular wait Maye isnuvati kilceva poslidovnist iz dvoh abo bilshe procesiv kozhen iz yakih ochikuye na zvilnennya resursa sho utrimuyetsya nastupnim chlenom poslidovnosti Inshimi slovami maye isnuvati mnozhina procesiv P 0 P 1 P n displaystyle P 0 P 1 dots P n nbsp tak sho proces P 0 displaystyle P 0 nbsp ochikuye na zvilnennya resuriv procesu P 1 displaystyle P 1 nbsp P 1 displaystyle P 1 nbsp ochikuye na P 2 displaystyle P 2 nbsp P n 1 displaystyle P n 1 nbsp ochikuye na P n displaystyle P n nbsp a P n displaystyle P n nbsp ochikuye na zvilnennya resursiv procesom P 0 displaystyle P 0 nbsp Dlya viniknennya situaciyi vzayemnogo blokuvannya neobhidno vikonannya vsih chotiroh umov vodnochas Yaksho hocha b odna z umov ne vikonuyetsya vzayemne blokuvannya nemozhlive Livelock RedaguvatiDinamichne vzayemne blokuvannya chi livelock ce koli stani procesiv postijno zminyuyetsya odin vidnosno odnogo ale vse odno voni u bezvihidnomu cikli sho ne robit niyakoyi korisnoyi roboti Zhittyevij priklad takoyi situaciyi dvoye zustrichayutsya u vuzkomu koridori Kozhen z nih namagayetsya vidijti vbik shob propustiti inshogo ale ne mozhut rozminutis bo vidhodyat v odnu i tu zh storonu odnochasno Modelyuvannya tupikovih situacij Redaguvati nbsp Priklad grafu vidilennya resursiv V comu prikladi vsi procesi otrimayut dostup do neobhidnih resursiv otzhe vzayemne blokuvannya nemozhlive Situaciyi vzayemnogo blokuvannya mozhlivo opisati tochnishe z dopomogoyu specialnogo zasobu grafu vidilennya resursiv angl system resource allocation graph V comu oriyentovanomu grafi mnozhina vershin skladayetsya iz dvoh pidmnozhin vsih aktivnih procesiv u sistemi P P 1 P 2 P n displaystyle P P 1 P 2 dots P n nbsp ta isnuyuchih tipiv resursiv R R 1 R 2 R m displaystyle R R 1 R 2 dots R m nbsp 7 8 9 Rebro vid procesu P i displaystyle P i nbsp do resursu P j displaystyle P j nbsp poznachayetsya yak P i P j displaystyle P i to P j nbsp oznachaye sho proces P i displaystyle P i nbsp podav zapit na odnu odinicyu resursu tipu R j displaystyle R j nbsp ta ochikuye na cej resurs skorocheno rebro zapitu Rebro vid resursu tipu R j displaystyle R j nbsp do procesu P i displaystyle P i nbsp poznachayetsya yak R j P i displaystyle R j to P i nbsp oznachaye sho odinicyu resursu tipu R j displaystyle R j nbsp bulo nadano procesu P i displaystyle P i nbsp skorocheno rebro vidilennya Oskilki mozhe isnuvati dekilka odinic resursiv odnogo tipu vershini z resursami poznachayutsya u viglyadi pryamokutnikiv iz krapkami v seredini Kilkist krapok poznachaye kilkist odinic resursu cogo tipu Mayuchi take viznachennya grafu vidilennya resursiv mozhna dovesti sho za umovi vidsutnosti cikliv v grafi zhoden iz procesiv ne potraplyaye v tupik Za umovi nayavnosti ciklu v grafi isnuye mozhlivist dlya viniknennya tupikiv 8 Yaksho kozhen tip resursiv maye lishe odin ekzemplyar to iz nayavnosti ciklu viplivaye nayavnist tupika Kozhen proces v cikli potraplyaye v tupik 8 Yaksho ye tipi resursiv z dekilkoma ekzemplyarami to iz nayavnosti ciklu nayavnist tupika ne viplivaye V comu vipadku nayavnist ciklu ye neobhidnoyu ale ne dostatnoyu umovoyu dlya viniknennya tupikiv 8 Merezhi Petri Redaguvati V merezhah Petri tupikom nazivayetsya taka mnozhina pozicij sho kozhen perehid yakij na vihodi maye odnu iz pozicij tupika vikoristovuye bud yaku poziciyu tupika yak vhid Tobto yaksho vsi poziciyi tupika v deyakij moment sporozhniyut to vsya cya mnozhina pozicij zalishitsya porozhnoyu nazavzhdi Zhoden iz perehodiv ne mozhe peresunuti fishku v tupik oskilki v tupiku vidsutni fishki yaki b dozvolili perehid vihodom yakogo ye poziciya z tupika 10 11 Pastkoyu nazivayetsya taka mnozhina pozicij dlya yakoyi kozhen perehid vhodom yakogo ye odna iz pozicij mnozhini na vihodi maye inshu poziciyu mnozhini Tobto yaksho v dovilnij poziciyi pastki ye fishka to vona zavzhdi perebuvatime v deyakij iz pozicij pastki Bulo dovedeno 10 sho neobhidnoyu i dostatnoyu umovoyu aktivnosti markovanoyi merezhi Petri z vilnim viborom ye vimoga togo shob kozhen tupik mistiv pastku z fishkoyu Obrobka tupikovih situacij RedaguvatiObrobku ta povodzhennya iz situaciyami vzayemnogo blokuvannya mozhna umovno podiliti na 12 Nehtuvannya problemoyu vzagali t z strausinij algoritm Viyavlennya ta vidnovlennya Dozvoliti vidbutisya vzayemnomu blokuvannyu viyaviti jogo ta vikonati deyaki diyi Dinamichne uniknennya vzayemnogo blokuvannya shlyahom pravilnogo rozpodilu resursiv Zapobigannya shlyahom nevikonannya odniyeyi iz chotiroh umov viniknennya vzayemnogo blokuvannya Pershij pidhid vikoristovuyetsya v bilshosti suchasnih operacijnih sistem pravilne povodzhennya u situaciyi vzayemnogo blokuvannya ye vidpovidalnistyu rozrobnika PZ 13 Zapobigannya Redaguvati Yak bulo vkazano vishe dlya viniknennya situaciyi vzayemnogo blokuvannya neobhidne odnochasne vikonannya chotiroh umov Yaksho hocha b odna z nih ne vikonuyetsya to situaciyi vzayemnogo blokuvannya vinikati ne budut 14 15 16 Nizhche navedeno opisannya pidhodiv do kozhnoyi z umov Vzayemne viklyuchennya Redaguvati Umova vzayemnogo viklyuchennya abo ekslyuzivnogo koristuvannya povinna vikonuvatis dlya nerozdilnih resursiv Napriklad printer maye vikoristovuvatis ekslyuzivno odnim procesom Odnak deyaki rozdilni resursi taki yak dostup do fajliv na chitannya mozhut rozdavatis bagatom procesam V zagalnomu vipadku umovu vzayemnogo viklyuchennya nemozhlivo obijti oskilki deyaki z resursiv mayut vikoristovuvatis lishe v ekslyuzivnomu rezhimi Utrimannya ta ochikuvannya Redaguvati Dlya nevikonannya ciyeyi umovi kozhen raz koli proces potrebuye novi resursi vin povinen ne utrimuvati inshi resursi Mozhlivi taki algoritmi Otrimuvati vsi resursi na pochatku roboti procesu do vikonannya reshti operacij Otrimuvati novij resurs lishe za umovi vivilnennya zajnyatih resursiv Pered zapitom novogo resursu proces zvilnyaye zajnyati nim resursi Nedolikom pershogo algoritmu ye neefektivne vikoristannya ta prostij resursiv Takozh isnuye mozhlivist golodu v perenavantazhenij sistemi proces sho potrebuye dekilka populyarnih resursiv mozhe nikoli yih ne otrimati oskilki hocha b odin iz nih mozhe buti zajnyatij inshim procesom Primusove zvilnennya resursiv Redaguvati Dlya nevikonannya umovi vidsutnosti primusovogo zvilnennya resursiv mozhlivi taki algoritmi U vipadkah koli proces zapituye dostup do resursu yakij ne mozhe buti odrazu nadano vin zvilnyaye reshtu zajnyatih resursiv i peredaye yih v chergu na zapit Robotu procesu bude vidnovleno pislya otrimannya dostupu do vsih resursiv u cherzi stari ta novi resursi Spochatku pereviriti mozhlivist nadannya resursu yaksho mozhlivist nadati resurs vidsutnya cherez vikoristannya jogo inshim procesom sho ochikuye na zvilnennya deyakih inshih resursiv to zvilniti cej resurs i peredati jogo procesu zamovniku Yaksho neobhidnij resurs yak nedostupnij tak i proces sho jogo vikoristovuye ne ochikuye na zvilnennya inshih resursiv to perevesti proces sho podav zapit v stan ochikuvannya Pid chas ochikuvannya deyaki utrimuvani nim resursi mozhut buti zvilneno cherez zapiti tretih procesiv Proces vidnovlyuye robotu pislya togo yak otrimaye neobhidni resursi ta resursi sho buli zvilneni pid chas ochikuvannya Takij algoritm vikoristovuyetsya dlya resursiv stan yakih mozhe buti legko zberezheno ta vidtvoreno takih yak registri procesora abo prostori pam yati Ciklichne ochikuvannya Redaguvati Uniknennya ciklichnogo ochikuvannya dosyagayetsya vstanovlennyam poryadku otrimannya dostupu do resursiv riznih tipiv Nehaj R R 1 R 2 R n displaystyle R R 1 R 2 dots R n nbsp mnozhina tipiv resursiv Ototozhnimo z kozhnim z nih cile chislo sho dozvolit porivnyuvati resursi ta vstanovlyuvati prioriteti div chastkovo vporyadkovana mnozhina Teper dlya uniknennya ciklichnogo ochikuvannya vstanovimo nastupne pravilo proces mozhe zapituvati resursi lishe v zrostayuchomu poryadku nomeriv Yak variant proces maye zvilnyati resurs z bilshim poryadkovim nomerom pered podannyam zapitu na resurs z menshim nomerom Popri te sho vstanovlennya ta dotrimannya pravilnogo poryadku otrimannya dostupu do resursiv ye vidpovidalnistyu rozrobnika PZ isnyut specializovani instrumenti dlya perevirki dotrimannya poryadku ta povidomlennya pro pomilki Odnim z prikladiv ye programa witness sho pracyuye na operacijnih sistemah sim yi BSD 17 Uniknennya Redaguvati Dlya uniknennya tupikovih sutacij programi mayut zazdelegid nadavati operacijnij sistemi informaciyu pro resursi sho budut vikoristani procesom pid chas roboti Mayuchi cyu informaciyu operacijna sistema mozhe virishuvati na zadovolennya yakih zapitiv proces mozhe zachekati Abi virishiti chi povinen proces chekati operacijna sistema maye brati do uvagi dostupni resursi resursi vidileni procesam ta majbutni zapiti yaki mozhut zrobiti procesi Instrumenti RedaguvatiVidomi taki instrumenti dlya roboti z klinchami v obchislyuvalnih sistemah witness programa witness sho pracyuye na operacijnih sistemah simejstva BSD otrimuye informaciyu pro otrimani loki ta pereviryaye na pripustimist ci zapiti 17 SPIN sistema dlya verifikaciyi modelej rozpodilenih sistem 18 Primitki Redaguvati Tanenbaum 2002 glava 3 stor 188 Abraham 2005 glava 7 stor 246 Bowman Gomez rozdil 12 2 Coffman et al 1971 Tanenbaum 2002 stor 188 189 Abraham 2005 rozdil 7 2 stor 247 249 Holt 1972 a b v g Abraham 2005 rozdil 7 2 2 stor 249 Tanenbaum 2002 stor 189 192 a b Hack 1972 Piterson 1984 rozdil 7 4 3 stor 202 203 Tanenbaum 2002 glava 3 stor 192 Abraham 2005 rozdil 7 3 stor 252 Havender 1968 Tanenbaum 2002 stor 206 Abraham 2005 rozdil 7 4 stor 253 a b FreeBSD 7 0 WITNESS 4 Manual page 24 lipnya 2008 Arhiv originalu za 25 chervnya 2013 Procitovano 24 lipnya 2008 Arhivovana kopiya Arhiv originalu za 25 kvitnya 2009 Procitovano 17 kvitnya 2009 Coffman E G Elphick M J and Shoshani A System Deadlocks Computing Surveys vol 3 pp 67 78 cherven 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 veresen 1972 Hack M Analysis of Production Schemata by Petri Nets Master s thesis Department of Electrical Engineering Massachusetts Institute of Technology lyutij 1972 Literatura RedaguvatiTanenbaum E 2002 glava 3 Sovremennye Operacionnye Sistemy vid 2 SPb Piter ISBN 5 318 00299 4 Piterson Dzh 1984 Teoriya setej Petri i modelirovanie sistem M Mir per z angl Abraham Silberschatz Peter Baer Galvin Greg Gagne 2005 glava 7 Operating Systems Concepts vid 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 Div takozh RedaguvatiParalelne programuvannya Proces Zavisannya Problema zupinki Pi chislennya Merezha Petri Obmin povidomlennyami Teoriya grafiv nbsp Ce nezavershena stattya pro informacijni tehnologiyi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Otrimano z https uk wikipedia org w index php title Vzayemne blokuvannya amp oldid 38256371