Tecnologia di un
data base server:
Controllo della Concorrenza
Leonardo Mostarda
Sea Lab
Controllo della concorrenza
 La concorrenza delle transazioni consente un
uso efficiente del DBMS, massimizzando il
tps.
 Il controllo di concorrenza fa riferimento al
livello più basso che attua il trasferimento di
blocchi fra memoria centrale e memoria di
massa (r/w).
 Le operazioni di r/w sono richieste dallo
scheduler.
Controllo della concorrenza
 Con r(x) si indica la lettura dell’area di
memoria contenente il dato x.
 Con w(x) si indica la scrittura dell’area di
memoria contenente il dato x.
 x, y .. Sono oggetti del database su cui
verranno effettuate operazioni numeriche
 Eseguire transazioni concorrenti aumenta il
tps ma può causare problemi.
Anomalia delle transazioni concorrenti
perdita di update
Siano date le transazioni:
t1: r1(x), x = x +1, w2(x)
t2: r1(x), x = x +1, w2(x)
 bot
 r1(x)
 x=x+1





 w1(x)
 commit
bot
r2(x)
x=x+1
w2(x)
commit
Anomalia delle transazioni concorrenti
Letture sporche
Siano date le transazioni:
t1: r1(x), x = x +1, w2(x)
t2: r1(x), x = x +1, w2(x)




bot
r1(x)
x=x+1
w1(x)





 abort
bot
r2(x)
x=x+1
w2(x)
commit
Tecnologia data base server
Tre oggetti x y z con definito il vincolo di integirtà x + y + z = 1000






bot
s=0
r1(x)
r1(y)
s=x+s
s=y+s











r1(z)
s=z+s
commit
bot
r2(z)
z=z+10
r2(y)
y = y -10
w2(y)
w2(z)
commit
Teria della concorrenza
 Modello formale di transazione: “sequenza di azioni
di lettura o scrittura, che si riconoscono eseguiti da
una stessa transazione in quanto caratterizzati dallo
stesso indice”
 Assunzioni:




si considerano le sole operazioni di lettura e scrittura,
omettendo qualsiasi manipolazione dei dati
bot e eof vengono omessi.
non si conosce a priori l’esito della transazione
supponiamo che una transazione non legga o scriva
più di una volta la stessa informazione
S9 = r1(x) r1(z) w1(x)
Teria della concorrenza
 Le transazioni avvengono in modo concorrente quindi
le letture e scritture sono richieste in istanti successivi
da diverse transazioni.
 Uno schedule rappresenta la sequenza di operazioni
di read e write effettuate da transazioni concorrenti
come

w0(x) r1(x) w0(z) r1(z) r2(x) r3(z) w3(z) w1(x)
 Le operazioni compaiono nello schedule come esse
vengono eseguite sulla base di dati
 Il controllore di concorrenza a il compito di accettare
o meno un determinato schedule, al fine di evitare i
problemi esposti.
Teria della concorrenza
 Lo scheduler effettua il compito di coordinare
le esecuzioni parallele:



tiene traccia di tutte le operazioni compiute
accetta o rifiuta le operazioni
progressivamente richieste dalle transazioni
produce uno schedule che non contiene i
problemi esposti.
Teria della concorrenza
 Consideriamo inizialmente transazioni con
esito noto, questo consente di:


eliminare le transazioni che contengono abort
considerare solo transazioni che eseguono
commit (schedule commit proiezione)
 Questo tipo di trattazione ha funzionalità
teorica dato che:


uno scheduler non conosce a priori l’esito di
una transazione
non consente di trattare letture sporche
Teria della concorrenza
 Schedule seriale “tutte le azioni di una transazione
compaiono in sequenza senza essere intercalate da
azioni di altre transazioni”
w0(x) w0(z) r2(x) r1(x) r1(z) w1(x) r3(z) w3(z)
 “L’esecuzione di una commit-proiezione di uno
schedule S è corretta quando produce lo stesso
risultato di un qualunque schedule seriale
contenente le stesse transazioni. In tal caso lo
schedule si dice serializzabile.”
 Per introdurre la nozione di stesso risultato si
introducono diverse nozioni di equivalenza
View-equivalenza
 Definiamo una relazione leggeda che lega due
operazioni: lettura e scrittura.
 Un operazione di lettura ri(x) leggeda wk(x) ( leggeda
( ri(x) , wk(x) ) ) quando wk(x) precede ri(x) e non vi è
nessun wn(x) compreso fra le due operazioni.
 Formalmente leggeda ( ri(x) , wk(x) )  wk(x) < ri(x) 
  wn(x) | wk(x) < wn(x) < ri(x)
S5 = w0(x) r2(x) w2(x) r1(x) w2(z)
Non sono in relazione visto che  w2(x) che precede r1(x)
e viene effettuata dopo w0(x)
View-equivalenza
 Un operazione di scrittura wk(x) viene detta finale se
è l’ultima scrittura sull’ oggetto x che appare nello
schedule.
 w0(x) non è l’ultima scrittura sull’oggetto x
 w2(x) è una scrittura finale sull’ oggetto x
 w2(z) è una scrittura finale sull’ oggetto z
S5 = w0(x) r2(x) w2(x) r1(x) w2(z)
View-equivalenza
 Due schedule vengono detti view-equivalenti
( Si V Sk ) se possiedono la stessa relazione
leggeda e le stesse scritture finali.
 Uno schedule viene detto view-serializzabile
se è view equivalente ad un generico
schedule seriale.
 VSR è l’insieme degli schedule viewserializzabili.
View-equivalenza
S5 = w0(x) r2(x) w2(x) r1(x) w2(z)
leggeda = { ( r2(x) , w0(x) ) ,} ( r1(x) , w2(x) )}
scrittura finale di x = w2(x)
scrittura finale di z = w2(z)
S6 = w0(x) r2(x) w2(x) w2(z) r1(x)
leggeda = { ( r2(x) , w0(x) ) ,} ( r1(x) , w2(x) )}
scrittura finale di x = w2(x)
scrittura finale di z = w2(z)
S4 = w0(x) r1(x) r2(x) w2(x) w2(z)
leggeda = { ( r1(x) , w0(x) ) , ( r2(x) , w0(x) )}
scrittura finale di x = w2(x)
scrittura finale di z = w2(z)
S5 V S6 visto che hanno la stessa relazione leggida e le stesse scritture finali
S5 V S4 visto che non hanno la stessa relazione leggida
S6 è uno schedule seriale poiché le azioni di tutte le transazioni sono in sequenza
quindi S5 è view-serializzabile
View-equivalenza
S3 = w0(x) r2(x) r1(x) w2(x) w2(z)
leggeda = { ( r2(x) , w0(x) ) , ( r1(x) , w0(x) )}
scrittura finale di x = w2(x)
scrittura finale di z = w2(z)
S4 = w0(x) r1(x) r2(x) w2(x) w2(z)
leggeda = { ( r1(x) , w0(x) ) , ( r2(x) , w0(x) )}
scrittura finale di x = w2(x)
scrittura finale di z = w2(z)
S5 = w0(x) r2(x) w2(x) r1(x) w2(z)
leggeda = { ( r2(x) , w0(x) ) , ( r1(x) , w2(x) )}
scrittura finale di x = w2(x)
scrittura finale di z = w2(z)
View-equivalenza
 Lo schedule S corrisponde alla perdita di update e
non è view serializzabile.
 Questo corrisponde ad una schedulazione delle
transazioni in modo da non ottenere un esecuzione
isolata.
 In generale, per dimostrare la non viewserializzabilità occorre permutare in tutti i possibili
modi le transazioni presenti negli schedule seriali e
confrontarli con lo schedule S.
S = r1(x) r2(x) w1(x) w2(x)
S’ = r1(x) w1(x) r2(x) w2(x)
S’ = r2(x) w2(x) r1(x) w1(x)
View-equivalenza
 Determinare la view-equivalenza di due schedule è
un problema lineare:


si determinano le due relazioni leggida
e le scritture finali
 Per verificare che uno schedule è view-serializzabile
è necessario confrontarlo con tutti i possibili schedule
seriali ottenuti permutando le transazioni in esso
contenuto.
 Determinare se uno schedule è view equivalente ad
un qualsiasi schedule seriale è un problema NP-hard
 Si preferisce quindi una nozione di equivalenza più
stretta che non copre tutti i casi, ma che abbia una
complessità inferiore.
Conflict-equivalenza
 definizione di conflitto: “Due azioni ai e ak si
dicono in conflitto (i  k) se entrambe operano
sullo stesso oggetto ed almeno una di esse è
una write”



r2(x) w1(x) è un conflitto lettura scrittura
w2(x) w1(x) è un conflitto lettura scrittura
r2(x) w2(x) non è un conflitto
Conflict-equivalenza
 Uno schedule Si è confilt-equivalente ad uno
schedule Sj ( Si c Sk ) se presentano le stesse
operazioni ed ogni coppia di operazioni in conflitto è
nello stesso ordine in entrambi gli schedule.
 Uno schedule è confilct serializzabile se esiste uno
schedule seriale ad esso conflict equivalente.
 CSR è l’insieme di tutti gli schedule per cui esiste uno
schedule seriale conflict equivalente.
Conflict-equivalenza
 CSR è strettamente contenuto in VSR. In altre parole
esistono schedule che sono view serializzabili ma
non sono conflict serializzabili.
 Tutti gli schedule in CSR sono in VSR
 Quindi la conflict-serializzabilità è una condizione
sufficiente ma non necessaria per la view
seriabilizzabilità.
Conflict-equivalenza
 Domande da porre:



operano sullo stesso oggetto
almeno una delle operazioni è di scrittura
i diverso da j
S9 = w0(x) r1(x) w0(z) r1(z) r2(x) r3(z) w3(z) w1(x)
S10 = w0(x) w0(z) r2(x) r1(x) r1(z) w1(x) r3(z) w3(z)
Conflict-equivalenza
 Naturalmente enumerare in modo esaustivo tutti gli
schedule seriali ripone lo stesso problema.
 E’ possibile determinare se uno schedule è conflictserializzabile mediante il grafo dei conflitti.

Ad ogni transazione dello schedule corrisponde un
nodo del grafo
S9 = w0(x) r1(x) w0(z) r1(z) r2(x) r3(z) w3(z) w1(x)
T0
T1
S10 = w0(x) w0(z) r2(x) r1(x) r1(z) w1(x) r3(z) w3(z)
T2
T3
Conflict-equivalenza
 E’ possibile determinare se uno schedule è conflict-
serializzabile mediante il grafo dei conflitti.


Ad ogni transazione dello schedule corrisponde un
nodo del grafo
Si traccia un arco fra i nodi Ti e Tk se esiste il conflitto
ai ak e ai precede ak nello schedule
S9 = w0(x) r1(x) w0(z) r1(z) r2(x) r3(z) w3(z) w1(x)
T0
T1
S10 = w0(x) w0(z) r2(x) r1(x) r1(z) w1(x) r3(z) w3(z)
T2
T3
Conflict-equivalenza
 E’ possibile determinare se uno schedule è conflict-serializzabile
mediante il grafo dei conflitti.



Ad ogni transazione dello schedule corrisponde un nodo del grafo
Si traccia un arco fra i nodi Ti e Tk se esiste il conflitto ai ak e ai
precede ak nello schedule
Lo schedule è in CSR se e solo se il corrispondente grafo dei conflitti è
aciclico
S9 = w0(x) r1(x) w0(z) r1(z) r2(x) r3(z) w3(z) w1(x)
T0
T1
S10 = w0(x) w0(z) r2(x) r1(x) r1(z) w1(x) r3(z) w3(z)
T2
T3
Conflict-equivalenza
 Nonostante la linearità per determinare se
uno schedule sia serializzabile o meno
questa tecnica non viene applicata:



il grafo risultante può essere di dimensioni
notevoli
La dinamicità vincola in alcuni casi a
ricostruire il grafo.
Si sta operando ancora in un contesto commitproiezione di schedule
 I metodi di locking a due fasi e timestamp
rimuovono le suddette assunzioni
Esercizio 1
 Si consideri il seguente schedule, dove ogni
operazione ri/wi si intende effettuata dalla
transazione Ti:


r1(x) r3(x) r2(x) r1(t) w1(r) r3(r) w1(y) w2(t)
w2(z) w3(t) w1(t)
si dica se lo schedule è VSR oppure no, e
perché, in termini delle relazioni legge-da e
scrittura-finale.
Esercizio 1

r1(x) r3(x) r2(x) r1(t) w1(r) r3(r) w1(y) w2(t) w2(z) w3(t) w1(t)

Dire che lo schedule è in VSR equivale a dimostrare che
esiste un qualunque schedule seriale view-equivalente ad
esso.
La view-equivalenza è definita in terimini delle relazioni:
Un operazione di lettura ri(x) leggeda wk(x) ( leggeda ( ri(x) ,
wk(x) ) ) quando wk(x) precede ri(x) e non vi è nessun wn(x)
compreso fra le due operazioni.




Un operazione di scrittura wk(x) viene detta finale se è l’ultima
scrittura sull’ oggetto x che appare nello schedule
soluzione1: permutare in tutti i possibili modi le transazioni presenti
negli schedule seriali e confrontarli con lo schedule.



r2(x) w2(t) w2(z) r1(x) r1(t) w1(r) w1(t) w1(y) w3(t) r3(r) r3(x)
r1(x) r1(t) w1(r) w1(t) w1(y) r2(x) w2(z) w2(t) w3(t) r3(r) r3(x)
Potrebbero esserci troppe permutazioni possibili
Esercizio 1







r1(x) r3(x) r2(x) r1(t) w1(r) r3(r) w1(y) w2(t) w2(z) w3(t) w1(t)
Soluzione 2:
A causa della presenza della scrittura del dato r da parte della
transazione T1, e la conseguente lettura del dato da parte della
transazione T3. la relazione leggeda contiene la coppia w1(r) r3(r)
l’ ipotetico schedule seriale view-equivalente deve quindi avere
elencate prima le operazioni delle transazioni T1 poi quelle di T3
per avere la stessa relazione leggeda.
r1(x) r3(x) r2(x) r1(t) w1(r) r3(r) w1(y) w2(t) w2(z) w3(t) w1(t)
ma la relazione T1 è l’ultima a scrivere il dato t quindi l’ ipotetico
schedule seriale view-equivalente deve avere elencate prima le
operazioni delle transazioni T3 poi quelle di T1 per avere la stessa
scrittura finale.
ASSURDO
Esercizio 2
 Si consideri il seguente schedule, dove ogni
operazione ri/wi si intende effettuata dalla
transazione Ti:

r1(x) r3(x) w3(x) r2(x) r2(v) r1(t) w1(r) r3(r)
w1(y) w2(z) w3(t) w3(v) w1(t) w3(t)
 si dica se lo schedule è VSR, indicando (se
esiste) un possibile schedule seriale
equivalente. Si svolga l’esercizio,
specificando le relazioni legge-da e scritturafinale.
Locking a due fasi
 Meccanismi che superano le limitazioni
discusse:


Locking a due fasi
Timestamp
 Le operazioni di scrittura e lettura sono
protette con l’esecuzione di tre primitive:



r_lock
w_lock
unlock
Locking a due fasi
DB
r_lock1(x) w_lock1(y) r_lock2(z) ……
scheduler
struttura
dei dati
Lo scheduler riceve una serie di richieste di queste primitive
ne determina la correttezza attraverso l’ispezione di una struttura dati
Locking a due fasi
r_lock1(x) r1(x)…
DB
r_lock1(x) r1(x) r_lock2(x) r2(x) unlock2(x) unlock1(x)
r_lock1(x) r1(x) unlock1(x) ……
scheduler
Vincoli sulle operazioni di read:
ogni operazione di read è preceduta da un r_lock
l’r_lock deve essere seguito da un unlock
il lock è condiviso perché su un dato possono essere
attivi contemporaneamente più lock
struttura
dei dati
Locking a due fasi
DB
w_lock1(x) w1(x)
(x)…
unlock
w_lock12(x)
(x)……
w_lock
w2(x) unlock
2(x) w2(x) unlock2
1(x)
scheduler
Vincoli sulle operazioni di write:
ogni operazione di write è preceduta da un w_lock
il w_lock deve essere seguito da un unlock
il lock è esclusivo perché su un dato non possono essere
attivi contemporaneamente più lock
struttura
dei dati
Locking a due fasi
 Proprietà
 una transazione si dice ben formata quando
rispetta le regole precedentemente illustrate
 l’operazione di lock della risorsa può avvenire
anche prima rispetto all’effettiva lettura e
scrittura
 potremmo avere un’unica operazione di lock
che di fatto è un lock esclusivo
 in generale un lock esclusivo in scrittura
consente anche la lettura o si può passare da
un lock condiviso ad uno esclusivo.
Locking a due fasi
 Lo scheduler riceve le richieste di lock dalle
transazioni e le concede in base a quelle già
precedentemente richieste.
 Quando la richiesta di lock viene concessa
allora si dice che la risorsa viene acquisita
dalla transazione richiedente.
 All’ atto dell’ unlock viene rilasciata.
 Se la richiesta di lock non viene concessa la
transazione viene messa in stato di attesa.
Locking a due fasi
 La richiesta di lock è caratterizzata dalla transazione
richiedente, e dalla risorsa richiesta.
 La politcha di decisione per la concessione dei lock e’
rappresentata nella tabella dei conflitti.
Stato della risorsa X
richiesta
X libera
X concessa
con r_lock
X concessa
con w_lock
r_lock ( x )
ok / r_lock ( x )
ok / r_lock ( x )
no / attesa
w_lock ( x )
ok / w_lock ( x )
no / attesa
no / attesa
unlock
error
ok / dipende
ok / libero
Locking a due fasi
 In generale, lo schedule ottenuto seguendo
queste regole non è serializzabile.
 Occorre porre delle restrizioni sulle singole
transizioni relative all’ordinamento della
richiesta dei lock.
 Locking a due fasi ( 2PL ): una transazione
dopo aver rilasciato un lock non può
acquisirne altri.
Locking a due fasi
Risorse
richieste
Fase crescente
Fase calante
t
Locking a due fasi
 Terema: Se il lock manager rispetta la politica
definita nella tabella dei conflitti e le
transazioni seguono il 2PL, genera schedule
serializzabile.
 La classe 2PL contiene gli schedule che
soddisfano queste condizioni.
Locking a due fasi
 Dim:
 Dimostriamo che la classe 2PL è strettamente contenuta nella






classe CSR
Se uno schedule è in 2PL allora è anche CSR
Supponiamo che lo schedule sia in 2PL sia e non in CSR.
S2PL e SCSR.
evidentemente esiste un ciclo t1 t2 t3 t4 t5 t6 ….. tn t1, t1 e t2
operano in modo conflittuale sulla stessa risorsa
quindi t1 deve rilasciare la risorsa a t2 affinchè si possa
procedere
il conflitto tn t1 stabilisce che la transazione t1 deve attendere
cha la transazione tn rilasci la risorsa prima di acquisirla
Assurdo la transazione t1 non segue il 2PL.
Locking a due fasi
 Le classi 2PL e CSR non sono equivalenti ci
sono schedule in CSR che non sono in 2PL.

r1(x) w1(x) r2(x) w2(x) r3(y) w1(y)
T1
T2
T3
Non è 2PL visto che la transazione T1
deve necessariamente rilasciare la
risorsa x per T2 e richiedere un lock
successivo per la risorsa y.
Locking a due fasi
Tre oggetti x y z con definito il vincolo di integirtà x + y + z = 1000






bot
s=0
r_lock(y)
read(y)
s=y+s
r_lock(z)







read(z)
s=s+z
r_lock(x)
read(x)
s=s+x
unlock(x) unlock(y) unlock(z)
commit








w_lock(x)
w_lock(z)
read(x)
read(z)
x=x+10
z=z-10
write(z)
unlock(z)

write(x)


unlock(x)
commit
Timestamp
 Semplice ma meno efficace del locking a due fasi
 Un timestamp è un evento che viene assiciato ad
ogni operazione nel sistema. (ad esempio l’orario)
 Il controllo mediante il metodo TS avviene nel
seguente modo:


Ad ogni transazione si associa un timestamp che
rappresenta il momento di inizio
si accetta uno schedule se e solo riflette l’ordinamento
seriale delle transazioni in base al valore del
timestamp di ciascuna transazione.
Timestamp
 Ad ogni oggetto x si associano due indicatori


WTM(x): il ts della transazione con timestamp
più grosso che ha eseguito l’ultima scrittura
RTM(x): il ts della transazione con timestamp
più grosso che ha eseguito l’ultima lettura
 Le richieste che arrivano allo scheduler sono
del tipo read(x,ts) e write(x,ts) dove ts è il
timestamp della transazione che esegue la
lettura o la scrittura.
Timestamp
 Politica dello scheduler
 read(x,ts): se ts < WTM(x) la transazione viene uccisa
altrimenti è accettata, RTM(x) è posto al valore
massimo fra RTM(x) e ts
 write(x,ts): se ts < WTM (x) o ts < RTM(x) la
transazione viene uccisa altrimenti viene accettata.
WTM(x) viene aggiornato con il valore di ts
 Ogni transazione non può leggere o scrivere un dato
scritto da una transazione con timestamp superiore
 Non può scrivere un dato già letto da una transazione
con timestamp superiore
Timestamp
valori

ok
RTM(x)=7

r(x,9)
ok
RTM(x)=9
w(x,8)
no
T8 uccisa
w(x,11)
ok
WTM(x)=11
r(x,10)
no
T10 uccisa
richieste
risposte
r(x,6)
ok
r(x,7)
read(x,ts): se ts < WTM(x)
la transazione viene uccisa
altrimenti è accettata,
RTM(x) è posto al valore
massimo fra RTM(x) e ts
write(x,ts): se ts < WTM (x)
o ts < RTM(x) la transazione
viene uccisa altrimenti viene
accettata. WTM(x) viene
aggiornato con il valore di ts
 RTM(x)=7
 WTM(x)=5
Timestamp
 IL metodo TS uccide un elevato numero di
transazioni.
 Per migliorarlo:

Pre-write: simile ad un lock in scrittura. Vengono rimandate
le letture che manderebbero in cattivo esito la scrittura. Fino
a quando il valore non viene effettivamente scritto.
(x)=0
RTM (x)=4
WTM(x)=0
r2(x) r3(x) r4(x) w1(x)
viene uccisa
visto di
La transazione t1 segnala
l’intenzione
che 1<RTM(x)=4
effettuare
una scrittura
w1(x) r2(x) r3(x) r4(x)
Timestamp
 Utilizzo delle multiversioni: si mantengono
diverse copie dello stesso oggetto una per
ogni transazione che lo modifica.
 Ogni volta che una transazione genera una
nuova copia dell’oggetto x, (la i-esima) viene
creata una nuova copia WTMi(x).
 RTM(x) rimane globale
Timestamp
 Regole:

r(x,ts): una lettura è sempre accettata, sia
WTMi(x) l’ultima versione aggiornata di x



se ts > i si legge WTMi(x)
altrimenti si sceglie una versione k t.c. WTMk(x) <
ts < WTMk+1 (x)
w(x,ts): se ts < RTM si rifiuta la richiesta
altrimenti si inserisce la i-esima copia
WTMi(x)=ts
Timestamp
 Nei sistemi reali le copie che si mantengono
sono al massimo 2.
 Questa tecnica introdotta per il metodo
basato sui timestamp, viene poi utilizzata
anche nel metodo di locking a due fasi.
Classi
VSR
CSR
TS
2PL
Classi
 La classe VSR include strettamente la classe
CSR
 La classe CSR include strettamente la classi
2PL e TS
 2PL e TS hanno intersezione non nulla ma
non sono una inclusa nell’altra
 Dimostriamo che ci sono schedule che sono
in TS ma non in 2PL
 Schedule che sono in 2PL ed in TS
 Schedule che sono in 2PL ma ma non in TS
Classi
 Il seguente schedule è in VSR?
 r1(x)w1(x)r2(x)r3(x)w2(y)r1(z)w3(z)r3(t)w3(t)r4(t)w4(y)w5(y)
T2
T3
T1
T4
T5
Classi
 Consideriamo gli indici delle transazioni come il TS ad essi
assegnato
 r1(x)w1(x)r2(x)r3(x)w2(y)r1(z)w3(z)r3(t)w3(t)r4(t)w4(y)w5(y)
 Lo schedule è in TS
 Considerando ogni oggetto del DB ogni transazione opera
nell’ordine indotto dal loro timestamp.
 Lo schedule è quindi inTS
 Non vi è mai una transazione che tenta di leggere un valore
scritto da una transazione con timestamp più grosso
 Non vi è mai una transazione che tenta di scrivere un oggetto
letto o scritto da una transazione con ts maggiore
Classi
 r1(x)w1(x)r2(x)r3(x)w2(y)r1(z)w3(z)r3(t)w3(t)r4(t)w4(y)w5(y)
 Lo schedule non è in 2PL
 La transazione 1 legge l’oggetto x ed è poi costretta a rilasciarlo
per la transazione2
 Poi essa acquisisce nuovamente l’oggetto z.
 Abbiamo quindi uno schedule TS ma non 2PL
Classi
 r1(x)w1(x)r2(x)w2(x)
 questo schedule è sia in TS che in 2PL
 r2(x)w2(x)r1(x)w1(x)


non è in TS in quanto la transazione con
timestamp superiore legge successivamente x
ma è in 2PL visto che le risorse vengono
allocate in modo oridinato
Classi
 Nel 2PL le transazioni sono poste in attesa,
nel TS uccise
 Nel 2PL l’ordine è imposto dai conflitti, nel TS
dai timestamp
 Il 2PL può portare a blocchi critici
 Costa più il restart del TS rispetto all’attesa
del 2PL
Gestione dei Lock
 Il lock manager riceve le richieste di r_lock w_lock e un_lock
caratterizzate dalle seguenti segnature:
 r_lock(T,x,errcod,timeout)
 w_lock(T,x,errcod,timeout)
 un_lock(T,x)
 Se la richiesta non può essere subito soddisfatta il processo
viene messo in coda
 La probabilità di essere messi in coda (conflitti) è pari a:
 (numero di transazioni x oggetti medi richiesti) / oggetti totali
 Quando scatta il timeout una transazione può decidere:
 di effettuare un rollback e ripartire dall’inizio
 richiedere nuovamente la risorsa conservando quelle
acquisite
Gestione dei lock
 Struttura delle tabelle dei conflitti, per ogni
oggetto del DB ci sono:


tre bit per lo stato dell’oggetto
un contatore per i processi in attesa
Lock gerarchico
 Tutte le tecniche teoriche viste funzionano
indipendentemente dalla risorsa su cui viene
effettuato il lock: tabelle, tuple, campi di singole tuple
 Granularità dei lock: si possono specificare lock a
diversi livelli


lock a livello molto alto (tabelle) limitano l’accesso
concorrente su tuple diverse aumentando i conflitti.
D’altra parte transazioni che effettuano consuntivi
(solitamente veloci) hanno bisogno di lock su tabelle
intere. Lock molto granulari renderebbero oneroso il
lavoro del lock manager esponendolo a rischi di
fallimento
 Per ovviare a questo problema si utilizza il lock
gerarchico
Lock gerarchico
 Ogni transazione può
operare ad un livello
prescelto della
gerarchia, definendo in
modo efficiente i lock di
cui ha bisogno
 Transazioni per il
backup dei DB possono
operare anche lock a
livello di DB
DB
Tab1
Tab2
parte1
tupla1
Tabn
parte2 …….
tupla2 …….
Lock gerarchico
 Primitive fornite dalla
tecnica:
 XL: lock esclusivo.
 SL: lock condiviso.
 ISL: intenzione di
bloccare uno dei “figli”
del nodo attuale in modo
condiviso.
 IXL: intenzione di
bloccare uno dei “figli”
del nodo attuale in modo
esclusivo.
 SIXL: lock condiviso del
nodo attuale e intenzione
di bloccare in modo
esclusivo uno dei figli.
DB
Tab1
Tab2
parte1
tupla1
Tabn
parte2 …….
tupla2 …….
Lock gerarchico
 Per richiedere in modo
esclusivo una tupla
occorrerà un IXL a
livello di DB, Tab e
parte. Una volta
ottenuto quello della
parte richiedere l’XL a
livello di tupla.
 Le risorse vengono
sempre rilasciate in
ordine inverso
DB
Tab1
Tab2
parte1
tupla1
Tabn
parte2 …….
tupla2 …….
Lock gerarchico
 Regole:
 Si richiedono i lock partendo dalla radice, scendendo
verso l’albero
 Si rilasciano le risorse partendo da quella con
granularità più bassa e risalendo l’albero.
 Per poter richiedere un SL o ISL su un nodo Si deve
giè possedere un SIXL o IXL sul padre
 Per poter richiedere un IXL, XL o SIXL su un nodo, si
deve già possedere un lock SIXL o IXL
Lock gerarchico
Stato risorsa
rischiest
a
DB
ISL
IXL
SL
SIXL
XL
free
Tab1
ISL
Ok
Ok
Ok
Ok
No
Ok
IXL
Ok
Ok
No
no
No
Ok
SL
Ok
No
Ok
No
No
Ok
SIXL
Ok
No
No
No
No
Ok
Tab2
parte1
tupla1
XL
No
No
no
no
no
Ok
Tabn
parte2 …….
tupla2 …….
Livelli di lock in lettura
 Compromesso prestazioni correttezza
 Le soluzioni proposte garantiscono la
correttezza ma possono degradare le
performance del sistema
 Si preferisce rinunciare alla correttezza di
letture a discapito delle performance
 Si definiscono tre livelli di consistenza in
ordine crescente
Livelli di lock in lettura
 Committed read: si richiede che i Dati letti sianio
quelli che effettivamente derivano da una commit
della transazione.


questo evita le letture sporche
la perdita di update?
 Cursor stability: per acceddere ad intere tabelle la
transazione viola il principio del 2PL. Effettuando il
lock e l’un_lock di una riga alla volta.
 Repeteable read: coincide col 2PL.
 A seconda della condizione si utilizza la strategia piu’
adeguata, ad esempio per transazioni bancarie si
utilizza il terzo livello.
Blocco critico (deadlock)
 Un problema rilevante tipico dei sistemi
concorrenti in cui si introducono attese.
 T1:r(x)w(y)
 T2:r(y)w(x)
 S: r_lock1(x) r_lock2(y) r1(x) r2(y) w_lock1(y)
w_lock2(x)
 T1 attende che l’oggetto y sia liberato daT2
 T2 attende che l’oggetto x sia liberato da T1
Blocco critico (deadlock)
 La probabilità che si verifiche un blocco
critico è molto bassa
 Ci sono 3 tecniche per risolvere il blocco
critico:



timeout
prevenzione
rilevamento
Timeout
 Utilizzato nella maggior parte dei DBMS reali
 Una transazione viene tenuta un tempo limitato in
attesa sulla risorsa
 Scaduta l’attesa alla transazione viene data una
risposta negativa per il lock richiesto
 In questo modo transazioni in deadlock vengono tolte
dall’attesa e forse abortite.
 Scelta del timeout


alta: risolve tardi i deadlock
basso: tende a rilevare come blocchi critici anche
semplice attese sulle risorse. Si uccidono quindi
transazioni che erano in semplice attesa sprecando
lavoro e tempo.
Prevenzione dei blocchi critici
 Sol1: una tecnica prevede di dichiarare all’inizio tutte
le risorse che la transazione dovrà utilizzare (spesso
non note all’inizio)
 Sol2: Si acquisiscono timestamp e ti attende la
risorsa acquisita da tj solo sotto determinate
condizioni (es i < j):

50% delle transazioni che generano conflitto vengono
messe in coda il restante uccise.
 per la scelta delle transizioni da uccidere
distinguiamo tutte le politiche in:


interrompenti: si uccide la transazione che detiene la
risorsa
non-interrompenti: la transazione viene uccisa solo
all’atto di fare una nova richiesta
Prevenzione dei blocchi critici
 Possiamo uccidere le transazioni che hanno fatto
meno lavoro



starvation: blocco individuale una transazione all’inizio
utilizza un oggetto su cui il conflitto e’ molto probabile.
Avendo fatto poco lavoro viene uccisa ripetutamente.
Per risolvere il problema una transazione non può
essere uccisa ripetutamente
Tecnica poco usata visto che per un ogni 2 conflitti si
uccide mediamente una transazione e la probabilità del
blocco critico è molto più bassa rispetto ad un conflitto.
Rilevamento dei deadlock
 Periodicamente si scorrono le tabelle di
allocazione delle risorse alla ricerca di
transazioni in deadlock
 Il rilevamento viene fatto analizzando le
relazioni di attesa fra le varie transazioni
determinando se esistono cicli.
Esercizio
 Dire se il seguente schedule
 w2(y)r1(z)w3(z)r3(t)w3(t)r4(t)w4(y)w5(y) r1(x)w1(x)r2(x)r3(x)
 è in VSR
Esercizio
 Si consideri il seguente schedule, dove ogni
operazione ri/wi si intende effettuata dalla
transazione Ti:
 r1(x) r3(x) w3(x) r2(x) r2(v) r1(t) w1(r) r3(r)
w1(y) w2(z) w3(t) w3(v) w1(t) w3(t)
 si dica se lo schedule è VSR, indicando (se
esiste) un possibile schedule seriale
equivalente. Si svolga l’esercizio,
specificando le relazioni legge-da e scritturafinale.
Esercizio
 T1 = r1(x) r1(t) w1(r) w1(y) w1(t) legge x e t
da T0 (stato iniziale), s.f. di y ed r
 T2 = r2(x) r2(v) w2(z) legge x da T3 e v da
T0 s.f. di z
 T3 = r3(x) w3(x) r3(r) w3(t) w3(v) w3(t) legge
x da T0 ed r da T1, s.f. x, t, v
 Innanzitutto si ha T3 < T2, perchè T2 legge x
da T3. Ma si ha anche T2 < T3, perché T2
legge v da T0, e invece T3 scrive v.
 Dunque lo schedule non è VSR.
Esercizio
 Quali anomalie producono i seguenti
schedule:
 r1(x) r2(x) w1(x) w2(x) perdita di udate
 r1(x) r1(y) r2(z) r2(y) w2(y) w2(z) r1(z)
 update fantasmi
Esercizio
 r1(x) r3(x) r2(x) r1(t)
w1(r) r3(r) w1(y) w2(t)
w2(z) w3(t) w1(t)
 WTM(x)=0
 RTM(X) =0
 WTM(t) =0
 RTM(t) =0
 WTM(r) =0
 RTM(r) =0
 WTM(y) =0
 RTM(y) =0
 RTM(z)=0
 WTM(z)=0
Esercizio
 Dire a quale situazione corrisponde lo
schedule seguente, supponendo che tutti i
lock richiesti vengano concessi:
r_lock1(x), r_lock2(y), r_lock3(z), w_lock3(x),
w_lock1(y) w_lock2(z)
Esercizio
 r1(x) r3(x) r2(x) r1(t)
w1(r) r3(r) w1(y) w2(t)
w2(z) w3(t) w1(t)
 WTM(x)=0
 RTM(X) =1
 WTM(t) =0
 RTM(t) =0
 WTM(r) =0
 RTM(r) =0
 WTM(y) =0
 RTM(y) =0
 RTM(z)=0
 WTM(z)=0
Esercizio
 r1(x) r3(x) r2(x) r1(t)
w1(r) r3(r) w1(y) w2(t)
w2(z) w3(t) w1(t)
 WTM(x)=0
 RTM(X) =3
 WTM(t) =0
 RTM(t) =0
 WTM(r) =0
 RTM(r) =0
 WTM(y) =0
 RTM(y) =0
 RTM(z)=0
 WTM(z)=0
Esercizio
 r1(x) r3(x) r2(x) r1(t)
w1(r) r3(r) w1(y) w2(t)
w2(z) w3(t) w1(t)
 WTM(x)=0
 RTM(X) =3
 WTM(t) =0
 RTM(t) =0
 WTM(r) =0
 RTM(r) =0
 WTM(y) =0
 RTM(y) =0
 RTM(z)=0
 WTM(z)=0
Esercizio
 r1(x) r3(x) r2(x) r1(t)
w1(r) r3(r) w1(y) w2(t)
w2(z) w3(t) w1(t)
 WTM(x)=0
 RTM(X) =3
 WTM(t) =0
 RTM(t) =1
 WTM(r) =0
 RTM(r) =0
 WTM(y) =0
 RTM(y) =0
 RTM(z)=0
 WTM(z)=0
Esercizio
 r1(x) r3(x) r2(x) r1(t)
w1(r) r3(r) w1(y) w2(t)
w2(z) w3(t) w1(t)
 WTM(x)=0
 RTM(X) =3
 WTM(t) =0
 RTM(t) =1
 WTM(r) =1
 RTM(r) =0
 WTM(y) =0
 RTM(y) =0
 RTM(z)=0
 WTM(z)=0
Esercizio
 r1(x) r3(x) r2(x) r1(t)
w1(r) r3(r) w1(y) w2(t)
w2(z) w3(t) w1(t)
 WTM(x)=0
 RTM(X) =3
 WTM(t) =0
 RTM(t) =1
 WTM(r) =1
 RTM(r) =3
 WTM(y) =0
 RTM(y) =0
 RTM(z)=0
 WTM(z)=0
Esercizio
 r1(x) r3(x) r2(x) r1(t)
w1(r) r3(r) w1(y) w2(t)
w2(z) w3(t) w1(t)
 WTM(x)=0
 RTM(X) =3
 WTM(t) =0
 RTM(t) =1
 WTM(r) =1
 RTM(r) =3
 WTM(y) =1
 RTM(y) =0
 RTM(z)=0
 WTM(z)=0
Esercizio
 r1(x) r3(x) r2(x) r1(t)
w1(r) r3(r) w1(y) w2(t)
w2(z) w3(t) w1(t)
 WTM(x)=0
 RTM(X) =3
 WTM(t) =2
 RTM(t) =1
 WTM(r) =1
 RTM(r) =3
 WTM(y) =1
 RTM(y) =0
 RTM(z)=0
 WTM(z)=0
Esercizio
 r1(x) r3(x) r2(x) r1(t)
w1(r) r3(r) w1(y) w2(t)
w2(z) w3(t) w1(t)
 WTM(x)=0
 RTM(X) =3
 WTM(t) =2
 RTM(t) =1
 WTM(r) =1
 RTM(r) =3
 WTM(y) =1
 RTM(y) =0
 RTM(z)=0
 WTM(z)=2
Esercizio
 r1(x) r3(x) r2(x) r1(t)
w1(r) r3(r) w1(y) w2(t)
w2(z) w3(t) w1(t)
 1 uccisa
 WTM(x)=0
 RTM(X) =3
 WTM(t) =3
 RTM(t) =1
 WTM(r) =1
 RTM(r) =3
 WTM(y) =1
 RTM(y) =0
 RTM(z)=0
 WTM(z)=2