Zastoj

U paralelnom izračunavanju, zastoj je situacija u kojoj dve ili više konkurentske akcije čekaju jedna drugu da se završe, pa samim tim nijedna od njih ne radi.

Oba procesa moraju imati izvore da bi nastavili sa izvršenjem. P1 zahteva dodatan izvor R1 i poseduje R2, P2 zahteba dodatan izvor R2 i poseduje R1; nijedan proces ne može nastaviti sa izršenjem .

U transakcija baze podataka, zastoj se dešava kada kada dva procesa tokom svojih transakcija ažuriraju  dva reda informacija ali u obrnutom smeru. Na primer, proces A ažurira red 1 pa red 2 u isto vreme dok proces B ažurira red 2 pa red 1. Proces A ne može da završi ažuriranje reda 2 dok se proces B ne završi, ali proces B ne može da završi ažuriranje reda 1 dok proces A nije završen. Bez obzira koliko je vremena dozvoljeno za prolazak, ova situacija se nikada neće završiti sama od sebe i zbog toga, baza podataka će ubiti transakciju procesa koji je uradio najmanje posla  .

U operativnom sistemu, zastoj je situacija koja nastaje kada proces ili nit uđu u stanje čekanja, jer je traženi resurs zadržan od strane drugog procesa koji čeka, koji takođe čeka drugi resurs koji je zadržan od strane drugog procesa koji čeka. Ako proces ne može da promeni njegovo stanje beskonačnosti jer je resurs se resurs koji se traži već koristini od strane drugog procesa koji čeka, onda se kaže da je sistem u zastoju .

Zastoj je čest problem u sistemima sa više procesa, Paralelna obrada i  u raspodeljenom izračunavanju, gde se softverske i hardverske brave koriste da kontrolišu podeljene resurse i da sprovedu sinhronizaciju procesa.

U sistemima telekomunikacije, zastoji se uglavnom javljaju tokom izgubljenih ili oštećenih signala umesto resursa tvrdnje .

Primeri

Bilo koji zastoj se može uporediti sa klasičnim "kokoška ili jaje" problemom.. Takođe se može smatrati i paradoksalnom "Uhvati-22" situacijom.. Pravi svetski primer bi bio nelogično usvojen statut zakonodavstva Kanzas u ranijim 20-tim, koji kaže :

Jednostavan računarski primer je sledeći. Pretpostavimo da računar ima tri CD diskova i tri procesa. Svaki od tri procesa sadrži jedan disk. Ako bi svaki proces sada zahtevao drugi disk, tri procesa bi bila u zastoju. Svaki proces bi čekao da CD disk bude slobodan, što se može jedino desiti od strane drugog procesa koji čeka. Stoga, ovo rezultira kružnom lancu.

Krećući se po šifrovanom nivou izvora, zastoj se može javiti čak i u slučaju jedne niti i jednog izvora (zastićen od strane muteksa). Pretpostavimo da postoji funkcija f1 koja radi neki posao nad resursom, zaključavajući muteks na početku i oslobađajući ga kada je gotovo. Sledeće, neko napravi drugu funkciju f2 prateći taj obrazac na istom izvoru ( zaključaj, uradi, oslobodi) ali odluči da uključuje i poziv na f1 da prenese deo posla. Desiće se to da će muteks biti zaključan onog trenutka kada se uđe u f2 i onda opet tokom poziva na f1, što rezultuje zastojem ako muteks nije uvučen (tj sorta "brzi muteks").

Neophodni uslovi

Situacija zastoja može se postići ako se svi sledeći uslovi nalaze istvoremeno u sistemu :

1. Muteks: barem jedan resurs mora biti zadržan u ne deljivom modu. Samo jedan proces može koristiti resurs u bilo kom vremenskom intervalu.
2. Drži i čekaj ili zadržavanje resursa: proces trenutno zadržava barem jedan resurs i zahteva dodatne resurse koji su zadržani od strane drugih procesa.
3. Bez prisvajanje: resurs može biti oslobođen samo dobrovoljno od strane procesa koji ga zadržava.
4. Kružno čekanje: proces mora da čeka resurs koji je zadžan od strane drugog procesa, koji čeka da prvi proces otpusti resurs. Uglavnom, tu je skup procesa koji čekaju, P={P1, P2,..., Pn} , takav da P1 čeka resurs zadržan od strane P2, P2 čeka resurs zadržan od strane P3 i tako sve do Pn koji čeka resurs zadržan od strane P1

Ova četiri uslova su poznati kao Kofmanovi uslovi iz njihovog prvog opisa iz 1971 u članku Edvarda G. Kofmana, Jr. . Neispunjenost bilo kog uslova je dovoljono da spreči zastoj da se desi.

Izbegavanje zastoja baze podataka

Dobar način da se izbegne zastoj baze podataka je taj da se proprati Oraklov Vodič za Preživljavanje Zastoja :

Ovoj rečenici je potrebno objašnjenje:

• Prvo, to ukazuje na činjenicu da procesi moraju biti unutar transakcije da bi se zastoji dogodili. Imati na umu da neki sistemi baze podataka mogu biti konfigurisani da stepeničasto brišu, koji stvaraju implicitne transakcije koje onda mogu uzrokovati zastoj. Takođ, neki DBMS proizvođači nude zaključavanje reda nivoa,  tip rekordno zaključavanje koji dosta smanjuje šanse za zastojem, suprotno stranica-nivo zaključavanja, koji ima mogućnost da zaključa mnogo više procesa.
• Drugo, pozivanje na "više izvora" znači "više od jednog reda u jednoj ili više tabela" . Primer zaključavanja istog redosleda može uključivati obradu svi INSERTS prvo, svih UPDATES drugo, i svih DELETES na kraju; u obradi svakog od njih sve roditeljske tabele se menjaju pre nego što se promene dečije tabele; i obrada tabele se menja u istom smeru (kao na primer po alfabetu, ili poređano po ID ili broju profila)  .
• Treće, eliminaciju svih rizika od zastoja je teško postignuti kada DBMS ima automatske zaključavanje-eskalacija karakteristike koje podižu brave red-nivo u stranicu zaključavanja koja može da eskalira do tabele zaključavanja. Iako rizik ili šansa doživljavanja zastoja neće otići do nule jer se zastoji dešavaju više  na velikim, velikog obima, kompleksnim sistemima, može biti dosta smanjen, i - kada je potrebno- programeri mogu poboljšati softver da povrate transakcije kada sistem detektuje zastoj.
• Četvrto, zastoji mogu dovesti do gubitka podataka ako programeri ne napišu softver specijalizovan da određuje upotrebu transakcije prilikom svake interakcija sa DBMS;  ovakav gubitak podataka je teško pronaći i može prouzrokovati neočekivane greške i probleme

Zastoji nude izazovan problem da se poprave dok dovode do gubitka podataka, teški su za izolovanje, prouzrokuju neočekivane probleme, i treba im duže vremena da se poprave. Izmena svakog dela softvera u velikom sistemu baze podataka u cilju da se uvek resursi zaključavaju u istom smeru kada naredba uzima značajne resurse i testira za sprovođenje.

Rukovanje zastojem

Većina operativnih sistema ne može izbeći zastoj da se dogodi.Kada se zastoj dogodi, različiti operativni sistemi različito reaguju na njih u različitim ne-standardnim načinima. Većina pristupa rade tako da spreče jedan od četiri Kofmanova uslova da se dogode, posebno četvrti . Glavni pristupi slede.

Ignorisanje zastoja

U ovom proistupu, pretpostavlja se da se zastoj nikada neće desiti. Ovo je takođe aplikacija Nojevog algoritma. Ovaj pristup je prvobitno korišćen od strane Miniksa i Juniksa. Ovo se koristi kada su vremenski intervali između izvršavanja zastoja veliki i kada je nastali gubitak podataka svaki put podnošljiv 

Otkrivanje

U otkrivanju zastoja, zastojima je dozvoljeno da se aktiviraju. Onda se stanje sistema ispituje da detektuje da se taj zastoj dogodio i potom on je ispravljen. Algoritam je zaspolen da prati raspodelu resursa i stanje procesa, vraća se nazad i restartuje jedan ili više procesa u cilju da izbriše detektovan zastoj. Otkrivanje zastoja koji se već dogodio je lako pošto resurse koji je svaki proces zaključao i trenutno tražio je poznat planeru resura operativnog sistema.

Tehnike otkrivanja zastoja uključuju, ali nisu ograničene, proveru modela. Ovaj pristup gradi model konačnog automata na kome se vrši analiza progresa i nalaze svi mogući terminali skupova u modelu. Svaki ponaosob predstavljaju zastoj. 

Nakon što je zastoj pronađen, može biti prepravljen koristeći jednu od sledećih metoda::

1. Proces terminacije: jedan ili više procesa uključenih u zastoj mogu biti prekinuti. Možemo da izaberemo da prekinemo sve procese uključene u zastoj. Ovime se osigurava da je zastoj rešen sa sigurnošću i brzo. Ali je cena visoka jer će parcijalni proračuni biti izgubljeni. Ili, možemo izabrati da prekinemo jedan proces u vreme dok se ne reši zastoj. Ovaj pristup ima visoke troškove zato što posle svakog prekida algoritam mora da odluči da li je sistem idalje u zastoju. Nekilo faktora moraju se uzeti u obzir dok se bira način za terminaciju, kao što su prioritet i starost procesa.
2. Prisvajanje resursa: sredstva izdvojena za različite  procese mogu biti uspešno prisvojena i dodeljena drugim procesima dok zastoj nije slomljen.

Prevencija

Prevencija zastoja radi tako što predviđa jedan od četiri Kofmanova stanja da ne započnu.

• Uklanjanje stanja međusobnog isključivanja znači da nijedan proces neće imati pristup resursu. Ovo dokazuje da resursi ne mogu biti spoolovani. Ali čak i sa spoolovanim resursima, zastoj može idalje da se dogodi. Algoritmi koji izbegavaju međusobno isključivanje nazivaju se algoritmi neblokirajuće sinhronizacije.
• Zadrži i čekaj ili zadržavanje resursa uslovi mogu biti uklonjeni zahtevanjem procesa da zatraži sve resurse koji su mu potrebni pre početka (ili pre nego što krene određeni skup operacija). Ova napredno znanje je teško zadovoljiti i, u bilo kom slučaju, predstavlja neefikasno korišćenje resursa. Drugi način je da se zatraži proces da zahteva resurse samo onda kada nema ništa. Dakle, moraju prvo da oslobode sve njihove trenutne zadržane resurse pre nego što zahteva sve resurse koji im trebaju za od nule. Ovo je često nepraktično. To je tako zato što resursi mogu biti dodeljeni i mogu da ostanu nekorišćeni duži vremenski period. Takođe, proces koji zahteva popularan resurs možda mora da čeka do beskonačnosti, zbog toga što resurs može uvek biti dodeljen nekom procesu, što dovodi do "gladi" resursa. (Ovi algoritmi, kao što je serializovanje tokena, poznati kao svi - ili - nijedni algoritmi).
• Stanje neprisvajanja može takođe biti teško ili nemoguće izbeći pošto proces mora biti u mogućnosti da poseduje resurs određeni vremenski period, ili ishod procesa može biti nedosledan ili se može javiti "mlaćenje". Inače, nemogućnost da se sprovede prisvajanje može ometati priroritet algoritma. Prisvajanje "potpuno zatvorenog" resursa uglavnom podrazumeva vraćanje, i treba ga izbegavati, jer je preskupo. Algoritmi koji dozvoljavaju prisvajanje uključuju zaključaj-besplatno i čekaj-besplatno algoritme i optimističnu kontrolu konkurencije. Ako proces zadržava neke resurse i zahteve za neki drugi resurs koji ne mogu odmah biti dodeljeni, stanje može biti odstranjeno tako što se otpuste svi trenutno zadržani resursi tog procesa .
• • Poslednji uslov je kružno čekanje. Pristupi koji izbegavaju kružna čekanja uključuju onemogućavanje prekida tokom kritičnih deonica i koriste hijerarhiju za određivanje delimičnog redosleda resursa. Ako ne postoji očigledna hijerarhija, čak se i memorija adrese resursa koristi za određivanje redosleda i od resursa se zahteva da povećaju redosled popisivanja. Dijkstra rešenje se takođe može koristiti.

Izbegavanje

Zastoj se može izbeći ako su određene informacije o procesu dostupne operativnom sistemu pre dodele resursa, kao što je koje će resurse proces imati tokom života. Za svaki zahtev resursa, sistem vidi da li će davanje dozvole značiti da će sistem ući u nesigurno stanje, tačnije da će doći do zastoja. Sistem onda samo dozvoljava zahteve koji će dovesti do sigurnog stanja. Da bi sistem mogao da utvrdi da li će sledeće stanje biti sigurno ili ne, mora unapred znati : 

•  resurse koji su trenutno dostupni; 
•  resurse koji su trenutno dodeljeni svakom procesu;
•  resure koji će biti traženi i oslobođeni od strane ovih procesa u budućnosti. 

Moguće je da proces bude u nesigurnom stanju ali da ne dovede do zastoja. Pojam sigurnog/nesigurnog stanja se odnosi samo na sposobnost sistema da uđe u stanje zastoja ili ne. Na primer, ako proces zahteva A koji bi doveo do nesigurnog stanja, ali oslobodi B koji bi sprečio kružno čekanje, onda je stanje nesigurno ali sistem nije u zastoju . 

Jedan poznat algoritam koji se koristi za izbegavanje zastoja je Bankarski algoritam, koji zahteva da se unapred zna ograničenje upotrebe resursa. Međutim, za neke sisteme je nemoguće znati unapred šta će koji proces tražiti. Ovo znači da je izbegavanje zastoja često nemoguće .

Dva ostala algoritma su Čekaj/Umri i Povredi/Čekaj, svaki koristi tehniku simetričnog prekida. U oba algoritma postoji stariji proces (O) i mlađi proces (Y). Starost procesa se može odrediti vremenskim markerom prilikom stvaranja procesa. Manji vremenski markeri su stariji procesi, dok veći vremenski markeri predstavljaju mlađe procese. 

Čekaj/Umri	Rani/Čekaj
O treba resurs držan od  Y	O čeka	Y umire
Y treba resurs držan od O	Y umire	Y čeka

Još jedan način da se izbegne zastoj je da se izbegne blokiranje, na primer korišćenjem neblokirajuće sinhronizacije ili čitaj-kopiraj-ažuriraj.

Živa blokada

Živa blokada je slična zastoja, samo što izjave procesa uključenih u živu blokadu se konstantno menjaju jedan u odnosu na drugog, niko ne napreduje. Ovaj termin je definican zvanično tokom 1970-ih —ranije viđen u objavljenoj literaturi u Babič artiklu 1979 o tačnosti programa. Živa blokada je specijalan slučaj izgladnjivanja resursa; opšta definicija samo navodi da se specijalan proces ne dešava.

Primer žive blokade u stvarnom životu se dešava kad se dvoje ljudi sretne u uskom hodniku, i svaki pokuša da bude učtiv tako što se pomeri sa strane i pusti drugog da prođe, ali oni završe klaćenjem sa strane na stranu bez ikakvog procesa zato što se oboje pomeraju na isto mesto u isto vreme.

Živa blokada je rizična sa nekim algoritmima koji detektuje i oživljava iz zastoja. Ako više od jednog procesa radi, algoritam detekcije zastoja se može aktivirati više puta. Ovo se može izbeći tako što se osigura da samo jedan proces (izabran proizvoljno ili po uslovu) stupi u akciju.

Raspodeljen zastoj

Raspodeljen zastoj se može javiti u raspodeljenom izračunavanju kada se raspodeljene transakcije ili kontrola konkurencije koriste. Raspodeljeni zastoji mogu biti detektovani ili pravljenjem globalnog čekaj-for grafa ili iz lokalnog čekaj-for grafa u detektoru zastoja ili preko raspodeljenog zastoja kao jurnjava ivice. 

Fantomski zastoji su zastoji koji su lažno detektovani u distributivnom sistemu tokom unutrašnjih kašnjena sistema ali oni u stvari ne postoje. Na primer, ako proces otpusti resurs R1 i izdaje zahtev za R2, i prva poruka je izgubljena ili odložena, kordinator (detektor zastoja) može lažno zaključiti zastoj(ako zahtev za R2 dok je tu R1 bi prouzrokovao zastoj).

Literatura

• (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. str. 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”. Arhivirano iz originala 2015-11-02. g. 
• 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. 

Spoljašnje veze

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