logo

Bankiersalgoritme in besturingssysteem (OS)

Het is een bankiersalgoritme dat gewend is vermijd een impasse En middelen toewijzen veilig naar elk proces in het computersysteem. De ' S-staat' onderzoekt alle mogelijke tests of activiteiten alvorens te beslissen of de toewijzing aan elk proces moet worden toegestaan. Het helpt het besturingssysteem ook om de bronnen met succes tussen alle processen te delen. Het algoritme van de bankier wordt genoemd omdat het controleert of aan een persoon een leningsbedrag moet worden opgelegd of niet, om het banksysteem te helpen de toewijzing van middelen veilig te simuleren. In dit gedeelte leren we de Het algoritme van de bankier in detail. Ook lossen we problemen op op basis van de Het algoritme van de bankier . Om het bankiersalgoritme eerst te begrijpen, zullen we er een echt woordvoorbeeld van zien.

Stel dat het aantal rekeninghouders bij een bepaalde bank 'n' is, en het totale geldbedrag bij een bank 'T'. Als een rekeninghouder een lening aanvraagt; eerst trekt de bank het geleende bedrag af van het volledige contante geld en schat vervolgens dat het contante verschil groter is dan T om het geleende bedrag goed te keuren. Deze stappen worden genomen omdat als een andere persoon een lening aanvraagt ​​of een bedrag bij de bank opneemt, dit de bank helpt alle zaken te beheren en te exploiteren zonder enige beperking in de functionaliteit van het banksysteem.

Op dezelfde manier werkt het in een besturingssysteem . Wanneer een nieuw proces in een computersysteem wordt aangemaakt, moet het proces allerlei soorten informatie aan het besturingssysteem leveren, zoals aankomende processen, verzoeken om hun bronnen, het tellen ervan en vertragingen. Op basis van deze criteria beslist het besturingssysteem welke procesvolgorde moet worden uitgevoerd of gewacht, zodat er geen impasse in een systeem ontstaat. Daarom wordt het ook wel genoemd Algoritme voor het vermijden van impasses of detectie van impasse in het besturingssysteem.

Voordelen

Hieronder volgen de essentiële kenmerken van het algoritme van de bankier:

  1. Het bevat verschillende hulpmiddelen die voldoen aan de vereisten van elk proces.
  2. Elk proces moet informatie aan het besturingssysteem verstrekken over aankomende resourceaanvragen, het aantal resources en hoe lang de resources zullen worden vastgehouden.
  3. Het helpt het besturingssysteem bij het beheren en controleren van procesaanvragen voor elk type bron in het computersysteem.
  4. Het algoritme heeft een Max resource-attribuut dat aangeeft dat elk proces het maximale aantal bronnen in een systeem kan bevatten.

Nadelen

  1. Het vereist een vast aantal processen en er kunnen geen extra processen in het systeem worden gestart tijdens de uitvoering van het proces.
  2. Het algoritme staat niet langer toe dat de processen hun maximale behoeften uitwisselen tijdens het verwerken van hun taken.
  3. Elk proces moet vooraf de maximale benodigde middelen voor het systeem kennen en opgeven.
  4. Het aantal resourceaanvragen kan in een beperkte tijd worden ingewilligd, maar de tijdslimiet voor het toewijzen van de resources is één jaar.

Wanneer je met het algoritme van een bankier werkt, vraagt ​​het om drie dingen:

  1. Hoeveel elk proces kan vragen voor elke bron in het systeem. Het wordt aangegeven met de [ MAX ] verzoek.
  2. Hoeveel elk proces momenteel elke bron in een systeem vasthoudt. Het wordt aangegeven met de [ TOEGEWEZEN ] bron.
  3. Het vertegenwoordigt het aantal van elke bron die momenteel beschikbaar is in het systeem. Het wordt aangegeven met de [ BESCHIKBAAR ] bron.

Hieronder volgen de belangrijke termen voor datastructuren die als volgt in het algoritme van de bankier worden toegepast:

1 miljoen nummer

Stel dat n het aantal processen is, en m het aantal van elk type bron dat in een computersysteem wordt gebruikt.

    Beschikbaar: Het is een array met de lengte 'm' die elk type bron definieert dat beschikbaar is in het systeem. Wanneer Beschikbaar[j] = K, betekent dit dat 'K'-instanties van het resourcetype R[j] beschikbaar zijn in het systeem.Maximaal:Het is een [n x m]-matrix die aangeeft dat elk proces P[i] het maximale aantal bronnen R[j] (elk type) in een systeem kan opslaan.Toewijzing:Het is een matrix van m x n orders die het type bronnen aangeeft dat momenteel aan elk proces in het systeem is toegewezen. Wanneer Toewijzing [i, j] = K, betekent dit dat aan proces P[i] momenteel K exemplaren van het Bronnentype R[j] in het systeem zijn toegewezen.Behoefte:Het is een M x N-matrixreeks die het aantal resterende bronnen voor elk proces vertegenwoordigt. Wanneer de Need[i] [j] = k, kan proces P[i] K extra exemplaren van het resourcetype Rj nodig hebben om het toegewezen werk te voltooien.
    Nedd[i][j] = Max[i][j] - Toewijzing[i][j].Finish: Het is de vector van de bestelling M . Het bevat een Booleaanse waarde (true/false) die aangeeft of het proces is toegewezen aan de gevraagde bronnen, en of alle bronnen zijn vrijgegeven nadat de taak is voltooid.

Het bankiersalgoritme is de combinatie van het veiligheidsalgoritme en het algoritme voor het aanvragen van middelen om de processen te controleren en een impasse in een systeem te voorkomen:

Veiligheidsalgoritme

Het is een veiligheidsalgoritme dat wordt gebruikt om te controleren of een systeem zich in een veilige toestand bevindt of de veilige volgorde van het bankiersalgoritme volgt:

1. Er zijn twee vectoren Wok En Finish met lengte m en n in een veiligheidsalgoritme.

Initialiseren: Werk = Beschikbaar
Eindig[i] = onwaar; voor I = 0, 1, 2, 3, 4… n - 1.

2. Controleer de beschikbaarheidsstatus voor elk type bronnen [i], zoals:

Heb ik nodig]<= work
Eindig[i] == onwaar
Als de i niet bestaat, ga dan naar stap 4.

3. Werk = Werk + Toewijzing(i) // om nieuwe toewijzing van middelen te krijgen

Afwerking[i] = waar

Ga naar stap 2 om de status van de beschikbaarheid van resources voor het volgende proces te controleren.

4. Als Einde[i] == waar; het betekent dat het systeem veilig is voor alle processen.

Algoritme voor resourceverzoeken

Een algoritme voor resourceverzoeken controleert hoe een systeem zich zal gedragen wanneer een proces elk type resourceverzoek in een systeem als een verzoekmatrix doet.

Laten we voor elk proces P[i] een resourceverzoekarray R[i] maken. Als het resourceverzoeki[j] is gelijk aan 'K', wat betekent dat het proces P[i] 'k'-instanties van het resourcetype R[j] in het systeem vereist.

1. Wanneer het aantal gevraagde middelen van elk type is kleiner dan de Behoefte bronnen, ga naar stap 2 en als de voorwaarde mislukt, betekent dit dat het proces P[i] de maximale claim voor de bron overschrijdt. Zoals de uitdrukking suggereert:

Indien verzoek(i)<= need
Ga naar stap 2;

2. En als het aantal aangevraagde bronnen van elk type kleiner is dan de beschikbare bronnen voor elk proces, ga dan naar stap (3). Zoals de uitdrukking suggereert:

Indien verzoek(i)<= available
Anders moet proces P[i] wachten op de hulpbron, omdat deze niet beschikbaar is voor gebruik.

3. Wanneer de gevraagde bron aan het proces wordt toegewezen door de status te wijzigen:

Beschikbaar = Beschikbaar - Aanvraag
Toewijzing(i) = Toewijzing(i) + Verzoek (i)
Behoeftei= Behoeftei- Verzoeki

Wanneer de toestand van de toewijzing van hulpbronnen veilig is, worden de hulpbronnen ervan toegewezen aan het proces P(i). En als de nieuwe toestand onveilig is, moet proces P(i) wachten op elk type verzoek R(i) en de oude toestand van de toewijzing van hulpbronnen herstellen.

Voorbeeld: Beschouw een systeem dat vijf processen P1, P2, P3, P4, P5 en de drie resourcetypen A, B en C bevat. Hieronder volgen de resourcetypen: A heeft 10, B heeft 5 en het resourcetype C heeft 7 instanties.

Proces Toewijzing
A B C
Max
A B C
Beschikbaar
A B C
P1 0 1 0 7 5 3 3 3 2
P2 200 3 2 2
P3 3 0 2 9 0 2
P4 2 1 1 2 2 2
P5 0 0 2 4 3 3

Beantwoord de volgende vragen met behulp van het algoritme van de bankier:

  1. Wat is de referentie van de behoeftematrix?
  2. Bepaal of het systeem veilig is of niet.
  3. Wat gebeurt er als het systeemverzoek (1, 0, 0) voor proces P1 het systeem dit verzoek onmiddellijk kan accepteren?

Jaren. 2: De context van de behoeftematrix is ​​als volgt:

Behoefte [i] = Max [i] - Toewijzing [i]
Behoefte aan P1: (7, 5, 3) - (0, 1, 0) = 7, 4, 3
Behoefte aan P2: (3, 2, 2) - (2, 0, 0) = 1, 2, 2
Behoefte aan P3: (9, 0, 2) - (3, 0, 2) = 6, 0, 0
Behoefte aan P4: (2, 2, 2) - (2, 1, 1) = 0, 1, 1
Behoefte aan P5: (4, 3, 3) - (0, 0, 2) = 4, 3, 1

inorder boomtraversatie
Proces Behoefte
A B C
P1 7 4 3
P2 1 2 2
P3 6 0 0
P4 0 1 1
P5 4 3 1

Daarom hebben we de context van de behoeftematrix gecreëerd.

Antw. 2: Pas het algoritme van de bankier toe:

Beschikbare grondstoffen van A, B en C zijn 3, 3 en 2.

Nu controleren we of elk type resourceverzoek voor elk proces beschikbaar is.

Stap 1: Voor proces P1:

Behoefte<= available< p>

7, 4, 3<= 2 3, condition is vals.

We onderzoeken dus een ander proces, P2.

Stap 2: Voor proces P2:

Behoefte<= available< p>

1, 2, 2<= 2 3, condition WAAR

Nieuw beschikbaar = beschikbaar + Toewijzing

(3, 3, 2) + (2, 0, 0) => 5, 3, 2

Op dezelfde manier onderzoeken we een ander proces P3.

Stap 3: Voor proces P3:

P3 Behoefte<= available< p>

6, 0, 0<= 2 5, 3, condition is vals.

Op dezelfde manier onderzoeken we een ander proces, P4.

Stap 4: Voor proces P4:

P4 Behoefte<= available< p>

0, 1, 1<= 2 5, 3, condition is WAAR

Nieuwe beschikbare bron = Beschikbaar + Toewijzing

5, 3, 2 + 2, 1, 1 => 7, 4, 3

Op dezelfde manier onderzoeken we een ander proces P5.

Stap 5: Voor proces P5:

P5 Behoefte<= available< p>

4, 3, 1<= 3 7, 4, condition is WAAR

Nieuwe beschikbare bron = Beschikbaar + Toewijzing

7, 4, 3 + 0, 0, 2 => 7, 4, 5

Nu onderzoeken we opnieuw elk type resourceverzoek voor de processen P1 en P3.

Stap 6: Voor proces P1:

P1 Behoefte<= available< p>

7, 4, 3<= 5 7, 4, condition is WAAR

Nieuwe beschikbare bron = Beschikbaar + Toewijzing

7, 4, 5 + 0, 1, 0 => 7, 5, 5

We onderzoeken dus een ander proces P2.

Stap 7: Voor proces P3:

P3 Behoefte<= available< p>

6, 0, 0<= 5 7, 5, condition is true< p>

Nieuwe beschikbare bron = Beschikbaar + Toewijzing

7, 5, 5 + 3, 0, 2 => 10, 5, 7

Daarom voeren we het algoritme van de bankier uit om de veilige toestand en de veilige reeks zoals P2, P4, P5, P1 en P3 te vinden.

npm-cache wissen

Jaren. 3: Voor het inwilligen van het Verzoek (1, 0, 2) moeten we dat eerst controleren Verzoek<= available< strong>, dat wil zeggen (1, 0, 2)<= (3, 3, 2), since the condition is true. so process p1 gets request immediately.< p>