cerca
Basi di Dati - Complementi - Esercizi: Timestamp
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

Uni.BDC-Timestamp History

Show minor edits - Show changes to output

Changed line 38 from:
** '''accettata''' se [@ts >= RTM(x)@]. Bisognerà quindi aggiornare il valore RTM(x) assegnandogli quello di ''ts''
to:
** '''accettata''' se [@ts >= RTM(x)@]. Bisognerà quindi aggiornare il valore WTM(x) assegnandogli quello di ''ts''
Added lines 1-164:
(:title Basi di Dati - Complementi - Esercizi: Timestamp:)
[[Torna alla pagina di Basi di Dati - Complementi -> BDComplementi]]
----

%titolo%''':: Basi di Dati - Complementi ::'''

%center%%sottotitolo%'''Esercizi: Timestamp'''

!!Teoria
Il ''timestamp'' è un metodo per il controllo della concorrenza utilizzato per garantire la serializzabilità di uno schedule. L'unico motivo per il quale non è stato trattato in [[questa pagina->BDC-Serializzabilità]] è che viene generalmente sottoposto come esercizio separato.

Anzitutto, cos'è il timestamp? E' un identificatore generato dall'orologio di sistema che definisce un ordinamento temporale tra gli eventi generati dal sistema stesso: ogni evento avrà un timestamp maggiore (quindi diverso) da quello degli eventi che l'hanno preceduto. Il principio del controllo di concorrenza è che uno schedule viene accettato solo se soddisfa l'ordine seriale delle transazioni basato sui valori dei timestamp.

A ogni oggetto (risorsa) ''x'' sono associati due indicatori:
* '''WTM(x)''': il massimo timestamp tra le transazioni che hanno scritto x, o in altre parole la transazione che vi ha eseguito l'ultima scrittura
* '''RTM(x)''': il massimo timestamp tra le transazioni che hanno letto x, o in altre parole la transazione che vi ha eseguito l'ultima lettura

Le richieste che arrivano al gestore dello scheduler possono essere di due tipi:
* '''read(x, ts)''', ovvero la richiesta di lettura dell'oggetto x con ''ts'' timestamp della transazione
* '''write(x, ts)''', ovvero la richiesta di scrittura dell'oggetto x con ''ts'' timestamp della transazione

Uno dei vantaggi di questo metodo è la scomparsa delle variabili di lock, che come sappiamo da [[certe materie->Sistemi Operativi]] possono incorrere in simpatiche situazioni come il deadlock. Ha però come svantaggio il fatto di comportare molti più rifiuti e di funzionare solo con l'assunzione di commit-proiezione (a meno di bufferizzare le scritture).

Una variante del metodo è l'utilizzo delle ''multiversioni'': le scritture avvengono su nuove copie dell'oggetto, così che le letture possano essere sempre accettate (e dirette verso la versione dei dati corretta rispetto il loro timestamp).

!!Cosa fare
!!!!Timestamp monoversione
Un classico esercizio sul timestamp monoversione è, data una sequenza di operazioni e i valori iniziali dell'RTM(x) e WTM(x), stabilire se le operazioni vengono accordate o meno e aggiornare i valori di RTM e WTM.

Le regole da applicare per accettare o rifiutare un'operazione sono le seguenti:

* se ho una ''read(x, ts)'' la dovrò:
** '''rifiutare''' se [@ts < WTM(x)@]. La transazione andrà riportata tra quelle uccise
** '''accettata''' se [@ts >= WTM(x)@]. Bisognerà quindi aggiornare il valore RTM(x) assegnandogli il valore più grande tra il ''ts'' e l'RTM(x) precedente

* se ho una ''write(x, ts)'' la dovrò:
** '''rifiutare''' se [@ts < RTM(x)@] oppure [@ts < WTM(x)@]. La transazione andrà riportata tra quelle uccise
** '''accettata''' se [@ts >= RTM(x)@]. Bisognerà quindi aggiornare il valore RTM(x) assegnandogli quello di ''ts''

Consideriamo ad esempio un controllo di concorrenza monoversione basato su timestamp e un oggetto x con timestamp RTM(x) = 4 e WTM(x) = 2. Date le seguenti operazioni:\\
[@read(x,3) , write(x,6), write(x,9), read(x,8), read(x,10), write(x,13)@]
indicare se l'operazione viene accordata o meno, indicare eventuali transazioni uccise e aggiornare i valori di RTM(x) e WTM(x).\\
La risoluzione del problema viene strutturata in forma tabellare: avremo una colonna per le richieste (le operazioni), una per le risposte (OK/NO), una per i valori di RTM e WTM aggiornati e un'ultima dove indicare le transazioni uccise, se ci sono. Nel nostro caso avremo:

(:table align=center width=550px:)
(:cellnr bgcolor=#d4e1f0 align=center:)'''RICHIESTA'''
(:cell bgcolor=#d4e1f0 align=center:)'''RISPOSTA'''
(:cell bgcolor=#d4e1f0 align=center:)'''RTM'''
(:cell bgcolor=#d4e1f0 align=center:)'''WTM'''
(:cell bgcolor=#d4e1f0 align=center:)'''TRANS.UCCISA'''
(:cellnr:)
(:cell:)
(:cell:)4
(:cell:)2
(:cell:)
(:cellnr:)read(x,3)
(:cell:)OK
(:cell:)4
(:cell:)2
(:cell:)
(:cellnr:)write(x,6)
(:cell:)OK
(:cell:)4
(:cell:)6
(:cell:)
(:cellnr:)write(x,9)
(:cell:)OK
(:cell:)4
(:cell:)9
(:cell:)
(:cellnr:)read(x,8)
(:cell:)NO
(:cell:)4
(:cell:)9
(:cell:)t'_8_'
(:cellnr:)read(x,10)
(:cell:)OK
(:cell:)10
(:cell:)9
(:cell:)
(:tableend:)

Perché [@read(x,8)@] è stato rifiutato? Perché il suo timestamp era inferiore al WTM(x) precedente: 8 < 9!!

!!!!Timestamp multiversione
Gli esercizi sui timestamp multiversioni sono simili a quelli monoversione, con la differenza che dovrò considerare gli RTM(x'_i_') e i WTM(x'_i_') della versione i-sima della risorsa.

Le regole da applicare per accettare o rifiutare un'operazione saranno dunque le seguenti:

* se ho una ''read(x, ts)'' la dovrò '''sempre accettare'''. In particolare:
** tra tutti gli x'_i_' con WTM(x'_j_') <= ''ts'', leggerà da quello che ha il WTM(x'_j_') maggiore
** aggiornerà il valore dell'RTM(x'_i_') assegnandogli il valore più grande tra il suo ''ts'' e l'RTM della stessa versione
** il WTM(x'_i_') non cambia

* se ho una ''write(x, ts)'' dovrò prima di tutto individuare tra tutte le versioni x'_i_' con WTM(x'_j_') <= ''ts'', quella che ha il WTM(x'_j_') maggiore. A questo punto dovrò:
** '''rifiutare''' se ''ts'' < RTM(x'_i_'). La transazione andrà riportata tra quelle uccise
** '''accettare''' se ''ts'' >= RTM(x'_i_'). Bisognerà quindi creare una nuova versione x'_i+1_' e assegnarle stessi valori di WTM(x'_i+1_') e RTM(x'_i+1_') pari al valore del suo ''ts''

Consideriamo ad esempio un controllo di concorrenza multiversione basato su timestamp e un oggetto x con timestamp RTM(x'_1_') = 10 e WTM(x'_1_') = 8. Date le seguenti operazioni:\\
[@read(x,12) , write(x,12), write(x,15), write(x,9), read(x,14), read(x,17)@]
indicare se l'operazione viene accordata o meno, indicare eventuali transazioni uccise e aggiornare i valori di RTM(x'_i_') e WTM(x'_i_').\\
Anche in questo caso dovremo compilare una tabella simile a quella vista per i timestamp monoversione, con l'aggiunta di una colonna ove indicare le versioni da associare alle varie richieste. Aggiungiamo inoltre per comodità di studio una colonna iniziale per indicare il numero di riga.

(:table align=center width=550px:)
(:cellnr bgcolor=#d4e1f0 align=center:)'''N.RIGA'''
(:cell bgcolor=#d4e1f0 align=center:)'''RICHIESTA'''
(:cell bgcolor=#d4e1f0 align=center:)'''RISPOSTA'''
(:cell bgcolor=#d4e1f0 align=center:)'''x'_k_' '''
(:cell bgcolor=#d4e1f0 align=center:)'''RTM(x'_k_') '''
(:cell bgcolor=#d4e1f0 align=center:)'''WTM(x'_k_') '''
(:cell bgcolor=#d4e1f0 align=center:)'''TRANS.UCCISA'''
(:cellnr:)
(:cell:)
(:cell:)
(:cell:)x'_1_'
(:cell:)10
(:cell:)8
(:cell:)
(:cellnr:)1
(:cell:)read(x,12)
(:cell:)OK
(:cell:)x'_1_'
(:cell:)12
(:cell:)8
(:cell:)
(:cellnr:)2
(:cell:)write(x,12)
(:cell:)OK
(:cell:)x'_2_'
(:cell:)12
(:cell:)12
(:cell:)
(:cellnr:)3
(:cell:)write(x,15)
(:cell:)OK
(:cell:)x'_3_'
(:cell:)15
(:cell:)15
(:cell:)
(:cellnr:)4
(:cell:)write(x,9)
(:cell:)NO
(:cell:)
(:cell:)
(:cell:)
(:cell:)t'_9_'
(:cellnr:)5
(:cell:)read(x,14)
(:cell:)OK
(:cell:)x'_2_'
(:cell:)14
(:cell:)12
(:cell:)
(:tableend:)

Commentiamo ora riga per riga:
# la lettura è sempre sicuramente accettata. Tra tutti i WTM di tutte le versioni, con valore minore del timestamp, il maggiore è quello associato a x'_1_' (8), quindi la lettura avverrà su esso. Il timestamp è maggiore dell'RTM precedente, quindi lo sostituirà
# tra tutti i WTM di tutte le versioni, con valore minore del timestamp, il maggiore è quello associato a x'_1_' (8). L'RTM corrispondente ha valore 12, che è minore uguale a quello del timestamp (12): quindi l'operazione di scrittura può avvenire. La versione sarà la x'_1+1_' = x'_2_', mentre RTM e WTM saranno fissati entrambi a 12
# stesso ragionamento del punto precedente
# tra tutti i WTM di tutte le versioni, con valore minore del timestamp, il maggiore è quello associato a x'_1_' (8). L'RTM corrispondente ha valore 12, che è maggiore del timestamp (9): quindi l'operazione di scrittura deve essere rifiutata. Nell'ultima colonna andrà scritto che la transazione uccisa è la t'_9_'
# la lettura è sempre sicuramente accettata. Tra tutti i WTM di tutte le versioni, con valore minore del timestamp (quindi tra 8 e 12), il maggiore è quello associato a x'_2_' (12), quindi la lettura avverrà su esso. Il timestamp è maggiore dell'RTM precedente, quindi lo sostituirà

----
[[Torna alla pagina di Basi di Dati - Complementi -> BDComplementi]]