Dacă resursa solicitată nu este disponibilă, procesul intră într-o stare de așteptare. Dacă resursa necesară este păstrată de un alt proces de așteptare, primul proces nu va putea să-și schimbe starea. Această situație se numește sfârșit de capăt. Se spune că într-un sistem multiprogramare procesul este într-o stare de impas dacă așteaptă un eveniment care nu se va întâmpla niciodată. Un blocaj de sistem sau un sistem de blocare se datorează faptului că unul sau mai multe procese se află într-o stare de blocare. În 1971, Coffman, Elfik și Shoshani au formulat următoarele patru condiții pentru apariția unor termene moarte:
1. Condiția excluderii reciproce. Fiecare resursă este alocată exact unui proces sau este disponibilă. Procesele necesită acordarea unui control monopol asupra resurselor alocate acestora.
2. Condiția de așteptare pentru resurse. Procesele își păstrează resursele deja alocate, așteptând în același timp alocarea de resurse suplimentare (care de obicei sunt reținute de alte procese).
3. Condiția non-redistribuirii. Resursa dată mai devreme nu poate fi îndepărtată forțat din proces. Ele pot fi eliberate numai prin procesul care le păstrează.
4. Starea de așteptare circumstante. Există un lanț inelar de procese în care fiecare proces își păstrează una sau mai multe dintre resursele necesare altor procese de lanț.
Pentru un impas, toate cele patru condiții trebuie îndeplinite.
Principalele direcții ale luptei împotriva secetelor. Problema temelor mortale a inițiat numeroase studii interesante în domeniul informaticii. Evident, condiția ciclică de așteptare diferă de restul. Primele trei condiții formează regulile existente în sistem, în timp ce a patra condiție descrie o situație care poate apărea cu o anumită secvență nefavorabilă de evenimente. Prin urmare, metodele de prevenire a blocajelor se concentrează în principal asupra încălcării primelor trei condiții prin introducerea unui număr de restricții privind comportamentul proceselor și modul de alocare a resurselor. Metodele de detectare și eliminare sunt mai puțin conservatoare și se reduc la descoperirea și ruperea ciclului de așteptare a resurselor.
Deci, principalele direcții ale luptei împotriva secetelor: 1) Prevenirea terminilor moarte. 2) Bypassing deadlocks. 3) Detectarea blocajelor. 4) Recuperarea după blocări
I) Prevenirea blocajelor din cauza încălcării condițiilor de apariție a blocajelor. Dacă în sistem nu există resurse dedicate, nu vor exista blocări. Cu toate acestea, este clar că socializarea, de exemplu, a unei imprimante, adică permiterea a două procese de a scrie la o imprimantă în același timp, va duce la haos. Prin organizarea tipăririi, este posibilă imprimarea simultană a mai multor procese. În acest model, singurul proces care interacționează într-adevăr cu imprimanta este daemonul imprimantei. Astfel, impasul pentru imprimanta este eliminat. Din păcate, nu toate dispozitivele pot fi spooleate (tabelul de proces nu este ușor de fals). Un efect secundar nefericit poate fi o situație potențială de blocare din cauza concurenței pentru spațiul de pe disc pentru tampoane. Cu toate acestea, într-o formă sau alta, această idee este adesea folosită.
Încălcarea condiției de așteptare pentru resurse suplimentare. În 1968, Havender a propus următoarea strategie: 1) Fiecare proces trebuie să solicite imediat toate resursele pe care le solicită și nu poate începe să fie executat până când nu i se oferă toate acestea. 2) Dacă procesul păstrează anumite resurse și i se refuză resurse suplimentare, atunci trebuie să elibereze resursele inițiale și, dacă este necesar, să le solicite din nou, împreună cu alte resurse suplimentare.
Deci, o modalitate este de a obține toate procesele pentru a solicita toate resursele lor înainte de a face (toate sau nimic). Dacă sistemul este capabil să aloce toate procesele necesare procesului, acesta poate funcționa până la finalizare. Dacă cel puțin una dintre resurse este ocupată, procesul va aștepta. Această abordare nu este foarte atractivă și duce la o scădere a eficienței calculatorului. Se întâmplă foarte rar ca toate dispozitivele solicitate să fie necesare în același timp de program. Desigur, puteți împărți programul în mai mulți pași și puteți aloca resurse separat pentru fiecare etapă a programului, dar problema principală este că multe procese nu știu câte resurse vor avea nevoie înainte de a începe calculul. Dacă astfel de informații sunt disponibile, atunci putem folosi algoritmul bancherului. Cu toate acestea, unele mainframe ambalate necesită utilizatorilor să enumere toate resursele necesare pentru programul său.
Încălcarea principiului non-redistribuirii. În conformitate cu al doilea principiu al lui Havender, este posibilă selectarea resurselor din procesele care le dețin până la finalizarea acestor procese. Dacă acest lucru a fost întotdeauna posibil, ar fi posibil să se atingă a treia condiție pentru apariția blocajelor. Dacă procesul utilizează anumite resurse pentru o perioadă de timp și apoi eliberează acele resurse, acesta pierde toate lucrările făcute până acum. Întreaga chestiune în prețul acestei decizii, care poate fi prea mare, dacă se produce o astfel de situație frecvent. Un alt dezavantaj al acestei scheme poate fi discriminarea proceselor individuale, care aleg în mod constant resurse.
Încălcarea condiției de așteptare circulară. Citirea ciclică poate fi evitată în mai multe moduri. Unul dintre ele este acela de a acționa în conformitate cu regula că fiecare proces poate avea o singură resursă la un moment dat. Dacă aveți nevoie de oa doua resursă - eliberați prima. Evident, pentru multe procese acest lucru nu este acceptabil, de exemplu, pentru cei care imprimă fișiere mari de pe bandă la imprimantă. O altă modalitate este să atribuiți numere unice tuturor resurselor și să cereți ca procesele să solicite resurse în ordine ascendentă a numerelor. Apoi nu se poate ivi o așteptare circulară.
O mică variantă a acestui algoritm va fi numerotarea în ordine ascendentă nu a resurselor, ci a cererilor de proces. După ultima solicitare și eliberare a tuturor resurselor, puteți permite procesului să efectueze din nou prima solicitare. Evident, este imposibil să găsim o ordine care să satisfacă pe toată lumea.
II) ocolirea blocajelor. Atunci când se împiedică blocarea, obiectivul este de a asigura condiții care exclud posibilitatea unor situații de blocare. Sistemul, în timp ce furnizează resursele la dispoziția procesului, trebuie să decidă dacă este sigur sau nu. Se pune întrebarea: există un algoritm care vă ajută mereu să evitați punctele de întârziere și să alegeți corect. Răspunsul este da, putem evita impasurile, dar numai dacă anumite informații sunt cunoscute în avans. În această secțiune, vom analiza modul de prevenire a blocajelor prin alocarea cu atenție a resurselor. Unul dintre algoritmii de prevenire a blocajelor se bazează pe conceptul de stări sigure.
Algoritmul bancherului. Puteți evita un impas dacă folosiți rațional resursele, respectând anumite reguli. Cel mai faimos dintre astfel de algoritmi este algoritmul bancar propus de Dijkstroy. El, așa cum a fost, imită acțiunile bancherului, care, având o anumită sursă de capital, acceptă împrumuturi și emite plăți. Să presupunem că sistemul are n dispozitive, de exemplu benzi. Esența algoritmului este următoarea: 1) OS primește o cerere din procesul utilizatorului, dacă cererea sa maximă nu depășește n. 2) Utilizatorul garantează că, dacă OS este capabil să-și satisfacă cererea, atunci toate dispozitivele vor fi returnate sistemului în timpul finit. 3) Starea actuală a sistemului se numește fiabilă dacă sistemul de operare poate asigura executarea tuturor proceselor într-un timp finit. 4) Potrivit algoritmului bancherului, dispozitivele pot fi alocate doar dacă starea sistemului rămâne fiabilă.
III) Detectarea blocajelor. Detectarea impasului este stabilirea faptului că a apărut o situație de blocaj și o definiție a proceselor și a resurselor implicate în această situație. De regulă, algoritmii de detectare se aplică atunci când apar primele trei condiții necesare pentru un blocaj. Apoi, se verifică prezența unui mod circular de așteptare. În același timp, graficele de alocare a resurselor deja menționate sunt utilizate în mod activ. Dacă graficul poate fi redus la toate procesele, atunci nu există un impas. În caz contrar, toate procesele non-reductibile sunt procese implicate într-o situație de blocaj.
IV) Recuperarea după blocări. Să presupunem că algoritmul de detectare sa confruntat cu sarcina sa și a găsit un punct mort. Ce urmează. Una dintre modalități este de a recupera și de a face sistemul să funcționeze. În această secțiune vom discuta despre diferite modalități de recuperare din impasuri. Sistemul, care se afla într-un punct mort, poate fi retras din el, încălcând una dintre condițiile existenței sale. În acest caz, este posibil ca mai multe procese să piardă unele sau toate rezultatele lucrărilor efectuate.
Complexitatea recuperării se datorează mai multor factori: 1) în majoritatea sistemelor nu există mijloace eficace de suspendare a procesului, de retragere din sistem și reluare ulterioară; 2) dacă există chiar și astfel de fonduri, utilizarea acestora necesită cheltuieli și atenție operatorului; 3) recuperarea dintr-un impas serios poate necesita multă muncă.
Restaurați prin redistribuirea de resurse. O modalitate de a recupera este de a forța un proces din sistem să fie folosit pentru utilizarea ulterioară a resurselor sale. Pentru a determina ce proces să eliminați din sistem, eforturile operatorului sunt deseori necesare. În unele cazuri, este posibil să se ia temporar o resursă de la proprietarul actual și să se transfere într-un alt proces. De exemplu, pentru a selecta o imprimantă laser dintr-un proces care se transmite către acesta, operatorul poate asambla hârtii imprimate deja și le poate stivui într-o teanc. Procesul poate fi apoi întrerupt și imprimanta transferată într-un alt proces. După terminarea lucrării, hârtia poate fi returnată la imprimantă, iar primul proces este reluat. Abilitatea de a lua o resursă dintr-un proces, de ao da unui alt proces și apoi să o întoarcă înapoi, fără a-l deteriora, depinde în mare măsură de natura resurselor. Această recuperare este adesea dificilă, dacă nu imposibilă.
Recuperare prin returnare înapoi. Aceasta este, cel mai probabil, cea mai eficientă modalitate de suspendare și reluare. Într-o serie de sisteme, mijloacele de repornire sunt implementate de la punctul de control (conservarea stării sistemului la un moment dat). În cazul în care aceste fonduri nu sunt furnizate, acestea ar trebui să fie organizate de către dezvoltatorii de aplicații. Dacă proiectanții de sisteme știu că este probabil un impas, pot organiza periodic puncte de control pentru procese. Când se descoperă un blocaj, este clar care sunt resursele implicate în ciclul de așteptare. Pentru a implementa restaurarea, procesul care deține astfel de resurse trebuie să fie eliminat până la momentul solicitării acestei resurse.
Recuperarea prin lichidarea unuia dintre procese. Rough, dar cea mai simplă cale de a elimina un sfârșit mort este de a ucide unul sau mai multe procese. De exemplu, ucideți procesul care este în buclă. Apoi, dacă este reușit, procesele rămase pot fi executate. Dacă acest lucru nu ajută, atunci un alt proces poate fi eliminat.
Dacă este posibil, este mai bine să ucizi procesul care poate fi returnat la început fără a se deteriora (astfel de procese se numesc procese idempotent), de exemplu compilația. Pe de altă parte, un proces care modifică conținutul unei baze de date nu poate fi întotdeauna reluat corect.