Buongiorno, sto studiando dal libro "i moderni sistemi operativi (Tenenbaum)" la struttura e il funzionamento dei sistemi operativi, studiati i processi e i thread sono arrivato al capitolo che affronta la comunicazione tra processi, ho però qualche dubbio sull'algoritmo di Peterson per l'implementazione della mutua esclusione. Non ho ben capito come funziona in generale l'algoritmo, e su internet non trovo molto (un paio di slide universitarie con con concetti schematizzati per lo studio), qualcuno gentilmente potrebbe spiegarmelo?
Abbiamo due processi paralleli eseguiti in maniera asincrona e una porzione di codice, chiamata sezione critica, per la quale vogliamo garantire mutua esclusione: al più un processo per volta deve aver accesso alla sezione critica e, in nessun caso, nessun processo deve ritrovarsi bloccato (deadlock e starvation) senza mai poter entrare o uscire dalla tale sezione. L'esempio classico riguarda l'utilizzo di risorse condivise: due processi vogliono scrivere sullo stesso file, ma se lo fanno contemporaneamente il risultato sarà incomprensibile.
Siamo negli anni '80, quindi non abbiamo hardware facilities come le istruzioni atomiche test-and-set e compare-and-swap. Se un processo assegna un valore ad una variabile quando un altro processo controlla il suo valore, il risultato è impredicibile. La prima soluzione a questo problema risale agli anni '60 (algoritmo di Dekker), usava un ciclo innestato e non è semplice da capire. Per circa 15 anni hanno provato a fornire semplificazioni di vario genere ma, in generale, gli algoritmi concorrenti sono difficili da analizzare correttamente e molte delle soluzioni proposte si sono poi rivelate sbagliate. L'algoritmo di Peterson è importante in quanto fornisce la prima soluzione semplice (semplice da scrivere, ma soprattutto semplice da dimostrare) per il problema della mutua esclusione.
Giusto per mettere le cose in chiaro, la condizione del while loop non viene calcolata in modo atomico quindi:
Dimostriamo che la mutua esclusione è garantita supponendo, per assurdo, che entrambi i processi si trovano contemporaneamente all'interno della sezione critica. Ovvero, sia F1 che F2 sono true quando in un certo istante di tempo P1 ha trovato turn a 1 e, in un altro istante di tempo, P2 ha trovato turn a 2. Questo scenario è impossibile perché nel momento in cui P1 trova turn a 1, l'assegnamento
Dimostriamo che nessun processo viene tagliato fuori (starvation) per sempre. Assumendo che P1 sia in possibile starvation nel ciclo while, ci ritroviamo in una di queste condizioni:
Mi rendo conto che è un po' una spiegazione "alla wikipedia", ma a domande vaghe non possono che esserci risposte generiche. Se mi chiarisci cosa non hai capito, o se provi a spiegarmi tutto l'algoritmo a parole tue, forse riesco a darti un aiuto più mirato.
Siamo negli anni '80, quindi non abbiamo hardware facilities come le istruzioni atomiche test-and-set e compare-and-swap. Se un processo assegna un valore ad una variabile quando un altro processo controlla il suo valore, il risultato è impredicibile. La prima soluzione a questo problema risale agli anni '60 (algoritmo di Dekker), usava un ciclo innestato e non è semplice da capire. Per circa 15 anni hanno provato a fornire semplificazioni di vario genere ma, in generale, gli algoritmi concorrenti sono difficili da analizzare correttamente e molte delle soluzioni proposte si sono poi rivelate sbagliate. L'algoritmo di Peterson è importante in quanto fornisce la prima soluzione semplice (semplice da scrivere, ma soprattutto semplice da dimostrare) per il problema della mutua esclusione.
Codice:
int turn;
bool F1 = false;
bool F2 = false;
P1 | P2
------------------------------------------------+------------------------------------------------
F1 = true; | F2 = true;
turn = 2; | turn = 1;
while (F2 == true && turn == 2) { /* wait */ } | while (F1 == true && turn == 1) { /* wait */ }
critical_section(); | critical_section();
F1 = false; | F2 = false;Giusto per mettere le cose in chiaro, la condizione del while loop non viene calcolata in modo atomico quindi:
- P1 controlla la prima metà del while,
F2 == true, e stabilisce che la condizione è vera; - P2 esegue
F2 = false;; - P1 controlla la seconda metà del while,
turn == 1, e stabilisce che la condizione è vera; e - P1 entra nel while senza accorgersi che la prima condizione è diventata falsa
Dimostriamo che la mutua esclusione è garantita supponendo, per assurdo, che entrambi i processi si trovano contemporaneamente all'interno della sezione critica. Ovvero, sia F1 che F2 sono true quando in un certo istante di tempo P1 ha trovato turn a 1 e, in un altro istante di tempo, P2 ha trovato turn a 2. Questo scenario è impossibile perché nel momento in cui P1 trova turn a 1, l'assegnamento
turn = 2 fatto da P1 è già stato sovrascritto da P2 e quindi non potrà essere usato a sua volta per sovrascrivere l'assegnamento turn = 2 fatto da P2. È banalmente vero il vice versa.Dimostriamo che nessun processo viene tagliato fuori (starvation) per sempre. Assumendo che P1 sia in possibile starvation nel ciclo while, ci ritroviamo in una di queste condizioni:
P2 non è interessato alla sezione critica: F2 è false perché P2 è già uscito dalla sezione critica o non ha mai provato ad entrarci, quindi P1 si sblocca immediatamente.
P2 è all'interno della sezione critica: P2 eseguirà
F2 = false non appena avrà terminato di usare la sezione critica, quindi P1 si sblocca dopo un lasso di tempo finito.P2 è anche lui in busy waiting nel ciclo while: visto che la variabile turn o vale 1 o vale 2, uno dei due processi è destinato a sbloccarsi immediatamente.
L'ultima condizione dimostra anche l'assenza di deadlock: quando entrambi sono in attesa non ci sono assegnamenti, e dato che turn può assumere solo due valori uno (e solo uno) non è in condizione di aspettare ulteriormente.Mi rendo conto che è un po' una spiegazione "alla wikipedia", ma a domande vaghe non possono che esserci risposte generiche. Se mi chiarisci cosa non hai capito, o se provi a spiegarmi tutto l'algoritmo a parole tue, forse riesco a darti un aiuto più mirato.
Si scusa, da quel che ho capito dal libro, l'algoritmo funziona in questo modo, quando P1 ha intenzione di entrare nella prorpia sezione critica imposta il flag (utilizziamo un array di valori booleani di due elementi), e turn a 0, controlla se il flag di P2 è impostato e se è il suo turno, se è il suo turno e il flag di P2 non è impostato, entra nella sezione critica, stesso discorso per P2.
Ma se qualcosa deve andare male lo farà, se P1 e P2 tentano di entrare nelle proprie sezioni critche "contemporaneamente" , turn viene posto col valore dell'ultimo processo che lo ha modificato, quindi se viene eseguito prima P1 e imposta turn a 0 e il flag, poi viene interrotto da P2 che sovrascrivere turn con 1 e imposta il flag, viene eseguito il confronto in P2, che risulta vero entrato in busy waiting, in quanto è il turno di P2 è il flag di P1 è impostato, restituito il controllo a P1 esegue anche lui il controllo che non è verificato entramdo nella zona critica (non è il suo turno), dopo di che pone il falg a 0 e P2 entra nella propria zona critica.
Da quel che ho capito se P2 interrompe P1, comunica ciò a P1 cambiando il turno,
P1 si accorge che non è il suo turno, sapendo che un secondo processo lo ha interrotto, a quel punto entra nella sezione critica, altrimenti busy waiting, che avviene quando è il suo turno è il flag di P2 è impostato.
Inoltre, non si potrebbe porre P2 nello stato di attessa apposto di entrare in busy waitng,
Credo che tu abbia invertito un po' di zeri e uni. Se, guardando il codice che ho scritto nel messaggio precedente, inverti
turn = 2 con turn = 1 perdi la proprietà di mutua esclusione. L'algoritmo di Peterson è gentiluomo: il processo alza la propria flag per dire "ho bisogno di entrare nella sezione critica" e poi cede il turno al suo contendente. Il processo 1 dice che è il turno del processo 2, e vice versa. Da come l'hai descritto tu, sembra che ogni processo dice "è il mio turno" e questa piccola modifica è sufficiente per mandare tutto in fumo. Il codice è molto corto, ma tutti i dettagli sono fondamentali. Non a caso ci hanno impiegato quasi 20 anni per trovare un algoritmo così semplice e pulito per risolvere questo problema.
Secondo me "interrompere" non è proprio il verbo più adatto per descrivere ciò che avviene. Io segnalo che ho interesse ad entrare in sezione critica e ti cedo il posto. Mentre sono in attesa (waiting), continuo a lavorare (busy) per controllare se è finalmente giunto il mio turno per entrare. Il body del ciclo while è un commento a tutti gli effetti: il processo non va in pausa, ma continua a ad eseguire il confronto del while. Poi vabbé, nulla mi vieta di mettere uno sleep di qualche per evitare di sparare un core al 100%, ma voglio sottolineare che non c'è una pausa vera come quella che avviene con i semafori. Nel busy waiting il processo rimane attivo e spreca cicli di cpu per ripetere più e più volte il controllo condizionale. In ogni caso, non è che io sto facendo qualcosa di importante (entrare nella sezione critica) e tu mi interrompi; sono io che entro volutamente in attesa, cedendoti il posto, per poi controllare freneticamente se è finalmente giunto il mio turno per entrare.
Comunque, per questo algoritmo una descrizione informale non è sufficiente. Per discuterlo è indispensabile scrivere e guardare uno pseudocodice perché se sbagli anche solo un piccolo particolare non funziona più niente: molte delle soluzioni che hanno pubblicato dopo l'algoritmo di Dekker e prima di quello di Peterson erano soluzioni che sembravano corrette, ma in qualche caso difficile da individuare violavano uno dei requisiti che ti ho brevemente descritto nel messaggio precedente. Gli algoritmi concorrenti sono molto fragili, non basta l'intuizione.
Sì, ho controllato e l'unica differenza rilevante è l'infelice scelta di chiamare quella variabile turn: la variabile turn presente nel mio pseudocodice, così come quella usata da wikipedia e dall''altra fonte indicata da Tralalla, ha un significato diverso (opposto) alla variabile turn che trovi sul tuo libro. Per il resto le differenze sono minime.
Nello pseudocodice che ti ho scritto e nelle fonti riportate da Tralalla, turn sta ad indicare: "ora è il turno di turn di entrare in zona critica". Sul tuo libro, turn sta ad indicare: "ora non è il turno di turn di entrare in zona critica", oppure "è il turno di turn di rimanere in attesa". Immagino che abbiano fatto quella scelta per il solo motivo di evitare di usare un != invece di un ==.
Nello pseudocodice che ti ho scritto e nelle fonti riportate da Tralalla, turn sta ad indicare: "ora è il turno di turn di entrare in zona critica". Sul tuo libro, turn sta ad indicare: "ora non è il turno di turn di entrare in zona critica", oppure "è il turno di turn di rimanere in attesa". Immagino che abbiano fatto quella scelta per il solo motivo di evitare di usare un != invece di un ==.
DISCUSSIONI SIMILI
- Release
- In evidenza
-
- 29
-
- 8K
- Release
-
- 3
-
- 3K
- In evidenza
-
- 20
-
- 13K