Variables atómicas
Las aplicaciones multiproceso que se ejecutan en procesadores multinúcleo o sistemas multiprocesador pueden lograr una buena utilización del hardware y ser altamente escalables. Pueden lograr estos fines haciendo que sus subprocesos pasen la mayor parte de su tiempo realizando un trabajo en lugar de esperar a que se complete el trabajo o esperar a adquirir bloqueos para acceder a estructuras de datos compartidas.
Sin embargo, el mecanismo de sincronización tradicional de Java, que impone la exclusión mutua (el hilo que sostiene el bloqueo que protege un conjunto de variables tiene acceso exclusivo a ellos) y la visibilidad (los cambios en las variables protegidas se vuelven visibles para otros hilos que posteriormente adquieren el bloqueo), impacta utilización y escalabilidad del hardware, como se indica a continuación:
- La sincronización asistida (múltiples subprocesos que compiten constantemente por un bloqueo) es costosa y, como resultado, el rendimiento se ve afectado. Una de las principales razones del gasto es el frecuente cambio de contexto que tiene lugar; una operación de cambio de contexto puede tardar muchos ciclos de procesador en completarse. Por el contrario, la sincronización no atendida es económica en las JVM modernas.
- Cuando un subproceso que tiene un bloqueo se retrasa (por ejemplo, debido a un retraso de programación), ningún subproceso que requiera ese bloqueo avanza, y el hardware no se utiliza tan bien como podría serlo.
Podría pensar que puede utilizarlo volatilecomo alternativa de sincronización. Sin embargo, las volatilevariables solo resuelven el problema de la visibilidad. No se pueden utilizar para implementar de forma segura las secuencias atómicas de lectura-modificación-escritura que son necesarias para implementar de forma segura contadores y otras entidades que requieren exclusión mutua.
Java 5 introdujo una alternativa de sincronización que ofrece exclusión mutua combinada con el rendimiento de volatile. Esta alternativa de variable atómica se basa en la instrucción de comparación e intercambio de un microprocesador y consta en gran medida de los tipos del java.util.concurrent.atomicpaquete.
Entendiendo comparar e intercambiar
La instrucción de comparar e intercambiar (CAS) es una instrucción ininterrumpida que lee una ubicación de memoria, compara el valor leído con un valor esperado y almacena un nuevo valor en la ubicación de memoria cuando el valor leído coincide con el valor esperado. De lo contrario, no se hace nada. La instrucción real del microprocesador puede diferir un poco (por ejemplo, devolver verdadero si CAS tuvo éxito o falso de lo contrario en lugar del valor leído).
Instrucciones CAS del microprocesador
Los microprocesadores modernos ofrecen algún tipo de instrucción CAS. Por ejemplo, los microprocesadores Intel ofrecen la cmpxchgfamilia de instrucciones, mientras que los microprocesadores PowerPC ofrecen instrucciones de enlace de carga (por ejemplo, lwarx) y condicionales de almacenamiento (por ejemplo, stwcx) para el mismo propósito.
CAS hace posible admitir secuencias atómicas de lectura, modificación y escritura. Por lo general, usaría CAS de la siguiente manera:
- Lea el valor v de la dirección X.
- Realice un cálculo de varios pasos para obtener un nuevo valor v2.
- Utilice CAS para cambiar el valor de X de v a v2. CAS tiene éxito cuando el valor de X no ha cambiado al realizar estos pasos.
Para ver cómo CAS ofrece un mejor rendimiento (y escalabilidad) sobre la sincronización, considere un ejemplo de contador que le permite leer su valor actual e incrementar el contador. La siguiente clase implementa un contador basado en synchronized:
Listado 4. Counter.java (versión 1)
public class Counter { private int value; public synchronized int getValue() { return value; } public synchronized int increment() { return ++value; } }Una gran contención por el bloqueo del monitor dará como resultado un cambio de contexto excesivo que puede retrasar todos los hilos y dar como resultado una aplicación que no se escala bien.
La alternativa CAS requiere una implementación de la instrucción de comparar e intercambiar. La siguiente clase emula CAS. Utiliza en synchronizedlugar de la instrucción de hardware real para simplificar el código:
Listado 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; } }Aquí, valueidentifica una ubicación de memoria, que puede ser recuperada por getValue(). Además, compareAndSwap()implementa el algoritmo CAS.
La siguiente clase se usa EmulatedCASpara implementar un no synchronizedcontador (simule que EmulatedCASno requiere synchronized):
Listado 6. Counter.java (versión 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; } }Counterencapsula una EmulatedCASinstancia y declara métodos para recuperar e incrementar un valor de contador con la ayuda de esta instancia. getValue()recupera el "valor actual del contador" de la instancia e increment()incrementa de forma segura el valor del contador.
increment()invoca repetidamente compareAndSwap()hasta que readValueel valor de 'no cambia. Entonces es libre de cambiar este valor. Cuando no hay ningún bloqueo, se evita la contención junto con el cambio de contexto excesivo. El rendimiento mejora y el código es más escalable.
ReentrantLock y CAS
Anteriormente aprendió que ReentrantLockofrece un mejor rendimiento que synchronizedbajo una alta contención de subprocesos. Para mejorar el rendimiento, ReentrantLockla sincronización de 'es administrada por una subclase de la java.util.concurrent.locks.AbstractQueuedSynchronizerclase abstracta . A su vez, esta clase aprovecha la sun.misc.Unsafeclase indocumentada y su compareAndSwapInt()método CAS.
Explorando el paquete de variables atómicas
No tiene que implementarlo a compareAndSwap()través de la interfaz nativa de Java no portátil. En cambio, Java 5 ofrece este soporte a través de java.util.concurrent.atomic: un conjunto de herramientas de clases que se utilizan para la programación segura para subprocesos y sin bloqueos en variables individuales.
Según java.util.concurrent.atomic's Javadoc, estas clases
volatilevalores, campos y elementos de matriz a aquellos que también proporcionan una operación de actualización condicional atómica del formulario
boolean compareAndSet(expectedValue, updateValue). Este método (que varía en tipos de argumentos en diferentes clases) establece atómicamente una variable en
updateValuesi actualmente tiene el
expectedValue, informando verdadero en caso de éxito.
Este paquete ofrece clases para los tipos Boolean ( AtomicBoolean), integer ( AtomicInteger), long integer ( AtomicLong) y reference ( AtomicReference). También ofrece versiones de matriz de número entero, entero largo, y la referencia ( AtomicIntegerArray, AtomicLongArrayy AtomicReferenceArray), clases de referencia marcables y estampadas para actualizar atómicamente un par de valores ( AtomicMarkableReferencey AtomicStampedReference), y más.
Implementación de compareAndSet ()
Java se implementa a compareAndSet()través de la construcción nativa más rápida disponible (por ejemplo, cmpxchgo load-link / store-conditional) o (en el peor de los casos) bloqueos de giro .
Considere AtomicInteger, lo que le permite actualizar un intvalor de forma atómica. Podemos usar esta clase para implementar el contador que se muestra en el Listado 6. El Listado 7 presenta el código fuente equivalente.
Listado 7. Counter.java (versión 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: anExecutorServiceimplementation that runsForkJoinTasks.ForkJoinPoolprovides task-submission methods, such asvoid execute(ForkJoinTask task), along with management and monitoring methods, such asint getParallelism()andlong getStealCount().ForkJoinTask: an abstract base class for tasks that run within aForkJoinPoolcontext.ForkJoinTaskdescribes 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 aForkJoinPoolinstance.ForkJoinWorkerThread: a class that describes a thread managed by aForkJoinPoolinstance.ForkJoinWorkerThreadis responsible for executingForkJoinTasks.RecursiveAction: an abstract class that describes a recursive resultlessForkJoinTask.RecursiveTask: an abstract class that describes a recursive result-bearingForkJoinTask.
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.
El Listado 8 presenta una aplicación que demuestra el ejemplo de ordenación en contextos sin bifurcación / unión y bifurcación / unión. También presenta información de tiempo para contrastar las velocidades de clasificación.
