7.5 - Deadlock Avoidance (p.328)
- Zorgen dat ten minste een van de 4 condities niet voor kan komen (zie paragraaf deadlock characteristics).
- Door het gebruik van meer informatie kan het systeem betere beslissingen maken mbt welke requests voor anderen gaan (aka priori information).
- Deze informatie bevat het maximum aantal van elk resource dat een process mogelijk gaat gebruiken.
- Sommige (complexere) algoritmes kunnen ook gebruik maken van de volgorde van de op te vragen resources.
- Wanneer de scheduler ziet dat een process of het toekennen van resources voor een potentiele deadlock kan zorgen wordt het process niet gestart of de resources niet toegewezen.
- De recource allocation status wordt gedefieerd van het aantal beschikbare en toegewezen resources, en de maximum aanvragen van alle processen in het systeem.
Safe State
NB. Een voorbeeld hiervan staat op p.330, of in de sheets van college 5 sheet 33.
- Deadlock avoidance algorithm.
- Safe Sequence = Het systeem is safe wanneer het systeem alle resources kan toewijzen aan alle processen (tot het door hun gestelde maximum) zonder in een deadlock te gaan.
- Als alle processen voor een bepaald process finishen, dan kan het bepaalde process ook finishen.
- Deze processen hoeven niet perse in 0-1-2-3 volgorde te zijn, dat kan ook 3-1-2-0 zijn.
- Unsafe state = Wanneer een systeem geen safe sequence van processen heeft, dan KAN dit tot een deadlock leiden, maar dat hoeft niet.
- Wanneer het syteem in een safe state is kan er geen deadlock voorkomen.
Resource Allocation Graph Algorithm
- Wanneer er een enkele instantie is van een resource type.
- Ex. Specifieke geheugen regio of bestand.
- Wanneer er een cyclus (circle) van pijlen ontstaat is het systeem dus niet in een safe state.
- Maakt gebruik van Claim Edges (zie System Model paragraaf over de RAG)
Bankers Algorithm
- Wanneer er meerdere instanties zijn van een resource type.
- Ex. Meerdere CPUs.
- Bankers Algortithm = Resources voor een process worden alleen uitgeleend aan het process wanneer het maximaal nodige resources die het process ooit nodig kan hebben ook daadwerkelijk beschikbaar is.
- Naam komt van bankiers, welke alleen hun geld uitleenden mits ze zeker wisten dat ze ook aan hun verwachtingen konden voldoen
- Ex. Een bankier zal geen geld uitlenen aan de bouw van een huis, mits ze er zeker van zijn dat ze ook de rest van het geld voor de bouw van het huis kunnen uitlenen.
- Hoe werkt het?
- Een process komt het systeem binnen.
- Het process geeft aan het maximum aantal instanties van elk resource die het ooit nodig kan hebben door.
- Dit nummer mag niet het maximum aantal resources in het systeem overtreffen.
- Het process doet de reqest voor de resources.
- Het systeem controleert of het toewijzen van deze resources het systeem wel in een safe state achterlaat.
- Wanneer dit niet het geval is wordt de request uitgesteld totdat stap 4 wel kan.
- Bepaalde gegevens moeten worden bewaard om het algoritme te laten werken:
- Nb. n is het aantal processen, m is het aantal verschillende typen resources.
Available[m]= Array welke aangeedt hoeveel van elk recource beschikbaar zijn.Max[n][m]= Tweedimentionale array welke aangeeft wat het maximum aantal benodigde resouces zijn per process.Allocation[n][m]= Tweedimentionale array welke aangeeft hoeveel van elk resource is toegewezen aan elk process.Need[n][m]= Tweedimentionale array welke aangeeft hoeveel van elk resouce nog nodig is voor elk process.Need = Max - Allocation
Het specifieke gedeelte over de Safety en Resource-Request Alogrithme heb ik overgeslagen. (Het boek is hier tamelijk vaag over en er wordt niets specifieks over genoemd in de sheets).
Rekenen met het Bankers Algorithm
Een video met redelijk goede uitleg hierover: HIER
- Op een gegeven moment (T0) wordt een snapshot gemaakt.
- Stel we hebben:
- Process P0 - P4 met allocation en max gegevens
- Resource A: 10 instances
- Resource B: 5 instances
- Resource C: 7 instances
- Hoe?:
- We kunnen deze tabel opstellen, en dan weten we ook hoeveel resources er nog beschikbaar zijn.
- We kunnen uitrekenen hoeveel van elke resources we nog beschikbaar hebben
- Ook kunnen we bepalen hoeveel elk process nog nodig heeft door:
NEED = MAX - ALLOCATION - We zoeken naar een process waarvan de MAX waarde kan worden geallocceerd.
- P0 werkt niet, want daar hebben we nog 743 voor nodig.
- P1 kan wel, we hebben 332 en we hebben nodig 122.
- Dus die doen we.
- De Sequence is dan als volgt:
<P1>
- De resources van P1 worden vrijgegeven waar door we nu (T1) hebben:
- We zoeken naar een process waarvan de MAX waarde kan worden geallocceerd.
- P0 kan nog steeds niet.
- P2 kan ook niet, we hebben 532 maar nodig 600. (te weinig A)
- P3 Kan wel, we hebben 532 en hebben nodig 011.
- Dus die doen we.
- De Sequence is dan als volgt:
<P1, P3>
- De resources van P2 worden vrijgegeven waar door we nu (T2) hebben:
- We herhalen deze bewerking steeds waardoor we uiteindidelijk de volgende sequence met requests hebben die veilig achter elkaar kan worden uitgevoerd:
<P1, P3, P4, P2, P0>- Hierdoor is de safe state van het systeem gegarandeerd. Omdat er genoeg resources zijn om de processen uit te voeren.
- We kunnen deze tabel opstellen, en dan weten we ook hoeveel resources er nog beschikbaar zijn.
