Algoritmo di Peterson in Java?

Question

Esiste un esempio di implementazione dell'algoritmo di Peterson per l'esclusione reciproca in Java?

Answer 1

Nessuno qui ha fornito una corretta implementazione/sicura di questo algoritmo in Java. Non sono sicuro di come si suppone che la soluzione di John W funzioni perché mancano dei pezzi (ovvero le dichiarazioni dei ThreadLocals e una spiegazione di ciò che dovrebbe essere nella sua matrice primitiva booleans non hanno get() e set()).

Chapter 17 of the Java Language Specification spiega il modello di memoria Java.Di particolare interesse è Section 17.4.5, che descrive l'ordine prima di. È abbastanza facile pensare in un singolo thread. Si consideri il frammento:

int x, y, z, w; 
x = 0; 
y = 5; 

z = x; 
w = y; 

tutti saranno d'accordo che alla fine di questo frammento, sia x e z sono uguali 0 ed entrambi y e w sono pari a 5. Ignorando le dichiarazioni, abbiamo sei azioni qui:

1. una scrittura x
2. Una scrittura a y
3. una lettura da x
4. Una scrittura a z
5. una lettura da y
6. A scrivere a w

Poiché tutti compaiono nello stesso thread, il JLS dice che queste letture e scritture sono garantite per mostrare questo ordine: ogni azione n precedente (perché le azioni sono in un singolo thread) ha una relazione prima-evento con tutte le azioni m, m>n.

Ma per quanto riguarda i diversi thread? Per i normali accessi di campo, non esistono relazioni precedenti tra i thread. Ciò significa che un thread A potrebbe incrementare una variabile condivisa e Thread B potrebbe leggere quella variabile ma non vedrà il nuovo valore. Nell'esecuzione del programma in JVM, la propagazione della scrittura del thread A potrebbe essere stata riordinata per accadere dopo la lettura del thread B.

Infatti, Filo A potrebbe scrivere a una variabile x, e quindi a una variabile y, stabilendo un rapporto che accade, prima tra queste due azioni all'interno Discussione A. Ma Discussione B può leggere x e y ed è legale per B per ottenere il nuovo valore di yprima del viene visualizzato il nuovo valore di x. Le specifiche dice:

In particolare, se due azioni condividono una verifica, prima relazione, essi non devono necessariamente comparire essere accaduto in questo ordine a qualsiasi codice con i quali non condividono un prima-accade relazione.

Come risolvere il problema? Per il campo normale accessi, la parola volatile è sufficiente:

Una scrittura ad una variabile volatili (§8.3.1.4) v sincronizza con tutti successive letture di v da qualsiasi thread (dove successivamente si definiscono secondo all'ordine di sincronizzazione).

sincronizza-con è una condizione più forte di verifica, prima, e dal momento che accade, prima è transitiva, se Discussione A vuole Discussione B per vedere le sue scritture x e y, ha solo bisogno di scrivere in un variabile volatile z dopo aver scritto x e . Thread B deve leggere da z prima di leggere x e e sarà garantito per vedere i nuovi valori di x e .

In soluzione di Gabriel, vediamo questo schema: si verifica una scrittura a in, che non sarebbe visibile ad altri thread, ma poi si verifica una scrittura a turn, così altri thread sono garantiti per vedere sia scrive fintanto che leggono turn prima.

Purtroppo, il condizionale ciclo while è indietro: per garantire un filo non vede dati non aggiornati per in, il ciclo while dovrebbe leggere da turn prima:

// ... 
    while (turn == other() && in[other()]) { 
     // ... 

Con questa correzione in mente, la maggior parte delle il resto della soluzione è ok: nella sezione critica, non ci interessa la stoltezza dei dati perché, beh, siamo nella sezione critica! L'unico altro difetto arriva alla fine: il Runnable imposta in[id] su un nuovo valore ed esce. Sarà garantito l'altro thread per vedere il nuovo valore di in[id]? Le specifiche dice no:

l'azione finale in T1 filo sincronizza-con qualsiasi azione un'altra T2 filo che rileva T1 è terminato. T2 può eseguire chiamando T1.isAlive() o T1.join().

Quindi come lo ripariamo? Basta aggiungere un'altra scrittura alla turn alla fine del metodo:

// ... 
    in[id] = false; 
    turn = other(); 
} 
// ... 

Essendo riordinato il ciclo while, l'altro filo sarà garantita per visualizzare il nuovo valore falso della in[id] perché la scrittura a in[id] accade-prima della scrivere su turn, prima che la lettura da turn avvenga prima della lettura da in[id].

Inutile dire che senza una metrica ton di commenti, questo metodo è fragile e qualcuno potrebbe venire avanti e modificare qualcosa e in modo subdolo spezzare la correttezza. Solo dichiarare l'array volatile non è sufficiente: come spiegato in this thread da Bill Pugh (uno degli lead researchers per il modello di memoria Java), la dichiarazione di un array volatile rende gli aggiornamenti dell'array riferimento visibili ad altri thread. Gli aggiornamenti agli elementi dell'array non sono necessariamente visibili (quindi tutti i loop che abbiamo dovuto semplicemente saltare usando un'altra variabile volatile per proteggere l'accesso agli elementi dell'array).

Se volete che il vostro codice sia chiaro e conciso, tenerlo così com'è e cambiare in essere un AtomicIntegerArray (uso 0 per falso, 1 per vero, non c'è AtomicBooleanArray). Questa classe agisce come un array i cui elementi sono tutti volatile e quindi risolverà tutti i nostri problemi.In alternativa, puoi semplicemente dichiarare due variabili volatili, boolean in0 e boolean in1, e aggiornarle invece di usare un array booleano.

Answer 2

non riuscivo a trovare uno sul web me, quindi ho deciso di provare a scriverlo:

public class Peterson implements Runnable { 

    private static boolean[] in = { false, false }; 
    private static volatile int turn = -1; 

    public static void main(String[] args) { 
     new Thread(new Peterson(0), "Thread - 0").start(); 
     new Thread(new Peterson(1), "Thread - 1").start(); 
    } 

    private final int id; 

    public Peterson(int i) { 
     id = i; 
    } 

    private int other() { 
     return id == 0 ? 1 : 0; 
    } 

    @Override 
    public void run() { 
     in[id] = true; 
     turn = other(); 
     while (in[other()] && turn == other()) { 
      System.out.println("[" + id + "] - Waiting..."); 
     } 
     System.out.println("[" + id + "] - Working (" 
       + ((!in[other()]) ? "other done" : "my turn") + ")"); 
     in[id] = false; 
    } 
} 

Sentitevi liberi di commentare, sarà apprezzato :)

Answer 3

A meno che non hai qualche esigenza specifica per l'agoritmo di Peterson (che sarebbe strano quando si lavora in un linguaggio di alto livello come Java), suggerisco di dare un'occhiata alle funzioni di sincronizzazione integrate nella lingua.

Ad esempio, si può trovare questo capitolo libro su "razza Condizioni e Mutua esclusione" in Java utili: http://java.sun.com/developer/Books/performance2/chap3.pdf

In particlar:

Java fornisce un supporto integrato in attesa di questo “ cambio di stato "via la nozione di una condizione. Una condizione è un po 'impropria, tuttavia, perché è interamente a carico dell'utente indipendentemente dal fatto che si sia verificata o meno una condizione in realtà . Inoltre, una condizione non deve essere specificatamente vera o false. Per utilizzare le condizioni, si deve familiarizzare con tre metodi principali della classe Object:

• wait(): Questo metodo viene utilizzato per attendere una condizione. Viene chiamato quando un blocco è attualmente trattenuto per un particolare oggetto (condiviso) .

• notify(): questo metodo è utilizzato per notificare a un singolo thread che una condizione ha (eventualmente) cambiato. Ancora, questo metodo viene chiamato quando un blocco è attualmente trattenuto per un oggetto particolare . Solo una singola stringa può essere risvegliata a seguito di questa chiamata.

• notifyAll(): Questo metodo viene utilizzato per notificare più thread che una condizione ha (eventualmente) cambiato. Tutti i thread che sono in esecuzione al momento in cui viene chiamato questo metodo saranno notificati .

Answer 4

Si consiglia di consultare il libro The Art of Multiprocessor Programming. Egli in grande dettaglio esamina diverse implementazioni di blocco (sia spin che block). Analizza anche altri tipi di algoritmi concorrenti (skip list per esempio). Ecco un frammento dal suo libro sull'algoritmo Peterson Blocco

Class Peterson implements Lock{ 
    private final boolean []flag = new boolean[2]; 
    private volatile int victim; 

    public void lock(){ 
     int i = ThreadID.get(); // ThreadID is a ThreadLocal field 
     int j= 1 - i; 
     flag[i] = true; // I'm Interested 
     victim = i;  // You go first 
     while(flag[j] && victim == i){}; //wait 
    } 
    public void unlock(){ 
     int i = ThreadID.get(); 
     flag[i] = false;  //Not interested anymore 
    } 
} 

Answer 5

Sebbene non siano le sole paterson, le classi AtomicBoolean e Atomic * utilizzano l'approccio di loop senza blocco e occupato per aggiornare i dati condivisi. Possono soddisfare le tue esigenze.