Aspectos básicos de SMP para Android

Android 3.0 y las versiones posteriores de la plataforma están optimizadas para admitir arquitecturas de varios procesadores. En este documento, se detallan los problemas que pueden surgir cuando se escribe código multiproceso para sistemas de multiprocesadores simétricos en C, C++ y el lenguaje de programación Java (a partir de ahora, "Java" para mayor brevedad). Además, está pensado a modo de material de consulta básico para desarrolladores de apps de Android y no debe considerarse como un análisis completo del tema.

Introducción

SMP es el acrónimo de "Multiprocesador simétrico". Describe un diseño en el que dos o más núcleos de CPU idénticos comparten acceso a la memoria principal. Hasta hace unos años, todos los dispositivos Android eran UP (monoprocesadores).

La mayoría de los dispositivos Android, si no todos, tenían múltiples CPU, pero solía usarse solo una para ejecutar aplicaciones. Las otras, en cambio, administraban diversos elementos del hardware del dispositivo (por ejemplo, la radio). Es posible que los CPU tuvieran arquitecturas diferentes y que los programas que ejecutaban no pudieran usar la memoria principal para comunicarse entre sí.

La mayoría de los dispositivos Android que se venden hoy en día se basan en diseños SMP, lo que dificulta un poco el trabajo de los desarrolladores de software. Las condiciones de carrera en un programa multiproceso pueden no causar problemas visibles en un monoprocesador, pero es posible que arrojen errores de forma habitual cuando se ejecutan de manera simultánea dos o más subprocesos en núcleos diferentes. Además, el código puede ser más o menos propenso a fallas cuando se ejecuta en arquitecturas de procesador diferentes o incluso en implementaciones diferentes de la misma arquitectura. Un código que se probó de manera exhaustiva en x86 puede fallar gravemente en ARM Los fallos pueden comenzar cuando se vuelve a compilar con un compilador más moderno.

En el resto de este documento, se detallarán las razones y se explicará qué debes hacer para asegurarte de que tu código se comporte de forma correcta.

Modelos de coherencia de memoria: razones por las que los SMP son diferentes

Este es un breve resumen sobre un tema complejo. Algunas áreas estarán incompletas, pero ninguna será incorrecta ni confusa. Como verás en la siguiente sección, en general, aquí los detalles no son importantes.

Consulta la sección Lecturas adicionales que se encuentra al final del documento para obtener sugerencias sobre recursos más completos del tema.

Los modelos de coherencia de memoria, a menudo denominados "modelos de memoria", describen las garantías del lenguaje de programación o de la arquitectura de hardware sobre los accesos a la memoria. Por ejemplo, si escribes un valor en la dirección A y, luego, otro en la dirección B, el modelo puede garantizar que cada núcleo de la CPU vea que esas escrituras ocurren en ese orden.

El modelo al que está acostumbrada la mayoría de los programadores se denomina consistencia secuencial y se describe de la siguiente forma (Adve y Gharachorloo):

  • Todas las operaciones de memoria parecen ejecutarse una a la vez.
  • Todas las operaciones de un solo subproceso parecen ejecutarse en el orden descrito por el programa de ese procesador.

Supongamos, por un momento, que tenemos un compilador o intérprete muy simple que no presenta sorpresas: traduce tareas en código fuente para cargar y almacenar las instrucciones en el orden exacto, una instrucción por acceso. Para que sea más simple, supongamos también que cada subproceso se ejecuta en su propio procesador.

Si analizas un fragmento de código y observas que hace algunas lecturas y escrituras de la memoria en una arquitectura de CPU con consistencia secuencial, sabes que el código realizará esas lecturas y escrituras en el orden esperado. Es posible que la CPU esté reordenando las instrucciones y retrasando las lecturas y escrituras, pero no hay forma de que el código que se ejecuta en el dispositivo sepa que la CPU está haciendo algo más que ejecutar las instrucciones de una manera directa. (No vamos a tener en cuenta la E/S del controlador del dispositivo asignado a la memoria).

Para ilustrar estos puntos, es útil considerar pequeños fragmentos de código, que suelen denominarse pruebas decisivas.

A continuación, se incluye un ejemplo sencillo con código que se ejecuta en dos subprocesos:

Subproceso 1 Subproceso 2
A = 3
B = 5
reg0 = B
reg1 = A

En este y en todos los ejemplos decisivos futuros, las ubicaciones de la memoria se representan con mayúsculas (A, B, C) y los registros de la CPU comienzan con "reg". En un principio, la memoria total es cero. Las instrucciones se ejecutan de arriba abajo. Aquí, el subproceso 1 almacena el valor 3 en la ubicación A y el valor 5 en la ubicación B. El subproceso 2 carga el valor de la ubicación B en reg0 y, luego, carga el valor de la ubicación A en reg1. (Observa que escribimos en un orden y leemos en otro).

Se da por sentado que los subprocesos 1 y 2 se ejecutan en diferentes núcleos de CPU. Es necesario que siempre des eso por sentado cuando piensas en el código multiproceso.

La consistencia secuencial garantiza que, una vez que terminen de ejecutarse ambos subprocesos, los registros estarán en uno de los siguientes estados:

Registros Estados
reg0=5, reg1=3 posible (se ejecutó primero el subproceso 1)
reg0=0, reg1=0 posible (se ejecutó primero el subproceso 2)
reg0=0, reg1=3 posible (ejecución concurrente)
reg0=5, reg1=0 nunca

Para encontrarnos en una situación donde vemos B=5 antes del almacenamiento en A, es necesario que las lecturas o escrituras ocurran de manera desordenada. En una máquina con consistencia secuencial, eso no puede suceder.

Los monoprocesadores, incluidos el x86 y el ARM, suelen tener consistencia secuencial. Los subprocesos parecen ejecutarse de forma intercalada, a medida que el kernel del SO pasa de uno al otro. La mayoría de los sistemas SMP, incluidos el x86 y el ARM, no tienen consistencia secuencial. Por ejemplo, es común que el hardware guarde en búfer almacenes en camino hacia la memoria para que no lleguen de inmediato a esta y se vuelvan visibles para otros núcleos.

Los detalles varían de manera considerable. Por ejemplo, en el caso del x86, aunque no tiene consistencia secuencial, igual garantiza que reg0=5 y reg1=0 sigan siendo imposibles. Los almacenamientos se guardan en búfer, pero se mantiene el orden. En ARM, en cambio, eso no ocurre. Por lo tanto, no se mantiene el orden de los almacenamientos guardados en búfer y es posible que estos no lleguen a todos los núcleos al mismo tiempo. Esas son diferencias importantes para programadores de ensamblado. Sin embargo, como veremos más adelante, los programadores de C, C++ o Java pueden y deben programar de una manera en que se oculten esas diferencias arquitectónicas.

Hasta ahora, dimos por sentado, aunque no es real, que solo el hardware reordena las instrucciones. En realidad, el compilador también lo hace para mejorar el rendimiento. En nuestro ejemplo, el compilador podría decidir que algún código posterior en el subproceso 2 necesitaba el valor de reg1 antes que el de reg0; por lo tanto, carga primero reg1. También es posible que algún código anterior ya haya cargado A, y el compilador podría decidir reutilizar ese valor en lugar de volver a cargar A. En cualquier caso, podrían reordenarse las cargas a reg0 y reg1.

El reordenamiento de accesos a diferentes ubicaciones de memoria, ya sea en el hardware o en el compilador, está permitido, dado que no afecta la ejecución de un solo subproceso y puede mejorar el rendimiento considerablemente. Como veremos, con un poco de cuidado también podemos evitar que afecte los resultados de programas multiproceso.

Debido a que los compiladores también pueden reordenar los accesos a memoria, este problema no es un problema nuevo de los SMP. Incluso en un monoprocesador, un compilador podría reordenar las cargas en reg0 y reg1 de nuestro ejemplo, y el subproceso 1 podría programarse entre las instrucciones reordenadas. Sin embargo, si por alguna razón el compilador no reordenó nada, es posible que nunca observemos este problema. En la mayoría de los SMP de ARM, incluso sin el reordenamiento de los compiladores, lo más probable es que el reordenamiento ocurra después de una gran cantidad de ejecuciones exitosas. A menos que estés programando en lenguaje de ensamblado, los SMP suelen aumentar las probabilidades de que veas problemas que siempre existieron.

Cómo programar sin carreras de datos

Por suerte, suele haber una forma sencilla de evitar pensar en esos detalles. Si sigues algunas reglas simples, en general no necesitas preocuparte por la sección anterior, excepto por la parte de la "consistencia secuencial". Lamentablemente, pueden aparecer las otras complicaciones si infringes esas reglas por error.

Los lenguajes de programación modernos fomentan lo que se conoce como un estilo de programación "sin carreras de datos". Siempre y cuando prometas no introducir "carreras de datos" y evites las pocas construcciones que le indican lo contrario al compilador, el hardware y el compilador prometen proporcionar resultados con consistencia secuencial. Eso no quiere decir que eviten el reordenamiento del acceso a la memoria. Significa que, si sigues las reglas, no podrás darte cuenta de que se están reordenando los accesos a la memoria. Es como decirte que las salchichas son deliciosas, siempre y cuando prometas que no vas a visitar la fábrica de salchichas. Las carreras de datos exponen los aspectos negativos del reordenamiento de memoria.

¿Qué es una "carrera de datos"?

Una carrera de datos ocurre cuando al menos dos subprocesos acceden de manera simultánea a los mismos datos ordinarios y al menos uno de ellos los modifica. La frase "datos ordinarios" hace referencia a algo que no es específicamente un objeto de sincronización destinado a la comunicación de subprocesos. Las exclusiones mutuas, las variables de condición, las variables volátiles de Java o los objetos atómicos de C++ no son datos ordinarios, y sus accesos pueden ser parte de una carrera. Es más, se utilizan para evitar carreras de datos en otros objetos.

Para determinar si dos subprocesos acceden de manera simultánea a la misma ubicación de memoria, podemos ignorar la explicación sobre el reordenamiento de memoria incluida arriba y dar por sentado que hay consistencia secuencial. El siguiente programa no tiene una carrera de datos si A y B son variables booleanas ordinarias que, en un principio, son falsas:

Subproceso 1 Subproceso 2
if (A) B = true if (B) A = true

Como no se reordenan las operaciones, se evaluarán ambas condiciones como falsas y no se actualizará ninguna de las dos variables. Como consecuencia, no puede haber una carrera de datos. No hace falta pensar en qué podría pasar si se reordenaran de alguna manera la carga de A y el almacenamiento en B en el subproceso 1. El compilador no puede reordenar el subproceso 1 reescribiéndolo como "B = true; if (!A) B = false", ya que eso sería como hacer salchichas en medio de la ciudad a plena luz del día.

Las carreras de datos se definen de manera oficial en tipos integrados básicos como valores enteros y referencias o punteros. Realizar una asignación a un int y leerlo en simultáneo en otro subproceso es, sin duda, una carrera de datos. Sin embargo, la biblioteca estándar de C++ y las bibliotecas de colecciones de Java están escritas para permitirte razonar también sobre las carreras de datos a nivel de la biblioteca. Prometen no introducir carreras de datos, a menos que haya accesos concurrentes al mismo contenedor y que, como mínimo, uno de ellos las actualice. Actualizar un set<T> en un subproceso y, al mismo tiempo, leerlo en otro permite que la biblioteca introduzca una carrera de datos; por lo tanto, puede considerarse de manera informal una "carrera de datos a nivel de la biblioteca". Por el contrario, actualizar un set<T> en un subproceso y, al mismo tiempo, leer uno diferente en otro subproceso no tiene como resultado una carrera de datos, ya que, en ese caso, la biblioteca promete no introducir una carrera de datos (de bajo nivel).

En general, los accesos simultáneos a diferentes campos de una estructura de datos no pueden introducir una carrera de datos. Sin embargo, hay una excepción importante a esta regla: las secuencias contiguas de campos de bits en C o C++ se tratan como una "ubicación de memoria" única. El acceso a cualquier campo de bits en esa secuencia se trata como el acceso a todos ellos con el fin de determinar la existencia de una carrera de datos. Eso refleja la incapacidad del hardware común para actualizar bits individuales sin leer y reescribir bits adyacentes. Los programadores de Java no tienen problemas similares.

Cómo evitar carreras de datos

Los lenguajes de programación modernos proporcionan varios mecanismos de sincronización para evitar las carreras de datos. Las herramientas más básicas son:

Bloqueos o exclusiones mutuas
Las exclusiones mutuas (std::mutex de C++11 o pthread_mutex_t) o los bloques synchronized en Java pueden usarse para garantizar que determinada sección del código no se ejecute al mismo tiempo con otras secciones de código que acceden a los mismos datos. Nos referiremos a este y otros recursos similares de manera general como "bloqueos". Con frecuencia, adquirir un bloqueo específico antes de acceder a una estructura de datos compartida y, luego, liberarlo evita las carreras de datos cuando se accede a la estructura de datos. Además, garantiza que las actualizaciones y los accesos sean atómicos; es decir, no se puede ejecutar ninguna otra actualización de la estructura de datos en el medio. Esa es, sin duda, la herramienta más común para prevenir las carreras de datos. El uso de bloques synchronized de Java o de bloques lock_guard o unique_lock de C++ garantiza que se liberen correctamente los bloqueos en caso de una excepción.
Variables volátiles/atómicas
Java proporciona campos volatile que admiten el acceso simultáneo sin introducir carreras de datos. Desde 2011, C y C++ admiten variables y campos atomic con semántica similar. Suelen ser más difíciles de usar que los bloqueos, ya que solo garantizan que los accesos individuales a una sola variable sean atómicos. (En C++, eso suele extenderse a operaciones simples de lectura, modificación y escritura, como incrementos. Java requiere métodos especiales para eso). A diferencia de los bloqueos, las variables volatile o atomic no pueden usarse directamente para evitar que otros subprocesos interfieran con secuencias de código más extensas.

Es importante tener en cuenta que volatile tiene significados muy diferentes en C++ y Java. En C++, volatile no evita las carreras de datos, aunque en el código más antiguo a menudo suele usarse como una solución para la falta de objetos atomic. Eso ya no se recomienda; en C++, usa atomic<T> para variables a las que puedan acceder varios subprocesos. volatile de C++ está diseñado para registros de dispositivos y elementos similares.

Las variables atomic de C/C++ o volatile de Java pueden usarse para evitar las carreras de datos en otras variables. Si se declara que flag tiene el tipo atomic<bool>, atomic_bool (C/C++) o volatile boolean (Java) y, al principio, es falso, el siguiente fragmento no tendrá carreras de datos:

Subproceso 1 Subproceso 2
A = ...
  flag = true
while (!flag) {}
... = A

Como el subproceso 2 espera que se establezca flag, el acceso a A en el subproceso 2 debe ocurrir después de la asignación a A en el subproceso 1, y no al mismo tiempo que ella. Por lo tanto, no hay carrera de datos en A. La carrera de flag no cuenta como carrera de datos, ya que los accesos volátiles o atómicos no son "accesos de memoria ordinarios".

La implementación es necesaria para evitar u ocultar el reordenamiento de memoria lo suficiente como para que el código, al igual que la prueba de litmus anterior, se comporte de la manera esperada. En general, eso suele hacer que los accesos de memoria volátiles o atómicos sean mucho más costosos que los ordinarios.

Si bien el ejemplo anterior no tiene carreras de datos, los bloqueos junto con Object.wait() en Java o las variables de condición en C/C++ suelen proporcionar una mejor solución que no implica esperar de manera indefinida mientras se consume la energía de la batería.

Cuando el reordenamiento de memoria se hace visible

La programación sin carreras de datos nos evita tener que lidiar de manera explícita con los problemas de reordenamiento del acceso a la memoria. Sin embargo, existen varios casos en los que se hace visible el reordenamiento:
  1. Si tu programa tiene un error que provoca una carrera de datos no intencional, las transformaciones del compilador y el hardware pueden hacerse visibles, y el comportamiento del programa puede ser sorprendente. Por ejemplo, si olvidamos declarar un elemento flag volátil en el ejemplo anterior, el subproceso 2 puede ver un elemento A no inicializado. Por otro lado, el compilador puede decidir que no es posible cambiar la marca durante el bucle del subproceso 2 y transformar el programa en
    Subproceso 1 Subproceso 2
    A = ...
      flag = true
    reg0 = marca; mientras (!reg0) {}
    ... = A
    Cuando se realiza la depuración, es posible que el bucle continúe para siempre a pesar de que flag sea verdadero.
  2. C++ proporciona recursos para relajar de manera explícita la consistencia secuencial incluso cuando no hay carreras. Las operaciones atómicas pueden tomar argumentos memory_order_ explícitos. De manera similar, el paquete java.util.concurrent.atomic proporciona un conjunto más restringido de recursos similares, en particular lazySet(). Y los programadores de Java a veces usan carreras de datos intencionales para obtener un efecto similar. Todas estas alternativas proporcionan mejoras de rendimiento a un alto costo en la complejidad de la programación. Las analizamos brevemente a continuación.
  3. Algunos códigos C y C++ están escritos en un estilo antiguo que no coincide completamente con los estándares de lenguaje actuales, en los que se usan las variables volatile en lugar de aquellas atomic, y se anula el ordenamiento de la memoria de manera explícita mediante la inserción de lo que se conoce como vallas o barreras. Eso requiere un razonamiento explícito sobre el reordenamiento de accesos y la comprensión de los modelos de memoria de hardware. Todavía se usa un estilo similar de código en el kernel de Linux. No se debe utilizar en nuevas aplicaciones de Android, y no se analiza en mayor detalle aquí.

Práctica

Depurar problemas de consistencia de la memoria puede ser muy difícil. Si la falta de un bloqueo, atomic o declaración volatile provoca que algún código lea datos inactivos, es posible que no encuentres la razón examinando los volcados de memoria con un depurador. Para cuando puedas emitir una consulta del depurador, es posible que todos los núcleos de la CPU hayan observado el conjunto completo de accesos, y el contenido de la memoria y los registros de la CPU parecerán estar en un estado "imposible".

Qué debes evitar hacer en C

A continuación, se incluyen algunos ejemplos de código incorrecto y maneras sencillas de corregirlos. Pero antes es necesario que hablemos sobre el uso de una función básica de lenguaje.

C/C++ y "volátil"

Las declaraciones volatile de C y C++ son herramientas de propósito muy especiales. Evitan que el compilador reordene o quite los accesos volátiles. Esto puede ser útil para el código que accede a registros de dispositivos de hardware, la memoria asignada a más de una ubicación o en conexión con setjmp. Pero volatile de C y C++, a diferencia de volatile de Java, no está diseñado para la comunicación de subprocesos.

En C y C++, se pueden reordenar los accesos a datos volatile con accesos a datos no volátiles y no hay garantías de atomicidad. Por lo tanto, no se puede usar volatile para compartir datos entre subprocesos en código portátil, incluso en un monoprocesador. En general, volatile de C no impide que el hardware reordene accesos. Entonces, por su cuenta, es incluso menos útil en entornos de SMP multiproceso. Por esa razón, C11 y C++11 admiten objetos atomic. Debes usar esos en su lugar.

Muchos códigos C y C++ más antiguos todavía abusan de volatile para la comunicación de subprocesos. Eso a menudo funciona bien para datos de un registro de máquinas, siempre y cuando se use con vallas explícitas o en casos en los que no sea importante el ordenamiento de la memoria. Sin embargo, no se garantiza que funcione de manera correcta con compiladores futuros.

Ejemplos

En la mayoría de los casos, sería mejor usar un bloqueo (como un pthread_mutex_t o std::mutex de C++11) en lugar de una operación atómica, pero utilizaremos esta última para mostrar cómo se usarían en una situación práctica.

MyThing* gGlobalThing = NULL;  // Wrong!  See below.
void initGlobalThing()    // runs in Thread 1
{
    MyStruct* thing = malloc(sizeof(*thing));
    memset(thing, 0, sizeof(*thing));
    thing->x = 5;
    thing->y = 10;
    /* initialization complete, publish */
    gGlobalThing = thing;
}
void useGlobalThing()    // runs in Thread 2
{
    if (gGlobalThing != NULL) {
        int i = gGlobalThing->x;    // could be 5, 0, or uninitialized data
        ...
    }
}

La idea aquí es que asignemos una estructura, inicialicemos sus campos y, justo al final, la "publiquemos" almacenándola en una variable global. En ese momento, cualquier otro subproceso puede verla, pero no hay problema porque está inicializada por completo, ¿no?

El problema es que el almacenamiento en gGlobalThing podría observarse antes de que se inicialicen los campos. Eso suele suceder porque el compilador o el procesador volvieron a ordenar los almacenamientos gGlobalThing y thing->x. Otro subproceso que lee desde thing->x podría ver 5, 0 o incluso datos sin inicializar.

El problema principal es una carrera de datos en gGlobalThing. Si el subproceso 1 llama a initGlobalThing() mientras que el subproceso 2 llama a useGlobalThing(), se puede leer gGlobalThing mientras se escribe.

Para solucionar ese problema, es necesario declarar gGlobalThing como atómico. En C++11:

atomic<MyThing*> gGlobalThing(NULL);

De esa forma, se garantiza que las escrituras serán visibles para otros subprocesos en el orden adecuado. También se garantiza la prevención de otros modos de falla que están permitidos, pero es poco probable que ocurran en hardware real de Android. Por ejemplo, se garantiza que no podamos ver un puntero gGlobalThing que se escribió solo de manera parcial.

Qué debes evitar hacer en Java

Ahora vamos a analizar algunas funciones relevantes del lenguaje Java que todavía no se analizaron.

Técnicamente, Java no requiere que el código no tenga carreras de datos. Y hay una pequeña cantidad de código Java muy bien escrito que funciona correctamente en presencia de carreras de datos. Sin embargo, escribir un código así es muy complicado, y solo se lo menciona al pasar a continuación. Para empeorar la situación, los expertos que especificaron el significado de ese código ya no creen que la especificación sea correcta. (La especificación está bien para el código sin carrera de datos).

Por ahora, seguiremos el modelo sin carreras de datos, para el que Java proporciona casi las mismas garantías que C y C++. De nuevo, el lenguaje proporciona algunas primitivas que relajan de manera explícita la consistencia secuencial, en particular las llamadas lazySet() y weakCompareAndSet() en java.util.concurrent.atomic. Al igual que con C y C++, ignoraremos eso por ahora.

Las palabras clave "sincronizadas" y "volátiles" de Java

La palabra clave "sincronizada" proporciona el mecanismo de bloqueo incorporado del lenguaje Java. Todos los objetos tienen un "monitor" asociado que se puede usar para proporcionar accesos mutuamente excluyentes. Si dos subprocesos intentan "sincronizarse" en el mismo objeto, uno de ellos esperará hasta que el otro termine.

Como mencionamos anteriormente, volatile T de Java es el análogo de atomic<T> de C++ 11. Se permiten los accesos simultáneos a los campos volatile, y no se generan carreras de datos. Al ignorar lazySet() et al. y las carreras de datos, el trabajo de la VM de Java es asegurarse de que el resultado siga teniendo consistencia secuencial.

En especial, si el subproceso 1 escribe en un campo volatile; luego, el subproceso 2 lo lee y observa el nuevo valor escrito, entonces también se garantiza que el subproceso 2 vea todas las escrituras que el subproceso 1 realizó con anterioridad. En cuanto al efecto de memoria, escribir en un volátil es similar a una liberación de monitor, y leer de un volátil es similar a una adquisición de monitor.

Hay una diferencia significativa en comparación con el atomic de C++: si escribimos volatile int x; en Java, entonces x++ es lo mismo que x = x + 1; este realiza una carga atómica, incrementa el resultado y, luego, realiza un almacenamiento atómico. A diferencia de C++, el incremento en su totalidad no es atómico. En su lugar, java.util.concurrent.atomic proporciona operaciones de incremento atómico.

Ejemplos

Aquí hay una implementación sencilla e incorrecta de un contador monotónico: (Teoría y práctica de Java: cómo administrar la volatilidad).

class Counter {
    private int mValue;
    public int get() {
        return mValue;
    }
    public void incr() {
        mValue++;
    }
}

Supongamos que se llama a get() y incr() desde múltiples subprocesos y queremos asegurarnos de que todos los subprocesos vean el conteo actual cuando se llama a get(). El problema más evidente es que mValue++ consta, en realidad, de tres operaciones:

  1. reg = mValue
  2. reg = reg + 1
  3. mValue = reg

Si se ejecutan dos subprocesos en incr() al mismo tiempo, podría perderse una de las actualizaciones. Para que el incremento sea atómico, debemos declarar a incr() "sincronizado".

Sin embargo, todavía está roto, en especial en SMP. Sigue habiendo una carrera de datos porque get() puede acceder a mValue al mismo tiempo que incr(). Según las reglas de Java, puede parecer que se reordena la llamada get() con respecto a otro código. Por ejemplo, si leemos dos contadores seguidos, los resultados pueden parecer incoherentes, ya que el hardware o el compilador reordenó las llamadas a get(). Para corregir el problema, podemos declarar a get() como sincronizado. Con este cambio, el código es sin duda correcto.

Lamentablemente, introdujimos la posibilidad de la contención de bloqueo, lo que podría dificultar el rendimiento. En lugar de declarar que get() está sincronizado, podríamos declarar mValue con "volátil". (Ten en cuenta que incr() igual debe usar synchronize, ya que, de lo contrario, mValue++ no será una sola operación atómica). Eso también evita todas las carreras de datos, por lo que se conserva la consistencia secuencial. incr() será un poco más lento, ya que incurre en la sobrecarga de entrada/salida del monitor y la sobrecarga asociada con un almacenamiento volátil, pero get() será más rápido. Por lo tanto, incluso cuando no hay contención, es una ventaja si hay muchas más lecturas que escrituras. (Consulta también AtomicInteger para conocer una manera de quitar el bloque sincronizado por completo).

Aquí hay otro ejemplo con una forma similar a los ejemplos anteriores de C:

class MyGoodies {
    public int x, y;
}
class MyClass {
    static MyGoodies sGoodies;
    void initGoodies() {    // runs in thread 1
        MyGoodies goods = new MyGoodies();
        goods.x = 5;
        goods.y = 10;
        sGoodies = goods;
    }
    void useGoodies() {    // runs in thread 2
        if (sGoodies != null) {
            int i = sGoodies.x;    // could be 5 or 0
            ....
        }
    }
}

Se presenta el mismo problema que tiene el código C; es decir, hay una carrera de datos en sGoodies. Por lo tanto, es posible que la asignación sGoodies = goods se observe antes de la inicialización de los campos en goods. Si declaras sGoodies con la palabra clave volatile, se restablecerá la consistencia secuencial y todo funcionará como se espera.

Ten en cuenta que solo la referencia sGoodies en sí es volátil. Los accesos a los campos que contiene no lo son. Una vez que sGoodies es volatile y el orden de la memoria se conserva correctamente, no es posible acceder a los campos al mismo tiempo. La instrucción z = sGoodies.x realizará una carga volátil de MyClass.sGoodies seguida de una carga no volátil de sGoodies.x. Si haces una referencia local MyGoodies localGoods = sGoodies, entonces una z = localGoods.x posterior no realizará ninguna carga volátil.

Una expresión más común en la programación Java es el mal reputado "bloqueo de doble control":

class MyClass {
    private Helper helper = null;
    public Helper getHelper() {
        if (helper == null) {
            synchronized (this) {
                if (helper == null) {
                    helper = new Helper();
                }
            }
        }
        return helper;
    }
}

La idea es tener una sola instancia de un objeto Helper asociada con una instancia de MyClass. Como debemos crearlo una sola vez, lo creamos y lo mostramos a través de una función getHelper() dedicada. Para evitar una carrera en la que dos subprocesos creen la instancia, debemos sincronizar la creación del objeto. Sin embargo, no queremos afrontar la sobrecarga del bloque "sincronizado" en cada llamada, por eso solo realizamos esa parte si helper es nulo en ese momento.

Esto tiene una carrera de datos en el campo helper. Se puede configurar de forma simultánea con helper == null en otro subproceso.

Para ver cómo puede fallar esto, imaginemos el mismo código un poco reescrito, como si se compilara en un lenguaje tipo C (se agregaron un par de campos de valores enteros para representar la actividad del constructor Helper’s):

if (helper == null) {
    synchronized() {
        if (helper == null) {
            newHelper = malloc(sizeof(Helper));
            newHelper->x = 5;
            newHelper->y = 10;
            helper = newHelper;
        }
    }
    return helper;
}

No hay nada que impida que el hardware o el compilador reordenen el almacén al helper con esos valores en los campos x/y. Otro subproceso podría hallar que helper no es nulo, pero sus campos todavía están sin configurar y no están listos para usar. Para obtener más detalles y más modos de falla, consulta el vínculo de "Instrucción 'Bloqueo de doble control está roto'" que aparece en el apéndice o el elemento 71 ("Usa la inicialización diferida con precaución") en Effective Java 2nd Edition de Josh Bloch.

Existen dos opciones para solucionar este problema:

  1. Lo más sencillo es borrar las verificaciones externas. Esto garantiza que nunca examinemos el valor de helper por fuera de un bloque sincronizado.
  2. Declara helper como volátil. Con este pequeño cambio, el código del ejemplo J-3 funcionará bien en Java 1.5 y en las versiones posteriores. (Tómate un minuto para convencerte de que eso es verdad).

Aquí hay otro ejemplo del comportamiento de volatile:

class MyClass {
    int data1, data2;
    volatile int vol1, vol2;
    void setValues() {    // runs in Thread 1
        data1 = 1;
        vol1 = 2;
        data2 = 3;
    }
    void useValues() {    // runs in Thread 2
        if (vol1 == 2) {
            int l1 = data1;    // okay
            int l2 = data2;    // wrong
        }
    }
}

En cuanto a useValues(), si el subproceso 2 aún no observó la actualización a vol1, no puede saber si ya se establecieron data1 o data2. Una vez que ve la actualización a vol1, sabe que se puede acceder con seguridad a data1 y se lo puede leer correctamente sin introducir una carrera de datos. Sin embargo, no puede hacer suposiciones sobre data2, ya que ese almacenamiento se realizó después del almacenamiento volátil.

Ten en cuenta que no se puede usar volatile para evitar el reordenamiento de otros accesos de memoria que compiten entre sí. No se garantiza que eso genere una instrucción de valla de memoria de la máquina. Se puede usar para evitar carreras de datos mediante la ejecución de código solo cuando otro subproceso haya cumplido con una condición determinada.

Qué hacer

En C/C++, otorga preferencia a las clases de sincronización de C++11, como std::mutex. De lo contrario, usa las operaciones pthread correspondientes. Estas incluyen las vallas adecuadas de memoria, que proporcionan comportamiento correcto (con consistencia secuencial, a menos que se especifique lo contrario) y eficiente en todas las versiones de la plataforma Android. Asegúrate de usarlas de manera correcta. Por ejemplo, recuerda que las esperas de las variables de condición pueden volver falsamente sin estar señalizadas y, por lo tanto, deben aparecer en un bucle.

Lo mejor es evitar el uso directo de funciones atómicas, a menos que la estructura de datos que estés implementando sea muy sencilla, como un contador. Bloquear y desbloquear una exclusión mutua de pthread requieren una sola operación atómica cada una, y, a menudo, tienen un costo menor que un solo error de caché, si no hay contención. Por lo tanto, no se ahorra demasiado si se reemplazan las llamadas de exclusiones mutuas con operaciones atómicas. Los diseños sin bloqueos para estructuras de datos no triviales requieren mucha más atención para garantizar que las operaciones de nivel más alto en la estructura de datos parezcan atómicas (en su totalidad, no solo los fragmentos explícitamente atómicos).

Si usas operaciones atómicas, es posible que relajar el ordenamiento con memory_order o lazySet() proporcione ventajas de rendimiento; sin embargo, esto requiere una comprensión más profunda que la que expresamos hasta ahora. Gran parte del código existente en el que se los usa demuestra tener errores con el tiempo. En la medida de lo posible, evítalos. Si tus casos prácticos no coinciden exactamente con los que se incluyen en la próxima sección, es necesario que seas un experto o que cuentes con la ayuda de uno.

Evita usar volatile para la comunicación de subprocesos en C/C++.

En Java, los problemas de simultaneidad a menudo se resuelven con una clase de utilidad apropiada del paquete java.util.concurrent. El código está bien escrito y probado en SMP.

Tal vez, lo más seguro es hacer que tus objetos sean inmutables. Los objetos de clases como Integer y String de Java contienen datos que no se pueden cambiar una vez que se crea un objeto, lo que evita todas las posibles carreras de datos en esos objetos. En el libro Effective Java, 2nd Ed., se incluyen instrucciones específicas. Consulta "Elemento 15: Minimiza la mutabilidad". En especial, ten en cuenta la importancia de declarar los campos de Java como "finales" (Bloch).

Incluso si un objeto es inmutable, recuerda que comunicarlo a otro subproceso sin ningún tipo de sincronización es una carrera de datos. A veces, eso puede ser aceptable en Java (ver a continuación), pero requiere mucho cuidado y es probable que tenga como resultado un código frágil. Si no es muy importante para el rendimiento, agrega una declaración volatile. En C++, comunicar un puntero o referencia a un objeto inmutable sin la sincronización adecuada, como cualquier carrera de datos, es un error. En este caso, es razonablemente probable que se produzcan fallas intermitentes, ya que, por ejemplo, el subproceso receptor puede ver un puntero de una tabla de métodos no inicializado debido al reordenamiento de almacenes.

Si no resulta adecuada ni una clase de biblioteca existente ni una clase inmutable, se debe usar la instrucción synchronized de Java o lock_guard/unique_lock de C++ para proteger los accesos a cualquier campo al que pueda acceder más de un subproceso. Si las exclusiones mutuas no son adecuadas para tu caso, debes declarar que los campos compartidos son volatile o atomic, pero debes comprender bien las interacciones entre los subprocesos. Estas instrucciones no te salvarán de los errores de programación concurrentes comunes, pero te ayudarán a evitar las fallas misteriosas asociadas con la optimización de compiladores y los contratiempos de SMP.

Debes evitar "publicar" una referencia a un objeto, es decir, ponerlo a disposición de otros subprocesos, en su constructor. Esto es menos importante en C++ o, si sigues nuestro consejo de que sea "sin carreras de datos" en Java. Sin embargo, siempre es un buen consejo, y se vuelve fundamental si se ejecuta el código Java en otros contextos en los que es importante el modelo de seguridad de Java, y el código que no es de confianza podría introducir una carrera de datos si accede a esa referencia de objeto "filtrada". También es fundamental si decides ignorar nuestras advertencias y usas algunas de las técnicas detalladas en la siguiente sección. Consulta (Técnicas de construcción seguras en Java) para obtener más información.

Un poco más de información sobre los ordenamientos de memoria no seguros

C++11 y versiones posteriores proporcionan mecanismos explícitos para relajar las garantías de consistencia secuencial en los programas sin carreras de datos. Los argumentos explícitos memory_order_relaxed, memory_order_acquire (solo cargas) y memory_order_release (solo almacenamientos) para operaciones atómicas proporcionan garantías menos seguras que el valor predeterminado, generalmente implícito, memory_order_seq_cst. memory_order_acq_rel proporciona garantías memory_order_acquire y memory_order_release para operaciones de escritura, lectura y modificación atómicas. memory_order_consume aún no se especificó adecuadamente o no se implementó de manera que sea útil, y debe ignorarse por el momento.

Los métodos lazySet de Java.util.concurrent.atomic son similares a los de almacenes memory_order_release de C++. Las variables ordinarias de Java se suelen usar como reemplazo de los accesos memory_order_relaxed, aunque en realidad son menos seguras. A diferencia de C++, no hay ningún mecanismo real para los accesos desordenados a variables que están declaradas como volatile.

En general, deberías evitarlas, a menos que haya razones urgentes relacionadas con el rendimiento para usarlas. En arquitecturas de máquinas poco ordenadas como ARM, usarlas suele ahorrar el orden de unas decenas de ciclos de máquinas para cada operación atómica. En x86, la ganancia de rendimiento se limita a los almacenamientos y es probable que no sea tan evidente. Aunque parezca contradictorio, es posible que disminuya el beneficio con conteos más altos de núcleos, ya que el sistema de la memoria se convierte en un factor más limitante.

La semántica completa de los atómicos poco ordenados es complicada. En general, requiere una comprensión precisa de las reglas del lenguaje, que no trataremos aquí. Por ejemplo:

  • El compilador o hardware puede mover los accesos memory_order_relaxed a una sección crítica limitada por una adquisición y liberación de bloqueo (pero no quitarlos de ella). Esto significa que dos almacenes de memory_order_relaxed se pueden volver visibles fuera de orden, incluso si están separados por una sección crítica.
  • Cuando se abusa de una variable ordinaria de Java como contador compartido, es posible que otro subproceso lo perciba como una disminución, aunque haya un incremento de un solo subproceso. Sin embargo, este no es el caso de memory_order_relaxed atómico de C++.

Con esa advertencia, a continuación incluimos una pequeña cantidad de modismos que parecen abarcar muchos de los casos prácticos de atómicos poco ordenados. Varios de estos solo pueden aplicarse a C++.

Accesos sin carreras

Es bastante común que una variable sea atómica porque a veces se lee al mismo tiempo que una escritura, pero no todos los accesos tienen este problema. Por ejemplo, es posible que una variable deba ser atómica porque se lee fuera de una sección crítica, pero todas las actualizaciones están protegidas por un bloqueo. En ese caso, una lectura que está protegida por el mismo bloqueo no puede ser parte de una carrera, ya que no puede haber escrituras concurrentes. En ese caso, el acceso sin carrera (en este supuesto, carga) puede anotarse con memory_order_relaxed sin cambiar la corrección del código C++. La implementación del bloqueo ya aplica de forma forzosa el orden requerido de memoria con respecto al acceso de otros subprocesos, y memory_order_relaxed especifica que no es necesario implementar ninguna restricción adicional para el acceso atómico.

No existe una situación similar en Java.

El resultado no es un indicador confiable de la corrección

Cuando usamos una carga de carreras solo para generar una sugerencia, también suele ser correcto no implementar ningún ordenamiento de memoria para la carga. Si el valor no es confiable, tampoco podemos usar el resultado de manera confiable para inferir algo sobre otras variables. Por lo tanto, no hay problema si no se garantiza el ordenamiento de memoria y se administra un argumento memory_order_relaxed a la carga.

Un ejemplo común de esto es el uso de compare_exchange de C++ para reemplazar x con f(x) de forma atómica. La carga inicial de x para calcular f(x) no necesita ser confiable. Si cometemos un error, compare_exchange fallará y volveremos a intentarlo. La carga inicial de x puede usar un argumento memory_order_relaxed; solo importa el ordenamiento de la memoria para el compare_exchange real.

Datos modificados de manera atómica pero no leídos

A veces, múltiples subprocesos modifican los datos en paralelo, pero no se los examina hasta que se completa el procesamiento en paralelo. Un buen ejemplo de esto es un contador que es aumentado de manera atómica (p. ej., con fetch_add() en C++ o atomic_fetch_add_explicit() en C) por múltiples subprocesos en paralelo, pero el resultado de esas llamadas siempre se ignora. El valor resultante solo se lee al final, después de que se completan todas las actualizaciones.

En este caso, no hay forma de saber si se reordenaron los accesos a esos datos y, por lo tanto, el código C++ puede usar un argumento memory_order_relaxed.

Los contadores de eventos simples son un buen ejemplo de esto. Como es tan común, vale la pena hacer algunas observaciones sobre este caso:

  • Usar memory_order_relaxed mejora el rendimiento, pero es posible que no resuelva el problema de rendimiento más importante: todas las actualizaciones requieren acceso exclusivo a la línea de caché que contiene el contador. Esto provoca un error de caché cada vez que un subproceso nuevo accede al contador. Si las actualizaciones son frecuentes y alternan entre los subprocesos, es mucho más rápido no actualizar el contador compartido en cada oportunidad. Por ejemplo, pueden usarse contadores de subprocesos locales y sumarlos al final.
  • Esta técnica se puede combinar con la sección anterior; es posible leer de manera simultánea valores aproximados y no confiables mientras se actualizan, y todas las operaciones usan memory_order_relaxed. Sin embargo, es importante tratar los valores resultantes como no confiables. El hecho de que el conteo parezca haberse incrementado una vez no significa que se pueda contar con que otro subproceso haya llegado al punto en el que se realizó el incremento. En vez de eso, es posible que se haya reordenado el incremento con el código anterior. (En cuanto al caso similar que mencionamos antes, C++ sí garantiza que una segunda carga de ese contador no devuelva un valor menor que una carga anterior del mismo subproceso. A menos, por supuesto, que se haya desbordado el contador).
  • Es común encontrar código que intente procesar valores aproximados del contador mediante lecturas y escrituras atómicas individuales (o no), pero sin hacer que el incremento completo sea atómico. El argumento habitual es esto es "suficientemente aproximado" para los contadores de rendimiento o elementos similares. En general, no lo es. Cuando las actualizaciones tienen una frecuencia suficiente (un caso que seguro te interesa), suele perderse una gran parte de los recuentos. En un dispositivo de cuatro núcleos, es común que se pierda más de la mitad de los conteos. (Un ejercicio sencillo es desarrollar un escenario de dos subprocesos en el que el contador se actualice un millón de veces, pero el valor final del contador sea uno).

Comunicación mediante marcas simples

Un almacenamiento memory_order_release (o una operación de lectura, modificación y escritura) garantiza que si, con posterioridad, una carga de memory_order_acquire (o una operación de lectura, modificación y escritura) lee el valor escrito, entonces, el valor también observará cualquier almacenamiento (ordinario o atómico) que haya antecedido al almacenamiento memory_order_release. Por el contrario, cualquier carga que anteceda a memory_order_release no observará ningún almacenamiento posterior a la carga de memory_order_acquire. A diferencia de memory_order_relaxed, esta permite que se usen esas operaciones atómicas para comunicar el progreso de un subproceso a otro.

Por ejemplo, podemos volver a escribir el ejemplo de doble control de bloqueo nombrado anteriormente en C++ de la siguiente manera:

class MyClass {
  private:
    atomic<Helper*> helper {nullptr};
    mutex mtx;
  public:
    Helper* getHelper() {
      Helper* myHelper = helper.load(memory_order_acquire);
      if (myHelper == nullptr) {
        lock_guard<mutex> lg(mtx);
        myHelper = helper.load(memory_order_relaxed);
        if (myHelper == nullptr) {
          myHelper = new Helper();
          helper.store(myHelper, memory_order_release);
        }
      }
      return myHelper;
    }
};

La adquisición de carga y liberación de almacenamiento garantizan que si vemos un helper que no es nulo, también veremos los campos que se inicializaron correctamente. Además, incorporamos la observación previa de que las cargas que no son de carrera pueden usar memory_order_relaxed.

Un programador de Java posiblemente podría representar a helper como un java.util.concurrent.atomic.AtomicReference<Helper> y usar lazySet() como liberación de almacenamiento. Las operaciones de carga seguirán usando llamadas get() sin formato.

En ambos casos, nuestro ajuste de rendimiento se concentró en la ruta de acceso de inicialización, que es poco probable que sea fundamental para el rendimiento. Una alternativa más legible podría ser la siguiente:

    Helper* getHelper() {
      Helper* myHelper = helper.load(memory_order_acquire);
      if (myHelper != nullptr) {
        return myHelper;
      }
      lock_guard&ltmutex> lg(mtx);
      if (helper == nullptr) {
        helper = new Helper();
      }
      return helper;
    }

Esta opción proporciona la misma ruta de acceso rápida, pero recurre a operaciones predeterminadas con consistencia secuencial en la ruta de acceso lenta que no es fundamental para el rendimiento.

Incluso en ese caso, es probable que helper.load(memory_order_acquire) genere el mismo código en arquitecturas compatibles con Android actuales como referencia clara (con consistencia secuencial) a helper. La optimización más beneficiosa que se incluye aquí sería la introducción de myHelper para eliminar una segunda carga, aunque es probable que un compilador futuro lo haga de manera automática.

El ordenamiento de adquisición y liberación no evita que los almacenamientos se retrasen visiblemente ni garantiza que se vuelvan visibles para otros subprocesos en un orden coherente. Por lo tanto, no admite un patrón de código complicado pero bastante común ejemplificado por el algoritmo de exclusión mutua de Dekker: Todos los subprocesos establecen primero un marcador para señalar que quieren realizar una acción; si un subproceso t luego observa que ningún otro subproceso está intentando realizar una acción, puede proceder de manera segura porque sabe que no habrá ninguna interferencia. En consecuencia, ningún otro subproceso podrá proceder, ya que aún estará establecida la marca de t. Este proceso fallará si se accede a la marca mediante el ordenamiento de adquisición y liberación, ya que de esta manera no se evita que la marca de un subproceso esté visible para otros una vez que se procedió erróneamente. Lo que lo impide es el valor predeterminado memory_order_seq_cst.

Campos inmutables

Si se inicializa un campo de objeto en el primer uso y nunca se modifica, sería posible inicializarlo y leerlo mediante accesos poco ordenados. En C++, se podría declarar como atomic y acceder a este mediante memory_order_relaxed; o bien en Java, se podría declarar sin volatile y su acceso no requeriría medidas especiales. Para ello, es necesario que se cumpla todo lo siguiente:

  • El valor de campo en sí mismo debería permitir saber si ya se inicializó. Para acceder al campo, el valor de prueba y devolución de la ruta de acceso rápida debe leer el campo una sola vez. En Java, esto último es esencial. Incluso si ya se inicializó el campo, una segunda carga podría leer el valor anterior a la inicialización. En C++, la regla "leer una sola vez" es simplemente una práctica recomendada.
  • Tanto la inicialización como las cargas posteriores deben ser atómicas, en el sentido de que no deben ser visibles las cargas parciales. Para Java, el campo no debe ser long ni double. En el caso de C++, se requiere una asignación atómica; si se la construye en el lugar, no funcionará porque la construcción de una asignación atomic no es atómica.
  • Las inicializaciones repetidas deben ser seguras, ya que es posible que varios subprocesos lean el valor no inicializado de manera simultánea. En el caso de C++, esta acción suele surgir del requisito de "copia trivial" impuesto para todos los tipos atómicos; los tipos con punteros anidados requieren que se anule la asignación en el constructor de copias, de manera que no se puedan copiar de forma trivial. En el caso de Java, se aceptan algunos tipos de referencias.
  • Las referencias de Java se limitan a tipos inmutables que solo contienen campos finales. El constructor del tipo inmutable no debería publicar una referencia al objeto. En ese caso, las reglas de campos finales de Java garantizan que si un lector ve la referencia, también verá los campos finales inicializados. En C++, no existe ninguna regla análoga a estas reglas; por esta razón, tampoco se aceptan los punteros a objetos con propietario (además de que infringen los requisitos de "copia trivial").

Notas finales

Si bien en este documento se hace un análisis detallado, no llega a ser exhaustivo, ya que es un tema muy amplio y profundo. A continuación, se exponen algunas áreas para su futura exploración:

  • Los modelos de memoria reales de C++ y Java se expresan en términos de una relación de sucede-antes que especifica cuándo se garantiza que dos acciones ocurrirán en un orden determinado. Cuando definimos una carrera de datos, hicimos referencia de manera informal a dos accesos a la memoria que ocurren "en simultáneo". De forma oficial, se define como que ninguno sucede antes que el otro. Es útil aprender las definiciones reales de sucede-antes y sincronizados-con de los modelos de memoria en Java o C++. Si bien la noción intuitiva de "en simultáneo" por lo general es suficiente, estas definiciones son útiles, particularmente si estás considerando usar operaciones atómicas poco ordenadas en C++. (En la especificación actual de Java, solo se define a lazySet() de manera muy informal).
  • Explora qué acciones pueden realizar los compiladores y cuáles no cuando se reordena el código. (En la especificación de JSR-133, se incluyen algunos ejemplos claros de transformaciones legales que tuvieron resultados inesperados).
  • Obtén información sobre cómo escribir clases inmutables en Java y C++. (No se trata solo de "no realizar cambios después de la construcción").
  • Internaliza las recomendaciones proporcionadas en la sección "Simultaneidad" de Effective Java, 2nd Edition. (Por ejemplo, deberías evitar llamar a métodos que deben anularse cuando están dentro de un bloqueo sincronizado).
  • Lee las API de java.util.concurrent y java.util.concurrent.atomic para ver las opciones disponibles. Procura usar anotaciones de simultaneidad, como @ThreadSafe y @GuardedBy (de net.jcrip.annotations).

En la sección Lectura complementaria del apéndice, se incluyen vínculos a documentos y sitios en los que obtendrás información adicional sobre estos temas.

Apéndice

Cómo implementar almacenes de sincronización

(Si bien no todos los programadores los implementarán, el análisis es esclarecedor).

En el caso de los tipos pequeños incorporados como int y el hardware compatible con Android, las instrucciones de carga y almacenamiento ordinarias garantizan que un almacenamiento esté completamente visible (o no) para otro procesador que cargue la misma ubicación. Por lo tanto, se proporciona una noción básica de la "atomicidad" de manera gratuita.

Sin embargo, como vimos anteriormente, no es suficiente. Para garantizar la consistencia secuencial, necesitamos evitar que se reordenen las operaciones y garantizar que las operaciones de memoria estén visibles para otros procesos en un orden consistente. Resulta que esta última acción se realiza automáticamente en el hardware compatible con Android, siempre y cuando tomemos decisiones acertadas para aplicar la primera, por lo que no la analizamos aquí.

El orden de las operaciones de memoria se conserva al evitar que tanto el compilador como el hardware las reordenen. En este documento hacemos foco en este último.

El ordenamiento de la memoria en ARMv7, x86 y MIPS se aplica de forma forzosa con las instrucciones "de valla" que, en términos generales, evitan que las instrucciones posteriores a la valla se vuelvan visibles antes de las que la anteceden. (También suelen llamarse instrucciones "de barrera", pero podrían confundirse con las barreras de estilo pthread_barrier, que cumplen otros propósitos). El significado preciso de las instrucciones de valla es un tema bastante complejo que debe abordar la manera en que interactúan las garantías provistas por los diferentes tipos de vallas, y cómo se combinan con otras garantías de ordenamiento que habitualmente proporciona el hardware. Esta es una descripción general, por lo que pasaremos por alto estos detalles.

El tipo de garantía de ordenamiento más básico es el que se proporciona en las operaciones atómicas memory_order_acquire y memory_order_release de C++. Las operaciones de memoria previas a un almacenamiento de liberación deberían estar visibles tras una carga de adquisición. En ARMv7, se aplica de la siguiente manera:

  • Se debe anteceder la instrucción de almacenamiento con una instrucción de valla adecuada. De esta manera, se evita que se reordenen todos los accesos de memoria anteriores con la instrucción de almacenamiento. (Además, se evita innecesariamente que se reordenen con la última instrucción de almacenamiento).
  • Se debe incluir una instrucción de valla adecuada luego de la instrucción de carga a fin de evitar que se reordene la carga con accesos posteriores. (Y, una vez más, se proporciona al ordenamiento innecesario las cargas anteriores, al menos).

En conjunto, estas opciones son suficientes para el ordenamiento de adquisición/actualización en C++. Son necesarias, pero no suficientes, para volatile de Java ni atomic con consistencia secuencial de C++.

Para conocer qué más se necesita, considera el fragmento del algoritmo de Dekker que mencionamos de manera breve más arriba. flag1 y flag2 son variables atomic de C++ o volatile de Java, establecidas inicialmente en falso.

Subproceso 1 Subproceso 2
flag1 = true
if (flag2 == false)
    critical-stuff
flag2 = true
if (flag1 == false)
    critical-stuff

La consistencia secuencial implica que debe ejecutarse primero una de las asignaciones a flagn, y que la prueba debe verla en el otro subproceso. Es por eso que nunca veremos a estos subprocesos ejecutar asignaciones críticas de manera simultánea.

No obstante, la protección requerida para el ordenamiento de adquisición/liberación solo agrega vallas al principio y al final de cada subproceso, lo que no es útil en este caso. Además, necesitamos garantizar que si un almacenamiento volatile/atomic es seguido por una carga volatile/atomic, estos no se reordenen. Para ello, normalmente no solo agregamos una valla antes de un almacenamiento con consistencia secuencial, sino también después de este. (Esta acción es mucho más compleja que lo que se necesita, ya que la valla suele ordenar todos los accesos a la memoria anteriores en relación con todos los posteriores).

En su lugar, podríamos asociar la valla adicional a cargas con consistencia secuencial. Como los almacenamientos son menos frecuentes, la convención que se describe es más común y se usa con mayor frecuencia en Android.

Como vimos en una sección anterior, debemos insertar una barrera de almacenamiento/carga entre ambas operaciones. El código que se ejecuta en la VM para un acceso volátil se verá más o menos de la siguiente manera:

carga volátil almacén volátil
reg = A
fence for "acquire" (1)
fence for "release" (2)
A = reg
fence for later atomic load (3)

Las arquitecturas de máquinas reales suelen proporcionar varios tipos de vallas, que ordenan distintos tipos de accesos cuyos costos pueden variar. La elección entre estos es muy sutil y está influenciada por la necesidad de garantizar que los almacenamientos estén visibles para otros núcleos en un orden consistente, y que el ordenamiento de la memoria impuesto por la combinación de varias vallas se componga correctamente. Para obtener más detalles, consulta asignaciones recopiladas de funciones atómicas a procesadores reales en la página de la Universidad de Cambridge.

En algunas arquitecturas, principalmente en x86, las barreras de "adquisición" y "liberación" son innecesarias, ya que el hardware siempre aplica suficiente ordenamiento de manera implícita. Por lo tanto, en x86, en realidad solo se genera la última valla (3). De manera similar, en x86, las operaciones atómicas de lectura, modificación y escritura incluyen una valla segura de manera implícita. Es por eso que nunca requieren vallas. En ARMv7, se requieren todas las vallas que se describieron con anterioridad.

ARMv8 proporciona instrucciones LDAR y STLR que aplican directamente los requisitos de cargas y almacenamientos volátiles de Java o C++ con consistencia secuencial. De esta manera, se evitan las restricciones de reordenamiento innecesarias que mencionamos más arriba. Por otro lado, el código de Android de 64 bits en ARM las usa; por lo tanto, decidimos focalizarnos en la colocación de vallas de ARMv7, ya que esclarece más los requisitos reales.

Lecturas adicionales

A continuación, se presentan documentos y páginas web que proporcionan información más detallada. Los artículos que suelen ser más útiles aparecen en la parte superior de la lista.

Modelos de consistencia de memoria compartida: instructivo
Escrito en 1995 por Adve & Gharachorloo, es un buen punto de partida si quieres profundizar en los modelos de consistencia de memoria.
http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf
Barreras de memoria
Es un pequeño artículo que resume los problemas.
https://en.wikipedia.org/wiki/Memory_barrier
Aspectos básicos de los subprocesos
Es una introducción a la programación multiproceso en C++ y Java, escrita por Hans Boehm. Análisis de carreras de datos y métodos de sincronización básicos.
http://www.hboehm.info/c++mm/threadsintro.html
Simultaneidad de Java en la práctica
Este libro, que se publicó en 2006, abarca una gran variedad de temas en gran detalle. Es muy recomendable para toda persona que escriba códigos multiproceso en Java.
http://www.javaconcurrencyinpractice.com
Preguntas frecuentes sobre JSR-133 (Modelo de memoria en Java)
Es una introducción gradual al modelo de memoria en Java, que incluye una explicación sobre la sincronización, las variables volátiles y la construcción de campos finales. (Un poco antiguo, especialmente cuando se analizan otros lenguajes).
http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html
Validez de las transformaciones de programas en el modelo de memoria en Java
Es una explicación bastante técnica de los problemas por resolver del modelo de memoria en Java. No se aplican estos problemas a los programas sin carreras de datos.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.112.1790&rep=rep1&type=pdf
Descripción general del paquete java.util.concurrent
Es la documentación del paquete java.util.concurrent. En la parte inferior de la página, hay una sección llamada "Propiedades de la consistencia de memoria" en la que se explican las garantías proporcionadas por las diferentes clases.
Resumen del paquete java.util.concurrent
Teoría y práctica de Java: Técnicas de construcción seguras en Java
En este artículo, se analizan en detalle los riesgos del escape de referencias durante la construcción de objetos y se proporcionan lineamientos para constructores seguros para subprocesos.
http://www.ibm.com/developerworks/java/library/j-jtp0618.html
Teoría y práctica de Java: Cómo administrar la volatilidad
Es un buen artículo en el que se describe lo que puedes y no puedes lograr con los campos volátiles en Java.
http://www.ibm.com/developerworks/java/library/j-jtp06197.html
Declaración "Se rompió el doble control de bloqueo"
Es una explicación detallada de las diferentes maneras en las que puede romperse el doble control de bloqueo sin volatile ni atomic. Incluye C/C++ y Java.
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
Guía de soluciones y pruebas decisivas de barreras [ARM]
Es una discusión sobre los problemas de SMR en ARM, con ejemplos de fragmentos breves de código ARM. Si los ejemplos de esta página no son muy específicos o si desea leer la descripción formal de la instrucción de DMB, lea esto. Además, se describen las instrucciones que se usan para las barreras de memoria en código ejecutable (que podrían resultar útiles si generas código sobre la marcha). Ten en cuenta que este documento es anterior a ARMv8, que también admite instrucciones de ordenamiento de memoria adicionales y se cambió a un modelo de memoria más fuerte. (Consulta el "Manual de referencia de arquitecturas ARM® ARMv8 para el perfil de arquitectura ARMv8-A" a fin de obtener detalles).
http://infocenter.arm.com/help/topic/com.arm.doc.genc007826/Barrier_Litmus_Tests_and_Cookbook_A08.pdf
Barreras de memoria del kernel de Linux
Es la documentación sobre las barreras de memoria del kernel de Linux, Incluye algunos ejemplos útiles y arte ASCII.
http://www.kernel.org/doc/Documentation/memory-barriers.txt
ISO/IEC JTC1/SC22/WG21 (estándares de C++) 14882 (lenguaje de programación C++), sección 1.10 y cláusula 29 ("Biblioteca de operaciones atómicas")
Es el proyecto de estándar para las funciones de operaciones atómicas de C++. Esta versión es similar al estándar de C++14, que incluye cambios menores en esta área desde C++11.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4527.pdf
(intro: http://www.hpl.hp.com/techreports/2008/HPL-2008-56.pdf)
ISO/IEC JTC1/SC22/WG14 (estándares de C) 9899 (lenguaje de programación C) capítulo 7.16 ("Funciones atómicas <stdatomic.h>")
Es un proyecto de estándar para las funciones de operaciones atómicas de C ISO/IEC 9899-201x. Para obtener más información, consulta también los informes de defectos posteriores.
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf
Asignaciones de C/C++11 a procesadores (Universidad de Cambridge)
Es una recopilación de traducciones de las funciones atómicas de C++ a diferentes conjuntos de instrucciones para procesadores comunes, escrita por Jaroslav Sevcik y Peter Sewell.
http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html
Algoritmo de Dekker
Es la "primera solución correcta conocida para el problema de exclusión mutua en la programación simultánea". En el artículo de Wikipedia, se incluye el algoritmo completo, con un debate sobre cómo debería actualizarse para funcionar con compiladores de optimización modernos y hardware SMP.
https://en.wikipedia.org/wiki/Dekker's_algorithm
Comentarios sobre ARM frente a Alpha y dependencias de dirección
Es un correo electrónico sobre la lista de distribución del kernel de ARM de Catalin Marinas. Se incluye un resumen detallado de las dependencias de dirección y control.
http://linux.derkeiler.com/Mailing-Lists/Kernel/2009-05/msg11811.html
Lo que todo programador debe saber sobre la memoria
Es un artículo muy extenso y detallado sobre los diferentes tipos de memoria, en especial las cachés de CPU, escrito por Ulrich Drepper.
http://www.akkadia.org/drepper/cpumemory.pdf
Razonamiento sobre el modelo de memoria poco consistente de ARM
Este documento fue escrito por Chong & Ishtiaq de ARM, Ltd. En él, se intenta describir el modelo de memoria de SMP de ARM de manera minuciosa, pero entendible. La definición de "observabilidad" que usamos aquí se extrajo de este documento. Una vez más, esto es anterior a ARMv8.
http://portal.acm.org/ft_gateway.cfm?id=1353528&type=pdf&coll=&dl=&CFID=96099715&CFTOKEN=57505711
La guía de soluciones de JSR-133 para escritores de compiladores
Doug Lea escribió este documento como complemento de la documentación sobre JSR-133 (modelo de memoria en Java). Contiene el conjunto inicial de lineamientos de implementación para el modelo de memoria en Java que usaron muchos escritores de compiladores, que aún se cita mucho, y puede brindarte información valiosa. Por desgracia, las cuatro variantes de valla que se analizan aquí no son una buena opción para las arquitecturas compatibles con Android, y las asignaciones C++11 que se mencionaron más arriba ahora son una mejor fuente de instrucciones precisas, incluso para Java.
http://g.oswego.edu/dl/jmm/cookbook.html
x86-TSO: Un modelo estricto y usable para programadores de multiprocesadores x86
Es una descripción precisa del modelo de memoria x86. Por desgracia, las descripciones precisas del modelo de memoria ARM son mucho más complicadas.
http://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf