Definiti blocajul. deadlockUn set de procese este blocat daca fiecare process din setul respective asteapta un eveniment care poate fi cauzat doar de un alt process din acest set. Niciunul din procese nu poate rula, elibera resurse, sau sa treaca in starea awake. Ce este o resursa preemptibila?O resursa care poate fi luata de la procesul care o detine fara efecte nedorite. Memoria este un exemplu de resursa preemtibila. Ce este o resurs nonpreemptibila?Este o resursa care nu poate fi luata de la detinatorul ei fara ca executia acestuia sa esueze. Daca un process a inceput sa inscriptioneze un cd-rom, de exemplu, si deodata I se ia accesul la unitatea de inscriptionare si se da altui process, va rezulta un cd cu informative amestecata, fara sens. In general blocajele sunt non-preemtibile. Care sunt conditiile de aparitie a unui blocaj?-excluziune mutual o resursa este fie ocupata de un process, fie este libera-de detinere-asteptare a unei resurse : un process ce detine resurse poate solicita resurse noi-nonpreemtivitatii: resursele ocupate nu pot fi retrase fortat unui process.-de asteptare circular: lantul circular de asteptare este format din cel putin 2 procese, fiecare resursa solicitata este detinuta de urmatorul process din lantul circular. Cum se pot modela blocajele?Cu ajutorul grafurilor orientate. Grafurile au doua tipuri de noduri : procesele, reprezentate prin cercuri, si resursele, reprezentate prin patrate. Un arc de la un nod tip resursa catre un nod de tip process arata ca acea resursa a fost ceruta, accesul la ea a fost acordat si ea este in present detinuta de procesul respectiv. Caracterizati algoritmul strutului.Se bazeaza pe prezumtia ca nu exista blocaje. Prezumtia este rezonabila daca blocajele apar foarte rar sau costul prevenirii blocajelor este mare.Unix si Windows utilizeaza aceasta abordare. Este un compromise intre comoditate si corectitudine. Cum se realizeaz detectia si rezolvarea blocajelor?Cand se foloseste tehnica aceasta , sistemul nu incearca sa previna aparitia blocajelor. In schimb, le lasa sa apara, incearca sa detecteze cand ele se intampla si apoi sa ia masuri pt recuperare. Poate fi dentificat un ciclu care denota aparitia unui blocaj. In acest caz, se trece larezolvarea blocajelor :1.prin preemtiune. Eliberarea unei resurse allocate unui alt process; metoda dependent de natura resursei; 2. Prin rollback. Marcarea punctelor de executie ale uni process, salvarea starii unui process si utilizarea ei; restartarea procesului din punctual de executie marcat daca se identifica blocaj. 3. Oprirea proceselor. Sea mai simpla si eficienta metoda, pp. oprirea proceselor a caror executie poate fi rulata de la inceput de exemplu nu se opreste un process de actualizare a unei baze de date. Cum se evita blocajele?Evitarea permite sistemului intrarea n starea de interblocare i rezolv apoi aceast situaie, reprezentnd de multe ori o soluie destul de dificila i de costisitoare,presupune folosirea de informaii suplimentare referitoare la modul n careprocesele vor formula cererile de acces la resurse.Cunoscnd toat secvena de cereri i eliberari de resurse pentru fiecaredintre procese se poate hotr pentru fiecare cerere n parte dacva fi sau nu satisfcut. n cazul fiecrei formulri de cerere se impune ca sistemul sia n considerare resursele disponibile n momentul respectiv, resurselealocate deja, precumi viitoarele cereri i eliberari de resurse corespunztoare fiecrui proces, pentru a putea decide dac cererea curent poate fi satisfcutsau trebuie s atepte n vederea evitrii apariiei unei interblocri.Pentru implementarea acestei metode se folosesc n prezent mai muli algoritmi care difer ntre ei prin tipul i cantitatea de informaie necesar. Caracterizati starea sigura si nesigura.O stare este numita sigura-safe- daca sistemul nu se afla in interblocare in acel moment si exista o ordine de planificare in care fiecare process poate rula pana la terminare, chiar daca procesele arc ere deodata numarul lor maxim de resurse.O stare nesigura nu este o stare in care sistemul se afla in interblocare. Dintr-o astefel de stare nu se poate garanta faptul ca toate procesele se vor termina, pe cand la cea sigur avem aceasta garantie. Caracterizati algoritmul bancherului pentru o singura resursaUn algoritm de planificare care poate evita blocajele este o extensie a lgoritmului de detectare a blocajelor. Algoritmul este modelat dupa felul in care un bancher dintr-un oras mic gestioneaza un grup de client carora le-a deschis linii de credit. Acesta verifica daca acceptrea unei cereri va duce la o stare nesigura.Daca da, cererea este respinsa. Daca cererea duce la o stare sigura, ea este indeplinita. Algoritmul ia in considereare fiecare cerere pe masura aparitiei ei si se uita daca acceptarea va duce la o stare sigura. Pentru a verifica asta, verifica daca are suficiente resurse pentru a satisface cativ client. IN caz ca are, se presupune ca aceste imprumuturi vor fi returnate si in continuare va fi verificat clientul cel mai apropiat de limita si asa mai departe. Daca toate imprumuturile pot fi retunate, starea este sigura si cererea initiate va fi acceptata. Caracterizati algoritmul bancherului pentru resurse multiple.Cauta pe rand, un R, ale carui nevoi de resurse sunt mai mici sau egale cu A. Daca nu exista niciun astfel de rand, sistemul se va bloca in cele din durma deoarece niciun process nu va putea relua pana la terminare. Presupunem ca procesul ales cere toate resursele de care are nevoie si se termina. Marcheaza acest proces ca fiind terminat si adauga toate resursele in vectorul A. Repeta acesti pasi fie pana cand toate procesele sunt marcate ca fiind terminate, in acest caz starea initiala este sigura, fie pana cand aparet un blocaj, caz in care starea initiala este nesigura. Acest algoritm este foarte bine reliefat in teorie, dar practice este nefolositor deoarece rareori procesle stiu in avans care vor fi nevoile lor maxime de resurse, iar numarul de procese variaz pe masura ce apar sau dispar utilizatori. Cum se previn blocajele? Blocajele se previn cu ajutorula patru conditii. Daca ne asiguram ca cel putin una dintre ele nu va fi niciodata satisfacuta, atunci este imposibil sa apara blocaje.1.Combaterea contidiei de excludere mutuala. Daca nicio resursa nu ar fi alocata exclusive pt un rproces, nu am avea niciodata blocaje. Totusi, daca am permite ca doua procese sa scrie in acelasi timp s-ar crea haos. Prin introducere in coasa de asteptare(spooling) mai multe rpocese pot genera simultan date de iesire. Insa, nu toate dispozitivele pot face spooling. Procesele care gestioneaza o actiune, sunt programate sa actioneze doar dup ace sunt disponibile doate datele de iesire. In acest caz avem doua procese care au furnizat fiecare o parte din datele de iesire, dar nu toate si de acees nu se poate continua. Niciunul dintre procese nu se va termina vreodata, asadar avem un blocaj. Totusi frecvent, se evita alocarea unei resurse cand aceasta nu este absolute necesara si se incearca asigurarea ca vor exista ca mai putine procese care ar putea cere resursa.2. Combaterea conditiei de detinere si asteptare. Daca am putea impiedica procesele care detin resurse sa mai astepte prolucrarea altor resurse, am pute alumina blocajele. Un mod de a face asta este sa le cerem tuturor proceseloe sa ceara toate resursele inainte de inceperea executiei. Daca totul este disponbil, procesului ii va fi alocat tot ceea ce ii trebuie si va putea rula pana se va termina. Daca una sau mai multe resurse sunt ocupate, nu se va aloca nimic si procesul doar va astepta. Un alt mode de combatere a cond de detinere si asteptare este ca fiecarui process care doreste o resursa sa I s e ceara sa elibereze temporar toate resursele pe care le detine in present. Apoi va incerca sa ia dintr-o data tot ce are nevoie.3.Combaterea lipsei de preeemptie este destul de rar folosita . Daca uni process i-a fost alocata imprimanta de ex, si se afla in mijlocul tiparirii datelor de iesire, faptul ca I s-ar lua fortat imprimanta deoarece un trasator cerut nu este disponibil, ar fi derutant sau chiar imposibil.4. Combaterea conditiei de asteptare circular. Asteptarea circular poate fi eliminate in mai multe fe;luri. Un mod ar fi sa impunem regula ca orice process are dreptul la o singura resursa la un moment dat. Daca are nevoie de o a doua, trebuie sa o elibereze pe prima. Pt un proces care are nevoie sa scoata la imprimanta un fisier urias pe o banda magnetic, aceasta restrictive este inacceptabila. Un at mod ar fi realizarea unei numerotari globale a resurselor. Regula este urmatoarea : procesele pot cere resurse oricand vor, dar toate cererile rebuiesc facute in ordinea numerelor. Un process poate cere mai intai o imprimanta si apoi o banda magnetic, dar nu va putea cere mai intai un trasator si apoi o imprimanta.Cu aceasta regula, nu pot exista niciodata cilcuri. Desi ordonarea numerica a resurselor elimiba problema blocajelor, ar putea fi indisponibila alegerea unei ordini in care sa satisfaca pe toata lumea. Cand resursele include intrari in tabela de procese, spatial de pe disc alocat pt spooling, intregistrari detinute din baza de date si alte surse, atat ele cat si diverse folosiri pot fi atat de numeroase a.i. nicio abordare nu mai este posibila. Explicati si dati exemplu de two-phase blocking.Desi atat evitarea cat si prevenirea blocajelor nu sunt foarte promitatoare, in multe sisteme de date, o operatie care apare frecvent este blocarea ccesului ca cateva inregistrari si avoi vizualizarea lor. In momentul in care exista mai multe procese care ruleaza in acelasi timp exista un real risc de aparitie a interblocarii. Abordarea folosita este denumita blocarea in doua faze. Aici, procesul incearca mai intai sa blocheze accesul pe rand la toate inregistrarile de care are nevoie. Dca reusese, incepe faza a doua in care realizeza actualizarile si apoi blocheaza accesul. In rima faza nu este realizata nicio modificcare. Daca in prima faza este nevoie de o inregistrare care este dj blocata de altcineva, procesul deblocheaza toate inregistrarile si reia aceasta etapa. Intr-un anumit sens aceasta abordare este similara cu cereaza in avans a tuturor resurselor necesar, sau cel putin inainte de a se realize ceva ireversibil. In ultimele versiuni ale blocarii in doaua faze nu are loc eliberarea si reluarea in cazul in care prima faza este intalnita cu o resursa dj blocata. In aceste versiuni poate aparea un blocaj. Algoritmul functioneaza doar in acele situatii in care programatorul are lucrurile aranjate foarte atent astfel incat programul sa poata fi oprit in orice punct in timpul unei faze si reluat. Multe aplicatii nu pot fi structurate in acest fel. Explicati si dati exemplu de comunication deadlock.Dou procese se pot bloca chiar dac nu doresc partajarea aceleiai resurse: Procesul A trimite o cerere ctre procesul B. Procesul A intr n starea blocked pn la recepionarea unui mesaj de la procesul B. Procesul B trimite mesaj ctre procesul A i intr la rndul su n starea blocked. Mesajul se pierde i ambele procese sunt blocate.

Exemplificati notiunea de starvation.Intr-un system dynamic, au tot timpul loc cereri de resurse. Este necesara o politica pt a stabili cine sa ia o anumita resursa sic and. Aceasta politica, dei pare rezonabila, poate duce sa ramanerea in asteptare a unor procee care nu vor fi niciodata luate in considerere, desi ele nu se afla in blocaj. Ca exemplu , sa luam alocarea imprimantei. Sa ne imaginam sa un system foloseste un anumit tip de algoritm pt a se asigura ca alocarea imprmantei nu duce la interblocare. Sa presupunem ca acum exista cateva procese cre o vor toate deosata. Care o va primii? Un posibil algoritm de alocare este ca ea sa fie data asta procesului cu fisierul cel mai mic de tiparit . Aceasta abordare maximizeaza numarul clientilor fericiti. Daca un system aglomerat are un fiesier urias de tiparit, de fiecare data cand imprimanta este libera, se va uita in jur-sistemul- si va allege procesul cu fisierul cel mai mic. Dca nu exista un flux constant de procese cu fisiere mici, imprimanta nu-I va fi alocata niciodata procesului cu fisierul uriam. Pur si simplu acesta va muri de foame(amanat la nesfarsit, chair daca nu e blocat). Infometarea poate fi evitata prin folosirea unor politici de locare a resurselor de tip primul sosit primul servit. In aceasta abordare este servit procesul care a asteptat cel mai mult. In timp, fiecare process va devein in cele din urma cel mai vechi si astfel isi va primi resursa de care are nevoie.