Blocarea reciprocă este o situație în care fiecare dintr-un grup de procese așteaptă un eveniment pe care numai un alt proces din acest grup îl poate declanșa. Adesea, o astfel de situație este observată în paradoxuri precum "pui sau ou". Există, de asemenea, nume de situație în care se întâmplă situații de urgență. impas. clinch. În literatura engleză, această situație se numește engleza. impas (pronunțat Deadlock).
În domeniul tehnologiei informației, blocarea reciprocă se referă la o situație în care două sau mai multe procese așteaptă până când un altul eliberează o anumită resursă sau dacă mai mult de două procese așteaptă eliberarea resurselor într-un circuit închis.
Ca exemplu al acestei situații, puteți aduce doi bărbați, schițe de desen, având doar un singur conducător și un creion. Dacă unul dintre bărbați ia un conducător și un alt creion, între ei apare o situație reciprocă de blocare atunci când pentru a elibera conducătorul aveți nevoie de un creion și pentru a elibera creionul aveți nevoie de un conducător.
În general, o blocare (sau agățare) este o situație în care, indiferent de cât timp trece, nu poate avea loc nici o prehidență de la o stare la alta.
Condiții de interblocare reciprocă
Sa demonstrat că pentru apariția unei situații de interblocare reciprocă trebuie îndeplinite simultan următoarele patru condiții:
- Condiție de excludere mutuală. Fiecare resursă este în prezent fie ocupată de un singur proces, fie gratuit. Asta este, resursele sunt în uz exclusiv.
- Condiția de deținere și de așteptare. Procesele care păstrează în prezent resursele dobândite anterior pot face cereri de noi resurse.
- Condiția absenței eliberării forțate a resurselor (limba engleză nu are o preemțiune). Este imposibil să forțați procesul să elibereze resursele primite anterior. Un proces care are resursele trebuie să le elimine.
- Starea de așteptare ciclică. Trebuie să existe o secvență inelară cu două sau mai multe procese, fiecare dintre acestea așteptând resemnarea resurselor deținute de următorul membru al secvenței. Cu alte cuvinte, trebuie să existe o mulțime de procese, astfel încât procesul P 0 se așteaptă la eliberarea resursei de proces P 1, P 1 așteaptă P 2. P N-1 se așteaptă ca P N. și P N să aștepte resursa care urmează să fie eliberată prin procesul P 0.
Pentru apariția unei situații de interblocare reciprocă, toate cele patru condiții trebuie îndeplinite simultan. Dacă nu este îndeplinită cel puțin una dintre condiții, blocarea reciprocă este imposibilă.
Simularea situațiilor de blocare
Un exemplu al unui grafic de alocare a resurselor. În acest exemplu, toate procesele vor avea acces la resursele necesare, prin urmare blocarea reciprocă este imposibilă.
Situația blocării reciproce poate fi descrisă mai exact cu ajutorul unui instrument special - graficul de alocare a resurselor (graficul de alocare a resurselor în limba engleză). În acest grafic orientat, mulțimea de vârfuri constă din două subseturi - toate procesele active din sistem (P =) și tipurile de resurse existente (R =).Marginea de la procesul P și resursa P J este notată cu; înseamnă că procesul P și a trimis o cerere pentru o unitate de resurse de tip R J și se așteaptă ca această resursă (abreviată, marginea interogării). Marginea de la tipul de resursă R J la procesul P și este notată ca; înseamnă că o unitate de resurse de tip R J a fost prevăzută cu procesul P și (abreviat, marginea de selectare).
Deoarece pot exista mai multe unități de resurse de același tip, vârfurile de resurse sunt desemnate drept dreptunghiuri cu puncte din interior. Numărul de puncte indică numărul de unități din acest tip de resursă.
Având o astfel de definiție a graficului de alocare a resurselor, se poate dovedi că, cu condiția că nu există cicluri în grafic, niciunul dintre procese nu intră într-un punct mort. Dacă există un ciclu în grafic, există o posibilitate de apariție a blocajelor.
Dacă fiecare tip de resursă are doar o instanță, atunci există un impas din prezența buclă. Fiecare proces din ciclu cade într-un punct mort.
Dacă există tipuri de resurse cu instanțe multiple, atunci nu există niciun blocaj din cauza prezenței ciclului. În acest caz, prezența unui ciclu este necesară, dar nu este o condiție suficientă pentru apariția blocajelor.
Plăci Petri
În rețelele Petri, un capăt mort este numit astfel de seturi de poziții pe care fiecare tranziție, care la ieșire are una din pozițiile de blocaj, folosește orice poziție ca punct de intrare. Adică, dacă toate pozițiile impasului sunt golite la un moment dat, atunci întregul set de poziții va rămâne gol pentru totdeauna. Niciunul dintre tranziții nu poate deplasa cipul într-un blocaj, deoarece nu există chipsuri în blocaj, permițând tranziția, ieșirea din care este poziția din impas.
O capcană este un set de poziții pentru care fiecare tranziție a cărei intrare este una dintre pozițiile setului la ieșire are o altă poziție a setului. Adică dacă există un cip într-o poziție arbitrară a capcanei, acesta va fi întotdeauna într-o anumită poziție din capcană.
Sa demonstrat că condiția necesară și suficientă pentru activitatea unei rețele Petri marcate cu liberă alegere este cerința ca fiecare blocaj să conțină o capcană cu un cip.
Confruntarea cu Deadlock-urile
Manipularea și manipularea situațiilor de blocare reciprocă pot fi împărțite condițional în:
- Neglijarea problemei în general (așa-numitul "algoritm de struț").
- Identificați și recuperați. Permiteți blocarea reciprocă, identificați-o și efectuați anumite acțiuni.
- Evitarea dinamică a blocării reciproce prin alocarea corespunzătoare a resurselor.
- Prevenirea prin neîndeplinirea uneia dintre cele patru condiții de interblocare reciprocă.
Prima abordare este folosită în majoritatea sistemelor de operare moderne. comportamentul corect în situația blocării reciproce este responsabilitatea dezvoltatorului de software.
profilaxie
Așa cum sa spus mai sus, pentru apariția situației de interblocare reciprocă, este necesar să se îndeplinească simultan patru condiții. Dacă una dintre ele nu este executată, atunci situațiile de blocare reciprocă nu vor avea loc. Iată descrierile abordărilor fiecărei condiții.
Excluderea mutuală
Trebuie să fie îndeplinită condiția de excludere reciprocă sau de utilizare exclusivă pentru resursele inseparabile. De exemplu, imprimanta trebuie să fie utilizată ex- tat, într-un singur proces. Cu toate acestea, unele resurse separate, cum ar fi accesul la fișiere, pot fi distribuite în mai multe procese.
În general, condiția de excludere reciprocă nu poate fi eludată, deoarece unele dintre resurse ar trebui utilizate numai în modul exclusiv.
Pentru a evita această condiție, de fiecare dată când un proces necesită resurse noi, acesta nu trebuie să conțină alte resurse. Următoarele algoritmi sunt posibile:
- Obțineți toate resursele la începutul procesului înainte de a efectua alte operațiuni.
- Primiți o nouă resursă dacă eliberați resursele ocupate. Înainte de a solicita o nouă resursă, procesul își eliberează resursele.
Dezavantajul primului algoritm este utilizarea ineficientă și resursele simple. De asemenea, există posibilitatea "foamei": într-un sistem supraîncărcat, un proces care necesită mai multe resurse populare nu le poate obține niciodată, deoarece cel puțin unul dintre ele poate fi ocupat de un alt proces.
Eliberarea forțată a resurselor
Pentru neîndeplinirea condiției de absență a eliberării forțate a resurselor, sunt posibili următorii algoritmi:
Un astfel de algoritm este folosit pentru resursele a căror stare poate fi ușor stocată și reprodusă, cum ar fi registrele procesoarelor sau spațiile de memorie.
Cyclic așteaptă
Evitarea așteptării ciclice se realizează prin stabilirea ordinii de acces la resurse de diferite tipuri.
Fie setul de tipuri de resurse. Identifică un număr întreg cu fiecare dintre ele, ceea ce va permite compararea resurselor și stabilirea priorităților (a se vedea setul parțial comandat).
Acum, pentru a evita așteptarea ciclică, stabilim următoarea regulă: procesul poate interoga resursele numai în ordinea ascendentă a numerelor. Alternativ, procesul trebuie să elibereze o resursă cu un număr de ordine mare înainte de a trimite o cerere pentru o resursă cu un număr mai mic.
Deși este responsabilitatea dezvoltatorului de software să stabilească și să impună procedura corectă de accesare a resurselor, există instrumente specializate pentru a verifica erorile de conformitate și de raportare. Un exemplu este programul de martori care rulează pe sistemele de operare ale familiei BSD.
Pentru a evita blocările, programele trebuie să furnizeze sistemului de operare în prealabil informații despre resursele care vor fi utilizate de proces la locul de muncă. Având aceste informații, sistemul de operare poate decide ce cereri poate aștepta procesul. Pentru a decide dacă un proces trebuie să aștepte, sistemul de operare trebuie să ia în considerare resursele disponibile, resursele sunt alocate proceselor și viitoarelor cereri pe care le pot face procesele.
instrumente
Cunoscute sunt astfel de instrumente pentru lucrul cu clinching în sistemele informatice:
program martor, care operează pe sistemele de operare ale familiei BSD, obține informații despre locurile luate și verificări pentru aceste solicitări. Sistem SPIN pentru verificarea modelelor sistemelor distribuite.
Articole similare
Trimiteți-le prietenilor: