Algoritmo Peterson en Java?

Question

¿Hay implementación de ejemplo del algoritmo de Peterson para la exclusión mutua en Java?

Answer 1

Aquí nadie ha proporcionado una aplicación correcta/seguridad de este algoritmo en Java. No estoy seguro de cómo se supone que la solución de John W funciona, ya que faltan piezas (es decir, las declaraciones de ThreadLocals y una explicación de lo que se supone que es en su primitiva matriz booleans no tienen get() y set()).

Chapter 17 of the Java Language Specification explica el modelo de memoria de Java.De particular interés es Section 17.4.5, que describe el pedido antes del pedido. Es bastante fácil pensar en un solo hilo. Considere el fragmento:

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

z = x; 
w = y; 

Todo el mundo estará de acuerdo en que al final de este fragmento, tanto x y z son iguales a 0 y ambos y y w son iguales a 5. Haciendo caso omiso de las declaraciones, tenemos seis acciones aquí:

1. una escritura en x
2. una escritura en y
3. una lectura de x
4. una escritura en z
5. una lectura de y
6. A escriba a w

Dado que todos aparecen en el mismo subproceso, el JLS dice que estas lecturas y escrituras tienen la garantía de mostrar este orden: cada acción n anterior (porque las acciones están en un solo subproceso) tiene una todas las acciones m, m>n.

¿Pero qué pasa con los diferentes hilos? Para los accesos de campo normales, no hay relaciones de sucesos anteriores establecidas entre subprocesos. Esto significa que un subproceso A puede incrementar una variable compartida y el subproceso B podría leer esa variable, pero no puede ver el nuevo valor. En la ejecución del programa en la JVM, la propagación de la escritura del subproceso A puede haberse reordenado después de la lectura del subproceso B.

De hecho, Tema A podría escribir a una variable x, y luego a una variable y, estableciendo una relación sucede-antes entre esas dos acciones dentro del hilo de rosca A. Pero B puede leer x y y y es legal para B para obtener el nuevo valor de yantes de aparece el nuevo valor de x. La especificación dice:

Más específicamente, si dos acciones comparten un pasa-antes de relación, que no necesariamente tiene que aparecer haber sucedido en ese orden para cualquier código con los que no comparten una relación anterior-anterior.

¿Cómo lo arreglamos? Para campo normal accesos, la palabra clave volatile es suficiente:

Una escritura a una variable (§8.3.1.4) v volátil sincroniza-con toda posterior lee de v por cualquier hilo (donde subsiguiente se define de acuerdo a la orden de sincronización).

sincroniza-con es una condición más fuerte que sucede antes, y desde que ocurre antes es transitivo, si Tema A quiere Tema B para ver sus escrituras en x y y, sólo tiene que escribir en una variable volátil z después de escribir x y y. El hilo B debe leerse desde z antes de leer x y y y se garantizará que vea los nuevos valores de x y y.

En la solución de Gabriel, vemos este patrón: una escritura ocurre en in, que no sería visible para otros hilos, pero luego se produce una escritura en turn, por lo que otros hilos tienen garantizado ambas escrituras mientras lean turn primero.

Por desgracia, de condicional del bucle while es al revés: para garantizar un hilo no ve datos antiguos para in, el bucle while debe leer desde turn primera:

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

Con esta corrección en mente, la mayoría de las El resto de la solución está bien: en la sección crítica, no nos importa la falta de datos porque, bueno, ¡estamos en la sección crítica! El único otro defecto aparece al final: Runnable establece in[id] en un nuevo valor y sale. ¿Se garantizará que el otro Thread vea el nuevo valor de in[id]? La especificación dice no:

La acción final en un T1 hilo sincroniza-con cualquier acción en otro hilo T2 que detecta que T1 ha terminado. T2 puede lograr llamando a T1.isAlive() o T1.join().

Entonces, ¿cómo lo arreglamos? Sólo tiene que añadir otra escritura a turn al final del método:

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

Ya que reordenan el bucle while, se garantizará el otro hilo para ver el nuevo valor falso de in[id] debido a que la escritura a in[id] sucede-antes de la escriba a turn sucede antes de que se lea desde turn antes de la lectura desde in[id].

No hace falta decir que, sin una métrica ton de comentarios, este método es frágil y alguien podría venir y cambiar algo y romper sutilmente la corrección. Sólo se declara la matriz volatile no es lo suficientemente bueno: como se explica in this thread por Bill Pugh (uno de los lead researchers para el modelo de memoria de Java), que declara una matriz volatile hace cambios a la referencia gama visible para otros hilos. Las actualizaciones de los elementos de la matriz no son necesariamente visibles (de ahí todos los bucles que tuvimos que saltar usando otra variable volatile para proteger el acceso a los elementos de la matriz).

Si quiere que su código sea claro y conciso, consérvelo como está y cambie in para que sea AtomicIntegerArray (use 0 para falso, 1 para verdadero, no hay AtomicBooleanArray). Esta clase actúa como una matriz cuyos elementos son todos volatile, por lo que resolverá todos nuestros problemas muy bien.Alternativamente, puede declarar dos variables volátiles, boolean in0 y boolean in1, y actualizarlas en lugar de usar una matriz booleana.

Answer 2

no pude encontrar uno en la web a mí mismo, así que decidimos probar escribirlo:

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; 
    } 
} 

Siéntase libre de comentar, se apreciará :)

Answer 3

A menos que tenga alguna necesidad específica para el agoritmo de Peterson (lo que sería extraño cuando trabajas en un lenguaje de alto nivel como Java), te sugiero que eches un vistazo a las herramientas de sincronización integradas en el lenguaje.

Por ejemplo, se puede encontrar este capítulo de un libro sobre las "condiciones de carrera y Exclusión Mutua" en Java útiles: http://java.sun.com/developer/Books/performance2/chap3.pdf

En particlar:

Java proporciona soporte integrado espera de esta “ cambie en el estado "a través de la noción de una condición. Sin embargo, una condición es un nombre incorrecto, , ya que depende totalmente del usuario si se produjo o no una condición realmente . Además, una condición no necesita ser específicamente cierta o falsa. Para utilizar condiciones, hay que familiarizarse con tres métodos principales de la clase Object:

• wait(): Este método se utiliza a la espera de una condición. Se llama cuando una cerradura está actualmente retenida para un objeto particular (compartido) .

• notify(): Este método es utilizado para notificar un solo hilo que una condición ha (posiblemente) cambiado. De nuevo, se llama a este método cuando un bloqueo se mantiene actualmente para un objeto particular . Solo se puede activar una única secuencia como resultado de esta llamada.

• notifyAll(): Este método se utiliza para notificar a múltiples hilos que tiene una condición (posiblemente) cambiado. Todos los hilos que se ejecutan en el momento de llamar a este método se notificarán .

Answer 4

Debería echar un vistazo al libro The Art of Multiprocessor Programming. Él en gran detalle repasa diferentes implementaciones de bloqueo (tanto giro como bloqueo). También repasa otros tipos diferentes de algoritmos concurrentes (lista de omisiones, por ejemplo). Aquí hay un fragmento de su libro sobre el algoritmo de Peterson bloqueo

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

Si bien no es el paterson algo, las clases AtomicBoolean y Atomic * utilizan el enfoque de bucles bloqueados y ocupados para actualizar los datos compartidos. Pueden adaptarse a sus requisitos.