Programación Concurrente

Clase 7

Facultad de Informática
UNLP
 Links al archivo con audio

La teoría con los audios está en formato MP4. Debe descargar los
archivos comprimidos de los siguientes links:
 Programación concurrente en memoria distribuida:
https://drive.google.com/uc?id=1Xdh_8do7D0XmRQBNDHmHf6
MA3usfZaUS&export=download
 Pasaje de Mensajes Asincrónicos (PMA):
https://drive.google.com/uc?id=1h3mD73WydEjYSlGXMxQCiJL
wsyM3QEbt&export=download

Clase 7 2
Programación concurrente en
memoria distribuida
 Conceptos generales

 Arquitecturas de memoria distribuida ⇒ procesadores + memo local + red

de comunicaciones + mecanismo de comunicación / sincronización ⇒
intercambio de mensajes.
 Programa distribuido: programa concurrente comunicado por mensajes.
Supone la ejecución sobre una arquitectura de memoria distribuida, aunque
puedan ejecutarse sobre una de memoria compartida (o híbrida).
 Primitivas de pasaje de mensajes: interfaz con el sistema de
comunicaciones ⇒ semáforos + datos + sincronización.
 Los procesos SOLO comparten canales (físicos o lógicos). Variantes para
los canales:
• Mailbox, input port, link.
• Uni o bidireccionales.
• Sincrónicos o asincrónicos.

Clase 7 4
 Características

 Los canales son lo único que comparten los procesos

• Variables locales a un proceso (“cuidador”).
• La exclusión mutua no requiere mecanismo especial.
• Los procesos interactúan comunicándose.
• Accedidos por primitivas de envío y recepción.

 Mecanismos para el Procesamiento Distribuido:

• Pasaje de Mensajes Asincrónicos (PMA)
• Pasaje de Mensajes Sincrónico (PMS)
• Llamado a Procedimientos Remotos (RPC)
• Rendezvous

 La sincronización de la comunicación interproceso depende del patrón de

interacción:
• Productores y consumidores (Filtros o pipes)
• Clientes y servidores
• Pares que interactúan

Cada mecanismo es más adecuado para determinados patrones

Clase 7 5
 Relación entre mecanismos de sincronización

 Semáforos ⇒ mejora respecto de busy waiting.

 Monitores ⇒ combinan Exclusión Mutua implícita y señalización explícita.
 PM ⇒ extiende semáforos con datos.
 RPC y rendezvous ⇒ combina la interface procedural de monitores con PM implícito.

Busy waiting

Semáforos

Asincrónico
Monitores Pasaje de mensajes Sincrónico

RPC Rendezvous

Clase 7 6
Pasaje de Mensajes
Asincrónicos (PMA)
 Uso de canales en PMA
 PMA ⇒ canales = colas de mensajes enviados y aún no recibidos.
 Declaración de canales → chan ch (id1 : tipo1, ... , idn : tipon )
• chan entrada (char);
• chan acceso_disco (INT cilindro, INT bloque, INT cant, CHAR* buffer);
• chan resultado[n] (INT);

 Operación Send → un proceso agrega un mensaje al final de la cola (“ilimitada”) de

un canal ejecutando un send, que no bloquea al emisor:
send ch(expr1, ... , exprn);
 Operación Receive → un proceso recibe un mensaje desde un canal con receive, que
demora (“bloquea”) al receptor hasta que en el canal haya al menos un mensaje;
luego toma el primero y lo almacena en variables locales:
receive ch(var1, ... , varn);
Las variables del receive deben tener los mismos tipos que la declaración del canal.
Receive es una primitiva bloqueante, ya que produce un delay. Semántica: el
proceso NO hace nada hasta recibir un mensaje en la cola correspondiente al canal.
NO es necesario hacer polling.
Clase 7 8
 Características de los canales

 Acceso a los contenidos de cada canal: atómico y respeta orden FIFO.

 En principio los canales son ilimitados, aunque las implementaciones reales
tendrán un tamaño de buffer asignado.
 Se supone que los mensajes NO se pierden ni modifican y que todo
mensaje enviado en algún momento puede ser “leído”.
 empty(ch) → determina si la cola de un canal está vacía. Útil cuando el
proceso puede hacer trabajo productivo mientras espera un mensaje, pero
debe usarse con cuidado.
 O podría ser false, y no haber más mensajes cuando sigue ejecutando
(si no en el único en recibir por ese canal).
 La evaluación de empty podría ser true, y sin embargo existir un
mensaje al momento de que el proceso reanuda la ejecución.

Clase 7 9
 Características de los canales

Los canales son declarados globales a los procesos, ya que

pueden ser compartidos. Según la forma en que se usan podría
ser:
 Cualquier proceso puede enviar o recibir por alguno de los canales
declarados. En este caso suelen denominarse mailboxes.
 En algunos casos un canal tiene un solo receptor y muchos emisores
(input port).
 Si el canal tiene un único emisor y un único receptor se lo denomina
link: provee un “camino” entre el emisor y sus receptores.

Clase 7 10
 Ejemplo

chan entrada(char), salida(char [CantMax]); Process Proceso_1

{ char a;
Process Carac_a_Linea WHILE (true)
{ char linea [CantMax], int i = 0; { leer_carácter_por_teclado(a);
WHILE (true) send entrada(a);
{ receive entrada (linea[i]); }
WHILE (linea[i] ≠ CR and i < CantMax) }
{ i := i + 1;
receive entrada (linea[i]); Process Proceso_2
} { char res[CantMax];
linea [i] := EOL; WHILE (true)
send salida(linea); { receive salida(res);
i := 0; imprimir_en_pantalla(res);
} }
} }

Entrada Salida
Proceso_1 Carac_a_ Proceso_2
linea

Clase 7 11
 Productores y consumidores (filtro)
Red de Ordenación
 Filtro: proceso que recibe mensajes de uno o más canales de entrada y envía
mensajes a uno o más canales de salida. La salida de un filtro es función de su estado
inicial y de los valores recibidos.
 Esta función del filtro puede especificarse por un predicado que relacione los valores
de los mensajes de salida con los de entrada.
 Problema: ordenar una lista de N números de modo ascendente. Podemos pensar en
un filtro Sort con un canal de entrada (N números desordenados) y un canal de salida
(N números ordenados).
Process Sort
{ receive todos los números del canal entrada;
ordenar los números;
send de los números ordenados por el canal OUTPUT;
}

 ¿Cómo determina Sort que recibió todos los números?

• conoce N.
• envía N como el primer elemento a recibir por el canal entrada.
• cierra la lista de N números con un valor especial o “centinela”.

Clase 7 12
 Productores y consumidores (filtro)
Red de Ordenación
 Solución más eficiente que la “secuencial” ⇒ red de pequeños procesos que ejecutan
en paralelo e interactúan para “armar” la salida ordenada (merge network).
 Idea: mezclar repetidamente y en paralelo dos listas ordenadas de N1 elementos cada
una en una lista ordenada de 2*N1 elementos.
 Con PMA, pensamos en 2 canales de entrada por cada canal de salida, y un carácter
especial EOS cerrará cada lista parcial ordenada.
 La red es construida con filtros Merge:
• Cada Merge recibe valores de dos streams de entrada ordenados, in1 e in2, y produce un
stream de salida ordenado, out.
• Los streams terminan en EOS, y Merge agrega EOS al final.
• ¿Cómo implemento Merge?. Comparar repetidamente los próximos dos valores recibidos
desde in1 e in2 y enviar el menor a out.

in1
EOS 9 8 5 5 3 1 1 out
Merge EOS 9 8 8 5 5 5 4 3 2 1 1 1
in2
EOS 8 5 4 2 2 1

Clase 7 13
 Productores y consumidores (filtro)
Red de Ordenación

chan in1(int), in2(int), out(int);

Process Merge
{ int v1, v2;

receive in1(v1);
receive in2(v2);
while (v1 ≠ EOS) and (v2 ≠ EOS)
{ if (v1 ≤ v2) { send out(v1); receive in1(v1); }
else { send out(v2); receive in2(v2); }
}

if (v1 == EOS) while (v2 ≠ EOS) {send out(v2); receive in2(v2);}

else while (v1 ≠ EOS) {send out(v1); receive in1(v1);}

send out (EOS);

}

Clase 7 14
 Productores y consumidores (filtro)
Red de Ordenación

EOS 5 EOS 5 2
Merge
EOS 2
Merge EOS 8 5 2 1

EOS 1
Merge
EOS 8 1 EOS 8 7 6 5 4 3 2 1
EOS 8
Merge

EOS 3 EOS 7 3
Merge
EOS 7
EOS 7 6 4 3
Merge

EOS 4
Merge
EOS 6 EOS 6 4

Clase 7 15
 Productores y consumidores (filtro)
Red de Ordenación

 n-1 procesos; el ancho de la red es log2n.

 Canales de entrada y salida compartidos
 Puede programarse usando:
• Static naming (arreglo global de canales, y cada instancia de Merge
recibe desde 2 elementos del arreglo y envía a otro ⇒ embeber el árbol
en un arreglo).
• Dynamic naming (canales globales, parametrizar los procesos, y darle a
cada proceso 3 canales al crearlo; todos los Merge son idénticos, pero
se necesita un coordinador).
 Los filtros podemos conectarlos de distintas maneras. Solo se necesita que
la salida de uno cumpla las suposiciones de entrada del otro ⇒ pueden
reemplazarse si se mantienen los comportamientos de entrada y salida.

Clase 7 16
 Clientes y Servidores.
Monitores Activos
 Servidor: proceso que maneja pedidos (“requests”) de otros procesos clientes.
¿Cómo implementamos C/S con PMA?

 Dualidad entre monitores y PM: cada uno de ellos puede simular al otro.

Monitor ⇒ manejador de recurso. Encapsula variables permanentes que registran el

estado, y provee un conjunto de procedures. Los simulamos, usando procesos
servidores y PM, como procesos activos en lugar de como conjuntos pasivos de
procedures.

monitor Mname
{ declaración de variables permanentes;
código de inicialización;
procedure op(formales) { cuerpo de op;}
}

Clase 7 17
 Clientes y Servidores.
Monitores Activos

 Un Servidor es un proceso que maneja pedidos (requerimientos) de otros

procesos clientes. Veremos cómo implementar Cliente/Servidor con PMA.

 Un proceso Cliente que envía un mensaje a un canal de requerimientos

general, luego recibe el resultado desde un canal de respuesta propio (¿por
qué?).

 En un sistema distribuido, lo natural es que el proceso Servidor resida en

un procesador físico y M procesos Cliente residan en otros N procesadores
(N<= M).

Clase 7 18
 Clientes y Servidores.
Monitores Activos – 1 operación

 Para simular Mname, usamos un proceso server Servidor.

 Las variables permanentes serán variables locales de Servidor.
 Llamado: un proceso cliente envía un mensaje a un canal de requerimiento.
 Luego recibe el resultado por un canal de respuesta propio

Cliente[1]

Servidor
requerimiento

Cliente[n]

Clase 7 19
 Clientes y Servidores.
Monitores Activos – 1 operación
chan requerimiento (int idCliente, tipos de los valores de entrada );
chan respuesta[n] (tipos de los resultados );

Process Servidor
{ int idCliente;
declaración de variables permanentes;
código de inicialización;
while (true)
{ receive requerimiento (IdCliente, valores de entrada);
cuerpo de la operación op;
send respuesta[IdCliente] (resultados);
}
}

Process Cliente [i = 1 to n]
{ send requerimiento (i, argumentos);
receive respuesta[i] (resultados);
}

Clase 7 20
 Clientes y Servidores.
Monitores Activos – Múltiples operaciones
 Podemos generalizar esta solución de C/S con una única operación para considerar
múltiples operaciones.
 El IF del Servidor será un CASE con las distintas clases de operaciones.
 El cuerpo de cada operación toma datos de un canal de entrada en args y los
devuelve al cliente adecuado en resultados.

type clase_op = enum(op1, ..., opn);

type tipo_arg = union(arg1 : tipoAr1, ..., argn : tipoArn );
type tipo_result = union(res1 : tipoRe1, ..., resn : tipoRen );

chan request(int idCliente, clase_op, tipo_arg);

chan respuesta[n](tipo_result);

Process Servidor .....

Process Cliente [i = 1 to n] .....

Clase 7 21
 Clientes y Servidores.
Monitores Activos – Múltiples operaciones
Process Servidor
{ int IdCliente; clase_op oper; tipo_arg args;
tipo_result resultados;
código de inicialización;
while ( true)
{ receive request(IdCliente, oper, args);
if ( oper == op1 ) { cuerpo de op1;}
.......
elsif ( oper == opn ) { cuerpo de opn;}
send respuesta[IdCliente](resultados);
}
}
Process Cliente [i = 1 to n]
{ tipo_arg mis_args;
tipo_result mis_resultados;
send request(i, opk, mis_args);
receive respuesta[i] (mis_resultados);
}
Clase 7 22
 Clientes y Servidores.
Monitores Activos – Múltiples operaciones y variables condición
 Hasta ahora el monitor no requería variables condición ya que el Servidor no
requería demorar la atención de un pedido de servicio. Caso general: monitor con
múltiples operaciones y con sincronización por condición. Para los clientes, la
situación es transparente ⇒ cambia el servidor.

 Consideramos un caso específico de Monitor Administrador_Recurso

{ int disponible = MAXUNIDADES;
manejo de múltiples unidades de un set unidades = valores iniciales;
recurso (ejemplos: bloques de memoria, cond libre;
impresoras). procedure adquirir( int *Id )
• Los clientes “adquieren” y devuelven { if (disponible == 0) wait(libre)
unidades del recurso. else disponible --;
remove(unidades, id);
• Las unidades libres se insertan en un }
“conjunto” sobre el que se harán las
operaciones de INSERTAR y REMOVER. procedure liberar(int id )
{ insert(unidades, id);
• El número de unidades disponibles es lo if (empty(libre)) disponible ++
que “controla” nuestra variable de else signal(libre);
sincronización por condición. }
}

Clase 7 23
 Clientes y Servidores.
Monitores Activos – Múltiples operaciones y variables condición

 Caso en que el servidor tiene dos operaciones:

• Si no hay unidades disponibles, el servidor no puede esperar hasta responder al pedido ⇒
debe salvarlo y diferir la respuesta.
• Cuando una unidad es liberada, atiende un pedido salvado (si hay) enviando la unidad.
type clase_op = enum(adquirir, liberar); { if empty (pendientes)
chan request(int idCliente, claseOp oper, int idUnidad ); { disponible= disponible + 1;
chan respuesta[n] (int id_unidad); insert(unidades, id_unidad);
}
Process Administrador_Recurso else
{ int disponible = MAXUNIDADES; { pop (pendientes, IdCliente);
set unidades = valor inicial disponible; send respuesta[IdCliente](id_unidad);
queue pendientes; }
while (true) }
{ receive request (IdCliente, oper, id_unidad); } //while
if (oper == adquirir) } //process Administrador_Recurso
{ if (disponible > 0)
{ disponible = disponible - 1; Process Cliente[i = 1 to n]
remove (unidades, id_unidad); { int id_unidad;
send respuesta[IdCliente] (id_unidad); send request(i, adquirir, 0);
} receive respuesta[i](id_unidad);
else push (pendientes, IdCliente); //Usa la unidad
} send request(i, liberar, id_unidad);
else }

Clase 7 24
 Clientes y Servidores.
Monitores Activos – Múltiples operaciones y variables condición

 El monitor y el Servidor muestran la dualidad entre monitores y PM: hay una

correspondencia directa entre los mecanismos de ambos.
 La eficiencia de monitores o PM depende de la arquitectura física de soporte:
• Con MC conviene la invocación a procedimientos y la operación sobre variables
condición.
• Con arquitecturas físicamente distribuidas tienden a ser más eficientes los mecanismos de
PM.

 Dualidad entre Monitores y Pasaje de Mensajes

Programas con Monitores Programas basados en PM
• Variables permanentes ↔ Variables locales del servidor
• Identificadores de procedures ↔ Canal request y tipos de operación
• Llamado a procedure ↔ send request( ); receive respuesta
• Entry del monitor ↔ receive request( )
• Retorno del procedure ↔ send respuesta( )
• Sentencia wait ↔ Salvar pedido pendiente
• Sentencia signal ↔ Recuperar/ procesar pedido pendiente
• Cuerpos de los procedure ↔ Sentencias del “case” de acuerdo a la
clase de operación.
Clase 7 25
 Clientes y Servidores.
Sentencia de Alternativa Múltiple
 Resolución del mismo problema con sentencias de alternativa múltiple. Ventajas y
desventajas
chan pedido (int idCliente); Process Cliente[i = 1 to n]
chan liberar (int idUnidad); { int id_unidad;
chan respuesta[n] (int idUnidad);
send pedido (i);
Process Administrador_Recurso receive respuesta[i](id_unidad);
{ int disponible = MAXUNIDADES; //Usa la unidad
set unidades = valor inicial disponible; send liberar (id_unidad);
int id_unidad, idCliente; }
while (true)
{ if ( (not empty(pedido) and (disponible >0) ) →
receive pedido (idCliente);
disponible = disponible - 1;
remove (unidades, id_unidad);
send respuesta[idCliente] (id_unidad);
(not empty(liberar)) →
receive liberar (id_unidad);
disponible= disponible + 1;
insert(unidades, id_unidad);
} //if
} //while
} //process Administrador_Recurso

Clase 7 26
 Clientes y Servidores.
Continuidad Conversacional

 Existen A alumnos que hacen consultas a D docentes.

 El alumno espera hasta que un docente lo atiende, y a partir de ahí le

comienza a realizar las diferentes consultas hasta que no le queden dudas.

 Los alumnos son los procesos “clientes”, y los docentes los procesos
“Servidores”. Los procesos servidores son idénticos, y cualquiera de ellos
que esté libre puede atender un requerimiento de un alumno.

Todos los alumnos pueden pedir atención por un canal global y recibirán
respuesta de un docente dado por un canal propio. ¿Por qué?

Clase 7 27
 Clientes y Servidores.
Continuidad Conversacional

Alumno[1] atención Docente[1]

rta_atención[j]

consulta[i]
respuesta[j] Docente[i]
Alumno[j]

Docente[D]
Alumno[A]

Clase 7 28
 Clientes y Servidores.
Continuidad Conversacional
chan atención (int); Process Docente [d = 1 to D]
chan consulta[D] (string); { string preg, res;
chan rta_atención[A](int); int idAlumno;
chan respuesta[A] (string); bool seguir = false;

Process Alumno [a = 1 to A] while (true)

{ int idDocente; { receive atención (idAlumno);
string preg, res; send rta_atención[idAlumno](d);
seguir = true;
send atención (a);
while (seguir)
receive rta_atención[a] (idDocente);
{ receive consulta[d](preg);
while (tenga consultas para hacer)
if (preg == ‘FIN’) seguir = false
{ send consulta[idDocente](preg);
else
receive respuesta[a](res);
{ res = resolver la pregunta (preg)
}
send respuesta [idAlumno](res);
send consulta [idDocente] (‘FIN’);
}
}
}
}
}

 Este ejemplo de interacción entre clientes y servidores se denomina continuidad

conversacional (desde la solicitud de atención hasta la última consulta).
 atención es un canal compartido por el que cualquier Docente puede recibir. Si cada canal
puede tener un solo receptor, se necesita otro proceso intermedio. ¿Para qué?.
Clase 7 29
 Pares (peers) interactuantes.
Intercambio de Valores

Problema: cada proceso tiene un dato local V y los N procesos

deben saber cuál es el menor y cuál el mayor de los valores.

Ejemplo donde los procesadores están conectados por tres

modelos de arquitectura: centralizado, simétrico y en anillo
circular.

Clase 7 30
 Pares (peers) interactuantes.
Intercambio de Valores – Solución centralizada
 Cada proceso tiene un valor V local. Al final todos los procesos deben
conocer el mínimo y máximo valor de todo el sistema.
 La arquitectura centralizada es apta para una solución en que todos envían
su dato local V al procesador central, éste ordena los N datos y reenvía la
información del mayor y menor a todos los procesos ⇒ 2(N-1) mensajes.
chan valores(int), resultados[n-1] (int minimo, int maximo);
Process P[0] Process P[i=1 to n-1]
{ int v; int nuevo, minimo = v, máximo = v; { int v; int minimo, máximo;
for [i=1 to n-1] send valores (v);
{ receive valores (nuevo); receive resultados[i-1](minimo, maximo);
if (nuevo < minimo) minimo = nuevo; }
if (nuevo > maximo) maximo = nuevo;
}
for [i=1 to n-1]
send resultados [i-1] (minimo, maximo);
}

 ¿Se puede usar un único canal de resultados?

Clase 7 31
 Pares (peers) interactuantes.
Intercambio de Valores – Solución simétrica
 En la arquitectura simétrica o “full conected” hay un canal entre cada par de
procesos. Todos los procesos ejecutan el mismo algoritmo.
 Cada proceso trasmite su dato local V a los N-1 restantes procesos. Luego recibe y
procesa los N-1 datos que le faltan, de modo que en paralelo toda la arquitectura está
calculando el mínimo y el máximo y toda la arquitectura tiene acceso a los N datos.
 Ejemplo de solución SPMD: cada proceso ejecuta el mismo programa pero trabaja
sobre datos distintos ⇒N(N-1) mensajes.
 Si disponemos de una primitiva de broadcast, serán nuevamente N mensajes.
chan valores[n] (int);
Process P[i=0 to n-1]
{ int v=…, nuevo, minimo = v, máximo=v;
for [k=0 to n-1 st k <> i ]
send valores[k] (v);  ¿Se puede usar un único canal?
for [k=0 to n-1 st k <> i ]
{ receive valores[i] (nuevo);
if (nuevo < minimo) minimo = nuevo;
if (nuevo > maximo) maximo = nuevo;
}
}

Clase 7 32
 Pares (peers) interactuantes.
Intercambio de Valores – Solución en anillo circular
 Un tercer modo de organizar la solución es tener un anillo donde P[i] recibe
mensajes de P[i-1] y envía mensajes a P[i+1]. P[n-1] tiene como sucesor a P[0].
 Esquema de 2 etapas. En la primera cada proceso recibe dos valores y los compara
con su valor local, trasmitiendo un máximo local y un mínimo local a su sucesor. En
la segunda etapa todos deben recibir la circulación del máximo y el mínimo global.
• P[0] deberá ser algo diferente para chan valores[n] (int minimo, int maximo);
“arrancar” el procesamiento. Process P[0]
• Se requerirán (2N)-1 mensajes. { int v=…, minimo = v, máximo=v;
send valores[1] (minimo, maximo);
• Notar que si bien el número de receive valores[0] (minimo, maximo);
mensajes es lineal (igual que en la send valores[1] (minimo, maximo);
centralizada) los tiempos pueden ser }
muy diferentes. ¿Por qué?. Process P[i=1 to n-1]
{ int v=…, minimo, máximo;
receive valores[i] (minimo, maximo);
if (v<minimo) minimo = v;
if (v> maximo) maximo = v;
send valores[(i+1) mod n] (minimo, maximo);
receive valores[i] (minimo, maximo);
if (i < n-1) send valores[i+1] (minimo, maximo);
};

Clase 7 33
 Pares (peers) interactuantes.
Comentarios sobre las soluciones

 Simétrica es la más corta y sencilla de programar, pero usa el mayor número

de mensajes (si no hay broadcast). Pueden transmitirse en paralelo si la red
soporta transmisiones concurrentes, pero el overhead de comunicación acota
el speedup.
 Centralizada y anillo usan n° lineal de mensajes, pero tienen distintos
patrones de comunicación que llevan a distinta performance:
• En centralizada, los mensajes al coordinador se envían casi al mismo tiempo ⇒
sólo el primer receive del coordinador demora mucho.
• En anillo, todos los procesos son productores y consumidores. El último tiene
que esperar a que todos los otros (uno por vez) reciban un mensaje, hacer poco
cómputo, y enviar su resultado.
Los mensajes circulan 2 veces completas por el anillo ⇒ Solución
inherentemente lineal y lenta para este problema.

Clase 7 34