31-5-20041 programación distribuida los métodos de sincronización que hemos visto se basan en...

31-5-2004 1

Programación Distribuida

Los métodos de sincronización que hemos visto se basan en leer y escribir variables compartidas, lo cual significa que los programas concurrentes se ejecuten sobre hardware con acceso a memoria compartida.

Las arquitecturas de memoria distribuida son cada vez más habituales. Esto implica procesadores + memoria local + red de comunicaciones + otro mecanismo de comunicación/sincronización mensajes.

Programación Concurrente 2003 - Clase 7

31-5-2004 2


Para escribir programas sobre una arquitectura de memoria distribuida, es necesario definir la interfaz con el sistema de comunicacionesprimitivas de pasaje de mensajes los procesos no comparten memoria, sino canales (físicos o lógicos).


Los programas concurrentes que se comunican por mensajes se denominan programas distribuidos. Esto supone la ejecución sobre una arquitectura de memoria distribuída, aunque puedan ejecutarse sobre una arquitectura de memoria compartida ( o híbrida).

31-5-2004 3


En un programa distribuido los canales son el único objeto que los procesos compartenno hay acceso concurrente a variables y la exclusión mutua no requiere ningún mecanismo especial.

Entre los mecanismos para la programación distribuida (que dependen del modo en que interactúan los procesos) tenemos productores-consumidores, clientes-servidores e interacción entre pares.


31-5-2004 4

Programación Distribuida. Conceptos de pasaje de mensajes.

Los canales pueden proveer comunicaciones half-duplex o full-duplex. A su vez estas comunicaciones pueden ser asincrónicas (no bloqueantes) o sincrónicas (bloqueantes).

Las combinaciones dan lugar a AMP, SMP, RPC y Rendezvous que son los 4 mecanismos (equivalentes funcionalmente ya que pueden intercambiarse) cuya sintaxis y semántica serán nuestro objetivo.


31-5-2004 5

Programación Distribuida. Conceptos de pasaje de mensajes.

El pasaje de mensajes (AMP o SMP) puede verse como una extensión de semáforos con datos. En RPC y Rendezvous se combina la interfaz procedural de los monitores con pasaje de mensajes implícito.


Si bien decimos que son equivalentes, veremos que AMP y SMP son mejores para modelos tipo productor-consumidor o pares interactivos, mientras RPC y Rendezvous serán más útiles para esquemas C-S.

31-5-2004 6

Pasaje de mensajes asincrónicos.

En ASM los canales son colas de mensajes que han sido enviados y aún no recibidos:chan ch(id1 : tipo1, ... , idn : tipon )

chan input(char);

chan disk_access(INT cylinder, INT block, INT count, CHAR* buffer);

chan result[n] (INT); {arreglo de canales}


31-5-2004 7


Un proceso agrega un mensaje al final de la cola de un canal ejecutando un send, que no bloquea al emisor send ch(expr1, ... , exprn);

Un proceso recibe un mensaje desde un canal con un receive, que demora al receptor hasta que en el canal haya al menos un mensaje; luego toma el primer mensaje y lo almacena en variables localesreceive ch(var1, ... , varn);


31-5-2004 8


Las variables del receive deben tener los mismos tipos que la declaración del canal ch.

Receive es una primitiva bloqueante, ya que produce un delay.

Sin embargo la semántica es que el proceso NO hace nada hasta recibir un mensaje en la cola correspondiente al canal ch; NO es necesario hacer polling (aquí tendríamos busy waiting)


31-5-2004 9


El acceso a los contenidos de cada canal es atómico y se respeta el 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


31-5-2004 10

Pasaje de mensajes asincrónicos.Un primer ejemplo.

Veremos un proceso filtro que recibe caracteres desde el canal entrada y los ensambla en líneas que envía al canal salida. CR indica el final de una línea de entrada; una línea contiene a lo sumo CANTMAX caracteres; el caráter especial EOL se agrega a la salida como fin de línea.

chan entrada(char), salida(char [CantMax]);Process Carac_a_Linea { char linea [CantMax], int i := 0;

WHILE true { receive entrada (linea[i]); WHILE linea[i] CR and i < CantMax { i := i + 1; receive entrada (linea[i]); } linea [i] := EOL; send salida(linea); i := 0 } }


31-5-2004 11

Pasaje de mensajes asincrónicos.Un primer ejemplo.

En el ejemplo anterior los canales Entrada y Salida son declarados globales a los procesos, ya que pueden ser compartidos.

Cualquier proceso puede enviar o recibir por alguno de los canales declarados, que a veces se denominan mailboxes.

En algunos casos un canal tiene un solo receptor y muchos emisores. Entonces se lo llama input port.

Si sucede la inversa (muchos receptores, un solo emisor) se lo denomina link ya que provee un “camino” entre el emisor y sus receptores.

Empty (ch) puede servir cuando un proceso NO quiere demorarse haciendo receive de un canal sin datos (imaginar un scheduler con varios canales que servir).


31-5-2004 12

Programación Distribuida: Filtros---> Red de ordenación de datos

Un filtro es un 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 adecuado que relacione los valores de los mensajes de salida con los de entrada.

Si consideramos el problema de ordenar una lista de N números de modo ascendente podemos pensar en un filtro SORT que tiene 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 INPUT; ordenar los números; send de los números ordenados por el canal OUTPUT;}


31-5-2004 13


El primer problema es que debemos conocer N.Para esto podemos enviar N como el primer elemento a recibir por el canal INPUT, o bien cerrar la lista de N números con un valor especial o “centinela”.

Podemos encarar una solución más eficiente que la “secuencial” pensando en una red de procesos que ejecutan en paralelo e interactúan para “armar” la salida ordenada. (merge network).

La idea es mezclar repetidamente y en paralelo dos listas ordenadas de N1 elementos cada una en una lista ordenada de 2*N1 elementos. En nuestro esquema de AMP estamos pensando en 2 canales de entrada por cada canal de salida. Un carácter especial EOS cerrará cada lista parcial ordenada.


31-5-2004 14


La red es construida con filtros MergeCada Merge recibe valores de dos streams de entrada ordenados, in1 e in2, y produce un stream de salida ordenado, out

Cómo implemento Merge ?a) Recibir todos los valores, mezclarlos, y enviar la lista mezclada a out (requiere almacenar todos los valores de entrada)

b) Comparar repetidamente los próximos dos valores recibidos desde in1 e in2 y enviar el menor a out


31-5-2004 15

Filtros---> Proceso MERGE

char 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); } # (v2 < v1) } #Consumir el resto de los datos IF (v1 == EOS) WHILE ( v2 EOS) { send out(v2); receive in2(v2);} ELSE # (v2 == EOS) WHILE ( v1 EOS) { send out(v1); receive in1(v1);} #Agregar el centinela al final send out (EOS) ; }


31-5-2004 16

Filtros---> Proceso MERGE


31-5-2004 17

Clientes y Servidores.

Un Servidor es un proceso que maneja pedidos (“requests”) de otros procesos clientes. Veremos como implementar C-S con AMP.

Ahora analizaremos como convertir monitores en servidores y como manejar recursos compartidos. Los ejemplos muestran la dualidad entre monitores y pasaje de mensajes: cada uno de ellos puede simular al otro.

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

}


31-5-2004 18

Monitores Activos. C-S con 1 operación

Para simular Mname, usamos un proceso server Sname. Las variables permanentes serán variables locales de Sname.Un proceso cliente que envía un mensaje a un canal de request; luego recibe el resultado desde un canal de reply propio.

chan request (INT IdCliente, tipos de los valores de entrada );chan reply[n] (tipos de los resultados );Process Server { INT IdCliente; declaración de variables permanentes; código de inicialización; WHILE true { receive request (IdCliente, valores de entrada); cuerpo de la operación op; send reply[IdCliente](resultados); }Process Client [i=0 to n-1] { send request(i, argumentos) # “llama” a op receive reply[i] (resultados) # espera el reply}


31-5-2004 19

Clientes-Servidor con múltiples operaciones.

Generalizando esta solución de C-S con una sóla operación, podemos considerar el caso de múltiples operaciones. El IF en el servidor funciona como un CASE que bifurca a diferentes clases de operaciones. El cuerpo de cada operación toma los datos de un canal de entrada en args y los devuelve al cliente adecuado en results.

type op_kind = enum(op1, ..., opn);type arg_type = union(arg1 : atype1, ..., argn : atypen );type result_type = union(res1 : rtype1, ..., resn : rtypen );chan request(INT IdCliente, op_kind, arg_type);chan reply[n](res_type);

Process Server Process Client [i=0 to n-1]


31-5-2004 20


Process Server { INT IdCliente; OP_KIND kind; ARG_TYPES args; RES_TYPE results; #otras declaraciones de variables código de inicialización;

WHILE ( true) { receive request(IdCliente, kind, args); IF ( kind == op1 ) { cuerpo de op1;} ... ELSE IF ( kind == opn ) { cuerpo de opn;} } send reply[IdCliente](results); }}


31-5-2004 21


Process Client [i = 0 to n-1] {

ARG_TYPE myargs; RESULT_TYPE myresults; # poner los valores de los argumentos en myargs; send request(i, opk, myargs); # “llama” a opk

receive reply[i] (myresults); # espera el reply }


31-5-2004 22

Dualidad entre monitores y Pasaje de Mensajes para manejar recursos.

Veremos un problema más general: hasta ahora nuestro Monitor no requería variables de condiciónServer no requería demorar la atención de un pedido de servicio.

Ahora veremos el caso general de un monitor que tiene múltiples operaciones y utiliza sincronización por condición.

Para los clientes, esta situación es transparente cambia el servidor.


31-5-2004 23


Consideraremos un caso específico de manejo de múltiples unidades de un dado recurso (bloques de memoria , PRNs por ejemplo).

Los clientes “adquieren” y devuelven unidades del recurso. Las unidades libres se insertan en un “conjunto” sobre el que se harán las operaciones de INSERTAR y REMOVER.

Obviamente el número de unidades disponibles será lo que controlará nuestra variable de sincronización por condición.


31-5-2004 24


monitor Resource_Allocator {

INT avail = MAXUNITS; SET units = valores iniciales; COND free; # TRUE cuando hay recursos procedure acquire( INT Id ) { IF (avail == 0) wait(free); ELSE avail := avail - 1; remove(units, id); } procedure release( INT id ) { insert(units, id); IF (empty(free)) avail := avail + 1; ELSE signal(free); }}


31-5-2004 25


type op_kind = enum(ACQUIRE,RELEASE);chan request(INT IdCliente, OP_KIND kind , INT unitid );chan reply[n] (INT unitid);

Process Allocator {INT avail= MAXUNITS;SET units = valor inicial disponible;QUEUE pending; # Inicialmente vacía# declaración de otras variables;

........... sigue


31-5-2004 26


WHILE (true) { receive request(IdCliente, kind, unitid); IF (kind == ACQUIRE) { IF (avail > 0) { # puede atender el pedido ahora avail := avail - 1; remove(units, unitid); send reply[IdCliente](unitid); } ELSE # recordar el pedido insert(pending, IdCliente);

ELSE # significa que el pedido es un RELEASE IF empty(pending) avail := avail + 1; insert(units,unitid);

ELSE { # darle unitid a un cliente esperando remove(pending, IdCliente); send reply[IdCliente](unitid); } } }

}


31-5-2004 27


Process Client[i=0 to n-1] { INT unitid; send request(i, ACQUIRE, 0) # “llama” a request

receive reply[i](unitid);

# usa el recurso unitid, y luego lo libera;

send release(i, RELEASE, unitid); .......}


31-5-2004 28


La eficiencia de monitores o pasaje de mensajes depende de la arquitectura física de soporte.

Con memoria compartida conviene la invocación a procedimientos y la operación sobre variables de condición.

Con arquitecturas físicamente distribuida tienden a ser más eficientes los mecanismos de pasaje de mensajes.

En general los sistemas operativos y los lenguajes de programación tienden a facilitar la utilización de ambos mecanismos.


31-5-2004 29

File Servers: Un ejemplo de Cliente-Servidor con AMP

Los procesos “cliente” pueden acceder a archivos externos, almacenados en disco. Deben hacer un OPEN del archivo; si el archivo se puede abrir pueden hacer una serie de pedidos de READ o WRITE y luego pueden cerrar (CLOSE) el archivo.

Si tenemos N archivos, consideraremos 1 File Server por archivo.Los procesos server serán idénticos, y cualquiera de ellos que esté libre podrá atender un requerimiento de OPEN.

Todos los clientes podrán pedir un OPEN por un canal global (qué argumentos serán necesarios??) y recibirán respuesta de un servidor dado por un canal propio. Por qué??


31-5-2004 30

File Servers: Un ejemplo de Cliente-Servidor con AMP .

type kind = enum(READ,WRITE,CLOSE)chan open (STRING fname; INT clientid);chan access[n] (INT kind, otros tipos de argumentos);chan open_reply[m](INT serverId); #Nro. Server o Cod. Errorchan access_reply[m] (tipos resultado); #datos, flags de error

Client [j=0 to m-1] { INT serverId; otras declaraciones; send open (“Pirulo.doc”, j); # trata de abrir el archivo receive open_reply[j] (serverId); # Nro. de servidor send access[serverid](argumentos de pedido); receive access_reply[j](resultados); .....}


31-5-2004 31


Process File_Server[i=0 to n-1] { STRING fname; INT clientId; Kind k; otras declaraciones; BOOL more= false; WHILE (true) { receive open(fname,clientid); OPEN FILE fname ; IF OK THEN { send open_reply[clientid](i); more := true; WHILE more { receive access[i](k,args); IF k == READ procesa pedido de lectura; ELSE IF k == WRITE procesa pedido de escritura; ELSE # k== CLOSE procesa el cierre; more=false; send access_reply[clientId] (results); } } }


31-5-2004 32


Este ejemplo de interacción entre clientes y servidores se denomina continuidad conversacional. (del OPEN al CLOSE).

Si el lenguaje soportara creación dinámica de procesos y canales, el número N de file servers puede adaptarse a los requerimientos del sistema real.

Otro esquema de solución sería un file server por disco. Analicemos conceptualmente las diferencias...

Otra solución: Sun Netwok File System: OPEN ===> adquirir un descriptor completo del file. Las operaciones sucesivas son RPC trasmitiendo el descriptor. (ventajas y desventajas)


31-5-2004 33

Intercambio de datos en pares (“peers”) con AMP

Nos planteamos un ejemplo donde los procesadores distribuídos están conectados por tres modelos de arquitectura: centralizado, simétrico y en anillo circular. El problema que planteamos es muy simple: cada proceso tiene un dato local V y los N procesos deben saber cual es el menor y cual el mayor de los valores en la red.

La arquitectura centralizada se presta para una solución donde todos envían su dato local V al procesador central y éste ordena los N datos y reenvía la información del mayor y menor valor a todos los procesos.

La solución centralizada requiere 2(N-1) mensajes. Si p[0] dispone de una primitiva de broadcast este número se reduce a N mensajes.


31-5-2004 34

Intercambio de datos en pares (“peers”) con AMP


31-5-2004 35

Intercambio de datos en pares con AMP: solución centralizada

Chan values(INT), results[n] (INT minimo, INT maximo);Process P[0] { #Proceso coordinador. v ya está inicializado. INT v; INT new, minimo = v, máximo=v; FOR [i=1 to n-1] { receive values (new); IF (new < minimo) minimo = new; IF (new > maximo) maximo = new; } FOR [i=1 to n-1] send results [i] (minimo, maximo);}

Process P[i=1 to n-1] { #Proceso cliente. v ya está inicializado. INT v; INT minimo, máximo; send values (v); receive results [i] (minimo, maximo);}

31-5-2004 36

Intercambio de datos en pares con AMP: solución simétrica

En la arquitectura simétrica o “full conected” existe un canal entre cada par de procesos. Esto da la posibilidad de que los mensajes y el procesamiento puedan ser paralelos.

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.

El resultado es que tenemos n(n-1) mensajes en el sistema. Si disponemos de una primitiva de broadcast, serán nuevamente n mensajes.


31-5-2004 37

Intercambio de datos entre pares. Solución simétrica con AMP.

Chan values(INT);Process P[i=0 to n-1] { # Todos los procesos son idénticosINT v; INT new, minimo = v, máximo=v; #estado inicial, v inicializado

FOR [k=0 to n-1 st k <> i ] #envío del dato local send values[k] (v);

FOR [k=0 to n-1 st k <> i ] { #recibo y proceso los datos remotos receive values[k] (new); IF (new < minimo) minimo = new; IF (new > maximo) maximo = new; }}


31-5-2004 38

Intercambio de datos en pares con AMP: solución con un anillo circular

Un tercer modo de organizar la solución es tener un anillo donde P[i] recibe mensajes de su predecesor y envía mensajes a su sucesor. P[n-1] tiene como sucesor a P[0]

Este esquema de solución tiene dos 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 “arrancar” el procesamiento. Se requerirán 2 (n-1) mensajes. Notar que si bien el número de mensajes es lineal (igual que en la solución centralizada) los tiempos pueden ser muy diferentes. Por qué???


31-5-2004 39

Intercambio de datos entre pares. Solución en anillo con AMP.

Chan values[n] (INT minimo, INT maximo);

Process P[0] { # Proceso que inicia los intercambios. INT v; INT minimo = v, máximo=v; #Enviar v al proceso P[1] send values[1] (minimo, maximo);

# Recibir los valores minimo y maximo globales de P[n-1] y pasarlos receive values[0] (minimo, maximo); send values[1] (minimo, maximo);}


31-5-2004 40

Intercambio de datos entre pares. Solución en anillo con AMP.

Process P[i=1 to n-1] { # Procesos del anillo. INT v; INT minimo, máximo; # Recibe los valores minimo y maximo hasta P[i-1] receive values[i] (minimo, maximo); IF (v < minimo) minimo = v; IF (v > maximo) maximo = v;# Enviar el minimo y maximo al proceso i+1 send values[i+1 MOD n] (minimo, maximo);

#Esperar el minimo y maximo global receive values[i] (minimo, maximo); IF (i < n-1) send values[i+1] (minimo, maximo);}


31-5-2004 41

Programación Distribuida. Pasaje de mensajes sincrónicos.(SMP)

La primitiva de trasmisión sync_send es bloqueante.

El trasmisor queda esperando que el mensaje sea recibido.

La cola de mensajes asociada con un send sobre un canal se reduce a 1 mensaje MENOS memoria.


31-5-2004 42

Programación Distribuida. Pasaje de mensajes sincrónicos.(SMP)

Si bien send y sync_send son similares (en algunos casos intercambiables) la semántica es diferente y las posibilidades de deadlock mayores en comunicación sincrónica.


Naturalmente el grado de concurrencia se reduce respecto de la sincronización por mensajes asincrónicos.

Como contrapartida los casos de falla y recuperación de errores son más fáciles de manejar.

31-5-2004 43

Pasaje de mensajes sincrónicos.

Chan values(INT);Process Producer { INT data[n]; FOR [i=0 to n-1] { #Hacer cálculos productor sync_send values (data[i]); }}Process Consumer { INT results[n]; FOR [i=0 to n-1] { receive values (results[i]); #Hacer cálculos consumidor }}


31-5-2004 44

Pasaje de mensajes sincrónicos.

Comentarios.Si los cálculos del productor se realizarán mucho más rápido que los del consumidor en las primeras n1 operaciones y luego se realizaran mucho más lento durante otras n1 interacciones.

Con el esquema sincrónico los pares send/receive se completaran asumiendo la demora del proceso que más tiempo consuma. Si la relación de tiempo fuera 10-1 esto significaría multiplicar por 10 los tiempos totales.

En cambio la misma solución con mensajes asincrónicos, al principio el productor es más rápido y sus mensajes se encolan. Luego el consumidor es más rápido y “descuenta” tiempo consumiendo la cola de mensajes.

--> Mayor concurrencia en AMP.


31-5-2004 45

Pasaje de mensajes sincrónicos. El tema del deadlock.

Supongamos dos procesos que intercambian valores:chan in1(INT), in2(INT);Process P1 { INT value1 = 1, value2; sync_send in2(value1); receive in1 (value2);}Process P2 { INT value1, value2=2; sync_send in1(value2); receive in2 (value1);}

Con mensajes sincrónicos esta solución entra en deadlock. Por qué??En cambio con AMP esta resolución es perfectamente posible.


31-5-2004 46

Mensajes sincrónicos: el lenguaje CSP de Hoare.

CSP (Hoare 1978) fue uno de los desarrollos fundamentales en Programación Concurrente. Muchos lenguajes reales (OCCAM, ADA, SR) se basan en CSP.

La idea básica de Hoare fue la de comunicación guardada: es decir pasaje de mensajes con waiting selectivo.

Canal: link directo entre dos procesos en lugar de mailbox global. Son half-duplex y nominados.

Sentencias de Entrada y Salida ( ? ! ) : único medio por el cual los procesos se comunican.

Efecto de la comunicación sentencia de asignación distribuida.


31-5-2004 47

El lenguaje CSP de Hoare. Primeros ejemplos.

Formas generales de sentencias de comunicación:

Destino ! port(e1, ..., en);Fuente ? port(x1, ..., xn);

Destino y Fuente nombran un proceso.

port es un canal de comunicación simple en el proceso destino o un elemento de un arreglo de ports en el proceso destino.

Los ports son usados (declarados) para distinguir entre distintas clases de mensajes que un proceso podría recibir.

Dos procesos se comunican cuando ejecutan sentencias de comunicación que hacen matching.

A! canaluno(dato); #el proceso A envia por canalunoB? canaluno(resultado); #el proceso B recibe por canaluno


31-5-2004 48


El nombre de los ports sirve para distinguir los tipos de mensajes que maneja un proceso. Si hay sólo un tipo de mensajes, port se puede omitir. Asimismo si hay un solo dato en juego, los paréntesis se pueden omitir.

Un proceso filtro que copia caracteres recibidos del proceso West al proceso East:Process Copy { CHAR c; do true West ? c; East ! c ; od }

Las operaciones de comunicación (? ! ) pueden ser guardadas, es decir hacer un AWAIT hasta que una condición sea verdadera.


31-5-2004 49


Server que calcula el Máximo Común Divisor de dos enteros con algoritmo de Euclides:GCD espera recibir entrada en su port args desde un único cliente.Envía la respuesta al port result del cliente.

Process GCD { INT Id, x, y; do true Client[*] ? args(Id, x,y); #Lo que sigue se repite hasta que x==y do x > y x := x - y;

x < y � y := y - x; od Client[Id] ! result(x); od}

Client se comunica con GCD ejecutando:... GCD ! args(v1, v2); GCD ? result(r) ...


31-5-2004 50

CSP: comunicación guardada.

Un proceso puede tener que realizar una comunicación sólo si se da una condición:IF B1; comunicación1----> S1; B2; comunicación2----> S2;FI

Asimismo en el ejemplo del COPY, si manejamos un buffer de tamaño 2, el proceso que copia puede estar recibiendo un segundo caráter de West o enviando un carácter a East.

Process Copy2 { CHAR c1, c2; West ? c1; DO West ? C2--> East ! c1 ; c1=c2; East ! c1 ; West? C1; od }


31-5-2004 51

Generalización del COPY en CSP para un buffer limitado..

Process Copy { CHAR buffer[80]; INT front = 0, rear = 0, count = 0 do count < 80; West ? buffer[rear]

count = count + 1; rear = (rear + 1)MOD 80; count > 0; East ! buffer[front] � count := count - 1; front := (front + 1) MOD 80;

od}

Notar que:۷con AMP, procesos como West e East ejecutan a su propia velocidad pues hay buffering implícito.۷con SMP, es necesario programar un proceso adicional para implementar buffering si es necesario.


31-5-2004 52

Proceso de asignación de recursos en CSP.

Process Allocator { INT avail = MaxUnits; SET units = valores iniciales; INT index, unitid; DO avail >0; client[*] ? acquire(index)---> avail = avail -1; remove (units, unitid); client[index] ! reply(unitid); client[*] ? release(index, unitid)---> avail=avail +1; insert (units, unitid); OD}

La solución sincrónica utiliza la definición de múltiples ports de CSP y resulta muy simple y clara.


31-5-2004 53

Intercambio de valores entre dos procesos en CSP.

Supongamos dos procesos que intercambian valores:Process P1 { INT value1 = 1, value2; IF P2 ! value1 ---> P2 ? value2; P2 ? value2 ---> P2 ! value1; FI}Process P2 { INT value1 , value2=2; IF P1 ! value2 ---> P1 ? value1; P1 ? value1 ---> P1 ! value2; FI}

Esta solución simétrica NO tiene deadlock porque el no determinismo en ambos procesos hace que se acoplen las comunicaciones correctamente.


31-5-2004 54

CSP: Generación de números primos: la criba de Eratóstenes.

Idea: generar todos los primos entre 2 y n

2 3 4 5 6 7 ... n

Comenzando con el primer número, 2, recorremos la lista y borramos los múltiplos de ese número. Si n es impar:

2 3 5 7 ... n

Pasamos al próximo número, 3, y borramos sus múltiplos.

Si seguimos hasta que todo número fue considerado, los que quedan son todos los primos entre 2 y n.


31-5-2004 55

La criba de Eratóstenes: solución paralela en CSP.

Process Sieve[i = 2 TO L] { INT p, next; Sieve[i-1] ? p # p es primo

DO Sieve[i-1] ? Next ---> #recibe el proximo candidato IF (next MOD p) <> 0 ---> #podría ser primo Sieve[i+1] ! Next; #entonces lo pasa FI OD}

El número total L de procesos Sieve debe ser lo suficientemente grande para garantizar que todos los primos hasta n se generan.


31-5-20041 programación distribuida los métodos de sincronización que hemos visto se basan en...

Documents