400430401. Concurrencia efectiva

Todo el mundo sabe lo básico en el uso de los bloqueos:

mut.lock(); // acquire lock on x

... read/write x ...

mut.unlock(); // release lock on x


Pero, ¿por qué funcionan los bloqueos, los estilos sin bloqueo y otras técnicas de sincronización?, y eso sin pensar en por qué interactúan bien entre sí y con optimizadores agresivos que transforman y reorganizan nuestro programa para hacer que funcione más rápido. lo hacen, porque toda técnica de sincronización de la que hayamos oído hablar ha de expresar – y toda optimización que pueda llevarse a cabo en cualquier momento ha de respetar y sustentar- el común y fundamental concepto de la sección crítica.

Carrera de datos

Una carrera de datos (o simplemente “carrera”) se produce cuando más de un hilo puede acceder simultáneamente a la misma sección de memoria, y cuando al menos uno de los accesos es un “write”. Consideremos el siguiente código, en el que x es un objeto compartido:

Thread 1 Thread 2

x = 1; obj.f( x );


Thread 1 escribe x y Thread 2 lo lee, y así se produce una carrera típica si no hay sincronización que evite que los dos hilos se ejecuten al mismo tiempo.
¿Hasta qué punto es potencialmente malo tener una carrera? Mucho, dependiendo del modelo de memoria de nuestro lenguaje y/o plataforma, que establece límites a la reorganización del compilador y del procesador y a las garantías, si las hay, de lo que podemos esperar. Por ejemplo, en Java, “ se pueden producir comportamientos muy extraños, confusos y antiintuitivos,» incluso como ver objetos construidos en parte. (1)

((No todo objeto es compartido durante todo su ciclo de vida: Sólo tenemos que protegerlo con secciones críticas mientras se está compartiendo))

En hilos POSIX (pthreads), no existe la carrera benigna: Casi cualquier carrera podría en principio causar la ejecución aleatoria de código.
Obviamente, queremos eliminar las carreras. La forma de hacerlo bien es usando secciones críticas para evitar que dos trozos de código que lean o escriban el mismo objeto compartido se ejecuten a la vez. Pero observemos:
– No todo objeto es compartido durante todo su ciclo de vida: Sólo tenemos que protegerlo con secciones críticas mientras se está compartiendo, o mientras está en transición desde uno no compartido a uno compartido y viceversa (por ejemplo, cuando un objeto que anteriormente era privado se “hace público” por primera vez a otros hilos al hacerlo accesible fuera de su hilo original).
– Un objeto compartido no necesita ser protegido de la misma forma durante todo su ciclo de vida: Es perfectamente válido proteger el mismo objeto con bloqueos en algunos momentos y con técnicas de sin bloqueo en otras. El próximo mes analizaremos con detalle algunos ejemplos.

Formas distintas de escribir “sección crítica”

Una “sección crítica” es una región del código que se ejecutará de forma independiente con respecto a parte o al resto del código del programa, y todas las formas de sincronización de las que hayamos oído hablar alguna vez son maneras de expresar secciones críticas. En la actualidad la herramienta de sincronización más frecuente es el humilde bloqueo, y toda región de código que se ejecuta bajo un bloqueo es una sección crítica. Por ejemplo, pensemos de nuevo en el código anterior:


mut.lock(); // enter critical section (acquire lock)

... read/write x ...

mut.unlock(); // exit critical section (release lock)


Las siguientes herramientas de sincronización más normales, utilizadas sólo por los expertos gurús de wizard, son las variedades de codificación sin bloqueo. Más allá de un puñado de patrones bien conocidos como el Bloqueo Doblemente Comprobado, los estilos sin bloqueo son normalmente difíciles de usar directamente en la programación normal, y generalmente se los utiliza dentro de las implementaciones de otras abstracciones (por ejemplo, en la implementación de una clase mutex, un contenedor reducido y mezclado de forma aleatoria, sincronizado internamente sin bloqueo, o un servicio de núcleo de SO).

El primer estilo sin bloqueo usa variables atómicas (Java/.NET volatile, C++0x atomic) que disponen de una semántica especial con soporte para el compilador y el procesador. Pensemos en un ejemplo similar al mencionado anteriormente, pero escrito en un estilo sin bloqueo, en el que myTurn es una variable atómica que protege a x.


while( !myTurn ) // enter critical section (spin read)

... read/write x ...

myTurn = false; // exit critical section (write)


El segundo estilo de codificación sin bloqueo es para explicitar vallas (también denominadas «barreras») como Linux mb(), o funciones especiales con semánticas de ordenación como InterlockedCompareExchange de Win32 . Estas herramientas expresan restricciones en la ordenación, mediante la colocación de puntos de control explícitos en los que se usan variables claves en el código.

((El primer estilo sin bloqueo usa variables atómicas (Java/.NET volatile, C++0x atomic) que disponen de una semántica especial con soporte para el compilador y el procesador))

La protección de una variable compartida con estas herramientas es difícil porque las vallas han de ser escritas correctamente en cada punto en el que utilizamos la variable (frente a hacerlo una vez en la declaración de la variable para declararlo inherentemente atómico), y sus semánticas son sutiles y tienden a variar de una plataforma a otra. Aquí tenemos una forma de escribir el ejemplo correspondiente, en el que myTurn es ahora una variable normal (que sigue teniendo que poder leerse y escribirse de forma atómica) y a la que se da una semántica especial mediante la aplicación de una simple valla en cada punto de uso de manera que siga protegiendo a x correctamente.


while( !myTurn ) // enter critical section

mb(); // (atomic spin read + fence)

... read/write x ...

mb(); // exit critical section

myTurn = false; // (fence + atomic write)


El punto clave es que todos los estilos basados en bloqueo y los sin bloqueo son sólo distintas formas de expresar el mismo concepto fundamental – la sección crítica contenida de forma exclusiva.

Reordenación de memoria

La figura 1 muestra la forma canónica y las normas que rigen la sección crítica. Como cualquier transacción, una sección crítica sigue la estructura básica de adquirir-funcionar-liberar.

Figura 1: Anatomía de una sección crítica

Los compiladores y procesadores ejecutan de manera rutinaria el código en el orden que habíamos especificado en nuestro fichero fuente, para hacerlo funcionar más rápido. Por ejemplo, los optimizadores compiladores quieren ayudarnos enarbolando cálculos invariantes de un bucle; ello implica trasladar las instrucciones desde el cuerpo del bucle y ejecutarlas de hecho antes del comienzo del bucle. Los procesadores quieren ayudarnos ocultando el coste de acceder a la memoria, lo que implica trasladar a la parte delantera las instrucciones caras a la memoria para que puedan empezar antes y superponerse al tener a varias en trayecto al mismo tiempo.

((Los compiladores y procesadores ejecutan de manera rutinaria el código en el orden que habíamos especificado en nuestro fichero fuente, para hacerlo funcionar más rápido))

Toda esta re-ordenación está bien, siempre y cuando nuestro programa no pueda notar la diferencia – y la definición de “el programa no puede notar la diferencia” es “todo el mundo respeta las secciones críticas.” Más concretamente:

– El programador eliminará de forma correcta las carreras utilizando las secciones críticas.
– Todas las transformaciones en la ordenación respetarán las secciones críticas (y las dependencias secuenciales normales de control/flujo como se ha hecho siempre para las sencillas optimizaciones secuenciales de siempre. Así pues, para que sea válida una transformación en la ordenación, tiene que respetar las secciones críticas del programa obedeciendo la regla clave de las secciones críticas: El código no puede trasladarse fuera de una sección crítica. (Siempre se puede trasladar código a la sección crítica). Aplicamos esta regla de oro requiriendo una semántica simétrica de valla de una vía para el principio y el final de cualquier sección crítica, que se ilustra mediante flechas en la figura 1.
– La entrada en una sección crítica es una operación acquire, o una valla de adquisición implícita: El código no puede nunca cruzar la valla hacia arriba, es decir, trasladarse de una situación original detrás de la valla a ejecutarse delante de la valla. El código que aparece antes de la valla en el orden del código fuente, no obstante, puede cruzar la valla hacia abajo sin problemas para ejecutarse más tarde.
– La salida de una sección crítica es una operación release, o una valla implícita de liberación. Esto es sólo el requisito inverso de que el código no puede cruzar la valla hacia abajo, sólo hacia arriba. Garantiza que cualquier otro hilo que vea el write de liberación final, verá también todos los writes que hay delante. (2)

El código nunca debe salir

Veamos lo que significa “el código no puede salir” dentro del contexto del código siguiente, que adquiere un mutex mut que protege dos enteros x e y:


mut.lock(); // enter ("acquire")

// critical section

x = 42; // where can this line

// appear to move to?

y = 43;

mut.unlock(); // exit ("release")

//critical section


¿Cuáles es la reorganización válida de la asignación a x? Es totalmente válido que el sistema transforme el código de arriba en el siguiente:


mut.lock();

y = 43;

x = 42; // ok: can move down

// past y's assignment

mut.unlock();


porque las dos asignaciones siguen ocurriendo dentro de la sección crítica protegida (y no dependen entre sí de ninguna otra manera, suponiendo que x e y sean independientes y no tengan un alias). No obstante, un sistema no puede transformar el código a


x = 42; // invalid: race bait

mut.lock();

y = 43;

mut.unlock();


o a:


mut.lock();

y = 43;

mut.unlock();

x = 42; // invalid: race bait


porque cualquiera de los dos trasladaría la asignación fuera de la sección crítica y por tanto crearía una carrera potencial en x.

¿Y qué pasaría si trasladamos código dentro de la sección crítica?

Siempre se puede trasladar código hacia dentro

Consideremos un ejemplo adaptado:


x = "life"; // where can this line

// appear to move to?

mut.lock(); // enter ("acquire")

// critical section

y = "universe";

mut.unlock(); // exit ("release")

// critical section

z = "everything"; // where can this

// line appear to

// move to?


¿Cuáles son las reorganizaciones válidas de las asignaciones a x y a z? Asumiendo una vez más que x, y y z son independientes y no tienen alias, es totalmente válido que el sistema transforme el código de arriba en el siguiente:


mut.lock();

z = "everything"; // ok: can move as

// far up as this

y = "universe";

x = "life"; // ok: can move as

// far down as this

mut.unlock();


Aunque las líneas trasladadas se ejecutan ahora mientas se mantiene el bloqueo, no altera el significado o la corrección del código. Es siempre más seguro añadir garantías adicionales; en este caso, mantener un bloqueo un poco más de tiempo.

Pero no es seguro eliminar las garantías de forma arbitraria, como por ejemplo no mantener un bloqueo necesario. Por tanto, un sistema no puede reorganizar de manera arbitraria el código para que cruce una de las dos vallas de la forma incorrecta:


z = "everything"; // invalid: race bait

mut.lock();

y = "universe";

mut.unlock();

x = "life"; // invalid: race bait


Observemos que eso es cierto incluso aunque las asignaciones a x y z no estuvieran dentro inicialmente de la sección crítica. Por ejemplo, ¿Qué pasaría si al establecimiento de y = “universe” se lo considera como una bandera que le dice a otro hilo que x está ahora lista para ser compartida, de manera que y haga público a x? Por eso es por lo que ningún código debe pasar la valla de liberación en dirección hacia abajo. (3)

Adquisición/liberación automática

Todo el sistema tiene que atenerse a las reglas – entendiendo por reglas las que escribimos en nuestro programa. En concreto, las normas para vallar la adquisición y la liberación tienen que aplicarse en todos los puntos fuera del código fuente, porque cuando nuestro programa hace cosas raras, no importa si fue el compilador el que reorganizó nuestras sentencias o fue nuestro procesador el que reorganizó las instrucciones emitidas por el compilador. A nivel de procesador, la única manera de evitar la reorganización de las instrucciones es mediante el uso de las vallas estilo adquisición y liberación que la mayoría de los procesadores soportan como instrucciones autónomas explícitas. Pero no queremos tener que escribir vallas a mano en nuestro código fuente. Así que, ¿qué podemos hacer para controlar la reorganización?

((Todo el sistema tiene que atenerse a las reglas – entendiendo por reglas las que escribimos en nuestro programa))

Podemos hacer que el compilador obedezca las normas y emita a la vez las vallas de procesador adecuadas en una sola acción: Podemos usar abstracciones que expresen secciones críticas; a saber, bloqueos y objetos atómicos. Pensemos en nuestro primer ejemplo de código basado en bloqueo, y cómo un compilador podría traducirlo a unas instrucciones específicas de “cargar adquirir” y “almacenar liberar” cuando está compilando parara un procesador IA64:


mut.lock();

// "acquire" mut => ld.acq mut.var

... read/write x ...

mut.unlock();

// "release" mut => st.rel mut.var


Y ¿qué pasa con el código sin bloqueo? De la misma forma, para nuestro otro ejemplo del principio de los estilos sin bloqueo, obtenemos:


while( !myTurn )

// "acquire" => ld.acq myTurn

... read/write x ...

myTurn = false;

// "release" => st.rel myTurn


Ambos estilos terminan generando unas instrucciones similares porque expresan el mismo concepto de sección crítica. Así , conviene evitar escribir las vallas a mano; es mejor usar estas abstracciones y dejar que sea el compilador quien las escriba por nosotros.

Resumen

Protegemos de carreras a todos los objetos mutables compartidos poniendo el código que accede a los mismos en secciones críticas. La sección crítica es un concepto fundamental que se aplica igualmente a todo tipo de sincronización. La entrada en una sección crítica – la toma de un bloqueo o la lectura de una variable atómica- es una operación de adquisición. La salida de una sección crítica – la liberalización de un bloqueo o la escritura de una variable atómica – es una operación de liberalización.

El próximo mes, examinaremos una serie de ejemplos prácticos sobre cómo usar y cómo no usar las secciones críticas, incluida la combinación de estilos diferentes.

Notas

(1) J. Manson, W. Pugh, y S. Adve. «JSR-133: Java Memory Model and Thread Specification» (Java Community Process, 2004).

(2) Conviene observar que no estoy especificando si dos secciones críticas consecutivas podrían superponerse, permitiendo que el extremo «release» del final de la primera sección crítica pase al extremo «acquire» inicial de la segunda sección crítica. Algunos modelos de memoria lo permiten, en tanto que otros tienen el requisito adicional de que las operaciones de adquisición y liberación no puedan pasar la una a la otra. Esta elección de diseño no afecta a los ejemplos del presente artículo.

(3) La gente propone con frecuencia sistemas que están más pulidos e intentan dejar que el programador especifique qué objetos son realmente importantes y deben respetar la valla. Estos no se han hecho muy populares, al menos no aún, fundamentalmente porque añaden gran complejidad al modelo de programación a cambio de pocas ventajas reales en los resultados para la mayoría de los casos de uso.