Possible de créer AtomicReference qui peut être permuté atomiquement?

Question

Y a-t-il un moyen d'implémenter un type de référence dont la valeur peut être échangée avec une autre atomiquement?

---

En Java, nous avons AtomicReference qui peut être échangé avec une variable locale, mais pas avec un autre AtomicReference.

Vous pouvez faire:

AtomicReference r1 = new AtomicReference("hello"); 
AtomicReference r2 = new AtomicReference("world"); 

et de les échanger avec une combinaison de deux opérations:

r1.set(r2.getAndSet(r1.get())); 

Mais ce qui les laisse dans un état incohérent entre, où les deux contiennent "hello". Même si vous pouviez les échanger atomiquement, vous ne pouviez toujours pas les lire (en paire) de façon atomique.

---

Ce que je voudrais être en mesure de faire est:

PairableAtomicReference r1 = new PairableAtomicReference("hello"); 
PairableAtomicReference r2 = new PairableAtomicReference("world"); 
AtomicRefPair rp = new AtomicRefPair(r1, r2); 

puis

Object[] oldVal, newVal; 
do { 
    oldVal = rp.get(); 
    newVal = new Object[] {oldVal[1], oldVal[0]}; 
} while (! rp.compareAndSet(oldVal, newVal)); 

pour échanger les valeurs, et dans un autre thread:

AtomicRefPair otherRP = new AtomicRefPair(r1, r2); 
System.out.println(Arrays.toString(otherRP.get())); 

et soyez certain que la sortie sera soit [hello, world] ou [world, hello].

Notes:

• r1 et r2 sont appairés pour cette opération, mais il est possible qu'un autre thread indépendamment paire, disent r1 et un autre r3
• Il (malheureusement, cela signifie que je ne peux pas utiliser this solution.) sera des centaines de milliers de ces références, donc un ReentrantLock serait un goulot d'étranglement majeur.
• rp et otherRP ne sont pas nécessairement partagés entre les threads, donc simplement les verrouiller ne fonctionnera pas. Ils pourraient être interned, mais le pool interne aurait besoin de sa propre synchronisation, ce qui serait un autre goulot d'étranglement.
• J'ai seulement fait des groupes de 2 références ici, mais la possibilité de grouper 3 ou plus serait un bonus.

Est-il possible d'implémenter une version sans verrou de AtomicRefPair? J'ai l'intuition que ce n'est pas le cas, mais sinon, peut-être qu'il y a un article quelque part qui explique pourquoi?

---

connexes: How do I atomically swap 2 ints in C#?

Answer 1

Je ne sais pas s'il y a une bonne solution, mais laide suivante pourrait fonctionner:

public final class MyReference<T> extends ReentrantLock implements Comparable<MyReference<T>> { 
    public MyReference() { 
     id = counter.incrementAndGet(); 
    } 

    public void swap(MyReference<T> other) { 
     if (id < other.id) { 
      lock(); 
      other.lock(); 
     } else { 
      other.lock(); 
      lock(); 
     } 
     final T tmp = value; 
     value = other.value; 
     other.value = tmp; 
     unlock(); 
     other.unlock(); 
    } 

    public static <T> List<T> consistentGet(List<MyReference<T>> references) { 
     final ArrayList<MyReference<T>> sortedReferences = Lists.newArrayList(references); 
     Collections.sort(sortedReferences); 
     for (val r : sortedReferences) r.lock(); 
     final List<T> result = Lists.newArrayListWithExpectedSize(sortedReferences.size()); 
     for (val r : references) result.add(r.value); 
     for (val r : sortedReferences) r.unlock(); 
     return result; 
    } 

    @Override 
    public int compareTo(MyReference<T> o) { 
     return id < o.id ? -1 : id > o.id ? 1 : 0; 
    } 

    private final static AtomicInteger counter = new AtomicInteger(); 

    private T value; 
    private final int id; 
} 

• Utilisation MyReference au lieu de AtomicReference.
• Il utilise beaucoup de verrous, mais aucun d'eux n'est global.
• Il acquiert des verrous dans un ordre fixe, donc il est sans interblocage.
• Il compile en utilisant lombok et goyave (le prendre comme pseudocode sans eux).

Answer 2

Avoir une classe immuable contenant la paire. C'est ton atome. Échanger la paire signifie remplacer l'atome.

mise à jour: votre question n'est pas très claire. mais en général, pour un système concurrent composé de plusieurs variables, on peut vouloir

1. prendre un instantané de l'état du système. l'instantané ne change pas une fois pris.
2. mettre à jour atomiquement l'état du système en changeant plusieurs variables à la fois. il peut être nécessaire qu'il n'y ait aucune autre mise à jour entre ma mise à jour et un instantané précédent (sur lequel mon calcul était basé)

Vous pouvez modéliser votre système directement dans les instantanés, s'il ne consomme pas trop de ressources.