logo

Algoritmo del banchiere nel sistema operativo (OS)

È un algoritmo bancario utilizzato per evitare lo stallo E allocare risorse in modo sicuro a ciascun processo nel sistema informatico. IL ' Stato S' esamina tutti i possibili test o attività prima di decidere se consentire l'allocazione a ciascun processo. Aiuta anche il sistema operativo a condividere con successo le risorse tra tutti i processi. L'algoritmo del banchiere è così chiamato perché controlla se una persona debba essere sanzionata per l'importo del prestito o meno per aiutare il sistema bancario a simulare in modo sicuro le risorse di allocazione. In questa sezione impareremo il Algoritmo del banchiere in dettaglio. Inoltre, risolveremo i problemi in base a Algoritmo del banchiere . Per comprendere prima l'algoritmo del banchiere ne vedremo un esempio reale.

Supponiamo che il numero di titolari di conti in una particolare banca sia 'n' e che il denaro totale in una banca sia 'T'. Se il correntista richiede un prestito; in primo luogo, la banca sottrae l’importo del prestito dall’intera liquidità e quindi stima che la differenza di cassa sia maggiore di T per approvare l’importo del prestito. Questi passaggi vengono adottati perché se un'altra persona richiede un prestito o ritira una somma dalla banca, ciò aiuta la banca a gestire e far funzionare tutte le cose senza alcuna restrizione nella funzionalità del sistema bancario.

Allo stesso modo, funziona in an sistema operativo . Quando viene creato un nuovo processo in un sistema informatico, il processo deve fornire tutti i tipi di informazioni al sistema operativo come processi imminenti, richieste di risorse, conteggio e ritardi. Sulla base di questi criteri, il sistema operativo decide quale sequenza di processo deve essere eseguita o attesa in modo che non si verifichi uno stallo in un sistema. Pertanto, è anche noto come Algoritmo per evitare lo stallo O rilevamento dello stallo nel sistema operativo.

Vantaggi

Di seguito sono riportate le caratteristiche essenziali dell'algoritmo del Banker:

  1. Contiene varie risorse che soddisfano i requisiti di ciascun processo.
  2. Ciascun processo dovrebbe fornire informazioni al sistema operativo sulle richieste di risorse imminenti, sul numero di risorse e sulla durata di conservazione delle risorse.
  3. Aiuta il sistema operativo a gestire e controllare le richieste di processo per ogni tipo di risorsa nel sistema informatico.
  4. L'algoritmo ha un attributo Max Resource che rappresenta indica che ogni processo può contenere il numero massimo di risorse in un sistema.

Svantaggi

  1. Richiede un numero fisso di processi e non è possibile avviare processi aggiuntivi nel sistema durante l'esecuzione del processo.
  2. L'algoritmo non consente più ai processi di scambiarsi i massimi bisogni durante l'elaborazione dei propri compiti.
  3. Ogni processo deve conoscere e dichiarare in anticipo il proprio fabbisogno massimo di risorse per il sistema.
  4. Il numero di richieste di risorse può essere concesso in un tempo finito, ma il limite temporale per l'assegnazione delle risorse è di un anno.

Quando si lavora con l'algoritmo di un banchiere, viene richiesto di conoscere tre cose:

  1. Quanto ciascun processo può richiedere per ciascuna risorsa nel sistema. È indicato con [ MASSIMO ] richiesta.
  2. Quanto ciascun processo detiene attualmente ciascuna risorsa in un sistema. È indicato con [ ASSEGNATO ] risorsa.
  3. Rappresenta il numero di ciascuna risorsa attualmente disponibile nel sistema. È indicato con [ DISPONIBILE ] risorsa.

Di seguito sono riportati i termini importanti delle strutture dati applicati nell'algoritmo del banchiere:

array Java ordinato

Supponiamo che n sia il numero di processi e m sia il numero di ciascun tipo di risorsa utilizzata in un sistema informatico.

    Disponibile: È un array di lunghezza 'm' che definisce ogni tipo di risorsa disponibile nel sistema. Quando Disponibile[j] = K, significa che nel sistema sono disponibili istanze 'K' di tipo Risorse R[j].Massimo:È una matrice [n x m] che indica che ciascun processo P[i] può immagazzinare il numero massimo di risorse R[j] (ciascun tipo) in un sistema.Assegnazione:È una matrice di m x n ordini che indica il tipo di risorse attualmente allocate a ciascun processo nel sistema. Quando Allocazione [i, j] = K, significa che al processo P[i] sono attualmente allocate K istanze di tipo Risorse R[j] nel sistema.Bisogno:È una sequenza di matrice M x N che rappresenta il numero di risorse rimanenti per ciascun processo. Quando Necessità[i] [j] = k, il processo P[i] può richiedere K più istanze di risorse di tipo Rj per completare il lavoro assegnato.
    Nedd[i][j] = Max[i][j] - Allocazione[i][j].Fine: È il vettore dell'ordine M . Include un valore booleano (vero/falso) che indica se il processo è stato assegnato alle risorse richieste e tutte le risorse sono state rilasciate dopo aver terminato l'attività.

L'algoritmo del banchiere è la combinazione dell'algoritmo di sicurezza e dell'algoritmo di richiesta delle risorse per controllare i processi ed evitare situazioni di stallo in un sistema:

Algoritmo di sicurezza

È un algoritmo di sicurezza utilizzato per verificare se un sistema è o meno in uno stato sicuro o segue la sequenza sicura nell'algoritmo di un banchiere:

1. Esistono due vettori Wok E Fine di lunghezza m e n in un algoritmo di sicurezza.

Inizializza: Lavoro = Disponibile
Fine[i] = falso; per I = 0, 1, 2, 3, 4… n - 1.

2. Controllare lo stato di disponibilità per ciascun tipo di risorsa [i], come ad esempio:

Bisogno[i]<= work
Fine[i] == falso
Se la i non esiste, vai al passaggio 4.

3. Lavoro = Lavoro + Allocazione(i) // per ottenere una nuova allocazione delle risorse

Fine[i] = vero

Andare al passaggio 2 per verificare lo stato della disponibilità delle risorse per il processo successivo.

4. Se Fine[i] == vero; significa che il sistema è sicuro per tutti i processi.

Algoritmo di richiesta di risorse

Un algoritmo di richiesta di risorse controlla come si comporterà un sistema quando un processo effettua ogni tipo di richiesta di risorsa in un sistema come matrice di richiesta.

Creiamo un array di richieste di risorse R[i] per ciascun processo P[i]. Se la richiesta di risorseio[j] uguale a 'K', il che significa che il processo P[i] richiede 'k' istanze di tipo Risorse R[j] nel sistema.

1. Quando il numero di risorse richieste di ciascun tipo è inferiore a Bisogno risorse, vai al passo 2 e se la condizione fallisce, significa che il processo P[i] supera la sua richiesta massima per la risorsa. Come suggerisce l'espressione:

Se Richiesta(i)<= need
Vai al passaggio 2;

2. E quando il numero di risorse richieste di ciascun tipo è inferiore alla risorsa disponibile per ciascun processo, andare al passaggio (3). Come suggerisce l'espressione:

Se Richiesta(i)<= available
Altrimenti il ​​processo P[i] deve attendere la risorsa poiché non è disponibile per l'uso.

3. Quando la risorsa richiesta viene allocata al processo cambiando stato:

Disponibile = Disponibile - Richiesta
Assegnazione(i) = Assegnazione(i) + Richiesta (i)
Bisognoio= Bisognoio- Richiestaio

Quando lo stato di allocazione delle risorse è sicuro, le sue risorse vengono allocate al processo P(i). E se il nuovo stato non è sicuro, il processo P (i) deve attendere ogni tipo di richiesta R (i) e ripristinare il vecchio stato di allocazione delle risorse.

Esempio: Considera un sistema che contiene cinque processi P1, P2, P3, P4, P5 e i tre tipi di risorsa A, B e C. Di seguito sono riportati i tipi di risorse: A ha 10, B ha 5 e il tipo di risorsa C ha 7 istanze.

Processi Assegnazione
A B C
Massimo
A B C
Disponibile
A B C
P1 0 1 0 753 3 3 2
P2 200 3 2 2
P3 3 0 2 902
P4 2 1 1 2 2 2
P5 0 0 2 4333

Rispondi alle seguenti domande utilizzando l'algoritmo del banchiere:

  1. Qual è il riferimento della matrice dei bisogni?
  2. Determinare se il sistema è sicuro o meno.
  3. Cosa accadrà se la richiesta di risorsa (1, 0, 0) per il processo P1 può essere accettata immediatamente dal sistema?

Anni. 2: Il contesto della matrice dei bisogni è il seguente:

Necessità [i] = Max [i] - Allocazione [i]
Necessità di P1: (7, 5, 3) - (0, 1, 0) = 7, 4, 3
Necessità di P2: (3, 2, 2) - (2, 0, 0) = 1, 2, 2
Necessità di P3: (9, 0, 2) - (3, 0, 2) = 6, 0, 0
Necessità di P4: (2, 2, 2) - (2, 1, 1) = 0, 1, 1
Necessità di P5: (4, 3, 3) - (0, 0, 2) = 4, 3, 1

Processi Bisogno
A B C
P1 74 3
P2 1 2 2
P3 600
P4 011
P5 431

Quindi, abbiamo creato il contesto della matrice dei bisogni.

Ris. 2: Applicare l'algoritmo del banchiere:

Le Risorse disponibili di A, B e C sono 3, 3 e 2.

Ora controlliamo se ogni tipo di richiesta di risorse è disponibile per ciascun processo.

Passo 1: Per il processo P1:

Bisogno<= available< p>

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

Quindi, esaminiamo un altro processo, P2.

Passo 2: Per il processo P2:

Bisogno<= available< p>

1, 2, 2<= 2 3, condition VERO

Nuovo disponibile = disponibile + Assegnazione

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

Allo stesso modo, esaminiamo un altro processo P3.

Passaggio 3: Per il processo P3:

P3 Bisogno<= available< p>

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

Allo stesso modo, esaminiamo un altro processo, P4.

Passaggio 4: Per il processo P4:

P4 Bisogno<= available< p>

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

Nuova risorsa disponibile = Disponibile + Allocazione

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

Allo stesso modo, esaminiamo un altro processo P5.

Passaggio 5: Per il processo P5:

P5 Bisogno<= available< p>

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

Nuova risorsa disponibile = Disponibile + Allocazione

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

Ora esaminiamo nuovamente ciascun tipo di richiesta di risorse per i processi P1 e P3.

Passaggio 6: Per il processo P1:

P1 Necessità<= available< p>

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

Nuova risorsa disponibile = Disponibile + Allocazione

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

Quindi, esaminiamo un altro processo P2.

Passaggio 7: Per il processo P3:

P3 Bisogno<= available< p>

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

Nuova risorsa disponibile = Disponibile + Allocazione

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

Quindi, eseguiamo l'algoritmo del banchiere per trovare lo stato sicuro e la sequenza sicura come P2, P4, P5, P1 e P3.

Anni. 3: Per concedere la Richiesta (1, 0, 2), dobbiamo prima verificarlo Richiesta<= available< strong>, cioè (1, 0, 2)<= (3, 3, 2), since the condition is true. so process p1 gets request immediately.< p>