Засто?

Во информатиката , засто? или ?ор-сокак ( англиски : deadlock ) е ситуаци?а во ко?а две или пове?е конкурентски акции чекаат прво другата да ?а заврши де?носта, па затоа и никогаш не ?а извршуваат. Во еден оперативен систем, deadlock е ситуаци?а ко?а се ?авува кога еден процес влегува во состо?ба на чека?е поради ресурс ко? од неа бара да се задржи до неко? друг процес во чека?е, ко? пак е на чека?е заради неко? друг ресурс. Ако процесот не е во можност да ?а промени сво?ота состо?ба на неодредено време, биде??и ресурсите бараат од неа да се користи од страна на други процеси во чека?е, тогаш се вели дека системот е во ?ор-сокак. Deadlock-от е вообичаен проблем во мултипроцес системите, паралелното пресметува?е и дистрибуираните системи, каде софтверските и хардверските брави се користат за справува?е со заедничките ресурси и спроведува?е на процесот на синхронизаци?а. Во телекомуникациските системи, по?авува?ето на deadlock-от главно се должи на изгубени или оштетени сигнали како замена на тврде?ето на ресурсите. Примери Deadlock ситуаци?ата може да се спореди со класичното праша?е "Кокошката или ?а?цето". Како аналогичен пример во реалниот свет би било нелогично дека статутот е донесен од законодавното тело Канзас во почетокот на 20 век каде е наведено: "Кога два воза ?е се приближат еден кон друг на премин, два?цата ?е застанат и ниту еден од нив нема да тргне повторно сe додека другиот не замине. "

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

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

Deadlock ситуаци?а може да се по?ави само ако сите од следните услови истовремено се случуваат во системот: 1. Взаемно исклучува?е : На?малку еден ресурс мора да биде несподелив. Само еден процес може да го користи ресурсот во било кое дадено време. 2. Одржи и чека или ресурси холдинг : Процес ко? моментално е допрен од на?малку еден ресурс и бара дополнителни ресурси кои се допрени од страна на други процеси. 3. Не купува?ето пред друг: Оперативниот систем не смее да ги пренамени ресурсите откако тие ?е бидат распределени, тие мора да бидат об?авени доброволно од страна на процес во чека?е. 4. Кружно чека?е : Процесот мора да чека еден ресурс ко? е задржан од друг процес, ко? пак е на чека?е за првиот процес да го ослободи ресурсот. Во принцип, таму има поставено процеси на чека?е, P = {P1, P2, ..., PN}, така што Р1 е во чека?е на еден ресурс задржан од Р2, Р2 е во чека?е на еден ресурс задржан од Р3 и така натаму додека PN чека неко? ресурс задржан од Р1. Овие четири услови се познати како Кофманови услови од нивниот прв опис во 1971 во стати?ата од Едвард Г Кофман, Неисполнува?ето на било ко? од овие услови е доволно да се спречи по?авата на ?ор-сокак.

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

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

Livelock [ уреди | уреди извор ]

Livelock (се чита ла?влок ) е сличен на засто?от, освен дека состо?бата на процесите кои се вклучени во livelock посто?ано се менуваат со поглед еден кон друг, каде нема напредок. Livelock е посебен случа? на гладува?е со ресурси. Општата дефиници?а само наведува дека одреден процес не напредува. Промер за livelock од реалниот свет имаме кога две лица се сретнуваат во тесен ходник, и секо? се обидува да биде ?убезен со поместува?е настрана за да им овозможи на другите да поминат, но тие завршуваат се ниша?е од една страна на друга без да се направи никаков напредок, биде??и тие посто?ано се движат на ист начин во исто време. Livelock е ризик со некои алгоритми кои детектираат и се опоравуваат од застои. Ако пове?е од еден процес е потребен за акци?ата, алгоритамот за открива?е на засто? може неколкупати да се активира. Ова може да се избегне со осигурува?е дека само еден процес (избран по случаен избор или по приоритет) зема акци?а.

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

Дистрибуиран засто? може да се случи во дистрибуирани системи кога се користат дистрибуирани трансакции или контролата за совпа?а?е. Дистрибуиран засто? може да се открие или со изградба на глобалното чека?е за графа, од локалните чека?е за графа во детекторот на застои или од страна на дистрибуиран алгоритам како брка?е на рабови. Во обврската за нарачува?е на заснована дистрибуирана околина (SS2PL, или ригорозни) дистрибуирани застои се решаваат автоматски од страна на атомски посветен протокол, и не е потребно глобалното чека?е за графа или други механизами за решава?е. Слична резолуци?а за автоматски глобални застои се случува, исто така, во средини кои се вработуваат 2pl кои не се SS2PL. Сепак, 2pl кои не се SS2PL ретко се користат во пракса. Фантомски застои се застои кои се откриени во дистрибуиран систем поради внатрешни одложува?а во системот, но ве?е не посто?ат од времето на нивното открива?е.

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

Размислете за "Кога два воза се доближуваат едни со други на премин" пример што е дефиниран погоре. Точно на време превенци?а работи како да имаш лице кое стои на премин со еден га?тан, ко? ?е ги сподели само со еден воз "супер песните" кои забрзуваат погоре и преку другите возови кои чекаат. ?За нерекурзивените брави, бравата може да се внесе само еднаш (каде една нишка двапати се внесува без отклучува?е, ?е предизвика засто?, или да се отфрли исклучокот за спроведува?е на превенци?а за кружно чека?е). ?За рекурзивените брави, дозволено е само една нишка да помине преку бравата. Ако било кои други нишки влезат во бравата, тие мора да почекаат до првичната нишка ко?а поминува преку завршните n-пати на влегува?е. Значи проблемот со првата е дека таа не прави засто? превенци?а на сите. Во втората не се дистрибуирани превенци?алните застои. Но, вториот е редефиниран за да се спречи сценарио на засто?от со ко? првата не може да се справи. ?Рекурзивно, само една нишка е дозволено да помине преку брава. Ако се користат други нишки за влез во бравата, тие мора да почекаат додека првичната нишка ко? помина низ завршите n-пати. Но, ако бро?от на нишки кои влегуваат, е еднаков на бро?от на нишки што се заклучени, се доделува една нишка како супер-нишка, и само му овозможува работи (следе?е на бро?от колку пати влегува и излегува) сe додека не заврши. Откако супер-нишката ?е заврши, состо?бата се вра?а назад на користе?е на логиката од рекурзивна брава, и излегува?ето од супер-нишката. 1. Се поставува себеси, биде??и не е супер-нишка 2. ?а известува бравата дека другите се заклучени, чека??и ?а нишката ко?а треба да ?а ре-провери оваа состо?ба Ако сценарио за засто?от постои, се поставува нова супер-нишка и продолжува да ?а следи таа логика. Инаку, продолжува со редовните заклучува?а.

Нерешени проблеми [ уреди | уреди извор ]

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

Другиот проблем не се однесува на привремените праша?е за засто?от (навистина не е ?ор-сокак, туку една претстава убиец), каде две или пове?е нишки заклучени еден со друг, додека друга неповрзана нишка работи. Овие привремени застои би можеле да имаат нишка ко?а работи исклучиво во нив, зголемува?е на паралелизам. Но, заради тоа како открива?ето на дистрибуирани застои работи за сите брави, неповрзаните нишки кои работат мора да завршат пред изведува?ето на логика на супер-нишка за да се отстрани привремено засто?от. Понатамошно проширува?е Ова може понатаму да се прошири за да вклучи дополнителна логика за да се зголеми паралелизамот каде што привремените застои може да се случат поинаку.

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

Стратегии за справува?е со засто?

Дополнителна литература [ уреди | уреди извор ]

Kaveh, Nima; Emmerich, Wolfgang. ?Deadlock Detection in Distributed Object Systems“ (PDF) . London: University College London. Наводот journal бара |journal= ( help )
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 . ACM: 41?50. doi : 10.1145/1147403.1147412 .
Coffman, Edward G., Jr.; Elphick, Michael J.; Shoshani, Arie (1971). ?System Deadlocks“ (PDF) . ACM Computing Surveys . 3 (2): 67?78. 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. doi : 10.1145/263326.263335 . ISSN 0734-2071 .
Havender, James W. (1968). ?Avoiding deadlock in multitasking systems“ . IBM Systems Journal . 7 (2): 74. Архивирано од изворникот на 2012-02-24 . Посетено на 2012-04-30 .
Holliday, JoAnne L.; El Abbadi, Amr. ?Distributed Deadlock Detection“ . Encyclopedia of Distributed Computing . Kluwer Academic Publishers . Архивирано од изворникот на 2015-11-02 . Посетено на 2012-04-30 .
Knapp, Edgar (1987). ?Deadlock detection in distributed databases“. ACM Computing Surveys . 19 (4): 303?328. doi : 10.1145/45075.46163 . ISSN 0360-0300 .
Ling, Yibei; Chen, Shigang; Chiang, Jason (2006). ?On Optimal Deadlock Detection Scheduling“. IEEE Transactions on Computers . 55 (9): 1178?1187.

Извори [ уреди | уреди извор ]

Silberschatz, Abraham (2006) - Operating System Principles , 7th Ed. ( На Google Books ) (англиски)
Schneider, G. Michael (2009) - Invitation to Computer Science На Google Books ) (англиски)
Padua, David (2011). Encyclopedia of Parallel Computing ( На Google Books ) (англиски)