400510304. Los Pilares de la Concurrencia

Rápido: ¿Qué es “concurrencia” para el lector? ¿y para sus colegas? ¿y para su proyecto?
Es probable que el lector conozca la fábula de los ciegos y el elefante: Hay varios ciegos que están explorando un elefante con el tacto, y cada uno saca su propia conclusión sobre lo que es un elefante.

El que está a la cola concluye que el elefante es como una cuerda; el que está en los colmillos asegura que no, que el elefante es como una lanza; el que está en la pierna piensa que es como un árbol; el que está en la oreja que es como un abanico; etc. Los ciegos discuten, cada uno con el convencimiento de que está en lo cierto, basándose en su propia experiencia y punto de vista.

Con el tiempo, hay varios que no esperan ya poder ponerse de acuerdo sobre lo que es en realidad esta criatura, y algunos se resignan a aceptar que lo más que pueden hacer es analizar en profundidad cada una de las partes de forma aislada y sin conexión con las otras. Mientras, el pobre elefante espera pacientemente, ligeramente confuso, pues desde luego no se parece a ninguna de esas cosas a nivel individual y no se ve a sí mismo tan difícil de entender como criatura en su conjunto.

((¿No se ha encontrado que cuando habla con otro desarrollador de concurrencia tiene la impresión de estar hablando dos lenguas totalmente distintas?))

¿No se ha encontrado el lector que cuando habla con otro desarrollador de concurrencia tiene la impresión de estar hablando dos lenguas totalmente distintas? Si es así, no es el único. Podemos observar la confusión que existe en nuestro vocabulario en inglés (y lo que presento aquí no es una lista exhaustiva):
acquire, and-parallel, associative, atomic, background, cancel, consistent, data-driven, dialogue, dismiss, fairness, fine-grained, fork-join, hierarchical, interactive, invariant, isolation, message, nested, overhead, performance, priority, protocol, read, reduction, release, structured, repeatable, responsiveness, scalable, schedule, serializable update, side effect, systolic, timeout, transaction, throughput, virtual, wait, write,…

Algunas de estas palabras tienen múltiples significados (como por ejemplo “performance”, que en español se podría traducir por cosas tan variadas como “actuación, prestaciones, resultados, rendimiento, funcionamiento, funcionalidad, etc.”) en tanto que otras no tienen relación entre sí (como por ejemplo responsiveness -en español “capacidad de respuesta”- y throughput –en español “rendimiento”). Gran parte de la confusión que encontramos se produce cuando la gente, sin darse cuenta, mantiene una conversación de besugos al usar palabras incompatibles.

Un problema básico es que no debería ser una lista única. Pero ¿cómo podemos agrupar estos términos con sensatez, cuando experimentados programadores de paralelo conocen decenas o centenas de distintos requisitos y técnicas de concurrencia que parecen representar un reto a la agrupación?

Los pilares de Callahan

Mi colega David Callahan lidera el equipo en Visual Studio que trabaja en modelos de programación para concurrencias, y ha indicado que los requisitos y técnicas fundamentales en la concurrencia se enclavan en tres categorías o pilares básicos, que se encuentran resumidos en la Tabla 1.

La comprensión de estos pilares nos proporciona un marco para razonar con claridad sobre todos los aspectos de la concurrencia – desde los requisitos y compensaciones de la misma que importan para el proyecto que tenemos entre manos, hasta por qué hay patrones de diseño y técnicas de implementación específicos que son aplicables para obtener resultados específicos y cómo pueden interactuar, e incluso hasta la evaluación de cómo futuras herramientas y tecnología encajarán con nuestras necesidades.

Vamos a considerar una visión general de cada uno de los pilares cada vez, anotar por qué técnicas de distintos pilares componen bien y ver cómo este marco nos ayuda a clarificar nuestro vocabulario.

Pilar número 1: Capacidad de respuesta y aislamiento mediante agentes asíncronos.

El pilar número 1 consiste en ejecutar tareas separadas, o agentes, y dejarles que se comuniquen de manera independiente mediante mensajes asíncronos. En particular queremos evitar el bloqueo, especialmente en la interfaz de usuario y otros hilos sensibles al tiempo, ejecutando el trabajo que resulta caro de forma asíncrona.

Además, el aislar las tareas que se pueden separar hace que éstas sean más fáciles de comprobar de forma separada, y de separar después en varios contextos paralelos con confianza. Utilizamos aquí términos clave como “interactivo”, “con capacidad de respuesta” y “segundo plano/fondo/trasfondo” (background); “mensaje” y “diálogo”; y “timeout” y “cancelar”.

[(Algunas de estas palabras tienen múltiples significados (como por ejemplo “performance”, que en español se podría traducir por cosas tan variadas como “actuación, prestaciones, resultados, rendimiento, funcionamiento, funcionalidad, etc.”) en tanto que otras no tienen relación entre sí (como por ejemplo responsiveness -en español “capacidad de respuesta”- y throughput –en español “rendimiento”))]

Una técnica típica del Pilar 1 es sacar el trabajo caro del hilo de bombeo de la GUI principal de una aplicación activa. En ningún momento queremos detener durante segundos o más tiempo nuestra presentación visual; los usuarios deberían seguir pudiendo pinchar con el ratón e interactuar con una GUI que tenga capacidad de respuesta mientras, como en segundo plano, se va realizando el trabajo difícil.

No pasa nada si los usuarios experimentan un cambio en la aplicación mientras se va realizando el trabajo (por ejemplo, algunos botones o elementos del menú podrían ser deshabilitados, o un icono animado o barra de progreso podría indicar la situación del trabajo que se va realizando en segundo plano) pero no deberían tener nunca una “pantalla en blanco” – un hilo de GUI que deja de responder a mensajes básicos como “volver a pintar” durante un rato porque los mensajes nuevos se amontonan tras uno que está tardando mucho en procesarse de forma sincrónica.

Normalmente, los usuarios siguen intentando pinchar en cosas para hacer que responda la aplicación y al final o bien lo abandonan y destruyen la aplicación porque piensan que se ha colapsado (posiblemente perdiendo o corrompiendo el trabajo aunque, con el tiempo, el programa hubiera empezado a funcionar otra vez) o esperan para sólo conseguir un flujo en el que todas las pinchadas del ratón que intentaban realizar por fin son procesadas, normalmente con resultados insatisfactorios o negativos. Es importante que nosotros no permitamos que esto le ocurra a nuestra aplicación, aunque las grandes compañías sí lo hagan.

Y así, ¿qué tipo de trabajo queremos extraer de los hilos sensibles a la capacidad de respuesta? Puede ser trabajo que realiza una computación cara o de latencia alta ( por ejemplo, una compilación , u reproducción de una impresión en segundo plano) o de bloqueo real (esperar inactivamente a que haya un bloqueo, un resultado de la base de datos, o una respuesta del servicio web).

Algunas de estas tareas sólo quieren devolver un valor; otras interactuarán más para suministrar resultados intermedios o aceptar input adicional conforme van avanzando en su trabajo.

Por último, ¿cómo deberían comunicarse las tareas independientes? Una clave es que la comunicación misma sea asíncrona, preferiblemente usando mensajes asíncronos cuando sea posible porque los mensajes son casi siempre preferibles a compartir objetos en la memoria (que es el territorio del tercer Pilar). En el caso de un hilo GUI, esto es una solución fácil porque las GUI ya utilizan modelos controlados por eventos basados en mensajes.

En la actualidad, normalmente expresamos el primer Pilar ejecutando el trabajo de segundo plano en su propio hilo o como un elemento de trabajo en un conjunto de hilos; La tarea en primer plano que quiere mantenerse en actitud de respuesta es, de forma característica, de larga duración y normalmente es un hilo; y la comunicación se produce mediante colas de mensaje y abstracciones tipo mensaje como futuros (Java Future, .NET IAsyncResult).

En años venideros, tendremos nuevas herramientas y abstracciones en este pilar, en donde entre los candidatos potenciales se incluye objetos/servicios activos (objetos que conceptualmente se ejecutan en su propio hilo, y la invocación de un método es un mensaje asíncrono); Canales de comunicación entre dos o más tareas; y contratos que nos permiten, de manera explícita, expresar, hacer cumplir y validar el orden esperado en los mensajes.

A este pilar no le corresponde mantener ocupados a centenas de núcleos; eso es tarea del segundo Pilar. El primer Pilar consiste enteramente en capacidad de respuesta, asincronía e independencia; pero puede que mantenga ocupados una serie de núcleos sólo como efecto secundario, porque sigue expresando trabajo que puede realizarse de forma independiente y, por tanto, en paralelo.

Pilar número 2: Rendimiento y escalabilidad mediante colecciones concurrentes

El segundo pilar, por otro lado, consiste en mantener ocupados a cientos de núcleos para computar los resultados más rápidamente, volviendo así a permitir la “gratuidad” (2). En particular queremos tener como objetivo las operaciones realizadas en colecciones (cualquier grupo de cosas, no sólo contenedores) y explotar el paralelismo en los datos y en las estructuras de algoritmos. Aquí utilizamos términos clave como “scalability” (escalabilidad) y “throughput” (rendimiento); “data-driven” (controlado por datos) y “fine-grained” (de baja granularidad, de grano fino) y “schedule” (plan, programa, planificación); y “side effect” (efectos secundarios) y “reduction” (reducción).

El hardware nuevo ya no da el “algo por nada” de ejecutar con más rapidez y de forma automática el código de un solo hilo en el punto en el que lo hacía anteriormente. En vez de eso, ofrece una mayor capacidad para ejecutar más tareas de forma concurrente en más núcleos de CPU y en hilos de hardware.

Cómo podemos escribir aplicaciones que recuperen el “dar algo por nada” que podamos enviar hoy y saber que se ejecutarán con mayor rapidez y de forma natural en máquinas futuras con un incluso mayor paralelismo.

((La clave para la escalabilidad está en no dividir el trabajo de computación intensiva entre un número determinado de hilos explícitos escritos con código protegido en la estructura de la aplicación (por ejemplo, cuando un juego pudiera intentar dividir su trabajo de computación entre un hilo de física, un hilo de reproducción, y un hilo de todo lo demás).))

La clave para la escalabilidad está en no dividir el trabajo de computación intensiva entre un número determinado de hilos explícitos escritos con código protegido en la estructura de la aplicación (por ejemplo, cuando un juego pudiera intentar dividir su trabajo de computación entre un hilo de física, un hilo de reproducción, y un hilo de todo lo demás).

Como veremos el próximo mes, esa ruta nos lleva a una aplicación que prefiere ejecutarse en un número constante K de núcleos, que pueden penalizar un sistema con menos núcleos que K y no escala en un sistema con más de K núcleos.

Lo que está bien si nuestro objetivo es una conocida y determinada configuración de hardware, como una consola de juegos específica cuya arquitectura no va a cambiar hasta la siguiente generación de consolas, pero no es escalable al hardware que soporta un mayor paralelismo.

Pero la clave para la escalabilidad es, más bien, expresar mucha concurrencia latente en el programa que escala para que coincida con sus inputs (número de mensajes, tamaño de los datos). Esto lo hacemos principalmente de dos formas.

La primera es usar bibliotecas y abstracciones que nos permitan decir lo que queremos hacer en lugar de especificar cómo hacerlo. En la actualidad, utilizamos herramientas como OpenMP para pedir que se ejecuten las iteraciones de un bucle en paralelo y dejar que el sistema de tiempo de ejecución decida la medida en que se va a subdividir el trabajo para que encaje en el número de núcleos disponibles.

En el día de mañana, herramientas como STL paralelo y LINQ paralelo (5) nos permitirán expresar solicitudes del tipo “seleccionar los nombres de todos los alumnos universitarios ordenados por nivel”, que se pueden ejecutar en paralelo frente a un contenedor dentro de la memoria tan fácilmente como se ejecuta de manera rutinaria en paralelo mediante un servidor de bases de datos SQL.

La segunda forma es expresar de forma explícita el trabajo que puede hacerse en paralelo. En la actualidad, esto lo podemos hacer ejecutando elementos del trabajo en un conjunto de hilos (por ejemplo, usando ThreadPoolExecutor de Java oBackgroundWorker de .NET ). Sólo tenemos que recordar que hay un coste extra al transferir el trabajo a un conjunto, así que es nuestra responsabilidad asegurarnos de que el trabajo es lo suficientemente grande como para que merezca la pena. Por ejemplo, podríamos implementar un algoritmo recursivo como la ordenación rápida (quicksort) para ordenar en cada paso los sub-rangos izquierdo y derecho en paralelo si los sub-rangos son lo suficientemente grandes, o en serie si son pequeños.

Los futuros sistemas de tiempo de ejecución basados en el “robo” del trabajo harán que este estilo resulte incluso más sencillo al permitirnos expresar de manera sencilla todo el paralelismo posible sin tener que preocuparnos de si es lo suficientemente grande, y dejarle al sistema de ejecución que decida de forma dinámica no realizar el trabajo en paralelo si no merece la pena en la máquina de un usuario dado (o con la carga de otro trabajo en el sistema en un momento dado), con un coste aceptablemente bajo para el paralelismo no realizado (por ejemplo, si el sistema decide ejecutarlo en serie, querríamos saber la penalización en el funcionamiento comparado con si simplemente hubiéramos escrito la invocación recursiva puramente en serie en primer lugar para que fuera similar al coste extra de invocar una función vacía).

Pilar número 3: Consistencia mediante recursos compartidos de forma segura

El tercer pilar consiste en encargarse de los recursos compartidos, especialmente el estado de la memoria compartida sin corrupción ni interbloqueo. Utilizamos aquí términos como acquire y release (adquirir y liberar); read y write (leer y escribir); y atomic (atómico) consistent (consistente) y transaction (transacción). En estas columnas, me voy a centrar fundamentalmente en tratar sobre objetos mutables en la memoria compartida.

El status quo actual para sincronizar el acceso a objetos mutables compartidos es el bloqueo. Se sabe que los bloqueos son inadecuados (véase (3) y (4)), pero son, no obstante, las mejores herramientas de carácter general que tenemos.

Algunas plataformas ofrecen estructuras de datos sin bloqueo (tablas hash), que se sincronizan internamente mediante variables atómicas de manera que puedan ser utilizadas con seguridad sin introducir los bloqueos de manera interna dentro de la implementación de la estructura de datos o externamente en nuestro código de invocación; son útiles, pero no suponen una forma de evitar el bloqueo en general, porque son pocas y, muchas estructuras corrientes de datos no tienen ningún tipo de implementación conocida sin bloqueo.

((
Una aplicación puede trasladar una transversal de árbol costosa desde el hilo de la GUI principal para que se ejecute como fondo y así mantener libre a la GUI para que bombee mensajes nuevos, mientras que la tarea de la transversal del árbol puede explotar el paralelismo internamente en el árbol para que lo cruce en paralelo y compute el resultado con más rapidez (rendimiento, Pilar número 2).

))

En el futuro, confiamos en poder disponer de un soporte mejorado para los bloqueos (por ejemplo, pudiendo expresar niveles/jerarquías de bloqueo de forma portátil, y qué datos son protegidos por qué bloqueo) y probablemente de una memoria transaccional (en donde la idea es versionar la memoria automáticamente para que el programador pueda simplemente escribir “iniciar la transacción; hacer el trabajo; finalizar la transacción” como lo hacemos con las bases de datos y dejar que el sistema gestione la sincronización y la contención de forma automática). Hasta que tengamos estas cosas, tendremos que aprender a amar al bloqueo.

“Componibilidad”: Más que la suma de las partes

Como los pilares abordan cuestiones independientes, también componen bien, de forma que una técnica o patrón dado puede aplicar elementos de más de una categoría.

Por ejemplo, una aplicación puede trasladar una transversal de árbol costosa desde el hilo de la GUI principal para que se ejecute como fondo y así mantener libre a la GUI para que bombee mensajes nuevos (capacidad de respuesta, Pilar número 1), mientras que la tarea de la transversal del árbol puede explotar el paralelismo internamente en el árbol para que lo cruce en paralelo y compute el resultado con más rapidez (rendimiento, Pilar número 2).

Las dos técnicas son independientes entre sí y persiguen objetivos distintos mediante patrones y técnicas diferentes, pero pueden ser usadas las dos juntas de forma eficaz.

El usuario tiene una aplicación con capacidad de respuesta independientemente del tiempo que tarde la computación en una máquina menos potente; también tiene el usuario una aplicación escalable que se ejecuta más rápidamente en el hardware más potente.

Y al contrario, podemos utilizar esta plataforma como una herramienta para descomponer las herramientas de concurrencia, los requisitos y las técnicas en sus partes fundamentales.

Al entender mejor las partes y la forma en que se relacionan, podemos obtener una comprensión más exacta de lo que el todo está exactamente intentando conseguir y evaluar si tiene sentido, si es un buen método, o cómo se puede mejorar mediante el cambio de una de las piezas fundamentales dejando las otras intactas.

Resumen

Es importante tener un modelo mental consistente para razonar sobre la concurrencia – incluyendo los requisitos, las compensaciones, los patrones, técnicas y tecnologías tanto actuales como futuras. También lo es distinguir entre los objetivos de capacidad de respuesta (haciendo el trabajo de forma asíncrona), rendimiento (minimizando el tiempo de solución) y consistencia (evitando la corrupción causada por las carreras y los interbloqueos).

En próximas columnas, me introduciré en los distintos aspectos específicos de estos tres pilares. El próximo mes contestaremos a la pregunta de “ ¿cuanta concurrencia tiene o necesita nuestra aplicación?” y distinguiremos entre concurrencia O(1), O(K), y O(N). Manteneos al tanto. DDJ