Originariamente inviato da YuYevon
(chiedo scusa se mi dilungherò un po')
L'algoritmo di Wikipedia (in italiano) mi sembra scritto male. Quel goto P non ha senso: se il processo 0 trova che il processo 1 ha il flag impostato a true e che il turno è suo (cioè del processo 1), non deve ritentare di entrare in sezione critica (quindi quel goto P non deve esserci), ma deve attendere che la variabile turno sia impostata a 0, per poi ritentare di entrare in sezione critica. Chiaramente lo stesso vale dal punto di vista del processo 1.
Ti consiglio di vedere l'algoritmo nella versione inglese di Wikipedia
http://en.wikipedia.org/wiki/Dekker%...thm#Pseudocode
In sostanza, se il processo i vede che la variabile turno è impostata proprio ad i, sa di poter "insistere" a entrare nella sezione critica e non si ferma nel ciclo while() "a vuoto", continuando quindi a verificare il valore del flag dell'altro processo.
Se non ci fosse la variabile turno, ma solo le due variabili "flag", l'algoritmo sarebbe come questo
(tratto da "Sistemi operativi", W. Stallings)
codice:
P0:
flag[0] = true;
while (flag[1]) {
flag[0] = false;
/* breve pausa */
flag[0] = true;
}
<sezione critica>
flag[0] = false;
<resto del programma>
P1:
flag[1] = true;
while (flag[0]) {
flag[1] = false;
/* breve pausa */
flag[1] = true;
}
<sezione critica>
flag[1] = false;
<resto del programma>
che potrebbe essere anche una soluzione corretta, ma presenta un problema di fondo: non tiene conto del fatto che, nella progettazione di algoritmi di sincronizzazione, non si debba fare alcuna ipotesi sulla velocità relativa di esecuzione dei due processi. Potrebbe infatti accadere questo:
P0 imposta flag[0] a true;
P1 imposta flag[1] a true;
P0 controlla flag[1];
P1 controlla flag[0];
P0 imposta flag[0] a false;
P1 imposta flag[1] a false;
--da capo--
P0 imposta flag[0] a true;
P1 imposta flag[1] a true;
...
in sostanza, se i due processi eseguissero le istruzioni dell'algoritmo alternandosi strettamente, continuerebbero a farsi le cerimonie reciprocamente e nessuno di loro entrerebbe mai in sezione critica, della serie "prima tu P0", "no ma figurati, prima tu P1" e così, da un punto di vista
teorico, potrebbero andare avanti all'infinito.
Ora è chiaro che una situazione del genere, sul piano
reale, è estremamente improbabile. Tuttavia il problema è che, da un punto di vista formale, questa soluzione fa un'ipotesi non legittima sulla velocità relativa dei processi, violando uno dei principi di base della problematica della sincronizzazione. Insomma probabilmente andrebbe quasi sempre bene, ma per essere valido l'algoritmo non può violare quello che è un assioma, un po' come se fosse un teorema di geometria.
In conclusione, comunque, ti consiglio di dare un'occhiata all'algoritmo di Petterson, che "semplifica" l'algoritmo di Dekker, anzi secondo Tanenbaum (in "I moderni sistemi operativi") lo rende addirittura "obsoleto", al punto che quest'ultimo nel suo libro non lo descrive nemmeno, limitandosi ad un semplice accenno alla sua esistenza.
Ti consiglio inoltre, se ne hai occasione, la lettura del succitato libro di Stallings per la parte relativa alla sincronizzazione dei processi: è spiegata in maniera eccellente a mio avviso, anche per quanto riguarda le soluzioni hardware e le primitive di sincronizzazione.
Tra l'altro, l'algoritmo riportato su Wikipedia in inglese è praticamente lo stesso dello Stallings; quello della versione italiana non so da chi sia stato partorito, sinceramente.
Rispondi quotando
