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
| t8
|
| 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(xi) e i WTM(xi) 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 xi con WTM(xj) <= ts, leggerà da quello che ha il WTM(xj) maggiore
- aggiornerà il valore dell'RTM(xi) assegnandogli il valore più grande tra il suo ts e l'RTM della stessa versione
- il WTM(xi) non cambia
- se ho una write(x, ts) dovrò prima di tutto individuare tra tutte le versioni xi con WTM(xj) <= ts, quella che ha il WTM(xj) maggiore. A questo punto dovrò:
- rifiutare se ts < RTM(xi). La transazione andrà riportata tra quelle uccise
- accettare se ts >= RTM(xi). Bisognerà quindi creare una nuova versione xi+1 e assegnarle stessi valori di WTM(xi+1) e RTM(xi+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(x1) = 10 e WTM(x1) = 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(xi) e WTM(xi).
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
| xk
| RTM(xk)
| WTM(xk)
| TRANS.UCCISA
|
|
|
|
| x1
| 10
| 8
|
|
| 1
| read(x,12)
| OK
| x1
| 12
| 8
|
|
| 2
| write(x,12)
| OK
| x2
| 12
| 12
|
|
| 3
| write(x,15)
| OK
| x3
| 15
| 15
|
|
| 4
| write(x,9)
| NO
|
|
|
| t9
|
| 5
| read(x,14)
| OK
| x2
| 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 x1 (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 x1 (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 x1+1 = x2, 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 x1 (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 t9
- 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 x2 (12), quindi la lettura avverrà su esso. Il timestamp è maggiore dell'RTM precedente, quindi lo sostituirà
Torna alla pagina di Basi di Dati - Complementi
