Realizzazione di azioni atomiche mediante acquisizione e rilascio degli oggetti condivisi (locks)
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:
Tre tecniche classiche di controllo di concorrenza sono:
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.
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).
I requisiti per l’equivalenza seriale degli accessi all’oggetto x sono:
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:
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:
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).
Una transazione deve però essere atomica non solo nei confronti della concorrenza, ma anche dei malfunzionamenti. Per garantire ciò occorre l’ulteriore requisito:
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).
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:
Considerati possibili conflitti tra operazioni, si ha lo schema di compatibilità dei lock in figura.
Allo scopo di aumentare il livello di concorrenza tra le transazioni, è possibile adottare uno schema di locking ottimistico detto two-version locking, in cui l’acquisizione di lock esclusivi è rinviata alla fase di commit.
Lo schema prevede tre tipi di lock, con le compatibilità riportate in figura:
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.
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.
Blocco critico
(deadlock)
L’uso dei lock può condurre a situazioni di blocco critico o stallo (deadlock) di due o più transazioni.
Un deadlock è uno stato in cui ogni membro di un gruppo di transazioni è in attesa che altri membri rilascino degli oggetti, per i quali hanno acquisito i relativi lock.
Le dipendenze d’attesa tra le transazioni possono essere rappresentate in un grafo bipartito, in cui i nodi rappresentano transazioni o oggetti, gli archi relazioni di possesso o attesa.
Poiché ogni transazione può essere in attesa di un solo oggetto in un dato istante, è possibile rimuovere gli oggetti dal grafo (fig.1).
Il grafo di attesa (wait-for graph) rappresenta le dipendenze d’attesa tra le transazioni: i nodi rappresentano transazioni e gli archi orientati relazioni di attesa (fig.2).
Una condizione per il verificarsi di un deadlock è la presenza di cicli nelle dipendenze tra le transazioni, rilevabile esaminando il grafo di attesa.
Es. in figura: T, U, V condividono un read lock su C; W detiene un write lock su B; V richiede B; T e W richiedono un write lock su C.
L’esempio mostra che, sebbene possa attendere un solo oggetto alla volta, una transazione può essere coinvolta in più cicli.
Esistono diverse tecniche per affrontare il problema dei deadlock:
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.
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.
Il problema grave di questa tecnica è che può capitare di abortire transazioni senza che vi sia effettivamente un deadlock.
La scelta della durata del timeout è critica.
Esempio in figura.
Transazioni composte e
regole di locking
In alcune applicazioni (p.es., per transazioni di lunga durata, o come strumento di modularità) è utile far sì che le transazioni possano essere composte di altre (sotto)transazioni (nested transactions).
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:
Le regole di completamento di transazioni composte sono:
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.
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:
A tale scopo si fa uso di un meccanismo di ereditarietà dei lock.
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.
Il secondo requisito è soddisfatto con le seguenti regole:
L’acquisizione ed il rilascio di lock in caso di nested transactions avvengono con le seguenti regole:
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.
1. Caratterizzazione dei sistemi distribuiti
2. Modelli di sistemi distribuiti
3. Tempo e sincronizzazione nei Sistemi Distribuiti
4. Stato globale nei Sistemi Distribuiti
5. Problemi di consenso nei sistemi distribuiti
7. Algoritmi di mutua esclusione nei sistemi distribuiti
8. Algoritmi di elezione nei sistemi distribuiti
10. Il Network File System di SUN Microsystems
11. AFS (Andrew File System) e GFS (Google File System)
12. Transazioni e controllo di concorrenza
13. Transazioni
15. Affidabilità (dependability) dei sistemi software distribuiti
16. Affidabilità dei sistemi software distribuiti
17. Software Faults
18. Classificazione e analisi dei difetti software