Paso por mensaje

De Departamento de Informatica
Saltar a: navegación, buscar

Contenido

Introducción

Esquema básico de comunicación entre hebras

En un entorno de memoria compartida, se requiere que los procesos que se comunican compartan una zona de la memoria y que el programador de la aplicación escriba explícitamente el código para acceder y manipular la memoria compartida. En un sistema distribuido, este modelo de memoria compartida es difícil o imposible de implementar, ya que no siempre existe memoria física compartida.


Otra forma de conseguir este efecto es que el sistema operativo proporcione los medios para que los procesos se comuniquen entre sí a través de una facilidad de paso por mensajes. Éste proporciona un mecanismo que permite a los procesos comunicarse y sincronizar sus acciones sin compartir el mismo espacio de memoria, y es muy útil en un entorno distribuido, en el que los procesos que se comunican pueden residir en distintos equipos conectados en red.

Operaciones Básicas

Un sistema de paso por mensajes debe tener al menos dos operaciones: Envío de mensaje (send) y recepción de mensajes (recieve). Los mensajes enviados por un proceso pueden tener un tamaño fijo o variable. Si tienen un tamaño fijo, la implementación a nivel del sistema es directa. De lo contrario, requieren una implementación más compleja a nivel de sistema, pero como ventaja su programación es más sencilla.

Si los procesos P y Q desean comunicarse, tienen que enviarse mensajes entre sí, por lo que se requiere un enlace de comunicación entre ellos, el cual puede ser implementado de diferentes formas. Existen varios métodos para implementar lógicamente un enlace y las operaciones de envío y recepción:

  • Comunicación sincrónica o asincrónica
  • Comunicación directa e indirecta
  • Almacenamiento en búfer explícito o automático

Existen varias situaciones que es necesario considerar al evaluar cada una de estas funcionalidades

Comunicación Directa

Simétrica

En el caso de la comunicación directa, cada proceso que desea establecer una comunicación debe nombrar al receptor o transmisor de la comunicación. En este esquema, send() y recieve() se definen de este modo:

  • send(P,mensaje): se envía un mensaje al proceso P
  • recieve(Q,mensaje): Se recibe mensaje desde el proceso Q

Este esquema de comunicación tiene las siguientes propiedades:

  • Los enlaces se establecen de forma automática entre cada par de procesos que quieran comunicarse. Los procesos sólo tienen que conocer la identidad del otro para comunicarse
  • Cada enlace se asocia con únicamente dos procesos
  • Entre cada par de procesos existe únicamente un enlace.

En este esquema puede notarse que tanto el transmisor como el receptor deben nombrar al otro para poder establecer una comunicación entre ellos. Es decir, existe simetría.

Asimétrica

En este caso, sólo el transmisor nombra al receptor, pero el receptor no nombra al transmisor. En este esquema, send() y recieve() se definirían del siguiente modo:

  • send(P,mensaje): se envía un mensaje a P
  • recieve(id,mensaje): recibe un mensaje de cualquier proceso, a la variable id se le asigna el nombre del proceso con que se ha llevado a cabo la comunicación

La desventaja de estos esquemas (simétrico y asimétrico) es la limitada modularidad de las definiciones de los procesos resultantes. Cambiar el identificador de un proceso puede requerir que se modifiquen todas las restantes definiciones de procesos. Además de que cambiar y sustituir todas las referencias al identificador antiguo con el nuevo identificador para evitar problemas.

Comunicación Indirecta

Con el modelo de comunicación indirecta, los mensajes se envían y reciben en buzones de correo o puertos. Un buzón de correo se ve de forma abstracta como un objeto en el que los procesos pueden colocar mensajes y del que pueden eliminar mensajes. Cada buzón tiene asociada una identificación única. En este esquema, cada proceso puede comunicarse con otros a través de una serie de buzones diferentes. No obstante, la comunicación entre dos procesos es posible solamente si tienen un buzón compartido. De esta forma, las primitivas send() y recieve() se definen:

  • send(A,mensaje): Se envía un mensaje al buzón A
  • recieve(A,mensaje): Se recibe un mensaje desde el buzón A

En este esquema pueden notarse las siguientes propiedades:

  • Puede establecerse un enlace entre un par de procesos únicamente si ambos tienen un buzón de correo compartido
  • Un enlace puede asociarse con más de dos procesos
  • Entre cada par de procesos puede haber una serie de enlaces diferentes, correspondiendo cada enlace a un buzón de correo.

Supongamos que los procesos P,Q y R comparten un buzón de correo A. El proceso P envía un mensaje a A, mientras que los procesos Q y R ejecutan una instrucción recieve() de A. Existen varias posibilidades de recepción del mensaje de P:

  • Permitir que cada enlace esté asociado con dos procesos máximo.
  • Permitir que sólo un proceso como máximo ejecute una operación de recepción en cada momento
  • Permitir que el sistema seleccione arbitrariamente qué proceso recibirá el mensaje (Q o R pero no ambos). El sistema también puede definir un algoritmo para definir qué proceso recibirá el mensaje.

Un buzón de correo puede ser propiedad de un proceso o del sistema operativo:

  • Si es propiedad de un proceso: el buzón forma parte del espacio de memoria del proceso, se puede diferenciar entre el propietario(el que recibe mensajes a través del buzón) y el usuario (aquél que sólo puede enviar mensajes al buzón). Puesto que cada buzón tiene un solo propietario, no puede haber confusión acerca de quién recibirá el mensaje. Cuando un proceso termina, el buzón desaparece. A cualquier proceso que envíe con posterioridad un mensaje se le debe notificar que el buzón ya no existe.
  • Si es propiedad del sistema operativo: Tiene existencia propia, es independiente y no está asociado a ningún proceso concreto. El sistema operativo debe proporcionar un mecanismo que permita a un proceso hacer lo siguiente:
    • Crear un buzón nuevo
    • Enviar y recibir mensajes de un buzón
    • Eliminar un buzón.

Por omisión, el proceso que crea un buzón de correo es su propietario. Inicialmente, el propietario es el único proceso que puede recibir mensajes a través de este buzón. Sin embargo, la propiedad y el privilegio de recepción puede ser pasado a otro proceso mediante las llamadas apropiadas al sistema.

Sincronización

Motivación: El problema del Productor-Consumidor

El problema del Productor - Consumidor es un ejemplo clásico de la sincronización entre procesos. El problema describe dos procesos (el productor y el consumidor), los cuales comparten un espacio de memoria fijo utilizado como una cola. El trabajo del Productor es generar un paquete de datos, ponerlo en la cola, y comenzar de nuevo. Por otro lado, el Consumidor debe consumir estos datos, un paquete a la vez. El problema consiste en asegurarse que el productor no intentará añadir más datos de los posibles en la cola, y, por otro lado, que el consumidor no intentará consumir datos de una cola vacía.

Sincronización entre envío y Recepción

La comunicación entre procesos tiene lugar a través de las llamadas a las primitivas send() y recieve(). Existen distintas opciones de diseño para implementar cada primitiva. El paso de mensajes puede ser con o sin bloqueo, mecanismos conocidos como síncrono y asincrónico.

  1. Envío con bloqueo: El proceso que envía se bloquea hasta que el proceso receptor o el buzón reciben el mensaje.
  2. Envío sin bloqueo: El proceso transmisor envía el mensaje y continúa operando.
  3. Recepción con bloqueo: El receptor se bloquea hasta que haya un mensaje disponible.
  4. Recepción sin bloqueo: El receptor extrae un mensaje válido o un mensaje nulo.

Son posibles diferentes combinaciones de las operaciones send() y recieve(). Cuando ambas operaciones se realizan con bloqueo, se tiene lo que se denomina un rendezvous entre el transmisor y el receptor.

La solución al problema del productor - consumidor final es trivial cuando se usan instrucciones send() y recieve() con bloqueo. El productor simplemente invoca la llamada send() con bloqueo y espera hasta que el mensaje se entrega al receptor o al buzón de correo. Por otro lado, cuando el consumidor invoca la llamada recieve(), se bloquea hasta que haya un mensaje disponible.

Problemas de llamadas con bloqueo

Sabemos que un emisor puede enviar mensajes de forma sincrónica a un receptor. Uno de los inconvenientes de las llamadas con bloqueo es la posibilidad de que el receptor puede no estar disponible por haber finalizado, y en este caso el emisor quedaría esperando infinitamente. Para solucionar este problema, se puede mejorar el mecanismo con un periodo máximo de respuesta (timeout). Esto presenta algunas ventajas:

  • Con un timeout podemos especificar cuánto tiempo estamos dispuestos a esperar que un envío tenga lugar.
  • Incluso en sistemas con cargas elevadas, las hebras deberían ser capaces de responder dentro de un cierto intervalo de tiempo.

De esta forma, el envío síncrono puede mejorarse de la siguiente forma:

  • envio_sincrono(receptor,mensaje,timeout,resultado)

Si el receptor no recibe un mensaje en un tiempo timeout, el emisor puede ser informado a través de la variable resultado de forma que pueda decidir como actuar y no quedar esperando infinitamente una respuesta.

Se observa que los conceptos de sincronía y asincronía se usan frecuentemente en los algoritmos de entrada/salida en los sistemas operativos.

Almacenamiento en Búfer

Sea la comunicación directa o indirecta, los mensajes intercambiados por los procesos que se están comunicando reside en una cola temporal. Básicamente, tales colas se pueden implementar de tres maneras distintas:

  1. Capacidad cero: La cola tiene una longitud máxima de cero, por lo tanto, no puede haber ningún mensaje esperando en el enlace. En este caso, el transmisor debe bloquearse hasta que el receptor reciba el mensaje.
  2. Capacidad limitada: La cola tiene una longitud finita n, por lo tanto, puede haber en ella n mensajes como máximo. Si la cola no está llena cuando se envía un mensaje, el mensaje se introduce en la cola (se copia o se almacena un puntero al mismo), y el transmisor puede continuar la ejecución sin esperar. Si la cola está llena, el transmisor debe bloquearse hasta que haya espacio disponible en la cola.
  3. Capacidad ilimitada: La longitud de la cola es potencialmente infinita, por lo tanto, puede existir cualquier cantidad de mensajes esperando en ella. El transmisor nunca se bloquea.

Ocasionalmente se dice que el caso de capacidad cero es un sistema de almacenamiento de mensajes sin almacenamiento en búfer; los otros casos son sistemas con almacenamiento en búfer automático.

El problema del Envío Asíncrono y Uso de Búfer

Ejemplo de desborde de búfer

Esto ocurre cuando una hebra envía repetidamente un mensaje a otra de forma asincrónica, hacia una hebra receptora sincrónica. Con esto se provoca un desborde del búfer, causando finalmente que el receptor quede finalmente fuera de alcance.

Solución

Solución del desborde reemplazando el tipo de envío

Generalmente, la solución consiste en cambiar el envío asíncrono por uno sincrónico y pasar el almacenamiento temporal (el búfer) al espacio del usuario.

Message Passing Interface

¿Qué es?

La interface de pases de mensajes MPI, por sus siglas en Inglés, (Message Passing Interface), es una biblioteca de funciones y subrutinas que pueden ser usadas en programas C, FORTRAN y C++. Con el uso de MPI en programas que modelan algún fenómeno o proceso de Ciencias e Ingeniería, se intenta explotar la existencia de múltiples procesadores a través del pase de mensajes. MPI fue desarrollado en los años 1993-1994 por un grupo de investigadores de la Industria y la comunidad académica. Hoy en día MPI es una biblioteca estándar en la programación paralela basada en el pase de mensajes.

Características de MPI:

  1. Estandarización.
  2. Portabilidad: multiprocesadores, multicomputadores, redes, heterogéneos, ...
  3. Buenas prestaciones.
  4. Amplia funcionalidad.
  5. Existencia de implementaciones libres (mpich, LAM-MPI, ...)
  6. La especificación detalla las funciones que se pueden utilizar, no el modo como se compilan y lanzan-ejecutan los programas, lo cual puede variar de una implementación a otra.

Características básicas de la programación con MPI

Siguiendo el modelo SPMD, el usuario escribirá su aplicación como un proceso secuencial del que se lanzarán varias instancias que cooperan entre sí. Los procesos invocan diferentes funciones MPI que permiten:

  1. Iniciar, gestionar y finalizar procesos MPI.
  2. Comunicar datos entre dos procesos.
  3. Realizar operaciones de comunicación entre grupos de procesos.
  4. Crear tipos arbitrarios de datos.

Funciones básicas de MPI

Cualquier programa paralelo con MPI puede implementarse con tan sólo 6 funciones, aunque hay muchas más funciones para aspectos avanzados. Todas ellas empiezan por MPI_ y obligan a que los programas MPI tengan #include "mpi.h".

  • Los programas MPI deben ser obligatoriamente inicializados y finalizados en MPI (MPI_Init, MPI_Finalize).
  • Los procesos en ejecución pueden saber cuántos procesos MPI forman parte de un grupo de procesos -communicator en la terminología MPI- (MPI_Comm_size) y qué número de orden -empezando por 0- tiene en ese grupo de procesos (MPI_Comm_rank).
  • Los mensajes punto a punto deben ser enviados explícitamente por el emisor y recibidos explícitamente por el receptor (más adelante se explicarán las operaciones de comunicación colectivas), para lo cual pueden emplearse dos funciones básicas (MPI_Send y MPI_Recv).

Aquí algunos ejemplos:

  1. MPI_Init: Inicia una sesión MPI.
  2. MPI_Comm_size: total proc. del comunicador.
  3. MPI_Comm_rank: id del proceso actual.
  4. MPI_Finalize: Termina una sesión MPI.
  5. MPI_Send: Envía un mensaje (bloqueante).
  6. MPI_Receive: Recibe un mensaje (bloqueante) .
  7. MPI_Receive: Recibe un mensaje (bloqueante) (Comunicación asíncrona).
  8. MPI_Isend: Envía un mensaje (no bloqueante).
  9. MPI_Irecv: Recibe un mensaje (no bloqueante).
  10. MPI_Test: Verifica si se ha realizado la operación.
  11. MPI_Wait: Bloquea hasta operación completada.
  12. MPI_Bcast: Envío a procesos de un comunicador.

Ejemplos de MPI

Ejemplo Básico: (en C)

   #include <iostream.h> 
   #include <mpi.h> 
   int main(int argc, char **argv) { 
  
   MPI_Init(&argc,&argv); 
   cout << “Hola Mundo” << endl; 
   MPI_Finalize(); 
   }

• mpi.h. Nos provee de las declaraciones de funciones para todas las funciones de MPI.

• Tenemos un comienzo y un final. El comienzo está en la forma de una llamada a MPI_Init(), lo cual le indica al sistema operativo que este es un programa MPI y permite al sistema operativo a realizar cualquier inicialización necesaria. El final está en la forma de una llamada a MPI_Finalize(), lo cual le indica al sistema operativo que el ambiente de programación MPI ha culminado.

Cuando se ejecuta un programa con MPI, todos los procesos usan el mismo objeto compilado, y por lo tanto, todos los procesos están ejecutando exactamente el mismo código. Nos surge la siguiente pregunta: Qué es lo que en MPI distingue un programa paralelo ejecutandose en P procesadores de la versión serial del código ejecutandose en P procesadores? Dos cosas distinguen el programa paralelo:

  1. Cada proceso usa su identificador de proceso para determinar que parte de las instrucciones del algoritmo le corresponden.
  2. Los procesos se comunican uno con el otro para llevar a cabo la tarea final.

Aunque cada proceso recibe una copia idéntica de las instrucciones a ser ejecutadas, ésto no implica que todos los procesos ejecutarían las mismas instrucciones. Debido a que cada proceso es capaz de obtener su identificador de proceso (usando MPI_Comm_rank), éste puede determinar que parte del código le es suministrado para ejecutar. Esto es llevado a cabo a trávez del uso de la sentencia if. La sección del código que va a ser ejecutado por un proceso particular debe estar encerrado dentro de una sentencia if, lo cual verifica el número de identificación del proceso. Si el código no está situado entre sentencias if específicas a un identificador particular, entonces el código sería ejecutado por todos los procesos (como en el caso del código mostrado anteriormente).


Ejemplo: Anillo de procesos (C)

En este ejemplo se crea un anillo de n procesos y m mensajes.Cada mensaje i itinera entre los procesos (comenzando en el proceso 0 hasta el proceso n), hasta que llega nuevamente al proceso 0, donde se descarta y se envía el mensaje i-1. Este anillo canónico se detiene cuando el mensaje 0 llega al proceso 0.


/*
 * Open Systems Laboratory
 * http://www.lam-mpi.org/tutorials/
 * Indiana University
 *
 * MPI Tutorial
 * Lab 2: The cannonical ring program
 *
 * Mail questions regarding tutorial material to lam at lam dash mpi dot org
 */
 
#include <stdio.h>
#include <mpi.h>
 
int main(int argc, char *argv[]){
  MPI_Status status;
  int num, rank, size, tag, next, from;
 
  /* Start up MPI */
 
  MPI_Init(&argc, &argv);
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  MPI_Comm_size(MPI_COMM_WORLD, &size);
 
  /* Arbitrarily choose 201 to be our tag.  Calculate the rank of the
     next process in the ring.  Use the modulus operator so that the
     last process "wraps around" to rank zero. */
 
  tag = 201;
  next = (rank + 1) % size;
  from = (rank + size - 1) % size;
 
  /* If we are the "console" process, get a integer from the user to
     specify how many times we want to go around the ring */
 
  if (rank == 0) {
    printf("Enter the number of times around the ring: ");
    scanf("%d", &num);
 
    printf("Process %d sending %d to %d\n", rank, num, next);
    MPI_Send(&num, 1, MPI_INT, next, tag, MPI_COMM_WORLD); 
  }
 
  /* Pass the message around the ring.  The exit mechanism works as
     follows: the message (a positive integer) is passed around the
     ring.  Each time is passes rank 0, it is decremented.  When each
     processes receives the 0 message, it passes it on to the next
     process and then quits.  By passing the 0 first, every process
     gets the 0 message and can quit normally. */

  do {

    MPI_Recv(&num, 1, MPI_INT, from, tag, MPI_COMM_WORLD, &status);
    printf("Process %d received %d\n", rank, num);
 
    if (rank == 0) {
      --num;
      printf("Process 0 decremented num\n");
    }
 
    printf("Process %d sending %d to %d\n", rank, num, next);
    MPI_Send(&num, 1, MPI_INT, next, tag, MPI_COMM_WORLD);
  } while (num > 0);
  printf("Process %d exiting\n", rank);

  /* The last process does one extra send to process 0, which needs to
     be received before the program can exit */
 
  if (rank == 0)
    MPI_Recv(&num, 1, MPI_INT, from, tag, MPI_COMM_WORLD, &status);
 
  /* Quit */
 
  MPI_Finalize();
  return 0;
}

Referencias

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas