DBMS distribuito - Gestione deadlock

Questo capitolo illustra i meccanismi di gestione dei deadlock nei sistemi di database. Studieremo i meccanismi di gestione dei deadlock nel sistema di database centralizzato e distribuito.

Cosa sono i deadlock?

Deadlock è uno stato di un sistema di database con due o più transazioni, quando ogni transazione è in attesa di un elemento di dati bloccato da un'altra transazione. Un deadlock può essere indicato da un ciclo nel grafico di attesa. Questo è un grafo diretto in cui i vertici denotano transazioni e i bordi denotano attese per elementi di dati.

Ad esempio, nel seguente grafico di attesa, la transazione T1 è in attesa dell'elemento dati X che è bloccato da T3. T3 sta aspettando Y che è bloccato da T2 e T2 sta aspettando Z che è bloccato da T1. Quindi, si forma un ciclo di attesa e nessuna delle transazioni può procedere con l'esecuzione.

Gestione dei deadlock nei sistemi centralizzati

Esistono tre approcci classici per la gestione del deadlock, vale a dire:

• Prevenzione dei deadlock.
• Evitamento del deadlock.
• Rilevamento e rimozione di deadlock.

Tutti e tre gli approcci possono essere incorporati sia in un sistema di database centralizzato che distribuito.

Prevenzione deadlock

L'approccio di prevenzione dei deadlock non consente a nessuna transazione di acquisire blocchi che porteranno a deadlock. La convenzione è che quando più di una transazione richiede il blocco dello stesso elemento di dati, solo a una di esse viene concesso il blocco.

Uno dei metodi di prevenzione dei deadlock più popolari è la pre-acquisizione di tutti i blocchi. In questo metodo, una transazione acquisisce tutti i blocchi prima di iniziare l'esecuzione e mantiene i blocchi per l'intera durata della transazione. Se un'altra transazione necessita di uno qualsiasi dei blocchi già acquisiti, deve attendere fino a quando tutti i blocchi necessari sono disponibili. Utilizzando questo approccio, il sistema non può essere bloccato poiché nessuna delle transazioni in attesa contiene alcun blocco.

Prevenzione della situazione di stallo

L'approccio per evitare i deadlock gestisce i deadlock prima che si verifichino. Analizza le transazioni e i blocchi per determinare se l'attesa porta o meno a un deadlock.

Il metodo può essere brevemente affermato come segue. Le transazioni iniziano a essere eseguite e richiedono elementi di dati che devono essere bloccati. Il gestore della serratura controlla se la serratura è disponibile. Se è disponibile, il gestore del blocco alloca l'elemento dati e la transazione acquisisce il blocco. Tuttavia, se l'elemento è bloccato da un'altra transazione in modalità incompatibile, il gestore dei blocchi esegue un algoritmo per verificare se mantenere la transazione in stato di attesa causerà o meno un deadlock. Di conseguenza, l'algoritmo decide se la transazione può attendere o se una delle transazioni deve essere interrotta.

Esistono due algoritmi per questo scopo, vale a dire wait-die e wound-wait. Supponiamo che ci siano due transazioni, T1 e T2, in cui T1 tenta di bloccare un elemento di dati che è già bloccato da T2. Gli algoritmi sono i seguenti:

• Wait-Die- Se T1 è più vecchio di T2, T1 può attendere. Altrimenti, se T1 è più giovane di T2, T1 viene interrotto e successivamente riavviato.

• Wound-Wait- Se T1 è più vecchio di T2, T2 viene interrotto e successivamente riavviato. Altrimenti, se T1 è più giovane di T2, T1 può aspettare.

Rilevamento e rimozione di deadlock

L'approccio di rilevamento e rimozione dei deadlock esegue periodicamente un algoritmo di rilevamento dei deadlock e rimuove i deadlock nel caso in cui ve ne sia uno. Non controlla il deadlock quando una transazione inserisce una richiesta di blocco. Quando una transazione richiede un blocco, il gestore dei blocchi controlla se è disponibile. Se è disponibile, la transazione può bloccare l'elemento di dati; altrimenti la transazione può attendere.

Poiché non sono previste precauzioni durante la concessione delle richieste di blocco, alcune transazioni potrebbero essere bloccate. Per rilevare i deadlock, il gestore dei blocchi controlla periodicamente se il wait-forgraph ha cicli. Se il sistema è in deadlock, il gestore della serratura sceglie una transazione vittima da ogni ciclo. La vittima viene abortita e rotolata indietro; e quindi riavviato in seguito. Alcuni dei metodi utilizzati per la selezione delle vittime sono:

• Scegli la transazione più giovane.
• Scegli la transazione con il minor numero di elementi di dati.
• Scegli la transazione che ha eseguito il minor numero di aggiornamenti.
• Scegli la transazione con il minor sovraccarico di riavvio.
• Scegli la transazione che è comune a due o più cicli.

Questo approccio è adatto principalmente per i sistemi con transazioni basse e dove è necessaria una risposta rapida alle richieste di blocco.

Gestione dei deadlock nei sistemi distribuiti

Viene distribuita anche l'elaborazione delle transazioni in un sistema di database distribuito, ovvero la stessa transazione può essere elaborata in più di un sito. I due principali problemi di gestione dei deadlock in un sistema di database distribuito che non sono presenti in un sistema centralizzato sonotransaction location e transaction control. Una volta risolti questi problemi, i deadlock vengono gestiti attraverso la prevenzione dei deadlock, l'evitamento dei deadlock o il rilevamento e la rimozione dei deadlock.

Posizione della transazione

Le transazioni in un sistema di database distribuito vengono elaborate in più siti e utilizzano elementi di dati in più siti. La quantità di elaborazione dei dati non è distribuita uniformemente tra questi siti. Anche il periodo di tempo per l'elaborazione varia. Pertanto la stessa transazione potrebbe essere attiva su alcuni siti e inattiva su altri. Quando due transazioni in conflitto si trovano in un sito, può accadere che una di esse sia inattivo. Questa condizione non si verifica in un sistema centralizzato. Questa preoccupazione è chiamata problema di posizione della transazione.

Questa preoccupazione può essere risolta dal modello Daisy Chain. In questo modello, una transazione trasporta determinati dettagli quando si sposta da un sito a un altro. Alcuni dei dettagli sono l'elenco delle tabelle richieste, l'elenco dei siti richiesti, l'elenco delle tabelle e dei siti visitati, l'elenco delle tabelle e dei siti ancora da visitare e l'elenco dei blocchi acquisiti con i tipi. Dopo che una transazione termina per commit o interruzione, le informazioni dovrebbero essere inviate a tutti i siti interessati.

Controllo delle transazioni

Il controllo delle transazioni riguarda la designazione e il controllo dei siti necessari per l'elaborazione di una transazione in un sistema di database distribuito. Ci sono molte opzioni riguardanti la scelta di dove elaborare la transazione e come designare il centro di controllo, come:

• Un server può essere selezionato come centro di controllo.
• Il centro di controllo può viaggiare da un server all'altro.
• La responsabilità del controllo può essere condivisa da più server.

Prevenzione dei deadlock distribuiti

Proprio come nella prevenzione centralizzata dei deadlock, nell'approccio di prevenzione dei deadlock distribuiti, una transazione dovrebbe acquisire tutti i blocchi prima di iniziare l'esecuzione. Ciò impedisce deadlock.

Il sito in cui entra la transazione è designato come sito di controllo. Il sito di controllo invia messaggi ai siti in cui si trovano gli elementi di dati per bloccare gli elementi. Quindi attende la conferma. Quando tutti i siti hanno confermato di aver bloccato gli elementi di dati, la transazione inizia. Se un sito o un collegamento di comunicazione non riesce, la transazione deve attendere fino a quando non sono stati riparati.

Sebbene l'implementazione sia semplice, questo approccio presenta alcuni inconvenienti:

• La pre-acquisizione dei blocchi richiede molto tempo per i ritardi di comunicazione. Ciò aumenta il tempo necessario per la transazione.

• In caso di errore del sito o del collegamento, una transazione deve attendere molto tempo affinché i siti vengano ripristinati. Nel frattempo, nei siti in esecuzione, gli elementi sono bloccati. Ciò potrebbe impedire l'esecuzione di altre transazioni.

• Se il sito di controllo non riesce, non può comunicare con gli altri siti. Questi siti continuano a mantenere gli elementi di dati bloccati nel loro stato bloccato, con conseguente blocco.

Evitare il deadlock distribuito

Come nel sistema centralizzato, l'eliminazione del deadlock distribuito gestisce il deadlock prima che si verifichi. Inoltre, nei sistemi distribuiti, è necessario affrontare i problemi di ubicazione e controllo delle transazioni. A causa della natura distribuita della transazione, potrebbero verificarsi i seguenti conflitti:

• Conflitto tra due transazioni nello stesso sito.
• Conflitto tra due transazioni in siti diversi.

In caso di conflitto, una delle transazioni può essere interrotta o lasciata attendere secondo gli algoritmi distribuiti wait-die o distribuiti ferita-attesa.

Supponiamo che ci siano due transazioni, T1 e T2. T1 arriva al sito P e tenta di bloccare un elemento di dati che è già bloccato da T2 in quel sito. Quindi, c'è un conflitto nel sito P. Gli algoritmi sono i seguenti:

• Distributed Wound-Die

  • Se T1 è più vecchio di T2, T1 può attendere. T1 può riprendere l'esecuzione dopo che il sito P riceve un messaggio che T2 ha eseguito il commit o interrotto correttamente in tutti i siti.

  • Se T1 è più giovane di T2, T1 viene interrotto. Il controllo della concorrenza nel sito P invia un messaggio a tutti i siti in cui è stato visitato T1 per interrompere T1. Il sito di controllo notifica all'utente quando T1 è stato interrotto correttamente in tutti i siti.

• Distributed Wait-Wait

  • Se T1 è più vecchio di T2, T2 deve essere interrotto. Se T2 è attivo nel sito P, il sito P interrompe e ripristina T2, quindi trasmette questo messaggio ad altri siti pertinenti. Se T2 ha lasciato il sito P ma è attivo nel sito Q, il sito P trasmette che T2 è stato interrotto; Il sito L quindi interrompe e ripristina T2 e invia questo messaggio a tutti i siti.

  • Se T1 è più giovane di T1, T1 può aspettare. T1 può riprendere l'esecuzione dopo che il sito P riceve un messaggio che T2 ha completato l'elaborazione.

Rilevamento deadlock distribuito

Proprio come l'approccio di rilevamento dei deadlock centralizzato, i deadlock possono verificarsi e vengono rimossi se rilevati. Il sistema non esegue alcun controllo quando una transazione invia una richiesta di blocco. Per l'implementazione, vengono creati grafici di attesa globali. L'esistenza di un ciclo nel grafico di attesa globale indica deadlock. Tuttavia, è difficile individuare i deadlock poiché la transazione attende le risorse attraverso la rete.

In alternativa, gli algoritmi di rilevamento deadlock possono utilizzare timer. Ogni transazione è associata a un timer che è impostato su un periodo di tempo in cui si prevede che una transazione termini. Se una transazione non termina entro questo periodo di tempo, il timer si spegne, indicando un possibile deadlock.

Un altro strumento utilizzato per la gestione dei deadlock è un rilevatore di deadlock. In un sistema centralizzato, è presente un rilevatore di deadlock. In un sistema distribuito, possono essere presenti più rilevatori di deadlock. Un rilevatore di deadlock può trovare deadlock per i siti sotto il suo controllo. Esistono tre alternative per il rilevamento dei deadlock in un sistema distribuito, vale a dire.

• Centralized Deadlock Detector - Un sito è designato come rilevatore di deadlock centrale.

• Hierarchical Deadlock Detector - Diversi rilevatori di deadlock sono disposti in gerarchia.

• Distributed Deadlock Detector - Tutti i siti partecipano alla rilevazione dei deadlock e alla loro rimozione.