4.МЪРТВА ХВАТКА

В мултипрограмната среда може да настъпи безизходна ситуация, при която два или повече процеси чакат за условия, които никога няма да настъпят.Подобна ситуация се нарича взаимна блокировка, мъртва хватка.Разпределението на ресурсите е една от главните функции на ОС.Когато ресурсите се разпределят между много потребители, всеки от които има монополно право за управление на отделния му ресурс, възможно е да настъпи мъртва хватка.Ресурсите могат да се разделят на постоянни(повторно използваеми) и временни(потреби ми) ресурси.Пример за постоянните ресурси са устройствата, а за временните съобщенията.

4.1.МЪРТВА ХВАТКА ПРИ РАЗПРЕДЕЛЕНИЕ НА РЕСУРСИТЕ

Постоянните ресурси са физически (процесор, памет, устройства) или логически(файлове от данни, програми, таблици).Някои ресурси допускат съвместно използване на няколко процеса(процесора, паметта,дисковете), а други се закрепват към индивидуален процес за монополно използване за определено време(магнитна лента).По често възниква мъртва хватка при ресурси от втория тип.Причините за възникване на мъртва хватка при работа с ресурсите ще бъдат изложени със следния пример.Предполага се, че процес заявява ресурс преди да го използва.Ако ресурсът не свободен, процесът се блокира.Или процесът се ръководи по схемата:заяви ресурс, използвай ресурс, освободи ресурс.Нека два процеса А и Б да споделят два ресурса p1 и p2.Всеки един от тях е заявил и е получил по един ресурс, след което е заявил и чака за следващ ресурс, но не освобождава своя (фиг. 4.1а), т. е. възниква мъртва хватка.

Процес А Процес Б

p1 p2

p2 p1

Примерът може да се онагледи чрез пространството на възможните ходове(фиг. 4.1б). Пътят на изпълнението (начупената линия) показва относителното напредване на хода на процесите (пречупването отразява превключването на контекста). Защрихованите с наклонени черти области са забранени зони, показващи, че съответните ресурси не могат да бъдат разпределени и на двата процеса. С вертикални черти е означена опасната зона - когато в нея навлезе пътят на изпълнение, неминуемо се достига до мъртва хватка в т.В. Пунктираните линии делят пространството на правоъгълници, всеки от която определя състояние на системата, в което тя може да изпадне.

4.2. УСЛОВИЯ ЗА ВЪЗНИКВАНЕ НА МЪРТВА ХВАТКА

Необходимите условия, които трябва да се изпълняват едновременно, за да настъпи мъртва хватка;

1. Взаимно изключване. Процесите заявяват монополно управление на ресурсите, които им се отделят, т. е. ресурсът може да се използва само за един процес в даден момент

2. Очакване на ресурси. Процесите държат вече отделените им ресурси и в същото време очакват да получат допълнителни ресурси.

3. Не преразпределение. Ресурси не могат да бъдат отнети те се освобождават само от процеса, който ги притежава, след като той изпълни задачата си.

4. Кръгово (циклично очакване). Съществува кръгова верига от процеси, всеки от който чака за ресурс (ресурси), държащ се от предшестващия го.

4.3.ГРАФ ЗА РАЗПРЕДЕЛЕНИЕ НА РЕСУРСИТЕ

Мъртвите хватки могат да бъдат описани по-прецизно в термините на ориентиран граф, наречен граф на разпределение на системните ресурси. Множеството върхове съдържа всички процеси и всички ресурси в системата. Всеки процес се представя в квадрат, а всеки тип ресурс с кръг.Броят на единиците на всеки тип ресурс се отбелязва с точки в кръга.Всяко ребро може да бъде ориентирано от процес към ресурс, означаващо че процес е заявл елемент на ресурс и чака да го получи.Обратно ако реброто е насочено от ресурс към процес,то ресурсът е разпределен на процеса. Ребрата се наричат съответно заявяващо и присвояващо.Заявяващо ребро се включва в графа, когато процес заяви елемент на ресурс.Когато заявката се изпълни, по незабавно се трансформира в присвояващо ребро.Когато процеса освободи ресурс(елемент на ресурс), присвояващото ребро се унищожава.На фиг. Е показана система,изпаднала в безизходна ситуация, тъй като съществува цикъл:

А Р2 Б Р1 А

Ако типът ресурси съдържа няколко идентични единици, тогава цикълът не води непременно до мъртва хватка.Тук цикълът е необходимо, но не достатъчно условие за съществуване на мъртва хватка.

P1

P2

Графите динамично се менят в зависимост от това как процесите завяват, получават и връщат след време ресурси на ОС.Когато в графа няма цикъл, тогава системата не е в състояние на мъртва хватка.Ако има цикъл, системата може да бъде или да не бъде в състояние на мъртва хватка.

4.4.СРАТЕГИИ ЗА БОРБА С МЪРТВАТА ХВАТКА

Съществуват три групи методи за борба с мъртвата хватка.Стратегията на предпазване от мъртва хватка изключва възникването на мъртва хватка, макар и с цената на допълнителни ресурси.Стратегията на избягването гарантира,че макар да е възможна мъртва хватка тя не възниква за конкретна група процеси и заявки, изпълнявани в даден момент.Стратегията на разпознаването на мъртвите хватки и след това възстановяване на системата се базира на извод,че мъртви хватки възникват рядко и, че по- скъпо е да се предотвратява или да се избягва възможността за появяването им, отколкото да се разпознаят и да се извърши възстановяване.

4.1.1.ПРДПАЗВАНЕ

Първото условие са взаимно изключване, осигуряващо на процесите право на монополно управление на разпределените им ресурси не е удачно да се нарушава, тъй като в системата трябва да се работи и със закрепени ресурси(магнитни ленти и др.) или с общи променливи в критични секции.За да се наруши второто условие за очакване на допълнителни ресурси, всеки процес трябва да заяви всички необходими ресурси на веднъж, като при това не може да започне да се изпълнява, докато те не му бъдат предоставени.една възможност за реализация на принципа е процесът да получи всички ресурси,преди да започне да се изпълнява.Алтернативно процесът може да заявява ресурси само тогава когато няма никакви ресурси.Този подход има два недостатъка.Първият е,че се снижава ефективността на използване на ресурсите, тъй като много от тях могат да бъдат разпределени но неизползвани дълго време.Вторият недостатък е,че е възможно безкрайно отлагане.Процеси които чакат популярни ресурси, могат да чакат неопределено дълго, докато поне един от тези ресурси се държи от друг процес.За да се наруши третото условие, предвиждащо непреразпределяемост на ресурсите, може да се направи следното.Процесът, притежаващ някакви ресурси и получил отказ на заявката за разпределените на допълнителни ресурси, е длъжен да освободи своите ресурси и при необходимост да ги заяви заедно с допълнителните точки.Недостатък на метода е, че е възможно с освобождаването на ресурс да се загуби работата извършена до този момент.Възможен е и модифициран вариант на тази стратегия.Когато процес заяви допълнителни ресурси и те не са на разположение проверява се те дали не се държат от друг процес чакащ за ресурси.Ако да, те се отнемат от чакащия процес и се дават на заявяващия процес.Ако ресурсите не са свободни или не се държат от чакащ процес, заявяващия процес трябва да чака.При това той освобождава ресурси само, ако друг процес ги заяви.Изключване на условието за кръгово очакване може да се постигне по следният на начин.Линейно се подреждат всички типове ресурси,като им се предписват уникални номера.Процесите са длъжни да заявяват ресурси в реда на нарастване на номерата,т.е. ресурсите се разпределят йерархично.Процес получил ресурс на едно ниво, може да заяви ресурс само от по - високо ниво.Той може да освободи ресурс на дадено ниво, само след освобождаване на ресурсите от по горните нива.този метод има също недостатъци.Загуба на ефективност може да има, ако на процес са необходими ресурси в ред отличаващ се от този в йерархията.Тогава той ще получава и държи ресурси, дълго преди да ги използва.Друг проблем е,че се усложнява писането на програми.

4.4.2.ИЗБЯГВАНЕ НА МЪРТВА ХВАТКА

Ако системата е в безопасно(сигурно ) състояние, съществува поне един път на изпълнение на процесите, който позволява да се обходи опасното(несигурното ) състояние. Следователно, достатъчно е да се провери не довежда ли отделянето на ресурса в опасно състояние.Ако да заявката се отклонява.В противен случай тя се изпълнява.Тази проверка изисква анализ на последователността от заявки на процесите.Често пъти последователността от заявки не известна предварително.Обаче ако е известна общата заявка за всеки тип ресурси(т.е. всеки процес трябва да декларира необходим максимален брой ресурси от всеки тип), разпределението може да се контролира.Класическото решение е известно като алгоритъм на банкера. Банкерът иска да раздели определен капитал(в една валута) от абстрактни парични между определен брой клиенти.всеки клиент оказва максималната сума. Обикновено капитала на банкера е по малък от колкото сумарните нужди на клиентите, тъй като банкерът предполага,че всички няма да вземат максималният заем.По време на транзакцията клиентът може да получава(или да връща) последователно по една p-единица капитал и няма гаранция,че ще върне част от заема, докато получи целя заем.Понякога клиента може да чака за следваща единица, при което банкера гарантира, че времето за чакане е крайно.Текущия заем не може да превишава максималната нужда на клиента.Ако банкера е способен да осигури максималният заем на клиента, клиента гарантира, че ще завърши транзакцията си и ще върне заема в краен интервал от време. Състоянието е безопасно ако банкерът може да осигури на своите клиенти довършването на всички техни транзакции в крайно време.В противен случай състоянието е опасно.

Алгоритъмът на банкера:

Procedure Банкер(капитал:integer; заявен заем, получен заем:array[1..N] of integer;

var състояние:boolean )

var I:integer;

може да завърши:array[1..N] of boolean;

продължи:boolean;

begin

{ оценка на текущото състояние на банкера и клиентите}

наличност:=капитал;{начален капитал на банкера}

for I:=1 to N do{за всички N клиенти }

begin

наличност:=наличност получен заем[I];

може да завърши[I]:=false;{не е известно дали ще завърши транзакцията}

остатък[I]:=заявен заем[I] получен заем[I];

end;

продължи:=true;

while продължи do{симулация на довършването на транзакциите}

begin

продължи:=false;

for I:=1 to N do

begin{проверка на възможност за завършване на транзакциите на всеки клиент}

if (not) може да завърши[I](and (остатък[I]<=наличност))

then{може да завърши ако получи остатъка}

begin

може да завърши[I]:=true;

{симулира се връщането на заема}

наличност:=наличност+получен заем[I];

продължи:=true;

end;

end;

end;

{всички транзакции са довършени или повече транзакции не могат да бъдат завършени}

if наличност:=капитал then състояние:=true{безопастно}

else състояние:=false;{опасно}

end.

4.4.3.ОТКРИВАНЕ НА МЪРТВИ ХВАТКИ

Откриването на мъртви хватки се състои в установяване на факта и определяне на процесите и ресурсите въвлечени в ситуацията(списък на ресурсите,чакани от всеки блокиран процес и списък на процесите държащи всеки недостъпен ресурс).тези алгоритми се използват в системи, в които се изпълняват първите 3 условия.След това те определят не съществували кръгово очакване.Алгоритмите са свързани с допълнителни разходи, затова често се приемат компромисни решения. Те могат да се изпълняват с различна честота- например един път на час или при отклоняване на заявката.Ако безизходни ситуации настъпват много рядко, тяхното разпознаване се възлага на оператора.Така стават излишни управляващите програми за предпазване, избягване или откриване на мъртви хватки. Възможно е оператора да не забележи веднага настъпилата ситуация, особено ако някой процеси работят.Загубите се състоят в задържане на процесите и понижаване на възможностите на системата ,но това може да е приемлива цена.Особено голямо значение имат мъртвите хватки в някои системи за реално време тъй като последиците могат да са катастрофални.

МЕТОДИ ЗА ОТКРИВАНЕ НА МЪРТВИТЕ ХВАТКИ

Съществуват различни алгоритми за откриване на мъртви хватки. Някои от тях прилагат т.нар.редукция на графите-това позволява да се определят процесите, който могат да завършат,и които остават в безизходна ситуация.Друг подобен подход е описан за случаите, когато се използват единични ресурси(всеки тип има един елемент).Отново се използува вариант на графа за разпределение на ресурси, наречен wait-for.Той се получава от началният граф чрез отстраняване на възлите на ресурсите и прекарване на съответните ребра.По точно, ако ребро е насочено от процес А към Б това означава в резултатният граф, че А чака Б да освободи ресурсите, които му трябват.Такова ребро съществува в графа само, ако началният граф съдържа две ребра към един и същ ресурс заявяващо от А и присвояващо към Б.

За да открие мъртва хватка системата трябва да поддържа такъв граф и периодично да стартира алгоритъма за търсене на цикъл, означаващ,че в системата съществува мъртва хватка.Алгоритъма изисква N*N операции при N възела в графа.

4.4.4.ВЪЗСТАНОВЯВАНЕ СЛЕД МЪРТВА ХВАТКА

След като детектиращия алг. Определи,че съществува мъртва хватка възможни са няколко алтернативи.Най-просто е да се информира оператора който ръчно да се заеме с мъртвата хватка.Другият начин е системата да извърши възстановяването автоматично.Тук са възможни две направления-унищожават се един или повече процеси, за да прекъсне цикъла,или се отнемат ресурси от един или повече взаимно блокирани процеси.

ТЕРМИНИРАНЕ НА ПРОЦЕСИ

За да се отстрани мъртвата хватка чрез унищожаване на процеса може да се постъпи по следните начини:

1. Принудително завършване на всички процеси и стартиране на ОС.

2. Принудително завършване на всички процеси, намиращи се в мъртва хватка.

3. Принудително завършване на намиращите се в мъртва хватка процеси,но по един,и след всяко терминиране се извиква алг. за детекция.

ПРЕРАЗПРЕДЕЛЕНИЕ НА РЕСУРСИТЕ

Трябва да се отговори на следните 3 въпроса:

1. Кои ресурси и кои процеси трябва да бъдат избрани за преразпределение т.е. коя е жертвата?

Изборът зависи от стойността на усилието.Могат да се вземат предвид броят на ресурсите и времето за изпълнение, което е консумирал блокирания процес.

2. Какво трябва да се направи с процес, след като се отнемат ресурсите му?Тъй като няма ресурси той не може да продължи.Затова трябва да бъде върнат в някакво безопасно състояние и да се рестартира от там.Но проблемът е как да се определи състоянието и колко лесно е това.Най-просто е процеса да се изхвърли и да се рестартира.Но много по ефективно е да се върне само толкова колкото е необходимо за да се излезе от мъртвата хватка.Това означава,че системата трябва да пази повече информация за състоянието на процесите.

3. Какво трябва да се направи, за да не възникне безкрайно отлагане, т.е. как да се гарантира,че ресурси няма да се отнемат от един и същ процес.

4.5.ПРОБЛЕМА НА БЕЗКРАЙНОТО ОТЛАГАНЕ

Система, където процесите трябва да чакат,докато ОС взема решение по разпределението на ресурсите и планирането, възможно е да настъпи ситуация, при която изпълнението на процес се отлага неопределено дълго време.Тази ситуация която се нарича безкрайно отлагане, също може да доведе до неприятни последици подобна на мъртва хватка. Например такъв проблем ще възникне, когато изборът на жертвата, от която трябва да се отнемат ресурсите, се прави въз основа на ценови фактори, резултат на което може да се случи да бъде издиран един и същи процес.За да се избегне това, в ценовия фактор може да се включи броят на изхвърлянията. Когато в ОС ресурсите се разпределят по приоритетен принцип, същото явление ще настъпи с постоянното идване на

по- високо приоритетни процеси.В някои системи се използва стареене на процесите т.е с течение на времето техния приоритет се увеличава. Изобщо в ОС трябва да се има в предвид не само ефективно , но и справедливо управление на ресурсите.

4.6.МЪРТВА ХВАТКА ПРИ КОМУНИКАЦИЯ

Съобщенията могат да бъдат разглеждани като потребими ресурси. При комуникацията чрез съобщения също може да настъпи мъртва хватка.Примера показва как процесите си разменят съобщения чрез пощенски кутии.

Процесът А изпраща съобщение към процеса Б и чака отговор. Б използва от В за организиране на отговори му изпраща съобщение. В обаче иска да използва А за отговор в резултат на което са получава затворен цикъл и се появява мъртва хватка. За да се избегне мъртвата хватка комуникацията трябва да отговаря на определени правила. Един от подходите е йерархичната комуникация, при която процесите се разделят на класове. В тази йерархия процесите от ниските нива (главните процеси) могат да изпращат съобщения на по-високите (подчинените процеси), които трябва в крайно време да изпратят отговор. Съобщенията се изпращат само в една посока, а отговорите в обратната посока. За да бъда предпазена йерархичната система от мъртва хватка важи основното правило: не трябва да се прави опит за изпращане на съобщения ( или отговор) без някой да го приеме в крайно време, както и не трябва да се прави опит за приемане на съобщение или отговор без някой наистина да го е изпратил.