Вікіпедія

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

Інтерактивний перегляд історії
[неперевірена версія][неперевірена версія]
← Попереднє редагуванняНаступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
Рядок 17:
 
== Моделювання тупикових ситуацій ==
[[Зображення:Sample-resource-allocation-graph.svg|thumb|250px|right|Приклад графу виділення ресурсів. В цьому прикладі всі процеси отримають доступ до необхідних ресурсів, отже, взаємне блокування неможливе.]]
 
Ситуації взаємного блокування можливо описати точніше з допомогою спеціального засобу&nbsp;— ''графу виділення ресурсів'' ({{lang-en|system resource-allocation graph}}). В цьому орієнтованому [[Граф (математика)|графі]], множина вершин складається із двох підмножин&nbsp;— ресурсіввсіх таактивних процесів у системі (<math>P = \{P_1, P_2, \dots, P_n\}</math>) та існуючих типів ресурсів (<math>R = \{R_1, R_2, \dots, R_m\}</math>).<ref>(Holt 1972)</ref><ref>(Abraham 2005) розділ 7.2.2, стор. 249.</ref><ref>(Таненбаум 2002), стор. 189—192</ref>
 
Ребро від процесу <math>P_i</math> до ресурсу <math>P_j</math> позначається як <math>P_i \to P_j</math>; означає, що процес <math>P_i</math> подав запит на одну одиницю ресурсу типу <math>R_j</math> та очікує на цей ресурс (скорочено, ребро запиту). Ребро від ресурсу типу <math>R_j</math> до процесу <math>P_i</math> позначається як <math>R_j \to P_i</math>; означає, що одиницю ресурсу типу <math>R_j</math> було надано процесу <math>P_i</math> (скорочено, ребро виділення).
 
Оскільки може існувати декілька одиниць ресурсів одного типу, вершини з ресурсами позначаються у вигляді прямокутників із крапками в середині. Кількість крапок позначає кількість одиниць ресурсу цього типу.
 
Маючи таке визначення графу виділення ресурсів, можна довести, що за умови відсутності [[Цикл (теорія графів)|циклів]] в графі жоден із процесів не потрапляє в тупик. За умови наявності циклу в графі, існує можливість для виникнення тупиків.<ref>(Abraham 2005) розділ 7.2.2, стор. 249.</ref>
 
Якщо кожен тип ресурсів має лише один екземпляр, то із наявності циклу випливає наявність тупика. Кожен процес в циклі потрапляє в тупик.<ref>(Abraham 2005) розділ 7.2.2, стор. 249.</ref>
 
Якщо є типи ресурсів з декількома екземплярами, то із наявності циклу наявність типика не випливає. В цьому випадку наявність циклу є необхідною, але не достатньою умовою для виникнення тупиків.<ref>(Abraham 2005) розділ 7.2.2, стор. 249.</ref>
 
== Обробка тупикових ситуацій ==
Отримано з https://uk.wikipedia.org/wiki/Взаємне_блокування