Застој

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

Оба процеса морају имати изворе да би наставили са извршењем. П1 захтева додатан извор Р1 и поседује Р2, П2 захтеба додатан извор Р2 и поседује Р1; ниједан процес не може наставити са изршењем .

У трансакција базе података, застој се дешава када када два процеса током својих трансакција ажурирају  два реда информација али у обрнутом смеру. На пример, процес А ажурира ред 1 па ред 2 у исто време док процес Б ажурира ред 2 па ред 1. Процес А не може да заврши ажурирање реда 2 док се процес Б не заврши, али процес Б не може да заврши ажурирање реда 1 док процес А није завршен. Без обзира колико је времена дозвољено за пролазак, ова ситуација се никада неће завршити сама од себе и због тога, база података ће убити трансакцију процеса који је урадио најмање посла  .

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

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

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

Примери

Било који застој се може упоредити са класичним "кокошка или јаје" проблемом.. Такође се може сматрати и парадоксалном "Ухвати-22" ситуацијом.. Прави светски пример би био нелогично усвојен статут законодавства Канзас у ранијим 20-тим, који каже :

Једноставан рачунарски пример је следећи. Претпоставимо да рачунар има три CD дискова и три процеса. Сваки од три процеса садржи један диск. Ако би сваки процес сада захтевао други диск, три процеса би била у застоју. Сваки процес би чекао да CD диск буде слободан, што се може једино десити од стране другог процеса који чека. Стога, ово резултира кружном ланцу.

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

Неопходни услови

Ситуација застоја може се постићи ако се сви следећи услови налазе истворемено у систему :

1. Мутекс: барем један ресурс мора бити задржан у не дељивом моду. Само један процес може користити ресурс у било ком временском интервалу.
2. Држи и чекај или задржавање ресурса: процес тренутно задржава барем један ресурс и захтева додатне ресурсе који су задржани од стране других процеса.
3. Без присвајање: ресурс може бити ослобођен само добровољно од стране процеса који га задржава.
4. Кружно чекање: процес мора да чека ресурс који је заджан од стране другог процеса, који чека да први процес отпусти ресурс. Углавном, ту је скуп процеса који чекају, П={П1, П2,..., Пн} , такав да П1 чека ресурс задржан од стране П2, П2 чека ресурс задржан од стране П3 и тако све до Пн који чека ресурс задржан од стране П1

Ова четири услова су познати као Кофманови услови из њиховог првог описа из 1971 у чланку Едварда Г. Кофмана, Јр. . Неиспуњеност било ког услова је довољоно да спречи застој да се деси.

Избегавање застоја базе података

Добар начин да се избегне застој базе података је тај да се пропрати Ораклов Водич за Преживљавање Застоја :

Овој реченици је потребно објашњење:

• Прво, то указује на чињеницу да процеси морају бити унутар трансакције да би се застоји догодили. Имати на уму да неки системи базе података могу бити конфигурисани да степеничасто бришу, који стварају имплицитне трансакције које онда могу узроковати застој. Такођ, неки ДБМС произвођачи нуде закључавање реда нивоа,  тип рекордно закључавање који доста смањује шансе за застојем, супротно страница-ниво закључавања, који има могућност да закључа много више процеса.
• Друго, позивање на "више извора" значи "више од једног реда у једној или више табела" . Пример закључавања истог редоследа може укључивати обраду сви INSERTS прво, свих UPDATES друго, и свих DELETES на крају; у обради сваког од њих све родитељске табеле се мењају пре него што се промене дечије табеле; и обрада табеле се мења у истом смеру (као на пример по алфабету, или поређано по ИД или броју профила)  .
• Треће, елиминацију свих ризика од застоја је тешко постигнути када ДБМС има аутоматске закључавање-ескалација карактеристике које подижу браве ред-ниво у страницу закључавања која може да ескалира до табеле закључавања. Иако ризик или шанса доживљавања застоја неће отићи до нуле јер се застоји дешавају више  на великим, великог обима, комплексним системима, може бити доста смањен, и - када је потребно- програмери могу побољшати софтвер да поврате трансакције када систем детектује застој.
• Четврто, застоји могу довести до губитка података ако програмери не напишу софтвер специјализован да одређује употребу трансакције приликом сваке интеракција са ДБМС;  овакав губитак података је тешко пронаћи и може проузроковати неочекиване грешке и проблеме

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

Руковање застојем

Већина оперативних система не може избећи застој да се догоди.Када се застој догоди, различити оперативни системи различито реагују на њих у различитим не-стандардним начинима. Већина приступа раде тако да спрече један од четири Кофманова услова да се догоде, посебно четврти . Главни приступи следе.

Игнорисање застоја

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

Откривање

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

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

Након што је застој пронађен, може бити преправљен користећи једну од следећих метода::

1. Процес терминације: један или више процеса укључених у застој могу бити прекинути. Можемо да изаберемо да прекинемо све процесе укључене у застој. Овиме се осигурава да је застој решен са сигурношћу и брзо. Али је цена висока јер ће парцијални прорачуни бити изгубљени. Или, можемо изабрати да прекинемо један процес у време док се не реши застој. Овај приступ има високе трошкове зато што после сваког прекида алгоритам мора да одлучи да ли је систем идаље у застоју. Некило фактора морају се узети у обзир док се бира начин за терминацију, као што су приоритет и старост процеса.
2. Присвајање ресурса: средства издвојена за различите  процесе могу бити успешно присвојена и додељена другим процесима док застој није сломљен.

Превенција

Превенција застоја ради тако што предвиђа један од четири Кофманова стања да не започну.

• Уклањање стања међусобног искључивања значи да ниједан процес неће имати приступ ресурсу. Ово доказује да ресурси не могу бити спооловани. Али чак и са споолованим ресурсима, застој може идаље да се догоди. Алгоритми који избегавају међусобно искључивање називају се алгоритми неблокирајуће синхронизације.
• Задржи и чекај или задржавање ресурса услови могу бити уклоњени захтевањем процеса да затражи све ресурсе који су му потребни пре почетка (или пре него што крене одређени скуп операција). Ова напредно знање је тешко задовољити и, у било ком случају, представља неефикасно коришћење ресурса. Други начин је да се затражи процес да захтева ресурсе само онда када нема ништа. Дакле, морају прво да ослободе све њихове тренутне задржане ресурсе пре него што захтева све ресурсе који им требају за од нуле. Ово је често непрактично. То је тако зато што ресурси могу бити додељени и могу да остану некоришћени дужи временски период. Такође, процес који захтева популаран ресурс можда мора да чека до бесконачности, због тога што ресурс може увек бити додељен неком процесу, што доводи до "глади" ресурса. (Ови алгоритми, као што је сериализовање токена, познати као сви - или - ниједни алгоритми).
• Стање неприсвајања може такође бити тешко или немогуће избећи пошто процес мора бити у могућности да поседује ресурс одређени временски период, или исход процеса може бити недоследан или се може јавити "млаћење". Иначе, немогућност да се спроведе присвајање може ометати прироритет алгоритма. Присвајање "потпуно затвореног" ресурса углавном подразумева враћање, и треба га избегавати, јер је прескупо. Алгоритми који дозвољавају присвајање укључују закључај-бесплатно и чекај-бесплатно алгоритме и оптимистичну контролу конкуренције. Ако процес задржава неке ресурсе и захтеве за неки други ресурс који не могу одмах бити додељени, стање може бити одстрањено тако што се отпусте сви тренутно задржани ресурси тог процеса .
• • Последњи услов је кружно чекање. Приступи који избегавају кружна чекања укључују онемогућавање прекида током критичних деоница и користе хијерархију за одређивање делимичног редоследа ресурса. Ако не постоји очигледна хијерархија, чак се и меморија адресе ресурса користи за одређивање редоследа и од ресурса се захтева да повећају редослед пописивања. Дијкстра решење се такође може користити.

Избегавање

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

•  ресурсе који су тренутно доступни; 
•  ресурсе који су тренутно додељени сваком процесу;
•  ресуре који ће бити тражени и ослобођени од стране ових процеса у будућности. 

Могуће је да процес буде у несигурном стању али да не доведе до застоја. Појам сигурног/несигурног стања се односи само на способност система да уђе у стање застоја или не. На пример, ако процес захтева А који би довео до несигурног стања, али ослободи Б који би спречио кружно чекање, онда је стање несигурно али систем није у застоју . 

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

Два остала алгоритма су Чекај/Умри и Повреди/Чекај, сваки користи технику симетричног прекида. У оба алгоритма постоји старији процес (О) и млађи процес (Y). Старост процеса се може одредити временским маркером приликом стварања процеса. Мањи временски маркери су старији процеси, док већи временски маркери представљају млађе процесе. 

Чекај/Умри	Рани/Чекај
O треба ресурс држан од  Y	O чека	Y умире
Y треба ресурс држан од O	Y умире	Y чека

Још један начин да се избегне застој је да се избегне блокирање, на пример коришћењем неблокирајуће синхронизације или читај-копирај-ажурирај.

Жива блокада

Жива блокада је слична застоја, само што изјаве процеса укључених у живу блокаду се константно мењају један у односу на другог, нико не напредује. Овај термин је дефиницан званично током 1970-их —раније виђен у објављеној литератури у Бабич артиклу 1979 о тачности програма. Жива блокада је специјалан случај изгладњивања ресурса; општа дефиниција само наводи да се специјалан процес не дешава.

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

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

Расподељен застој

Расподељен застој се може јавити у расподељеном израчунавању када се расподељене трансакције или контрола конкуренције користе. Расподељени застоји могу бити детектовани или прављењем глобалног чекај-for графа или из локалног чекај-for графа у детектору застоја или преко расподељеног застоја као јурњава ивице. 

Фантомски застоји су застоји који су лажно детектовани у дистрибутивном систему током унутрашњих кашњена система али они у ствари не постоје. На пример, ако процес отпусти ресурс Р1 и издаје захтев за Р2, и прва порука је изгубљена или одложена, кординатор (детектор застоја) може лажно закључити застој(ако захтев за Р2 док је ту Р1 би проузроковао застој).

Литература

• (PDF) http://www.cs.ucl.ac.uk/staff/w.emmerich/publications/ESEC01/ModelChecking/esec.pdf.  Kaveh, Nima; Emmerich, Wolfgang. "Deadlock Detection in Distributed Object Systems" (PDF). London: University College London.
• Bensalem, Saddek; Fernandez, Jean-Claude; Havelund, Klaus; Mounier, Laurent (2006). „Confirmation of deadlock potentials detected by runtime analysis”. Proceedings of the 2006 workshop on Parallel and distributed systems: Testing and debugging. стр. 41—50. ISBN 978-1-59593-414-7. S2CID 2544690. doi:10.1145/1147403.1147412. 
• Coffman, E. G.; Elphick, M.; Shoshani, A. (1971). „System Deadlocks”. ACM Computing Surveys. 3 (2): 67—78. S2CID 15975305. doi:10.1145/356586.356588. 
• Mogul, Jeffrey C.; Ramakrishnan, K. K. (1997). „Eliminating receive livelock in an interrupt-driven kernel”. ACM Transactions on Computer Systems. 15 (3): 217—252. S2CID 215749380. doi:10.1145/263326.263335. 
• Havender, J. W. (1968). „Avoiding deadlock in multitasking systems”. IBM Systems Journal. 7 (2): 74—84. doi:10.1147/sj.72.0074. 
• Holliday, JoAnne L.; El Abbadi, Amr. „Distributed Deadlock Detection”. Архивирано из оригинала 2015-11-02. г. 
• Knapp, Edgar (1987). „Deadlock detection in distributed databases”. ACM Computing Surveys. 19 (4): 303—328. S2CID 2353246. doi:10.1145/45075.46163. 
• Yibei Ling; Shigang Chen; Cho-Yu Jason Chiang (2006). „On Optimal Deadlock Detection Scheduling”. IEEE Transactions on Computers. 55 (9): 1178—1187. S2CID 7813284. doi:10.1109/tc.2006.151. 

Спољашње везе

• "Advanced Synchronization in Java Threads" by Scott Oaks and Henry Wong
• Deadlock Detection Agents
• DeadLock at the Portland Pattern Repository
• Etymology of "Deadlock"