La mutua esclusione regola l'accesso concorrente ad una risorsa. Quando un processo ha bisogno di accedere piu' risorse in modo esclusivo, nascono problemi dovuti ad una possibile inconsistenza e/o possibile perdita di dati.

Esempio 1: Race condition

Esempio 2: Perdita di dati a causa di crash

Il C/C A contiene 50M
Il C/C B contiene 19M
Esecuzione:
Leggo dal C/C A
Sottraggo 1M
Scrivo sul C/C A (49M)
Leggo dal C/C B
Sommo 1M sul C/C B
                                    <------------Crash
Scrivo C/C B (11M)

Risultato:  il C/C A contiene 49M, il C/C B contiene 10M

Esempio 3: Possibili serializzazioni di esecuzioni concorrenti

Crediti iniziali
C/C A   credito di 20M
C/C B   credito di 10M
C/C C   credito di 5M

Processo T1
begin
1    read   credito A
2    read   credito B
3    write  credito A-10M su C/C a
4    write  credito B+10M su C/C B
end
Processo T2
begin
1    read   credito B
2    read   credito C
3    write  credito B-5M su C/C B
 4    write  credito C+5M su C/C C
end

Risultato corretto:  C/C A = 10M, C/C B = 15M, C/C C = 10M

Esempio di sequenza corretta:
T1.1, T2.1, T2.2, T2.3, T1.2, T1.3, T1.4, T2.4

Esempio di sequnza non corretta:
T1.1, T2.1, T2.2, T1.2, T2.3, T1.3, T1.4, T2.4
 

• Comunicaizoni reliable (controllo degli errori ai vari livelli di protocollo)
• Sicurezza di non perdere dati durante l'elaborazione,
• Modello di Transazione per gestione della concorrenza e atomicita' dell'accesso ai dati.

• RAM  memoria volatile
• Disco  puo' sopravvivere a mancanza di tensione o crash di CPU
• Stable Storage  sopravvive anche ad un limitato numero di disk crash

• livello hardware: un blocco disco puo' perdere il valore di 1 bit ==> e' rilevabile attraverso l'uso di checksum (es. XOR)
• primo livello software: careful-write. Dopo ogni write si fa un'operazione read. Se il valore che avrebbe dovuto essere scritto non corrisponde con quello letto, si ripete alcune volta l'operazione. Se si continua ad avere fallimenti, si segna "bad" il blocco
• secondo livello software: stable storage. Uno stable storage block corrisponde ad una coppia ordinata di "careful block" (possibilmente su driver diversi). Si garantisce che almeno 1 dei due blocchi e' corretto.

• se uno e' "good" e l'altro e' "bad", quest'ultimo e' rimpiazzato con un altro "good" su cui e' ricopiata l'informazione memorizzata sull'unico elemento "good" della coppia.
• effettua il controllo sui checksum.

Transazione

• Serializzabilita': le transazioni eseguite concorrentemente non devono interferire in modo scorretto.
• Atomicita': la transazione appare all'esterno come un'operazione indivisibile.
• Permanenza: quando la transazione termina (commit) le modifiche sono permanenti.

2. Atomicita'
Le transazioni sono chiamate anche talvolta azioni atomiche.
L'azione atomica e' una astrazione che ha avuto diverse definizioni diverse, ad esempio:

• un'azione e' atomica se il processo (processi) che la effettua non comunica con altri processi durante l'esecuzione dell'azione (per comunicazione si intende la possibilita' di conoscere, in qualsiasi modo, qualche informazione sull'evoluzione di un processo).
• ... se puo' essere considerata indivisibile ed istantanea, senza stati intermedi visibili.

3. Permanenza
Dopo che una transazione ha effettuato un commit, i risultati devono essere visibili e permanenti. In un nesting di transazioni ognuna e' committed "relativamente al suo parent".

Sono 2 i punti da considerare:

1. possibilita' di ritornare nella situazione iniziale della transazione.
2. esecuzione atomica anche del commit finale, che riassume i criteri dell'istantaneita' e indivisibilita' dell'azione atomica: prima del commit non e' ancora "successo" niente, poi ogni modifica e' visibile e permanente. Anche il commit non deve risentire di failure.

A. private work space
Ogni transazione ha il suo private workspace in cui ricopia tutti i file e i dati che modifichera'. Lo stesso avviene per eventuali nested transaction. E' un metodo molto costoso.

B.Utilizzo di shadow block dei file
Solo i blocchi di file modificati o aggiunti sono ricopiati. Nel private workspace viene mantenuto solo l'indice (modificato) dei blocchi dei file. Gli altri processi vedono quindi sempre i blocchi originali dei file, finche' un processo non effettua il commit di una transazione. In questo caso l'indice del private work space viene ricopiato in modo atomico su quello originale.
Questo sistema deve essere accoppiato con un sistema di lock o di controllo ottimistico per escludere situazione di inconsistenza dovuto all'accesso concorrente in scrittura da parte di piu' processi in diverse transazioni.

C. Utilizzo di writeahead log.
I blocchi del file vengono effettivamente scritti, ma e' mantenuta una traccia delle modifiche sotto forma di coppia vecchio-valore / nuovo-valore. Se la transazione effettua un commit, il log e' cancellato. Se abortisce, le modifiche apportate sono recuperate (roll-back).

I file non sono le uniche risorse richiedibili in una transazione. >si possono anche richiedere dei servizi al sistema. In questo caso le risorse sono dei server. Se un servizio cambia stato in conseguenza della transazione, occorre fare una copia anche del server (ad es. in un servizio di file system distribuito, puo' rimanere l'impostazione della working directory). E' necessario allora fare una copia dello stato del server.

2. Two phase commit protocol
Se una transazione abortisce (volontariamente, o per failure di un componente) bisogna riportare il sistema alla situazione precedente, con un'operazione undo.
Occorre quindi memorizzare (su un file log) le operazioni che sono state fatte e le risorse che sono state accedute (per farne poi il roll-back).

Le operazioni possibili sulla transazione sono:
DO esegue làazione e scrive il log
UNDO recupera (torna indietro) le operazioni scritte sul log
REDO riesegue le operazioni scritte sul log.

Il two phase commit protocol consente di effettuare il commitment finale se non si verifica un failure. In caso di failure invece e' possibile riparare il guasto (ad esempio rilanciare un processo che si e' interrotto, riconoscere la precedente esecuzione, riportare lo stato del sistema nella posizione corretta....)

Non fatto

Abbiamo visto prima l'implementazione dell'atomicita' come possibilita' di effettuare un UNDO della transazione, e come esecuzione del "tutto o niente" dell'operazione finale di commit.
L'atomicita' deve pero' essere estesa a tutta la transazione, cioe' non deve essere visibile dall'esterno nessun suo stato intermedio.  Inoltre bisogna coordinare l'accesso alle risorse in modo da evitare (o rompere) il deadlock. Il meccanismo che consente il completamento dell'atomicita' consente anche di ottenere uno schedule consistente, e si chiama

1. Locking

E' il sistema piu' semplice: ogni oggetto ha un solo lock, ottenibile da una sola transazione alla volta. se una transazione cerca di fare un lock su un oggetto gia' bloccato, puo' aspettare, abortire o interrompere (e causarne il roll-back) l'altra transazione, per evitare di finire in deadlock.
Una transazione e' ben formata se:

• blocca un oggetto prima di accederlo
• non blocca oggetti gia' bloccati

2PL: 2 Phase Lock

Transazione T1
begin
   lock  conto A
   read  credito A
   lock  conto B
   read  credito B
   write credito A-10M su conto A
   unlock conto A
   write  credito B+10M su conto B
   unlock conto B
end

Nell'esempio fatto e' possibile un deadlock.
Si utilizzano in genere tecniche di deadlock detection, con interruzione e recovery delle transazioni, associato con time-out.
I metodi di avoidance sono poco utili perche' non consentono la dinamicita', soprattutto in ambiente distribuito.

Si puo' dimostrare che sae tutte le transazioni usano il 2PL, allora tutti gli schedule ottenibili sono serializzabili.

Ci possono essere ancora dei problemi di atomicita' in caso di failure (vedi dopo, effetto domino). In questo caso si puo' imporre che tutti i lock siano rilasciati solo dopo la fase di commit.

In ogni caso, se una risorsa fosse acquisita e poi rilasciata prima del commit, si violerebbe comunque il concetto di atomicita', rendendo visibile uno stato intermedio prima del commit finale.

I protocolli Two Phase Lock prevedono che le risorse siano rilasciate dopo averle tutte acquisite, e non ne siano piu' prese altre. Normalmente il rilascio viene effettuato come atto di terminazione. In questo modo si preserva l'atomicita' dell'azione e si impedisce l'effetto domino.

L'atomicita' perche' la stessa variabile non puo' essere acquisita piu' di una volta, rendendo cosi' visibile una zsua situazione intermedia:

L'effetto domino si ha quando una transazione fallisce, effettua il roll-back e trascina eventualmente con se' altre transazioni a causa dle recovery che effettua sulle risorse (se il commitment fosse fatto dopo aver rilasciato gia' delle risorse).

Nel caso precedente, l'effetto domino non e' neacnche il caso peggiore. Infatti se T2 fosse gia' stata committed al momento del failure di T1, ci si troverebbe in una situazione d'errore.

2. Metodo ottimistico

In questo caso  ogni transazione lavora su di una copia delle risorse (ad esempio utilizzando il metodo di shadow block). Al momento del commit si verifica se nel frattempo ci sono o ci sono state altre transazioni che hanno utilizzato le stesse risorse, in modo tale da rendere l'esecuzione corrente non consistente. In questo caso o si abortisce la transazione, o si causa l'abort di altre transazioni in corso. Per evitare starvation si utilizza il metodo del time stamp (identificatore unico, attribuito in modo da ottenere un ordinamento assoluto fra le transazioni) per selezionare la transazione che puo' sopravvivere.

Durante il lock delle risorse (nel caso di algoritmi di locking) e' ovviamente possibile il deadlock. In ambiente distribuito e soprattutto quando gli oggetti accessibili sono numerosi (tipo blocchi di file) e variano rapidamente con il tempo, abbiamo visto che i metodi di deadlock avoidance e prevention sono poco pratici. Il metodo di deadlock detection e recovery e' complicato dal fatto che occorre mantenere un allocation graph distribuito (problemi di sincronizzazione). Si utilizza in genere un metodo misto, di prevention-detection, basato sui time stamp.

Un time stamp e' un numero unico assegnato ad una transazione (ad esempio da un gestore centralizzato, oppure utilizzando un meccanismo distribuito di clock logico) in modo monototono crescente.
Nell'esecuzione delle transazioni si da' la priorita' alle transazioni che hanno il time stamp minore, in modo da garantire l'assenza di starvation. Infatti, una volta assegnato un time stamp ad una transazione (che rimane lo stesso anche se la transazione abortisce e poi ricomincia), solo un numero finito di altre transazioni hanno la priorita' su di essa.
Si puo' utilizzare il time stamp nei sistema con lock per evitare il deadlock, e nei sistemi ottimistici per effettuare il commit di una transazione piuttosto che di un'altra.
Vediamo il primo casa.

In congiunzione con i lock
Ogni risorsa e' controllata da un gestore (processo) che si trova sullo stesso host su cui e' collocata la risorsa. Un gestore riceve le richieste da uno dei processi coinvolti in una transazioni, e memerizza lo stato della risorsa.
Quando una risorsa e' gia' assegnata ad una transazione Tj (con time stamp TSj) e il gestore riceve una richiesta da parte di un'altra transazione Ti con time stamp TSi, puo' effettuare una delle seguenti azioni:

• Wait: fare aspettare Ti finche' la risorsa non e' libera. Questa scelta potrebbe portare al deadlock.
• Abort-Restart: abortire e riavviare una delle due transazioni: quella che detiene la risorsa o quella che la richiede. Questa scelta potrebbe portare alla starvation. L'operazione abort-restart e' effettuato usando una delle due primitive:
• Die: restart della transazione richiedente (Die(Ti))
• Wound: la transazione che detiene la risorsa e' segnalata al sistema come "ferita" e si manda un messaggio a tutti i siti visitati dalla transazione ferita: se e' in fase di terminazione (shrinking phase: ha gia' acquisito tutti i lock) la si lascia terminare, altrimenti si effettua un abort-rester (die). Nell'esempio fatto prima, verrebbe eseguito Wound(Tj).

1. Wait-Die
• se TSi < TSj (Ti e' piu' vecchia) ==> Ti aspetta il rilascio della risorsa 
  ==> Wait (Ti)
• se TSi > TSj ==> Ti viene ucciso, e rilascia le aeventuali altri risorse che possiede.
  ==> Die (Ti)
2. Wound-Wait
• se TSi < TSj ==> Tj viene ferita
  ==> Wound (Tj)
• se TSi > TSj ==> Ti aspetta il suo turno
  ==> Wait (Ti)

Ci sono diversi S.O. che mettono a disposizione primitive per la realizzazione di transazioni.  Ad esempio:

Zeus, sistema distribuito sviluppato dall'Universita' del Minnesota e dalla Honeywell) per applicazioni object-oriented, basato sull'effettuazione di checkpoint degli oggetti (sono file)

Clouds (Universita' della Georgia) che consente la replica degli oggetti