Peterson algorithme en Java?

Personne ici n'a fourni une correcte et sûre de la mise en œuvre de cet algorithme en Java. Je ne suis pas sûr de savoir comment John W la solution est censé marcher, car il a des pièces manquantes (à savoir les déclarations de la ThreadLocals et une explication de ce qui est censé être dans son tableau de primitif booleans n'ont pas get() et set()).

Le chapitre 17 de la Spécification du Langage Java explique la Java du modèle de mémoire. D'intérêt particulier est Section 17.4.5, qui décrit la se passe-avant commande. Il est assez facile de penser dans un seul thread. Considérons l'extrait de code:

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

z = x;
w = y;

Tout le monde sera d'accord qu'à la fin de cet extrait, les deux x et z sont égales à 0 et les deux y et w sont égales à 5. Ignorant les déclarations, nous avons six actions ici:

1. D'une écriture x
2. D'une écriture y
3. Une lecture de la x
4. D'une écriture z
5. Une lecture de la y
6. D'une écriture w

Parce qu'ils apparaissent tous dans le même thread, JL dit que ces lectures et écritures sont garantis à exposer cette commande: chaque action n ci-dessus (parce que les actions sont dans un seul thread) est un passe-avant relation avec toutes les actions m, m > n.

Mais ce sur les différents threads? Pour champ normal d'accès, il n'y a aucun passe-avant les relations établies entre les threads. Cela signifie qu'un Thread peut incrémenter une variable partagée et le Fil B peut lire que variable, mais de ne pas voir la nouvelle valeur. Dans l'exécution du programme dans la JVM, la propagation de Fil d'Une écriture peut avoir été réorganisées à se produire après que le Thread B lire.

En fait, le Thread A pu écrire dans une variable x, puis à une variable y, l'établissement d'un passe-avant la relation entre ces deux actions, au sein de Filetage A. Mais le Fil B peut lire x et y et il est légal pour B pour obtenir la nouvelle valeur de y avant la nouvelle valeur de x s'affiche. La spécification dit:

Plus précisément, si deux actions
partager un passe-avant la relation,
ils ne doivent pas nécessairement apparaître
qui est arrivé dans cet ordre à tout
code avec qui ils ne partagent pas une
-passe-avant la relation.

Comment pouvons-nous résoudre ce problème? Pour le champ normal accède, l' volatile mot-clé est assez:

Une écriture d'une variable volatile
(§8.3.1.4) v synchronise avec tous les
les lectures suivantes de v par n'importe quel thread
(où subséquente est définie en fonction
à l'ordre de synchronisation).

synchronise avec est une condition plus forte que se passe-avant, et depuis que se passe-avant est transitive, si Un Thread veut Thread B pour voir sa écrit à x et y, il a juste besoin d'écrire dans une variable volatile z après avoir écrit x et y. Le fil B à lire à partir de z avant de lire x et y et il sera assuré de voir les nouvelles valeurs de x et y.

Gabriel solution, nous voyons ce modèle: une écriture se produit à in, qui ne serait pas visible pour les autres threads, mais alors une écriture se produit à turn, de sorte que les autres threads sont garantis à voir à la fois écrit, aussi longtemps qu'ils lire turn premier.

Malheureusement, le tout en boucle conditionnelle est à l'envers: pour garantir un thread ne voit pas de données obsolètes pour in, la boucle while devrait se lire de turn première:

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

Avec ce correctif à l'esprit, la plupart du reste de la solution est ok: dans la section critique, nous ne nous soucions pas de caducité de données parce que, eh bien, nous sommes dans la section critique! Le seul autre défaut vient à la fin: l'Exécutable jeux de in[id] une nouvelle valeur, et les sorties. Les autres Thread être assuré de voir la nouvelle valeur de in[id]? La spécification dit pas:

L'action finale dans un thread T1
synchronise avec toute action en
un autre thread T2 qui détecte que T1
a mis fin. T2 peut accomplir
cela en appelant T1.isAlive() ou
T1.join().

Alors, comment pouvons-nous résoudre ce problème? Juste ajouter une autre écriture de turn à la fin de la méthode:

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

Depuis nous avons réorganisé le tout en boucle, l'autre thread sera assuré de voir la nouvelle valeur fausse de in[id] parce que l'écriture de in[id] se passe-avant de l'écrire à turn se passe-avant de le lire à partir de turn se passe-avant de le lire à partir de in[id].

Inutile de dire que, sans une métrique tonne de commentaires, cette méthode est fragile et si quelqu'un pourrait venir le long et changer quelque chose et subtilement briser l'exactitude. Juste de la déclaration du tableau volatile n'est pas assez bon: comme expliqué dans ce fil par le projet de Loi Pugh (l'un des chercheurs pour le Java modèle de mémoire), déclaration d'un tableau volatile met à jour le tableau référence visible pour les autres threads. Les mises à jour des éléments du tableau ne sont pas nécessairement visibles (donc, toutes les boucles que nous avons juste eu à passer à travers en utilisant un autre volatile variable à la garde de l'accès aux éléments du tableau).

Si vous voulez que votre code d'être clair et concis, gardez-le comme il est et le changement in être un AtomicIntegerArray (utilisez 0 pour false, 1 pour vrai; il n'y a pas de AtomicBooleanArray). Cette classe se comporte comme un tableau dont les éléments sont tous volatile, et permettra de résoudre tous nos problèmes bien. Alternativement, vous pouvez simplement déclarer deux variables, boolean in0 et boolean in1, et de les mettre à jour au lieu d'utiliser un booléen tableau.

Je ne pouvais pas en trouver un sur le web, moi-même, j'ai donc décidé d'essayer de l'écrire:

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

N'hésitez pas à commenter, il sera apprécié:)

Alors que les paterson algo, le AtomicBoolean et Atomique* classes utilisent l'approche de lockless, occupé les boucles de mise à jour de données partagée. Ils peuvent répondre à vos exigences.