6. Collections synchronisées et concurrentes

6.1. Introduction

Les problèmes de concurrence d'accès ne se pose pas que pour les champs de type primitif ou objet. Ils se posent de façon également aiguë lorsque l'on manipule des collections et des tables de hachage. C'est la raison pour laquelle l'API Concurrent propose plusieurs implémentations de List, de Set et de Map, à la fois thread-safe et performantes.

6.2. Position du problème

L'API Java nous offre déjà quelques solutions pour construire des collections thread-safe . Les classes Vector et Hashtable sont synchronisées, et la classe Collections expose plusieurs méthodes pour créer des collections synchronisées, par enveloppement de ces collections et synchronisation des accès. Malheureusement ces classes ne sont pas suffisantes pour traiter de façon atomique des problèmes simples.

6.2.1. Concurrence d'accès sur une table de hachage

Considérons le simple code suivant.

Exemple 72. Concurrence sur une table de hachage

public  class ConcurrentAccessMap {

    // création d'une map classique
    private Map<String, Marin> map =  new HashMap<String, Marin>() ;
   
    public  boolean addIfAbsent(Marin m) {

       // on ajoute notre marin que s'il ne s'y trouve pas déjà
       if (!map.keySet().contains(m.getNom())) {
      
         map.put(m.getNom(), m) ;
          return true ;
      }

       return false ;
   }
}

Cette implémentation ne fonctionne pas en concurrence d'accès, et changer notre implémentation, ici HashMap en Hashtable ne changerait rien à l'affaire. Si l'on applique les mêmes principes d'analyse que dans les paragraphes précédents, on se rend compte que deux thread différents peuvent se trouver en même temps dans le bloc du if(...), portant deux marins de même nom. Ces deux marins seront donc ajoutés, l'un après l'autre, ce que l'on veut précisément éviter. On pourrait synchroniser la méthode addIfAbsent(), et cela résoudrait le problème. L'API Concurrent nous offre une autre solution, comme nous allons le voir.

6.2.2. Concurrence d'accès sur une collection

Prenons un autre exemple, cette fois sur une collection.

Exemple 73. Concurrence sur une collection

public  class ConcurrentAccessCollection {

    // création d'une liste classique
    private List<Marin> liste =  new ArrayList<Marin>() ;
   
    public Marin getLastMarin() {
      
       // on détermine l'index du dernier élément
       int lastIndex = liste.length() -  1 ;
       return liste.get(lastIndex) ;
   }
   
    public  boolean remove(Marin marin) {
      
       return liste.remove(marin) ;
   }
}

De même, on constate après analyse que cette classe n'est pas thread-safe . Si un premier thread appelle getLastMarin(), et est interrompu entre le moment où il calcule lastIndex et le moment où il lit effectivement ce dernier marin, alors qu'un autre retire un marin de la liste, par la méthode remove(Marin m), alors une erreur sera générée, puisque la valeur de lastIndex sera trop grande. Encore une fois, synchroniser le tout résoudrait le problème, mais l'API Concurrent permet de mieux faire.
Synchroniser une collection ou une table, comme c'est le cas pour Vector et Hashtable n'apporte pas toujours de solution satisfaisante, voire pas de solution du tout. Une collection utilisée en concurrence d'accès peut poser des problèmes, même si tous ses accès sont synchronisés. Comme nous l'avons déjà vu, itérer sur une collection alors qu'une autre partie de l'application ajoute des éléments dedans peut mener à une ConcurrentModificationException. Or, quelques méthodes peuvent itèrer en interne, sans exposer explicitement ce comportement. C'est le cas de hashCode(), et des méthodes du type addAll(), containsAll(), removeAll() ou retainAll(). Dans tous ces cas, la synchronisation n'est pas suffisante, on a besoin d'un mécanisme différent, qui nous garantisse le fonctionnement dans tous les cas possibles de la concurrence d'accès.

6.3. Solutions proposées

L'API Concurrent propose de nouvelles implémentations de quelques interfaces de l'API Collection, qui enrichissent ces interfaces de quelques méthodes, et apportent des solutions complètes aux problèmes que nous venons de présenter. On ne parle pas de collections synchronisées pour ces nouvelles interfaces et classes, mais plutôt de collections concurrentes. Ces collections concurrentes sont utilisées pour résoudre les problèmes de forte concurrence d'accès, sans sacrifier aux pertes de performances que peut entraîner la synchronisation à outrance.

6.3.1. Collections concurrentes

Deux classes sont apportées par l'API Concurrent, implémentation respectivement de List et de Set : CopyOnWriteArrayList et CopyOnWriteArraySet. L'implémentation CopyOnWriteArrayList apporte deux opérations supplémentaires à List, qui sont atomiques : addItAbsent(T t) et addAllAbstent(Collection<? extends E> collection). Ces deux classes peuvent être utilisées en concurrence d'accès. On peut itérer dessus sans risque qu'une exception de type ConcurrentModificationException soit jetée. Ces deux collections sont construites sur des tableaux d'objets, qui sont recopiés intégralement à chaque fois qu'une modification est effectuée. Seul le changement de tableau (qui n'est qu'un jeu de pointeurs) est synchronisé. Toutes les opérations de lecture sont effectuées sur un unique tableau, en lecture seule, qui ne pose donc aucun problème de modification concurrente. Ces deux classes ne sont donc pas utilisables dans tous les cas. Les lectures sont très performantes, mais les écritures très peu performantes. Les bons cas sont donc ceux dans lesquels les lectures sont beaucoup plus fréquentes que les modifications, et pour les collections qui ne sont pas trop volumineuses.

6.3.2. Tables de hachage concurrentes

L'API Concurrent fournit dans ce domaine une interface et quelques implémentations. Cette interface ajoute quatre méthodes, que nous allons voir. L'interface ConcurrentMap<K, V> est une extension de Map<K, V>, qui propose les méthodes supplémentaires suivantes.
  • putIfAbsent(K key, V value) : ajoute ce couple (clé, valeur) si cette clé n'est pas déjà présente.
  • remove(Object key, Object value) : retire cette clé de la table, si elle est associée à la valeur passée en paramètre. Cela permet d'éviter de retirer une clé qu'un autre thread aurait ajoutée par ailleurs.
  • replace(K key, V value) : remplace la valeur associée à cette clé par celle passée en paramètre.
  • replace(K key, V oldValue, V newValue) : remplace la valeur associée à cette clé par celle passée en paramètre, si l'actuelle valeur est oldValue.
L'implémentation fournie par l'API Concurrent est ConcurrentHashMap. Son implémentation est la classe ConcurrentHashMap<K, V>. Elle autorise autant de lectures que l'on veut, et ces lectures sont non-bloquantes. Les itérateurs construits sur cette table ne jettent pas de ConcurrentModificationException. En revanche, les opérations de modifications sont contrôlées. Lors de la construction de cette table, on peut lui passer un paramètre, concurrencyLevel (la valeur par défaut est 16), qui règle certains éléments internes de la table. Le but est de réduire les goulets d'étranglement, tout en conservant la sécurité des opérations concurrentes.

6.3.3. Extension de SortedSet et SortedMap

L'API Concurrent nous donne également deux implémentations de ces interfaces, qui, rappelons-le, permettent de conserver les éléments enregistrés triés. Les deux implémentations fournies sont ConcurrentSkipListSet<K, V> et ConcurrentSkipListMap<K, V>. De la même façon que les autres classes, elles sont optimisées pour les accès en lecture, notamment pour être non-bloquantes.
Java API avancées
Retour au blog Java le soir
Cours & Tutoriaux
Table des matières
API Collection
1. Introduction
2. Interface Collection
2.1. Notion de Collection
2.2. Détail des méthodes disponibles
2.3. Interface Iterator
2.4. Implémentation, exemples d'utilisation
3. Interface List
3.1. Notion de List
3.2. Détail des méthodes disponibles
3.3. Interface ListIterator
3.4. Implémentations, exemples d'utilisation
4. Interface Set
4.1. Notion de Set
4.2. Implémentations HashSet et LinkedHashSet
4.3. Exemples d'utilisation
5. Interface SortedSet
5.1. Notion de SortedSet
5.2. Détails des méthodes disponibles
5.3. Exemples d'utilisation
6. Interface NavigableSet
6.1. Notion de NavigableSet
6.2. Détails des méthodes disponibles
6.3. Exemple d'utilisation
7. Interfaces Queue et Deque
7.1. Notion de file d'attente
7.2. Détail des méthodes disponibles
7.3. Utilisation des interfaces Queue et Deque
8. Tables de hachage
8.1. Notion de table de hachage
8.2. Interface Map
8.3. Interface Map.Entry
8.4. Interface SortedMap
8.5. Interface NavigableMap
8.6. Implémentations
8.7. Exemples d'utilisation
9. Classes utilitaires Collections et Arrays
9.1. Introduction
9.2. Classe Arrays
9.3. Classe Collections
Génériques
1. Introduction
2. Un premier exemple
2.1. Une première classe générique
2.2. Une première méthode générique
3. Contraindre un type générique
3.1. Problème posé
3.2. Contraindre un type générique
4. Implémentation des génériques
4.1. Type erasure
4.2. Types génériques et casts
4.3. Type générique et exception
4.4. Construction d'une instance générique
4.5. Génériques et membres statiques
4.6. Collisions de méthodes génériques
4.7. Implémentation de plusieurs types identiques
5. Type <?>
5.1. Introduction
5.2. Type ? extension d'un type
5.3. Type ? super-type d'un type
Expressions régulières
1. Introduction
2. Mise en œuvre des expressions régulières
2.1. Fonctionnement d'une regexp
2.2. Fonctionnement de l'API en Java
2.3. Un premier exemple
2.4. Classe Pattern
2.5. Classe Matcher
2.6. Utilisation des méthode find() et group()
2.7. Méthodes de remplacement
2.8. Sélection de régions
3. Syntaxe des expressions régulières
3.1. Notion de classe
3.2. Étude d'un cas réel
3.3. Recherche d'un mot précis
3.4. Recherche de deux mots précis
3.5. Recherche d'un mot commençant par une lettre donnée
3.6. Cas de mots comportant des caractères accentués
3.7. Recherche sur les lignes
Introspection
1. Introduction
2. La classe Class
2.1. Utilisation de Class
2.2. Méthodes disponibles
2.3. Remarque sur la propriété Accessible
2.4. Type d'une classe
2.5. Création d'une instance à partir d'un objet Class
2.6. Cas des énumérations
3. Les classes Method et Constructor
3.1. Utilisation de Method
3.2. Utilisation de Constructor
3.3. Méthodes disponibles
3.4. Invocation d'une méthode par introspection
4. La classe Field
4.1. Utilisation de Field
4.2. Méthodes disponibles
4.3. Accès à un champ par introspection
5. La classe Modifier
Programmation concurrente
1. Introduction
2. Lançons nos premiers threads
2.1. Introduction
2.2. Un premier thread, extension de Thread
2.3. Un deuxième thread, implémentation de Runnable
2.4. Remarque sur la méthode Thread.sleep(long)
2.5. Arrêter un thread
3. Concurrence d'accès
3.1. Notion d'état
3.2. Exemple de concurrence d'accès sur un état
3.3. Analyse de la concurrence d'accès
3.4. Solution au problème
3.5. Champs volatile
4. Synchronisation
4.1. Définition d'un bloc synchronisé
4.2. Fonctionnement d'un bloc synchronisé
4.3. Notion de deadlock
4.4. Bonnes pratiques pour la synchronisation de threads
5. Opérations atomiques
5.1. Atomicité d'une opération
5.2. Solutions disponibles
5.3. Variables atomiques
6. Collections synchronisées et concurrentes
6.1. Introduction
6.2. Position du problème
6.3. Solutions proposées
7. Files d'attente
7.1. Introduction, pattern producteur / consommateur
7.2. Interface BlockingQueue<E>
7.3. Implémentations de BlockingQueue
7.4. Exemple de producteur / consommateur
7.5. Arrêter un producteur / consommateur : pilule empoisonnée
8. Classes utilitaires de l'API Concurrent
8.1. Introduction
8.2. Énumération TimeUnit
8.3. Interface Callable<V>
8.4. Interfaces Future<V> et RunnableFuture<V>
8.5. Interface ScheduledFuture<V> et RunnableScheduledFuture<V>
9. Pattern executor
9.1. Notion de réserve de threads
9.2. Interface Executor
9.3. Interface ExecutorService
9.4. Interface ScheduledExecutorService
9.5. Classe Executors
9.6. Pattern de lancement de tâches
10. Classes de contrôle d'accès
10.1. Introduction
10.2. Interfaces Lock et ReadWriteLock
10.3. Notion de verrou réentrant
10.4. Classe RentrantLock
10.5. Classe ReadWriteRentrantLock
11. Sémaphores, barrières et latches
11.1. Introduction
11.2. Notion de sémaphore, classe Semaphore
11.3. Notion de latch, classe CountDownLatch
11.4. Notion de barrière, classe CyclicBarrier