Appunti - Sapienza

Dai sistemi concorrenti a quelli distribuiti:
il problema della mutua esclusione Quando si hanno processi concorrenti che accedono ad un risorsa condivisa
nasce il bisogno di sincronizzarli in modo tale che tale risorsa sia
assegnata ad un processo alla volta. Questo problema va sotto il nome di
mutua esclusione. Dal punto di vista astratto il problema puo' essere
formulato come segue. Ci sono N processi ognuno dei quali ripete la
seguente sequenza di passi di programma


sezione critica


Una volta uscito dall'exit protocol il processo puo' rientrare infinite
volte nel trying protocol. Questo problema e' stato definito per la prima
volta da Dijkstra nel 1965 il quale fornisce anche una soluzione (istanzia
cioé il trying protocol e l'exit protocol) in un modello di sistema che noi
chiameremo concorrente. In un sistema concorrente esiste uno "scheduler"
centralizzato che permette ad un solo processo alla volta di entrare in
esecuzione e quindi di evolvere secondo il suo codice. Di fatto quindi lo
scheduler esegue una linearizzazione di tutte le istruzioni elementari
effettuate dai vari processi. La linearizzazione creata dalla singola
esecuzione dell'algoritmo è chiamata "schedule". Il modello di Dijkstra si
basa sulle seguenti assunzioni:
1) i processi comunicano leggendo e scrivendo variabili condivise
2) la lettura e la scrittura di una variabile è una azione atomica
Nessuna assunzione viene fatta sulla velocità dei processi e sul tempo che
i processi ci mettono ad eseguire una singola azione atomica. Questa e' la
tipica situazione di più processi che condividono una parte della stessa
memoria.
Le proprietà di correttezza del problema di mutua esclusione da rispettare
sono le seguenti (formulazione originale di Dijstra 1965):
a) Mutua esclusione (ME): due processi non posseno essere nelle loro
sezioni critiche contemporaneamente
b) No deadlock (ND): in una esecuzione di N processi dove un processo
rimane bloccato nella sua trying section, ci sono uno o più processi
che riescono ad entrare ed a uscire dalla loro sezione critica
E' anche interessante aggiungere altre proprietà al problema:
No Starvation (NS) nessun processo può rimanere bloccato per sempre nella
sua trying section.
Da notare che NS ( ND. Algoritmo di Dijkstra (1965)
Quando il processo i vuole entrare in sezione critica prova prima ad
impostare k al suo id i, passando quello che si chiama il ciclo di
sentinella. Il valore di k ci dice chi e' l'ultimo processo pj che e'
uscito dal ciclo della sentinella. Da notare che ciò non significa
necessariamente che pj è l'unico processo che supera il ciclo della
sentinella.
Esempio: Consideriamo infatti un sistema di 3 processi, p1, p2 e p3. Tutti
e tre i processi iniziano ad eseguire la loro trying section. P1 entra nel
ciclo della sentinella (esegue il test sul while) e poi viene interrotto
dallo scheduler che mette in esecuzione p2. Anche p2 entra nel ciclo e
viene bloccato dallo scheduler. Infine lo scheduler attiva p3 che esegue
con successo tutto il ciclo della sentinella (settando il valore di k a 3).
A questo punto lo scheduler sveglia prima p1 e poi p2, quindi quando tutti
e tre i processi sono usciti dal ciclo della sentinella k ha assunto il
valore 2. Nel secondo ciclo (for) si controlla se ci sono stati passaggi concorrenti
attraverso il primo ciclo ed in questo caso si deve eseguire una ulteriore
scrematura per permettere ad un solo processo di entrare in sezione critica
tra quelli passati per il ciclo della sentinella. Esempio: riconsideriamo l'esempio precedente. Diversi casi possono accadere
una volta p1, p2 e p3 superano il ciclo della sentinella. Analizziamo i due
casi estremi particolarmente significativi. Se grazie alle attivazioni
dello scheduler un processo, per esempio p1, riesce ad eseguire con
successo il ciclo for (cio' significa che p2 e p3 sono stati bloccati
dallo scheduler prima di eseguire l'istruzione 6), allora entrerà nelle sua
CS indipendentemente dal fatto che k è stato settato da p2. Nel caso in
cui tutti e tre i processi non riescono a completare il ciclo for,
ritorneranno alla linea 3 (goto statement). A questo punto mentre p1 e p3
si bloccheranno nel ciclo della sentinella, p2 sarà l'unico processo in
grado di superarlo e quindi di portare con successo l'ingresso in sezione
critica poiché p2 sarà l'unico processo ad eseguire il ciclo for. Questo algoritmo soddisfa ME, ND ma non NS.
Shared variables
x[1,..n]: array of Boolean, initially all false
y[1,..n]: array of Boolean, initially all false
k: integer in range 1,..N, initially any value in its range
Local variables
j: integer in range 1,..N
repeat
1. NCS
2. y[i]:= true % inizio trying protocol %
3. x[i]:= false
4. while k(i do % ciclo della sentinella %
5. if not y[k] then k:=i
6. x[i]:= true
7. for j:= 1 to n do
8. if i(j and x[j] then goto 3 % fine trying protocol %
9. CS
10. y[i]:=x[i]:= false; % exit protocol %
forever
Algoritmo di Dijkstra (1965) Prova di ME. Per contraddizione supponiamo due processi i e j in sezione
critica. Poiché i è in sezione critica allora i trovò x[j]=false durante il
test di linea 8. Questo implica che pi ha eseguito la linea 8 prima che pj
eseguisse la linea 6, pertanto i.8 ( j.6. Chiaramente i.6 ( i.8 quindi si
ha i.6 ( j.6. Scambiando i e j e seguendo lo stesso ragionamento otteniamo
j.6 ( i.6. pertanto i.6 ( i.6, ovvero una contraddizione. ( Prova di ND. Supponiamo per contraddizione che esiste un deadlock che
coinvolge un insieme di processi D (ovvero tutti i processi in D sono
bloccati nella trying e nessuno può entrare nella propria CS). Per tutti i
processi i' in D, y[i']=true. Prendiamo il processo i che fa l'ultima
assegnazione della variabile k (linea 5). Ovvero dopo questa assegnazione
k=i per sempre. Questo processo i appartiene a D altrimenti qualche altro
processo j in D troverebbe y[i]=false e quindi porrebbe a j il valore della
variabile k a linea 5. A questo punto ogni processo i' in D\{i} avrà prima
o poi (eventually) x[i']=false, di conseguenza questi processi si bloccano
nel while (linee 4-5). Inoltre la variabile x[i'] sarà prima o poi falsa
anche per tutti quei processi che non appartengono a D e che sono in NCS.
Consideriamo ora il processo i. Questo processo salta il ciclo while (linea
4) poiché k=i ed entrerà in sezione critica poiché tutti i valori x[i'] dei
processi diversi da i sono falsi. Ma allora il processo i non può
appartenere a D, contraddizione all'ipotesi che i deve necessariamente
appartenere a D. ( Domanda: Un processo che setta con successo la variabile k quante volte può
eseguire l'istruzione "goto 3" prima di entrare in sezione critica?
Domanda: Perché NS non è soddisfatta? Fornire un particolare scenario in
cui si viola NS. Il primo algoritmo derivato da quello di Dijkstra e starvation-free è
dovuto a Knut (1966). L'algoritmo del panettiere di Lamport (1975)
Nell'algoritmo di Dijkstra si assume che le read e le write sono atomiche
ovvero o si esegue una o l'altra. Inoltre poiché esiste una variabile che
viene letta e scritta da tutti (variabile k), questo imporrebbe che
processi accedano alla stessa memoria fisica. Se si ragiona in un sistema
con singola CPU (a livello harware) a memoria unica questo modello è
assolutamente realistico. Una CPU o organizza un accesso in memoria in
scrittura o in lettura. Se pensiamo ad un livello di astrazione più alto
per esempio un sistema distribuito classico basato su reti di calcolatori o
ad un sistema multiprocessore in cui ogni processore ha una memoria locale
dove tiene le proprie variabili, questa assunzione comincia ad essere un
po' troppo forte. Potremmo avere copie di una stessa variabile su diverse
macchine o accessi concorrenti in lettura ed in scrittura ad una variabile
condivisa o file system che permettono ad utenti di leggere e scrivere file
contemporaneamente. Questo potrebbe portare una operazione di write a
prendere un tempo considerevole per la sua esecuzione su diverse macchine.
Dal punto di vista teorico è oltremodo interessante chiedersi: possiamo
risolvere il problema della mutua escusione senza basarci su primitive
hardware sottostanti che di fatto eseguono una mutua esclusione?
Oltre a D1, le assunzioni su cui si basa Lamport sono :
1) la lettura e la scrittura di una variabile non è una azione atomica.
Uno scrittore potrebbe scivere mentre un lettore sta leggendo e
nessuno (lettore o scrittore) viene notificato di tale interferenza.
2) Ogni variabile condivisa è di proprietà di un processo. Questo
processo è l'unico che può scrivere tutti gli altri possono solo
leggere (differentemente dalla variabile k dell'algoritmo di
Dijkstra).
3) Nessun processo può emettere due scritture concorrentemente
4) Le velocità di esecuzione dei processi sono non correlate. In un tempo
infinito ogni processo esegue infiniti step elementari mentre in un
tempo finito esegue un numero finito di passi.
In questo algoritmo la trying section è divisa in due parti: la doorway (da
linea 2 a linea 4) e il bakery (dal linea 5 a linea 8). Quando un processo
entra nella doorway lo segnala agli altri attrave