DBMS - Deadlock

In un sistema multi-processo, il deadlock è una situazione indesiderata che si verifica in un ambiente di risorse condivise, in cui un processo attende per un tempo indefinito una risorsa che viene trattenuta da un altro processo.

Ad esempio, supponiamo un insieme di transazioni {T ₀ , T ₁ , T ₂ , ..., T _n }. T _{0 ha} bisogno di una risorsa X per completare il suo compito. La risorsa X è detenuta da T ₁ e T ₁ è in attesa di una risorsa Y, che è detenuta da T ₂ . T ₂ è in attesa della risorsa Z, che è trattenuta da T ₀ . Pertanto, tutti i processi si attendono a vicenda per rilasciare risorse. In questa situazione, nessuno dei processi può completare il proprio compito. Questa situazione è nota come deadlock.

I deadlock non sono sani per un sistema. Nel caso in cui un sistema sia bloccato in un deadlock, le transazioni coinvolte nel deadlock vengono annullate o riavviate.

Prevenzione deadlock

Per prevenire qualsiasi situazione di deadlock nel sistema, il DBMS ispeziona in modo aggressivo tutte le operazioni in cui le transazioni stanno per essere eseguite. Il DBMS ispeziona le operazioni e analizza se possono creare una situazione di deadlock. Se rileva che potrebbe verificarsi una situazione di deadlock, la transazione non potrà mai essere eseguita.

Esistono schemi di prevenzione dei deadlock che utilizzano il meccanismo di ordinamento delle transazioni con timestamp per predeterminare una situazione di deadlock.

Schema di attesa

In questo schema, se una transazione richiede di bloccare una risorsa (elemento di dati), che è già trattenuta con un blocco in conflitto da un'altra transazione, può verificarsi una delle due possibilità:

• Se TS (T _i ) <TS (T _j ) - cioè _Ti , che richiede un blocco in conflitto, è più vecchio di T _j - allora _Ti è permesso di aspettare fino a quando l'elemento di dati è disponibile.

• Se TS (T _i )> TS (t _j ) - cioè _Ti è più giovane di T _j - allora _Ti muore. T _i viene riavviato dopo con un ritardo casuale ma con lo stesso timestamp.

Questo schema consente alla transazione più vecchia di attendere ma uccide quella più giovane.

Schema di attesa della ferita

In questo schema, se una transazione richiede di bloccare una risorsa (elemento di dati), che è già trattenuta con un blocco in conflitto da un'altra transazione, può verificarsi una delle due possibilità:

• Se TS (T _i ) <TS (T _j ), allora _Ti costringe T _j ad essere ritirato - cioè _Ti ferisce T _j . T _j viene riavviato in seguito con un ritardo casuale ma con lo stesso timestamp.

• Se TS (T _i )> TS (T _j ), allora _Ti è costretto ad aspettare fino a quando la risorsa è disponibile.

Questo schema, permette alla transazione più giovane di aspettare; ma quando una transazione più vecchia richiede un elemento detenuto da uno più giovane, la transazione più vecchia costringe quella più giovane ad abortire e rilasciare l'oggetto.

In entrambi i casi, la transazione che entra nel sistema in una fase successiva viene interrotta.

Prevenzione della situazione di stallo

Interrompere una transazione non è sempre un approccio pratico. Invece, i meccanismi di prevenzione dei deadlock possono essere utilizzati per rilevare in anticipo qualsiasi situazione di deadlock. Sono disponibili metodi come "wait-for graph" ma sono adatti solo per quei sistemi in cui le transazioni sono leggere e hanno meno istanze di risorsa. In un sistema ingombrante, le tecniche di prevenzione dei deadlock possono funzionare bene.

Aspetta grafico

Questo è un semplice metodo disponibile per tenere traccia di eventuali situazioni di deadlock. Per ogni transazione che entra nel sistema, viene creato un nodo. Quando una transazione _Ti richiede un blocco su un elemento, diciamo X, che è trattenuto da qualche altra transazione T _j , viene creato un arco diretto da _Ti a T _j . Se T _j rilascia l'elemento X, il bordo tra di loro viene lasciato cadere e _Ti blocca l'elemento dati.

Il sistema mantiene questo grafico di attesa per ogni transazione in attesa di alcuni elementi di dati detenuti da altri. Il sistema continua a controllare se è presente un ciclo nel grafico.

Qui, possiamo utilizzare uno dei due seguenti approcci:

• In primo luogo, non consentire alcuna richiesta di un elemento, che è già bloccato da un'altra transazione. Ciò non è sempre fattibile e può causare la fame, dove una transazione attende indefinitamente un elemento di dati e non può mai acquisirlo.

• La seconda opzione è ripristinare una delle transazioni. Non è sempre possibile eseguire il rollback della transazione più recente, poiché potrebbe essere importante di quella precedente. Con l'aiuto di alcuni algoritmi relativi, viene scelta una transazione, che deve essere interrotta. Questa transazione è nota comevictim e il processo è noto come victim selection.