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 el acceso a la memoria principal. Hasta hace unos años, todos los dispositivos Android eran UP (monoprocesadores).

La mayoría, si no todos, los dispositivos Android tenían múltiples CPU, pero solía usarse solo una para ejecutar aplicaciones. Las otras, en cambio, administraban varios bits de hardware del dispositivo (por ejemplo, la radio). Es posible que las CPU tuvieran arquitecturas diferentes y 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 manera regular cuando dos o más subprocesos se ejecutan de manera simultánea 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. El código que se probó de manera exhaustiva en x86 puede romperse en ARM. El código puede comenzar a fallar 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á que 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 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 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á acostumbrado la mayoría de los programadores se denomina coherencia secuencial, que se describe de la siguiente forma (Adve y Gharachorloo):

  • Todas las operaciones de memoria parecen ejecutarse una a la vez.
  • Todas las operaciones en 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 coherencia secuencial, sabes que el código realizará esas lecturas y escrituras en el orden esperado. Es posible que la CPU realmente 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 I/O 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 de litmus.

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 futuros de litmus, las ubicaciones de la memoria se representan con mayúsculas (A, B, C) y los registros de la CPU comienzan con "reg". Inicialmente, toda memoria 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. (Ten en cuenta que escribimos en un orden y leemos en otro).

Se supone que los subprocesos 1 y 2 se ejecutan en diferentes núcleos de CPU. Es necesario que siempre supongas eso cuando piensas en código multiproceso.

La coherencia secuencial garantiza que, una vez que terminan 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 coherencia secuencial, eso no puede suceder.

Los monoprocesadores, incluidos x86 y ARM, suelen tener coherencia 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 x86 y ARM, no tienen coherencia 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 de x86, aunque no tiene coherencia secuencial, igual garantiza que reg0 = 5 y reg1 = 0 siguen siendo posibles. Los almacenes 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 almacenes 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 en C, C++ o Java pueden y deben programar de una manera que oculte esas diferencias arquitectónicas.

Hasta ahora, supusimos de manera no realista 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 de que necesitara reg0 y, por eso, 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, las cargas a reg0 y reg1 pueden reordenarse.

El reordenamiento de accesos a diferentes ubicaciones de memoria, ya sea en el hardware o el compilador, está permitido, ya que no afecta la ejecución de un 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 una novedad para SMP. Incluso en un monoprocesador, un compilador puede reordenar las cargas en reg0 y reg1 en nuestro ejemplo, y el subproceso 1 puede 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 tener que pensar en esos detalles. Si sigues algunas reglas simples, en general, no hay problema si no tienes en cuenta la sección anterior, excepto la parte de la "coherencia secuencial". Desafortunadamente, 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". Mientras 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 coherencia 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" se refiere 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 discusión de reordenamiento de memoria incluida arriba y suponer que hay coherencia secuencial. El siguiente programa no tiene una carrera de datos si A y B son variables booleanas ordinarias que al principio son falsas:

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

Como las operaciones no se reordenan, ambas condiciones se evaluarán 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 la carga de A y el almacenamiento en B en el subproceso 1 se reordenaran de alguna manera. El compilador no puede reordenar el subproceso 1 reescribiéndolo como "B = true; if (!A) B = false". 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 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 acerca de 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 al menos 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 y, por lo tanto, puede considerarse de manera informal una "carrera de datos a nivel de biblioteca". Por el contrario, actualizar un set<T> y leer uno diferente en otro no resulta en una carrera de datos, porque, en ese caso, la biblioteca promete no introducir una carrera de datos (de bajo nivel).

En general, los accesos simultáneos a diferentes campos en 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. Acceder a cualquier campo de bits en dicha secuencia se trata como el acceso a todos a fin de determinar la existencia de una carrera de datos. Eso refleja la incapacidad del hardware común para actualizar bits individuales sin también 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 o pthread_mutex_t de C++11) 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 lock_guard de C++ o unique_lock garantiza que los bloqueos se liberen de manera correcta en el 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. Estos 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-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 largas.

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 múltiples 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> o atomic_bool (C/C++) o volatile boolean (Java), y, al principio, es falso, el siguiente fragmento no tiene 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 en flag no cuenta como una 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, como 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 una sorpresa. Por ejemplo, si olvidamos declarar una flag volátil en el ejemplo anterior, el subproceso 2 puede ver una A no inicializada. O 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 es verdadero.
  2. C++ proporciona recursos para relajar de manera explícita la coherencia secuencial incluso cuando no hay carreras. Las operaciones atómicas admiten 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 de manera breve a continuación.
  3. Algunos códigos C y C++ están escritos en un estilo antiguo que no coincide por completo con los estándares de lenguaje actuales, en los que se usan las variables volatile en lugar de 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. Un estilo similar de código todavía se usa en el kernel de Linux. No debe utilizarse en nuevas apps de Android, y tampoco se analiza en más detalle aquí.

Práctica

Depurar problemas de consistencia de la memoria puede ser muy difícil. Si un bloqueo o una declaración atomic o volatile faltantes provocan que algún código lea datos obsoletos, es posible que no puedas averiguar por qué si examinas 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 corregirlo. Pero antes es necesario que hablemos sobre el uso de una característica 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, 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++, los accesos a datos volatile se pueden reordenar con accesos a datos no volátiles y no hay garantías de atomicidad. Por lo tanto, volatile no se puede usar 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 and C++11 admiten objetos atomic. Debes usar esos en su lugar.

Muchos códigos C and 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 el ordenamiento de la memoria no sea importante. Pero 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 asignamos una estructura, inicializamos sus campos y justo al final la "publicamos" 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 volvió a ordenar los almacenes a gGlobalThing y thing->x. Otro subproceso que lee de thing->x puede ver 5, 0 o incluso datos sin inicializar.

Aquí el problema principal es una carrera de datos en gGlobalThing. Si el subproceso 1 llama a initGlobalThing(), mientras 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 garantiza prevenir otros modos de falla que, de lo contrario, están permitidos, pero es poco probable que ocurran en hardware real de Android. Por ejemplo, garantiza que no podamos ver un puntero gGlobalThing que se escribió de manera parcial.

Qué debes evitar hacer en Java

Ahora vamos a analizar algunas características relevantes del lenguaje Java que todavía no se tocaron.

Técnicamente, Java no requiere que el código sea sin carreras de datos. Y hay una pequeña cantidad de código Java escrito con mucho cuidado que funciona bien en presencia de carreras de datos. Sin embargo, escribir dicho código es muy complicado. A continuación, lo analizamos de manera breve. Para empeorar la situación, los expertos que especificaron el significado de dicho 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 coherencia 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 puede usarse para proporcionar accesos mutuamente exclusivos. Si dos subprocesos intentan "sincronizarse" en el objeto, uno de ellos esperará hasta que el otro termine.

Como mencionamos arriba, volatile T de Java es el análogo de atomic<T> de C++11. Es decir, se permiten los accesos concurrentes a campos volatile, y no resultan en carreras de datos. Al ignorar lazySet() y otros, y carreras de datos, el trabajo de la VM de Java es asegurarse de que el resultado siga teniendo coherencia secuencial.

En especial, si el subproceso 1 escribe en un campo volatile y, luego, el subproceso 2 lee el mismo campo y ve el nuevo valor escrito, entonces también se garantiza que el subproceso 2 vea todas las escrituras que realizó antes el subproceso 1. En cuanto al efecto de memoria, escribir en un volátil es similar a una versión de monitor y leer de un volátil es como adquirir un 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 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 get() y incr() se llaman desde múltiples subprocesos y queremos asegurarnos de que todos los subprocesos vean el contador actual cuando se llama a get(). El problema más evidente es que mValue++ en realidad es tres operaciones:

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

Si dos subprocesos se ejecutan 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(). Bajo las reglas de Java, puede parecer que la llamada get() se reordena con respecto a otro código. Por ejemplo, si leemos dos contadores seguidos, los resultados pueden parecer incoherentes porque las llamadas a get() se reordenaron, ya sea por el hardware o el compilador. Para corregir el problema, podemos declarar a get() 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 impedir 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 es una sola operación atómica). Eso también evita todas las carreras de datos, por lo que se conserva la coherencia 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 almacén 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 ver una manera de quitar por completo el bloque sincronizado).

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
                ....
            }
        }
    }

Esto tiene el mismo problema que el código C, en particular porque hay una carrera de datos en sGoodies. Por lo tanto, es posible que la asignación sGoodies = goods se observe antes que la inicialización de los campo en goods. Si declaras sGoodies con la palabra clave volatile, se restaura la coherencia 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 en su interior no lo son. Una vez que sGoodies es volatile y el ordenamiento de la memoria se conserva de manera adecuada, no es posible acceder a los campos al mismo tiempo. La instrucción z = 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.

Algo más común en la programación Java es el infame "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 que queremos tener una sola instancia de un objeto Helper asociada con una instancia de MyClass. Como debemos crearlo una sola vez, lo creamos y lo devolvemos a través de una función exclusiva getHelper(). Para evitar una carrera en la que dos subprocesos crean 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 la actualidad.

Eso tiene una carrera de datos en el campo helper. Puede establecerse de manera simultánea con el helper == null en otro subproceso.

Para ver cómo puede fallar esto, considera el mismo código un poco reescrito, como si se compilara en un lenguaje tipo C (se agregaron un par de campos de 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 en los campos x/y. Otro subproceso podría encontrar helper no nulo, pero sus campos sin configurar y 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'" 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. Eso garantiza que nunca examinemos el valor de helper fuera de un bloque sincronizado.
  2. Declara a helper volátil. Aquí hay un pequeño cambio, el código en el ejemplo J-3 funcionará bien en Java 1.5 y versiones posteriores. (Tómate un minuto para convencerte de que eso es verdad).

Aquí hay otro ejemplo del comportamiento 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
            }
        }
    }

Al analizar useValues(), si el subproceso 2 aún no observó la actualización a vol1, no puede saber si se establecieron data1 o data2. Una vez que ve la actualización a vol1, sabe que se puede acceder de manera segura a data1 y leer de manera correcta sin introducir una carrera de datos. Sin embargo, no puede hacer suposiciones sobre data2, porque ese almacenamiento se realizó después del almacén 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 se genere una instrucción de valla de memoria de la máquina. Puede usarse para evitar carreras de datos mediante la ejecución de código solo cuando otro subproceso cumplió con una condición determinada.

Qué hacer

En C/C++, prefiere las clases de sincronización de C++11, como std::mutex. De lo contrario, usa las operaciones pthread correspondientes. Esas incluyen las vallas adecuadas de memoria, que proporcionan comportamiento correcto (con coherencia secuencial, a menos que se especifique lo contrario) y eficiente en todas las versiones de la plataforma Android. Asegúrate de usarlos 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 requiere una sola operación atómica cada una y a menudo tiene un costo menor que un solo error de caché, si no hay contención. Por eso, no se ahorra demasiado al reemplazar las llamadas de extensiones 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, pero requiere una comprensión más profunda de la que transmitimos hasta ahora. Se descubre que una gran parte del código existente tiene errores después del hecho. En la medida de lo posible, evítalas. Si tus casos prácticos no coinciden exactamente con los que se incluyen en la próxima sección, debes ser un experto o contar con la ayuda de uno.

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

En Java, los problemas de concurrencia 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.

Quizás 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". Ten en cuenta, en particular, 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 resulte en código frágil. Si no es fundamental 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 inicializados debido al reordenamiento de almacenes.

Si no es adecuada ni una clase de biblioteca existente ni una clase inmutable, debe usarse 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 no te sirven las exclusiones mutuas, 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 crítico en C++ o, si sigues nuestro consejo de que sea "sin carreras de datos" en Java. Pero siempre es un buen consejo, y se vuelve fundamental si el código Java se ejecuta 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 al acceder a esa referencia de objeto "filtrada". También es crítico si decides ignorar nuestras advertencias y usar 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 coherencia secuencial para programas sin carreras de datos. Los argumentos explícitos memory_order_relaxed, memory_order_acquire (solo cargas) y memory_order_release (solo almacenes) para operaciones atómicas proporcionan garantías estrictamente menos seguras que la opción predeterminada, en general implícita, memory_order_seq_cst. memory_order_acq_rel proporciona las dos garantías memory_order_acquire y memory_order_release para las operaciones atómicas de lectura-modificación-escritura. memory_order_consume todavía no está lo suficientemente bien especificada o implementada para ser útil y debe ignorarse por ahora.

Los métodos lazySet en Java.util.concurrent.atomic son similares a los almacenes memory_order_release de C++. Las variables ordinarias de Java a veces se usan 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 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 un par de docenas de ciclos de máquinas para cada operación atómica. En x86, la ganancia de rendimiento se limita a los almacenes y es probable que no sea tan evidente. Aunque parezca contradictorio, es posible que el beneficio disminuya 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 pueden mover los accesos de memory_order_relaxed a una sección crítica (pero no fuera de ella) limitada por una adquisición y liberación de bloqueo. Eso quiere decir que dos almacenes de memory_order_relaxed pueden volverse visibles fuera de orden, incluso si están separados por una sección crítica.
  • Cuando un contador compartido abusa de una variable ordinaria de Java, es posible que para otro subproceso eso se vea como una disminución, aunque haya un incremento de un solo subproceso. Pero eso no es cierto para 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 con una escritura, pero no todos los accesos tienen este problema. Por ejemplo, es posible que una variable necesite 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 caso, carga), puede anotarse con memory_order_relaxed sin cambiar la corrección del código C++. La implementación del bloqueo ya impone 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 hay 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, suele estar bien 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, está bien si no se garantiza el ordenamiento de la memoria, y la carga se suministra con un argumento memory_order_relaxed.

Una instancia común de esto es el uso de compare_exchange de C ++ para reemplazar de manera atómica x con f(x). No es necesario que la carga inicial de x para procesar f(x) sea 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 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 los examinan hasta que no se completa el procesamiento en paralelo. Un buen ejemplo de esto es un contador que incrementa 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:

  • El uso de memory_order_relaxed mejora el rendimiento, pero puede 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. La consecuencia de eso es 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 evitar la actualización del contador compartido cada vez. Para hacerlo, por ejemplo, usa contadores de subprocesos locales y súmalos 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 el resto de las operaciones usan memory_order_relaxed. Pero es importante tratar los valores resultantes como no confiables. El hecho de que el conteo parezca haber incrementado una vez no quiere decir que otro subproceso se pueda contar como si hubiera llegado al punto en el que se realizó el incremento. En su lugar, es posible que el incremento se haya reordenado con el código anterior. (En cuanto al caso similar que mencionamos antes, C++ garantiza que una segunda carga de dicho contador no devolverá un valor menor que una carga anterior en el mismo subproceso. A menos que el contador se desbordara).
  • Es común encontrar código que intente procesar valores aproximados del contador. Para hacerlo, realiza lecturas y escrituras atómicas individuales (o no), pero sin hacer el incremento como un atómico completo. El argumento habitual es que "se aproxima lo suficiente" para los contadores de rendimiento o elementos similares. En general, no lo es. Cuando las actualizaciones son lo suficientemente frecuentes (un caso que seguro te interesa), suele perderse una gran fracción de los conteos. En un dispositivo de cuatro núcleos, es común que se pierdan más de la mitad de los conteos. (Un ejercicio sencillo es desarrollar un escenario de dos subprocesos en el que el contador se actualiza un millón de veces, pero el valor final del contador es uno solo).

Comunicación mediante indicadores simples

El almacén memory_order_release A (o bien la operación de lectura-modificación-escritura) garantiza que si posteriormente una carga de memory_order_acquire (o bien, una operación de lectura-modificación-escritura) lee el valor escrito, entonces el valor también observará cualquier almacén (ordinario o atómico) que anteceda al almacén memory_order_release A. Por el contrario, cualquier carga que anteceda a memory_order_release no observará ningún almacén posterior a la carga memory_order_acquire. A diferencia de memory_order_relaxed, esta permite que esas operaciones atómicas se usen 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 carga de adquisición y el almacén de liberación garantizan que si vemos un helper no nulo, también veremos que sus campos 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 el almacén de liberación. 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 coherencia secuencial en la ruta de acceso lenta que no es fundamental para el rendimiento.

Incluso aquí, es probable que helper.load(memory_order_acquire) genere el mismo código en arquitecturas actuales compatibles con Android como referencia clara (con coherencia 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 almacenes obtengan visibilidad retrasada 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, sino bastante común que se ejemplifica en el algoritmo de exclusión mutua de Dekker: Todos los subprocesos primero establecen un indicador 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 el indicador de t aún estará establecido. Este proceso fallará si se accede al indicador mediante el ordenamiento de adquisición y liberación, ya que de esta manera no se evita que el indicador de un subproceso esté visible para otros una vez que se procedió erróneamente. El memory_order_seq_cst predeterminado sí lo evita.

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++, podría declararse como atomic y acceder a este mediante memory_order_relaxed; o bien, en Java, podría declarase sin volatile y acceder a este sin medidas especiales. Para ello, es necesario que se cumpla todo lo siguiente:

  • Debería poder identificarse si ya se inicializó partir del valor del campo. 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, lo último es esencial. Incluso si el campo ya se inicializó, una segunda carga podría leer el valor anterior a la inicialización. En C++, se recomienda usar la regla "leer una sola vez".
  • Tanto la inicialización como las cargas posteriores deben ser atómicas y no deben ser visibles en las actualizaciones parciales. En el caso de Java, el campo no debe ser long ni double. En el caso de C++, se requiere una asignación atómica; si la construyes 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 este 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 y, por este motivo, 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. A continuación, se muestran 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 "simultáneamente". Oficialmente, 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 "simultáneamente" por lo general es suficiente, estas definiciones son útiles, particularmente si estás considerando usar operaciones atómicas de poco orden 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 al reordenar el código. (En la especificación de JSR-133, se incluyen algunos ejemplos claros de transformaciones legales que tuvieron resultados inesperados).
  • Descubre cómo escribir clases inmutables en Java y C++. (No se trata solo de "no realizar cambios luego 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).
  • Consulta las API de java.util.concurrent y java.util.concurrent.atomic para ver lo que hay disponible. Considera usar anotaciones de simultaneidad como @ThreadSafe y @GuardedBy (de net.jcip.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 almacén ordinarios garantizan que un almacén estará completamente visible (o no) para otro procesador que carga 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 coherencia secuencial, necesitamos evitar que se reordenen las operaciones y garantizar que las operaciones de memoria estén visibles para otros procesos en un orden coherente. 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 el último.

El ordenamiento de la memoria en ARMv7, x86 y MIPS se aplica con las instrucciones de valla que difícilmente evitan que las instrucciones posteriores a la valla se vuelvan visibles antes de las que la anteceden. (Estas 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 las garantías provistas por diferentes tipos de vallas interactúan, y cómo estas se combinan con otras garantías de ordenamiento que suele proporcionar el hardware. Esta es una descripción general de alto nivel, por lo que no abordaremos 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 almacén 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 del almacén 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 del almacén. (Además, se evita innecesariamente que se reordenen con la última instrucción del almacén).
  • Se debe incluir una instrucción de valla adecuada luego de la instrucción de carga a fin de evitar que la carga se reordene con accesos posteriores. (Y nuevamente se proporciona ordenamiento innecesario con cargas anteriores, como mínimo).

En conjunto, estas opciones son suficientes para el ordenamiento de adquisición/liberación en C++. Sin embargo, son necesarias, pero no suficientes para volatile de Java o atomic con coherencia 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 coherencia secuencial implica que una de las asignaciones a flagn debe ejecutarse primero y 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 almacén volatile/atomic es seguido por una carga volatile/atomic, estos no se reordenarán. Para ello, normalmente no solo agregamos una valla antes de un almacén con coherencia secuencial, sino también después de este. (Esta acción es mucho más compleja que la 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 coherencia secuencial. Como los almacenes 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 almacén/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 almacenes estén visibles para otros núcleos en un orden coherente, 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-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 anteriormente.

ARMv8 proporciona instrucciones LDAR y STLR que aplican directamente los requisitos de cargas y almacenes volátiles de Java o C++ con coherencia 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 que decidimos focalizarnos en la colocación de vallas de ARMv7 porque esclarece los requisitos reales.

Lecturas adicionales

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

Modelos de coherencia de memoria compartida: Instructivo
Escrito en 1995 por Adve & Gharachorloo, es un buen punto de partida si quieres conocer más a fondo los modelos de coherencia de memoria.
http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf
Barreras de memoria
Es un artículo breve en donde se resumen los problemas.
http://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. Es una discusión sobre los métodos de sincronización básicos y las carreras de datos.
http://www.hboehm.info/c++mm/threadsintro.html
Simultaneidad de Java en la práctica
Publicado en 2006, este libro abarca una gran variedad de temas en gran detalle. Se recomienda para aquellos que escriben código 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. (Es un poco anticuada, particularmente en lo que respecta la discusión sobre 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 más bien técnica de los problemas aún existentes del modelo de memoria en Java. Estos no afectan 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 coherencia 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 construir subprocesos de manera segura.
http://www.ibm.com/developerworks/java/library/j-jtp0618.html
Teoría y práctica de Java: Cómo administrar la volatilidad
Es un artículo en el que se describe lo que puedes hacer y lo que no 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, escrita por Bill Pugh. 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 te parece que los ejemplos en este documento no son específicos o quieres leer la descripción formal de las instrucciones de DMB, te recomendamos que la leas. 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. (Para obtener información detallada, consulta el "Manual de referencia de arquitecturas ARMv8 de ARM® , para el perfil de arquitectura de ARMv8-A").
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, que incluye 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 pequeños cambios en esta área de C++11.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4527.pdf
(introducción: 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 información detallada, consulta 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 al problema de exclusión mutua en la programación simultánea". En el artículo de Wikipedia, se incluye el algoritmo completo, además de una discusión sobre cómo debería actualizarse para que funcione con compiladores de optimización modernos y hardware SMP.
http://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. En este, se incluye un resumen detallado de las dependencias de control y direcciones.
http://linux.derkeiler.com/Mailing-Lists/Kernel/2009-05/msg11811.html
Lo que todo programador debe saber sobre la memoria
Es una artículo muy extenso y detallado sobre los diferentes tipos de memoria, en especial las caché de CPU, escrito por Ulrich Drepper.
http://www.akkadia.org/drepper/cpumemory.pdf
Razonamiento sobre el modelo de memoria poco coherente 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. Cabe aclarar que este documento 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. Lamentablemente, las cuatro variedades de vallas que se explican aquí no son buenas para las arquitecturas compatibles con Android, y las asignaciones de C++11 nombradas anteriormente 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. Lamentablemente, las descripciones precisas del modelo de memoria de ARM son mucho más complicadas.
http://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf