logo

Bankers algoritme i operativsystem (OS)

Det er en bankalgoritme vant til unngå vranglås og allokere ressurser trygt til hver prosess i datasystemet. den ' S-stat' undersøker alle mulige tester eller aktiviteter før det bestemmes om tildelingen skal tillates til hver prosess. Det hjelper også operativsystemet med å dele ressursene mellom alle prosessene. Bankmannens algoritme er navngitt fordi den sjekker om en person skal ilegges et lånebeløp eller ikke for å hjelpe banksystemet med å simulere allokeringsressurser på en sikker måte. I denne delen vil vi lære Bankers algoritme i detalj. Vi vil også løse problemer basert på Bankers algoritme . For å forstå Bankers Algorithm først vil vi se et ekte ordeksempel på det.

Anta at antallet kontoinnehavere i en bestemt bank er 'n', og de totale pengene i en bank er 'T'. Hvis en kontoinnehaver søker om lån; først trekker banken lånebeløpet fra hele kontanter og estimerer deretter kontantdifferansen som er større enn T for å godkjenne lånebeløpet. Disse trinnene tas fordi hvis en annen person søker om et lån eller tar ut et beløp fra banken, hjelper det banken med å administrere og drive alle ting uten noen begrensning i funksjonaliteten til banksystemet.

På samme måte fungerer det i en operativsystem . Når en ny prosess opprettes i et datasystem, må prosessen gi alle typer informasjon til operativsystemet som kommende prosesser, forespørsler om ressursene deres, telling av dem og forsinkelser. Basert på disse kriteriene, bestemmer operativsystemet hvilken prosesssekvens som skal kjøres eller ventes slik at det ikke oppstår noen dødlås i et system. Derfor er det også kjent som algoritme for å unngå dødlås eller deteksjon av vranglås i operativsystemet.

Fordeler

Følgende er de essensielle egenskapene til bankmannens algoritme:

  1. Den inneholder ulike ressurser som oppfyller kravene til hver prosess.
  2. Hver prosess skal gi informasjon til operativsystemet for kommende ressursforespørsler, antall ressurser og hvor lenge ressursene vil bli holdt.
  3. Det hjelper operativsystemet med å administrere og kontrollere prosessforespørsler for hver type ressurs i datasystemet.
  4. Algoritmen har et Maks ressursattributt som representerer indikerer at hver prosess kan inneholde maksimalt antall ressurser i et system.

Ulemper

  1. Det krever et fast antall prosesser, og ingen ekstra prosesser kan startes i systemet mens prosessen utføres.
  2. Algoritmen lar ikke lenger prosessene utveksle sine maksimale behov mens de behandler oppgavene.
  3. Hver prosess må kjenne til og angi sitt maksimale ressursbehov på forhånd for systemet.
  4. Antall ressursforespørsler kan innvilges på en begrenset tid, men fristen for tildeling av ressursene er ett år.

Når du arbeider med en bankers algoritme, ber den om å vite om tre ting:

  1. Hvor mye hver prosess kan kreve for hver ressurs i systemet. Det er betegnet med [ MAKS ] be om.
  2. Hvor mye hver prosess for øyeblikket inneholder hver ressurs i et system. Det er betegnet med [ TILDELT ] ressurs.
  3. Det representerer nummeret på hver ressurs som for øyeblikket er tilgjengelig i systemet. Det er betegnet med [ TILGJENGELIG ] ressurs.

Følgende er de viktige datastrukturbegrepene som brukes i bankmannens algoritme som følger:

Anta at n er antall prosesser, og m er antallet av hver type ressurs som brukes i et datasystem.

    Tilgjengelig: Det er en matrise med lengde 'm' som definerer hver type ressurs som er tilgjengelig i systemet. Når Tilgjengelig[j] = K, betyr at 'K'-forekomster av Ressurstype R[j] er tilgjengelige i systemet.Maks:Det er en [n x m] matrise som indikerer at hver prosess P[i] kan lagre maksimalt antall ressurser R[j] (hver type) i et system.Tildeling:Det er en matrise av m x n ordrer som indikerer hvilken type ressurser som for tiden er allokert til hver prosess i systemet. Når Allokering [i, j] = K, betyr det at prosess P[i] for øyeblikket er tildelt K instanser av Ressurstype R[j] i systemet.Trenge:Det er en M x N matrisesekvens som representerer antall gjenværende ressurser for hver prosess. Når Behov[i] [j] = k, kan prosess P[i] kreve K flere forekomster av ressurstype Rj for å fullføre det tildelte arbeidet.
    Nedd[i][j] = Maks[i][j] - Allokering[i][j].Bli ferdig: Det er vektoren for ordren m . Den inkluderer en boolsk verdi (true/false) som indikerer om prosessen har blitt allokert til de forespurte ressursene, og alle ressursene er frigitt etter at oppgaven er fullført.

The Banker's Algorithm er kombinasjonen av sikkerhetsalgoritmen og ressursforespørselsalgoritmen for å kontrollere prosessene og unngå dødlås i et system:

Sikkerhetsalgoritme

Det er en sikkerhetsalgoritme som brukes til å sjekke om et system er i sikker tilstand eller ikke følger den sikre sekvensen i en bankers algoritme:

1. Det er to vektorer Wok og Bli ferdig av lengde m og n i en sikkerhetsalgoritme.

Initialiser: Arbeid = Tilgjengelig
Fullfør[i] = usann; for I = 0, 1, 2, 3, 4… n - 1.

2. Sjekk tilgjengelighetsstatusen for hver type ressurser [i], for eksempel:

Trenger[i]<= work
Fullfør[i] == usann
Hvis i-en ikke eksisterer, gå til trinn 4.

3. Arbeid = Arbeid +Tildeling(i) // for å få ny ressursallokering

Fullfør[i] = sant

Gå til trinn 2 for å sjekke status for ressurstilgjengelighet for neste prosess.

4. Hvis Finish[i] == sant; det betyr at systemet er trygt for alle prosesser.

Algoritme for ressursforespørsel

En ressursforespørselsalgoritme sjekker hvordan et system vil oppføre seg når en prosess gjør hver type ressursforespørsel i et system som en forespørselsmatrise.

La lage en ressursforespørselsmatrise R[i] for hver prosess P[i]. Hvis ressursforespørselenJeg[j] lik 'K', som betyr at prosessen P[i] krever 'k'-instanser av Ressurstype R[j] i systemet.

1. Når antall etterspurte ressurser av hver type er mindre enn Trenge ressurser, gå til trinn 2 og hvis betingelsen mislykkes, noe som betyr at prosessen P[i] overskrider dets maksimale krav for ressursen. Som uttrykket antyder:

Hvis forespørsel(i)<= need
Gå til trinn 2;

2. Og når antallet forespurte ressurser av hver type er mindre enn den tilgjengelige ressursen for hver prosess, går du til trinn (3). Som uttrykket antyder:

Hvis forespørsel(i)<= available
Ellers må prosess P[i] vente på ressursen siden den ikke er tilgjengelig for bruk.

3. Når den forespurte ressursen er allokert til prosessen ved å endre tilstand:

Tilgjengelig = Tilgjengelig - Forespørsel
Tildeling(i) = Tildeling(i) + Forespørsel (i)
TrengeJeg= TrengerJeg- Be omJeg

Når ressursallokeringstilstanden er trygg, allokeres ressursene til prosessen P(i). Og hvis den nye tilstanden er usikker, må prosess P(i) vente på hver type forespørsel R(i) og gjenopprette den gamle ressursallokeringstilstanden.

Eksempel: Tenk på et system som inneholder fem prosesser P1, P2, P3, P4, P5 og de tre ressurstypene A, B og C. Følgende er ressurstypene: A har 10, B har 5 og ressurstypen C har 7 instanser.

Prosess Tildeling
A B C
Maks
A B C
Tilgjengelig
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

Svar på følgende spørsmål ved hjelp av bankmannens algoritme:

  1. Hva er referansen til behovsmatrisen?
  2. Finn ut om systemet er trygt eller ikke.
  3. Hva vil skje hvis ressursforespørselen (1, 0, 0) for prosess P1 kan systemet godta denne forespørselen umiddelbart?

år. 2: Konteksten til behovsmatrisen er som følger:

js global variabel

Behov [i] = Maks [i] - Tildeling [i]
Behov for P1: (7, 5, 3) - (0, 1, 0) = 7, 4, 3
Behov for P2: (3, 2, 2) - (2, 0, 0) = 1, 2, 2
Behov for P3: (9, 0, 2) - (3, 0, 2) = 6, 0, 0
Behov for P4: (2, 2, 2) - (2, 1, 1) = 0, 1, 1
Behov for P5: (4, 3, 3) - (0, 0, 2) = 4, 3, 1

Prosess Trenge
A B C
P1 7 4 3
P2 1 2 2
P3 6 0 0
P4 0 1 1
P5 4 3 1

Derfor skapte vi konteksten for behovsmatrise.

Ans. 2: Bruk bankmannens algoritme:

Tilgjengelige ressurser for A, B og C er 3, 3 og 2.

Nå sjekker vi om hver type ressursforespørsel er tilgjengelig for hver prosess.

Trinn 1: For prosess P1:

Trenge<= available< p>

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

Så vi undersøker en annen prosess, P2.

Steg 2: For prosess P2:

Trenge<= available< p>

1, 2, 2<= 2 3, condition ekte

Ny tilgjengelig = tilgjengelig + Tildeling

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

På samme måte undersøker vi en annen prosess P3.

Trinn 3: For prosess P3:

P3 trenger<= available< p>

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

På samme måte undersøker vi en annen prosess, P4.

Trinn 4: For prosess P4:

P4 trenger<= available< p>

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

Ny tilgjengelig ressurs = Tilgjengelig + Allokering

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

På samme måte undersøker vi en annen prosess P5.

Trinn 5: For prosess P5:

P5 trenger<= available< p>

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

Ny tilgjengelig ressurs = Tilgjengelig + Tildeling

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

Nå undersøker vi igjen hver type ressursforespørsel for prosessene P1 og P3.

Trinn 6: For prosess P1:

P1 trenger<= available< p>

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

Ny tilgjengelig ressurs = Tilgjengelig + tildeling

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

Så vi undersøker en annen prosess P2.

Trinn 7: For prosess P3:

P3 trenger<= available< p>

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

Ny tilgjengelig ressurs = Tilgjengelig + tildeling

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

Derfor utfører vi bankmannens algoritme for å finne den sikre tilstanden og den sikre sekvensen som P2, P4, P5, P1 og P3.

år. 3: For å innvilge forespørselen (1, 0, 2), må vi først sjekke det Be om<= available< strong>, det vil si (1, 0, 2)<= (3, 3, 2), since the condition is true. so process p1 gets request immediately.< p>