Controllo della concorrenza nei DBMS: protocolli di blocco e basati su timestamp.

Cos'è il controllo della concorrenza?

Controllo della concorrenza In un sistema di gestione di database, la gestione simultanea di operazioni è una procedura che consente di operare simultaneamente senza che si verifichino conflitti. Garantisce che le transazioni del database vengano eseguite in modo concorrente e accurato, producendo risultati corretti senza compromettere l'integrità dei dati del database stesso.

L'accesso simultaneo è piuttosto semplice se tutti gli utenti si limitano a leggere i dati, poiché non vi è modo che possano interferire l'uno con l'altro. Tuttavia, qualsiasi database pratico presenta un mix di operazioni di lettura e scrittura, quindi la concorrenza diventa una sfida.

Il controllo della concorrenza del DBMS viene utilizzato per gestire tali conflitti, che si verificano principalmente in un sistema multiutente. Il controllo della concorrenza è quindi uno degli elementi più importanti per il corretto funzionamento di un database in cui due o più transazioni vengono eseguite simultaneamente e richiedono l'accesso agli stessi dati. Funziona a stretto contatto con gestione delle transazioniche definisce le unità di lavoro che il controllo della concorrenza deve intercalare in modo sicuro.

Potenziali problemi di concorrenza

Ecco alcuni problemi che potresti incontrare senza un adeguato controllo della concorrenza nel DBMS:

• Aggiornamenti persi Questo problema si verifica quando più transazioni selezionano la stessa riga e la aggiornano in base al valore selezionato.
• Dipendenza non ancora confermata (lettura sporca) si verifica quando una seconda transazione seleziona una riga che è stata aggiornata da un'altra transazione che non è ancora stata confermata.
• Lettura non ripetibile Si verifica quando una seconda transazione accede alla stessa riga più volte e legge dati diversi ogni volta.
• Riepilogo errato Si verifica quando una transazione esegue un riepilogo del valore di tutte le istanze di un elemento di dati ripetuto, mentre una seconda transazione aggiorna solo alcune di queste istanze. Il riepilogo risultante non riflette un risultato corretto.

Perché utilizzare un metodo di concorrenza?

Motivi per utilizzare un metodo di controllo della concorrenza in un DBMS:

• Applicare l'isolamento tramite mutua esclusione tra transazioni in conflitto.
• Per risolvere i problemi di conflitto di lettura-scrittura e di scrittura-scrittura.
• Per preservare la coerenza del database applicando costantemente vincoli di esecuzione.
• Per controllare l'interazione tra transazioni concorrenti, si utilizza l'impiego di schemi di controllo della concorrenza.
• Per contribuire a garantire la serializzabilità.

Esempio

Ipotizziamo che due persone si rechino contemporaneamente ai chioschi elettronici per acquistare un biglietto del cinema per lo stesso film e lo stesso orario.

Tuttavia, per quello spettacolo in sala è rimasto un solo posto libero. Senza un sistema di controllo simultaneo, è possibile che entrambi gli spettatori finiscano per acquistare lo stesso biglietto. Il controllo simultaneo lo impedisce. Entrambi gli spettatori possono comunque accedere alle informazioni relative ai posti a sedere nel database, ma il sistema assegna il biglietto solo all'acquirente che completa per primo la transazione.

Protocolli di controllo della concorrenza

I diversi protocolli di controllo della concorrenza offrono diversi compromessi tra la quantità di concorrenza consentita e il sovraccarico che impongono. Le principali tecniche di controllo della concorrenza nei DBMS sono:

• Protocolli basati su lock
• Protocollo di blocco bifase
• Protocolli basati su timestamp
• Protocolli basati sulla convalida

Ciascuno di essi viene esaminato a turno di seguito, a partire dai protocolli basati su serrature, i più diffusi.

Protocolli basati su lock

Protocolli basati su serrature Nei DBMS, i protocolli basati sui lock sono un meccanismo in cui una transazione non può leggere o scrivere un elemento di dati finché non acquisisce un blocco appropriato. I protocolli basati sui lock aiutano a eliminare il problema della concorrenza bloccando o isolando un particolare elemento di dati per una singola transazione.

Un blocco è una variabile di dati associata a un elemento di dati che indica quali operazioni possono essere eseguite su di esso. I blocchi aiutano a sincronizzare l'accesso agli elementi del database da parte di transazioni concorrenti. Tutte le richieste di blocco vengono inviate al gestore del controllo della concorrenza e le transazioni procedono solo dopo che la richiesta di blocco è stata concessa.

Blocchi binari: Un blocco binario su un elemento dati può trovarsi nello stato bloccato o sbloccato.

Condiviso/Esclusivo: Questo meccanismo di bloccaggio separa i lucchetti in base al loro utilizzo. Se un lucchetto viene acquisito per eseguire un'operazione di scrittura, viene definito lucchetto esclusivo.

1. Blocco condiviso (S): Un blocco condiviso è anche chiamato blocco di sola lettura. Con un blocco condiviso, l'elemento dati può essere condiviso tra transazioni, perché nessuna di esse ha il permesso di aggiornare l'elemento. Ad esempio, se due transazioni leggono il saldo del conto di una persona, banca dati Consente loro di leggere tramite l'inserimento di un blocco condiviso. Se un'altra transazione tenta di aggiornare tale saldo, il blocco condiviso lo impedisce fino al termine della lettura.

2. Blocco esclusivo (X): Con un blocco esclusivo, un elemento dati può essere sia letto che scritto. È esclusivo e non può essere bloccato contemporaneamente sullo stesso elemento dati. Un blocco X viene richiesto utilizzando l'istruzione lock-x. Ad esempio, quando una transazione deve aggiornare il saldo di un conto, ciò è consentito applicando un blocco X; una seconda transazione che tenti di leggere o scrivere viene quindi impedita.

3. Protocollo di blocco semplificato: Ciò consente alle transazioni di ottenere un blocco su ogni oggetto prima di iniziare un'operazione. Le transazioni possono sbloccare l'elemento dati al termine dell'operazione di scrittura.

4. Blocco della pre-reclamo: Questo protocollo valuta le operazioni e crea un elenco degli elementi di dati necessari per avviare l'esecuzione. Quando tutti i blocchi vengono concessi, la transazione viene eseguita e tutti i blocchi vengono rilasciati al termine delle operazioni.

Fame: La starvation è la situazione in cui una transazione attende per un periodo indefinito per acquisire un blocco. Le cause includono una gestione inadeguata del meccanismo di attesa per gli elementi bloccati, una perdita di risorse o la stessa transazione che viene ripetutamente selezionata come vittima.

Impasse: Il termine deadlock si riferisce a una situazione in cui due o più processi attendono che l'altro rilasci una risorsa, formando una catena circolare.

Protocollo di blocco a due fasi (2PL)

Migliori Protocollo di blocco bifase, noto anche come 2PL, è un metodo di controllo della concorrenza che garantisce la serializzabilità applicando un blocco ai dati della transazione, impedendo così ad altre transazioni di accedere simultaneamente agli stessi dati.

Il protocollo di blocco a due fasi consente a ciascuna transazione di effettuare una richiesta di blocco o sblocco in due passaggi:

• Fase di crescita: In questa fase una transazione può ottenere blocchi, ma non può rilasciarne alcuno.
• Fase di restringimento: In questa fase una transazione può rilasciare i blocchi ma non può acquisirne di nuovi.

È vero che 2PL offre serializzabilità. Tuttavia, non garantisce che non si verifichino deadlock. Nel diagramma sopra, i rilevatori di deadlock locali e globali cercano i deadlock e li risolvono riprendendo le transazioni ai loro stati iniziali.

Metodo di blocco rigoroso a due fasi

Strict-2PL è quasi identico a 2PL. L'unica differenza è che Strict-2PL non rilascia mai un blocco dopo averlo utilizzato. Mantiene tutti i blocchi fino al punto di commit e li rilascia tutti contemporaneamente al termine del processo.

2PL centralizzato

Nella logistica 2PL centralizzata, un singolo sito è responsabile del processo di gestione dei blocchi. Dispone di un unico gestore dei blocchi per l'intero DBMS.

Copia primaria 2PL

Nel meccanismo 2PL a copia primaria, numerosi gestori di blocco sono distribuiti su siti diversi e ciascun gestore di blocco è responsabile della gestione del blocco per un insieme di elementi di dati. Quando la copia primaria viene aggiornata, la modifica viene propagata ai nodi slave.

2PL distribuito

In questo meccanismo, i gestori dei blocchi sono distribuiti su tutti i siti e sono responsabili della gestione dei blocchi per i dati in quel sito. Se non vengono replicati dati, è equivalente a un 2PL a copia primaria. I costi di comunicazione del 2PL distribuito sono notevolmente superiori a quelli del 2PL a copia primaria.

Protocolli basati su timestamp

Migliori Protocollo basato su timestamp Nei DBMS, esiste un algoritmo che utilizza l'ora di sistema o un contatore logico come timestamp per serializzare l'esecuzione di transazioni concorrenti. Garantisce che ogni operazione di lettura e scrittura in conflitto venga eseguita nell'ordine del timestamp.

In questo metodo, la transazione più vecchia ha sempre la priorità. Utilizza l'ora di sistema per determinare il timestamp della transazione ed è il protocollo di concorrenza più comunemente utilizzato. I protocolli basati su lock gestiscono l'ordine tra transazioni in conflitto al momento della loro esecuzione; i protocolli basati su timestamp gestiscono i conflitti non appena viene creata un'operazione.

Esempio:

Suppose there are three transactions T1, T2, and T3.
T1 has entered the system at time 0010
T2 has entered the system at 0020
T3 has entered the system at 0030
Priority will be given to transaction T1, then T2 and lastly T3.

vantaggi:

• Gli schemi sono serializzabili, proprio come i protocolli 2PL.
• Nessun tempo di attesa per la transazione, il che elimina la possibilità di blocchi.

svantaggi: È possibile che si verifichi un blocco se la stessa transazione viene riavviata e ripetutamente interrotta.

Protocollo basato sulla convalida

Migliori Protocollo basato sulla convalida Nei DBMS, noto anche come tecnica di controllo ottimistico della concorrenza, è un metodo per evitare conflitti di concorrenza nelle transazioni. In questo protocollo, vengono aggiornate le copie locali dei dati della transazione anziché i dati stessi, il che si traduce in una minore interferenza durante l'esecuzione.

Il protocollo di validazione si articola in tre fasi:

1. Fase di lettura
2. Fase di convalida
3. Fase di scrittura

Fase di lettura

Nella fase di lettura, i valori dei dati possono essere letti da una transazione, ma le operazioni di scrittura o gli aggiornamenti vengono applicati solo alle copie locali dei dati, non al database effettivo.

Fase di convalida

Nella fase di validazione, i dati vengono controllati per garantire che l'applicazione degli aggiornamenti non violi la serializzabilità.

Fase di scrittura

Nella fase di scrittura, gli aggiornamenti vengono applicati al database se la convalida ha esito positivo; in caso contrario, gli aggiornamenti vengono scartati e la transazione viene annullata.

Confronto tra protocolli di controllo della concorrenza

Le quattro famiglie di protocolli fanno previsioni diverse sulla frequenza con cui le transazioni entrano effettivamente in conflitto. La tabella seguente riassume la posizione di ciascuna.

In breve, i protocolli basati su lock e 2PL presuppongono che i conflitti siano frequenti e li prevengono a priori, mentre i protocolli basati su timestamp e validazione presuppongono che i conflitti siano rari e li risolvono solo quando si presentano.

Caratteristiche di un buon protocollo di concorrenza

Un meccanismo ideale di controllo della concorrenza ha i seguenti obiettivi:

• Deve essere resistente ai guasti del sito e delle comunicazioni.
• Consente l'esecuzione parallela di transazioni per ottenere la massima concorrenza.
• I suoi meccanismi di archiviazione e i metodi di calcolo dovrebbero essere modesti per ridurre al minimo le spese generali.
• Deve imporre alcuni vincoli sulla struttura delle azioni atomiche delle transazioni.

DOMANDE FREQUENTI