Introducción

En una serie anterior nos preocupamos por estudiar cómo es posible mejorar las cotas de ejecución de soluciones de software a través de la aplicación de modelos de desarrollo asíncrono. Se trataba en esencia de transformar cada una de las funciones y procedimientos de un cuerpo algorítmico en operaciones no bloqueantes que devolvieran instantáneamente el control al programa llamante para empezar a ejecutar de forma paralela.

En la ejecución concurrente, por el contrario, un conjunto de agentes opera de manera autónoma e independiente para resolver un problema de manera conjunta ya sea a través de estrategias de cooperación o competición. Esto no solamente requiere lanzar a ejecución dichos agentes en paralelo sino además establecer los criterios de coordinación oportunos para que la ejecución avance de forma adecuada.

Pese a sus aparentes diferencias, ambos tipos de problemas pertenecen a la misma dimensión temporal dentro del marco de trabajo que definimos al caracterizar los modelos de ejecución. Y es que en realidad existen entre ellos más concomitancias de lo que pudiera parecer en un principio. En efecto, aunque se atiende a preocupaciones diferentes, como veremos, los mecanismos de coordinación que requiere la ejecución concurrente se apoyan fuertemente en las primitivas de sincronización de código que se analizaron al hablar de la asincronía.

A lo largo de esta serie describiremos la colección de modelos de desarrollo que se ofrecen para dar respuesta a la necesidad de coordinación en los escenarios multiagente que plantea la programación concurrente. Durante este artículo, haremos una presentación formal y precisa del espacio del problema y trataremos de dar un marco de caracterización donde se ubican cada una de las propuestas de soluciones que recorreremos a lo largo de los próximos artículos.

Espacio del Problema

En el desarrollo de software muchos problemas pueden describirse en términos de un escenario de ejecución concurrente. En este tipo de situaciones, un conjunto de agentes opera de forma simultánea sobre un espacio compartido para alcanzar unos objetivos bien definidos. Cada agente se adscribe de forma prototípica a un comportamiento frecuentemente cíclico que se describe a través de un algoritmo. Y a parte de esta descripción, este tipo de problemas se caracterizan por una configuración paramétrica que indica el tipo, número y cadencia de operación de los agentes implicados dentro del escenario.

Todo esto es así con independencia de los artefactos de soporte que se utilicen para conferir ejecución paralela a los agentes. Este es un asunto del que ya nos ocuparemos más adelante. Porque lo que verdaderamente es relevante aquí, es establecer los mecanismos de coordinación pertinentes que permitan a los agentes acompasar sus operaciones de contribución en tiempo y forma tal que se garantice el avance adecuado de la actividad como un todo sistémico.

Esta garantía se expresa en términos de tres factores característicos. En primer lugar, deben cumplirse para cada problema, las propiedades oportunas de vivacidad que aseguren, de manera absoluta, la continuidad en la ejecución. Esto significa que en ningún momento debería llegarse a situaciones en las que el estado global del sistema impida el progreso de algunos agentes frente a otros o que las acciones de algunos impidan el progreso de los demás.

Adicionalmente, también deberían garantizarse ciertas propiedades de seguridad. De cara a la ejecución concurrente ello implica que ni las acciones tomadas por ningún tipo de agente ni las potenciales interferencias entre unos y otros debería dejar el sistema en una situación de inconsistencia. Pero tampoco se debería permitir que ningún agente realice operaciones no permitidas en función del estado global.

Y finalmente, también se deberían garantizar ciertas propiedades en atención a la prioridad. En efecto, si el sistema por diseño ya resulta seguro y vivaz es probable que estemos ante una solución correcta. Sin embargo, sería conveniente establecer ciertos criterios de balanceo sobre las operaciones realizadas por unos y otros agentes. En este sentido, debería garantizarse siempre por construcción un flujo equilibrado de progreso para cada tipo de agente implicado, si bien ello requerirá siempre tener en cuenta la carga volumétrica de los mismos. Es decir, es probable que una alteración considerable en esta configuración demande un tipo de solución diferente en prioridades que ofrezca un nuevo reequilibrio en relación a la vivacidad evitando que ningún tipo de agente quede rezagado en favor de otros.

Ejecución Concurrente. En la ejecución concurrente una colección de agentes opera de forma coordinada y paralela sobre un espacio compartido para alcanzar unos objetivos ya sean éstos alineados o en conflicto competitivo.

En términos generales podemos afirmar que dentro de este tipo de escenarios es posible encontrar actividades de carácter competitivo y cooperativo de forma simultánea. Como veremos en la siguiente sección, el mero acceso al espacio compartido puede traducirse en una actividad competitiva sobre todo si ello se pretende realizar de manera vivaz y segura. Pero a la vez, dicho acceso puede tener por objetivo hacer una contribución sumativa que viene a ofrecer oportunidades de progreso a otros tipos de agentes dentro del problema. No obstante, mirado a nivel global los tipos de soluciones sí pueden clasificarse en estos dos tipos de escenarios. Ilustraremos esta clasificación con diferentes ejemplos y trataremos de caracterizarlos en términos de su demanda en vivacidad, prioridad y seguridad.

• Ejecución Cooperativa. En los escenarios de ejecución cooperativa existen diferentes tipos de agentes con objetivos claramente alineados, aunque complementarios. Es fácil identificar relaciones de dependencia nítidamente establecidas entre los mismos. Y el espacio compartido opera como un elemento de soporte vehicular para realizar las operaciones de comunicación pertinentes que resuelven dichas dependencias.

• Ejecución Competitiva. En los escenarios de ejecución competitiva, por el contrario, los agentes no necesariamente se clasifican en distintas categorías, sino que más bien presentan un comportamiento potencialmente cambiante que depende del estado interno dentro de su propio ciclo de vida. Por su parte, tampoco existen relaciones claras entre los agentes y el espacio compartido es interpretado como un recurso por el que rivalizar en apropiación a lo largo del tiempo.

Un banco de sangre, un sistema de calefacción o un aparcamiento público son casos típicos de escenarios cooperativos. En el banco de sangre hay agentes donantes para cada grupo sanguíneo y agentes en salas de operación que demandan unidades de sangre. Las restricciones de compatibilidad y el número de bolsas necesarias forman parte del entramado de relaciones y se requiere garantizar continuidad en el flujo de sangre. En el sistema de calefacción existen sensores que emiten cambios de temperatura y calefactores que pueden emitir más o menos calor. Ambos tipos de agentes operan sobre la base de un termostato que debe garantizar un acompasado entre los comandos entregados a los calefactores y cada dato recibido por los sensores. En el aparcamiento hay instaladas varias barreras de entrada y varias barreras de salida de manera que cuando se abre una barrera de entrada entra un único coche y cuando se abre una barrera de salida sale un único coche. Por seguridad se exige que nunca debe ser superado el aforo máximo de coches mientras que por vivacidad debe garantizarse que no se forman colas interminables de entrada.

Un aeropuerto, una cena de filósofos orientales o un sistema de reserva en línea de un teatro, por el contrario, son escenarios de competición. En el aeropuerto los agentes son aviones que pueden estar esperando pista de despegue o aterrizaje. Cuando un avión aterriza, carga nuevo pasaje, tripulación y repostaje y vuelve a despegar de manera cíclica. Sin embargo, el número de pistas es limitado y desde la torre de control debe hacerse una cesión de acceso a pista racionalizado teniendo en cuenta que, por motivos evidentes, el aterrizaje es más prioritario que el despegue. En la cena de orientales cada filósofo come un cuenco de arroz en torno a una mesa circular. Sin embargo, los palillos son recursos escasos. Sólo se ha dispuesto un palillo entre cada par de cuencos. Dado que comer requiere dos palillos, los agentes orientales tienen que acompasar concesivamente el uso de sendos palillos para garantizar que ningún colega se quede sin cenar. En el teatro, cada usuario debe acceder al mapa de asientos libres por orden de llegada al sistema de reserva. Pero este acceso debe ser concedido en exclusiva para que no se solape la reserva de un mismo asiento por dos agentes distintos.

La clasificación anterior resulta de utilidad en el plano conceptual para entender las categorías de problemas que surgen en el seno de la ejecución concurrente. No obstante, esta clasificación es en ocasiones débil. En el caso del aparcamiento si la entrada y la salida se configura por la misma barrera el escenario pasa de cooperación a competición. Se compite por el uso de la barrera para entrar o salir. En el aeropuerto si en lugar de hablar de aviones hablamos de tripulación de vuelo y de tierra siendo los primeros los que aterrizan y los segundos los que preparan de nuevo el avión, se transita de escenario competitivo a cooperativo. La pista es el espacio compartido que vehicula tal cooperación.

De acuerdo a todo lo anterior, y sin pérdida de generalidad, podemos afirmar que todo problema concurrente puede adscribirse al arquetipo que queda representado en la figura 1. Todo problema concurrente consiste en una colección de agentes productores y otra de agentes consumidores que comparten un espacio común como medio de transferencia. Los productores funcionan cíclicamente escribiendo datos en el espacio mientras que los consumidores realizan operaciones de lectura. El volumen, prioridad y cadencia de operación de cada tipo de agente puede ser configurado. Y deben garantizarse la fluidez y la ausencia de corrupción de datos a nivel global. A lo largo de toda esta serie trabajaremos con este espacio de problema como marco de referencia para explicar este modelo de ejecución.

Espacio de la Solución

Durante las fases de desarrollo concurrente, uno de los aspectos más relevantes, y a la vez más complicados de llevar a cabo, consiste en encontrar una formulación oportuna para expresar toda la lógica de coordinación propia del problema que regule el comportamiento participativo de los agentes a lo largo del tiempo. Dicha lógica debe ser el garante en las propiedades de seguridad, viveza y prioridad necesarias tal y como explicamos en la sección anterior. En general, para cada una de estas propiedades es frecuente reconocer distintas estrategias de aplicación recurrente.

• Propiedades de Seguridad. En relación a las propiedades de seguridad, la lógica de coordinación frecuentemente debe hacer frente a situaciones en las que diferentes tipos de agentes - típicamente con objetivos complementarios - deben tener un acceso al espacio compartido alterno y no solapante en el tiempo. Esto es lo que se conoce con el nombre de acceso en exclusión mutua y es una estrategia típica de condiciones de seguridad. Cuando este acceso se produce de manera completamente exclusiva con respecto a cualquier otro agente hablamos de exclusión mutua total mientras que si el esquema de solución tolera aproximaciones menos restrictivas hablamos de exclusión mutua parcial.

• Propiedades de Vivacidad. En relación a la vivacidad la lógica de coordinación debe evitar que se alcancen en cualquier momento situaciones de inanición o interbloqueo. Cuando se alcanza a una situación tal en la que un agente o tipo de agentes no puede progresar su ejecución de manera irreversible, hablamos de inanición. Cuando el efecto de bloqueo es causado por una situación en la que unos agentes impiden el progreso de otros y recíprocamente, hablamos de situación de interbloqueo.

• Propiedades de Prioridad. Finalmente, en torno a la prioridad también es necesario aplicar una lógica de coordinación que resulte conservadora. En este sentido, es importante preservar, en la medida de lo posible, el orden de llegada de los agentes en relación a la petición de acceso al espacio compartido, pero hacerlo de tal forma que se tengan en cuenta los criterios de prioridad oportunos.

La expresión de toda esta lógica suele frecuentemente venir expresada en términos de las condiciones del estado global del sistema. Por eso, en ocasiones es posible hablar de sincronización por condición y exclusión como un binomio indivisible al realizar el diseño de soluciones concurrentes. No obstante, a lo largo de esta serie nosotros evitaremos estos términos en favor de la expresión lógica de coordinación que resulta más neutral.

Revisemos algunos ejemplos de este tipo de lógica sobre el arquetipo de problema que estamos utilizando. En el acceso a un espacio compartido entre lectores y escritores, es frecuente exigir que el entrelazado de operaciones se produzca en exclusión mutua total. Si se permite concurrencia de varios lectores o escritores operando simultáneamente entonces estamos ante un escenario de exclusión mutua parcial. Si, por cualquier motivo, se da siempre prioridad a los lectores frente a los escritores con independencia del orden de llegada podríamos alcanzar una situación de desequilibrio inconveniente. Si además no regulamos una cesión concesiva de turnos entre lectores y escritores, los primeros podrían alcanzar rápidamente una situación de bloqueo cuando no hubiera más datos que leer.

Como quedó representado en la figura 1, la lógica de coordinación característica de cada problema queda expresada sobre la base de un protocolo de actuación cíclico propio de cada tipo de agente. Tanto lectores como escritores, antes de proceder con su operación de lectura o escritura, quedan potencialmente bloqueados a la espera de que se den las condiciones ambientales adecuadas para poder operar. Y tras su operación se realizan acciones de desbloqueo que, pertinentemente, garantizan la continuidad en ejecución a nivel sistémico.

Para dar soporte a estos protocolos se requiere proporcionar una arquitectura de bloqueo sobre la que poder desplegar toda esta lógica. A la postre, dicha arquitectura es la materialización particular de lo que hasta este punto hemos venido llamando, así de una manera intencionalmente abstracta, espacio compartido. Y es que justo aquí es donde se da una importante divergencia entre dos grandes familias de solución dentro de la ejecución concurrente al diferenciar entre arquitecturas de memoria compartida y arquitecturas de mensajería.

• Arquitecturas de Memoria Compartida. En este tipo de aproximaciones, todos los agentes implicados en el marco del problema se apoyan en el uso de una memoria común que materializa el espacio compartido. Allí no sólo se produce toda la actividad de compartición de datos propia de la operación, sino que también se soporta toda la lógica de coordinación que se apoya en el uso de arquitecturas basadas en colas donde los agentes quedan retenidos temporalmente a la espera de entrar a operar.

• Arquitecturas de Mensajería. En este otro tipo de soluciones, por el contrario, el espacio compartido queda materializado a partir de una arquitectura de canales de comunicación por las que es posible realizar intercambio de mensajes. En este sentido, el soporte a la operación queda sustentado en actividades de comunicación y la lógica de coordinación se articula en base al carácter bloqueante que, por construcción, presentan las operaciones de envío o recepción de mensajes.

Las arquitecturas de memoria compartida son apropiadas en espacios de computación centralizada donde toda la ejecución se despliega sobre la base de un único proceso. Por el contrario, las arquitecturas de mensajería, aunque no obligan a ello, sí facilitan una operación en escenarios de computación distribuida donde cada agente se despliega en un nodo de red y los mensajes se soportan sobre un entramado de comunicaciones remotas.

Como descubriremos a lo largo de esta serie, sobre cada uno de estos dos tipos de arquitecturas se han planteado modelos de desarrollo diferentes. Los cerrojos, semáforos, regiones críticas condicionales o monitores son modelos típicos basados en arquitecturas de memoria compartida mientras que los canales, buzones o procedimientos remotos son modelos soportados por arquitecturas de mensajería.

Pero con independencia de todo lo anterior, lo cierto es que en el desarrollo de la lógica de coordinación concurrente pueden reconocerse una colección de patrones de diseño que resultan de aplicación recurrente en las fases de bloqueo y desbloqueo. En la figura 2, pueden verse representados algunos de los más relevantes. En el caso de ser aplicados sobre arquitecturas de memoria compartida los cilindros representan colas de bloqueo mientras que si usamos arquitecturas de mensajería dichos cilindros corresponderían a canales de comunicación entre agentes.

En la fase de bloqueo, el bloqueo por orden de llegada, por tipo de agente y por prioridad son tres patrones característicos de coordinación entrante. En efecto, preservar el orden de llegada es una de las técnicas más habituales para garantizar un buen comportamiento sistémico. Hacer una lógica de coordinación por tipo de operación es muy habitual en escenarios de cooperación y usar bloqueo por prioridad puede llegar a ser relevante en algunos tipos de problema, si bien su uso requiere cierta atención para no caer en situación de inanición.

En la fase de desbloqueo, por su parte, el desbloqueo cruzado, en cascada, por prioridad, por volumetría e incluso aleatorio suelen ser patrones recurrentes. El desbloqueo cruzado por cortesía persigue alcanzar situaciones de equilibrio en el que tras la operación de un lector se concede paso a un escritor y recíprocamente. El desbloqueo en cascada se da en situaciones en las que un agente, tras su operación, alcanza un estado sistémico que permite la operación simultanea de todos los agentes en cierta cola. El desbloqueo de prioridad es aquél en el que los criterios de desbloqueo tienen en cuenta criterios de predominancia de unos agentes frente a otro mientras que el desbloqueo volumétrico atiende a criterios de carga de trabajo sobre los tipos de operación. Y finalmente el desbloqueo aleatorio es una técnica que busca alcanzar un equilibrio estable a largo plazo a la vez que mantiene la azarosidad en los turnos de intervención.

En el diseño de la lógica de coordinación tanto de bloqueo como de desbloqueo es frecuente aplicar técnicas que hagan una conjugación compositiva de algunos de los patrones anteriores. Por ejemplo, es posible aplicar un desbloqueo volumétrico pero alternar a uno cruzado en caso de alcanzar igualdad de volumetrías entre lectores y escritores. O también es posible priorizar un criterio de cesión cruzada de turno y saltar al desbloqueo en cascada de lectores o escritores cuando no hay agentes del otro tipo en cola de espera.

Conclusiones

A lo largo de este artículo de introducción hemos presentado la ejecución concurrente como un marco de problemas donde una colección de agentes realizan contribuciones sobre un espacio compartido para alcanzar ciertos objetivos. En este tipo de escenarios, la caracterización del problema puede expresarse de manera genérica en términos del número, tipo y cadencia de los agentes implicados junto con su lógica de operación. Pero sobre todo a partir de las propiedades de seguridad, vivacidad y prioridad que deben exigirse.

Al transitar a la fase de diseño, esta caracterización se concentra especialmente en la lógica de coordinación que modula el comportamiento de los agentes en el tiempo y que se expresa en base a protocolos de bloqueo condicional a la espera de encontrar las condiciones oportunas de operación.

El uso de dos tipos complementarios de arquitecturas de soporte para articular tanto la lógica de operación como la de coordinación conduce a una clara diferenciación entre dos grandes familias de modelos de desarrollo. Sobre la base de arquitecturas de memoria compartida surgen varios modelos que se apoyan en el uso de colas como elemento de bloqueo condicional mientras que a partir de arquitecturas de mensajería surgen otros tantos modelos que se apoyan en el carácter bloqueante de las primitivas de comunicación.

El conjunto de artículos que dan cuerpo a esta serie se centra, precisamente, en describir en detalle cada uno de los modelos de soporte a la ejecución concurrente. Primero recorreremos los basados en memoria compartida y luego transitaremos a los propios del paso de mensajes.

Como iremos descubriendo con la lectura, cada modelo propuesto persigue ofrecer una familia de primitivas centradas en la coordinación progresivamente más abstractas y donde dicha lógica quede más centralizada y oculta a través de esfuerzos sistemáticos de encapsulación. El éxito de este viaje terminará en modelos donde hayamos conseguido que todo el cuerpo algorítmico de los agentes quede despojado de cualquier lógica de coordinación para concentrarse exclusivamente en la lógica de operación. Será en cualquier caso interesante comprobar cómo, de cara al soporte subyacente, los modelos de ejecución concurrente hacen un uso intensivo de las capacidades expuestas por los modelos de asincronía en uso.