Utilisation de threads avec des collections, partie 1

Les threads font partie intégrante du langage Java. En utilisant des threads, de nombreux algorithmes, tels que les systèmes de gestion de files d'attente, sont plus faciles d'accès qu'ils n'utilisent des techniques d'interrogation et de bouclage. Récemment, lors de l'écriture d'une classe Java, j'ai découvert que je devais utiliser des threads lors de l'énumération des listes, ce qui a révélé des problèmes intéressants associés aux collections prenant en charge les threads.

Cette colonne Java In Depth décrit les problèmes que j'ai découverts lors de ma tentative de développement d'une collection thread-safe. Une collection est appelée «thread-safe» lorsqu'elle peut être utilisée en toute sécurité par plusieurs clients (threads) en même temps. "Donc quel est le problème?" tu demandes. Le problème est que, dans l'utilisation typique, un programme modifie à la fois une collection (appelée mutation ) et la lit (appelée énumération ).

Certaines personnes n'enregistrent tout simplement pas l'instruction "La plate-forme Java est multithread". Bien sûr, ils l'entendent et ils hochent la tête. Mais ils ne comprennent pas que, contrairement au C ou au C ++, dans lequel le threading était boulonné du côté du système d'exploitation, les threads en Java sont des constructions de langage de base. Ce malentendu, ou mauvaise compréhension, de la nature intrinsèquement threadée de Java, conduit inévitablement à deux défauts communs dans le code Java des programmeurs: Soit ils ne déclarent pas une méthode comme synchronisée qui devrait l'être (car l'objet est dans un état incohérent pendant la méthode) ou ils déclarent une méthode comme synchronisée afin de la protéger, ce qui entraîne un fonctionnement inefficace du reste du système.

Je suis tombé sur ce problème lorsque je voulais une collection que plusieurs threads pourraient utiliser sans bloquer inutilement l'exécution des autres threads. Aucune des classes de collection de la version 1.1 du JDK n'est thread-safe. Plus précisément, aucune des classes de collection ne vous permettra d'énumérer avec un thread tout en mutant avec un autre.

Collections non thread-safe

Mon problème de base était le suivant: en supposant que vous ayez une collection ordonnée d'objets, concevez une classe Java de telle sorte qu'un thread puisse énumérer tout ou partie de la collection sans craindre que l'énumération ne devienne invalide en raison d'autres threads qui modifient la collection. Comme exemple du problème, considérons la Vectorclasse de Java . Cette classe n'est pas thread-safe et pose de nombreux problèmes aux nouveaux programmeurs Java lorsqu'ils la combinent avec un programme multithread.

La Vectorclasse fournit une fonctionnalité très utile pour les programmeurs Java: à savoir, un tableau d'objets de taille dynamique. En pratique, vous pouvez utiliser cette fonction pour stocker des résultats où le nombre final d'objets que vous allez traiter n'est pas connu tant que vous n'en avez pas terminé avec eux tous. J'ai construit l'exemple suivant pour illustrer ce concept.

01 import java.util.Vector; 02 import java.util.Enumeration; 03 public class Demo {04 public static void main (String args []) {05 Vector digits = new Vector (); 06 résultat int = 0; 07 08 if (args.length == 0) {09 System.out.println ("Usage is java demo 12345"); 10 System.exit (1); 11} 12 13 pour (int i = 0; i = '0') && (c <= '9')) 16 digits.addElement (new Integer (c - '0')); 17 sinon 18 pause; 19} 20 System.out.println ("Il y a" + digits.size () + "chiffres."); 21 for (Enumeration e = digits.elements (); e.hasMoreElements ();) {22 result = result * 10 + ((Integer) e.nextElement ()). IntValue (); 23} 24 System.out.println (args [0] + "=" + résultat); 25 System.exit (0); 26} 27}

La classe simple ci-dessus utilise un Vectorobjet pour collecter les caractères numériques d'une chaîne. La collection est ensuite énumérée pour calculer la valeur entière de la chaîne. Il n'y a rien de mal avec cette classe, sauf qu'elle n'est pas thread-safe. Si un autre thread contenait une référence au vecteur de chiffres et que ce thread insérait un nouveau caractère dans le vecteur, les résultats de la boucle des lignes 21 à 23 ci-dessus seraient imprévisibles. Si l'insertion a eu lieu avant que l'objet d'énumération n'ait dépassé le point d'insertion, le résultat du calcul du thread traiterait le nouveau caractère. Si l'insertion s'est produite après que l'énumération a passé le point d'insertion, la boucle ne traitera pas le caractère. Le pire des cas est que la boucle peut lancer unNoSuchElementException si la liste interne a été compromise.

Cet exemple n'est que cela - un exemple artificiel. Cela démontre le problème, mais quelle est la chance qu'un autre thread s'exécute pendant une courte énumération à cinq ou six chiffres? Dans cet exemple, le risque est faible. Le laps de temps qui s'écoule lorsqu'un thread démarre une opération à risque, qui dans cet exemple est l'énumération, puis termine la tâche est appelé fenêtre de vulnérabilité ou fenêtre du thread . Cette fenêtre particulière est connue comme une condition de concurrencecar un thread est "en course" pour terminer sa tâche avant qu'un autre thread n'utilise la ressource critique (la liste des chiffres). Cependant, lorsque vous commencez à utiliser des collections pour représenter un groupe de plusieurs milliers d'éléments, comme avec une base de données, la fenêtre de vulnérabilité augmente car le thread énumérant passera beaucoup plus de temps dans sa boucle d'énumération, ce qui rend la chance d'un autre thread en cours d'exécution bien plus haut. Vous ne voulez certainement pas qu'un autre thread change la liste en dessous de vous! Ce que vous voulez, c'est l'assurance que l' Enumerationobjet que vous tenez est valide.

Une façon d'examiner ce problème est de noter que l' Enumerationobjet est séparé de l' Vectorobjet. Parce qu'ils sont séparés, ils sont incapables de garder le contrôle les uns sur les autres une fois qu'ils sont créés. Cette reliure lâche m'a suggéré que peut-être un chemin utile à explorer était une énumération qui était plus étroitement liée à la collection qui l'a produite.

Créer des collections

Pour créer ma collection thread-safe, j'avais d'abord besoin d'une collection. Dans mon cas, une collection triée était nécessaire, mais je n'ai pas pris la peine de suivre l'itinéraire complet de l'arbre binaire. Au lieu de cela, j'ai créé une collection que j'ai appelée SynchroList . Ce mois-ci, je vais examiner les éléments de base de la collection SynchroList et décrire comment l'utiliser. Le mois prochain, dans la partie 2, je prendrai la collection d'une classe Java simple et facile à comprendre à une classe Java multithread complexe. Mon objectif est de garder la conception et la mise en œuvre d'une collection distincte et compréhensible par rapport aux techniques utilisées pour la rendre sensible aux threads.

J'ai nommé ma classe SynchroList. Le nom «SynchroList», bien sûr, vient de la concaténation de «synchronisation» et «liste». La collection est simplement une liste à double lien, comme vous pourriez trouver dans n'importe quel manuel universitaire sur la programmation, bien que grâce à l'utilisation d'une classe interne nommée Link, une certaine élégance puisse être atteinte. La classe interne Linkest définie comme suit:

class Link {données d'objets privés; lien privé nxt, prv; Lien (objet o, lien p, lien n) {nxt = n; prv = p; données = o; if (n! = null) n.prv = this; if (p! = null) p.nxt = this; } Object getData () {données de retour; } Lien suivant () {return nxt; } Lien suivant (Link newNext) {Link r = nxt; nxt = nouveauSuivant; return r;} Link prev () {return prv; } Link prev (Link newPrev) {Link r = prv; prv = newPrev; return r;} chaîne publique toString () {return "Link (" + data + ")"; }}

Comme vous pouvez le voir dans le code ci-dessus, un Linkobjet encapsule le comportement de liaison que la liste utilisera pour organiser ses objets. Pour implémenter le comportement de liste à double lien, l'objet contient des références à son objet de données, une référence au lien suivant dans la chaîne et une référence au lien précédent dans la chaîne. En outre, les méthodes nextet prevsont surchargées pour fournir un moyen de mettre à jour le pointeur de l'objet. Cela est nécessaire car la classe parente devra insérer et supprimer des liens dans la liste. Le constructeur de lien est conçu pour créer et insérer un lien en même temps. Cela enregistre un appel de méthode dans l'implémentation de la liste.

Une autre classe interne est utilisée dans la liste - dans ce cas, une classe d'énumérateur nommée ListEnumerator. Cette classe implémente l' java.util.Enumerationinterface: le mécanisme standard que Java utilise pour itérer sur une collection d'objets. En demandant à notre énumérateur d'implémenter cette interface, notre collection sera compatible avec toutes les autres classes Java qui utilisent cette interface pour énumérer le contenu d'une collection. L'implémentation de cette classe est indiquée dans le code ci-dessous.

la classe LinkEnumerator implémente l'énumération {lien privé actuel, précédent; LinkEnumerator () {current = head; } public boolean hasMoreElements () {return (current! = null); } Objet public nextElement () {Résultat d'objet = null; Link tmp; if (current! = null) {result = current.getData (); courant = courant.next (); } retourne le résultat; }}

Dans son incarnation actuelle, la LinkEnumeratorclasse est assez simple; cela deviendra plus compliqué à mesure que nous le modifierons. Dans cette incarnation, il parcourt simplement la liste de l'objet appelant jusqu'à ce qu'il arrive au dernier lien dans la liste chaînée interne. Les deux méthodes requises pour implémenter l' java.util.Enumerationinterface sont hasMoreElementset nextElement.

Bien sûr, l'une des raisons pour lesquelles nous n'utilisons pas la java.util.Vectorclasse est que j'avais besoin de trier les valeurs de la collection. Nous avions le choix: construire cette collection pour être spécifique à un type d'objet particulier, utilisant ainsi cette connaissance intime du type d'objet pour le trier, ou créer une solution plus générique basée sur des interfaces. J'ai choisi cette dernière méthode et défini une interface nommée Comparatorpour encapsuler les méthodes nécessaires pour trier les objets. Cette interface est illustrée ci-dessous.

Comparateur d'interface publique {booléen public lessThan (objet a, objet b); public boolean greaterThan (objet a, objet b); public boolean equalTo (objet a, objet b); void typeCheck (objet a); }

Comme vous pouvez le voir dans le code ci-dessus, l' Comparatorinterface est assez simple. L'interface nécessite une méthode pour chacune des trois opérations de comparaison de base. À l'aide de cette interface, la liste peut comparer les objets ajoutés ou supprimés avec des objets déjà présents dans la liste. La méthode finale,, typeCheckest utilisée pour assurer la sécurité de type de la collection. Lorsque l' Comparatorobjet est utilisé, le Comparatorpeut être utilisé pour garantir que les objets de la collection sont tous du même type. L'intérêt de cette vérification de type est qu'elle vous évite de voir les exceptions de conversion d'objet si l'objet de la liste n'était pas du type attendu. J'ai un exemple plus tard qui utilise a Comparator, mais avant d'en arriver à l'exemple, regardons SynchroListdirectement la classe.

public class SynchroList {class Link {... cela a été montré ci-dessus ...} class LinkEnumerator implémente Enumeration {... the enumerator class ...} / * Un objet pour comparer nos éléments * / Comparator cmp; Lien tête, queue; public SynchroList () {} public SynchroList (Comparateur c) {cmp = c; } private void before (Object o, Link p) {new Link (o, p.prev (), p); } vide privé après (Object o, Link p) {new Link (o, p, p.next ()); } private void remove (Lien p) {if (p.prev () == null) {head = p.next (); (p.next ()). prev (null); } else if (p.next () == null) {tail = p.prev (); (p.prev ()). suivant (nul); } else {p.prev (). next (p.next ()); p.next (). prev (p.prev ()); }} public void add (Object o) {// si cmp est nul, toujours ajouter à la fin de la liste. if (cmp == null) {if (head == null) {head = new Link (o, null, null); queue = tête; } else {tail = new Link (o, tail,nul); } revenir; } cmp.typeCheck (o); if (head == null) {head = new Link (o, null, null); queue = tête; } else if (cmp.lessThan (o, head.getData ())) {head = new Link (o, null, head); } else {Lien l; for (l = head; l.next ()! = null; l = l.next ()) {if (cmp.lessThan (o, l.getData ())) {before (o, l); revenir; }} queue = nouveau lien (o, queue, null); } revenir; } public boolean delete (Object o) {if (cmp == null) return false; cmp.typeCheck (o); for (Link l = head; l! = null; l = l.next ()) {if (cmp.equalTo (o, l.getData ())) {remove (l); retourne vrai; } if (cmp.lessThan (o, l.getData ())) break; } return false; } éléments publics synchronized Enumeration () {return new LinkEnumerator (); } public int size () {int result = 0; for (Link l = head; l! = null; l = l.next ()) result ++; résultat de retour; }}if (head == null) {head = new Link (o, null, null); queue = tête; } else if (cmp.lessThan (o, head.getData ())) {head = new Link (o, null, head); } else {Lien l; for (l = head; l.next ()! = null; l = l.next ()) {if (cmp.lessThan (o, l.getData ())) {before (o, l); revenir; }} queue = nouveau lien (o, queue, null); } revenir; } public boolean delete (Object o) {if (cmp == null) return false; cmp.typeCheck (o); for (Link l = head; l! = null; l = l.next ()) {if (cmp.equalTo (o, l.getData ())) {remove (l); retourne vrai; } if (cmp.lessThan (o, l.getData ())) break; } return false; } éléments publics synchronized Enumeration () {return new LinkEnumerator (); } public int size () {int result = 0; for (Link l = head; l! = null; l = l.next ()) result ++; résultat de retour; }}if (head == null) {head = new Link (o, null, null); queue = tête; } else if (cmp.lessThan (o, head.getData ())) {head = new Link (o, null, head); } else {Lien l; for (l = head; l.next ()! = null; l = l.next ()) {if (cmp.lessThan (o, l.getData ())) {before (o, l); revenir; }} queue = nouveau lien (o, queue, null); } revenir; } public boolean delete (Object o) {if (cmp == null) return false; cmp.typeCheck (o); for (Link l = head; l! = null; l = l.next ()) {if (cmp.equalTo (o, l.getData ())) {remove (l); retourne vrai; } if (cmp.lessThan (o, l.getData ())) break; } return false; } éléments publics synchronized Enumeration () {return new LinkEnumerator (); } public int size () {int result = 0; for (Link l = head; l! = null; l = l.next ()) result ++; résultat de retour; }}} else {Lien l; for (l = head; l.next ()! = null; l = l.next ()) {if (cmp.lessThan (o, l.getData ())) {before (o, l); revenir; }} queue = nouveau lien (o, queue, null); } revenir; } public boolean delete (Object o) {if (cmp == null) return false; cmp.typeCheck (o); for (Link l = head; l! = null; l = l.next ()) {if (cmp.equalTo (o, l.getData ())) {remove (l); retourne vrai; } if (cmp.lessThan (o, l.getData ())) break; } return false; } éléments publics synchronized Enumeration () {return new LinkEnumerator (); } public int size () {int result = 0; for (Link l = head; l! = null; l = l.next ()) result ++; résultat de retour; }}} else {Lien l; for (l = head; l.next ()! = null; l = l.next ()) {if (cmp.lessThan (o, l.getData ())) {before (o, l); revenir; }} queue = nouveau lien (o, queue, null); } revenir; } public boolean delete (Object o) {if (cmp == null) return false; cmp.typeCheck (o); for (Link l = head; l! = null; l = l.next ()) {if (cmp.equalTo (o, l.getData ())) {remove (l); retourne vrai; } if (cmp.lessThan (o, l.getData ())) break; } return false; } éléments publics synchronized Enumeration () {return new LinkEnumerator (); } public int size () {int result = 0; for (Link l = head; l! = null; l = l.next ()) result ++; résultat de retour; }}typeCheck (o); for (Link l = head; l! = null; l = l.next ()) {if (cmp.equalTo (o, l.getData ())) {remove (l); retourne vrai; } if (cmp.lessThan (o, l.getData ())) break; } return false; } éléments publics synchronized Enumeration () {return new LinkEnumerator (); } public int size () {int result = 0; for (Link l = head; l! = null; l = l.next ()) result ++; résultat de retour; }}typeCheck (o); for (Link l = head; l! = null; l = l.next ()) {if (cmp.equalTo (o, l.getData ())) {remove (l); retourne vrai; } if (cmp.lessThan (o, l.getData ())) break; } return false; } éléments d'énumération synchronisés publics () {return new LinkEnumerator (); } public int size () {int result = 0; for (Link l = head; l! = null; l = l.next ()) result ++; résultat de retour; }}