Se conoce por programación concurrente a la
rama de la informática que trata de las técnicas de programación que se usan
para expresar el paralelismo entre tareas y para resolver los problemas de
comunicación y sincronización entre procesos.
El principal problema de la programación
concurrente corresponde a no saber en que orden se ejecutan los programas
(en especial los programas que se comunican). Se debe tener especial cuidado
en que este orden no afecte el resultado de los programas.
Este tipo de programación se
utiliza cuando tenemos que realizar varias acciones a la vez y se debe controlar
en que secuencia y lógica se hará cada una para que no halla un conflicto entre
ellas. Se suele utilizar para
controlar los accesos de usuarios y programas a un recurso de forma simultanea.
Se trata de una programación más lenta y laboriosa, obteniendo unos resultados
lentos en las acciones. Este tipo de
programación es la utilizada para desarrollar sistemas operativos en red y multiusuarios. También pueden existir aplicaciones
especificas que necesites trabajar en forma concurrente sobre un determinado
elemento.
También
es necesario considerar que el programar concurrentemente permite que los
sistemas sean más fácilmente escalables debido a la modularidad de su
desarrollo y que también estos pueden ser mucho más eficientes debido a que
permiten la ejecución en paralelo de múltiples instrucciones. La
programación concurrente es usada para modelar y simular sistemas físicos,
inclusive si esos sistemas no están controlados directamente por un
computador. La simulación es una herramienta importante en la optimización
de sistemas físicos; la programación concurrente brinda una forma natural de
asignar segmentos del programa para representar objetos físicos y por eso
ayuda mucho a representar simulaciones.
Al programar concurrentemente y por ello compartir recursos surgen algunos
problemas que necesitan ser resueltos para así aprovechar al máximo todas
las ventajas que la programación concurrente nos puede brindar. Entre los
problemas más importantes podemos mencionar algunos:
-
La ejecución de un de proceso que puedan afectar la información
perteneciente a otro proceso que se ejecuta en paralelo a menos que esté
autorizado a hacerlo (datos compartidos).
-
El abrazo mortal, que es el estado en el que dos transacciones se queden
bloqueadas cada una esperando por recursos que esta utilizando la otra.
-
Inanición: Estado al que llega una transacción cuando es
seleccionada repetidamente para abortar y así evitar un abrazo mortal.
-
Livelock:
Estado en donde una transacción cambia continuamente de
estado en respuesta a cambios en otra transacción mientras la otra hace
lo mismo, sin conseguir ningún resultado con ello.
Existen distintos formas para solucionar estos problemas partiendo de
mecanismos de bajo nivel como semáforos que como obliga a los procesos a
ponerse en cola y así evitar problemas con memoria compartida. Mecanismos de
envío de mensajes para el mismo propósito. Hasta mecanismos de más alto
nivel como monitores que proveen ciertas operaciones internas que deben ser
llamadas para poder modificar los datos asegurando así el control sobre los
mismos.
Cuando se piensa en utilizar la
programación concurrente como
herramienta de desarrollo es preciso hablar primero de la metodología de
diseño de sistemas concurrentes y una en particular que es ampliamente usada
y define los siguientes pasos
Partición o
Descomposición
El problema computacional se descompone en pequeñas tareas pequeñas que
forman las unidades de concurrencia ya sea relacionando su nivel de
interacción o simplemente haciendo uso de alguna heurística conservando
siempre en mente la necesidad de eliminar redundancia en procesamiento y
almacenamiento.
Coordinación
Esto paso define la incorporación de mecanismos que permitan la comunicación
y sincronización de tareas que se puede realizar usando el paso de mensajes
o la memoria compartida.
Tratando siempre de garantizar que todas las tareas
tengan aproximadamente el mismo número de comunicaciones, que cada tarea se
comunica sólo con un pequeño número de vecinos y que estas operaciones de
comunicaciones puedan realizarse de forma simultanea.
Aglomeración o Asignación
En este paso, las tareas se agrupan basadas en procesos para optimizar el
rendimiento, reducir costes de desarrollo y garantizar la flexibilidad y
escalabilidad.
Proyección
En este último paso los procesos se asignan a los procesadores que haya
disponibles de forma que se minimice los costos de comunicación y al mismo
tiempo se maximice el uso de esos procesadores, es decir que exista un buen
balance.
Dentro de los lenguajes para la programación concurrente vale la pena hablar
un poco de dos en especial por su gran importancia, estos son:
Redes de Petri
Es un modelo gráfico para describir sistemas concurrentes, se puede ver como
un grafo dirigido y bipartido donde las dos clases de vértices se denominan
lugares y transiciones, se permiten lados paralelos en estas redes. Al
modelar una red de Petri, los lugares representan condiciones, las
transiciones representan eventos y la presencia de por lo menos una ficha en
un lugar indica que la condición se cumple. En una red de Petri (P) es un
lugar de entrada para la transición T, si existe un lado dirigido que va
desde el lugar P hasta la transmisión T. De igual forma se define un lugar
de salida. Si todo lugar de entrada para una transmisión T tiene al menos
una ficha, se dirá que T es permitida. Una transición permitida que quita
una ficha a cada lugar de entrada y agrega una ficha a cada de salida se
llama descarga.
Una marca M para una red de Petri esta viva si al empezar en M es posible
descargar cualquier transición dada a través de una sucesión adicional de
descarga, sin importar que la sucesión de descarga ya haya sucedido.
Una marca en una red de Petri es acotada si existe un entero positivo N que
tiene la propiedad de que en cualquier sucesión de descarga ningún lugar
recibe mas de N fichas. Ahora si una marca M esta acotada y en cualquier
sucesión de descarga ningún lugar recibe mas de una ficha, se dice que M es
una marca segura.
CSP (Communicating Sequential Processes)
Es una teoría matemática para especificar y verificar patrones de
comportamiento como abrazos mortales o Livelocks que se dan durante al
interacción de objetos concurrentes. Su semántica formal y composicional
esta completamente ligada con nuestra intuición natural sobre las formas en
que las cosas funcionan. Podemos ver el modelo como un grupo de componentes
organizados en una capa y comunicándose con otra capa de componentes a
través de canales unidireccionales. Este modelo nació debido a la necesidad
de encapsular la información de tal manera que esta permanezca correcta,
facilitar el diseño y poder detectar fallas antes de que estas ocurran.
Entre muchas de las ventajas que este modelo brindan esta su semántica
sencilla y por ende su facilidad de aplicar, sus kernel tan liviano
mejorando así el rendimiento de las máquinas y el que haya software del tipo
de FDR que permita verificar sí el modelo esta correcto o no.
El enfoque de sincronización que utiliza CSP es el de rende Vuez, que no
permite que un proceso escriba si al mismo tiempo el otro proceso esta
haciendo un leer y viceversa, como estas acciones en teoría se deben
realizar en paralelo estas deberían ser no bloqueantes[WOT01].
JCSP (Java communicating sequential processes)
Java también desarrolla su propia implementación basada en el álgebra de
CSP, orientada a la concurrencia de procesos. No se requiere conocimientos
avanzados en matemáticas para usar esta herramienta. Al contrario permite
una simplificación en el diseño que la concurrencia genera.
JCSP brinda la capacidad a través de bibliotecas completas de desarrollar
programas de funcionalidad compleja sobre capas de procesos de comunicación.
Con esta implementación el modelo CSP aparece soportado por las aplicaciones
multihilo de Java.
Los Procesos interactuan solamente a través de la primitivas de
sincronización de CSP como channels, CALL channels, timers, crews, barriers,
buckets o otros modos bien definidos de accesos a objetos pasivos. Dos
procesos no invocan procesos de si mismos. Estos procesos pueden corren en
forma secuencial o paralela.
Existen también en el mercado aplicaciones que nos permiten verificar
computacionalmente modelos especificados con CSP y una de las más
sobresalientes es FDR.
FDR (Failures-Divergence Refinement)
Permite la verificación de muchas de las propiedades de sistemas de estados
finitos y la investigación de sistemas que no pasan ese tipo de
verificaciones. Esta basado en la teoría de CSP. Fue desarrollado en la
universidad de Oxford.
Su método de probar si una propiedad se cumple es el de probar el
refinamiento de un sistema de transición que captura la propiedad a través
de la máquina candidato.
También permite verificar el determinismo de una máquina de estados y esto
es usado primordialmente para corroborar propiedades de seguridad
Ejemplo de programación concurrente-
La ejecución concurrente de los procesos la
indicaremos mediante la estructura cobegin/coend. La palabra cobegin indica el comienzo de la ejecución concurrente de los procesos
que se señalan hasta la sentencia coend.
Veamos un ejemplo:
S1;
COBEGIN
S2;
S3;
COEND
S4;
Esto quiere decir que:
• Primeramente se debe ejecutar S1, y no se
puede ejecutar en paralelo con nada.
• S2 y S3 se pueden ejecutar en paralelo,
luego de ejecutado S1
• S4 se ejecutará al terminar S2 y S3, y no se
puede ejecutar en paralelo con nada.
Veamos un ejemplo de un programa no
consistente: el orden de ejecución de las sentencias afecta el resultado.
J= 10;
COBEGIN
Print J;
J = 1000;
COEND
Print J;
Si se ejecutara primero la sentencia Print J
entonces se imprimiría “10 1000”. Pero si se ejecutara primero la sentencia
J=1000 entonces se imprimiría “1000 10”. El resultado no es el mismo, por lo
cual el programa es inconsistente.
