Che cos'è il deadlock nel sistema operativo: condizioni e algoritmo di rilevamento

Che cos'è il deadlock nel sistema operativo: condizioni e algoritmo di rilevamento

L'obiettivo principale di un sistema operativo è fornire una corretta comunicazione tra le risorse hardware e software e fornire anche servizi comuni ai programmi. Quando un processo del sistema operativo desidera accedere a qualsiasi risorsa, invia prima una richiesta alla particolare risorsa a cui desidera accedere, quindi utilizza la risorsa e infine rilascia la risorsa dopo l'utilizzo. Supponendo che molti processi stiano tentando di accedere a una risorsa contemporaneamente, diventa difficile fornire una risorsa a tutti i processi contemporaneamente in una situazione del genere, sorge il concetto denominato deadlock. Pertanto, in questo articolo viene descritto come si verifica il deadlock e come superare questa situazione di deadlock.



Qual è il deadlock nel sistema operativo?

Definizione: Dead-Lock è una situazione in cui due o più processori sono in attesa che si verifichi un evento, ma tali eventi che non si verificano sono una condizione di deadlock e si dice che i processori siano in uno stato di deadlock. Ad esempio, supponiamo uno scenario in tempo reale, in cui ci sono due auto A e B, guidate da due singoli conducenti su una strada a senso unico. Ora si verifica la situazione in cui il guidatore dell'auto A dice che muoversi verso nord è una direzione corretta, mentre il guidatore dell'auto B dice che muoversi verso sud è corretto. Ma nessuno dei due torna indietro per consentire a un'altra macchina di andare avanti, questa condizione è chiamata condizione di deadlock.


Esempio di auto

esempio di auto





Per una migliore comprensione, consideriamo un altro esempio in cui ci sono due risorse R1, R2 e due processi P1 e P2, dove R1 è assegnato a P1 e R2 è assegnato a P2. Ora se P1 vuole accedere a R2, come sappiamo già R2 è tenuto da P2, e ora P2 vuole accedere a R1, che è P1 viene eseguito solo quando si accede a R2, anche P2 esegue solo quando si accede a R1 questa situazione è uno stato di deadlock.

Processore-Esempio

processore-esempio



Condizioni dead-lock

Di seguito sono riportate le quattro importanti condizioni di deadlock che si verificano se tutte le condizioni si verificano contemporaneamente, ci sono determinate possibilità che si verifichi il deadlock.

Esclusione reciproca

Significa che qualsiasi risorsa che stiamo utilizzando deve essere utilizzata in modo che si escluda a vicenda. Dove solo un processo utilizza una sola risorsa alla volta. Ad esempio, il processo di stampa è in corso e all'improvviso un altro processo tenta di interrompere il processo di stampa. Quindi qui in situazione di mutua esclusione, solo dopo che l'attività di stampa è stata completata, viene elaborata solo l'attività successiva. L'esclusione reciproca può essere eliminata condividendo le risorse contemporaneamente, il che non è praticamente possibile.

Esclusione reciproca

esclusione reciproca

Nessuna prelazione

Secondo preventivo algoritmi basati, se è presente un'attività prioritaria che tenta di interrompere l'attività corrente. L'algoritmo preventivo che contiene l'attività corrente e in primo luogo esegue l'attività prioritaria e torna alla sua prima attività. Una situazione spiegata come nell'esempio precedente in cui un processo mantiene la risorsa finché viene eseguita, ovvero P1 può rilasciare R1 solo dopo l'esecuzione, allo stesso modo P2 rilascia R2 solo dopo l'esecuzione. In assenza di prelazione, potrebbe verificarsi un deadlock.


Nessun esempio di prelazione

no-prelazione-esempio

Aspetta e aspetta

Un processo contiene alcune risorse ed è in attesa di risorse aggiuntive, ma tali risorse vengono acquisite da un altro processo. Dall'esempio precedente, P1 tiene R1 e aspetta R2, dove R2 viene acquisito da P2, e P2 tiene R2 e aspetta R1, dove R1 viene acquisito da P1 è una situazione di attesa e potrebbe verificarsi un deadlock nel sistema.

Hold-and-Wait-Esempio

esempio di attesa e attesa

Attesa circolare

Si dice che un insieme di processi sia in deadlock se un processo è in attesa di una risorsa assegnata a un altro processo e quel processo è in attesa di una risorsa, è simile all'esempio sopra spiegato in cui è in forma di loop. Dove P1 è in attesa di R2 e R2 è allocato per P2 e P2 è in attesa di R1 e R1 allocato per P1 che è una forma di attesa circolare se questa condizione soddisfa il deadlock.

Esempio di attesa circolare

esempio-di-attesa-circolare

Algoritmo di rilevamento dead-lock

I casi in cui allociamo risorse ai processi e il sistema operativo ricontrolla se si è verificato un deadlock nel sistema o no utilizzando 2 algoritmi di rilevamento deadlock principali, sono

  • Singola istanza
  • Istanze multiple del tipo di risorsa

Singola istanza

Una singola istanza è una situazione in cui un sistema dispone di singole istanze di tutte le risorse. È anche noto come attesa per algoritmo grafico o grafico di allocazione delle risorse. Il grafico di allocazione delle risorse è costituito da un insieme di processi e un insieme di risorse che sono rappresentati come due diversi vertici. Le risorse nel grafico di allocazione delle risorse vengono modificate e sono rappresentate come forma di grafico di attesa. Dove attesa per la forma del grafico ha solo processi che sono rappresentati come vertici come mostrato di seguito in cui,

  • Grafico di allocazione delle risorse: i processi P1, P2, P3 e le risorse R1, R2, R3 sono rappresentati nel grafico di allocazione delle risorse.
  • Attendi il grafico: solo i processi P1, P2, P3 sono menzionati in attesa del grafico.
  • Se c'è una condizione di ciclo, che se c'è un flusso continuo di un processo in una direzione significa che la condizione di ciclo esce e aspetta che il grafico sia in una condizione di deadlock.

Esempio 1: L'esempio seguente mostra che non è presente uno stato di deadlock perché non è stato osservato alcun flusso continuo in attesa del grafico.

Esempio di istanza singola 1

single-instance-example1

Esempio 2: La condizione di deadlock si è verificata perché c'è un flusso continuo di ciclo da P1 a P4.

Istanza singola - Esempio 2

single-instance-example2

Se il deadlock si verifica molto frequentemente nel sistema, l'algoritmo di rilevamento viene utilizzato frequentemente. Se c'è più utilizzo dell'algoritmo di rilevamento, ci sarà più overhead e più tempo di calcolo. Quindi per ovviare a questo, invochiamo l'algoritmo dopo, dando una quantità di tempo uguale, questo è il modo in cui il peso per il grafico viene utilizzato per rilevare il deadlock.

Istanze multiple di tipo di risorsa

Istanze multiple del tipo di risorsa è una situazione in cui un sistema ha più istanze di tutte le risorse, è anche noto come algoritmo Bankers. Secondo l'algoritmo Bankers, non appena il processo ottiene tutte le risorse richieste, rilascia le sue risorse.

Consideriamo il seguente esempio, supponiamo che ci siano 3 processi P0, P1, P2 e tipo di risorsa A, B, C dove A può essere processore , B può essere la stampante e C può essere la tastiera. Le cifre '0' nella colonna rappresentano la disponibilità delle risorse.

Caso (i): Supponiamo che se prendiamo la condizione richiesta è la condizione '000' che è presente in P0 e P2, dovremmo controllare quale richiesta è soddisfatta, i processi P0 rilasciano i processi dopo essere stati allocati, quindi il successivo P2 elabora i rilasci dopo essere stato allocato. In questo modo, in sequenza, uno per uno il processo rilascia P0, P2, P3, P1, P4 in sequenza. Infine, otteniamo le risorse disponibili come P7, P2, P6. La sequenza disponibile è una condizione in cui non è presente un deadlock.

Bankers-Algorithm-Example 1

banchieri-algoritmo-esempio1

Case (ii): Supponiamo che P2 sia 001 invece di 000, ora applica l'algoritmo del banchiere per verificare la condizione di deadlock, in cui l'unico P0 viene eseguito tra tutti e 5 i processi. Quindi P1, P2, P3, P4 sono in stato di deadlock ad eccezione di P0.

Banchieri-Esempio2

banchieri-esempio2

Applicazioni di Deadlock

Le applicazioni di deadlock possono essere spiegate con un esempio in tempo reale dei risultati degli esami online, in cui diversi studenti cercano di accedere al loro sito web universitario al momento del rilascio. Si può osservare che a volte la pagina web non viene caricata contemporaneamente da più utenti, questa è una condizione di deadlock. Questo può essere superato utilizzando uno qualsiasi degli algoritmi.

Vantaggi

I vantaggi del deadlock sono

  • Nessuna prelazione viene osservata nell'elusione del deadlock
  • Nessun ritardo nel processo

Svantaggi

Lo svantaggio del deadlock è

  • La risorsa da utilizzare deve essere conosciuta in anticipo
  • Blocco del processo per lungo tempo
  • Le perdite di prelazione vengono ereditate.

Questo articolo riassume come si verifica il deadlock quando ci sono due o più processi e le tre condizioni che sono la causa del deadlock, ei due tipi di algoritmi, vale a dire l'algoritmo di condivisione delle risorse che rileva che esiste un condizione di deadlock e l'algoritmo dei banchieri che è un algoritmo per evitare i deadlock. Ecco la domanda 'Cosa succede se il deadlock viene ignorato?'.