Comment rendre mon thread de structure de données sûr?

Question

I définit une classe Element:

class Element<T> { 
    T value; 
    Element<T> next; 

    Element(T value) { 
     this.value = value; 
    } 
} 

également défini une classe de liste basée sur un élément. Il est une liste typique, comme dans tous les livres de structure de données, a addHead, supprimer et etc opérations

public class List<T> implements Iterable<T> { 
    private Element<T> head; 
    private Element<T> tail; 
    private long size; 

    public List() { 
     this.head = null; 
     this.tail = null; 
     this.size = 0; 
    } 

    public void insertHead (T node) { 
     Element<T> e = new Element<T>(node); 
     if (size == 0) { 
      head = e; 
      tail = e; 
     } else { 
      e.next = head; 
      head = e; 
     } 
     size++;  
    } 

    //Other method code omitted 
} 

Comment puis-je faire ce fil de classe Liste sûre?

mettre synchronisé sur toutes les méthodes? Ça ne marche pas. Deux threads peuvent travailler sur des méthodes différentes en même temps et provoquer une collision.

Si j'ai utilisé un tableau pour conserver tous les éléments de la classe, alors je peux utiliser un volatile sur le tableau pour m'assurer qu'un seul thread travaille avec les éléments internes. Mais actuellement tous les éléments sont liés par l'objet refernece sur le prochain pointeur. Je n'ai aucun moyen d'utiliser volatile.

Utilisation de matières volatiles sur la tête, la queue et la taille? Cela peut provoquer des interblocages si deux threads exécutent des méthodes différentes en attente de la ressource.

Des suggestions?

Answer 1

Je regarderais le code source de la classe java.util.LinkedList pour une implémentation réelle.

Synchronisé par défaut verrouille sur l'instance de la classe - ce qui peut ne pas être ce que vous voulez. (surtout si Element est accessible de l'extérieur). Si vous synchronisez toutes les méthodes sur le même verrou, vous aurez des performances concurrentes terribles, mais cela les empêchera d'exécuter en même temps - efficacement un seul thread d'accès à la classe.

Également - je vois une référence arrière, mais ne vois pas l'élément avec un champ précédent correspondant, pour une double liste-liée - raison?

Answer 2

Je vous suggère d'utiliser un ReentrantLock que vous pouvez passer à tous les éléments de la liste, mais vous devrez utiliser une fabrique pour instancier chaque élément.

Chaque fois que vous avez besoin de retirer quelque chose de la liste, vous bloquez le même verrou, ce qui vous assure que deux threads n'accèderont pas en même temps.

Answer 3

Si vous mettez synchronized sur chaque méthode, la structure de données sera thread-safe. Parce que par définition, un seul thread exécutera n'importe quelle méthode sur l'objet à la fois, et l'ordre inter-thread et la visibilité sont également assurés. Donc, c'est aussi bon que si un thread fait toutes les opérations.

La mise en place d'un bloc synchronized(this) ne sera pas différente si la zone couverte par le bloc correspond à l'ensemble de la méthode. Vous pourriez obtenir de meilleures performances si la zone est plus petite que cela.

Faire quelque chose comme

private final Object LOCK = new Object(); 

public void method(){ 
    synchronized(LOCK){ 
     doStuff(); 
    } 
} 

est considérée comme bonne pratique, mais pas pour de meilleures performances. Faire cela fera en sorte que personne ne peut utiliser votre serrure, et sans le vouloir créer une mise en œuvre sujettes à une impasse, etc.

Dans votre cas, je pense que vous pouvez utiliser ReadWriteLock pour mieux les performances de lecture.Comme son nom l'indique, un ReadWriteLock laisse passer plusieurs threads s'ils accèdent à la "méthode de lecture", méthodes qui ne modifient pas l'état de l'objet (bien sûr, vous devez identifier correctement les méthodes "read method" et "write méthode ", et utiliser ReadWriteLock en conséquence!). En outre, il s'assure qu'aucun autre thread n'accède à l'objet pendant que "write method" est exécuté. Et il prend en charge la planification des threads en lecture/écriture.

Autre façon bien connue de créer une classe de thread-safe est "CopyOnWrite", où vous copiez la structure de données entière lors d'une mutation. Ceci n'est recommandé que lorsque l'objet est principalement "lu" et rarement "écrit".

Voici un exemple d'implémentation de cette stratégie. http://www.codase.com/search/smart?join=class+java.util.concurrent.CopyOnWriteArrayList

private volatile transient E[] array; 

/** 
* Returns the element at the specified position in this list. 
* 
* @param index index of element to return. 
* @return the element at the specified position in this list. 
* @throws IndexOutOfBoundsException if index is out of range <tt>(index 
*   < 0 || index >= size())</tt>. 
*/ 
public E get(int index) { 
    E[] elementData = array(); 
    rangeCheck(index, elementData.length); 
    return elementData[index]; 
} 
/** 
* Appends the specified element to the end of this list. 
* 
* @param element element to be appended to this list. 
* @return true (as per the general contract of Collection.add). 
*/ 
public synchronized boolean add(E element) { 
    int len = array.length; 
    E[] newArray = (E[]) new Object[len+1]; 
    System.arraycopy(array, 0, newArray, 0, len); 
    newArray[len] = element; 
    array = newArray; 
    return true; 
} 

Ici, lisez méthode accède sans passer par une serrure, tandis que la méthode d'écriture doit être synchronized. L'ordre inter-thread et la visibilité pour les méthodes de lecture sont assurés par l'utilisation de volatile pour le tableau. La raison pour laquelle les méthodes d'écriture doivent "copier" est que l'affectation array = newArray doit être "one shot" (en java, l'affectation de la référence d'objet est atomique), et vous ne pouvez pas toucher le tableau original pendant la manipulation.