Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Stefano Russo » 12.Transazioni e controllo di concorrenza


Sommario

  • Transazioni e proprietà ACID; Coordinatore delle transazioni
  • Atomicità nei confronti della concorrenza
    • I problemi di lost update e inconsistent read
    • Conflitti ed equivalenza seriale
  • Atomicità nei confronti dei malfunzionamenti
    • I problemi di dirty reads, cascading aborts e premature writes
  • Locks
  • Transazioni composte
  • Deadlock
  • Transazioni distribuite
  • Deadlock distribuito

Transazioni

Una transazione è un insieme di elaborazioni che – pur eseguite in concorrenza con le elaborazioni di altre transazioni in competizione per l’accesso a risorse condivise, ed in un contesto in cui sono possibili malfunzionamenti – costituiscono un’unità di lavoro indivisibile, che gode di opportune proprietà atte a garantirne la correttezza e la persistenza degli effetti.
Tali proprietà sono in letteratura con l’acronimo ACID (Atomicità, Consistenza, Isolamento, Durata) (Härder e Reuter, 1983).

Proprietà ACID

  • Atomicità: una transazione è un’unità di lavoro indivisibile: essa è svolta per intero, oppure intermante annullata; non sono possibili esecuzioni parziali.
  • Consistenza: una transazione che parte da uno stato consistente delle risorse (dati) accedute, deve rilasciare le risorse stesse in uno stato consistente.
  • Isolamento: l’esecuzione di una transizione in concorrenza con altre, con cui compete per l’accesso alle risorse, deve produrre gli stessi effetti di una qualunque esecuzione seriale delle transazioni concorrenti.
  • Durata: gli effetti di una transazione (aggiornamenti dello stato delle risorse) devono essere persistenti.

Tutto o niente, concorrenza e malfunzionamenti

L’atomicità può essere riguardata come la proprietà di indivisibilità o del “tutto o niente” nei riguardi dei malfunzionamenti (failure atomicity).
L’isolamento può essere riguardato come la proprietà di indivisibilità o del “tutto o niente” di una transazione nei riguardi dell’esecuzione concorrente con altre transazioni in competizione sugli stessi oggetti.

Ripristino dello stato degli oggetti

Le proprietà di atomicità e durata richiedono che lo stato degli oggetti condivisi sia ripristinabile in caso di guasti (objects recoverability).

Al momento in cui un server accetta la richiesta di completamento con successo (commit) di una transazione, tutte le modifiche da essa effettuate sugli oggetti devono essere state registrate in memoria non volatile.

In tal modo, in caso di crash improvvisi (ed eventualmente ripetuti) del server per un guasto hardware o per un’anomalia software, sarà prima o poi possibile il ripristino dello stato degli oggetti da parte di un nuovo server.

Coordinatore delle transazioni

Un modo per conferire caratteristiche di transazionalità a un server che gestisce oggetti recoverable è di creare un oggetto coordinatore delle transazioni, che implementi la seguente interfaccia:

  • openTransaction() -> trans;
    • apre una transazione, cui assegna un identificatore univoco (TID). Il TID deve essere usato in tutte le successive operazioni da parte della transazione.
  • closeTransaction(trans) -> (commit, abort);
    • conclude una transazione: restituisce il valore commit in caso di esito positivo, ovvero il valore abort in caso di aborto da parte del server.
  • abortTransaction(trans);
    • abortisce una transazione da parte del client.

Coordinatore delle transazioni

La transazionalità si ottiene grazie alla cooperazione tra il client, gli oggetti condivisi (e recoverable), ed il coordinatore.
Il client deve racchiudere tutte le operazioni sugli oggetti recoverable condivisi tra una coppia di operazioni sul coordinatore
openTransaction() / closeTransaction(),

oppure

openTransaction() / abortTransaction().


Azioni in caso di fallimenti

Azioni lato server in caso di crash:

  • del server: il server viene prima o poi sostituito; il nuovo server:
    • invalida ed abortisce tutte le transazioni uncommitted;
    • esegue il ripristino dello stato di tutti gli oggetti condivisi ai valori finali delle più recenti transazioni committed;
    • restituisce un’eccezione a tutte le successive operazioni da parte di transazioni invalidate.
  • del client: tipicamente il server assegna un tempo massimo (expiry date) a ogni transazione, ed abortisce una transazione che per effetto di un fallimento del client non viene completata entro il tempo massimo.

Azioni lato client in caso di crash del server:

  • le operazioni invocate sul server hanno una scadenza (timeout), dopo la quale restituiscono un’eccezione; l’applicazione deve essere programmata per decidere di conseguenza.

Equivalenza seriale

Se due o più transazioni producono effetti “corretti” quando sono eseguite in isolamento (nel senso che rispettano la proprietà di consistenza), una loro qualsiasi esecuzione seriale (in cui cioè le transazioni sono eseguite una dopo l’altra, senza che singolarmente siano interrotte) è anch’essa corretta.
Si ha dunque che condizione sufficiente affinché una esecuzione concorrente di tali transazioni sia anch’essa corretta (pur se esse competono per l’accesso ad alcuni oggetti condivisi), è che essa sia equivalente ad una loro qualsiasi esecuzione seriale, cioè produca gli stessi effetti di una esecuzione sequenziale delle transazioni in un qualsiasi ordine.
Naturalmente le possibili esecuzioni sequenziali di un insieme di transazioni non producono tutte gli stessi effetti, in generale.

Il problema degli aggiornamenti persi

I valori iniziali dei conti sono: A=100, B=200, C=300.
T: incrementa il conto B del 10%, prelevando l’importo dal conto A.
U: incrementa il conto B del 10%, prelevando l’importo dal conto C.

L’effetto finale su B dovrebbe essere: B=242 (indipendentemente dall’ordine relativo di T e U).


Il problema degli aggiornamenti persi

In figura è mostrata una possibile esecuzione concorrente di T1 e T2.

L’effetto finale su Y in tale esecuzione concorrente è Y=22.
Il problema è che Y è una risorsa condivisa, e T1 non si accorge degli aggiornamenti di T2, ed aggiorna Y annullando le modifiche di T2.


Il problema degli aggiornamenti persi

Il problema degli aggiornamenti persi (lost update) può presentarsi quando due transazioni leggono il valore di una variabile e successivamente lo usano per calcolarne un nuovo valore.

Il problema dunque non può presentarsi se una transazione è eseguita – per quanto concerne gli accessi alla variabile condivisa – prima dell’altra, perché in tal caso la seconda leggerebbe il valore finale della prima.

Il problema degli aggiornamenti persi

Una esecuzione concorrente ma serialmente equivalente di T1 e T2. T1 esegue tutte le sue operazioni sulla risorsa condivisa B prima di T2

Una esecuzione concorrente ma serialmente equivalente di T1 e T2. T1 esegue tutte le sue operazioni sulla risorsa condivisa B prima di T2


Il problema delle letture inconsistenti

I valori iniziali dei conti sono: X=10, Y=10.
T1: trasferisce un importo da X a Y.
T2: calcola la somma dei saldi di tutti i conti della filiale.
Il totale (parziale) di T2 è inconsistente in quanto T1 ha effettuato solo il prelievo da X quando T2 legge i saldi sia di X sia di Y.


Il problema delle letture inconsistenti

Il problema può presentarsi quando le transazioni in sola lettura operano concorrentemente con quelle in modifica.

Non può presentarsi se tutte le letture sono eseguite prima o dopo gli aggiornamenti.

In figura è mostrata una esecuzione serialmente equivalente di V e W.


Conflitti tra operazioni

Due operazioni si dicono confliggenti se il loro effetto combinato dipende dall’ordine relativo secondo cui esse sono eseguite.

Regole di conflitto per le operazioni di lettura e scrittura

Regole di conflitto per le operazioni di lettura e scrittura


Conflitti ed equivalenza seriale

Affinché una esecuzione concorrente di due transazioni sia equivalente a una qualsiasi loro esecuzione seriale è necessario e sufficiente che tutte le coppie di operazioni in conflitto delle due transazioni siano eseguite nello stesso ordine per tutti gli oggetti da esse condivisi.
L’equivalenza seriale è utile come criterio per la definizione di protocolli di controllo di concorrenza.
Tre tecniche classiche di controllo di concorrenza sono:

  • uso di lock;
  • controllo di concorrenza ottimistico;
  • uso di marcature temporali (timestamp ordering).

Conflitti ed equivalenza seriale

Esempio: i, j: risorse condivise

Transazione T1: A=leggi(X); write(X,5); write(Y,6);

Transazione T2: B=read(Y); write(Y,7); C=read(X);

In figura è mostrata una possibile esecuzione concorrente.

T1 effettua tutti gli accessi a X prima di T2.

T2 effettua tutti gli accessi a Y prima di T1.


Conflitti ed equivalenza seriale

L’esecuzione non è equivalente a una esecuzione seriale di T1 e T2, perché l’ordine delle operazioni confliggenti non è lo stesso per tutti gli oggetti.

L’equivalenza seriale richiede in questo caso che:

  • T1 effettui tutti gli accessi a X prima di T2 tutti gli accessi a Y prima di T2,oppure che:
  • T2 effettui tutti gli accessi a Y prima di T1 e tutti gli accessi a X prima di T1.

Annullabilità degli effetti in caso di aborti

Un server deve rendere permanenti gli effetti delle transazioni che eseguono il commit ed annullare quelli delle transazioni che abortiscono.

Occorre però anche garantire che l’aborto di una transazione non abbia effetti collaterali negativi su altre transazioni concorrenti.
Alcuni problemi che possono verificarsi a seguito di aborti sono:

  • il problema delle letture spurie (dirty reads);
  • il problema degli aborti a cascata (cascading aborts);
  • il problema delle scritture premature (premature writes).

Il problema delle letture spurie

La proprietà di isolamento richiede che le transazioni non vedano gli stati non committed delle altre transazioni.

In figura è mostrato l’esempio, Valori iniziali: X=1, A=2, B=3

T1 abortisce, e T2 – che dopo il commit non può più essere abortita – ha letto un valore mai esistito per l’oggetto X (dirty read).


Il problema delle letture spurie

Per evitare il problema delle letture spurie, occorre evitare che una transazione (come T2, nell’esempio) effettui il commit dopo aver visto gli effetti di un’altra transazione (T1) che non è stata ancora completata, e che può quindi ancora essere abortita (dal client o dal server).

Per prevenire letture spurie occorre ritardare il commit di una transazione, eseguendolo dopo il commit di tutte le altre transazioni in modifica delle quali sono stati osservati stati intermedi.

Se una di tali transazioni (come T1) abortisce, anche la transazione “sospesa” (come T2) deve essere abortita.

Il problema degli aborti a cascata

In una situazione come quella delle letture spurie, l’aborto di una transazione (come T1, nell’esempio) causa l’aborto di un’altra transazione (T2); ciò potrebbe determinare l’aborto di altre transazioni (che a loro volta hanno visto stati intermedi di T2), causando un effetto domino.

Per prevenire aborti a cascata, ogni operazione di lettura (read) su un oggetto x deve essere rinviata a dopo il completamento (commit o abort) di tutte le transazioni che hanno effettuato scritture (write) sullo stesso oggetto x.

Questa condizione è più stringente di quella necessaria per prevenire le letture spurie.

Il problema delle scritture premature

Si tratta di un problema connesso ad aborti in caso di scritture concorrenti sullo stesso oggetto da parte di due o più transazioni.

In figura è mostrato l’esempio: inizialmente X=1.
La serializzabilità è soddisfatta (le transazioni consistono di una sola operazione). Se T1 fa il commit e T2 abortisce, lo stato finale dovrebbe essere X=3. Nel caso duale, dovrebbe aversi X=5.

Il problema nasce dal fatto che tipicamente il ripristino in caso di aborto viene realizzato facendo ricorso ai valori precedenti a tutte le operazioni write della transazione (before images).


Il problema delle scritture premature

Il valore before image di T1 è X0=1, per T2 è X=3.

Perciò se T esegue commit e T2 abortisce, il ripristino si avrà al valore before image di T2: X=5 (corretto, coincide con l’after image di T1).

Se T2 esegue commit e poi T abortisce, il ripristino si avrà al valore before image di T1: X=1 (non corretto, perché annulla il commit di T2 a 5).

Se entrambe abortiscono – nell’ordine T1, poi T2 – , il ripristino si avrà al valore finale X=3 (before image di T2, abortita per ultima), valore chiaramente non corretto (annullando tutti gli effetti si dovrebbe ritornare al valore iniziale X=1).

Le tecniche di ripristino che fanno uso dei valori before image devono dunque rinviare le operazioni write a dopo il completamento (commit o abort) delle transazioni “precedenti” che hanno aggiornato gli stessi oggetti.

Esecuzione stretta

Riepilogando:

  • per evitare dirty reads e cascading aborts, le letture devono essere posticipate a dopo il completamento delle transazioni concorrenti in scrittura sugli stessi oggetti;
  • per evitare gli effetti di premature writes, le scritture devono essere posticipate a dopo il completamento delle transazioni “precedenti” in scrittura sugli stessi oggetti.

Si parla di esecuzione stretta se il server ritarda qualunque operazione (lettura o scrittura) su un oggetto x finché tutte le transazioni che hanno in precedenza modificato x sono completate.

L’esecuzione stretta rispetta la proprietà di isolamento delle transazioni.

I materiali di supporto della lezione

G. Coulouris et al.: Distributed Systems: Concepts and Design (Cap. XIII §1-5), IV ed., 2005.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion