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

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

У оперативном систему , засто? ?е ситуаци?а ко?а наста?е када процес или нит  у?у у ста?е чека?а, ?ер ?е тражени ресурс задржан од стране другог процеса ко?и чека, ко?и тако?е чека други ресурс ко?и ?е задржан од стране другог процеса ко?и чека. Ако процес не може да промени ?егово ста?е бесконачности ?ер ?е ресурс се ресурс ко?и се тражи ве? користини од стране другог процеса ко?и чека, онда се каже да ?е систем у засто?у . ^[1]

Засто? ?е чест проблем у системима са више процеса , Паралелна обрада и  у расподе?еном израчунава?у , где се софтверске и хардверске браве користе да контролишу поде?ене ресурсе и да спроведу синхронизаци?у процеса . ^[2]

У системима телекомуникаци?е , засто?и се углавном ?ав?а?у током изгуб?ених или оште?ених сигнала уместо ресурса тврд?е . ^[3]

Примери [ уреди | уреди извор ]

Било ко?и засто? се може упоредити са класичним " кокошка или ?а?е " проблемом.. ^[4]  Тако?е се може сматрати и парадоксалном " Ухвати-22 " ситуаци?ом.. ^[5]  Прави светски пример би био нелогично усво?ен статут законодавства Канзас у рани?им 20-тим, ко?и каже : ^{[1] [6]}

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

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

Неопходни услови [ уреди | уреди извор ]

Ситуаци?а засто?а може се пости?и ако се сви следе?и услови налазе истворемено у систему : ^[1]

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

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

Избегава?е засто?а базе података [ уреди | уреди извор ]

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

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

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

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

Рукова?е засто?ем [ уреди | уреди извор ]

Ве?ина оперативних система не може избе?и засто? да се догоди. ^[1] Када се засто? догоди, различити оперативни системи различито реагу?у на ?их у различитим не-стандардним начинима. Ве?ина приступа раде тако да спрече ?едан од четири Кофманова услова да се догоде, посебно четврти . ^[8]  Главни приступи следе.

Игнориса?е засто?а [ уреди | уреди извор ]

У овом проиступу, претпостав?а се да се засто? никада не?е десити. Ово ?е тако?е апликаци?а Но?евог алгоритма . ^{[8] [9]}  Ова? приступ ?е првобитно кориш?ен од стране Миникса и ?уникса . ^[7]  Ово се користи када су временски интервали изме?у извршава?а засто?а велики и када ?е настали губитак података сваки пут поднош?ив 

Открива?е [ уреди | уреди извор ]

У открива?у засто?а, засто?има ?е дозво?ено да се активира?у. Онда се ста?е система испиту?е да детекту?е да се та? засто? догодио и потом он ?е исправ?ен. Алгоритам ?е засполен да прати расподелу ресурса и ста?е процеса, вра?а се назад и рестарту?е ?едан или више процеса у ци?у да избрише детектован засто?. Открива?е засто?а ко?и се ве? догодио ?е лако пошто ресурсе ко?и ?е сваки процес зак?учао и тренутно тражио ?е познат планеру ресура оперативног система. ^[9]

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

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

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

Превенци?а [ уреди | уреди извор ]

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

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

Избегава?е [ уреди | уреди извор ]

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

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

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

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

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

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

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

Жива блокада [ уреди | уреди извор ]

Жива блокада ?е слична засто?а, само што из?аве процеса ук?учених у живу блокаду се константно ме?а?у ?едан у односу на другог, нико не напреду?е. Ова? термин ?е дефиницан званично током 1970-их ?рани?е ви?ен у об?ав?ено? литератури у Бабич артиклу 1979 о тачности програма. Жива блокада ?е специ?алан случа? изглад?ива?а ресурса ; општа дефиници?а само наводи да се специ?алан процес не дешава. ^[10]

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

Жива блокада ?е ризична са неким алгоритмима ко?и детекту?е и ожив?ава из засто?а. Ако више од ?едног процеса ради, алгоритам детекци?е засто?а се може активирати више пута. Ово се може избе?и тако што се осигура да само ?едан процес (изабран произво?но или по услову) ступи у акци?у. ^[11]

Расподе?ен засто? [ уреди | уреди извор ]

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

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

Референце [ уреди | уреди извор ]

Литература [ уреди | уреди извор ]

Спо?аш?е везе [ уреди | уреди извор ]

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