uni
La concorrenza è fondamentale, decine o centinaia di transazioni al secondo non possono essere seriali. Si appoggia sulla Gestione delle Transazioni.
Senza una gestione accurata la concorrenza causerebbe però anomalie: per esempio se due transazioni operano sullo stesso valore possono leggere un valore intermedio “sporco”.
Ci sono diversi tipi di anomalie:

perdita di aggiornamento: W-W
Quando una transazione aggiorna un valore senza sapere che anche un’altra transazione lo aggiorna.
Lettura sporca: R-W o W-W con aborto
Quando una transazione legge e opera su un valore che è stato aggiornato da una transazione che è stata poi abolita.
Lettura inconsistente: R-W
Quando una transazione ha due letture, che leggono valori diversi sullo stesso oggetto per via di un’altra transazione che cambia il valore in mezzo.
Aggiornamento Fantasma: R-W
Quando una transazione legge due valori sui quali vi è une vincolo di integrità, ma in mezzo vi è un aggiornamento corretto, quindi la base di dati soddisfa il vincolo, ma la transazione che legge i due valori non lo vede corretto.
Ovvero si presenta quando ci sono due scritture di transazioni diverse di seguito, senza che la seconda scrittura abbia una relativa lettura dopo la prima scrittura.
Inserimento fantasma: R-W su dato “nuovo”

Scheduler

La componente del sistema di gestione della concorrenza che tiene traccia di tutte le operazioni elementari richieste ed eseguite sulla base di dati dalle transazioni, e che ha il compito di decidere se accettare o rifiutare le operazioni che vengono via via richieste si chiama scheduler.
Tali decisioni devono garantire che non si creino anomalie, e che il mondo esterno abbia sempre l’impressione che l’esecuzione delle transazioni sia avvenuta in modo seriale, secondo un qualche ordinamento delle transazioni.

Schedule

Uno schedule $S$ è una sequenza di operazioni di lettura/ scrittura di transazioni concorrenti.
Esempio: $S : r_{1} (x) r_{2} (z) w_{1} (x) w_{2} (z)$ dove $r_{2} (x)$ rappresenta la lettura dell’oggetto $x$ da parte della transazione $T_{1}$ .
Le operazioni compaiono nello schedule nell’ordine temporale di esecuzione sul database.

Schedule seriale

Uno schedule di transazioni $T = {T_{1}, ..., T_{n}}$ è detto seriale se per ogni coppia di transazioni tutte le operazioni di una delle due sono eseguite prima di qualsiasi operazione dell’altra.

Assumendo che ogni singola transazione mantenga il Database in uno stato consistente, concludiamo che ogni schedule seriale sia corretto.

Esempio: $T = {T_{0}, T_{1}} \to S = r_{0} (x) r_{0} (y) r_{1} (x) w_{1} (y)$

Schedule Serializzabile

Per ragioni di prestazioni non possiamo permetterci di accettare solo schedule seriali, definiamo quindi gli schedule serializzabili.
Questo è un insieme di transazioni che produce lo stesso risultato di uno schedule seriale sulle stesse transazioni.
Questa definizione richiede però un concetto di equivalenza fra schedule.

View-Equivalenza e View-Serializzabilità

Dato uno schedule $S$ , il suo insieme scritture-finali $F ina l i (S)$ è composto da tutte le ultime scritture $w_{i} (x)$ di $S$ per un qualsiasi oggetto $x$ della base di dati.

Diciamo che esiste una relazione legge-da tra le operazioni $r_{i} (x)$ e $w_{j} (x)$ presenti in uno schedule $S$ se $w$ precede $r$ e se tra le due non ci sono altre $w$ .
L’insieme relazione legge-da è l’insieme di tutte le relazioni legge-da della schedule.

Due schedule $S_{i}$ e $S_{j}$ sono detti view-equivalenti, $S_{i} \approx_{v} S_{j}$ se hanno la stessa relazione legge-da e le stesse scritture finali su ogni oggetto.
Ovvero: $L e gg eD a (S_{1}) = L e gg eD a (S_{2}) \land F ina l i (S_{1}) = F ina l i (S_{2}) ⟹ S_{1} \approx_{v} S_{2}$ .

Uno schedule $S$ è view-serializzabile se è view-equivalente ad un qualche schedule seriale con le stesse transazioni di $S$ .

L’insieme degli schedule view-serializzabili è indicato con VSR.

La verifica della view-equivalenza di due dati schedule ha complessità polinomiale.
La verifica sulla view-serializzabilità di uno schedule è un problema NP-completo poiché è necessario confrontare lo schedule con tutti i possibili schedule seriali, questo lo rende inutilizzabile nella pratica.
Poiché l’uso della view-serializzabilità nella pratica è impossibile definiamo una condizione di equivalenza più ristretta ma che sia utilizzabile nella pratica, quindi che abbia una complessità inferiore.

Conflict-Serializzabilità

Un’operazione $a_{i}$ è in conflitto con un’altra operazione $a_{j}$ se operano sullo stesso oggetto e almeno una di esse è una scrittura. Nota bene: nei conflitti conta l’ordine.

Il conflitto può essere:

R-W oppure W-R
W-W

Due schedule $S_{i}$ e $S_{j}$ sono detti conflict-equivalenti, $S_{i} \approx_{c} S_{j}$ se hanno le stesse operazioni e ogni coppia di operazioni in conflitto compare nello stesso ordine in entrambi.

Uno schedule $S$ è conflict-serializzabile se è conflict-equivalente ad un qualche schedule seriale.

L’insieme degli schedule conflict-serializzabili è indicato con CSR.

Teorema: ogni schedule conflict-serializzabile è view-serializzabile, ma non necessariamente viceversa, quindi $CSR ⟹ V SR$ poiché $\approx_{c} ⟹ \approx_{v}$ .

Verifica della Conflict-Serializzabilità

Si fa tramite il grafo dei conflitti (Grafo):

Un nodo per ogni transazione $T_{i}$
un arco (orientato) da $T_{i}$ a $T_{j}$ se c’è almeno un conflitto fra un’operazione $a_{i}$ e un’operazione $a_{j}$ tale che $a_{i}$ precede $a_{j}$
Teorema: Uno schedule è in CSR se e solo se il grafo è aciclico.
Esempio:
- S = $w_{1} (x) w_{2} (x) r_{3} (x) r_{1} (y) w_{2} (y) r_{1} (z) w_{3} (z) r_{4} (z) w_{4} (y) w_{5} (y)$
- $x : w_{1} w_{2} r_{3}$
- $y : r_{1} w_{2} w_{4} w_{5}$
- $z : r_{1} w_{3} r_{4}$
- Il grafo è aciclico $\to$ $S$ è CSR, quindi anche VSR

graph LR
    1((1)) --> 2((2))
    1 --> 3((3))
    1 --> 4((4))
    1 --> 5((5))
    2 --> 3
    2 --> 4
    2 --> 5
    3 --> 4
    3 --> 5
    4 --> 5

La verifica di aciclicità di un grafo è polinomiale rispetto al numero dei nodi.

Locking

I più diffusi algoritmi di scheduling delle transazioni si basano sul concetto di lock.

Un lock su un oggetto $x$ è un meccanismo di controllo della concorrenza che regola l’accesso simultaneo all’oggetto $x$ .

I lock sono acquisiti e rilasciati dalle transazioni per mezzo dello scheduler.

Prima di eseguire una lettura sull’oggetto $x$ , una transazione $T_{i}$ deve acquisirne il lock condiviso, questa azione si indica con $r l_{i} (x)$ . Dopo aver eseguito la lettura deve rilasciarlo: $r u_{i} (x)$ .

Prima di eseguire una scrittura sull’oggetto $x$ , una transazione $T_{i}$ deve acquisirne il lock esclusivo $w l_{i} (x)$ . Dopo aver eseguito la scrittura deve rilasciarlo: $w u_{i} (x)$ .

Due lock sullo stesso oggetto sono in conflitto se almeno uno dei due è esclusivo.

Locking Scheduler

Uno scheduler che inoltre gestisce le richieste di lock si chiama locking scheduler, a questo fine deve implementare un opportuno algoritmo di locking, per l’assegnamento e il rilascio dei lock.

Algoritmo 2PL

L’algoritmo di locking più diffuso nei DBMS è l’algoritmo di locking a due fasi, 2PL (two-phase locking).

Questo si basa sulle seguenti regole:

Quando lo scheduler riceve un’operazione $p_{i} (x)$ , controlla se il lock $p l_{i} (x)$ è in conflitto con qualche lock $q l_{i} (x)$ già acquisito da un’altra transazione sullo stesso oggetto.
Se è in conflitto blocca l’operazione $p_{i} (x)$ e mette $T_{i}$ in attesa fino a quando non riesce ad acquisire il lock di cui ha bisogno.
Quando il lock può effettivamente essere rilasciato, assegna $p l_{i} (x)$ a $T_{i}$ , che eseguirà l’operazione $p_{i} (x)$ .
Lo scheduler non può rilasciare il lock $p l_{i} (x)$ almeno fino a quando l’operazione $p_{i} (x)$ si è conclusa.
Regola delle due Fasi: una volta che lo scheduler rilascia un lock per una transazione, non può più assegnare nessun lock, su nessun oggetto, a quella transazione.

La terza regola divide ogni transazione in due fasi: la fase crescente e la fase calante. La sua funzione è quella di garantire che tutte le coppie di operazioni in conflitto di due transazioni siano schedulate nello stesso ordine.

Teorema $2 P L \subset CSR$ : ogni schedule producibile da uno scheduler 2PL è conflict-serializzabile, ma non necessariamente viceversa.

Algoritmo 2PL Stretto

Praticamente tutti gli scheduler 2PL usano una variante, detto 2PL stretto, in cui vi è una quarta regola: lo scheduler deve rilasciare tutti i lock di una transazione contemporaneamente, al termine della transazione stessa.

Questo perché la variante non stretta necessita che lo scheduler assumi quando vuole rilasciare un lock, che la transazione ha acquisito tutti i lock di cui aveva e avrà bisogno e che la transazione non eseguirà più nessuna operazione che coinvolge l’oggetto $x$ .

Implementazione attraverso Tabella dei Lock

Una possibile implementazione dei meccanismi di Lock è tramite la tabella dei lock, gestita da un componente del gestore della concorrenza chiamato Gestore dei Lock.
Le operazione a disposizione per la tabella sono lock(t,x,m) e unlock(t,x,m), dove t indica la relativa transazione, x l’oggetto e m la modalità del lock: condiviso o esclusivo.
L’esecuzione di una operazione lock: se il lock è assegnabile comporta l’inserimento nella tabella del lock, se non è assegnabile comporta l’inserimento di questa operazione in una lista di attesa.

L’implementazione di questa tabella dei lock è normalmente attraverso Tabella Hash, per la sua estrema velocità di ricerca basata su contenuto.

Una coppia chiave-valore della tabella ha come chiave l’oggetto $x$ e come valore due liste: una prima lista di lock che sono stati concessi su $x$ e una seconda lista di richieste di lock su $x$ .
Ogni Lock e richiesta di Lock contiene l’identificatore della transazione e la modalità del lock.

Deadlock

Uno scheduler 2PL abbiamo detto che produce schedule conflict serializzabili, e quindi risolve tutte le anomalie risolte da schedule CSR, ne introduce però una nuova: il deadlock.
Un deadlock è quando due o più transazioni sono ferme in attesa del rilascio di un lock, assegnato alle altre transazioni e quindi non rilasciabile.

Per risolvere questa anomalia impieghiamo la strategia del timeout: se una transazione rimane in attesa di un lock più a lungo di un dato lasso di tempo prefissato (il valore di timeout) lo scheduler assume una situazione di deadlock e abortisce la transazione.

Un’altra strategia consiste nella certa identificazione dei deadlock, per poterlo fare lo scheduler mantiene aggiornato un grafo orientato detto grafo delle attese, i suoi nodi sono le transazioni in esecuzione, un arco $T_{i} \to T_{j}$ rappresenta il fatto che la transazione $T_{i}$ è in attesa del rilascio di un lock assegnato alla transazione $T_{j}$ , se in questo grafo è presente un ciclo, le transazione coinvolte nel ciclo sono in stato di deadlock, in questo caso allora lo scheduler sceglie una transazione e la abortisce, rimuovendo il nodo dal grafo e liberando il deadlock.

Media

graph TD
    A[Gestore dei metodi d'accesso] -->|read, write| B[Gestore della concorrenza]
    C[Gestore delle transazioni] -->|begin, commit, abort| B
    B --> D(Tabella dei lock)
    B --> |read,write: non tutte e in ordine ev. diverso| E[Gestore della memoria secondaria]
    E --> F[(BD)]

flowchart TB
    subgraph S1[ ]
        direction TB
        subgraph S2[ ]
            direction TB
            subgraph S3[ ]
                ScheduleSeriali(Schedule Seriali)
            end
            ScheduleCSR(Schedule CSR)
        end
        ScheduleVSR(Schedule VSR)
    end
    Schedule(Schedule)

    S1 --- Schedule
    S1 --- ScheduleVSR
    S2 --- ScheduleCSR
    S3 --- ScheduleSeriali

🪴 Quartz 4.0

Explorer

Gestione della Concorrenza