Викигимназијалац:Оперативни системи/Детекција заглављивања

Детекција заглављивања је концепт који допушта да до заглављивања дође, па се тек онда примењују мере да се таква ситуација отклони.Откривање да је до заглављивања дошло може да буде активно и пасивно. Активно откривање је приступ у коме се коришдењем алгоритама проверава да ли је до заглављивања дошло.Пасивни приступ подразумева да се провера врши само кад у систему нема активности, или се региструје да нешто није у реду.

ДЕТЕКЦИЈА У СЛУЧАЈУ ДА РЕСУРСИ ИМАЈУ ЈЕДНУ ИНСТАНЦУ

Ако сви ресурси имају само једну инстанцу, примењује се алгоритам за детекцију застоја који користи специјалан граф чекања на ресурсе (wait-for graph). Граф чекањасе конструише од графа додељених. Правила конструкције графа су следећа:

чворови графа су само процеси (нема ресурса) и
стрелице се цртају само између процеса који чекају један другог за ресурсе.

Постојање застоја утврђује се испитивањем постојања кружних токова: ако кружни ток постоји, то је застој. Дакле, алгоритам се периодично позива да испита постојање кружних токова, за шта је потребно н2 операција, при чему је н број стрелица у графу чекања. Стање система се може приказатиграфовима. Чворови оваквих графова супроцеси (цртамо кругове) и ресурси (цртамо правоугаоник).

Гране графова су ознаке да ли неки процес држи ресурс, што се означава стрелицом од ресурса ка процесу. Док стрелица од процеса каресурсу означава да ли неки процес захтева тај ресурс, али га тренутно не држи.

ДЕТЕКЦИЈА У СЛУЧАЈУ ДА РЕСУРС ИМА ВИШЕ ИНСТАНЦИ

Алгоритам за детекцију помоћу графа чекања није погодан за коришћење уколико ресурси имају више инстанци. У том случају користи се алгоритам сличан банкарском. Најпре ћемо увести следеће структуре података:

Вектор раположивости: available[ј], ј∈[0,м]. Ако је available[ј]=к, тада је к инстанци ресурса Рј распложиво.
Матрица алокације: allocation[н,м]. Ако је allocation[и,ј]=к, тада је процес Пи тренутно добио к инстанци ресурса Рј.
Матрица тренутних захтева request[н,м]. Матрица указује на тренутне захтеве процеса. Ако је request[и,ј]=к, тада процес Пи тренутно тражи к инстанци ресурса Рј.

Алгоритам функционише на следећи начин: Нека су work и finish вектори дужине м и н, респективно:

У овом кораку сви процеси који имају било какве ресурсе се обележавају као незавршени, а у противном испадају из алгоритма work = available for i = 1,2, …, n if allocationi ≠ 0 then finish[i]=0; else finish[i]=1.
У овом кораку налази се процес који може да задовољи све своје потребе и заврши активност, односно процес за који важи: finish[и]=0 (2.б) requesti ≤ work. Ако нема таквих процеса, иди на корак 4.
У овом кораку се ресурси процеса враћају у систем. work = work + allocationi finish[i]=1.Иди на корак 2.

Ако је finish[и]=0, за било које и∈[1,н], тада је систем у стању застоја. Прецизније, ако је finish[и]=0, тада је процес Пи у застоју. Алгоритам захтева м x н2 операција да би установио да ли је систему стању застоја.

Када се примени алгоритам за детекцију, може се доказати да постоји секвенца која доводи до резултата finish[и]=1 за све процесе, што значи да систем неће бити доведен у стање застоја. Интересантно је да систем у тренутку т0 нема расположивих ресурса, али да се почевши од процеса који најмање траже (П0 и П2) може обавити додела ресурса без довођења до застоја. Међутим, довољно је да процес П2 тражи једну инстанцу ресурса Ц и систем ће бити доведен у стање застоја. Доказаћемо то применом претходно описаног алгоритма за детекцију: процес П0 има најмање прохтеве, и ако би завршио своје активности и вратио ресурсе, стање расположивих ресурса би било (0,1,0) након чега немамо процес који може да задовољи своје потребе. Значи систем је у стању застоја - процеси П1, П2, П3, и П4 су заглављени.

КОРИШЋЕЊЕ АЛГОРИТМА ЗА ДЕТЕКЦИЈУ

Учестаност позивања алгоритма за детекцију застоја зависи од тога учестаности појаве застоја и просечног броја процеса захваћеног застојем. Са једне стране, застој се мора детектовати на време јер су сви процеси (а самим тим и ресурси које процеси користе) заглављени, али како детекција конзумира доста времена, алгоритам се не сме позивати често.