Tecnologia di un data base server: Controllo della Concorrenza Leonardo Mostarda Sea Lab.

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 concorrentiperdita di update

bot r1(x) x=x+1

w1(x) commit

bot r2(x) x=x+1 w2(x) commit

Siano date le transazioni:t1: r1(x), x = x +1, w2(x) t2: r1(x), x = x +1, w2(x)

Anomalia delle transazioni concorrentiLetture sporche

bot r1(x) x=x+1 w1(x)

abort

bot r2(x) x=x+1 w2(x) commit

Siano date le transazioni:t1: r1(x), x = x +1, w2(x) t2: r1(x), x = x +1, w2(x)

Tecnologia data base server

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

Tre oggetti x y z con definito il vincolo di integirtà x + y + z = 1000

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)


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.


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.


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


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 view-serializzabili.

View-equivalenza

S5 = w0(x) r2(x) w2(x) r1(x) w2(z)

S6 = w0(x) r2(x) w2(x) w2(z) r1(x)

leggeda = { ( r2(x) , w0(x) ) }leggeda = { ( r2(x) , w0(x) ) , ( r1(x) , w2(x) )}

leggeda = { ( r2(x) , w0(x) ) }leggeda = { ( r2(x) , w0(x) ) , ( r1(x) , w2(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

S4 = w0(x) r1(x) r2(x) w2(x) w2(z) leggeda = { ( r1(x) , w0(x) ) , ( r2(x) , w0(x) )}


S5 V S4 visto che non hanno la stessa relazione leggida

S6 è uno schedule seriale poiché le azioni di tutte le transazioni sono in sequenzaquindi S5 è view-serializzabile

View-equivalenza

S5 = w0(x) r2(x) w2(x) r1(x) w2(z) leggeda = { ( r2(x) , w0(x) ) , ( r1(x) , w2(x) )}


S3 = w0(x) r2(x) r1(x) w2(x) w2(z)

S4 = w0(x) r1(x) r2(x) w2(x) w2(z)

leggeda = { ( r2(x) , w0(x) ) , ( r1(x) , w0(x) )}

leggeda = { ( r1(x) , w0(x) ) , ( r2(x) , w0(x) )}



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 view-serializzabilità 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


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.


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à.


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)


Naturalmente enumerare in modo esaustivo tutti gli schedule seriali ripone lo stesso problema.

E’ possibile determinare se uno schedule è conflict-serializzabile mediante il grafo dei conflitti. Ad ogni transazione dello schedule corrisponde un

nodo del grafo



T0

T1 T2

T3


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



T0

T1 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



T0

T1 T2

T3


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 commit-

proiezione 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 scrittura-finale.

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

scheduler

DB

r_lock1(x) w_lock1(y) r_lock2(z) ……strutturadei dati

Lo scheduler riceve una serie di richieste di queste primitivene determina la correttezza attraverso l’ispezione di una struttura dati

Locking a due fasi

scheduler

DB

r_lock1(x) r1(x) unlock1(x) ……

strutturadei dati

Vincoli sulle operazioni di read:

r_lock1(x) r1(x) r_lock2(x) r2(x) unlock2(x) unlock1(x)

r_lock1(x) r1(x)…

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 essereattivi contemporaneamente più lock

Locking a due fasi

scheduler

DB

w_lock1(x) w1(x) unlock1(x) ……

strutturadei dati

Vincoli sulle operazioni di write:

w_lock1(x) w1(x) w_lock2(x) w2(x) unlock2(x) unlock1(x) w_lock1(x) w1(x)…

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 essereattivi contemporaneamente più lock

w_lock1(x) w1(x) unlock1(x) w_lock2(x) w2(x) unlock2(x)

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.

richiesta

Stato della risorsa X

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

Risorserichieste

t

Fase crescente

Fase calante

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.

S2PL e SCSR. 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

T3

T2

Non è 2PL visto che la transazione T1deve necessariamente rilasciare la risorsa x per T2 e richiedere un locksuccessivo per la risorsa y.

Locking a due fasi

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

Tre oggetti x y z con definito il vincolo di integirtà x + y + z = 1000

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 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

richieste risposte valori

r(x,6) ok

r(x,7) 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

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.

w1(x) r2(x) r3(x) r4(x)r2(x) r3(x) r4(x) w1(x)

La transazione t1 segnala l’intenzione dieffettuare una scrittura

RTM (x)=0WTM(x)=0RTM (x)=4WTM(x)=0

La transazione t1 viene uccisa vistoche 1<RTM(x)=4

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

VSRCSR

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)

T1

T5

T3

T4

T2

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 Tabn

parte1 parte2 …….

tupla1 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 Tabn



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 Tabn



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

DB

Tab1 Tab2 Tabn



rischiesta

Stato risorsa

ISL IXL SL SIXL XL free

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

XL No No no no no Ok

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 scrittura-finale.

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



Esercizio



Esercizio



Esercizio



Esercizio



Esercizio



Esercizio



Esercizio



Esercizio



Esercizio


1 uccisa


Date post:	01-May-2015
Category:	Documents
Upload:	fabio-sartori
View:	219 times
Download:	1 times

Tecnologia di un data base server: Controllo della Concorrenza Leonardo Mostarda Sea Lab.

Documents