Безизходица - ситуация, в която всеки един от групата на процесите в очакване на едно събитие, което може да доведе до поредната процес в тази група. Често такава ситуация се наблюдава в парадоксите на "кокошката или яйцето". Също така, там са имената на задънената улица. безизходица. клинч. В английската литература, тази ситуация се нарича на английски език. застой (произнася Deadlock).
В областта на информационните технологии, взаимното блокиране се отнася до ситуация, в която се очаква два или повече процеси, а другият не, не освобождава конкретен ресурс, или ако има повече от два процеса са в очакване на освобождаването на ресурси в един затворен кръг.
Като пример, такава ситуация може да доведе двама мъже се направи схема, като само една линия и един молив. Ако един от мъжете да се линийка, молив и от друга страна, между тях се намират в положение на взаимно блокиране, когато за да се освободи линията трябва да бъде един молив, и че е необходимо да се освободи молива линия.
Най-общо казано, блокирането (или обесване) е налице ситуация, в която няма значение колко минава много време, никой prehid от едно състояние в друго, не може да се осъществи.
Условия за поява на безизходица
Доказано е, че за възникване на ситуация на безизходица, трябва да отговарят на следните четири условия в същото време:
- Състояние на взаимно изключване (инж. Взаимно изключване). Всеки ресурс в момента е зает или точно един процес или безплатно. Това означава, че ресурсите са разположени в режим на изключително ползване.
- Състоянието на задържане и очаквания (инж. Задръжте и да чакаме). Процесите в момента държат по-рано получените средства, може да прави искания за нови ресурси.
- Състоянието на липса на задължителното освобождаване на ресурси (инж. Не присвояване). Невъзможно е да се принуди процеса за освобождаване на получените по-рано, притежаващи ресурси resursy.Protsess трябва да ги уволни себе си.
- Circular състояние на изчакване (инж. Circular изчакване). Трябва да има пръстеновиден поредица от две или повече процеси, всеки от които чака за прекратяване на ресурс, притежаван от следващия член на последователността. С други думи, там би трябвало да съществува множество процеси, така че процесът P 0 чака РЕСУРСИ процес P 1, P 1 чака P 2. P N - 1 и P Н. очаква P N е в очакване на процес на ресурсите P 0.
За възникването на ситуация на безизходица, е необходимо, че всички четири условия едновременно. Ако поне едно от условията не е изпълнено, безизходица е невъзможно.
моделиране безизходица
Пример разпределение графика ресурс. В този пример, всички процеси, да имат достъп до необходимите ресурси, следователно, не може да бъде поравно.
Безизходна ситуация, може да се опише по-точно с помощта на специални инструменти - (. Английски ресурс система на разпределяне графиката) разпределението на ресурсите графика. В този насочено графика, множество върхове се състои от две подгрупи - всички активни процеси в системата (Р =) и съществуващите видове ресурси (R =).Краят на процеса P и ресурса е обозначена като Р J; Това означава, че процес Р и подава искане за една единица от тип ресурс R J и чака за ресурса (накратко, искането кош). Rib вид ресурс R J и процесът се нарича Р; Това означава, че тип един ресурс R J е даден процес и P (ръб съкращение освобождаване).
Тъй като може да има няколко единици от същия вид на ресурси, ресурсите са отбелязани върхове като правоъгълници с точки вътре. Броят на точките показва броя на ресурсните единици от този тип.
С това определение за разпределението на колоната на ресурсите, може да се докаже, че ако няма цикли в графиката, нито един от процесите не попада в задънена улица. При условие, че цикъл на графиката, има възможност за възникване на мъртвите зони.
Ако всеки вид ресурс има само едно копие, наличието на един цикъл предполага съществуването на безизходица. Всеки процес в цикъла удря в задънена улица.
Ако има видове ресурси с множество случаи, наличието на застой не произтича от наличието на цикъла. В този случай присъствието на цикъла е необходимо, но не достатъчно условие за възникване на мъртвите зони.
мрежи на Петри
В мрежата на Петри, наречен в задънена улица толкова много позиции, които всеки преход, че изходът е един от позициите на застоя, безизходица използва всяка позиция, като принос. Това означава, че ако всички задънена улица позиция в някакъв момент ще стане празен, целия набор от позиции ще останат празни завинаги. Никой от реброто не може да се движи в безизходица, защото не задънени чипове, позволяващи преход, изходът от които е позицията на застоя.
Trap се нарича набор от позиции, за които всеки преход, на входа на който е един от множеството позиции на изхода има различен набор позиция. Това означава, че ако на произволна позиция в капаните има функция, тя винаги ще бъде в състояние да капан.
Доказано е, че с надпис Петри нетна необходимо и достатъчно активност с възможност за свободен избор е изискването, че всяка съдържаше безизходица капан чип.
обработка безизходица
Обработка и пренос задънени ситуации могат да се разделят на:
- Пренебрегването проблем на всички (т.е.. Н. "щраус алгоритъм").
- Откриване и възстановяване. Позволявам се случи взаимно блокиране, идентифицира го и вземат някои мерки.
- Dynamic избягвайте безизходица чрез правилно разпределение на ресурсите.
- Предотвратяване на отказ от един от четирите условия на настъпване на блокировка.
Първият подход се използва в повечето съвременни операционни системи. правилно поведение в ситуация на безизходица е отговорност на разработчик на софтуер.
предотвратяване
Както бе споменато по-горе, възникването на ситуация на безизходица трябва да бъде едновременно изпълнение на четири условия. Ако един от тях не е изпълнено, тогава ситуацията на безизходица няма да се случи. Ето описание на подходите за всеки от условията.
взаимно изключване
Състояние на взаимно изключване, или изключителна употреба трябва да се извършва за неразделими ресурси. Например, устройството трябва да се използва Изключителен един процес. Въпреки това, някои от отделните ресурси, като например достъп до файлове на вашия четене, може да чуете много процеси.
Като цяло, състоянието на взаимно изключване не могат да бъдат избегнати, тъй като някои от ресурсите, трябва да се използва само в изключителен режим.
За неизпълнение на това, всеки път, когато процесът изисква нови ресурси, тя не трябва да съдържа и други ресурси. Следващите алгоритми:
- Получаване на всички ресурси в началото на процеса за извършване на други операции.
- Получаване на нов ресурс подлежи на освобождаване на заети ресурси. Преди да поискате нов ресурс, процесът освобождава ресурсите, заети от тях.
Недостатъкът на първия алгоритъм е неефективно използване на ресурсите и лесно. Също така, има възможност за "глад": в претоварена система, процес, който изисква няколко популярни ресурси никога не може да ги получи, тъй като най-малко един от тях може да се използва от друг процес.
Принудително освобождаване на ресурси
За неспазване на условията на липса на свободно място в ресурса, следните алгоритми:
Такъв алгоритъм се използва за ресурси, чието състояние може лесно да бъде записан и възпроизведен, като например регистър или памет.
циклични очаквания
цикличен избягване очаквания постига чрез създаване на процедура за достъп до ресурсите на различни видове.
Да - много видове ресурси. Ние се идентифицираме с всеки един от тях е цяло число, което ще сравни ресурси и определяне на приоритети (вж. Poset).
Сега, за да се избегне цикличните очаквания, установи следните права: процесът може да поиска средства само във възходящ ред на номерата. Алтернативно, процесът трябва да се освободи ресурс с голям брой последователност, преди да влезе искане за ресурс с по-малък брой.
Въпреки факта, че създаването и спазването на правилните процедури за получаване на достъп до ресурси е отговорност на разработчик на софтуер, има специализирани инструменти за проверка на съответствието със съобщенията за поръчки и за грешки. Един пример е програмата свидетел, който работи на BSD семейството на операционни системи.
За да се избегне застой sutatsy, програмата трябва предварително да се предостави информация на ресурсите на операционната система, която ще бъде използвана по време на процеса. С тази информация на операционната система може да реши да се срещне всеки процес заявка може да почака. За да се реши е да се изчака за процеса, операционната система трябва да се вземат предвид наличните ресурси, ресурсите са разпределени процеси и бъдещи изисквания, които могат да направят процеси.
инструменти
Той е известен с такива инструменти, които да работят с затягаща в изчислителни системи:
свидетел свидетел програма, която се изпълнява на operatsiniynih системи BSD-базирани, получава информация за Локи получи и проверка на допустимостта на тези искания. SPIN система за проверка на разпределени системи за модели.
Свързани статии