Mettre en œuvre Peterson Lock dans Java

Question

Je suis en train de mettre en œuvre Peterson's algorithm en Java, et ont créé ce qui suit pour le moment

public class Peterson { 
    private volatile boolean[] flag = new boolean[2]; 
    private volatile int victim; 

    public void lock(int id) 
    { 
     //System.out.println(id); 
     int i = id; 
     int j = 1 - id; 
     flag[i] = true; 
     victim = i; 
     while (flag[j] && victim == i) {}; 
    } 

    public void unlock(int id) 
    { 
     flag[id] = false; 
    } 
} 

Je suis le code suivant pour tester la serrure ...

class Counter { 
    private int value; 

    public Counter(int c) { 
     value = c; 
    } 

    public int get() 
    { 
     return value; 
    } 

    public int getAndIncrement() {  
     return value++; 
    } 
} 


class Thread1 implements Runnable { 
    private Counter c; 
    private int id; 
    private List<Integer> values; 
    private Peterson lock; 

    public Thread1(Counter c, int id, List<Integer> values, Peterson l) { 
     this.c = c; 
     this.id = id; 
     this.values = values; 
     this.lock = l; 
    } 

    public void run() { 

     while (true) 
     { 
      lock.lock(id); 
      try { 
       try { 

        if (c.get() > 20000) 
         return; 

        int n = c.getAndIncrement(); 
        values.add(n); 
       } catch (Exception e) { 
        e.printStackTrace(); 
       } 
      } 
      finally { 
       lock.unlock(id); 
      } 
     } 
    } 
} 

public class Tmp { 

    public static void main(String[] args) throws IOException { 

     Counter c = new Counter(1); 
     Thread[] t = new Thread[2]; 
     List<Integer> values = new ArrayList<Integer>(); 
     Peterson l = new Peterson(); 

     for (int i = 0; i < t.length; ++i) { 
      t[i] = new Thread(new Thread1(c, i, values, l)); 
      t[i].start(); 
     } 

     System.out.println(values.size()); 
    } 
} 

et même si je m'attends à System.out.println(values.size()); pour imprimer 20000 Il imprime sur chaque course des numéros différents. Pourquoi est-ce? Qu'ai-je fait de mal?

Answer 1

vous ne créez pas une barrière de mémoire lorsque vous déverrouillez de garantir l'arrive avant

ajouter un volatile boolean barr et d'écriture vrai dans déverrouiller et changer le tout dans la serrure à while (barr && flag[j] && victim == i) {};

que vous n'attendez pas sur les discussions que vous avez créé

for (int i = 0; i < t.length; ++i) { 
    t[i] = new Thread(new Thread1(c, i, values, l)); 
    t[i].start(); 
} 

for (int i = 0; i < t.length; ++i) { 
    try{ 
     t[i].join(); 
    }catch(InterruptedException e){ 
     Thread.currentThread().interrupt();//don't expect it but good practice to handle anyway 
    } 
} 

Answer 2

Je suppose que c'est parce que la méthode lock() dans la classe Lock n'est pas atomique. Plus précisément, ce code modifie deux adresses mémoire et vérifie ensuite l'état en utilisant les deux w/o verrouillage:

public void lock(int id) 
{ 
    ... 
    flag[i] = true; 
    victim = i; 
    while (flag[j] && victim == i) {}; 
} 

Est-ce que l'algorithme travail si deux threads entrelacer lors de l'exécution

flag[i] = true; 
    victim = i; 

En second lieu, parce que private volatile boolean[] flag = new boolean[2] marque la référence du tableau comme volatile, pas le contenu du tableau.

Answer 3

Comme les autres gars ont souligné, Java n'a pas de lecture/écriture volatile sur les éléments du tableau. Vous pouvez utiliser AtomicIntegerArray qui a get() et set() avec des effets volatiles.

Answer 4

Cela ne fonctionne pas parce que vous avez rendu la référence du tableau volatile, pas le contenu (comme déjà souligné). Mais vous pouvez toujours envelopper un champ volatile dans une classe et en faire un tableau.