2015-06-20 42 views
6

Attualmente sto cercando di capire i timestamp di Lamport. Considerano due processi P1 (produzione di eventi a1, a2, ...) e P2 (eventi producono b1, b2, ...). Let C (e) indica il timestamp Lamport associato all'evento e. Ho creato timestamp per ogni evento, come descritto nella Wikipedia article about Lamport timestamps:Orologi logici: Lamport Timestamps

enter image description here

Secondo Wikipedia, la seguente relazione è vero per tutti gli eventi e1, e2:

Se e1 è successo prima e2, quindi C (e1) < C (e2).

Guardiamo a1 e b2. Chiaramente a1 successo prima b2, e poiché C (a1) = 1 e C (b2) = 3, la relazione vale: C (a1) < C (b2).

Problema: La relazione non vale per b3 e a3. Ovviamente, b3 è avvenuto prima del a3. Tuttavia, C (b3) = 4 e C (a3) ​​= 3. Quindi C (b3) < C (a3) ​​ non non.

Che cosa ho frainteso? L'aiuto è molto apprezzato!

risposta

1

Ho individuato il mio errore.Ho scritto:

Se e1 è accaduto prima e2, allora C (e1) < C (e2).

Tuttavia, Lamport ha definito "preceduto" come ordine parziale. Così dice Wikipedia relazione d'ordine:

Tale rapporto è chiamato un ordine parziale per riflettere il fatto che non ogni coppia di elementi deve essere correlato: per alcune coppie, può essere che né elemento precede la altro nel poset.

Secondo la definizione di Lamport di "successo prima", b3 e a3 non sono legati, in tal modo b3 non ha "accadere prima" a3, quindi equasion indicato nella domanda non deve essere vero.

1

Lamport ipotizza che: non possiamo in genere utilizzare il tempo fisico per scoprire l'ordine di qualsiasi coppia arbitraria di eventi che si verificano all'interno di esso. Nell'esempio proposto, ignori questa ipotesi.

P1 e P2 incrementare i loro orologi indipendente. Quando si verifica un evento, il processo di origine invia il suo valore corrente al processo di destinazione, che controlla se il valore ricevuto è inferiore al suo valore corrente. Se lo è, cambia il suo valore corrente al valore ricevuto + 1, altrimenti scarta il valore ricevuto. Nel tuo caso, P1 e P2 non inviano i loro eventi a3 e b3.

3

Sì, quella definizione potrebbe essere leggermente confusa. È corretto ciò che tutti gli altri hanno detto finora, tuttavia forse manca una parola, per capire meglio il sistema. - concomitante

Se sei processi p1 e p2 sono in esecuzione sulla stessa macchina, non c'è davvero troppo di una necessità di utilizzare gli orologi di Lamport (forse alcuni casi estremamente specifico). Invece puoi semplicemente usare l'orologio fornito dal tuo sistema operativo. Ma cosa succede se p1 e p2 sono su computer che sono separati da una rete lenta e inaffidabile?

Lamport presuppone che non ci si possa fidare del proprio orologio locale e che non si dispone di uno stato globale del sistema distribuito, in cui si sono verificati eventi dell'ordine su 2 computer distinti. Questo è quando chiami quegli eventi che si verificano contemporaneamente.

quando si sarebbe debug l'esecuzione del sistema distribuito e vedreste gli eventi A3 e b3 naturalmente, si potrebbe supporre, a3 successo prima b3. Nel tuo caso specifico ora rivendicherai, sì, ma è sbagliato. Tuttavia, poiché gli eventi non sono correlati, poiché non comunicano tra loro, l'ordine è generalmente considerato concorrente e in tal caso non importa quale sia successo prima o secondo, per l'intera esecuzione di il sistema.

Dato che i computer e le reti stanno lavorando in modo veloce e ancora molto preciso, a volte è difficile da comprendere, guardiamo la stessa cosa in modo leggermente diverso:

p1 e p2 sono due persone che vivono pochi 100 anni fa in due valli diverse. Comunicano insieme usando i pidgin e non parlano mai di quando hanno fatto un determinato compito, solo quello che hanno fatto. In questo modo, nessuno potrebbe sapere, chi se a3 è successo prima b3 o viceversa, quindi sono avvenuti contemporaneamente. Forse non nessuno, dio guardando da su su p1 e p2 potrebbe vederlo.

Purtroppo, quando si dispone di un sistema distribuito, si può non essere Dio e guardare p1 e p2, allo stesso tempo, appena fuori della ragione che i messaggi provenienti da p1 potrebbero richiedere più tempo da p2. Quindi, anche se il tuo sistema di monitoraggio (dio) ha ricevuto le informazioni di b3 prima di ricevere le informazioni su a4, ciò non significa che siano avvenute in questo ordine, forse i pacchetti contenenti informazioni su a4 hanno richiesto un tempo più lungo o percorso più lento.

Alla fine, c'è un'altra cosa chiamata vector clocks. Ogni processo ha un orologio lamport per ogni processo nel sistema. La chiave qui è, evento un sarebbe accaduto solo prima dell'evento b se tutti gli orologi di Lamport di un erano più piccole o uguali quelli di B. Se proverai il tuo piccolo esempio, vedrai che nessun evento è accaduto prima che gli altri => siano concomitanti.