Swappa : Uni / Basi di Dati - Complementi

Torna alla pagina di Basi di Dati - Complementi

 :: Basi di Dati - Complementi ::

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 è 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 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 WTM(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:

RICHIESTA	RISPOSTA	RTM	WTM	TRANS.UCCISA
		4	2
read(x,3)	OK	4	2
write(x,6)	OK	4	6
write(x,9)	OK	4	9
read(x,8)	NO	4	9	t₈
read(x,10)	OK	10	9

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₁) = 10 e WTM(x₁) = 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.

N.RIGA	RICHIESTA	RISPOSTA	x_k	RTM(x_k)	WTM(x_k)	TRANS.UCCISA
			x₁	10	8
1	read(x,12)	OK	x₁	12	8
2	write(x,12)	OK	x₂	12	12
3	write(x,15)	OK	x₃	15	15
4	write(x,9)	NO				t₉
5	read(x,14)	OK	x₂	14	12

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₁ (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₁ (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₁₊₁ = x₂, 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₁ (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₉
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₂ (12), quindi la lettura avverrà su esso. Il timestamp è maggiore dell'RTM precedente, quindi lo sostituirà

Torna alla pagina di Basi di Dati - Complementi