Interblocaj

In August 2010, pe autostrada Beijing – Zhanghiakou din China, a avut loc cel mai mare blocaj din istorie, 100 de kilometrii lungime. Acest blocaj a durat de pe 14 August 2010 pana pe 26 August 2010.

Interblocajul este o problema specifica programarii paralele, situatie in care doua (sau mai multe) actiuni asteapta de la cealalta sa se finalizeze, astfel niciuna nu reuseste sa fie finalizata.

Vorbind doar despre doua procese, fiecare are nevoie de resurse pentru a finaliza sarcina. Primul proces (denumit P1) contine resursa (R2) si are nevoie de resursa aditionala R1, iar procesul P2 contine resursa R1 si are nevoie de resura aditionala R2. In acest caz, niciunul din procesele mentionate nu poate accesa resursa necesara, ea fiind blocata in celalalt proces. Cele doua procese vor astepta resura neputand continua. O astfel de situatie duce la interblocarea celor doua procese.

O situatie de interblocaj poate fi usor comparata cu clasica problema "oul sau gaina".

Fiecare sesiune poate avea una sau mai multe sarcini care rulează simultan, în care fiecare sarcină ar putea dobândi sau aștepta să achiziționeze o varietate de resurse . Următoarele tipuri de resurse se pot bloca, fapt ce ar putea duce la un interblocaj:

Blocaje. Asteptand sa se blocheze resursele, precum obiecte, pagini, randuri, metadata si aplicatii se pot crea interblocaje. De exemplu, tranzactia T1 are un blocaj comun (S) pe randul r1 si asteapta sa aibe un blocaj exclusiv (X) pe randul r2. Tranzactia T2 are un blocaj comun (S) pe randul r2 si asteapta sa aibe un blocaj exclusive (x) pe randul r1. Acest rezultat va bloca ciclul in care T1 si T2 se vor astepta intre ele sa elibereze resursele blocate.

Fire de executie. O sarcina in asteptarea unui fir de executie liber poate crea un interblocaj. Daca sarcina in asteptare detine resurse care blocheaza toate celelalte fire de executie se va realiza un interblocaj. De exemplu, sesiunea S1 incepe o tranzactie si obtine un blocaj comun (S) pe randul r1, apoi devine inactive. Sesiunile active ce ruleaza pe toate firele de executie incearca sa obtina un blocaj exclusive (X) pe randul r1. Pentru ca sesiunea S1 nu poate primi un fir de executie, nu poate continua tranzactia pentru a elibera blocajul de pe randul r1. Acest rezultat va fi un interblocaj.

Memoria. Cand cererile paralele asteapta plusuri de memorie ce nu pot fi satisfacute cu memoria disponibila, un interblocaj poate aparea. De exemplu, doua interogari paralele, Q1 si Q2, executate ca functii definite de utilizator primesc 10MB, respectiv 20MB de memorie. Daca fiecare interogare are nevoie de 30MB, iar memoria disponibila este de 20MB, atunci Q1 si Q2 trebuie sa se astepte una pe cealalta sa eliberezee memorie, fapt ce duce la un interblocaj.

Resursele legate de executarea interogarilor in paralel. Firele de executie coordonator, producatori sau consumatori associate cu un port de tranzactie se pot bloca intre ele realizand un interblocaj de obicei atunci cand este inclus cel putin un alt process care nu face parte din interogarile paralele. De asemenea, cand o interogare paralela isi incepe executia, serverul SQL determina gradul de paralelizare sau numarul de fire de executie, bazat pe volumul de munca actual. Daca volumul de lucru al sistemului se schimba neasteptat, de exemplu candnoi interogari pornesc pe server sau sistemul ramane fara fire de executie, atunci poate aparea un interblocaj.

Toate resursele listate mai sus participa in motorul de cautare a interblocajelor de baze de date. Cautarea interblocajelor este efectuate de un fir de executie care monitorizeaza blocajele, fir care initiaza periodic cautarea lor prin toate sarcinile unei instante de motor de baze de date. Urmatoarele puncte descriu un proces de cautare:

Intervalul implicit de cautare este de 5 secunde

Daca firul de monitorizare al blocajelor gaseste un interblocaj, intervalul de cautare al interblocajelor scade de la 5 secunde pana la 100 de milisecunde, depinzand de frecventa interblocajelor

Daca firul de monitorizare al blocajelor nu mai gaseste interblocaje, motorul de baze de date creste intervalul de cautare la 5 secunde.

Daca un interblocaj a fost detectat, presupune ca urmatoarele fire de executie trebuie sa astepte un blocaj pentru a intra in interblocaj. Primele blocaje de dupa detectarea unui interblocaj vor declasa imediat o cautare de interblocaj in loc sa astepte urmatoarea cautare de interblocaje. De exemplu, daca intervalul curent de cautare este de 5 secunde si este detectat un interblocaj, urmatorul blocaj va porni imediat detectorul de interblojace. Daca acest blocaj face parte din interblocaj, el va fi detectat imediat in loc sa fie detectat la urmatoarea cautare.

In programarea paralela, un interblocaj poate aparea daca urmatoarele conditii sunt indeplinite simultan intr-un sistem:

Excludere reciproca: Cel putin o resursa trebuie sa fie detinuta intr-un mod non-partajabil. Doar un singur proces se poate folosi de acea resursa intr-un moment de timp.

Mentine si Asteapta sau Mentinere de Resurse: Un proces detine in acest moment cel putin o resursa si solicita resurse aditionale care sunt detinute de alte procese.

Fara Preferinta: O resursa poate fi eliberada doar voluntar de catre procesul care o detine.

Asteptare circulara: Un procest trebuie sa astepte o resursa care este detinuta de un alt proces, care la randul lui asteapta de la primul proces sa elibereze resursa. In general, exista un set de procese P={P1,P2,…,PN), in asa fel incat P1 asteapta resursa detinuta de P2, P2 asteapta resursa detinuta de P3, PN asteapta resursa detinuta de P1.

Aceste patru contitii sunt cunoscute drept Conditiile Coffman.

Majoritatea sistemelor de operare utilizate in momentul de fata, nu pot preveni aparitia unui interblocaj. Cand un interblocaj apare, sistemele de operare raspund in mod diferit, intr-o maniera non-standard. Majoritatea abordarilor Previn una dintre cele patru conditii Coffman, in special a patra.

Ignorarea interblocajelor

In aceasta abordare, se presupune ca interblocajele nu vor aparea niciodata. Aceasta este o aplicatie a algoritmului Ostrich. Aceasta maniera a fost intital folosita de MINIX si UNIX. Este folosita cand intervalele de timp intre aparitiile interblocajelor sunt mari si pierderea de date suportata de fiecare data este suportata. Este numit asa pentru efectul de strut, “a-ti baga capul in nisip si a te preface ca nu exista nicio problema” Este folosit atunci cand este mai eficient sa permiti problemei sa apara decat sa incerci sa o previ.

Detectarea

In aceasta situatie, interblocajele sunt lasate sa apara. Apoi starea sistemului este examinata pentru a detecta aparitia interblocajului si acesta este corectat. Un algoritm a fost implementat pentru a monitoriza alocarea de resurse si starile proceselor, deruleaza inapoi si reporneste unul sau mai multe proceste pentru a inlatura interblocajul detectat. Detectarea interblocajului care a aparut deja este posibila din moment ce resursele fiecarui process au fost blocate si/sau resursele care sunt cerute sunt in evidenta planificatorului de resurse al sistemului de operare.

Tehnicile de detectare a interblocajelor includ, dar nu sunt limitate la verificarea de modele. Aceasta abordare construieste un model-stare pe care indeplineste o analiza de progress si gaseste toate posibilele seturi terminale din cadrul modelului. Fiecare dintre acestea reprezinta un interblocaj. Dupa ce a fost detectat un interblocaj, el poate fi corectat folosind una din urmatoarele metode:

Terminarea de Proces: unul sau mai multe procese implicate intr-un interblocaj pot fi anulate. Putem allege sa anulam toate procesele implicate intr-un interblocaj. Acest lucru asigura ca interblocajul a fost rezolvat cu viteza. Dar costul este mare pentru ca se vor pierde calculi partiale. Sau putem alege sa anulam pe rand cate un proces pana cand interblocajul este rezolvat. Aceasta abordare are costuri generale mari pentru ca dupa fiecare anulare, un algoritm va trebui sa verifice daca sistemul inca se afla in interblocaj. Cativa factiori trebuie luati in considerare cand alegem ce proces trebuie sa fie terminat, precum prioritatea si varsta procesului.

Resurse Preferentiale: Resursele allocate diferitelor procese pot fi alese succesiv si allocate altor procese pana a cand interblocajul este rupt.

Figura 2 Exemplu de interblocaj

Prevenirea

Prevenirea interblocajelor inseamna sa prevenim una dintre cele patru conditii Coffman.

Inlaturarea Excluderii reciproce inseamna ca niciun procesnu trebuie sa aibe acces exclusive la o resursa. Dar chiar si asa, interblocajele pot aparea. Algoritmii ce evita excluderea reciproca se numesc algoritmi de sincronizare non-blocare.

Conditiile de Mentine si Asteapta sau Mentinere de Resurse pot fi inlaturate prin obligatia proceselor sa obtina toate resursele de care au nevoie inainte de a fi pornite(sau inainte de inceperea unui anumit set de operatii). Aceste cunostinte in avans sunt frecvent greu de satisfacut, si in orice caz, folosesc resursele in mod ineficient. O alta varianta ar fi obligatia proceselor sa obtina resurse doar atunci cand nu detin nicio resursa, astfel, ele trebuie mai intai sa elibereze toate resursele pe care le au inainte sa ceara toate resursele de care au nevoie. Acesti lucru este deseori nepractic. Este asa deoarece resursele pot fi alocate si raman neutilizate pentru perioade lungi de timp. De asemenea, un proces ce are nevoie de o resursa populara ar putea astepta un timp nedeterminat, deoarece aceasta resursa poate fi mereu alocata unui alt proces, rezultand astfel lipsa de resurse.

Conditia “Fara preferinte” poate fi si ea dificil sau chiar imposibil de evitat, pentru a evita ca un proces sa poata avea o resursa pentru o anumita perioada de timp sau rezultatul prelucrarii va fi inconsistent. Totusi, inabilitatea de a aplica preemtiunea poate interfera cu un algoritm de prioritate. Preemtiunea unei resurse blocate, in general, implica un rollback si ar fi de preferat sa fie evitat acest lucru deoarece este foarte costisitor. Algoritmii care permit preferentierea resurselor include algoritmi lock-free, wait-free si de contolul paralelismului. Aceasta conditie poate fi inlaturata dupa cum urmeaza: Daca un process ce detine resurse si cere alte resurse care nu pot fi imediat allocate lui, atunci elibereaza toate resursele ce sunt detinute de acel process.

Ultima conditie este asteptarea circular. Abordari care evita asteptarea circular includ dezactivarea intreruperilor dintr-o sectiune critica folosind o ierarhie sa determine ordinea resurselor. Daca nicio ierarhie nu exista, adresele de memorie ale resurselor sunt folosite pentru a determina ordinea. Se poate folosi si solutia Dijkstra.

Evitarea

Interblocajul poate fi evitat daca anumite informatii despre procese sunt disponibile sistemului de operare inainta alocarii resurselor, precum care resurse vor fi utilizate de care proces. Pentru fiecare cerere de resurse, sistemul verifica daca aprobarea cererii va duce la intrarea sistemului intr-o stare nesigura, ce poate duce la un interblocaj. Apoi sistemul aproba cererile care duc la o stare sigura. Pentru ca sistemul sa poata determina daca urmatoarea stare va fi sigura sau nu, el trebuie sa stie dinainte urmatoarele:

Resursele dispunibile din acel momen

Resursele alocate fiecarui proces din acel moment

Resursele care sunt necesare si resursele care vor fi eliberate de catre procese in viitor.

Este posibil pentru un proces sa fie intr-o stare nesigura dar cu toate astea sa nu existe un interblocaj. Notiunea de stare „sigura” / ”nesigura” se refera la abilitatea sistemului de a intra intr-un interblocaj sau nu. De exemplu, daca un proces necesita resursa A, primind-o va rezulta o stare nesigura, dar elibereaza resursa B cu care ar preveni o asteptare circulara, atunci starea va fi nesigura dar sistemul nu va intra intr-un interblocaj.

Un algoritm cunoscut care se foloseste pentru evitarea interblocajelor este algoritmul lui Banker, in care este necesara cunoasterea in avans a limitei utilizarii de resurse. Totusi, pentru multe sisteme este imposibil sa stim in avans ce va cere fiecare proces. Asta inseamna ca evitarea interblocajelor este de cele mai multe ori imposibila

Alti doi algoritmi sunt Wait/Die si Wound/Wait, ambii folosind o tehnica de rupere a simetriei. In ambele cazuri exista un proces mai vechi (O) si unul mai tanar (Y). Varsta proceselor poate fi determinata de un timestamp.

Algoritmul “Wait-Die”:

Este permisa asteptarea doar daca procesul mai vechi asteapta. Deoarece amprentele de timp cresc in orice lant de asteptare, ciclurile sunt imposibile.

El distruge procesele mai tinere. Cand procesul mai tanar reporneste si solicita iar resursa, el poate fi distrus inca o data.

Acest algoritm este mai putin eficient decat „Wound-Wait”.

Algoritmul „Wound-Wait”:

Este permisa asteptarea doar daca procesul mai tanar asteapta. Aici amprenetele de timp de timp scad in lantul de asteptare, asadar ciclurile sunt imposibile.

Este mai intelept sa aibă prioritate procesul mai vechi.

Cand o resursa necesara procesului mai vechi este detinuta de un proces mai tanar, acesta din urma ii cedeaza resursa si asteapta pana cand cel dinaintea lui termina.

Interblocajele distribuite pot aparea in sistemele distribuite atunci cand sunt folosite tranzactii distribuite sau controlul paralel. Interblocajele distribuite pot fi detectate de un detector de interblocaje ce construieste un graf „de asteptare” global din grafurile „de asteptare” locale sau de un algoritm distribuit precum „edge chasing”.

Interblocajele fantoma sunt interblocajele false ce sunt detectate intr-un system distribuit datorita intarzierilor interne ale sistemului. De exemplu, daca un proces elibereaza resursa R1 si transmite necesitatea resursei R2, iar primul mesaj s-a pierdut sau intarzie, coodonatorul (detectorul de interblocaje) ar putea detecta un interblocaj false (cererea pentru R2 este trimisa in timp ce R1 este detinuta ar putea realiza un interblocaj).

Unul dintre cei mai buni algoritmi de detectare a interblocajelor pentru sistemele distribuite este algoritmul „Chandy-Mistra-Hass”.

Daca un proces face o cerere pentru o resusra, iar aceasta cerere esueaza, procesul genereaza un mesaj sonda si il trimite la fiecare proces ce detine una sau mai multe din resursele cerute.

Fiecare mesaj sonda contine:

Id-ul procesului care este blocat (cel care a trimis mesajul sonda initial)

Id-ul procesului care trimite aceasta versiune al mesajului sonda

Id-ul procesului care ar trebui sa primeasca acest mesaj sonda

Cand un proces primeste un mesaj sonda, verifica daca si el asteapta resursele. Daca nu, verifica daca el foloseste resursele necesare si daca va termina si va elibera acele resurse. Daca si el asteapta resursele, trimite mesajul sonda la toate procesele care sunt cunoscute de el ca ar putea detine resurse. Procesul mai intai modifica mesajul sonda, schimband expeditorul si destinatarul. Daca un proces primeste un mesaj sonda pe care el l-a initiat, atunci stie ca exista un ciclu in sistem, adica un interblocaj.

Exemplu:

In acest caz P1 initiaza mesajul sonda, asa ca toate mesajele il vor avea pe P1 ca initiator. Cant mesajul sonda este primit de procesul P3, este modificat si trimis la alte doua procese. In cele din urma, mesajul sonda se reintoarce la procesul P1. Exista interblocaj.