Cercando di capire l'algoritmo N-Process di Peterson

Question

Sto cercando di capire l'algoritmo N-Process di Peterson e mi sono imbattuto in questa domanda.

Domanda: Supponiamo 3 processi hanno ID di processo 0, 1 and 2. Questi processi vengono eseguiti simultaneamente su un processore Uni e utilizzano l'algoritmo N-process di Peterson per controllare l'esecuzione della sezione critica. Ogni processo esegue il seguente pseudo codice:

lock(pid); 
<critical section>; 
unlock(pid 

dove lock() e unlock() funzioni sono definiti come

lock(for Process i): 

/* repeat for all partners */ 
for (count = 0; count < (NUMPROCS-1); count++) { 
    flags[i] = count; 
    turn[count] = i; 
    "wait until (for all k != i, flags[k]<count) or (turn[count] != i)" 
} 


Unlock (for Process i): 

/* tell everyone we are finished */ 
flags[i] = -1; 

Supponiamo lo stato del sistema in un dato momento è definita da <flags[0], flags[1], flags[2], turn[0], turn[1]> valori e l'id il processo attualmente in esecuzione. Supponiamo inoltre che lo stato attuale del sistema sia <0,0,0,2,-1> con il processo 0attualmente in esecuzione. Mostra un modo particolare per i tre processi da eseguire fino al completamento a partire da questo stato. Mentre si traccia l'esecuzione simultanea di tre processi, mostrare lo stato del sistema ad ogni passaggio.

mie osservazioni

processi eseguiti contemporaneamente su un monoprocessore non possono eseguire sulla CPU contemporaneamente. Solo uno di questi può essere eseguito sulla CPU alla volta. Mentre un processo è in esecuzione sulla CPU, può eseguire qualsiasi parte del suo codice.

// NUMPROCS = 3 

- Per i = 0

lock(for Process 0): 
for (count = 0; count < 2; count++) { 
    flags[0] = count; 
    turn[count] = 0; 
    "wait until (for all k != 0, flags[k]<count) or (turn[count] != 0)" 
} 


Unlock (for Process 0): 
flags[0] = -1; 

- Per i = 1

lock(for Process 1): 
for (count = 0; count < 2; count++) { 
    flags[1] = count; 
    turn[count] = 1; 
    "wait until (for all k != 1, flags[k]<count) or (turn[count] != 1)" 
} 


Unlock (for Process 1): 
flags[1] = -1; 

- Per i = 2

lock(for Process 2): 
for (count = 0; count < 2; count++) { 
    flags[2] = count; 
    turn[count] = 2; 
    "wait until (for all k != 2, flags[k]<count) or (turn[count] != 2)" 
} 


Unlock (for Process 2): 
flags[2] = -1; 

La mia domanda è quella Dove iniziare a tracciare il codice? È dato che flags[0]=0, flags[1]=0, flags[2]=0, turn[0]=2, turn[1]=-1 ma come ci aiuterà a dove iniziare a tracciare il codice?

• Se cominciamo a poco prima del ciclo for del processo 0 quindi tutti i valori di direzione verrebbero impostati su valori diversi diversi da ciò che è dato a noi.

• Se assumiamo eseguendo domanda significa processo 0 è nel suo sezione critica poi il ciclo for del prossimo processo imposterà i valori di direzione a qualcos'altro.

Perché ci vengono dati valori di stato e come può aiutarci a trovare da dove iniziare a tracciare il codice.

Sarebbe bello se avessi qualche suggerimento per aiutarmi a iniziare a tracciare il codice.

Grazie e scusa per la lunga domanda.

Answer 1

Dato che non hai chiesto la risposta alla domanda e hai fatto una domanda ragionevole e ragionevole, mi sento fiducioso di poterti indirizzare nella giusta direzione senza fare i compiti a casa (o qualsiasi altra cosa) per te.

Innanzitutto, la parte fondamentale della questione è qui:

Supponiamo lo stato del sistema in un dato momento è definita da <flags[0], flags[1], flags[2], turn[0], turn[1]> valori e l'ID del processo in esecuzione. Supponiamo inoltre che lo stato corrente del sistema sia <0,0,0,2,-1> con il processo 0 attualmente in esecuzione.

Da questo si può supporre che il sistema sia stato avviato normalmente e sia arrivato a quello stato durante l'esecuzione. Quindi dobbiamo trovare un punto in cui il sistema può trovarsi in quello stato e il processo 0 sta eseguendo. La parte successiva ci dà un po 'di spazio di manovra:

Mostra un modo particolare per tre processi per eseguire il completamento a partire da questo stato.

Quindi, ci possono essere diversi modi per arrivare a quei valori di variabile con l'esecuzione del processo 0 ma è OK trovarne uno e andare da lì per completare il sistema.

Inoltre, possiamo vedere che tutti i processi vengono eseguiti una volta ed escono - c'è un ciclo ma possiamo anche vedere che incrementa i valori di flags ad ogni turno, quindi possiamo fare una buona impressione che colpiamo solo questo scenario per i valori delle variabili una volta. Ma dovremmo lavorarci per scoprirlo.

I processi sono in esecuzione contemporaneamente, ma su un singolo processore. Quindi in realtà solo uno è mai in esecuzione, ma una potenza maggiore (un sistema operativo per esempio) sta passando tra di loro in un modo che non possiamo determinare. Tu dici:

Mentre un processo è in esecuzione sulla CPU, è possibile eseguire qualsiasi parte del suo codice.

Penso che hai appena formulato questo male, ho il sospetto si capisce la realtà è che ogni processo comincia all'inizio e corre fino a quando è fine, quindi, "Mentre un processo è in esecuzione sulla CPU si inizia dove si era interrotto e può eseguire un numero qualsiasi di istruzioni finché non perde il diritto di funzionare sulla CPU (il numero di istruzioni dipende da qualsiasi cosa stia controllando il sistema) "è un'affermazione più accurata.

Quindi il modo più semplice è solo iniziare all'inizio e girare la maniglia. La questione non dire questo, ma le bandiere e girare normalmente inizializzato a -1 quindi all'inizio abbiamo:

flags = [ -1, -1, -1 ]; turn = [ -1, -1 ] 

Poiché le cose sono in esecuzione contemporaneamente diciamo solo supporre che ogni processo viene eseguito in modo efficace ogni linea allo stesso tempo. Non fa alcuna differenza, come si spera sarà in grado di vedere da solo in seguito.

for (count = 0; count < (NUMPROCS-1); count++) { 

OK, count = 0 per tutti i processi e tutti vanno alla riga successiva:

flags[i] = count; 

Così ora:

flags = [ 0, 0, 0 ]; turn = [ -1, -1 ] 

Fin qui, tutto bene - riga successiva :

turn[count] = i; 

OK, questo è problematico - ogni p il processo tenta di impostare la stessa variabile. Uno di loro vincerà ma non sappiamo quale:

flags = [ 0, 0, 0 ]; turn = [ ?, -1 ] 

Eccetto che lo facciamo, come è nella domanda. Possiamo fare turn[0] = 2. Quindi siamo in uno stato adeguato con le variabili, possiamo assumere processo 0 è in controllo e sappiamo che è su questa linea:

"wait until (for all k != i, flags[k]<count) or (turn[count] != i)" 

per iniziare, per il processo 0, count = 0 ei = 0 così

"wait until (for all k in {1,2}, flags[k]<0) or (turn[0] != i)" 

si può vedere che la clausola or è falsa, quindi processo 0 andrà tutto il ciclo di nuovo. Così procederà 1. La clausola for all k non è vera per nessuno. Quindi il processo 2 attenderà il valore di turn[0] - si può anche vedere che questo non cambierà mai, quindi il processo 2 è ora bloccato in attesa che la clausola for all k diventi vera - in effetti è la chiave per il funzionamento di questo sistema. Se segui la logica per rispondere alla domanda, vedrai come i processi si bloccano a vicenda in modo che solo uno esegua la sezione critica alla volta. Continua a fare quello che ho fatto sopra, dal momento che devi solo trovare un percorso per eseguire linee nello stesso momento e quando c'è un potenziale scontro, scegli un valore e vai da lì.

Si può anche vedere che se il processo 2 avesse eseguito tutte le sue linee contemporaneamente prima che gli altri avessero una possibilità, e poi processare 1 e poi elaborare 0 si finirebbe nello stesso posto. Se si lavora con l'intero sistema in vari modi, si troverà il modello simile (si noti che non vi è alcuna garanzia sull'ordine in cui i processi eseguiranno le loro sezioni critiche, dipende da chi "vince" sulle linee contestate).

Quindi, tornando alla domanda originale, ci sono solo pochi punti in cui il processo 0 può essere in controllo con quello stato del sistema. O sulla linea wait o sulla riga for quando il conteggio viene aumentato a 1 (dopo il ciclo continuo) o sulla linea in cui viene impostato flag[0]. Dopo che lo stato del sistema non è lo stesso. È meglio assumerne la prima poiché il processo 1 non è ancora bloccato e potrebbe anche cambiare lo stato.

Una ruga finale, per completezza. C'è un altro posto in cui quel processo può avere il controllo e lo stato del sistema può essere così. Ed è appena prima della linea turn[count] = i;. In questo scenario, il processo 2 ha appena impostato la variabile e il processo 0 sta per sovrascriverlo. Puoi continuare da qui, ma saranno i processi 1 e 2 a fare il giro. Includo questo anticipando un commento a riguardo, in realtà non sto suggerendo di usarlo come punto di partenza, sebbene sia completamente valido. La domanda quasi certamente si aspetta che tu inizi dai processi 0 e 1 andando in giro per il ciclo, con 2 bloccati nell'attesa attesa per vedere cosa succede da lì.

Buona fortuna.