Cap.7 Tecniche per il controllo della concorrenza Flashcards
Quali sono le tecniche per il controllo della concorrenza?
Con l’esecuzione di transazioni concorrenti è necessario evitare che esse interferiscano fra di loro garantendo l’isolamento.
Per favorire ciò si utilizzano delle tecniche di gestione delle transazioni, per garantire che il database consistente, tali tecniche garantiscono la serializzabilità degli schedule e sono:
▪ Tecniche di locking: i data item sono bloccati per prevenire che transazioni multiple accedano allo stesso item concorrentemente.
▪ Timestamp: un identificatore unico per ogni transazione, generato dal sistema. Un protocollo può usare l’ordinamento dei timestamp per assicurare la serializzabilità
Quali sono le tecniche di locking? Lock Shared/Esclusivi
Le tecniche di locking si basano sul concetto di “blocco” (lock) di un item. Un lock è una variabile associata ad un data item nel database, e descrive lo stato di quell’elemento rispetto alle possibili operazioni applicabili ad esso. Possono essere utilizzati diversi tipi di lock:
▪ Lock binario, associato a ciascun elemento del DB, può assumere due valori, se lock(X) = 1 le operazioni del database non possono accedere all’elemento, altrimenti lock(X) = 0 si può accedere all’elemento quando richiesto. Un lock binario rafforza la mutua esclusione di un data item.
Le operazioni di lock e unlock devono essere implementate come unità indivisibili (sezioni critiche), nel senso che non è consentito alcun interleaving dall’avvio fino al termine dell’operazione di lock/unlock o all’intervento della transazione di una coda di attesa;
▪ Lock shared/esclusivi, il lock binario è troppo restrittivo, poiché l’accesso ad un data item è consentito ad una sola transazione per volta, è possibile consentire l’accesso in sola lettura a più transazioni contemporaneamente. Se una transazione deve scrivere un data item, deve avere un accesso esclusivo su quel dato. Per questo motivo si utilizza un multiple mode lock, cioè un lock che può avere più stati. Ciascuna delle tre operazioni, Read_lock(X), Write_lock(X), Unlock_item(X), deve essere considerata indivisibile, cioè nessun interleaving deve essere consentito dall’inizio dell’operazione fino al completamento o all’inserimento della transazione in una coda di attesa per quell’elemento.
Conversioni di lock (regole per aumentare un read lock a un write lock / regole per diminuire un write lock a un read lock)
Una transazione può invocare un Read_Lock(X) e poi successivamente incrementare il lock, invocando un Write_Lock(X). Tale conversione è possibile solo se T è l’unica transazione che ha un Read_Lock su X, altrimenti deve aspettare. È possibile anche decrementare un lock, se una transazione T invoca una Write_Lock(X) e successivamente una Read_Lock(X).
Protocolli per il controllo della concorrenza + 2pl (perché protocollo 2pl? per la serializzabilità) + Serializzabilità 2pl + 2pl deadlock free
Il protocollo Two-Phase Locking (2PL) è un algoritmo di controllo della concorrenza utilizzato nei sistemi di gestione di database per garantire la coerenza dei dati durante le transazioni concorrenti. L’obiettivo principale del protocollo 2PL è prevenire le anomalie dei dati, come la perdita di aggiornamenti e la lettura sporca, attraverso l’utilizzo di un meccanismo di lock (blocco) sui dati condivisi.
Il protocollo 2PL opera in due fasi: la fase di crescita (o di acquisizione dei lock) e la fase di rilascio dei lock.
Durante la fase di crescita, una transazione può acquisire i lock su risorse condivise nel database. Questo significa che, prima che una transazione possa leggere o scrivere su una risorsa, deve richiedere e ottenere un lock su quella risorsa. I lock possono essere di due tipi: lock di lettura (shared lock) e lock di scrittura (exclusive lock). Un lock di lettura consente ad altre transazioni di leggere la risorsa, ma non di scriverci, mentre un lock di scrittura garantisce l’esclusività in lettura e scrittura.
Durante la fase di rilascio dei lock, una transazione rilascia gradualmente i lock acquisiti. Una volta rilasciato un lock, la risorsa può essere accessibile da altre transazioni. Il rilascio dei lock avviene solo dopo che la transazione ha completato tutte le sue operazioni sulle risorse.
Il protocollo 2PL garantisce che le transazioni siano serializzabili, ovvero che il risultato finale delle transazioni sia equivalente a una loro esecuzione in sequenza. Ciò evita situazioni di inconsistenza dei dati che possono verificarsi quando più transazioni operano sullo stesso dato contemporaneamente.
Tuttavia, il protocollo 2PL può causare il fenomeno del “deadlock” (o interblocco) in cui due o più transazioni sono bloccate in attesa l’una dell’altra per rilasciare una risorsa. Per gestire i deadlock, possono essere adottati meccanismi aggiuntivi come la rilevazione dei deadlock e l’aborto di una delle transazioni coinvolte per risolvere la situazione di stallo.
Il protocollo 2PL appena visto è detto 2PL di base. Una variazione del 2PL è nota come 2PL conservativo (o statico). Esso richiede che una transazione, prima di iniziare, blocchi tutti gli elementi a cui accede, pre-dichiarando i propri read_set (insieme di tutti i data item che saranno letti dalla transazione) e write_set (insieme di tutti i data item che saranno scritti dalla transazione). Se qualche data item dei due insiemi non può essere bloccato, la transazione resta in attesa finché tutti gli elementi necessari non divengono disponibili. Il 2PL conservativo è un protocollo deadlock-free.
La variazione più diffusa del protocollo 2PL è il 2PL stretto, che garantisce schedule stretti, in cui le transazioni non possono né scrivere né leggere un elemento X finché l’ultima transazione che ha scritto X non termina (con commit o abort), esso non risulta essere deadlock-free.
Deadlock e starvation in gestione transazioni (problematiche da risolvere in ambiente concorrente)
Il protocollo di lock a due fasi garantisce la serializzabilità, ma non consente tutti i possibili schedule serializzabili, cioè alcuni schedule serializzabili vengono vietati da protocollo, perché possono causare:
▪ Deadlock, quando due o più transazioni aspettano qualche item bloccato da altre transazioni T’ in un insieme. Ogni transazione T’ è in una coda di attesa e aspetta che un elemento sia rilasciato da un’altra transazione in attesa. Per prevenire il deadlock, occorre usare il deadlock prevention
protocol, usato nel 2PL conservativo;
▪ Starvation, se una transazione non può procedere per un tempo indefinito mentre altre transazioni nel sistema continuano normalmente. La causa è nello schema di waiting non sicuro che dà la precedenza ad alcune transazioni invece di altre. Un possibile schema di waiting sicuro (safe) usa una
coda first-come-first-serve (FCFS) dove le transazioni bloccano gli elementi rispettando l’ordine con cui hanno richiesto il lock
Granularità + in che modo la scelta della granularità ci determina le possibilità della concorrenza?
La dimensione del data item è detta granularità, può essere un singolo campo di un record, così come un intero blocco di un disco, e può essere:
▪ Fine: riferita a data item di piccole dimensioni come un campo di un record.
▪ Grossa: riferita a data item di dimensioni maggiori come file o database intero.
La granularità influenza le prestazioni nel controllo della concorrenza e del recovery. Maggiore è il livello di granularità, minore è la concorrenza permessa. Se la dimensione di un data item è un blocco del disco, una transazione che necessita di leggere un record in quel blocco effettuerà un lock
dell’intero blocco. Altre transazioni, interessate a record diversi ma ugualmente in quel blocco, resteranno inutilmente in attesa.
Per contro, a un data item di dimensioni inferiori corrisponde un numero maggiore di item nel database, quindi ci sarà una quantità superiore di lock ed il lock manager introdurrò un overhead nel sistema a causa delle molte operazioni che dovrà gestire.
Timestamp e schemi
Nelle transazioni, un timestamp viene utilizzato per registrare quando una transazione è stata avviata, completata o registrata nel sistema. Questo è particolarmente importante in scenari in cui possono verificarsi più transazioni contemporaneamente, come nel caso degli scambi finanziari o delle transazioni in borsa.
“Wait-die” e “wound-wait” sono due schemi di gestione dei blocchi o dei lock utilizzati nel contesto del controllo della concorrenza nei database. Entrambi gli schemi mirano a risolvere i conflitti tra transazioni concorrenti che cercano di accedere alle stesse risorse.
Wait-die: Nello schema "wait-die", quando una transazione T1 richiede un blocco o un lock su una risorsa che è già bloccata da un'altra transazione T2, si verifica quanto segue: Se T1 ha un timestamp maggiore o uguale a quello di T2 (T1 è stata creata dopo T2 o entrambe sono state create contemporaneamente), allora T1 attende il rilascio del blocco da parte di T2. In altre parole, T1 aspetta. Se T1 ha un timestamp inferiore a quello di T2 (T1 è stata creata prima di T2), allora T1 viene "riavvolta" (rollback) allo stato precedente e poi rieseguita con un nuovo timestamp più recente. In altre parole, T1 viene "uccisa" (die) e fatta ripartire con un nuovo timestamp.
Questo schema garantisce che le transazioni con timestamp più elevati abbiano la priorità e mantengano il blocco, mentre le transazioni con timestamp più bassi vengano riavviate in modo da evitare situazioni di deadlock.
Wound-wait: Nello schema "wound-wait", quando una transazione T1 richiede un blocco o un lock su una risorsa che è già bloccata da un'altra transazione T2, si verifica quanto segue: Se T1 ha un timestamp maggiore di quello di T2 (T1 è stata creata dopo T2), allora T1 "uccide" (wound) T2, cioè T2 viene interrotta o abortita, e T1 ottiene immediatamente il blocco sulla risorsa. Se T1 ha un timestamp inferiore o uguale a quello di T2 (T1 è stata creata prima di T2 o entrambe sono state create contemporaneamente), allora T1 attende il rilascio del blocco da parte di T2. In altre parole, T1 aspetta.
Questo schema assicura che le transazioni con timestamp più bassi vengano uccise (riavviate) se cercano di accedere a risorse bloccate da transazioni con timestamp più elevati, evitando così situazioni di deadlock.
Schemi senza timestamp
Gli schemi “No Waiting” (senza attesa) e “Cautious Waiting” (attesa cauta) sono due approcci di controllo della concorrenza utilizzati per prevenire il deadlock nelle transazioni concorrenti in un sistema di gestione di database. Entrambi questi schemi mirano a evitare situazioni in cui le transazioni si bloccano reciprocamente, impedendosi a vicenda di progredire.
No Waiting (Senza attesa): Nello schema "No Waiting", una transazione che richiede un blocco o un lock su una risorsa attende solo se il blocco non è disponibile, ma non aspetta mai che un altro processo rilasci il blocco. In altre parole, se una transazione T1 richiede un blocco detenuto da un'altra transazione T2, T1 non aspetterà il rilascio del blocco da parte di T2, ma verrà immediatamente annullata (rollback).
Questo schema può prevenire il deadlock, ma potrebbe comportare un’elevata quantità di rollback e riavvio delle transazioni. Inoltre, può portare a situazioni di starvation, in cui una transazione potrebbe essere costantemente annullata e non riesce mai ad accedere alle risorse.
Cautious Waiting (Attesa cauta): Nello schema "Cautious Waiting", una transazione che richiede un blocco su una risorsa attende solo se il blocco non è disponibile e la transazione che detiene il blocco ha un timestamp maggiore o uguale al suo. In altre parole, una transazione T1 attende solo se la transazione T2 che detiene il blocco è stata creata dopo T1 (T1 ha un timestamp inferiore a quello di T2).
Se la transazione T1 ha un timestamp maggiore di T2 (T1 è stata creata dopo T2), allora T1 prende il controllo del blocco e T2 viene annullata (rollback). Questo approccio assicura che le transazioni con timestamp più elevati abbiano la priorità nell’accesso alle risorse e previene situazioni di deadlock.
