Шта је застој у оперативном систему: услови и алгоритам откривања

Испробајте Наш Инструмент За Елиминисање Проблема





Главни циљ оперативног система је да обезбеди одговарајућу комуникацију између хардверских и софтверских ресурса, а такође пружа заједничке услуге програмима. Када процес оперативног система жели да приступи било којем ресурсу, прво шаље захтев одређеном ресурсу којем жели да приступи, затим користи ресурс и на крају га ослобађа након употребе. Претпоставимо да многи процеси покушавају да приступе једном ресурсу истовремено, постаје тешко обезбедити један ресурс свим процесима истовремено, у таквој ситуацији настаје концепт назван застој. Отуда овај чланак описује како настаје застој и како се превазилази ова ситуација.

Шта је ћорсокак у оперативном систему?

Дефиниција: Деад-Лоцк је ситуација када два или више процесора чекају да се неки догађај деси, али такви догађаји који се не догоде су стање мртве тачке, а за процесоре се каже да су у мртвом стању. На пример, претпоставимо сценарио у стварном времену, где се налазе два аутомобила А и Б, која два једнострука возача возе једносмерним путем. Сада се јавља ситуација када возач аутомобила А каже да је кретање према северу исправан смер, док возач аутомобила Б каже да је кретање према смеру према југу тачан. Али ниједно се не помера уназад да би дозволило да се други аутомобил креће напред, ово стање се назива мртвом тачком.




Пример аутомобила

ауто-пример

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



Пример процесора

процесор-пример

Деад-Лоцк услови

Следе четири важна услова застоја који настају ако се сви услови јављају истовремено, постоје одређене шансе да се застој догоди.

Узајамно искључивање

Значи да се било који ресурс који користимо мора користити на међусобно искључив начин. Тамо где само један процес истовремено користи само један ресурс. На пример, поступак штампања траје и одједном други поступак покушава да прекине поступак штампања. Дакле, овде у ситуацији узајамног искључивања, тек након што је задатак штампања завршен, обрађује се само следећи задатак. Узајамно искључивање може се елиминисати истовременим дељењем ресурса, што практично није могуће.

Узајамно искључивање

узајамно искључивање

Нема прече куповине

Према превентивни засновани на алгоритмима, ако постоји приоритетни задатак који покушава да прекине тренутни задатак. Превентивни алгоритам садржи тренутни задатак, прво извршава приоритетни задатак и враћа се свом првом задатку. Ситуација објашњена према горе наведеном примеру када процес држи ресурс све док се извршава, то јест П1 може ослободити Р1 тек након извршења, слично П2 ослободити Р2 само након извршења. Ако не дође до прече куповине, може доћи до застоја.


Пример без преузимања

не-преемп-пример

Чекај и чекај

Процес задржава неке ресурсе и чека додатне ресурсе, али ти ресурси се прибављају неким другим процесом. Из горњег примера, П1 држи Р1 и чека Р2, где Р2 преузима Р2, а П2 држи Р2 и чека Р1, где Р1 преузима П1, у систему може доћи до застоја и стања чекања.

Пример чекања и чекања

пример чекања и чекања

Кружно чекање

За скуп процеса се каже да је у застоју ако један процес чека ресурс који је додељен другом процесу, а тај процес чека ресурс, слично је горе објашњеном примеру где је у облику петље. Тамо где П1 чека Р2 и Р2 је додељен за П2, а П2 чека Р1 и Р1 додељен за П1, што је кружни облик чекања ако овај услов задовољава застој.

Пример кружног чекања

пример кружног чекања

Алгоритам откривања мртвих блокада

Случајеви када алоцирамо ресурсе на процесе и оперативни систем поново проверава да ли је дошло до застоја у систему или га нема помоћу два главна алгоритма за откривање застоја, они су

  • Појединачна инстанца
  • Више инстанци типа ресурса

Сингле Инстанце

Једна инстанца је ситуација када систем има појединачне инстанце свих ресурса. Такође је познат као алгоритам за чекање графа или граф за алокацију ресурса. Графикон расподјеле ресурса састоји се од скупа процеса и скупа ресурса који су представљени као два различита врха. Ресурси у графикону алокације ресурса су измењени и представљени су као облик чекања на графикон. Тамо где облик чекања графикона има само процесе који су представљени као врхови као што је приказано доле, при чему,

  • Графикон расподјеле ресурса: Процеси П1, П2, П3 и ресурси Р1, Р2, Р3 представљени су на графикону расподјеле ресурса.
  • Сачекајте графикон: У процесу чекања на графикон помињу се само процеси П1, П2, П3.
  • Ако постоји услов циклуса, то значи да ако постоји континуирани ток процеса у једном правцу, то значи да ће стање циклуса изаћи и сачекати да се граф заустави.

Пример 1: Пример у наставку показује да нема стања мртве тачке јер нема континуираног протока који се примећује у ишчекивању графикона.

Пример појединачне инстанце1

појединачни пример1

Пример 2: Дошло је до застоја јер постоји непрекидни проток циклуса од П1 до П4.

Једна инстанца - пример2

појединачни пример2

Ако се застој врло често јавља у систему, алгоритам откривања се често користи. Ако се алгоритам за откривање више користи, биће више трошкова и више времена за рачунање. Стога да бисмо то превазишли, позивамо се на алгоритам након што, дајући једнако време, на овај начин се тежина графикона користи за откривање мртве тачке.

Више инстанци врсте ресурса

Више инстанци типа ресурса је ситуација када систем има више инстанци свих ресурса, познат је и под називом Банкарски алгоритам. Према алгоритму Банкари, чим процес добије све потребне ресурсе, тада ослобађа своје ресурсе.

Размотримо следећи пример, претпоставимо да постоје 3 процеса П0, П1, П2 и тип ресурса А, Б, Ц где А може бити Процесори , Б може бити штампач, а Ц може бити тастатура. Знаменке „0“ у колони представљају доступност ресурса.

Случај (и): Претпоставимо да ако узмемо да је услов услов „000“ који је присутан у П0 и П2, требало би да проверимо који је захтев испуњен, процеси П0 ослобађају процесе након додељивања, а затим се следећи П2 процеси издају након додељивања. Овако, у низу, један по један процес ослобађа П0, П2, П3, П1, П4 у низу. На крају, добијамо доступне ресурсе као П7, П2, П6. Доступни редослед је услов када нема застоја.

Банкари-Алгоритам-Пример1

банкари-алгоритам-пример1

Куће (ии): Претпоставимо да ако је П2 001 уместо 000, сада примените банкарски алгоритам да бисте проверили стање мртве тачке, где се једини П0 извршава међу свих 5 процеса. Отуда су П1, П2, П3, П4 у стању застоја, осим за П0.

Банкари-Пример2

банкари-пример2

Примене мртве тачке

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

Предности

Предности мртве тачке су

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

Мане

Недостатак мртве тачке је

  • Ресурс који се користи мора бити познат унапред
  • Блокада процеса дуго времена
  • Предкупни губици се наслеђују.

Овај чланак даје преглед начина на који долази до застоја када постоје два или више процеса и три стања која су узрок настанка застоја, као и две врсте алгоритама, наиме алгоритам за поделу ресурса који открива да постоји стање ћорсокака и алгоритам банкара који је алгоритам за избегавање мртвих тачака. Ево питања „Шта ће се догодити ако се застој занемари?“.