Java 101: la concurrence Java sans la douleur, partie 2

Précédent 1 2 3 4 Page 3 Suivant Page 3 sur 4

Variables atomiques

Les applications multithreads qui s'exécutent sur des processeurs multicœurs ou des systèmes multiprocesseurs peuvent atteindre une bonne utilisation matérielle et être hautement évolutives. Ils peuvent atteindre ces objectifs en faisant passer la majeure partie de leur temps à leurs threads à effectuer un travail plutôt que d'attendre le travail à accomplir ou d'attendre d'acquérir des verrous pour accéder aux structures de données partagées.

Cependant, le mécanisme de synchronisation traditionnel de Java, qui applique l'exclusion mutuelle (le thread détenant le verrou qui protège un ensemble de variables y a un accès exclusif) et la visibilité (les modifications apportées aux variables protégées deviennent visibles pour d'autres threads qui acquièrent par la suite le verrou), a un impact utilisation du matériel et évolutivité, comme suit:

  • La synchronisation conflictuelle (plusieurs threads en concurrence constante pour un verrou) est coûteuse et le débit en souffre. Une raison majeure de la dépense est le changement de contexte fréquent qui a lieu; une opération de changement de contexte peut prendre plusieurs cycles de processeur. En revanche, la synchronisation incontrôlée est peu coûteuse sur les JVM modernes.
  • Lorsqu'un thread tenant un verrou est retardé (par exemple, à cause d'un retard de planification), aucun thread qui nécessite ce verrou ne progresse, et le matériel n'est pas utilisé aussi bien qu'il pourrait l'être autrement.

Vous pourriez penser que vous pouvez utiliser volatilecomme alternative de synchronisation. Cependant, les volatilevariables ne résolvent que le problème de visibilité. Ils ne peuvent pas être utilisés pour implémenter en toute sécurité les séquences atomiques de lecture-modification-écriture qui sont nécessaires pour implémenter en toute sécurité des compteurs et d'autres entités qui nécessitent une exclusion mutuelle.

Java 5 a introduit une alternative de synchronisation qui offre une exclusion mutuelle combinée aux performances de volatile. Cette alternative de variable atomique est basée sur l'instruction compare-and-swap d'un microprocesseur et se compose en grande partie des types du java.util.concurrent.atomicpackage.

Comprendre la comparaison et l'échange

L' instruction de comparaison et d'échange (CAS) est une instruction ininterrompue qui lit un emplacement mémoire, compare la valeur lue à une valeur attendue et stocke une nouvelle valeur dans l'emplacement mémoire lorsque la valeur lue correspond à la valeur attendue. Sinon, rien n'est fait. L'instruction réelle du microprocesseur peut différer quelque peu (par exemple, renvoyer true si CAS réussit ou false dans le cas contraire au lieu de la valeur lue).

Instructions CAS du microprocesseur

Les microprocesseurs modernes offrent une sorte d'instruction CAS. Par exemple, les microprocesseurs Intel offrent la cmpxchgfamille d'instructions, tandis que les microprocesseurs PowerPC offrent des instructions de liaison de charge (par exemple lwarx) et de stockage conditionnel (par exemple stwcx) dans le même but.

CAS permet de prendre en charge des séquences atomiques de lecture-modification-écriture. Vous utiliseriez généralement CAS comme suit:

  1. Lisez la valeur v à partir de l'adresse X.
  2. Effectuez un calcul en plusieurs étapes pour dériver une nouvelle valeur v2.
  3. Utilisez CAS pour changer la valeur de X de v à v2. CAS réussit lorsque la valeur de X n'a ​​pas changé lors de l'exécution de ces étapes.

Pour voir comment CAS offre de meilleures performances (et évolutivité) par rapport à la synchronisation, considérez un exemple de compteur qui vous permet de lire sa valeur actuelle et d'incrémenter le compteur. La classe suivante implémente un compteur basé sur synchronized:

Listing 4. Counter.java (version 1)

public class Counter { private int value; public synchronized int getValue() { return value; } public synchronized int increment() { return ++value; } }

Un conflit élevé pour le verrouillage du moniteur entraînera une commutation de contexte excessive qui peut retarder tous les threads et entraîner une application qui ne s'adapte pas correctement.

L'alternative CAS nécessite une implémentation de l'instruction compare-and-swap. La classe suivante émule CAS. Il utilise à la synchronizedplace de l'instruction matérielle réelle pour simplifier le code:

Listing 5. EmulatedCAS.java

public class EmulatedCAS { private int value; public synchronized int getValue() { return value; } public synchronized int compareAndSwap(int expectedValue, int newValue) { int readValue = value; if (readValue == expectedValue) value = newValue; return readValue; } }

Ici, valueidentifie un emplacement de mémoire, qui peut être récupéré par getValue(). Implémente également compareAndSwap()l'algorithme CAS.

La classe suivante utilise EmulatedCASpour implémenter un non- synchronizedcompteur (faire semblant qui EmulatedCASne nécessite pas synchronized):

Listing 6. Counter.java (version 2)

public class Counter { private EmulatedCAS value = new EmulatedCAS(); public int getValue() { return value.getValue(); } public int increment() { int readValue = value.getValue(); while (value.compareAndSwap(readValue, readValue+1) != readValue) readValue = value.getValue(); return readValue+1; } }

Counterencapsule une EmulatedCASinstance et déclare des méthodes pour récupérer et incrémenter une valeur de compteur avec l'aide de cette instance. getValue()récupère la "valeur actuelle du compteur" de l'instance et increment()incrémente en toute sécurité la valeur du compteur.

increment()invoque à plusieurs reprises compareAndSwap()jusqu'à ce que readValuela valeur de ne change pas. Il est alors libre de modifier cette valeur. Lorsqu'aucun verrou n'est impliqué, les conflits sont évités avec un changement de contexte excessif. Les performances s'améliorent et le code est plus évolutif.

ReentrantLock et CAS

Vous avez déjà appris qu'il ReentrantLockoffre de meilleures performances qu'en synchronizedcas de conflit de threads élevé. Pour améliorer les performances, ReentrantLockla synchronisation de est gérée par une sous-classe de la java.util.concurrent.locks.AbstractQueuedSynchronizerclasse abstraite . À son tour, cette classe exploite la sun.misc.Unsafeclasse non documentée et sa compareAndSwapInt()méthode CAS.

Explorer le package de variables atomiques

Vous n'avez pas à implémenter compareAndSwap()via l'interface native Java non portable. Au lieu de cela, Java 5 offre ce support via java.util.concurrent.atomic: une boîte à outils de classes utilisées pour la programmation sans verrouillage et sans thread sur des variables uniques.

Selon java.util.concurrent.atomicJavadoc de 's, ces classes

étendre la notion de volatilevaleurs, de champs et d'éléments de tableau à ceux qui fournissent également une opération de mise à jour conditionnelle atomique du formulaire boolean compareAndSet(expectedValue, updateValue). Cette méthode (qui varie dans les types d'argument selon les différentes classes) définit de manière atomique une variable sur updateValuesi elle contient actuellement le expectedValue, indiquant true en cas de succès.

Ce package propose des classes pour les types Boolean ( AtomicBoolean), integer ( AtomicInteger), long integer ( AtomicLong) et reference ( AtomicReference). Il propose également des versions de tableau de nombre entier, entier long et référence ( AtomicIntegerArray, AtomicLongArrayet AtomicReferenceArray), des cours de référence marquables et timbrée pour la mise à jour atomiquement une paire de valeurs ( AtomicMarkableReferenceet AtomicStampedReference), et plus encore.

Implémentation de compareAndSet ()

Java implémente compareAndSet()via la construction native la plus rapide disponible (par exemple, cmpxchgou load-link / store-conditionitional) ou (dans le pire des cas) des verrous rotatifs .

Considérez AtomicInteger, qui vous permet de mettre à jour une intvaleur de manière atomique. Nous pouvons utiliser cette classe pour implémenter le compteur indiqué dans le Listing 6. Le Listing 7 présente le code source équivalent.

Listing 7. Counter.java (version 3)

import java.util.concurrent.atomic.AtomicInteger; public class Counter { private AtomicInteger value = new AtomicInteger(); public int getValue() { return value.get(); } public int increment() { int readValue = value.get(); while (!value.compareAndSet(readValue, readValue+1)) readValue = value.get(); return readValue+1; } }

Listing 7 is very similar to Listing 6 except that it replaces EmulatedCAS with AtomicInteger. Incidentally, you can simplify increment() because AtomicInteger supplies its own int getAndIncrement() method (and similar methods).

Fork/Join framework

Computer hardware has evolved significantly since Java's debut in 1995. Back in the day, single-processor systems dominated the computing landscape and Java's synchronization primitives, such as synchronized and volatile, as well as its threading library (the Thread class, for example) were generally adequate.

Multiprocessor systems became cheaper and developers found themselves needing to create Java applications that effectively exploited the hardware parallelism that these systems offered. However, they soon discovered that Java's low-level threading primitives and library were very difficult to use in this context, and the resulting solutions were often riddled with errors.

What is parallelism?

Parallelism is the simultaneous execution of multiple threads/tasks via some combination of multiple processors and processor cores.

The Java Concurrency Utilities framework simplifies the development of these applications; however, the utilities offered by this framework do not scale to thousands of processors or processor cores. In our many-core era, we need a solution for achieving a finer-grained parallelism, or we risk keeping processors idle even when there is lots of work for them to handle.

Professor Doug Lea presented a solution to this problem in his paper introducing the idea for a Java-based fork/join framework. Lea describes a framework that supports "a style of parallel programming in which problems are solved by (recursively) splitting them into subtasks that are solved in parallel." The Fork/Join framework was eventually included in Java 7.

Overview of the Fork/Join framework

The Fork/Join framework is based on a special executor service for running a special kind of task. It consists of the following types that are located in the java.util.concurrent package:

  • ForkJoinPool: an ExecutorService implementation that runs ForkJoinTasks. ForkJoinPool provides task-submission methods, such as void execute(ForkJoinTask task), along with management and monitoring methods, such as int getParallelism() and long getStealCount().
  • ForkJoinTask: an abstract base class for tasks that run within a ForkJoinPool context. ForkJoinTask describes thread-like entities that have a much lighter weight than normal threads. Many tasks and subtasks can be hosted by very few actual threads in a ForkJoinPool instance.
  • ForkJoinWorkerThread: a class that describes a thread managed by a ForkJoinPool instance. ForkJoinWorkerThread is responsible for executing ForkJoinTasks.
  • RecursiveAction: an abstract class that describes a recursive resultless ForkJoinTask.
  • RecursiveTask: an abstract class that describes a recursive result-bearing ForkJoinTask.

The ForkJoinPool executor service is the entry-point for submitting tasks that are typically described by subclasses of RecursiveAction or RecursiveTask. Behind the scenes, the task is divided into smaller tasks that are forked (distributed among different threads for execution) from the pool. A task waits until joined (its subtasks finish so that results can be combined).

ForkJoinPool manages a pool of worker threads, where each worker thread has its own double-ended work queue (deque). When a task forks a new subtask, the thread pushes the subtask onto the head of its deque. When a task tries to join with another task that hasn't finished, the thread pops another task off the head of its deque and executes the task. If the thread's deque is empty, it tries to steal another task from the tail of another thread's deque. This work stealing behavior maximizes throughput while minimizing contention.

Using the Fork/Join framework

Fork/Join was designed to efficiently execute divide-and-conquer algorithms, which recursively divide problems into sub-problems until they are simple enough to solve directly; for example, a merge sort. The solutions to these sub-problems are combined to provide a solution to the original problem. Each sub-problem can be executed independently on a different processor or core.

Lea's paper presents the following pseudocode to describe the divide-and-conquer behavior:

Result solve(Problem problem) { if (problem is small) directly solve problem else { split problem into independent parts fork new subtasks to solve each part join all subtasks compose result from subresults } }

The pseudocode presents a solve method that's called with some problem to solve and which returns a Result that contains the problem's solution. If the problem is too small to solve via parallelism, it's solved directly. (The overhead of using parallelism on a small problem exceeds any gained benefit.) Otherwise, the problem is divided into subtasks: each subtask independently focuses on part of the problem.

Operation fork launches a new fork/join subtask that will execute in parallel with other subtasks. Operation join delays the current task until the forked subtask finishes. At some point, the problem will be small enough to be executed sequentially, and its result will be combined along with other subresults to achieve an overall solution that's returned to the caller.

The Javadoc for the RecursiveAction and RecursiveTask classes presents several divide-and-conquer algorithm examples implemented as fork/join tasks. For RecursiveAction the examples sort an array of long integers, increment each element in an array, and sum the squares of each element in an array of doubles. RecursiveTask's solitary example computes a Fibonacci number.

Le listing 8 présente une application qui montre l'exemple de tri dans des contextes non-fork / join ainsi que fork / join. Il présente également des informations de synchronisation pour contraster les vitesses de tri.