Programación Concurrente Imperativa

La Programación Concurrente estudia y diseña algoritmos de tipo imperativo con el objetivo de resolver problemas, o que se ejecuten tareas utilizando al menos dos programas diferentes los cuales se ejecutan de forma simultánea.
Estos programas terminan cuando terminan todos los programas secuenciales que lo integran.

Está ligado al concepto de PROCESO:

Un proceso es un programa secuencial considerado en ejecución.

En general, estos procesos:

- Compiten para acceder a recursos escasos.

- Cooperan para realizar cierta tarea.

Algoritmo Concurrente:

Dada las especificaciones de un problema, consiste en diseñar y gestionar:

- Cuántos y qué tipos de procesos emplear para hacerlo.

- Cómo deben interactuar los procesos implicados en el diseño.

REGLAS BÁSICAS QUE HAY QUE CONSIDERAR EN PROGRAMAS CONCURRENTES:

- La interacción entre procesos debe estar perfectamente SINCRONIZADA.

- Los procesos deben COMUNICARSE para poder efectuar esa sincronización.

TIPOS DE PROGRAMAS CONCURRENTES:

En función de cómo se efectúa la comunicación entre procesos, en programación concurrente imperativa, existen básicamente dos tipos de programas:

- Programas en los que la comunicación entre procesos se realiza leyendo y escribiendo el contenido de variables globales y compartidas por todos los procesos implicados en el programa. (En la mayoría de las implementaciones de este tipo se utilizan variables globales ubicadas en una memoria común en la que se ejecuta el código de los procesos). Son los que históricamente se han llamado concurrentes.

- Programas en los que la comunicación entre procesos se realiza enviando y recibiendo mensajes utilizando canales de comunicación entre procesos. (Los canales suelen representarse como colas que contienen los mensajes). Son programas que se engloban en lo que se entiende actualmente por Programación Distribuida.

COMUNICACIÓN BASADA EN LA UTILIZACIÓN DE VARIABLES GLOBALES COMPARTIDAS POR LOS PROCESOS. (CONCURRENCIA):

Un modelo teórico de concurrencia:

Se basa en los conceptos:

1. ATOMICIDAD. Puede ilustrarse como sigue: Un programa concurrente imperativo π, que denotaremos por el siguiente algoritmo:

π:: variables_globales
co P//Q//...//R// oc,

está formado por dos o más programas secuenciales:

P: S1;S2;...;Si;...;Sp-1;Sp,
Q: T1;T2;...;Tq,
...
R: U1;U2;...;Ur

que comparten variables globales para comunicarse.

Cada programa se ejecuta en el o en los procesadores de una máquina, después de que cada instrucción se traduzca, en lenguaje máquina, a instrucciones atómicas como por ejemplo:

S1: < S11 >;< S12 >;...;< S1s1 >
S2: < S21 >;< S22 >;...;< S2s2 >
...
Si: < Si1 >;< Si2 >;...;< Sisi >
...
Sp: < Sp1 >;< Sp2 >;...;< Spsp >

Expresiones en las que < S > representa la ejecución de S con atomicidad, indicando con este concepto que, si se inicia la ejecución de la instrucción S en un procesador de la máquina, ninguna otra instrucción puede empezarse a ejecutar en el mismo procesador hasta que finalice la ejecución de S.

La atomicidad real depende de la máquina y del lenguaje máquina. Para elaborar un modelo de diseño de algoritmos concurrentes que sea independiente de la máquina en la que se ejecuten los procesos asociados a esos algoritmos, se han diseñado elementos propios de programación concurrente (tales como semáforos y monitores) que proporcionan una atomicidad virtual (representada aquí por instrucciones S;P;...;R encerradas entre los símbolos "<" y ">") de manera que se consigue que una o varias instrucciones consecutivas del código de un proceso se consideren a todos los efectos como una instrucción atómica, con independencia de la máquina en la que se ejecute:

P: S1;S2;S3;S4;S5...;Sn-1;Sn -->

P: S1;< S2;S3;S4 >;S5...;Sn-1;Sn -->

P: S1;< S* >;S5...;Sn-1;Sn

siendo S* el subprograma de P tal que S*: S2;S3;S4.

2. INTERFOLIZACIÓN de instrucciones atómicas, que ilustro como sigue:

Los procesos P, Q,...,R del programa concurrente

π:: variables_globales
co P//Q//...//R// oc

pueden ejecutarse simultáneamente en una máquina con varios procesadores o debe pareces que se ejecutan simultáneamente en una máquina con un único procesador (por ejemplo, ejecuciones administradas por un sistema operativo como UNIX).

Para evitar de nuevo la dependencia de la máquina (multiprocesador o no) en la que se ejecute el programa, en este modelo teórico de programación concurrente imperativa se supone que:

Todo conjunto de instrucciones atómicas que resulta al considerar globalmente el código de todos los procesos P, Q,...,R, se ejecuta secuencialmente teniendo en cuenta únicamente la interfoliación entre instrucciones atómicas, que consiste en obtener secuencias utilizando todas las instrucciones, pero conservando el orden que tienen las que pertenecen a un mismo proceso.

Se obtendría así varios algoritmos distintos, llamados Historias Asociadas A La Ejecucuón Del Programa π.

EJEMPLO: Algoritmo para procesos lectores y procesos escritores que acceden concurrentemente a una misma base de datos.

Consideramos n, (n>=2), procesos diferenciados, pero con código idéntico que llamaremos procesos lectores: Lector[1], Lector[2], ..., Lector[n] y otros procesos m, (m>=2), procesos con código idéntico que llamaremos procesos escritores: Escritor[1], Escritor[2], ..., Escritor[m].

Estos procesos deben acceder repetida y concurrentemente a los ítems de una base de datos bajo las siguientes condiciones:

1) La función de cada proceso lector consiste en repetir la siguiente tarea: intentar entrar en la base de datos, leer ítems de la base de datos y salir de la base de datos. Puesto que no modificamos información, pueden coincidir varios lectores diferentes en el proceso de lectura de ítems.

2) Cada proceso escritor debe intentar entrar en la base de datos, modificar parámetros de los ítems de la misma y finalmente salir de la base de datos. Para evitar posibles inconsistencias, esta tarea de modificación debe hacerse con exclusividad, es decir, la presencia de un escritor en la base de datos excluye la presencia en la misma de cualquier otro proceso lector o proceso escritor.

Por lo tanto, la función de cada uno de los dos tipos de procesos puede expresarse por los siguientes esquemas:

Lector[i]:: mientras TRUE -->
Ejecutar_protocolo_entrada_lector
Leer
Ejecutar_protocolo_salida_lector
fin

Escritor[j]:: mientras TRUE -->
Ejecutar_protocolo_entrada_escritor
Escribir
Ejecutar_protocolo_salida_escritor
fin

En los que la frase "mientras TRUE" indica que han de intentar efectuar su código repetidamente, y en los que las frases del tipo "Ejecutar_protocolo..." se traducirán por instrucciones de programa que contengan variables globales (es decir visibles y modificables por los distintos procesos) y que permitan la intercomunicación necesaria para conocer el estado del recurso (en este caso la presencia o ausencia de procesos en la base de datos). Además, en esos protocolos se deben reflejar tanto la atomicidad como la sincronización necesaria para asegurar que se ejecutarán únicamente las historias que se ajusten a las condiciones del problema.



Volveremos más adelante a este algoritmo.

SEMÁFOROS

Un semáforo es un tipo abstracto de datos cuya representación viene dada por una variable entera que es manipulada por dos únicas operaciones atómicas: P (espera) y V (señal). La operación V (del holandés verhogen=incrementar) señala la ocurrencia de un evento. La operación P (proberen=comprobar) se utiliza para poner en espera a un proceso hasta que se verifique una condición.

Las dos operaciones deben implementarse en un programa de forma que conserven siempre el siguiente invariante de semáforo:

Invariante de Semáforo IS: Si s, que pertenece a Z, representa al semáforo, nP y nV son respectivamente los números de operaciones del tipo P y del tipo V completadas sobro s, e inicio, que pertenece a Z, es el valor inicial del semáforo s, entonces para todo estado visible del programa se debe verificar:

SEM: nP<=nV + inicio.

Es decir, la ejecución de una operación P puede ponerse en espera hasta que se haya ejecutado un número adecuado de operaciones V.

Las implementaciones del semáforo s por

s = inicio + nV - nP

reduce el IS a: SEM: s>=0

Dado que una nueva operación P realizada sobre s incrementa nP, el resultado (según se desprende de la expresión s = inicio + nV - nP) es un decremento de s.

Como SEM es invariante global, se verifica:

wp(s:=s-1, SEM)= wp(s:=s-1, s>=0)=s-1>=0 = s>0

En consecuencia, la operación P sobre el semáforo s es del tipo:

P(s): < await s > 0 --> s := s-1 >

Una operación V sobre el semáforo s incrementa nV y en consecuencia s y (teniendo en cuenta que s >= 0) obtenemos:

wp(s:= s+1, SEM) = wp(s:=s+1, s>=0)= s+1 >= 0 = true

con lo que la operación V sobre s se reduce a:

V(s): < s:= s+1 >

Un semáforo s se llama binario si s vale {0,1}. En este caso se debe cumplir para la operación V:

V(s): < await s < 1 --> s:= s+1 >

Por ejemplo, la solución el problema de la sección crítica asociada al invariante (dentro[1]+ dentro[2]+ ...+ dentro[n]<=1) = SUMA(<=1)

var dentro[i:1..n]:= ([n],0)

Proceso[i:1..n]::
< await SUMA 0 --> dentro[i]:=dentro[i]+1 >
sección crítica i
< dentro[i]:=dentro[i]-1 >
sección no crítica i

Con el cambio de variables:

exmut=1-SUMA, se verifica:

- exmut >= 0 (puede ser una variable de tipo semáforo)
- (SUMA = 0) = (exmut>0)
- (dentro[i]:=dentro[i]+1) = (exmut:=exmut-1)
-(dentro[i]:=dentro[i]-1) = (exmut:=exmut+1)

Luego se verifican las equivalencias:

< await SUMA 0 --> dentro[i]:=dentro[i]+1 > =
< await exmut > 0 --> exmut:= exmut -1 > = P (exmut)

y

< dentro[i]:= dentro[i]-1 > = < exmut:= exmut+1 > = V(exmut)

En consecuencia el código queda al efectuar el cambio de variables:

var exmut:=1

Proceso[i:1..n]::
< await exmut > 0 --> exmut:= exmut-1 >
sección crítica i
< exmut:0 exmut+1 >
sección no crítica i

Y se transforma, al expresarlo con las operaciones P y V sobre semáforos, en:

var exmut:sem:=1

Proceso[i:1..n]::
P(exmut) #Prot. Ent.
sección crítica i
V(exmut)
sección no crítica #Prot.S.

Lectores y escritores.

Dos tipos de procesos, lectores y escritores ejecutan repetida y concurrentemente su código bajo las condiciones siguientes:

(1) Hay al menos dos procesos lectores y dos procesos escritores.

(2) En la ejecución de su código, los lectores y escritores deben acceder a una misma base de datos en la que los primeros leen ítems y los segundos editan ítems, por lo que la parte de código de un escritor en la base de datos es sección crítica, y debe hacerse con exclusión mutua. En conclusión, la presencia de un escritor en la base de datos excluye la presencia de cualquier otro proceso.

(3) Si un proceso intenta ejecutar la parte de código que se refiere a la base de datos, debe conseguir ejecutarlo. Además, todo proceso que consiga iniciar esa parte de código, la acaba y sale de la base de datos.

Primera aproximación:
Suponemos que hay m lectores y n escritores (m>1, n>1)

Se utilizan variables globales que indican la situación de los procesos en la base de datos:

nl: contador de lectores en el recurso,
Leyendo: presencia de algún lector en el recurso.
escribiendo[i:1..n]: presencia de cada escritor en el recurso.

Los lectores tienen un compromiso: señalar el caso en el que no hay o hay lectores en la base de datos.

var nl:=0 #contador de lectores en el recurso
var leyendo:=0 #presencia de algún lector en el recurso
var escribiendo[i]:=([n],0) #presencia de escritor i en el recurso.

lector[i:1..m]:: do true -->
< nl:=nl +1, if nl=1 --> leyendo:= leyendo+1 fi >
leer en la base de datos
< nl:=nl-1, if nl=0 --> leyendo:=leyendo-1 fi >
od

escritor[j:1..n]::do true -->
< escribiendo[i]:=escribiendo[i]+1 >
escribir en la base de datos
< escribiendo[i]:= escribiendo[i]-1 >
od

Invariante global:

IG: leyendo + escribiendo[1] + ... + escribiendo[n] <= 1

Escribimos

SUMA = leyendo + escribiendo[1] + ... + escribiendo[n]

Corrección:

wp(leyendo:=leyendo+1,IG) = (SUMA=0)
wp(leyendo:=leyendo-1,IG) = (SUMA<=2)
wp(escribiendo[i]:=escribiendo[i]+1,IG) = (SUMA=0)
wp(escribiendo[i]:=escribiendo[i]-1,IG) = (SUMA<=2)

Hay que sincronizar en los protocolos de entrada de los lectores y de los escritores.

El algoritmo quedaría:

var nl:=0 #contador de lectores en el recurso
var leyendo:=0 #presencia de algún lector en el recurso
var escribiendo[i]:=([n],0) #presencia de escritor i en el recurso.

lector[i:1..m]::do true -->
< nl:=nl+1, if nl=1 --> await SUMA = 0 --> leyendo:=leyendo+1 fi >
leer en la base de datos
leyendo:= leyendo -1 fi >
od

escritor[j:1..n]:: do true -->
< await SUMA = 0 --> escribiendo[i]:=escribiendo[i]+1 >
escribir en la base de datos
< escribiendo[i]:=escribiendo[i-1]
od

Si se hace el cambio:

LE=1-(leyendo+escribiendo[1]+...+escribiendo[n]) = 1-SUMA,

se obtiene: (SUMA=0)=(LE>0)
(leyendo:=leyendo+1)=(LE:=LE-1)
(leyendo:=leyendo-1)=(LE:=LE+1)
(escribiendo[i]:=escribiendo[i]+1)=(LE:=LE-1)
(escribiendo[i]:=escribiendo[i]-1)=(LE:=LE+1)

var nl:=0
var LE:=1

lector[i:1..m]::do true -->
< nl:=nl+1, if nl=1 --> await LE>0 --> LE:=LE-1 fi >
leer en la base de dator
< nl:=nl-1, if nl=0 --> LE:=LE+1 fi >
od

escritor[j:1..n]::do true -->
< await LE > 0 --> LE:=LE-1 >
escribir en la base de datos
< LE:=LE+1 >
od

---------------

No es equitativo, ya que la presencia de un lector en el recurso favorece la entrada de los otros lectores aunque un escritor esté esperando a entrar con antelación.

La variable LE es un semáforo binario {0,1}
Con las operaciones:

P(LE): < await LE > 0 --> LE:=LE-1 >

V(LE): < LE:=LE+1 >

(Solución obtenida partiendo del invariante global: leyendo+escribiendo[1]+...+escribiendo[n]<=1)

Con el semáforo de exclusión mutua exmutL para lectores:

< nl:=nl+1; if nl=1 --> await LE>0 --> LE:=LE-1 fi >
P(exmutL)
nl:=nl+1; if nl=1 --> await LE>0 --> LE:=LE-1 fi
V(exmutL), etc

var nl:=0
var exmutL:sem:=1 #semáforo de exclusión entre lectores
var LE:sem:=1 #semáforo asociado al invariante

lector[i:1..m]:: do true -->
P(exmutL)
nl:=nl+1
if nl=1 --> P(LE) fi
V(exmutL)
leer en la base de datos
P(exmutL)
nl:=nl-1
if nl=0 --> V(LE) fi
V(exmutL)
od

escritor[j:1..n]:: do true -->
P(LE)
escribir en la base de datos
V(LE)
od