Stefano Russo » 13.Transazioni

Transazioni

Realizzazione di azioni atomiche mediante acquisizione e rilascio degli oggetti condivisi (locks)

Tecniche di controllo di concorrenza

L’equivalenza seriale è utile come criterio per la definizione di protocolli di controllo di concorrenza.
Gli approcci al controllo di concorrenza possono essere classificati in:

• approcci ottimistici: si basano sull’assunzione che di norma tutto vada bene, e non si presentino conflitti; la sincronizzazione avviene alla fine di una transazione, e nel caso ci siano stati conflitti una o più transazioni sono abortite
• approcci pessimistici: si basano sulla legge di Murphy; tutte le operazioni sono sincronizzate prima di essere espletate, in modo che i conflitti siano risolti prima delle effettive operazioni.

Tecniche di controllo di concorrenza

Tre tecniche classiche di controllo di concorrenza sono:

1. uso di lock;
2. controllo di concorrenza ottimistico;
3. uso di marcature temporali (timestamp ordering).

In generale, i principi possibili sono: 1) far attendere le transazioni in caso di conflitti; 2) rilevare ex post eventuali conflitti, e nel caso ri-eseguire le transazioni; 3) usare un approccio ibrido tra i due.
La tecnica più diffusa nei sistemi reali è quella dei lock, che può dar luogo a situazioni di stallo (deadlock), che a loro volta richiedono opportune tecniche di prevenzione o gestione.

Locks

Le operazioni di due o più transazioni concorrenti devono essere schedulate in modo che i loro effetti sugli oggetti condivisi siano serialmente equivalenti.

Una modalità con cui un server può realizzare ciò è di serializzare gli accessi agli oggetti, mediante un opportuno protocollo di richiesta e rilascio degli oggetti stessi (locking/unlocking). Il protocollo è implementato dal server a fronte delle richieste di accesso agli oggetti da parte delle transazioni.

Lo schema di locking più semplice fa uso di accessi esclusivi agli oggetti (exclusive locks): la richiesta da parte di un client di accesso a un oggetto già in possesso di un altro cliente viene sospesa, ed il client messo in attesa fino al rilascio dell’oggetto.
Le operazioni di richiesta di uso esclusivo e di rilascio di un oggetto x sono dette rispettivamente lock(x) e unlock(x).

Lock esclusivi

I requisiti per l’equivalenza seriale degli accessi all’oggetto x sono:

• R1: ogni oggetto deve essere acquisito in modo esclusivo prima di qualunque operazione su di esso; ciò si ottiene effettuando l’operazione lock(x) prima del primo accesso, che deve essere bloccante se l’oggetto non è disponibile; tale requisito è chiaramente necessario in quanto in caso contrario non sarebbe garantita neppure la consistenza dei singoli oggetti;
• R2: nessun oggetto deve essere rilasciato prima che siano eseguite tutte le operazioni su di esso; ciò si ottiene effettuando l’operazione unlock(x) solo dopo l’ultimo accesso a x; tale requisito è necessario in quanto l’oggetto x non deve essere accessibile ad altre azioni atomiche finché è ancora in uno stato intermedio inconsistente.

Lock esclusivi

Poiché la proprietà di consistenza di una transazione non riguarda i singoli oggetti, ma il loro insieme, tutte le coppie di operazioni in conflitto di due transazioni devono essere eseguite nello stesso ordine per tutti gli oggetti da esse condivisi. Ciò può essere garantito con il requisito:

• R3: nessun oggetto può essere richiesto dopo che sia stato eseguito il rilascio di un altro oggetto; ciò si ottiene effettuando l’operazione unlock(x) solo dopo l’ultimo accesso; tale requisito assicura che quando una transazione rilascia un oggetto contenente il valore finale, nessuno degli altri oggetti su cui essa opera è libero e non contenente il valore finale.

Two-phase exclusive locking

Il protocollo di richieste e rilasci degli oggetti che rispetta i requisiti R1-R3 va sotto il nome di protocollo di acquisizione rilascio a due fasi (two-phase lock protocol).
Il nome deriva dal fatto che la transazione può essere concettualmente suddivisa in due fasi per quanto concerne l’acquisizione esclusiva degli oggetti:

1. fase crescente: l’azione atomica acquisisce gli oggetti in maniera esclusiva ed opera su di essi.
2. fase calante: inizia al primo rilascio e durante tale fase non è possibile effettuare ulteriori acquisizioni di oggetti.

Se ogni azione atomica segue il protocollo di two-phase lock non possono nascere inconsistenze a causa della concorrenza tra le azioni atomiche (Eswaran 1976).

Strict two-phase exclusive locking

Una transazione deve però essere atomica non solo nei confronti della concorrenza, ma anche dei malfunzionamenti. Per garantire ciò occorre l’ulteriore requisito:

• R4: nessun oggetto può essere rilasciato prima che la transazione abbia completato la sua esecuzione; i rilasci devono costituire le ultime operazioni di una transazione.

Il requisito R4 garantisce l’assenza di inconvenienti quali le letture sporche, l’effetto domino e le scritture premature: esso garantisce l’atomicità nei confronti dei malfunzionamenti.

Un protocollo di lock a due fasi che rispetta anche il requisito R4 viene detto protocollo di lock esclusivo a due fasi in senso stretto (strict two-phase locking).

Lock non esclusivi

L’uso di lock esclusivi riduce la concorrenza tra le transazioni più di quanto sia necessario in molte applicazioni pratiche, che prevedono in generale operazioni sia di lettura sia di scrittura sugli oggetti condivisi.
È possibile aumentare la concorrenza adottando uno schema di locking che consenta l’accesso concorrente di più transazioni in sola lettura, e di una sola transazione alla volta in fase di scrittura, ma non consenta la concorrenza di operazioni di lettura e scrittura.
Si distinguono due tipi di lock:

• lock per operazioni di sola lettura (read lock o shared lock);
• lock per operazioni di scrittura (write lock o exclusive lock).

Strict two-phase locking con lock non esclusivi

1. When an operation accesses an object within a transaction:
   • (a) If the object is not already locked, it is locked and the operation proceeds.
   • (b) If the object has a conflicting lock set by another transaction, the transaction must wait until it is unlocked.
   • (c) If the object has a non-conflicting lock set by another transaction, the lock is shared and the operation proceeds.
   • (d) If the object has already been locked in the same transaction, the lock will be promoted if necessary and the operation proceeds. (Where promotion is prevented by a conflicting lock, rule (b) is used.)
2. When a transaction is committed or aborted, the server unlocks all objects it locked for the transaction.

Two-version locking

La richiesta di un read lock è posta in attesa solo se sull’oggetto è presente un commit lock.

La richiesta di un write lock è posta in attesa se sull’oggetto è presente un altro write lock, oppure un commit lock.
Il commit lock è richiesto dal coordinatore delle transazioni quando riceve il commit da parte di una transazione.
In tal caso il coordinatore tenta di convertirne tutti i write lock in commit lock: se su qualche oggetto esistono già dei read lock, la transazione deve attendere il loro rilascio.

Two-version locking

Rispetto allo schema base di read-write locking, il two-version locking presenta il vantaggio di non ritardare le operazioni di lettura durante l’esecuzione di altre transazioni concorrenti, ponendole in attesa solo se queste ultime sono in fase di commit.
Tale schema è dunque vantaggioso se mediamente la fase di commit dura un tempo trascurabile rispetto all’esecuzione di un’intera transazione.

Transazioni

Blocco critico

(deadlock)

Deadlock prevention

Esistono diverse tecniche per affrontare il problema dei deadlock:

• deadlock prevention
• deadlock detection and resolution

Una tecnica di prevenzione consiste nel “lockare” tutti gli oggetti richiesti in un’unica operazione atomica all’inizio della transazione.

Tale tecnica non può però essere applicata in molte applicazioni interattive, in cui non si conoscono a priori gli oggetti richiesti.
In ogni caso, la tecnica riduce sensibilmente gli accessi concorrenti.

Alternativamente, si può imporre un ordine predefinito di lock, ma anche questa tecnica riduce la concorrenza perché anticipa i lock.

Deadlock detection e resolution

La presenza di deadlock può essere verificata ogni volta che si aggiunge un ramo al grafo, oppure periodicamente.

Quando si rileva un deadlock, si sceglie una transazione da abortire.
La scelta non è semplice: due possibili criteri sono l’età della transazione e il numero di cicli in cui è coinvolta.

Una tecnica di risoluzione dei deadlock molto usata si basa sull’uso di timeouts.
Allo scadere di un apposito timeout, un lock diventa vulnerabile. Se non ci sono altre richieste per l’oggetto, esso resta locked.
Se altre transazioni effettuano richieste di lock per l’oggetto, il lock vulnerabile è infranto e la relativa transazione è abortita.

Transazioni

Transazioni composte e

regole di locking

Transazioni composte

Una sottotransazione deve apparire atomica alla transazione di livello superiore, sia dal punto di vista della concorrenza sia della tolleranza ai guasti.
Le transazioni composte presentano i seguenti vantaggi:

• Due sottotransazioni dello stesso livello possono essere concorrenti, e devono avere un’esecuzione serialmente equivalente, p. es. mediante locks.
  • Ciò può dar luogo ad un maggior livello di concorrenza.
• Una sottotransazione può essere completata con successo, ovvero abortire, indipendentemente dalle altre di qualsiasi livello.
  • Ciò può dar luogo ad un maggior livello di robustezza.

Regole per le transazioni composte

Le regole di completamento di transazioni composte sono:

• Una transazione può eseguire commit o abortire solo dopo il completamento delle sue sottotransazioni.
• Al completamento, una sottotransazione può prendere autonomamente la decisione:
  • di abortire, ovvero:
  • di completare provvisoriamente con successo.
• La decisione di abortire da parte di una sottotransazione è definitiva e irrevocabile.
• Se una transazione abortisce, tutte le sue sottotransazioni devono essere abortite (anche nel caso in cui abbiano eseguito provvisoriamente il commit).

Regole per le transazioni composte

• Se una sottotransazione abortisce, la sua transazione “madre” può decidere sia di abortire sia di completare.
• Se la transazione di più alto livello decide di completare con successo, tutte le sottotransazioni provvisoriamente completate con successo e che non discendano da una sottotransazione che ha abortito devono completare con successo.

NB: Gli effetti di una sottotransazione in caso di completamento con successo non sono permanenti fino al completamento con successo della transazione radice dell’albero.

Regole di locking per le transazioni composte

In caso di transazioni composte, l’obiettivo di uno schema di locking è di serializzare gli accessi agli oggetti in modo da rispettare i seguenti requisiti:

• ogni insieme (albero) di transazioni composte è un’unica entità che non deve vedere gli effetti parziali di ogni altro insieme concorrente;
• ogni transazione di un insieme non deve vedere gli effetti parziali delle altre transazioni nello stesso albero.

A tale scopo si fa uso di un meccanismo di ereditarietà dei lock.

Regole di locking per le transazioni composte

Il primo requisito è soddisfatto se un lock acquisito da una sottotransazione viene ereditato, al suo completamento, dalla transazione madre.

I lock ereditati sono trasmessi agli ulteriori antenati, e prima o poi la transazione di più alto livello acquisisce tutti i lock.

Si noti che l’eredità viene lasciata dai figli ai genitori.

Con tale meccanismo di ereditarietà dei lock si garantisce che gli oggetti siano acceduti solo quando servono (dalle sottotransazioni), e siano rilasciati solo al completamente della transazione radice, impedendo che altri alberi di transazioni ne vedano effetti parziali.

Regole di locking per le transazioni composte

Il secondo requisito è soddisfatto con le seguenti regole:

• una (sotto)transazione non può accedere a oggetti condivisi in concorrenza con le sue sottotransazioni. Se una transazione ha un lock su un oggetto, lo mantiene, ma esso viene acquisito temporaneamente dalle sue sottotransazioni;
• poiché due sottotransazioni di pari livello sono concorrenti, lo schema di locking deve serializzare i loro accessi agli stessi oggetti.

Acquisizione e rilascio di lock per le transazioni composte

L’acquisizione ed il rilascio di lock in caso di nested transactions avvengono con le seguenti regole:

• affinché una sottotransazione possa acquisire un read lock su un oggetto, nessun’altra transazione attiva deve possedere un write lock sullo stesso oggetto, e le sole transazioni che eventualmente possiedono un write lock sono suoi antenati;
• affinché una sottotransazione possa acquisire un write lock su un oggetto, nessun’altra transazione attiva deve possedere un qualsiasi lock (read o write) sullo stesso oggetto, e le sole transazioni che possiedono un lock sono suoi antenati;

Acquisizione e rilascio di lock per le transazioni composte

• se una sottotransazione completa termporaneamente con successo, i suoi lock sono ereditati dal genitore con gli stessi privilegi (read o write);
• se una sottotransazione completa con aborto, i suoi lock sono rilasciati; se il genitore possiede lock per gli stessi oggetti, li mantiene inalterati.

NB: poiché una sottotransazione acquisisce temporaneamente i lock di un genitore, sottotransazioni di pari livello che operano sugli stessi oggetti di un genitore acquisiscono a turno tali lock.