Застој

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

Еве еден прост компјутерски пример во продолжение. Да претпоставиме дека еден компјутер има три ЦД-дискови и три процеси. Секој од трите процеси зазема по еден од дисковите. Ако секој процес сега бара друг диск, трите процеси ќе бидат во ќор-сокак. Сите процеси ќе чекаат 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-пати. Но, ако бројот на нишки кои влегуваат, е еднаков на бројот на нишки што се заклучени, се доделува една нишка како супер-нишка, и само му овозможува работи (следење на бројот колку пати влегува и излегува) сè додека не заврши. Откако супер-нишката ќе заврши, состојбата се враќа назад на користење на логиката од рекурзивна брава, и излегувањето од супер-нишката. 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. Архивирано од изворникот (PDF) на 2012-01-27. Посетено на 2012-04-30.
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) (англиски)