proyectos de investigación i y ii - 148.206.53.84148.206.53.84/tesiuami/uami10920.pdf · asesor:...

Universidad Autónoma Metropolitana Iztapalapa

Proyecto de Investigación I y II

“Migración de datos entre nodos de un cluster”

Ciencias Básicas e Ingeniería

Licenciatura en Computación Autores:

Fernando Fernández Vergara José Bernardo Hipatl Santiago

Asesor: Dra. Graciela Román Alonso

Este proyecto fue desarrollado en el marco del Proyecto CONACyT 342330-A Infraestructura para la construcción de aplicaciones fuertemente distribuidas.

Duración del proyecto: 2 trimestres

TRIMESTRE DE TERMINACIÓN: 03P

2

Agradecimientos Agradecemos infinitamente a nuestros padres que nos hayan apoyado incondicionalmente a lo largo de nuestra carrera, dándonos palabras de aliento en momentos difíciles y que han hecho grandes sacrificios por que nosotros cumplamos nuestras metas. Agradecemos también a nuestros profesores que nos han transmitido su conocimiento adquirido a lo largo no sólo de su carrera sino de experiencias personales. También damos las gracias a nuestro asesor la Dra. Graciela Román Alonso por habernos tenido paciencia.

Agradecemos a los Laboratorios de Docencia y Laboratorio de Súper cómputo a cargo del Ing. Juan Carlos Rosas Cabrera, por el apoyo proporcionado al facilitar los recursos necesarios para el desarrollo de gran parte de este proyecto. Así como al laboratorio de Sistemas Distribuidos del área de Computación de Sistemas de la UAM-I por facilitar sus recursos en el desarrollo de este proyecto.

3

Tipografía En este documento el código del lenguaje C y de las rutinas de MPI utilizadas en código en C, se representan en color azul. El uso de las negritas es utilizado en comandos y/o opciones de comandos en el sistema operativo, así como en los prototipos de las rutinas de MPI extraídos de los archivos de inclusión. Se incluyen algunos mensajes de error generados por el sistema en la línea de comandos, en color rojo, las letras cursivas sólo son usadas para hacer referencia a términos ya definidos o tratados en temas anteriores.

4

TABLA DE CONTENIDOS 1. INTRODUCCION .................................................................................................................................7

1.1. Objetivo ...........................................................................................................................................7 1.2. Justificación ....................................................................................................................................7

2. CONCEPTOS BÁSICOS ......................................................................................................................9 2.1. Clasificación de las arquitecturas de computadoras .......................................................................9

2.1.1. SISD (Single Instruction Single Data).....................................................................................9 2.1.2. SIMD (Single Instruction Multiple Data) ................................................................................9 2.1.3. MIMD (Multiple Instruction Multiple Data) ...........................................................................9

2.2. Clusters..........................................................................................................................................12 2.2.1. Definiciones básicas...............................................................................................................12 2.2.2. Funcionamiento de un Cluster ...............................................................................................13 2.2.3. Tipos de Clusters....................................................................................................................13 2.2.4. Características importantes de los Clusters............................................................................14 2.2.5. Middleware ............................................................................................................................14

2.3. Programación con MPI (Message Passing Interface) ...................................................................16 2.3.1. Introducción a MPI ................................................................................................................16 2.3.2. Características ........................................................................................................................16 2.3.3. Elementos Básicos de la Programación de MPI ....................................................................18 2.3.4. Compilación de programas MPI ............................................................................................27 2.3.5. Ejecución de Programas MPI.................................................................................................29

2.4. Balance de Carga ..........................................................................................................................31 3. MIGRACIÓN DE DATOS..................................................................................................................34

3.1. Definición e Implementación de un TDA lista balanceable ........................................................35 3.1.1. Implementación......................................................................................................................36

3.2. Envío/Recepción de un nodo de un TDA lista..............................................................................38 3.2.1. Envío/Recepción del nodo Campo por Campo (Versión 1 “camxcam.c”)...........................39 3.2.2. Envío/Recepción nodo empaquetado (Versión 2.1 “empaketado.c”)....................................41 3.2.3. Envío/Recepción TDA empaquetado (Versión 2.2 “empaketado_b.c”) ...............................44 3.2.4. Envío/Recepción de un nodo usando uniones (Versión 3.1 “uniones.c”) .............................47 3.2.5. Envío/Recepción de un nodo usando uniones (Versión 3.2 “uniones_b.c”) .........................49

4. RECONOCIMIENTO DEL TDA LISTA BALANCEABLE.............................................................53 4.1 Algoritmo .......................................................................................................................................54 4.2. Implementación.............................................................................................................................55

4.2.1. Obtención de los bloques .......................................................................................................55 4.2.2. Verificación de los bloques....................................................................................................55 4.2.3. Registro de la Estructura ........................................................................................................56 4.2.4. Creación del archivo de Salida...............................................................................................56

5. MIGRACIÓN DE DATOS COMPARTIDOS POR HILOS...............................................................58 5.1. Uso de Hilos en MPI .....................................................................................................................58

5.1.1. hilos_1.c .................................................................................................................................59 5.1.2. hilos_2.c .................................................................................................................................61

5.2. Sincronización para la lista balanceable .......................................................................................63 5.2.1. hilos_3.c .................................................................................................................................64 5.2.2. hilo_3.c 2ª versión..................................................................................................................70

5

5.3. Rutinas para el balance de carga (versión final) ...........................................................................75 6. RESULTADOS....................................................................................................................................77

6.1. Desempeño del programa hilos_3.c 1ª versión.............................................................................77 6.2. Desempeño del programa hilos_3.c 2ª versión.............................................................................77

7. CONCLUSIONES Y PERSPECTIVAS..............................................................................................79 8. BIBLIOGRAFIA .................................................................................................................................82 9. ANEXOS .............................................................................................................................................84

9.1. Anexo A (Codigos Fuentes para la migración de datos) ..............................................................84 Listado “protos.h” ............................................................................................................................84 Listado “operlis.c” ...........................................................................................................................85 Listado “ent_sal.c” ...........................................................................................................................87 Listado “val_azar.c”.........................................................................................................................88 Listado “camxcamp.c” .....................................................................................................................89 Listado “empaketado.c” ...................................................................................................................91 Listado “empaketado_b.c” ...............................................................................................................94 Listado “uniones.c” ..........................................................................................................................98 Listado “uniones_b.c” ....................................................................................................................100

9.2. Anexo B (Códigos Fuentes para el Reconocimiento del TDA Lista).........................................103 Listado “scan.c” .............................................................................................................................103

9.3. Anexo C (Códigos Fuentes para Migración de datos compartidos con hilos)............................112 Listado “hilos_1.c”........................................................................................................................112 Listado “hilos_2.c”.........................................................................................................................115 Listados “Primera versión” ............................................................................................................119 Listado “protos.h” ..........................................................................................................................120 Listado “def_TDA.h”.....................................................................................................................122 Listado “balance.c” ........................................................................................................................122 Listado “hilos_3.c”.........................................................................................................................125 Listado “operlis.c” .........................................................................................................................129 Listado “ent_sal.c” .........................................................................................................................131 Listados “Segunda Versión” ..........................................................................................................132 Listado “protos.h” ..........................................................................................................................132 Listado “def_TDA.h”.....................................................................................................................132 Listado “balance.c” ........................................................................................................................132 Listado “Hilos_3.c”........................................................................................................................134 Listado “operlis.c” .........................................................................................................................135 Listado “ent_sal.c” .........................................................................................................................135 Listado “MPI_lista.c”.....................................................................................................................135 Listado “scan.c” .............................................................................................................................137

9.4. Anexo D (Códigos Fuentes Versión final)..................................................................................147 Listado “protos.h” ..........................................................................................................................147 Listado “MPI_lista.orig” ................................................................................................................148 Listado “balance.c” ........................................................................................................................149 Listado “scan.c” .............................................................................................................................152

9.4. Anexo E.......................................................................................................................................162 Manual de usuario “Rutinas de Balance” ......................................................................................162

9.5. Anexo F.......................................................................................................................................165 Manual de usuario programa “scan” ..............................................................................................165

6

1. INTRODUCCIÓN

7

1. INTRODUCCIÓN

1.1. Objetivo

Realizar un trabajo de investigación en el área de sistemas distribuidos, con el fin de dar una propuesta de un mecanismo de balance de datos haciendo uso de la herramienta MPI.

1.2. Justificación

En la actualidad los grandes volúmenes de información en formato digital, así como los pesados cálculos para la investigación científica que llevan a cabo las universidades y empresas en nuestro país, han obligado a éstas a buscar herramientas que hagan más rápidas y por tanto eficientes sus investigaciones. Una alternativa es el uso de las supercomputadoras, el cual representa un problema, ya que el costo de las mismas es muy elevado, costo que muchas instituciones no pueden solventar. Pero, no es la única opción, ni mucho menos la mejor, por lo menos en el aspecto económico.

Otra alternativa lo son los cluster, que en muchos aspectos y en gran medida son la mejor opción para la investigación que se desarrolla en las universidades como la nuestra. Pero esta opción, también tiene sus desventajas, entre las más importantes se encuentra la necesidad de personal calificado para lograr un buen desempeño en la paralelización de aplicaciones, personal que es capacitado casi en su totalidad por instituciones educativas como la nuestra.

Pero el buen desempeño de una aplicación paralela no depende sólo de una buena codificación, además esta en gran medida en función de una buena administración del cluster, para que le mismo rinda al máximo. El principal problema de un cluster en una institución como la nuestra es que no sólo es utilizado para el procesamiento de una aplicación paralela, lo cual sería absurdo, ya que el cluster no sería aprovechado a su máximo, también se da el caso que hay clusters que también son usados para el desempeño de las actividades docentes. Es aquí cuando surgen nuevos problemas, ya que el buen desempeño de las aplicaciones paralelas, depende en gran medida de la carga de trabajo de los nodos del cluster.

Existen herramientas que auxilian en la administración de un cluster, y entre las tareas que desempeñan están, la detección de nodos con una gran carga de trabajo, para que los procesos sean lanzados en los nodos con menor carga. Pero, ¿qué pasa si se lanza una aplicación en un nodo que inicialmente no se encuentra cargado, pero que posteriormente se carga, ya sea por el uso del nodo como estación de trabajo o por la gran cantidad de datos de nuestra misma aplicación? Pues la respuesta es obvia, nuestro proceso paralelo se verá afectado por la sobrecarga. Por otra parte nosotros al codificar una aplicación paralela, si pensamos en prever la situación anterior, nos haremos complicada nuestra tarea de paralelización más de lo que ya es. Ya que no sólo habría que codificar rutinas para censar la carga del nodo, sino además la forma de migrar nuestros datos para que el procesamiento llevado hasta el momento no sea en vano. Por tanto el objetivo de este proyecto es contribuir al desarrollo de las rutinas encargadas del balance de la carga de datos para nuestras aplicaciones paralelas.

8

2. Conceptos Básicos

9

2. CONCEPTOS BÁSICOS

2.1. Clasificación de las arquitecturas de computadoras [2] La clasificación de las arquitecturas de computadoras fue propuesta por Michael Flynn y se basa en basa en el número de instrucciones y de la secuencia de datos que la computadora utiliza para procesar información. Puede haber secuencias de instrucciones sencillas o múltiples y secuencias de datos sencillas o múltiples. Esto da lugar a 4 tipos de computadoras, de las cuales solamente dos son aplicables a las computadoras paralelas.

2.1.1. SISD (Single Instruction Single Data) Este es el modelo tradicional de computación secuencial donde una unidad de procesamiento recibe una sola secuencia de instrucciones que operan en una secuencia de datos.

Por ejemplo para procesar la suma de N números a1, a2,... aN, el procesador necesita acceder a memoria N veces consecutivas (para recibir un número) También son ejecutadas en secuencia N-1 adiciones. Es decir los algoritmos para las computadoras SISD no contienen ningún paralelismo, éstas están constituidas de un procesador.

2.1.2. SIMD (Single Instruction Multiple Data) A diferencia de SISD, en este caso se tienen múltiples procesadores que sincronizadamente ejecutan la misma secuencia de instrucciones, pero en diferentes datos. El tipo de memoria que estos sistemas utilizan es distribuida.

Aquí hay N secuencias de datos, una por procesador, así que diferentes datos pueden ser utilizados en cada procesador. Los procesadores operan sincronizadamente y un reloj global se utiliza para asegurar esta operación. Es decir, en cada paso todos lo procesadores ejecutan la misma instrucción, cada uno en diferente dato.

2.1.3. MIMD (Multiple Instruction Multiple Data) Este tipo de computadora es paralela al igual que las SIMD, la diferencia con estos sistemas es que MIMD es asíncrono. No tiene un reloj central. Cada procesador en un sistema MIMD puede ejecutar su propia secuencia de instrucciones y tener sus propios datos. Esta

10

característica es la más general y poderosa de esta clasificación. Se tienen N procesadores, N secuencias de instrucciones y N secuencias de datos. Si el sistema de multiprocesamiento posee procesadores de aproximadamente igual capacidad, estamos en presencia de multiprocesamiento simétrico, en el otro caso hablamos de multiprocesamiento asimétrico. Cada procesador opera bajo el control de una secuencia de instrucciones, ejecutada por su propia unidad de control, es decir cada procesador es capaz de ejecutar su propio programa con diferentes datos. Esto significa que los procesadores operan asincrónicamente, o en términos simples, pueden estar haciendo diferentes cosas en diferentes datos al mismo tiempo.

Los sistemas MIMD se clasifican en: • Sistemas de Memoria Compartida. • Sistemas de Memoria Distribuida. • Sistemas de Memoria Compartida Distribuida

En este tipo de sistemas cada procesador tiene acceso a toda la memoria, es decir hay un espacio de direccionamiento compartido. Se tienen tiempos de acceso a memoria uniformes ya que todos los procesadores se encuentran igualmente comunicados con la memoria principal y las lecturas y escrituras de todos los procesadores tienen exactamente las mismas latencias; Y además el acceso a memoria es por medio de un conducto común. En esta configuración, debe asegurarse que los procesadores no tengan acceso simultáneamente a regiones de memoria de una manera en la que pueda ocurrir algún error. Desventajas: • El acceso simultáneo a memoria es un problema. • En PC’s y estaciones de trabajo:

Todos los CPU’s comparten el camino a memoria. Un CPU que acceda la memoria, bloquea el acceso de todos los otros CPU’s.

• En computadoras vectoriales como Crays, etc. Todos los CPU’s tienen un camino libre a la memoria. No hay interferencia entre CPU’s.

• La razón principal por el alto precio de Cray es la memoria.

Ventaja: La facilidad de la programación. Es mucho más fácil programar en estos sistemas que en

sistemas de memoria distribuida.

Sistemas de Memoria Distribuida Estos sistemas tienen su propia memoria local. Los procesadores pueden compartir información solamente enviando mensajes, es decir, si un procesador requiere los datos contenidos en la memoria de otro procesador, deberá enviar un mensaje solicitándolos. Esta comunicación se le conoce como Paso de Mensajes. Ventajas:

La escalabilidad. Las computadoras con sistemas de memoria distribuida son fáciles de escalar, mientras que la demanda de los recursos crece, se puede agregar más memoria y procesadores. Desventajas:

11

• El acceso remoto a memoria es lento. • La programación puede ser complicada.

Las computadoras MIMD de memoria distribuida son conocidas como sistemas de procesamiento

en paralelo masivo (MPP) donde múltiples procesadores trabajan en diferentes partes de un programa, usando su propio sistema operativo y memoria. Además se les llama multicomputadoras, máquinas libremente juntas o cluster.

Sistemas de Memoria Compartida Distribuida Es un cluster o una partición de procesadores que tienen acceso a una memoria compartida común pero sin un canal compartido. Esto es, físicamente cada procesador posee su memoria local y se interconecta con otros procesadores por medio de un dispositivo de alta velocidad, y todos ven las memorias de cada uno como un espacio de direcciones globales.

El acceso a la memoria de diferentes clusters se realiza bajo el esquema de Acceso a Memoria No Uniforme (NUMA), la cual toma menos tiempo en acceder a la memoria local de un procesador que acceder a memoria remota de otro procesador. Ventajas:

• Presenta escalabilidad como en los sistemas de memoria distribuida. • Es fácil de programar como en los sistemas de memoria compartida. • No existe el cuello de botella que se puede dar en máquinas de sólo memoria compartida.

La arquitectura que nos interesa es la MIMD con memoria distribuida, en la cual se encuentran

clasificados los clusters, en el siguiente apartado da una breve descripción de lo que es un cluster.

12

2.2. Clusters

[5] El término cluster es usado generalmente para referirnos a un grupo de componentes distribuidos que colaboran en conjunto para presentarse al usuario como un solo sistema.

Un Cluster es un conjunto o conglomerado de computadoras interconectadas entre sí de alguna manera, que trabajan en conjunto, distribuyéndose las tareas entre ellas, logrando que el usuario lo vea como una sola, simulando una sola computadora muy potente. Son construidos utilizando componentes de hardware comunes, lo que los hace un poco más accesibles y con el software que en su mayoría se apega a la licencia GNU. El principal papel que juegan es el de proporcionar soluciones a la investigación científica, que requieren mucho tiempo de procesamiento y de cálculos pesados, aunque también son usados en las ingenierías y en las aplicaciones comerciales.

2.2.1. Definiciones básicas Rendimiento: Es la efectividad del desempeño de una computadora, sobre una aplicación o un

benchmark en particular. Flops: Es una medida de la velocidad del procesamiento numérico del procesador. Son

operaciones de punto flotante por segundo. Alto Rendimiento (HPC): Gran demanda de procesamiento de datos en procesadores, memoria

y otros recursos de hardware, donde la comunicación entre ellos es muy rápida. Latencia: Tiempo de transferencia de mensajes de una interfaz a otra. Ancho de Banda: Capacidad de transferencia que tiene un canal de comunicaciones en una

unidad de tiempo.

13

Switches: Es un conjunto de puertos de entrada, un conjunto de puertos de salida y una red cruzada interna (crossbar) que conecta cada entrada a cada salida, el buffering interno, y el control lógico para efectuar la conexión de entrada y salida en cada punto de tiempo (malla)

Hub: es un conjunto de puertos de entrada y salida multiplexado (un alambre) Ethernet: Protocolo de comunicación basado en el estándar IEEE. VIA: Protocolo de comunicación con características de baja latencia.

2.2.2. Funcionamiento de un Cluster En su parte central, la tecnología de Clusters consta de dos partes. La primera componente,

consta de un sistema operativo confeccionado especialmente para esta tarea, un conjunto de compiladores y aplicaciones especiales, que permiten que los programas que se ejecutan sobre esta plataforma tomen las ventajas de esta tecnología de Clusters.

La segunda componente es la interconexión de hardware entre las máquinas (nodos) del Cluster. Se han desarrollado interfaces de interconexión especiales muy eficientes, pero comúnmente las interconexiones se realizan mediante una red Ethernet dedicada de alta velocidad. Es mediante esta interfaz que los nodos del Cluster intercambian entre sí asignación de tareas, actualizaciones de estado y datos del programa. Existe otra interfaz de red que conecta al Cluster con el mundo exterior. Un nodo esencialmente se compone de:

• Procesador. • Memoria. • Dispositivos de almacenamiento. • Tarjeta de Red.

2.2.3. Tipos de Clusters [5] Beowulf Concepto de los primeros clusters

(componentes COTS, filosofía “Hágalo usted mismo”). En 1994, se integró el primer cluster de PC’s en el Centro de Vuelos Espaciales Goddard de la NASA, para resolver problemas computacionales que aparecen en las ciencias de la Tierra y el Espacio. Los pioneros de este proyecto fueron Thomas Sterling, Donald Becker y otros científicos de la NASA. El cluster de PC’s desarrollado tuvo una eficiencia de 70 megaflops (millones de operaciones de punto flotante por segundo). Los investigadores de la NASA le dieron el nombre de Beowulf a este cluster, en honor del héroe de las leyendas medievales, quien derrotó al monstruo gigante Grendel. Nombre de un héroe de la mitología danesa relatado en el libro La Era de las Fábulas, del autor norteamericano Thomas Bulfinch (1796-1867).

Clusters de Alto Rendimiento (HPC) Dedicados a tareas que requieran de muchos recursos (CPU, memoria, comunicaciones). La tecnología de Clusters de Alto Rendimiento para Linux más conocida es la tecnología Beowulf. Esta tecnología puede proporcionar potencial de cómputo del tipo de una supercomputadora utilizando computadoras personales sencillas. Al conectar estas entre sí mediante una red Ethernet de alta velocidad, las computadoras personales se combinan para lograr la potencia de una supercomputadora.

Clusters de Alta Disponibilidad Garantizan que un determinado recurso este disponible por mayor tiempo posible. Por ejemplo, los servicios de TCP/IP (Web, Telnet, etc.) pueden estar

14

asegurados por medio del Sist. Operativo. La alta disponibilidad en tareas de cómputo en general tiene que estar proporcionada por el mismo programa. Los servidores de un Cluster de Alta Disponibilidad normalmente su función es la de esperar listos para entrar inmediatamente en funcionamiento en el caso de que falle algún otro servidor.

Clusters Homogéneos Son aquellos en los cuales la tecnología es la misma (PC’s, SCSI, etc.).

Clusters Heterogéneos Aquellos en los que la tecnología puede ser diferente o hasta pueden usarse diferentes plataformas

Clusters Dedicados Son maquinas que se usan específicamente como un cluster. En la fotografía se muestra un cluster dedicado con 20 nodos, cada nodo cuenta con dos procesadores Intel Pentium III a 1 GHz y 1 GB en RAM, una interfaz de red para la administración del sistema Ethernet 10/100 Mb y otra para las aplicaciones paralelas Giganet a 1Gb. Este se encuentra en el “Laboratorio de Súper cómputo y visualización paralela” de la UAM-Iztapalapa.

Clusters No Dedicados Trabajan como un cluster solo una parte del tiempo.

2.2.4. Características importantes de los Clusters • Uso de Hardware convencional.

PC’s Servidores.

• Memoria Distribuida. Cada procesador tiene acceso sólo a la memoria local, se necesitan usar bibliotecas del tipo (DSM-Dynamic Shared Memory).

• Uso de software abierto. En el 95% de Clusters al momento, se usa Linux como sistema operativo. Solo el 0.01% de Clusters hace uso de Windows.

2.2.5. Middleware Es aquel modulo que interactúa como conductor entre sistemas permitiendo a cualquier usuario de sistemas de información comunicarse con varias fuentes de información que se encuentran interconectadas a través de una red.

Interfases más usadas: • MPI (Message Passing Interface) Interfaz mas usada para paso de mensajes, existen varias

implementaciones: MPICH, LAM-MPI, VAMPIR. Entre las ventajas que tiene esta interfaz se encuentran: distintos modos de comunicación, la sincronización de procesos, el traslape de procesos de computo con procesos de comunicación, entre otras.

• PVM (Parallel Virtual Machine) Desarrollada para NOW, totalmente libre, capaz de trabajar en redes homogéneas y heterogéneas, realiza un manejo transparente del ruteo de los mensajes, conversión da datos, calendarización de tareas a través de una red de arquitecturas incompatibles.

• DSM (Memoria Compartida Distribuida): Es un modelo que hace que la memoria distribuida de todos los nodos aparezca como memoria compartida desde el punto de vista de programador.

15

2.3. Programación Paralela [S2001] Para paralelizar una aplicación es necesario contar con un lenguaje o una biblioteca que brinde las bibliotecas necesarias para esto. Dependiendo de la herramienta con que se cuente, se particionará el código en piezas para que se ejecute en paralelo en varios procesadores. Es aquí donde entra el termino granularidad. Granularidad es el tamaño de las piezas en que se divide una aplicación. Dichas piezas pueden ser una sentencia de código, una función o un proceso en si que se ejecutara en paralelo. Granularidad es categorizada en paralelismo de grano fino y paralelismo de grano grueso. De grano fino es cuando el código se divide en una gran cantidad de piezas pequeñas. Es a nivel de sentencia donde un ciclo se divide en varios subciclos que se ejecutaran en paralelo. Se le conoce además como paralelismo de datos. De grano grueso es a nivel de subrutinas o segmentos de código, donde las piezas son pocas y de cómputo más intensivo que las de grano fino. Se le conoce como paralelismo de tareas. En el paralelismo de grano grueso en el nivel más alto se presenta cuando en la aplicación se detectan tareas independientes y estas se ejecutan en procesos independientes en, más de un procesador. En los modelos de memoria distribuida (paso de mensajes) sólo se implementa paralelismo de grano grueso. Un programador puede desarrollar aplicaciones paralelas con código fuente en C, C++ y FORTRAN, mediante el uso de paradigmas o modelos provistos por los Sistemas Operativos como lo es en los sistemas tipo Unix. Con la clonación de procesos o creación de hilos, o usando directivas a nivel sentencia, las cuales, también son provistas por los Sistemas Operativos, pero cuando se cuenta con un paralelismo real, es decir, a nivel de Hardware. Además del paso de mensajes, el cual es usado para sistemas de memoria distribuida en donde cada procesador tiene su propia memoria. Este modelo es apropiado para la comunicación y sincronización entre los procesos que se ejecutan de manera independiente (con su propio espacio de direcciones) en diferentes computadoras. La programación usando el modelo de paso de mensajes consiste en enlazar y hacer llamadas dentro del programa, a unas bibliotecas que manejarán el intercambio de datos entre los procesadores. Existen principalmente dos bibliotecas para la programación bajo este esquema:

• MPI (Message Passing Interface). • PVM (Parallel Virtual Machine).

El esquema de implementación de paralelismo mediante el paso de mensajes es a nivel de grano grueso dada la generación de procesos o tareas independientes que se ejecutan en varios procesadores. En MPI y PVM, uno de los esquemas que se emplean en la comunicación y generación de los procesos es el modelo Maestro-Esclavo. Un proceso maestro divide u distribuye el trabajo en subtareas, que las asigna a cada nodo conocido como “esclavo”. Terminando cada “esclavo” su parte, envían los resultados al “maestro” para que este recopile la información y la presente. Otro esquema utilizado en este modelo es el de “todos esclavos” que consiste en que todos los procesos no son generados por un “maestro” y se ejecutan independientemente sin notificar a un proceso maestro sus resultados.

16

2.3. Programación con MPI (Message Passing Interface)

2.3.1. Introducción a MPI [3] MPI es un estándar para el paradigma de programación de paso de mensajes. En este paradigma el programador se imagina varios procesadores, cada uno con su propio espacio de memoria, y escribe un programa para correr en cada procesador. Pero esto no es programación en paralelo, no mientras que dichos procesos no intercambien información, es decir, no tengan una coparticipación. Por lo que debe de haber una coparticipación entre los procesadores para el intercambio de información, y la forma en que ocurra este intercambio es mediante los mensajes. Así el punto principal del paradigma de paso de mensajes es el que los procesos se comuniquen mediante el envió y recepción de mensajes. De esta forma en el paso de mensajes no hay una concepción sobre memoria compartida o procesos que acceden la memoria de otros procesadores. Por lo que no hay preocuparse por la consistencia de los datos, es decir, que no se escriba un dato mientras se esta leyendo por otro proceso, el cual puede llevar a resultados no deseados. El hecho de que para cada procesador se tenga un proceso corriendo, el cual tiene interacción con otros procesos corriendo en procesadores distintos, no quiere decir que el programador tenga que escribir una serie de programas secuénciales que sean capaces de comunicarse entre sí, sino que el programador sea capaz de crear código, que dependiendo sobre que y/o cuantos procesadores se encuentre corriendo, el proceso aplique el mismo funcionamiento a cada parte de los datos que le corresponda, para que posteriormente los resultados individuales de cada procesador sean unificados y evaluados en un solo proceso para llegar al fin deseado. Así que lo que hace un típico programa paralelo es “dividir el problema en problemas chiquitos y después reunir los resultados parciales y obtener un resultado final”. Es así como con MPI se crea paralelismo de grano grueso ya que esta herramienta provee funciones que determinan que fragmento de código serán ejecutados por cada procesador. MPI no provee paralelismo de datos, sino paralelismo de tareas.

2.3.2. Características [3] MPI es un estándar para la comunicación inter-proceso en un esquema de multiprocesador

de memoria-distribuida. El estándar ha sido desarrollado por un comité de proveedores, laboratorios del gobierno y universidades. La implementación del estándar es usualmente dejada para los diseñadores de sistemas en el cual MPI corre, pero una implementación de dominio público está disponible en http://www-unix.mcs.anl.gov/mpi/. MPI es un conjunto de rutinas de librería para C/C++ y FORTRAN. Además MPI es un conjunto de rutinas de biblioteca para C/C++ y FORTRAN.

Cuando un programa bajo MPI comienza, el programa se descompone en un número de procesos especificados por el usuario. Cada proceso corre y se comunica con otras instancias del programa, posiblemente corriendo en el mismo procesador o en diferentes. La comunicación básica consiste en enviar y recibir datos de un proceso a otro. Esta comunicación toma lugar en una red de trabajo muy rápida, que conecta a los procesadores en un sistema de memoria-distribuida.

17

Un paquete de datos enviados con MPI requiere bastantes piezas de información: el proceso de envío, el proceso de recepción, la dirección de comienzo en memoria a ser enviados, el número de datos que han sido enviados, un identificador de mensajes, y el grupo de todos los procesos que puede recibir el mensaje. Todos estos objetos están disponibles para ser enviados por el programador.

En uno de los programas más simples en MPI, un proceso maestro despacha trabajo a los procesos esclavos. Esos procesos reciben los datos, realizan tareas en ellos, y envían los resultados al proceso maestro, el que combinará los resultados. Los otros procesos corren continuamente desde el comienzo del programa. Las características de MPI son:

§ Generales - Los comunicadores combinan procesamiento en contexto y en grupo para seguridad de los mensajes. - Seguridad en las aplicaciones con hebrado.

§ Manejo de ambiente. MPI incluye definiciones para: - Temporizadores y sincronizadores. - Inicializar y finalizar. - Control de Errores. - Interacción con el ambiente de ejecución.

§ Comunicación punto a punto. - Heterogeneidad para el buffer y tipos de datos derivados. - Varios modos de Comunicación.

§ Comunicaciones colectivas: - Capacidad de manipulación de operaciones colectivas con operaciones propias o definidas por el usuario. - Gran número de rutinas para el movimiento de datos. - Los subgrupos pueden definirse directamente o por la topología.

§ Topologías por procesos: - Soporte incluido para las topologías virtuales para procesos.

§ Caracterización de la interfase: - Se permite al usuario interceptar llamadas MPI para instalar sus propias herramientas.

18

2.3.3. Elementos Básicos de la Programación de MPI

Iniciación y terminación de MPI [4] Lo primero que necesita hacer el programador para paralelizar sus programas con MPI es iniciar MPI. Por lo tanto la rutina a ser llamada por cualquier programa hecho con MPI es la rutina de iniciación, antes de cualquier otra rutina de MPI. Para la codificación en C, dicha rutina acepta los argumentos del main (argc y argv) para que estos puedan ser pasados a cada uno de los procesos, lo cual es una ventaja sobre la codificación en FORTRAN, ya que podemos crear ejecutables que reciba argumentos. La rutina de iniciación es la siguiente:

int MPI_Init(int *argc, char ***argv); Un programa con MPI debe de llamar a la rutina:

int MPI_Finalize(void); Cuando todas las comunicaciones son completadas. Esta rutina limpia todas las estructuras de datos de MPI, entre otras cosas. Esta rutina no cancela el estado las comunicaciones, es responsabilidad del programador completar y/o terminar con todas las comunicaciones. Esta rutina sólo puede ser llamada una vez, después de la llamada de dicha rutina ninguna otra rutina de MPI puede ser llamada, incluso MPI_Init, solo otro proceso nuevo lo podrá hacer.

Terminación anormal de procesos de MPI En ocasiones hay que prever una posible situación que pueda bloquear la terminación de nuestros procesos que se encuentran corriendo en paralelo. Un ejemplo de este tipo de situaciones que podrían presentarse, es el hecho de que uno de nuestros procesos se quede esperando la recepción de un mensaje, cuando todos los demás ya han terminado, esta situación impedirá a nuestra aplicación paralela terminar. Claro que esta es una situación que no se debe de presentar si el programa esta bien hecho, pero en ocasiones es posible que se presente dicha situación. Otra situación que puede provocar una terminación anormal de nuestros procesos es que en algún nodo se presente una situación que pueda afectar el desempeño de la aplicación en general, por lo que sería conveniente terminar nuestros procesos. Para esto se tiene la siguiente rutina que trata de terminar la aplicación paralela. int MPI_Abort(MPI_Comm comm, int codigoerror); Esta aplicación trata de terminar todos los procesos contenidos en comm, para que el programa paralelo termine.

Información del Ambiente Cuando el programador ejecuta sus programas con MPI, hay información que podría a llegar a ser relevante para nuestros propósitos, como lo es el número de procesos corriendo, numero (identificador) de proceso que se trata y/o en donde se encuentra corriendo. MPI provee rutinas que ayudan en la obtención de dichos datos. El valor para el número de procesos se obtiene con la rutina:

int MPI_Comm_size(MPI_Comm comm, int *numproc); comm Es el comunicador, utilizado en la comunicación de los proceso, este parámetro es usado pero no

modificado por la rutina. numproc Es el número de proceso en el grupo del comunicador, debe ser un apuntador ya que la rutina

modifica dicho parámetro. El identificador del proceso, es el número o rango del proceso, es un número entre cero y el total de procesos menos uno (n-1). La rutina para la obtención del identificador es:

19

int MPI_Comm_rank(MPI_Comm comm, int *identificador); comm Es el comunicador, utilizado en la comunicación de los proceso, este parámetro es usado

pero no modificado por la rutina. identificador Es el rango del proceso en el grupo del comunicador, debe ser un apuntador ya que la

rutina modifica dicho parámetro. El nombre de la estación donde se encuentra corriendo lo proporciona la rutina:

int MPI_Get_processor_name(char *nombre, int *longitud); nombre Es el apuntador de la cadena donde se guardara el nombre del procesador, este parámetro es

modificado por la rutina. longitud Es la longitud de la cadena nombre, este parámetro es modificado por la rutina. Es importante hacer notar que al pasarle un apuntador a una cadena, hay que reservar el espacio necesario que pudiese ocupar el nombre de la estación de trabajo. Para esto MPI define la macro MPI_MAX_PROCESSOR_NAME la cual es igual 256. Dicha macro esta definida en “mpi.h”.

Comunicadores y Etiquetas Entre las rutinas de iniciación que lleva a cavo MPI_Init esta la definición de algo llamado MPI_COMM_WORLD para cada proceso que llama dicha macro. MPI_COMM_WORLD es un comunicador. Todas las comunicaciones en MPI realizan llamadas a rutinas que requieren de un argumento comunicador, y los procesos en MPI sólo pueden comunicarse si comparten el mismo comunicador, ya que éste especifica un dominio de comunicación. Cada comunicador contiene un grupo que es una lista de procesos. Un proceso puede tener varios comunicadores y por consiguiente pertenecer a varios grupos. MPI_COMM_WORLD es el comunicador de todos los procesos en MPI. El procesamiento por grupos permite a MPI cubrir una serie de debilidades presentes en algunas bibliotecas de paso de mensajes e incrementa sus capacidades de portabilidad, eficiencia y seguridad. El procesamiento por grupos agrega elementos como: división de procesos, transmisión de mensajes sin conflictos, extensibilidad para los usuarios (para la creación de bibliotecas) y seguridad. MPI_GROUP_EMPTY sirve para denotar aquel grupo que no tiene miembros., La constante MPI_GROUP_NULL es el valor usado para referirse a un grupo no valido. Para crear un nuevo comunicador se debe partir de un comunicador ya existente. La rutina que implementa la creación de un comunicador es:

int MPI_Comm_dup(MPI_Comm comm, MPI_Comm *newcomm); comm Comunicador a partir del cual se generara uno nuevo, la rutina sólo hace uso de este

argumento. newcomm Nuevo comunicador, la rutina modifica dicho parámetro. Esta rutina le permite crear un nuevo comunicador (newcomm) compuesto de los mismos procesos que hay en comm pero con un nuevo contexto para asegurar que las comunicaciones efectuadas para distintos propósitos no sean confundidas. Finalmente cuando se han efectuado todas las comunicaciones asociadas al nuevo comunicador, este deberá ser destruido la rutina para la liberación del comunicador es como sigue, esta no implica mayor dificultad por lo que no requiere mayor explicación.

MPI_Comm_free(MPI_Comm *comm); En cuanto a las etiquetas, la función principal de estas es que un proceso tenga la opción de recibir o no, mensajes dependiendo de la “etiqueta” asociada a dicho mensaje, que no es otra cosa que

20

un número entero. Con esto MPI implementa la recepción de mensajes selectiva por parte de los procesos receptores.

Medición de tiempo Medir el tiempo que dura un programa es importante para establecer su eficiencia y para fines de depuración, sobre todo cuando éste es paralelo. Para esto MPI ofrece las funciones MPI_Wtime y MPI_Wtick. Ambas proveen alta resolución y poco costo.

double MPI_Wtime(void); MPI_Wtime devuelve un punto flotante que representa el número de segundos transcurridos a

partir de cierto tiempo pasado, el cual se garantiza que no cambia durante la vida del proceso. Es responsabilidad del usuario hacer la conversión de segundos a otras unidades de tiempo: horas, minutos, etc.

double MPI_Wtick(void); MPI_Wtick permite saber cuantos segundos hay entre tic's sucesivos del reloj. Por ejemplo, si el

reloj esta implementado en hardware como un contador que se incrementa cada milisegundo, entonces MPI_Wtick debe devolver 10-3

Tipos de datos en MPI Para el envió y recepción de mensajes es muy importante indicarle exactamente a las rutinas encargadas de ello, los tipos de datos que serán enviados, por lo que MPI establece una equivalencia entre los datos definidos en C/C++ y los tipos de datos de MPI. La siguiente tabla muestra las macros definidas para los tipos de datos de MPI y su equivalente en C, así como el valor de la macro.

Tipo de Dato en C Macro Valor de la Macro char MPI_CHAR 1 unsigned char MPI_UNSIGNED_CHAR 2 MPI_BYTE 3 short MPI_SHORT 4 unsigned short MPI_UNSIGNED_SHORT 5 int MPI_INT 6 unsigned MPI_UNSIGNED 7 long MPI_LONG 8 unsigned long MPI_UNSIGNED_LONG 9 float MPI_FLOAT 10 double MPI_DOUBLE 11 long double MPI_LONG_DOUBLE 12 long long int MPI_LONG_LONG_INT 13 MPI_PACKED 14 MPI_LB 15 MPI_UB 16 MPI_FLOAT_INT 17 MPI_DOUBLE_INT 18 long int MPI_LONG_INT 19 short int MPI_SHORT_INT 20 MPI_2INT 21

21

Tipo de Dato en C Macro Valor de la Macro MPI_LONG_DOUBLE_INT 22

Algunas de las macros definidas por MPI hacen referencia a datos que no son tipos de datos en C. En algunos casos simplemente se tratan de estructuras con la siguiente forma: struct { double var; int loc; } Como lo son las macros MPI_FLOAT_INT, MPI_DOUBLE_INT y MPI_LONG_DOUBLE_INT. Estos casos en particular al ser declarados en código C puro generaría el siguiente error en la compilación “too many types in declaration”(demasiados tipos en la declaración). Algunos otros son tipos simples como MPI_BYTE, el cual no requiere mayor explicación. Otros son más complejos como el MPI_PACKED, el cual será tratado más adelante.

Comunicación punto a punto Una comunicación punto-a-punto siempre involucra solamente dos procesos. Un proceso que envía el mensaje y otro que lo recibe. En el envío el proceso fuente hace una llamada a una rutina especificándole el proceso destino dentro del rango del comunicador. El proceso receptor sólo hace la llamada a la rutina de MPI para la recepción del mensaje, dentro del rango del comunicador, no es necesario especificar la fuente de quien se espera el mensaje. Existen cuatro modos de comunicación provistas por MPI: estándar, sincrono, buffered y lectura. Los cuatro tipos se refieren a cuatro tipos de envío, no es significante el modo de recepción de los mensajes en los modos de comunicación. El envío de un mensaje se completa cuando el buffer, el cual es el canal de comunicación, puede ser reutilizado. Los modos estándar,

sincrono y buffered difieren en el envío, sólo en un aspecto. Como se completa el envío dependiendo de cómo se recibe el mensaje. La siguiente tabla muestra los cuatro tipos de envío, así como la rutina encargada de ella y una descripción.

Modo de Comunicación

Rutina de MPI

Descripción

Estándar MPI_Send Se completa cuando el mensaje puede ser enviado, no implica que el mensaje pueda o no ser recibido.

Sincrono MPI_Ssend Sólo se completa cuando la recepción se ha completado Buffered MPI_Bsend Siempre se completa (a menos que ocurra un error), sin

considerar si la recepción se ha completado. El mensaje se copia a un sistema de buffer para después transmitir si es necesario.

Lectura MPI_Rsend Siempre se completa (a menos que ocurra un error), sin considerar si la recepción se ha completado.

El envío de mensajes involucra el intercambio de información entre los proceso. Pero, ¿Qué es un mensaje?

22

Un mensaje es un arreglo de elementos de un tipo de dato particular de MPI. Para todos los mensajes en MPI deben especificarse el tipo en el envío y la recepción. Los aspectos que MPI provee para el envío de mensajes y ganar portabilidad son los siguientes:

• Especificación de los datos a enviar con tres campos: dirección de inicio, tipo de dato y contador.

• Los tipos de datos son construidos recursivamente por las rutinas de MPI • La especificación de tipos de datos permite comunicaciones heterogéneas. • Se elimina la longitud de un mensaje a favor de un contador.

Cualquiera de las rutinas de envío de mensajes sigue el patrón de la rutina MPI_Send, el cual es el siguiente: MPI_Send(void *buf, int count, MPI_Datatype tipo, int dest, int etiqueta, MPI_Comm comunicador); donde:

buf Es la dirección del buffer de envío. count Es un entero que indica el número de elementos a recibir

tipo Tipo de datos de MPI de los elementos en el buffer de envío. destino Identificador del proceso destino.

etiqueta Etiqueta de un mensaje. comunicador Comunicador al cual pertenece el proceso que envía y recibe mensaje.

La recepción de un mensaje se realiza mediante la rutina: MPI_Recv(void *buf, int count, MPI_Datatype tipo, int fuente, int etiqueta, MPI_Comm

comunicador, MPI_Status estado); donde:


tipo Tipo de datos de MPI de los elementos en el buffer de envío. fuente Identificador del proceso fuente o MPI_ANY_SOURCE (reciba de cualquier fuente)

etiqueta Etiqueta de un mensaje o MPI_ANY_TAG (cualquier etiqueta). comunicador Comunicador al cual pertenece el proceso que envía y recibe mensaje.

estado Estructura de tipo MPI_Status con información variada. La estructura MPI_Status es usada para la información del mensaje recibido, esto en caso de que se hallan utilizado algunas de las macros MPI_ANY_TAG o MPI_ANY_SOURCE, que posteriormente puedan necesitarse, e incluso tiene un campo que indica el error que ocurrió en caso de que la recepción no se logre completar. La estructura es la siguiente:

typedef struct {

int count; int MPI_SOURCE; int MPI_TAG; int MPI_ERROR; int private_count;

}MPI_Status; Esta estructura se encuentra declarada dentro de “mpi.h”

23

Comunicaciones colectivas Además de las comunicaciones punto a punto MPI provee rutinas para las comunicaciones colectivas, por lo que permite la comunicación entre varios tipos de procesos. Las comunicaciones colectivas permiten la transferencia de datos entre procesos que tienen el mismo canal de comunicación, es decir, comunicador. En el caso de dichas comunicaciones se usan etiquetas para los mensajes, se hace uso del comunicador. [S2001] Las comunicaciones colectivas pueden ser clasificadas en tres clases:

• Sincronización: barreras para sincronizar. • Movimiento (transferencia) de datos: operaciones para difundir, recolectar y esparcir datos. • Cálculos colectivos: operaciones para reducción global, tales como suma, multiplicación,

máximo o mínimo o cualquier función definida por el usuario.

Sincronización Una operación de barrera sincroniza a todos los procesos que compartan el mismo canal de

comunicación, es decir, que pertenezcan al mismo grupo. No hay intercambio de datos. La rutina encargada de dicha operación es: int MPI_Barrier(MPI_Comm comunicador);

Movimiento (transferencia) de datos Para la transferencia de datos, en primer lugar se tiene a la comunicación uno-a-muchos en este el proceso raíz difunde el mismo mensaje a múltiples procesos con una simple operación.

La rutina de MPI que implementa dicho broadcast es: int MPI_Bcast(void *inbuf, int numelem, MPI_Datatype tipo, int raiz, MPI_Comm comunicador); donde:

24

inbuf Dirección del buffer de recepción, o buffer de envío si se trata del proceso raíz numelem Numero de elementos en el buffer de envío.

tipo Tipo de dato de los elementos en el buffer. raiz Rango del proceso raíz, es decir, el encargado de difundir los datos.

comunicador Canal de comunicación. Otras rutinas para las comunicaciones colectivas son: int MPI_Gather(void *inbuf, int numelem, MPI_Datatype intipo, void *outbuf, int outelem, MPI_Datatype outtipo, int raiz, MPI_Comm comunicador); La rutina anterior hace que cada proceso, incluyendo el proceso raíz, envié el contenido de su buffer de envío (inbuf) al proceso raíz. El proceso raíz recibe los mensajes y los almacena en orden (según el rango del proceso que realiza el envío) en el buffer de recepción (outbuf). int MPI_Scatter(void *inbuf, int numelem, MPI_Datatype intipo, void *outbuf, int outelem, MPI_Datatype outtipo, int raiz, MPI_Comm comunicador); En esta rutina el proceso raíz envié un trozo de información a cada proceso incluyéndolo a él. El proceso raíz enviará u trozo del contenido del buffer de envío (inbuf). Comenzando desde la dirección inicial de dicho buffer se desplazara una cantidad (numelem) para realizar el siguiente envío. donde:

inbuf Dirección del buffer envío. numelem Numero de elementos a enviar a cada proceso.

intipo Tipo de dato de los elementos en el buffer de entrada. outbuf Dirección del buffer de recepción.

outelem Número de elementos a recibir cada uno outtipo Tipo de elementos en el buffer de recepción.

raiz Rango del proceso raíz, es decir, el encargado de difundir los datos. comunicador Canal de comunicación.

Cálculos colectivos Básicamente las operaciones colectivas son operaciones de reducción. Una operación de reducción toma datos de diferentes procesos y los reduce a un simple dato. El orden de evaluación canónico de una reducción esta determinado por el rango de los procesos. La operación de reducción puede ser una operación predefinida o una definida por el usuario, Las operaciones definidas en MPI se muestran en la siguiente tabla:

Nombre de operación en

MPI Operación

MPI_MAX Máximo MPI_MIN Mínimo MPI_PROD Producto MPI_SUM Suma MPI_LAND Y lógico MPI_LOR O lógico MPI_LXOR XOR lógico MPI_BAND Y bit a bit MPI_BOR OR bit a bit

25

Nombre de operación en

MPI Operación

MPI_BXOR XOR bit a bit MPI_MAXLOC Máximo y su posición MPI_MINLOC Mínimo y su posición

Las rutinas que realizan las operaciones de reducción se explican a continuación. La diferencia entre estas dos rutinas es que en la primera sólo el proceso raíz tiene el resultado de la operación en su buffer de recepción, la segunda todos los procesos cuentan con el resultado en su buffer de recepción. int MPI_Reduce(void *inbuf, void *outbuf, int numelem, MPI_Datatype tipo, MPI_Op operacion, int root, MPI_Comm comunicador); int MPI_Allreduce(void *inbuf, void *outbuf, int numelem, MPI_Datatype tipo, MPI_Op operacion, int root, MPI_Comm comunicador); donde:

inbuf Dirección del buffer de envío. outbuf Dirección del buffer de recepción.

numelem Numero de elementos en el buffer de envío. tipo Tipo de datos de los elementos del buffer de envío.

operacion Operación a realizar sobre los elementos del buffer de envío. root Rango del proceso raíz.

comunicador Canal de comunicación.

Comunicaciones sin bloqueo El rendimiento de muchas operaciones se puede mejorar si se logran solapar las comunicaciones y el cálculo. La forma de solapar las comunicaciones es la creación de hilos de ejecución, con esto se puede crear una hilo que se encargue de las comunicaciones, mientras que el proceso siga realizando su trabajo. En este caso no habría problema al utilizar comunicaciones con bloqueo ya que el hilo encargado de las comunicaciones podría permanecer bloqueado, esperando la terminación de las mismas. La comunicación sin bloqueo es una alternativa, que usualmente da un buen resultado. La forma en que operan las comunicaciones es como sigue: para enviar y/o recibir un mensaje la rutina encargada de ello hace la solicitud y regresa antes de que el canal de comunicación se encuentre libre y/o ocupado, es así, como la rutina regresa antes de que el buffer de envío sea reutilizable y/o utilizable, por lo que hay que realizar una llamada a una rutina de verificación, para ver si el envío y/o recepción se han completado. Hasta el momento se han hablado de comunicaciones con bloqueo, esto quiere decir que la rutina llamada para la transmisión regresa si se han completado las operaciones, por lo que el proceso es detenido en cuanto las comunicaciones no terminen. Pero, MPI implementa estas mismas comunicaciones, sin bloqueo, las rutinas siempre regresan directamente y permiten que el proceso continué realizando su trabajo y después de un lapso de tiempo realice un test para verificar la terminación de la operación de envío y/o recepción. Las rutinas de MPI para la comunicación sin bloqueo tienen la misma sintaxis que las rutinas con bloqueo, excepto por el prefijo I (Inmediato), además las rutinas de envío se les agrega un parámetro en la llamada, dicho parámetro es un tipo de dado de MPI que posteriormente será utilizado para determinar si el mensaje se ha completado. Las rutinas de envío sin bloqueo son:

26

MPI_Isend MPI_Issend

MPI_Ibsend MPI_Irsend La sintaxis de estas rutinas tienen la misma sintaxis que la de MPI_Isend que es como sigue: int MPI_Isend(void *buf, int count, MPI_Datatype tipo, int dest, int etiqueta, MPI_Comm

comunicador, MPI_Request *request); donde:


tipo Tipo de datos de MPI de los elementos en el buffer de envío. destino Identificador del proceso destino.

etiqueta Etiqueta de un mensaje. comunicador Comunicador al cual pertenece el proceso que envía y recibe mensaje.

request Estructura de tipo MPI_Request con información que ayuda a determinar si las comunicaciones se han completado.

La rutina de recepción tiene la siguiente sinopsis: MPI_Recv(void *buf, int count, MPI_Datatype tipo, int fuente, int etiqueta, MPI_Comm

comunicador, MPI_Request *request); donde:


tipo Tipo de datos de MPI de los elementos en el buffer de envío. fuente Identificador del proceso fuente o MPI_ANY_SOURCE (reciba de cualquier fuente)

etiqueta Etiqueta de un mensaje o MPI_ANY_TAG (cualquier etiqueta). comunicador Comunicador al cual pertenece el proceso que envía y recibe mensaje.

request Estructura de tipo MPI_Request con información que ayuda a determinar si las comunicaciones se han completado.

Como ya se menciono anteriormente las rutinas de envío y recepción sin bloqueo no completan las comunicaciones, sólo hacen la solicitud de envío o recepción según sea el caso. Las funciones para completar el envío o la recocción son MPI_Wait y MPI_Test, la primera permite esperar por la finalización de una operación y la otra verifica si se ha completado dicha operación. La sinopsis de dichas rutinas es: int MPI_Wait(MPI_Request *request, MPI_Status *estado); int MPI_Test(MPI_Recuest *request, int *bandera, MPI_Status *estado); donde: request Tipo de dato de MPI_Recuest que determina la operación que se trata, envío o recepción.

bandera Bandera que especifica si la operación ha sido contemplada. estado Tipo de dato MPI_Status en donde se gurda toda la información sobre la operación

completada. En MPI existen otras rutinas que ayudan a la comunicación sin bloqueo, por ejemplo, en ocasiones no importa que un proceso se espere a que termine de enviar un mensaje, sino que hay muchos que esperan un mensaje que posiblemente no llegará, esto se presenta cuando no se sabe en realidad como se presentaran las comunicaciones entre los proceso, como lo es en este proyecto. Para

27

esto existen dos rutinas que ayudan a que un proceso no se bloquee esperando un mensaje, lo que se hace es verificar si se ha recibido un mensaje de una fuente especifica y con una etiqueta determinada. Las rutinas que realizan dicha verificación son: int MPI_Probe(int fuente, int etiqueta, MPI_Comm comunicador, MPI_Status *estado) ; int MPI_Iprobe(int fuente, int etiqueta, MPI_Comm comunicador, int *bandera, MPÌ_Status *estado) ; donde:

fuente Identificador rango del proceso enviador. etiqueta Etiqueta del mensaje.

comunicador Canal de comunicación. bandera Entero que determina si hay un mensaje con la respectiva etiqueta y fuente.

estado Tipo de dato de MPI_Status en donde se guarda información del mensaje recibido. La primera es una verificación con bloqueo, es decir, que esta se bloquea hasta que se presente un mensaje con las características especificadas. La segunda es sin bloqueo, esta rutina verifica si hay un mensaje que se ajuste a los parámetros y regresa, si se presenta esta situación modifica el parámetro bandera=true. Una vez que se sabe que llegó el mensaje, se puede recibir usando MPI_Recv. Con estas rutinas no sólo se puede evitar el bloqueo de un proceso además se pueden establecer comunicaciones sin que se tenga que establecer previamente una comunicación para establecer la longitud del mensaje a enviar, Esto se debe a que una vez que MPI_Probe o MPI_Iprobe hayan sido exitosas, se puede revisar la estructura estado con MPI_Get_count para obtener la información respectiva y usarla en MPI_Recv. La sinopsis esta rutina es: int MPI_Get_count(MPI_Status estado, MPI_Datatype tipo, int *contador); donde:

estado Tipo de dato MPI_Status donde se guarda información de la comunicación establecida. tipo Tipo de dato de los elementos recibidos.

contador Número de elementos recibidos.

2.3.4. Compilación de programas MPI [1] Para compilar los programas MPI, usualmente se utiliza el comando mpicc (o mpif77 en el caso de FORTRAN) cuyo funcionamiento y parámetros son similares a la del compilador gcc, no existe un manual del comando mpicc la siguiente sinopsis y opciones del compilador son tomadas del manual del gcc, pero fueron probadas exitosamente con programas MPI.

Sinopsis de mpicc mpicc [opciones] <fuente | Fuentes> [opciones]

Opciones: Algo muy importante que hay que tomar en cuenta es que las opciones van separadas una de otra, por ejemplo, si se tienen las opciones v y o no es posible ponerlas de la siguiente forma:

$: mpicc -vo hola holamundo.c Esto es incorrecto y el compilador marcará un error. La forma correcta de poner estas opciones es:

$: mpicc -v -o hola holamundo.c Las opciones más comunes son:

28

-o file Coloca la salida del proceso en un archivo con el nombre especificado especificando en file. Si no se utiliza esta opción la salida por default dependerá de la etapa en la que se encuentre, es decir, si se está en el preprocesado, compilado o ensamblado la salida será el nombre del fuente con la extensión correspondiente a la etapa de que se trate; si se trata del ejecutable la salida será a.out. -v Imprime en la salida estándar del error la ejecución de la instrucción al recorrer cada una de las etapas de la compilación. También imprime el número de versión del compilador y del preprocesador -Dmacro=valor Esta es utilizada para la creación de macros que no fueron declarados en el código fuente, por ejemplo, el archivo “prueba.c” con el siguiente código.

#include <stdio.h> #include “mpi.h” int id, proc, longitud; char nombre[50]; int main (int argc, char *argv[]) { MPI_Init (&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &id); MPI_Comm_size(MPI_COMM_WORLD, &proc); MPI_Get_processor_name(nombre, &longitud); printf("hola Mundo , estoy en el procesador %s\n", nombre); printf(“Macro definida : %d\n”, MCR); MPI_Finalize(); }

Hay que observar que la macro MCR no es declarada en el código fuente, para que nuestra compilación no tenga errores hay que realizarla de con la siguiente instrucción:

$: mpicc -o salida prueba.c -DMCR=1 Y no tendremos ningún problema en obtener nuestro ejecutable. -include file Esta opción debe ser utilizada para indicarle un archivo de cabecera que no halla sido declarado en el código fuente. Por ejemplo, si tenemos el archivo holamundo.c con el siguiente código:

#include <stdio.h> int id, proc, longitud; char nombre[50]; int main (int argc, char *argv[]) { MPI_Init (&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &id); MPI_Comm_size(MPI_COMM_WORLD, &proc); MPI_Get_processor_name(nombre, &longitud); printf("hola Mundo , estoy en el procesador %s\n", nombre); MPI_Finalize(); }

29

Hay que observar que no se ha incluido la biblioteca “mpi.h” y es necesario incluirla para poder compilar este programa. Pero la podemos incluir desde la línea de comandos como sigue:

$: mpicc holamundo.c -o salida -include /usr/share/mpi/include/mpi.h -static Esta opción es muy impórtate cuando uno crea los ejecutables en un sistema Linux y se los lleva para correrlos en otra distribución o en otro Unix, ya que el enlazado es simbólico. ¿Que quiere decir esto?, pues muy simple, en los ejecutables en los sistema tipo Unix no se inserta el código de las bibliotecas que se utilizan durante el programa, solamente se crea un enlace hacia la biblioteca necesaria para la corrida de nuestros ejecutables, esto hace a nuestros ejecutables compactos, pero, ¿Qué sucede si corremos nuestro ejecutable en una distribución que no tiene la biblioteca a la que se hace referencia?, pues se tendrán problemas para correr nuestra aplicación. Pero eso se soluciona muy fácilmente con esta opción, aunque se tiene un costo en el tamaño de nuestros ejecutables. -w Deshabilita el desplegado de todos los mensajes warnigs(advertencias). Estas son sólo algunas de las opciones que posiblemente se lleguen a utilizar para la compilación de programas MPI, este compilador también acepta la compilación paso por paso, pero en tal caso hay que tener cuidado principalmente al enlazar los programas ya que hay que conocer los parámetros utilizados para la llamada del enlazador.

2.3.5. Ejecución de Programas MPI MPI no especifica como serán arrancados los procesos MPI. Cada una de las implementaciones de MPI se encarga de definir los mecanismos de arranque de los procesos; para tales fines algunas versiones coinciden en el uso de un programa especial denominado mpirun. Dicho programa no es parte del estándar MPI. [1] Para ver las opciones del comando mpirun solo hay que poner la siguiente instrucción: $: mpirun -h Esto mostrará las opciones de dicho comando. A continuación se presenta la sinopsis del comando y alguna de las opciones más importantes, si se desea conocer el total de estas deberá verificar la ayuda de este comando.

Sinopsis. mpirun [opciones_mpirun...] <nombre_programa> [opciones_programa...]

opciones_mpirun: -arch <arquitectura> Especifica la arquitectura donde serán lanzados los programas. -h

30

Muestra la ayuda. -machine <nombre_maquina> Se usa para poner en marcha el proceso en la maquina especificada. -machinefile <nombre del machine_file> Toma la lista de las maquinas en donde el proceso será lanzado del archivo machine_file Este archivo es una lista de todas la maquinas disponibles. Si o se usa esta opción se toma el archivo por default machines.LINUX (en el caso de LINUX) que se encuentra en mpi/share/ la ubicación de la carpeta mpi variara dependiendo del sistema. En esta ubicación se encuentra un ejemplo de como debe de ser este archivo, ya que al instalarlo no se tiene configurado, o bien se puede utilizar el comando mpi/sbin/tstmachines el cual realiza una prueba sobre las posibles maquinas que pueden formar parte del cluster, este mismo comando configura el archivo machinefile que será usado por default. -np <numero_procesos> Especifica el número de procesos que serán lanzados de la aplicación paralela, estos no necesariamente se encontrara corriendo uno por maquina. -nodes <nodos> Especifica el numero de nodos que serán tomados del archivo machinesfile para lanzar los procesos -nolocal Especifica que el proceso no deberá ser lanzado en la machina local. -stdin archivo Usa el archivo como entrada estándar para la aplicación en paralelo. -v Imprime algunos mensajes en pantalla del trabajo que realiza. Al terminar mpirun regresa un cero, a menos que mpirun haya detectado un problema en alguno de los procesos, en tal caso regresa un valor distinto de cero.

31

2.4. Balance de Carga

Uno de los principales aspectos para obtener un buen rendimiento en los sistemas distribuidos

es el balance de carga. Es un componente muy importante, ya que de él depende el buen uso que se hace de la capacidad global de rendimiento del sistema (eficiencia). El rendimiento global depende en gran medida del algoritmo elegido para el balance de carga . El balance de carga es el método para que los sistemas distribuidos obtengan el mayor grado de eficiencia posible. El balance de carga consiste en el reparto de la carga entre los nodos del sistema para que la eficiencia sea mayor. La carga se distribuye y se traslada de los nodos más cargados a los nodos menos cargados del sistema. Con esto se consigue una reducción del tiempo de ejecución de las tareas en el sistema distribuido, y se consigue aproximar el tiempo de finalización de la ejecución de las tareas de cada uno de los nodos, es decir, se consigue que los nodos terminen de ejecutar "al mismo tiempo", y que no haya grandes diferencias entre el término de uno de ellos y él de los demás. Con todo esto se consigue que no haya nodos sobrecargados, y otros libres de trabajo, porque estos nodos sobrecargados trasladarían parte de su trabajo a esos otros nodos más libres de trabajo. Los algoritmos de distribución de carga se basan en unos componentes, que marcan las diferencias entre unos algoritmos y otros:

• Política de información: La cuál decide qué tipo de información debe recoger de los nodos, de qué nodos debe recoger ésta información, y cuándo debe recogerla.

• Política de transferencia: Decide si cada uno de los nodos es apto o no para llevar a cabo una transferencia, tanto de emisor como de receptor.

• Política de selección: Decide cuál es la carga que se va a transferir en una transferencia. • Política de localización: Localiza el nodo adecuado para realizar una determinada

transferencia.

De éste aspecto depende en gran medida el rendimiento global, ya que dependiendo de la elección del algoritmo de balance, se puede conseguir que todos los nodos del sistema estén trabajando en todo momento para minimizar el tiempo de ejecución de los procesos, o una mala elección del algoritmo de balance puede hacer que tan solo unos pocos nodos estén sobrecargados mientras que otros no tengan nada de trabajo.

Esa es la función principal que debe llevar a cabo el algoritmo de balance de carga, hacer que todos los nodos estén trabajando mientras que haya algún proceso pendiente, y sea posible ejecutar dicho proceso en varios nodos consiguiendo una disminución en el tiempo de proceso. Hay algunos casos en los que el algoritmo de distribución no debe repartir carga entre los demás nodos ya que el tiempo de ejecución de dicho proceso puede ser tan pequeño, que si se repartiera entre los nodos se perdería demasiado tiempo en la comunicación y el resultado sería un tiempo de ejecución mayor.

El algoritmo encargado del balance debe tener en cuenta todos estos detalles. Pero además existen varios políticas que hay que definir para llegar a elegir un algoritmo de distribución eficiente:

32

• Centralizado vs. Distribuido: Las políticas centralizadas son aquellas en las que la información

se concentra en una única ubicación física, que toma todas las decisiones de planificación. Esta solución presenta problemas de cuellos de botella, y tiene un límite en su grado de escalabilidad. Por otro lado las políticas distribuidas son aquellas en las que la información está repartida entre los distintos nodos, y las decisiones son tomadas entre todos. Los problemas son que la información puede no ser coherente, se replica la información y necesita más comunicaciones.

• Estáticas vs. Dinámicas: Las políticas estáticas toman decisiones de forma determinista o probabilística sin tener en cuenta el estado actual del sistema. Esta solución puede ser efectiva cuando la carga se puede caracterizar suficientemente bien antes de la ejecución, pero falla al ajustar las fluctuaciones del sistema. Las políticas dinámicas utilizan información sobre el estado del sistema para tomar decisiones, por lo que potencialmente mejoran a las políticas estáticas mejorando la calidad de las decisiones. Incurren en mayor sobrecarga al tener que recoger información de estado en tiempo real.

Todos estos conceptos y otros más son los que habrá que tener en cuenta para llegar a diseñar un

algoritmo de balance de carga, para un sistema distribuido, que consiga obtener el mayor rendimiento global posible.

3. Migración de datos

34

3. MIGRACIÓN DE DATOS [S2001] En el modelo de envió y recepción de mensajes, los mensajes son datos que un proceso

envía a otro o a otros, los datos es la información guardada en variables del proceso en cuestión. Estas variables pueden ser de diferente tipo, es decir, se puede tratar de un entero, una flotante, un carácter, una cadena, inclusive variables que guarden un conjunto de elementos de información conformados por alguno de los anteriores, etc. Pero no sólo se encuentra involucrado el tipo de información que se enviara, sino además a quien y/o a quienes les será enviado, y por supuesto la cantidad que se enviara de información. Estos parámetros son importantes para el envió de información. MPI implementa rutinas para el envió y recepción de mensajes. De tal manera MPI provee tres aspectos para el envío de datos, con los cuales gana portabilidad. La especificación de los datos a enviar con tres campos.

1. Dirección de inicio 2. Tipo de dato. 3. Contador.

Con las especificaciones de datos se permiten las comunicaciones heterogéneas. Las funciones básicas de MPI para el envío y recepción de datos son:

MPI_Send(void *buf, int count, MPI_Datatype tipo, int dest, int etiqueta, MPI_Comm comunicador);

MPI_Recv(void *buf, int count, MPI_Datatype tipo, int fuente, int etiqueta, MPI_Comm comunicador, MPI_Status estado);

Ya mencionadas en el apartado “Comunicación punto a punto” Además se establecen los cuatro tipo de comunicación en MPI: Estándar, Sincrono, Buffered y de Lectura mencionados en el mismo apartado. De tal manera que para enviar, por ejemplo el contenido de la variable x del proceso 0 al proceso 1, la forma de invocar la rutina para el envío seria como sigue:

MPI_Send(&x, 1, MPI_INT, 1, 99, MPI_COMM_WORLD); Y el proceso receptor realizaría la llamada a la rutina de recepción de la siguiente forma,

suponiendo que el resultado lo desea guardar en otra variable, digamos y: MPI_Recv(&y, 1, MPI_INT, 0, 99, MPI_COMM_WORLD, &status); Es importante que al enviar un dato se haga uso del equivalente declarado en MPI, ya que la

utilización de cualquier otro provoca que MPI, cometa errores en la recepción y por consiguiente quede bloqueado o sea abortado en el peor de los casos. Aunque para la recepción de un mensaje no necesariamente se necesite saber de quien viene o la etiqueta del mismo, por lo que otra forma de recibir un mensaje es como sigue:

MPI_Recv(&y, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status); La migración de datos no queda sólo en el envío, para que se hable de migración de información

el elemento enviado a otro proceso debe de desaparecer del proceso que lo envía. Esto se muestra en la figura. Que finalmente es lo que se pretende con este proyecto.

35

3.1. Definición e Implementación de un TDA lista balanceable

[AJ1994] Existen básicamente dos formas de implementar un TDA lista, una de ellas hace uso de arreglos, lo cual especifica una lista estática. Supongamos que deseamos realizar una lista estática de elementos los cuales contienen los siguientes datos: matricula, nombre, edad y sexo de un alumno. Lo primero que se pensaría en hacer es la creación de una estructura que tuviera tales elementos, esto se lograría de la siguiente forma:

struct registro { long matricula; char nombre[30]; int edad; char sexo;

}; El siguiente paso es la creación de la lista y como dicha lista es estática, lo más lógico es el uso de arreglos, así que el siguiente paso es: struct registro lista[50]; De tal forma que cada no de los elementos se encontraría uno seguido de otro en memoria como se muestra en la siguiente figura.

El enunciado anterior declara una lista con 50 elementos, lo cual es un inconveniente, ya que lo más probable es que se tengan más o menos elementos, por lo que se tendrían dos situaciones, la primera y no tan grave, es el desperdicio de memoria, la segunda sería fatal y provocaría una terminación anormal de nuestro proceso, al no tener memoria para guardar más elementos para los cuales reservamos memoria. La principal limitante es que se debe conocer el número de elementos que se tendrán, aunque por otro lado es de fácil manejo. [AJ1994] La otra forma de crear la lista es de forma dinámica, es decir en tiempo de ejecución pedir la memoria para que ésta sea tan grande como nos lo permita la memoria asignada a nuestro proceso. Además de esta forma nuestra lista puede estar vacía sin ocupar memoria. Esta forma de crear las listas nos trae el concepto de “listas ligadas”, lo cual se explica a continuación.

Ya observamos que el uso información de múltiples tipos involucra las estructuras. Pues a la estructura utilizada para la creación de la lista estática le agregamos un campo quedándonos de la siguiente forma:

struct registro { long matricula; char nombre[30]; int edad; char sexo; struct registro *sig; };

36

El campo agregado es un apuntador al tipo de dato creado para manejar los datos. En otras palabras, la estructura contiene un apuntador a su propio tipo. Esto significa que una instancia de tipo registro puede apuntar a otra instancia del mismo tipo. Esta es la menara en que se crean los enlaces en una lista ligada. Cada elemento de la lista tiene un campo que apunta al siguiente elemento de la lista como lo ilustra la siguiente figura.

Cada lista tiene un principio y un final. [MJ1995] El inicio de la lista está marcado por el apuntador a la cabeza, el cual apunta a la primera estructura de la lista. El apuntador de cabeza no es una instancia de la estructura, sino simplemente un apuntador al tipo de dato que forma la lista. El final de la lista está marcado por una estructura la cual tiene su campo apuntador igual a NULL. Debido a que todos los demás elementos de la lista tienen en su campo apuntador un valor distinto a NULL, que apunta al siguiente elemento de la lista, un valor de apuntador de NULL es una manera inequívoca para indicar el final de la lista. La estructura de la lista ligada, con su apuntador de cabeza y si último elemento se muestra en la siguiente figura.

Entre las ventajas significativas que se tienen con esta forma de realizar la implementación la lista, es en la inserción y eliminación de elementos de la lista, lo cual es una tarea común de programación. Mientras que con los arreglos, la eliminación de elementos así como la inserción, cuando se requiere preservar un orden, involucra gran cantidad de procesamiento al realizar corrimientos de los elementos, con las listas ligadas todo lo que se requiere es un manejo adecuado de apuntadores, de hecho no se necesitan mover los datos. Pero la principal ventaja es el espacio de almacenamiento como se explico anteriormente.

3.1.1. Implementación [AJ1994] Primeramente se hará uso de la palabra clave typedef para crear un sinónimo de la estructura que se pretende crear. Por ejemplo, si tomamos el ejemplo anterior: typedef struct registro nodo;

El que se haga uso de typedef o de la etiqueta de la estructura para declarar a las estructuras casi no tiene diferencia práctica, sólo da como resultado un código más conciso.

Enseguida se establece la estructura que será utilizada para guardar la información que se necesita guardar, anexando un campo, el cual deberá ser un apuntador al mismo tipo de la estructura, como se muestra a continuación:

struct registro {

37

long matricula; char nombre[30]; int edad; char sexo; nodo *sig; }; Una vez establecidas nuestras estructuras se procede a la creación de la lista, la cual en un

principio se encuentra vacía, con el siguiente enunciado ilustra la acción a tomar. nodo *lista=NULL; Una vez creada nuestra lista vacía, para agregar elementos a la misma se deberá solicitar

memoria para la creación de un elemento y una vez creado se deberá insertar en la lista. La forma de pedir memoria para un elemento de la lista se ilustra en las siguientes líneas:

nodo *aux=NULL; aux=(nodo *)malloc(sizeof(nodo)); if(aux!=NULL) { /**** Se inicializa el nodo con los elementos necesarios ****/ /**** El apuntador al siguiente elemento deberá ser inicializado a NULL *****/ aux->sig=NULL; } Las funciones de creación de nodos, la inserción y eliminación de nodos se dejan a

consideración del usuario. Es importante declarar un apuntador al tipo de elemento con el cual se formará la lista y no una

instancia de la misma. Uno de los motivos es que si se declara una instancia de la misma, en realidad no se llegará gamas a tener una lista vacía además todo el manejo de apuntadores será peligroso.

38

3.2. Envío / recepción de un nodo de un TDA lista

Como ya se mencionó uno de los objetivos de este proyecto es el envío y la recepción de uno o varios nodos de un TDA lista, sin importar los campos que contenga cada nodo de dicha lista. Para tal motivo se creará un TDA lista cuyos nodos poseen los siguientes datos de un alumno, como lo son: nombre, edad, matricula y sexo. El código de las funciones para el manejo de la lista se muestra en el Anexo A listado “operlis.c”, se encuentran debidamente documentadas, pero se considera que estas no son de gran importancia ya que se pretende que el usuario cree sus propias funciones de manejo de la lista y sólo haga uso de las funciones creadas para la migración de nodos del TDA. Se usan otras funciones que solamente son auxiliares en el desplegado de información en pantalla, creación del TDA a partir de un archivo y obtención de valores al azar para la simulación de una petición para enviar nodos del TDA a otro nodos del cluster, con lo cual se lograría un balance de carga, el cual es el objetivo principal de dicho proyecto. Dichos códigos se encuentran en el Anexo A. MPI implementa rutinas para el envío y recepción de datos primitivos de C. En el caso de un TDA, el contenido de los nodos puede llegar a ser tan sencillo como enviar un dato nativo de C. Ahora el problema con el TDA que se pretende manejar, es que además de ser un TDA creado dinámicamente, pueden estar involucrados el manejo de otras estructuras. Para lograr enviar nodos de un TDA lista de un nodo del cluster a otro, se exploran las diferentes opciones mediante las cuales se puede realizar dicha tarea. Todas las versiones aquí presentadas tienen la misma función principal. A continuación se presenta el código fuente del modulo principal de cada uno de los programas, el cual es idéntico para todas las formas en que se envían los nodos de TDA. main(int argc, char *argv[]) { nodo *lista=crea_lista(); MPI_Init (&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &id); MPI_Comm_size(MPI_COMM_WORLD, &proc); MPI_Get_processor_name(nombre, &long_nom); if(id==COORDINADOR) { int destino=0, num_elem=0, lon_tda=0; printf("Soy el coordinador desde %s\n", nombre); lista=obten_datos("/tmp/regis.txt"); //Creación del TDA a partir de un archivo. Printf(lista); //Impresión del TDA lon_tda=longitud_TDA(lista); //Se prepara para migrar elementos valores_azar(proc, lon_tda, &destino, &num_elem); lista=Envia_TDA(lista, destino, num_elem); //Envía elementos printf("%d elementos son enviados a: %d\n", num_elem, destino); printf("Soy el coordinador desde %s\n", nombre); Printf(lista); //Función que imprime la lista } else { printf("\n Hola Mundo, soy el proceso %d, desde %s\n", id, nombre); lista=Recive_TDA(lista); if(!es_vacia(lista)) Printf(lista); //Función que imprime la lista printf("\n"); } MPI_Finalize(); return 0;

39

}

Cabe recordar que el desarrollo del proyecto para el balance de carga se basa en un “problema de juguete”, el cual nos ayudara a ver como y en que forma debemos utilizar para la migración de los nodos del TDA lista de una forma más general, es decir, que nuestro código sea capaz de migrar nodos de una lista sin tener que conocer los elementos que conforman dicho nodo.

3.2.1. Envío / recepción del nodo Campo por Campo (Versión 1 “camxcam.c”) El primer acercamiento que se tiene para migrar los nodos del TDA lista es el más “sencillo”, pero es el menos conveniente para ser utilizado. Este consiste en que el proceso enviador envié cada nodo del TDA lista, campo por campo, esto claro trae repercusiones en las comunicaciones y en el caso de un gran manejo de información llegar a saturar el canal de comunicación, ya que las comunicaciones en el modelo de paso de mensajes utiliza el protocolo TCP/IP. Bueno para realizar el envío campo por campo solamente se realiza un ciclo para cumplir con el envío de los nodos solicitados. En cada iteración se envía cada uno de los campos al proceso destino. Es un procedimiento que no requiere mayores explicaciones, pero si hay que realizar ciertas precisiones: 1.Se debe tener cuidado con enviar y recibir el tipo de dato especificado en C con su equivalente en

MPI, es decir, que si yo declaro un double x; para el envío de este dato de debe especificar MPI_DOUBLE como parámetro de tipo de dato en la función de envío y recepción, cualquier otro parámetro diferente al equivalente de MPI puede causar resultados inesperados.

2.Antes de comenzar a enviar cada uno de los nodos se debe de mandar un mensaje al proceso receptor indicándole cuantos nodos se le van a enviar, para que este realice las iteraciones necesarias para la recepción de todos los nodos que le sean enviados.

3.En caso de que el dato a enviar, sea un arreglo, se pueden presentar dos situaciones, una que se envié el numero de elementos del arreglo antes que el arreglo mismo, de esta forma el proceso receptor sabrá la longitud del siguiente mensaje; la segunda es hacer uso de las rutinas MPI_Probe y MPI_Get_count en conjunto para la recepción del arreglo. En esta versión se opta por la primera opción.

4.Si el nodo del TDA lista hace usos de estructuras como campos, se le deberá dar el mismo tratamiento a dichos campos para enviarlos.

El código de la función de envío es el siguiente: /***** En este primer acercamiento se envía campo por campo ****/ nodo *Envia_TDA(nodo *lista, int destino, int num_elem) { int i=0, etiqueta=99, cero=0; int longitud=0; nodo *ap=lista; //Primero se manda el numero de elementos a migrar for(i=1; i<proc; i++) { if(i==destino) MPI_Send(&num_elem, 1, MPI_INT, i, etiqueta, MPI_COMM_WORLD); else //Si se trata de alguien diferente al destino MPI_Send(&cero, 1, MPI_INT, i, etiqueta, MPI_COMM_WORLD); } for(i=0; i<num_elem; i++) {

40

ap=lista; longitud=strlen(ap->nombre)+1; //longitud de la cadena // Se envía campo por campo MPI_Send(&ap->matricula, 1, MPI_UNSIGNED, destino, etiqueta, MPI_COMM_WORLD); MPI_Send(&longitud, 1, MPI_INT, destino, etiqueta, MPI_COMM_WORLD); // Se envía la longitud de la cadena antes de enviarla MPI_Send(&ap->nombre, longitud, MPI_CHAR, destino, etiqueta, MPI_COMM_WORLD); MPI_Send(&ap->edad, 1, MPI_INT, destino, etiqueta, MPI_COMM_WORLD); MPI_Send(&ap->sexo, 1, MPI_CHAR, destino, etiqueta, MPI_COMM_WORLD); // Se elimina del TDA el nodo enviado lista=lista->sig; free(ap); } return lista; }

El código de la función de recepción es el siguiente: /***** Él(los) proceso(s) receptor(es) reconstruye(n) el TDA que les es enviado *****/ nodo *Recive_TDA(nodo *lista) { int num_elem=0, i=0, longitud=0; nodo *ap=NULL; unsigned matricula=0; char nombre[40], sexo; int edad; /*** Se recibe el numero de elementos a recibir ***/ MPI_Recv(&num_elem, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); printf("El mensaje recibido es: %d \n", num_elem); for(i=0; i<num_elem; i++) { MPI_Recv(&matricula, 1, MPI_UNSIGNED, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); // Se recibe la longitud del campo siguiente MPI_Recv(&longitud, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); MPI_Recv(nombre, longitud, MPI_CHAR, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); MPI_Recv(&edad, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); MPI_Recv(&sexo, 1, MPI_CHAR, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); // Reconstrucción del TDA ap=crea_nodo(matricula, nombre, edad, sexo); lista=inserta_nodo(lista, ap); } return lista; }

El inconveniente con esta versión del programa es que genera una gran cantidad de mensajes, lo que tiene gran repercusión en las comunicaciones. Pero el problema fundamental es que no es un código genérico, esto trae como consecuencia que, si se maneja un TDA lista diferente al usado para el desarrollo de esta versión, este código no funcionará.

41

3.2.2. Envío / recepción nodo empaquetado (Versión 2.1 “empaketado.c”) Para la segunda versión el problema a vencer es la gran cantidad de mensajes que se generan al enviar los nodos del TDA lista campo por campo. La solución a este problema la provee MPI mediante el empaquetado de datos. En el apartado “Tipos de dados de MPI” del capitulo 2.2. se menciono un tipo de dato de MPI, este es el MPI_PACKED. MPI provee mecanismos para el empaquetamiento de datos. Empacar datos es “almacenar datos no continuos en un buffer continuo, para que sean enviados y una vez recibidos nuevamente almacenarlos en localidades discontinuas”. Las rutinas encargadas del empaquetamiento y desempaquetamiento de datos son: int MPI_Pack(void *inbuff, int num_elem, MPI_Datatype tipo, void *outbuff, int outtam, int *posicion, MPI_Comm comuicador); donde:

inbuff buffer de entrada num_elem Número de elementos a ser empaquetados.

tipo Tipo de dato en la entrada outbuff buffer de salida, donde se almacenarán los datos en forma continua. outtam Tamaño del buffer de salida.

posicion Indicador de posición actual en el buffer de salida. comunicador Canal de comunicación.

MPI_Pack permite copiar en un buffer (outbuff) continuo de memoria datos almacenados en el

buffer (inbuff) de entrada. Cada llamada a la rutina MPI_Pack modificará el valor del parámetro posicion incrementándolo según el valor de num_elem. int MPI_Unpack(void *inbuff, int intam, int *posicion, void *outbuff, int outelem, MPI_Datatype tipo, MPI_Comm comuicador); donde:

inbuff buffer de entrada intam Tamaño del buffer de entrada en bytes,

posicion Indicador de posición actual en el buffer de salida. outbuff buffer de salida, donde se almacenarán los datos en forma continua. outelem Número de elementos a ser desempaquetados.

tipo Tipo de dato en la salida comunicador Canal de comunicación.

MPI_Unpack permite copiar en un buffer (outbuff) los datos almacenados en el buffer continuo (inbuff) de entrada. Cada llamada a la rutina MPI_Unpack modificará el valor del parámetro posicion incrementándolo según el valor de outelem. Para esta versión se crea un paquete por cada nodo del TDA lista y es enviado. El proceso receptor se encarga de desempaquetar la información contenida en el buffer de recepción y reconstruye el nodo del TDA y lo enlista.

42

El código de la función de envío es: nodo *Envia_TDA(nodo *lista, int destino, int num_elem) { int i=0, etiqueta=99, cero=0, posicion=0; int longitud=0; nodo * ap=lista; size_t tam=0; char *buffer; //Primero se manda el numero de elementos a migrar for(i=1; i<proc; i++) { if(i==destino) MPI_Send(&num_elem, 1, MPI_INT, i, etiqueta, MPI_COMM_WORLD); else //Si se trata de alguien diferente al destino MPI_Send(&cero, 1, MPI_INT, i, etiqueta, MPI_COMM_WORLD); } for(i=0; i<num_elem; i++) { ap=lista; longitud=strlen(ap->nombre)+1; //longitud de la cadena posicion=0; //Se inicializa el indicador de la posición en el buffer //Se calcula el tamaño de la memoria a solicitar tam=sizeof(int)+sizeof(char)*longitud+sizeof(unsigned)+sizeof(int)+sizeof(char); // También se empaqueta la longitud de la cadena para ser enviada buffer=(char *)malloc(tam); if(buffer!=NULL) { //Se envía el tamaño del paquete a ser enviado. MPI_Send(&tam, 1, MPI_INT, destino, etiqueta, MPI_COMM_WORLD); //Comienza el empaquetado de la información MPI_Pack(&longitud, 1, MPI_INT, buffer, tam, &posicion, MPI_COMM_WORLD); MPI_Pack(&ap->nombre, longitud, MPI_CHAR, buffer, tam, &posicion, MPI_COMM_WORLD); MPI_Pack(&ap->matricula, 1, MPI_UNSIGNED, buffer, tam, &posicion, MPI_COMM_WORLD); MPI_Pack(&ap->edad, 1, MPI_INT, buffer, tam, &posicion, MPI_COMM_WORLD); MPI_Pack(&ap->sexo, 1, MPI_CHAR, buffer, tam, &posicion, MPI_COMM_WORLD); //Fin del empaquetado. //Se envía el paquete. MPI_Send(buffer, posicion, MPI_PACKED, destino, etiqueta, MPI_COMM_WORLD); // Se elimina del TDA el nodo enviado lista=lista->sig; free(ap); free(buffer); } else { perror("Memoria Insuficiente..."); //Se envía un cero para identificar que hubo un error y se rompe el ciclo MPI_Send(&cero, 1, MPI_INT, destino, etiqueta, MPI_COMM_WORLD); break; } } return lista; }

43

El código de la función de recepción es: ***** Él(los) proceso(s) receptor(es) reconstruye(n) el TDA que les es enviado *****/ nodo *Recive_TDA(nodo *lista) { int num_elem=0, i=0, longitud=0, posicion=0; nodo *ap=NULL; unsigned matricula; char nombre[40], sexo; int edad; size_t tam; char *buffer; /*** Se recibe el numero de elementos a recibir ***/ MPI_Recv(&num_elem, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); printf("El mensaje recibido es: %d \n", num_elem); for(i=0; i<num_elem; i++) { posicion=0; //Se inicializa la posición en el buffer MPI_Recv(&tam, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); if(tam<0) //Si se recibe un cero es que hubo un error y se rompe el ciclo break; buffer=(char *)malloc(tam); if(buffer!=NULL) { //Se recibe el paquete. MPI_Recv(buffer, tam, MPI_PACKED, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); //Se comienza a desempaquetar // Se recibe la longitud del campo siguiente MPI_Unpack(buffer, tam, &posicion, &longitud, 1, MPI_INT, MPI_COMM_WORLD); MPI_Unpack(buffer, tam, &posicion, nombre, longitud, MPI_CHAR, MPI_COMM_WORLD); MPI_Unpack(buffer, tam, &posicion, &matricula, 1, MPI_UNSIGNED, MPI_COMM_WORLD); MPI_Unpack(buffer, tam, &posicion, &edad, 1, MPI_INT, MPI_COMM_WORLD); MPI_Unpack(buffer, tam, &posicion, &sexo, 1, MPI_CHAR, MPI_COMM_WORLD); // Reconstrucción del TDA ap=crea_nodo(matricula, nombre, edad, sexo); lista=inserta_nodo(lista, ap); free(buffer); } else perror("Memoria Insuficiente..."); } return lista; }

Con esta versión se logra eliminar un gran número de mensajes, hay que considerar que aún se debe de enviar un mensaje al proceso receptor antes de mandar los nodos del TDA lista, para que sepa cuantos nodos serán recibidos.

44

3.2.3. Envío / recepción TDA empaquetado (Versión 2.2 “empaketado_b.c”) La siguiente versión es aún mejor ya que se solo se envían dos mensajes para migrar todos los nodos de TDA lista, uno con el tamaño del paquete y el paquete en sí. En esta versión del programa se crea un paquete que contiene todos los nodos de la lista. El código para la función de envío es: ***** En este acercamiento se envía un paquete para todos los nodos del TDA lista ****/ nodo *Envia_TDA(nodo *lista, int destino, int num_elem) { int i=0, etiqueta=99, cero=0, posicion=0; int longitud=0; nodo *ap=lista; size_t tam=calcula_tam_buffer(lista, num_elem); char *buffer; //Primero se manda el numero de elementos a migrar for(i=1; i<proc; i++) { if(i==destino) MPI_Send(&num_elem, 1, MPI_INT, i, etiqueta, MPI_COMM_WORLD); else //Si se trata de alguien diferente al destino MPI_Send(&cero, 1, MPI_INT, i, etiqueta, MPI_COMM_WORLD); } buffer=(char *) malloc(tam); if(buffer!=NULL) { ap=lista; //Se envía el tamaño del paquete a ser enviado. MPI_Send(&tam, 1, MPI_INT, destino, etiqueta, MPI_COMM_WORLD); //Este ciclo crea un solo paquete para todos los nodos. for(i=0; i<num_elem; i++) { ap=lista; longitud=strlen(ap->nombre)+1; //longitud de la cadena MPI_Pack(&longitud, 1, MPI_INT, buffer, tam, &posicion, MPI_COMM_WORLD); MPI_Pack(&ap->nombre, longitud, MPI_CHAR, buffer, tam, &posicion, MPI_COMM_WORLD); MPI_Pack(&ap->matricula, 1, MPI_UNSIGNED, buffer, tam, &posicion, MPI_COMM_WORLD); MPI_Pack(&ap->edad, 1, MPI_INT, buffer, tam, &posicion, MPI_COMM_WORLD); MPI_Pack(&ap->sexo, 1, MPI_CHAR, buffer, tam, &posicion, MPI_COMM_WORLD); // Se elimina del TDA el nodo enviado lista=lista->sig; free(ap); } //Se envía el paquete. MPI_Send(buffer, posicion, MPI_PACKED, destino, etiqueta, MPI_COMM_WORLD); free(buffer); //se libera el espacio asignado. } else { perror("Memoria Insuficiente..."); //Se envía un cero para indicar que hubo un error. MPI_Send(&cero, 1, MPI_INT, destino, etiqueta, MPI_COMM_WORLD); } return lista; }

45

[MJ1995] En esta versión se utiliza una función la cual calcula el tamaño del paquete a ser enviado, el código de dicha función es: size_t calcula_tam_buffer(nodo *lista, int num_elem) { nodo *aux=lista; int i=0, longitud=0; size_t tama=0; for(i=0; i<num_elem; i++) { longitud=strlen(aux->nombre)+1; tama+=sizeof(int)+sizeof(char)*longitud+sizeof(unsigned)+sizeof(int)+sizeof(char); aux=aux->sig; } return tama; }

Es importante hacer el cálculo correcto del tamaño del buffer para enviar, un cálculo mal hecho provocaría que los procesos se pasmaran, ya sea porque el proceso encargado de enviar el mensaje escriba fuera de los límites establecidos para el buffer o por que el proceso receptor se quede esperando a que el canal de comunicación este vacío. Cabe mencionar que si se tiene que calcular el tamaño de una estructura como lo es en este caso, no es lo mismo realizar el cálculo de la estructura que de todos sus campos en conjunto, es decir, si tenemos la siguiente estructura:

struct Nodo_A { int x; double y; char array[20]; } Tenemos las siguientes formas de calcular su tamaño: size_a=sizeof(struct Nodo_a); size_b=sizeof(int)+sizeof(bouble)+20*sizeof(char);

Esto no necesariamente da el mismo resultado. La forma correcta de realizar el calculo, es hacerlo campo por campo y la razón es muy obvia. Nosotros no necesitamos el espacio que ocupa la estructura, ya que no guardamos la estructura en el buffer de envío, nosotros guardaremos los campos de la estructura en el buffer, por tal motivo lo que necesitamos es calcular el espacio de los campo en conjunto.

46

El código para la función de recepción es: /***** Él(los) proceso(s) receptor(es) reconstruye(n) el TDA que les es enviado *****/ nodo *Recive_TDA(nodo *lista) { int num_elem=0, i=0, longitud=0, posicion=0; nodo *ap=NULL; unsigned matricula; char nombre[40], sexo; int edad; size_t tam=0; char *buffer; /*** Se recibe el numero de elementos a recib ir ***/ MPI_Recv(&num_elem, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); printf("El mensaje recibido es: %d \n", num_elem); if(num_elem>0) MPI_Recv(&tam, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); if(tam>0) { buffer=(char *)malloc(tam); if(buffer!=NULL) { //Se recibe el paquete. MPI_Recv(buffer, tam, MPI_PACKED, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); //Se comienza a desempaquetar for(i=0; i<num_elem; i++) { // Se recibe la longitud del campo siguiente MPI_Unpack(buffer, tam, &posicion, &longitud, 1, MPI_INT, MPI_COMM_WORLD); MPI_Unpack(buffer, tam, &posicion, nombre, longitud, MPI_CHAR, MPI_COMM_WORLD); MPI_Unpack(buffer, tam, &posicion, &matricula, 1, MPI_UNSIGNED, MPI_COMM_WORLD); MPI_Unpack(buffer, tam, &posicion, &edad, 1, MPI_INT, MPI_COMM_WORLD); MPI_Unpack(buffer, tam, &posicion, &sexo, 1, MPI_CHAR, MPI_COMM_WORLD); // Reconstrucción del TDA ap=crea_nodo(matricula, nombre, edad, s exo); lista=inserta_nodo(lista, ap); } free(buffer); } else perror("Memoria Insuficiente..."); } return lista; }

En estas versiones se soluciona el problema del envío de múltiples mensajes, pero no se tiene ganancia alguna en cuanto a la generalidad de las funciones, se sigue teniendo el problema al manejar los campos de los nodos del TDA lista. Además se presenta otro problema, que es el manejo de la memoria para la versión 2.2, se puede presentar el caso que la memoria no sea asignada al ser de un gran tamaño.

47

3.2.4. Envío / recepción de un nodo usando uniones (Versión 3.1 “uniones.c”) Hasta el momento en las versiones anteriores se tiene el problema que para migrar un nodo de un TDA lista se debe conocer los campos del nodo, lo cual es un problema, ya que lo que se pretende que la migración sea independiente de dichos campos. [AJ1994] En C existe un tipo de estructuras especiales para guardar diferentes tipos de datos en un momento dado, estas estructuras son las uniones, las cuales permiten solapar sobre una misma dirección de memoria distintos tipos de datos, ya sea de datos primitivos de C o de datos derivados. Supongamos que definimos una unión de la siguiente forma: union prueba { char letra; int x; double y; }var; En el ejemplo anterior se tienen 3 tipos de datos, los cuales tienen la misma dirección de memoria, pero cada uno ocupa un espacio diferente en la misma; la variable de tipo char ocupa 1 byte , la variable tipo int ocupa 2 bytes y la variable de tipo double ocupa 4 bytes (puede variar dependiendo del compilador). Es así como el espacio que ocupe en memoria la variable “var” de tipo unión declarada, será del tamaño del dato más grande, en este ejemplo será de 4 bytes. Esta unión permite guardar tres tipos de datos diferentes en una sola dirección de memoria. Esta característica se usa en MPI para evitar el empaquetamiento y desempaquetamiento de datos, los que se hace es crear una unión con dos campos, uno de ellos es el tipo de dato que se desea enviar, en este caso el nodo de un TDA lista, el otro campo es un arreglo de tipo char con la longitud equivalente al tamaño del nodo del TDA lista. En una versión anterior se calculó el tamaño de los datos a enviar campo por campo, en esta ocasión si necesitamos el tamaño de la estructura, ya que realmente lo que haremos es enviar la estructura tal cual y no campo por campo. La forma de hacer uso de esta unión es muy sencilla, lo que hay que hacer es copiar el nodo que se desea migrar a la unión, enseguida se manda como un mensaje de longitud igual al tamaño del nodo del TDA lista, y se recibe de la misma forma, una vez recibido se puede hacer uso normalmente de la estructura para manejar el nodo del TDA lista. La unión utilizada se presenta a continuación, así mismo se presenta la estructura de datos declara para el desarrollo de esta parte del proyecto, dicha estructura se encuentra declarada en el archivo “protos.h”.

typedef union Nodos_TDA e_TDA; union Nodos_TDA { nodo ap; char mensaje[STRUCTSIZE]; }; typedef struct Registro nodo; struct Registro

48

{ char nombre[40]; unsigned matricula; int edad; char sexo; nodo *sig; };

Enseguida se muestra el código para la función de envío del nodo del TDA lista haciendo uso de las uniones de C. /***** En esta v ersión se realiza el envío mediante el uso de uniones ****/ nodo *Envia_TDA(nodo *lista, int destino, int num_elem) { int i=0, etiqueta=99, cero=0; int longitud=0; e_TDA elem; nodo *ap=NULL; //Primero se manda el número de elementos a migrar for(i=1; i<proc; i++) { if(i==destino) MPI_Send(&num_elem, 1, MPI_INT, i, etiqueta, MPI_COMM_WORLD); else //Si se trata de alguien diferente al destino MPI_Send(&cero, 1, MPI_INT, i, etiqueta, MPI_COMM_WORLD); } for(i=0; i<num_elem; i++) { ap=lis ta; strcpy(elem.ap.nombre, ap->nombre); elem.ap.matricula=ap->matricula; elem.ap.edad=ap->edad; elem.ap.sexo=ap->sexo; MPI_Send(elem.mensaje, STRUCTSIZE, MPI_CHAR, destino, etiqueta, MPI_COMM_WORLD); lista=lista->sig; free(ap); } return lis ta; } El siguiente código corresponde a la función de recepción del nodo TDA lista. /***** Él(los) proceso(s) receptor(es) reconstruye(n) el TDA que les es enviado *****/ nodo *Recive_TDA(nodo *lista) { int num_elem=0, i=0, longitud=0; e_TDA elem; nodo *ap=NULL; /*** Se recibe el numero de elementos a recibir ***/ MPI_Recv(&num_elem, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); printf("El mensaje recibido es: %d \n", num_elem); for(i=0; i<num_elem; i++) { MPI_Recv(elem.mensaje, STRUCTSIZE, MPI_CHAR, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); ap=crea_nodo(elem.ap.matricula, elem.ap.nombre, elem.ap.edad, elem.ap.sexo); lista=inserta_nodo(lista, ap); } return lista;

49

} Cabe realizar unas observaciones para esta versión.

1. Es claro que el código es mucho más compacto que en las versiones anteriores. 2. Hay que mandar un mensaje por cada nodo a enviar. 3. Solamente se logra eliminar el manejo de los capos en el código de recepción del nodo del TDA

lista. El problema persiste en la función de envío. [MJ1995] Por ultimo es importante que en la unión se declare una variable del tipo que se desea

migrar y no un apuntador a una variable de dicho tipo. ¡Forma incorrecta! union Nodos_TDA { nodo *ap; char mensaje[STRUCTSIZE]; }mensg;

Esta forma se ve muy conveniente, ya que para copiar el nodo que se va a migrar, solo habría

que igualar sus apuntadores de la siguiente forma, por ejemplo: mensg=lista; lista=lista->sig; De esta forma se evitaría la copia de campo por campo, pero esto es un error fatal, para que

podamos realizar el envío de un nodo del TDA lista, utilizando uniones, debemos de garantizar que la información del nodo se encuentre en el lugar que ocupa la unión en memoria, para poder solaparla con el arreglo de tipo char. Lo cual no se logra igualando apuntadores, no de esta forma, lo que logramos hacer con esto es hacer que el apuntador de la unión apunte al apuntador del nodo del TDA lista, pero eso no quiere decir que la información ya se encuentra donde queremos.

3.2.5. Envío / recepción de un nodo usando uniones (Versión 3.2 “uniones_b.c”) El problema de la versión anterior es que en la función de envío aún se necesitaba manejar los campos de cada uno de los nodos del TDA lista, la forma en que se soluciona este problema es usando apuntadores, pero no como se indico anteriormente. Sino de la siguiente forma: Primero declaramos la unión de la forma correcta, que es como sigue:

union Nodos_TDA { nodo ap; char mensaje[STRUCTSIZE]; }mensg;

[AJ1994] Hay que hacer la observación que dentro de la estructura se tiene declarada una variable del tipo que se desea migrar y no un apuntador, pues como ya mencionamos necesitamos garantizar que la información del nodo a migrar se encuentre en el lugar que ocupa la unión en memoria.

Como segundo paso realizaremos la copia, mediante los apuntadores de la siguiente forma: ap=lista; elem.ap=*ap; Las variables ap y lista son nodos del TDA lista, la variable elem es la variable de tipo unión, de tal forma que elem.ap es del tipo nodo del TDA lista. Lo que se hace con la segunda instrucción es la copia del nodo hacia la unión, es decir, copia lo que se encuentra en la dirección *ap en elem.ap.

50

Con esto se soluciona por completo el problema del manejo de los campos de los nodos. Por lo que en esta versión se tienen las funciones de envío y recepción como sigue: nodo *Envia_TDA(nodo *lista, int destino, int num_elem) { int i=0, etiqueta=99, cero=0; nodo *ap=NULL; e_TDA elem; //Primero se manda el número de elementos a migrar for(i=1; i<proc; i++) { if(i==destino) MPI_Send(&num_elem, 1, MPI_INT, i, etiqueta, MPI_COMM_WORLD); else //Si se trata de alguien diferente al destino MPI_Send(&cero, 1, MPI_INT, i, etiqueta, MPI_COMM_WORLD); } for(i=0; i<num_elem; i++) { ap=lista; //Se realiza una copia del nodo en el elemento de la unión para poder ser transferido. elem.ap=*ap; //Es importante inicializar el campo a nulo elem.ap.sig=NULL; MPI_Send(elem.mensaje, STRUCTSIZE, MPI_CHAR, destino, etiqueta, MPI_COMM_WORLD); // Se elimina el nodo de la lista lista=lista->sig; free(ap); } return lista; } /***** Él(los) proceso(s) receptor(es) reconstruye(n) el TDA que les es enviado *****/ nodo *Recive_TDA(nodo *lista) { int num_elem=0, i=0, longitud=0; e_TDA elem; nodo *ap=NULL; /*** Se recibe el numero de elementos a recibir ***/ MPI_Recv(&num_elem, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); printf("El mensaje recibido es: %d \n", num_elem); for(i=0; i<num_elem; i++) { ap=(nodo *)malloc(sizeof(nodo)); if(ap!=NULL) { MPI_Recv(elem.mensaje, STRUCTSIZE, MPI_CHAR, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); *ap=elem.ap; lista=inserta_nodo(lista, ap); } else perror("Memoria Insuficiente..."); } return lista; }

Lo único que hay que considerar en esta versión es cuando se vallan a migrar los nodos del TDA lista se deberá asignar el valor NULL al apuntador al siguiente elemento, de la misma forma se

51

deberá hacer en una lista doblemente ligada. La razón es que en la practica después de migrar algunos nodos del TDA lista el proceso receptor se confunde al recibir valores que no tiene sentido para él.

52

4. RECONOCIMIENTO AUTOMÁTICO DEL TDA LISTA BALANCEABLE

53

4. RECONOCIMIENTO DEL TDA LISTA BALANCEABLE En esta sección se pretende crear un programa capaz de reconocer una estructura dentro de un archivo, y guardar dicha estructura en un archivo con extensión .h. Para el desarrollo de este programa hay que tener en consideración lo siguiente:

• El parámetro que se le pasará al programa. El usuario puede pasar el nombre de la estructura, o una redefinición de la misma.

• No se conoce el formato (aspecto) que tiene definido la estructura, por lo que hay que garantizar que la búsqueda no dependa del formato que tiene al ser declarada en el archivo.

• Una vez que la estructura se ha encontrado, es posible que dicha estructura contenga algunos otros tipos de datos derivados, es decir, otras estructuras. Por tal motivo se debe de realizar una verificación de cada uno de los campos de la estructura, de no reconocer algún campo como básico, deberá ser buscado recursivamente.

El modelo conceptual del programa esta representado por la siguiente figura:

54

4.1 Algoritmo

Establece_flujo(archivo, TDA) com flujo=abre_archivo(archivo) Cola_estrutras=Busca_Estructura(flujo, TDA) Crea def_TDA(Cola_Estructuras) term. Busca_Estructuras(flujo, TDA): Cola_estructuras com Mientras(salida=Falso) com bloque=Obten_bloque(flujo, TDA) sig_paso=Verifica_bloque(bloque) Caso sig_paso:

com Encontrada: Cola_estruturas=Registra_TDA(bloque, Cola_estructuras) salida=Termina. Redefinición_busca: Cola_estruturas=Registra_TDA(bloque, Cola_estructuras) salida=Sigue_buscando Redefinición_busca_original: Cola_estruturas=Registra_TDA(bloque, Cola_estructuras) TDA=nueva_TDA salida=Sigue_buscando term term Regresa Cola_estructuras term Registra_TDA(bloque, Cola_estructuras): Cola_estructuras com Haz campo=Verifica_Campos(bloque) Si(campo=No_Reconocido) entonces Cola_Estructuras=Busca_Estructuras(flujo, campo) Mientras(campo=No_Reconocido) Regresa Cola_estructuras term

55

4.2. Implementación

4.2.1. Obtención de los bloques El programa al comenzar a buscar la estructura, lo que hace es localizar bloques que pudiesen tratarse de la definición de la estructura buscada. Primero se establecen tres criterios para descartar un bloque. El primer criterio es la identificación de un carácter “#” el cual es utilizado en el lenguaje C para la identificación de las directivas de procesamiento; el segundo criterio es la existencia de los prototipos de función que están caracterizados por seguir el patrón <nombre_funcion>([argumentos]); si dicho patrón es identificado también es descartado; También se considera si se trata del cuerpo de una función, ya que generalmente una estructura no es declarada para una sola función. Las funciones tienen el siguiente patrón:

[Tipo del valor de retorno] <nombre_funcion>([argumentos]){[cuerpo función]} Además se utiliza el patrón que tiene la declaración de una estructura que es como sigue:

struct <nombre_estructura>{<campo;|campos>}[declaración_variable]; Donde:

campos=<campo; [campos]> campo=<tipo_dato> < variable>

La función “obten_bloque”, es la encargada de identificar estos patrones, ignora espacios en blanco, tabuladores y saltos de línea innecesarios y regresa el bloque que posiblemente sea el TDA buscado, el cual es una cadena de texto.

4.2.2. Verificación de los bloques El siguiente paso es verificar si realmente se trata de la estructura buscada. Supongamos que

tenemos la siguiente estructura con la siguiente redefinición. typedef struct registro nodo: struct registro { int edad; char nombre[]; char sexo; double saldo; nodo *sig; }; En este caso se pueden llegar a presentar las siguientes tres situaciones:

• Que el argumento pasado al programa sea el nombre de la estructura a buscar en este caso seria registro. Si no existe la redefinición, se ha encontrado la estructura (RE_END Registra Estructura y Termina).

• Que el argumento pasado al programa sea el nombre de la estructura como en el caso anterior, pero en esta ocasión se encuentre primero la redefinición. Si este el caso, se debe registrar la línea y seguir buscando (RL_SBE Registra Línea y Sigue Buscando Estructura.).

• Que el argumento pasado al programa sea el de la redefinición de la estructura, es decir, nodo. En tal caso se tendría que registrar la línea, obtener el nombre real de la estructura y buscar la nueva estructura (RL_BNE Registra Línea y Busca Nueva Estructura.).

56

4.2.3. Registro de la Estructura El registro de las redefiniciones y las estructuras se realiza en un TDA cola, con el objetivo de llevar un registro de los tokens buscados y la estructura guardada con la búsqueda de dicho término y evitar de esta forma la búsqueda de términos que ya han sido localizados, esto cuando se estén verificado los campos de la estructura encontrada. Después de encontrar la estructura, el paso a realizar es verificar cada uno de los campos, ya que la estructura puede contener tipos de datos derivados, que posteriormente sean necesarios. Si un campo no es reconocido, se llama a la función de búsqueda de estructura, con el nuevo dato a buscar. La función regresa la cola que contiene las definiciones de los tipos de datos buscados una vez que se ha encontrado la estructura y que sus campos han sido verificados.

4.2.4. Creación del archivo de Salida Finalmente la cola obtenida es registrada en el archivo “def_TDA.h”, para su posterior uso.

57

5. Migración de datos compartidos por hilos

58

5. MIGRACIÓN DE DATOS COMPARTIDOS POR HILOS

[S2001] El uso de hilos de ejecución involucra necesariamente la concurrencia entre ellos, es decir, que ambos existan realmente como programas que compiten por recursos de procesador, por ende cuando se hace uso de hilos de ejecución, se pueden presentar dos situaciones, la primera es que los hilos se ejecuten de manera independiente, la otra situación es que dichos hilos estén relacionados, esto implica que en ambos se haga uso de los mismos datos, ya sea leyendo y/o sobrescribiendo éstos. El principal problema se presenta cuando se hace uso de hilos de ejecución y estos interactúan entre ellos, ya que en dos procesos corriendo concurrentemente, se puede presentar que éstos requieran acceder al mismo tiempo la misma variable o el mismo recurso, lo cual traería consigo inconsistencia en los datos. Por ejemplo, imaginemos que los procesos son de reservación de boletos para aerolíneas. Sin un adecuado control, dos procesos pudieran requerir el leer y modificar la variable BoletosDisponibles al mismo tiempo. El proceso A leería la variable, y antes de poder modificarla, B también la leería. A guardaría entonces BoletosDisponibles-1, y B guardaría ese mismo valor. De esta manera, parecería que se hubiera vendido un solo boleto en lugar de dos.

De esta forma el decrementar la variable, en este caso se considera una sección crítica, dentro del código del programa. Por tal motivo hay que asegurar a los hilos de ejecución la exclusión mutua cuando se encuentre dentro de una sección crítica. Es decir, hay que asegurar que cuando un hilo entre a su sección crítica ningún otro hilo pueda acceder a su propia sección crítica, hasta que el proceso que estaba en su sección crítica la abandone.

El uso de la exclusión mutua como consecuencia que los hilos que entren en su sección critica, mantengan bloqueados al resto de los hilos que quieran acceder a su sección. Así, no es práctico incluir a todo un hilo en una sección crítica, ya que los demás hilos permanecerían bloqueados y el multihebrado perdería su concurrencia. Es importante el incluir sólo lo indispensable en la sección crítica, el resto del hilo deberá permanecer fuera de la sección.

En el caso de este proyecto la sección crítica se presenta durante el manejo de los datos y el momento de migrar la información. Los datos no deberán poder ser migrados a otro nodo del cluster si en el momento se están realizando operaciones sobre ellos y no se podrán agregar elementos nuevos mientras se estén realizando operaciones sobre los mismos. Por lo que las rutinas encargadas de realizar la migración (envió y recepción) deberán ser tomadas como una sección crítica, en cuanto al código que pretenda hacer uso de las rutinas de balance, la sección crítica estará determinada por las operaciones que sobre la lista se efectúen, es importante hacer notar que la lectura en los elementos de la lista también debe ser considerada una sección crítica ya que la lectura se puede ver afectada por el proceso de balanceo, ya sea por la inserción de elementos, lo cual no es tan grabe, como la eliminación de nodos del TDA lista, lo cual involucra el libramiento de memoria que conlleva a una perdida en los apuntadores, que acarrearía una terminación anormal del proceso.

5.1. Uso de Hilos en MPI

En esta parte del proyecto se pretende ver el funcionamiento de los hilos en MPI. El objetivo es crear dos hebras de un programa, mientras el núcleo del programa realiza sus tareas correspondientes sobre los datos, una de las hebras se encargará de migrara datos, la otra se encargará de verificar si se han recibido datos de otro nodo.

59

Se deben de tener en consideración dos situaciones: la primera es que se deben de garantizar la integridad de los datos, es decir se debe de evitar que un dato sea escrito mientras es leído; la otra situación es que los hilos deben de hacer el manejo de los datos de manera independiente al núcleo, se deberán crear “procedimientos” y no funciones, para que en el manejo de los datos no se tenga que terminar el hilo para que los datos sean modificados, es decir, se deberán pasar por referencia. En esta primera fase sobre el manejo de hilos se trata con un “problema de juguete” para ver la forma de proceder para el uso con el TDA lista.

5.1.1. hilos_1.c Para el desarrollo del proyecto en esta fase se plantea el siguiente problema: se tiene dos procesos corriendo uno de los procesos (Coordinador –proceso 0- ) inicializa un arreglo con números al azar, creara dos hilos, uno para la migración del arreglo y el otro que realizara la impresión de los datos en pantalla, el proceso receptor sólo esperará por lo elementos que le sean enviados. El objetivo de esta fase es ver el desempeño de los hilos en procesos que corren en paralelo así como garantizar la integridad de los datos. Las tareas del proceso cero se muestran en el siguiente código.

inicializa(arreglo); fprintf(stdout,"Proceso %d, desde %s\n", id, nombre); //Creación del hilo monitor encargado de migrar elementos del arreglo pthread_create(&hilo1, NULL, (void *)&monitor, (void *)1); //Creación del hilo que realiza el desplegado en pantalla pthread_create(&hilo2, NULL, (void *)&proceso, (void *)2); //Espera por la terminación de los hilos. pthread_join(hilo1, (void *)&vr); pthread_join(hilo2, (void *)&vr); printf("Los hilos del proceso %s han terminado...\n", id); Una vez creados lo hilos el proceso debe esperan la terminación de los mismos, de lo contrario no se observará resultado alguno del lado de este proceso. La tarea del monitor es realizar la petición del número de elementos que serán enviados al proceso 1. void monitor(void *datos) { int hilo=(int)datos; int num_nodos=0, i=0, etiqueta=0; if(id==0) { sleep(5); //Lapso de espera antes de comenzar el envío pthread_mutex_lock(&candado); //Cierra el candado para garantizar la integridad de los datos. fprintf(stdout,"Hola soy el hilo %d\n",hilo); fprintf(stdout,"del proceso %d\n",id); fprintf(stdout,"Desde el procesador %s\n",nombre); //Este ciclo valida que el usuario no exceda el límite del arreglo. do { printf("Dime cuantos nodos quieres migrar: "); scanf("%d", &num_nodos); }while(num_nodos<0 || num_nodos>20); printf("\n los elementos a migrar son %d\n",num_nodos); //Manda el mensaje con el número de elementos que enviará al proceso 1 MPI_Send(&num_nodos, 1, MPI_INT, 1, etiqueta, MPI_COMM_WORLD); //Envía cada uno de los elementos(envía los últimos). for(i=20-num_nodos; i< 20 ; i++)

60

{ MPI_Send(&arreglo[i], 1, MPI_INT, 1, etiqueta, MPI_COMM_WORLD); arreglo[i]=-1; //Borra el elemento del arreglo. } pthread_mutex_unlock(&candado); //Abre el candado. } pthread_exit((void *)hilo); }

El hilo espera un momento antes de comenzar el envío, cuando pretenda iniciar la transferencia se tendrá que garantizar la integridad de los datos, es por lo que se hace uso de los candados, los cuales no permiten que otro hilo y/o el proceso mismo tenga acceso a los datos una vez cerrado el candado, [S2001] el candado es una variable de tipo pthread_mutex_t, debe ser global, para su uso la instrucción que establece la sección de exclusión es pthread_mutex_lock, y recibe como parámetro la dirección de la variable usada para la exclusión. Una vez enviado el dato, debe ser eliminado, y una vez terminado el envío se debe liberar la sección. La función que libera la sección de la exclusión es pthread_mutex_unlock, el parámetro que recibe la misma es la dirección de la variable usada para la exclusión. También el proceso que haga uso de los datos debe contar con dichas instrucciones para que de la misma forma no sean enviados y eliminados mientras se están usando, ya que generaría valores incorrectos en la lectura y/o operación de los mismos. En este programa la operación de los datos es la impresión, en el listado de la función encargada del manejo de los datos de observa dicho procedimiento. void proceso(void *numero) { int i=0, count=0; int hilo=(int)numero; printf("\n Soy el hilo %d del procesador %s\n", hilo, nombre); while(count<5) { pthread_mutex_lock(&candado); //Se cierra el candado para garantizar la integridad. for(i=0; (arreglo[i]!=-1 && i<20); i++) printf("%3d",arreglo[i]); printf("\n"); pthread_mutex_unlock(&candado); //Se abre el candado sleep(2); count ++; } pthread_exit((void *)hilo); }

Es importante que la exclusión comience antes de la petición de los elementos a migrar, ya que posiblemente el proceso que haga uso de ello posiblemente se encuentre agregando o incluso eliminado datos, lo que acarrearía un problema si se quisieran enviar menos elementos de los que se tienen. Claro que en este programa no se da el caso como antes de ser enviados todos los datos se le manda un mensaje al proceso receptor indicándole la cantidad de elementos que se le enviran, el proceso receptor podría recibir basura o en el peor de los casos quedarse esperando por un elemento que no llegará.

En esta fase el proceso receptor no tiene mayor tarea que la de recibir los datos del proceso enviador en un arreglo que se encuentra inicialmente “vacío”, por lo que no requiere mayor explicación.

fprintf(stdout,"Proceso %d, desde %s\n", id, nombre); //Iniciación del arreglo for(i=0;i<20; i++) array[i]=-1;

61

//Recibe el mensaje con la cantidad de elementos que recibirá. MPI_Recv(&num_dat, 1, MPI_INT, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); //ciclo para la Recepción de los elementos del arreglo. for(i=0; i<num_dat; i++) MPI_Recv(&array[i], 1, MPI_INT, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); //Desplegado del arreglo en este proceso. for(i=0; (array[i]!=-1 && i<20); i++) printf("%3d",array[i]); El listado de este programa se encuentra en el Anexo C, el programa es el hilo_1.c

5.1.2. hilos_2.c Hasta ahora se ha visto la forma de hacer uso de los hilos en MPI, garantizando la exclusión mutua. Pero el programa anterior cuenta con muchas restricciones, una de ellas es que sólo hay comunicación entre dos procesos, si se corren más éstos no hacen nada. También se tiene la situación de espera de un mensaje. Uno de los objetivos del proyecto es crear una rutina que reciba una señal de otro proceso o un hilo del mismo programa, el cual se esta ejecutando en el mismo nodo de la máquina y su trabajo consiste en censar la carga del procesador y si este determina que el nodo del cluster esta sobrecargado, manda la señal para que este mande sus datos a otro nodo. Lo anterior implica que todos los procesos son susceptibles de enviar o recibir información, es así como todos los procesos deberían crear los hilos encargados del envío y la recepción de datos. La siguiente parte de código del listado “hilos_2.c”, realiza dicha tarea, con el problema del ejemplo anterior. Ahora se pretende hacer desarrollar el mismo problema pero de una forma más general. //Se inicializan los arreglos que posteriormente serán enviados inicializa(arreglo); //Se crean los hilos encargados del balance de carga. pthread_create(&envio, NULL, (void *)&Envia, (void *)1); pthread_create(&recepcion, NULL, (void *)&Recibe, (void *)salir); //Función que opera con los datos. proceso(); //Crea la señal para la terminación de los hilos MPI_Term_hilo(signal); //Se espera la terminación de los hilos para el balance de carga. //Y se guarda el valor de retorno. pthread_join(envio,(void *)&vr_env); pthread_join(recepcion, (void *)&vr_rec); fprintf(stdout, "Proceso %d, desde %s ---->", id, nombre); if(vr_env && vr_rec) fprintf(stdout, " El balance ha terminado sin problemas.\n"); Esta parte del problema no requiere mayor explicación. Lo interesante se presenta en las funciones de envío y recepción de datos. Hay que observar que los hilos que estén encargados del balance, no es posible determinar durante cuanto tiempo se necesite estén corriendo, quien determinará que el balance se ha terminado es el proceso principal, y el momento para finalizar el balance es la terminación de los cálculos. Así que los hilos tendrán que esperar por la señal que les dé la hebra principal. En el caso del envío no se sabe en que momento se deberán enviar datos, inclusive cuantos datos serán enviados, en este programa se hace uso de una espera de 0 a 10 segundo al azar para enviar de igual forma un numero de elementos a un destinatario en las mismas condiciones. Lo anterior con el fin de realizar el desarrollo de las rutinas de balance en condiciones extremas y las condiciones extremas en este caso es que la migración de datos se de cada cierto tiempo. A continuación se presenta

62

el cuerpo de la función void Envia_TDA(void *num) que sería el hilo encargado de enviar elementos del arreglo a otro nodo del cluster. /***** Función encargada del envío de elementos del arreglo, se hace al azar *****/ void Envia(void *num) { int destino=0, num_elem=0; int vr=(int)num; int tam=0, i=0; time_t semilla; //Iniciación de la semilla. srand((unsigned) semilla +id); while(MPI_Signal_term_hilo) { sleep(rand()%10); //Espera un tiempo al azar antes de realizar un envío valores_azar(proc,20,&destino,&num_elem); if(destino!=id && num_elem) { fprintf(stdout,"\n proceso %d -----> Hilo envía %d datos a %d...\n",id, num_elem, destino); //se cierra el candado para garantizar la integridad de los datos pthread_mutex_lock(&candado); //Se manda el mensaje que indica cuantos elementos se van a migrar. MPI_Send(&num_elem, 1, MPI_INT, destino, CANTIDAD, MPI_COMM_WORLD); //Ciclo encargado del envío de los elementos. //Se obtiene el tamaño actual del arreglo para enviar los últimos elementos. tam=calcula_tam(arreglo); for(i=tam-num_elem; i<tam; i++) { MPI_Send(&arreglo[i], 1, MPI_INT, destino, ELEMENTO, MPI_COMM_WORLD); arreglo[i]=-1; } //Se abre el candado para que el proceso que los opera pueda hacer uso de estos. pthread_mutex_unlock(&candado); } } pthread_exit((void *)&vr); } En este caso se ha decidido enviar los últimos elementos del arreglo lo cual es lo más conveniente para evitar que se estén realizando corrimientos. En la parte del envío de datos no se presenta mayor problema que garantizar la integridad de los datos, ya que si no se recibe la señal de enviar, no se realizará envío alguno, por lo que no hay la posibilidad de bloqueo por este lado. En el caso de la recepción de un dato o mejor dicho de un mensaje indicando cuantos elementos le serán enviados, la situación es muy diferente. En realidad el hilo encargado de la recepción de datos no sabe si le serán enviados datos, por lo que esperar por un mensaje que posiblemente no llegue provocaría un posible bloqueo de la aplicación paralela. La forma de evitar el bloqueo es hacer uso de las rutinas de MPI para las comunicaciones sin bloqueo. Es así como la forma de proceder del hilo receptor es verificar si se ha recibido un mensaje sin realmente recibirlo, con ciertas características, como lo son la fuente y la etiqueta del mensaje. Pero como no se sabe con certeza de quien esperar mensajes, pues sólo hay que tomar en cuenta la etiqueta del mensaje, por lo que se establecieron dos etiquetas para el envío y recepción de datos. Una vez comprobada la recepción del mensaje, es cuando se pasa realmente a recibirlo, en este mensaje se indicara cuantos elementos le serán enviados entonces se tendrá la certeza de cuantos elementos se recibirán y de quien.

63

Es importante considerar que se debe de tener espacio para recibir los elementos que le sean enviados y en caso de no tenerlo evitar que se bloque el proceso por no tener el mismo, aunque esto signifique perdida de datos. Como resultado se tiene la siguiente función de recepción de datos. void Recibe(void *salida) { int *termina=(int *)salida; int bandera=0, fuente=0, elem=0, i=0, basura=0, vr=0, tam=0; int count =0; MPI_Status estado; while(MPI_Signal_term_hilo) { //Se realiza una prueba, para ver si se han recibido mensajes MPI_Iprobe(MPI_ANY_SOURCE, CANTIDAD, MPI_COMM_WORLD, &bandera, &estado); if(bandera)//Verificación de recepción de mensajes. { //Obtención de la fuente que envío el mensaje. fuente=estado.MPI_SOURCE; //Recepción de la cantidad de elementos a recibir. MPI_Recv(&elem, 1, MPI_INT, fuente, CANTIDAD, MPI_COMM_WORLD, &estado); //Se cierra el candado para garantizar la integridad. pthread_mutex_lock(&candado); tam=calcula_tam(arreglo); //Obtención del numero de elementos en el arreglo. fprintf(stdout, "\n El proceso %d recibe señal de %d ---> datos a recibir %d\n",id, fuente, elem); for(i=0; i<elem; i++,tam++) { //Recepción de los elementos enviados. if(tam<100) MPI_Recv(&arreglo[tam], 1, MPI_INT, fuente, ELEMENTO, MPI_COMM_WORLD, &estado); //Esto garantiza que no se sobrepase del tamaño del arreglo, aunque provoca perdida de datos. else MPI_Recv(&basura, 1, MPI_INT, fuente, ELEMENTO, MPI_COMM_WORLD, &estado); } //Se abre el candado nuevamente. pthread_mutex_unlock(&candado); } } pthread_exit((void *)&vr); } Se establecieron dos etiquetas, CANTIDAD la cual indica que el mensaje recibido nos dice la cantidad de elementos que debemos esperar y ELEMENTO el cual indica que es un dato. En este programa el proceso realiza la impresión del arreglo cada cierto tiempo en archivo llamado como el nodo del cluster donde esta activo este proceso y el número de proceso que corresponde. El listado de este programa se encuentra en el Anexo C.

5.2. Sincronización para la lista balanceable

Hasta ahora se ha logrado que dos hilos de un proceso trabajen sin problemas, ya que no requieren mayor sincronización que la que proporciona la exclusión mutua, para el manejo de los datos. En la recepción de datos, la rutina de recepción realiza una verificación para ver si han llegado

64

mensajes, si se han recibido pues comienza su trabajo, pero, ¿Qué pasa con la rutina de envió?, pues hasta el momento ella misma decide cuando y cuanto enviar, cuando en realidad este debe de estar en espera de la señal que le indique comenzar a trabajar. Así esta debe de responder a otra rutina que le indique empezar a trabajar. Se contempla que la rutina encargada de dar esta señal es otro el cual se encarga de monitorear la carga del procesador y si se encuentra muy cargado comenzar a migrara la información. Pues bien, para llevar a cabo la sincronización entre el hilo que monitorea la carga del procesador y el hilo encargado del envió de los datos se deberá hacer uso de los semáforos. [S2001] Los semáforos son un mecanismo de sincronización entre procesos e hilos de ejecución. Los semáforos son variables enteras que no aceptan valores negativos. Si el semáforo tiene una valor de cero indica que no se puede continuar, es decir esta en rojo, si el valor es mayor que cero indica que se puede seguir, es decir, esta en verde. Para que los hilos hagan uso de semáforos para poder sincronizarse, existen dos operaciones básicas en los semáforos, las cuales son la espera por el verde (sem_wait) y da el verde (sem_post). Cuando un hilo da luz verde al semáforo, es decir, realizar sem_post a una variable de tipo semáforo, lo que se hace es incrementar en uno a la variable, de tal forma que si algún otro hilo esperaba por el mismo semáforo, es decir, esta bloqueado en una llamada a sem_wait, éste podrá continuar su ejecución ya que el semáforo es mayor que cero, pero una vez que se deja de esperar por la variable semáforo, la llamada a sem_wait lo que hará es decrementar el valor en uno de dicho semáforo. Un valor de uno dejara continuar a un proceso que espera por el semáforo, este lo decrementará y si en el momento otro hilo espera por el mismo semáforo éste no podrá continuar, ya que el semáforo sólo le dio luz verde a uno. Es así como el valor que tenga la variable de tipo semáforo le dará luz verde a la cantidad de esperas por el verde que indica el valor de la variable. Es así como la rutina encargada del envió de datos deberá realizar la espera por la señal que le indique que comience a hacer su trabajo, esta señal es la luz verde de un semáforo. El hilo encargado del monitoreo deberá ser el encargado de dar dicha señal, por tanto en el monitor se deberá hacer una llamada sem_post para dar luz verde y comenzar el envió de datos.

5.2.1. hilos_3.c En dos casos anteriores se manejaba un arreglo global, lo cual simplificaba en gran medida las cosas ya que los hilos deben tener acceso a éste, en el caso anterior además cada uno de los hilos encargados del balance hace uso de algunos parámetros como lo son, la señal de terminación, y en el caso del envío, el destino y el número de elementos para realizar un envío. En el programa anterior, algunos de estos parámetros son declarados dentro de la función misma, lo cual no es lo que se busca, se busca que la función de envío responda a los parámetros que le sea pasados de algún otro hilo que se encuentre permanentemente censando la carga del nodo del cluster. Para que los parámetros que necesitan los hilos sean pasazos sin que el usuario tenga que estar declarando cada uno de ellos y además no tengan que ser globales, ya que una buena practica de programación es hacer el menor uso de variables globales, se crea una estructura que contenga cada uno de los campos, para que el usuario al hacer usos de las rutinas de balance sólo tenga que declarar una variable de este tipo y pasar por referencia dicha variable a las rutinas de balanceo. La estructura creada para dicho propósito es como sigue:

typedef struct Parametros_Balance { nodo **TDA; int MPI_DEST; int MPI_ELEM;

65

int MPI_SIGNAL_TERM; }MPI_Balance;

Como tanto la rutina de envío como la de recepción hacen uso de la lista creada dinámicamente, es necesario pasarle la lista, por lo que el campo nodo **TDA es utilizado para hacer referencia a la dirección del apuntador a la cabeza de la lista y de esta forma pueda ser modificada la lista. [AJ1994] Por ejemplo, la siguiente declaración int *ptr;

Declara un apuntador, llamado ptr, que puede apuntar a una variable de tipo int. Posteriormente se tendrá que inicializar ese apuntador haciendo uso del carácter de in dirección & para hacer que el apuntador apunte a una variable específica del tipo correspondiente, Suponiendo que la variable x ha sido declarada como variable de tipo int, el enunciado de inicialización sería como sigue:

ptr = &x; Es así como se le asigna la dirección de x a ptr y hace que ptr apunte a x. Una vez hecho esto se

tiene dos formas de modificar el valor de la variable x=12; *ptr=12; Ambos enunciados asignaran el valor de 12 a la variable, Usando el carácter de in dirección en

el apuntador se logra el mismo efecto sobre la variable, de esta forma se pasan los argumentos a las funciones para que estas puedan modificar el parámetro que les es pasado.

Pero, en el caso de las listas ligadas dinámicamente lo que se declara inicialmente es un apuntador, que no apunta a la dirección de memoria de una variable ya que no es declarada ninguna instancia de nuestro tipo de dato. El apuntador es inicializado con la memoria asignada dinámicamente. Ahora como el apuntador en sí mismo es una variable numérica, es guardada en una dirección en particular de la memoria. Por lo tanto, se puede crear un apuntador a un apuntador, la cual es una variable cuyo valor es la dirección de un apuntador. La manera de hacer esto es:

int x=12; int *ptr=&x; int **ptr_a_ptr=&ptr ; Para el caso de las listas ligadas dinámicamente lo

que se necesita es hacer uso de un doble apuntador y de esta forma poder modificar la lista. La figura “Ilustración de un apuntador a un apuntador” de la pagina anterior ilustra de mejor manera la forma de operar de un doble apuntador.

Así para que le sea pasada la lista ligada dinámicamente a los hilos encargados del balaceo y que estos puedan modificarla se tendrá que iniciar este doble apuntador a la dirección de la cabeza de la lista de la siguiente forma:

nodo *lista: MPI_Balance elem;

66

elem.TDA=&lista; El resto de los campos de la estructura MPI_Balance no requiere mayor explicación ya que

cuentan con un nombre muy descriptivo. El envío de los nodos del TDA lista se hará por medio de una estructura auxiliar (unión) como

se realizo en la versión 3.2 (uniones_b.c) de la sección “Envío y Recepción de un nodo de un TDA lista” la estructura es como sigue:

typedef union Nodos_TDA e_TDA; union Nodos_TDA { nodo ap; char mensaje[STRUCTSIZE]; };

Ya se observo la forma de hacer uso de la misma en la sección antes mencionada. Ahora no se pretende que el usuario de las rutinas tenga que estar realizando la creación de los hilos encargados del balance y ni que tenga que estar codificando las instrucciones para la finalización de las mismas, el objetivo principal es que el usuario realice una llamada a las rutinas de balance de carga y una llamada a la finalización de las mismas. Para eso se crean las rutinas MPI_Init_balance y MPI_Finaliza_balance las cuales serán las encargadas de iniciar la estructura con los parámetros necesarios para los hilos, crear los hilos y esperar por la terminación de los mismos respectivamente de tal forma que el usuario de las rutinas las invoque como si realizará una invocación a la función printf por poner un ejemplo. Las rutinas de iniciación y de finalización son las siguientes:

void MPI_Init_balance(MPI_Balance *par_bal, nodo **lista) { //Se inicia el semáforo el cual indicará el momento para comenzar el balance sem_init(&signal,0,0); //Iniciación de la estructura //Se indica la dirección de los datos que podrían ser enviados a otro proceso par_bal->TDA=lista; //Se inicia el parámetro destino, con un valor igual al proceso par_bal->MPI_DEST=id; //Se inicia el número de elementos a enviar par_bal->MPI_ELEM=0; //Se inicia la señal que indica a los hilos que terminen par_bal->MPI_SIGNAL_TERM=0; //Iniciación de los hilos para el balance pthread_create(&envio, NULL, (void *)&Envia_TDA, (void *)par_bal); pthread_create(&recepcion, NULL, (void *)&Recibe_TDA, (void *)par_bal); //Esta Función no va a ser necesaria para el uso en general //Este hilo es el encargado de determinar a quien, cuantos y en que momento le serán enviados datos pthread_create(&monitor, NULL, (void *)&Monitor,(void *)par_bal); } void MPI_Finaliza_balance(MPI_Balance *par_bal) { int vr_env=0, vr_rec=0, vr_mon=0; //Se manda la señal a los hilos para que terminen su trabajo par_bal->MPI_SIGNAL_TERM=1; //Se espera la terminación de los hilos que realizan el balance de carga.

67

//Y se guarda el valor de retorno. pthread_join(monitor,(void *)&vr_mon); pthread_join(envio,(void *)&vr_env); pthread_join(recepcion, (void *)&vr_rec); if(vr_env || vr_rec) fprintf(stdout, "Proceso %d, desde %s ----> si hubo balance \n", id, nombre); else fprintf(stdout, "Proceso %d, desde %s ----> no hubo balance \n", id, nombre); }

Esta rutinas no requieren mayor explicación más que la línea 3 del la rutina de iniciación del balance, Este enunciado es la inicialización de un variable de tipo sem_t, la cual es un semáforo usada para la coordinación de la rutina de envío de datos (Envia_TDA) y la rutina encargada del monitoreo de la carga del procesador. El monitor deberá de dar un sem_post para darle luz verde a la rutina de envío la cual realizará un sem_trywait la cual es una espera del semáforo, pero sin bloqueo para evitar una señal que posiblemente no llegue y entrar nuevamente al mismo problema que se tiene al recibir datos. Las rutinas que son invocadas en la iniciación son las siguientes: void Envia_TDA(void *datos) { int i=0, vr=0; nodo *ap=NULL, *aux=NULL, *aux_2=NULL; e_TDA elem; MPI_Balance *param_bal=(MPI_Balance *)datos; while(!param_bal->MPI_SIGNAL_TERM) { if(sem_trywait(&signal)==0) { //Se realiza una validación para no enviarse a sí mismo los datos y/o evitar enviar un mensaje innecesario if(param_bal->MPI_DEST!=id && param_bal->MPI_ELEM) {//Se indica al proceso principal que si hubo balance vr=1; fprintf(stdout,"\n proceso %d -----> Hilo envía %d datos a %d...\n",id, param_bal->MPI_ELEM, param_bal->MPI_DEST); //se cierra el candado para garantizar la integridad de los datos Cierra_candados(); //Se manda el mensaje que indica los elementos a migrar. MPI_Send(&param_bal->MPI_ELEM, 1, MPI_INT, param_bal->MPI_DEST, CANTIDAD, MPI_COMM_WORLD); for(i=0; i<param_bal->MPI_ELEM; i++) { //Se obtiene el ultimo elemento de la lista para su envío. ap=aux=*param_bal->TDA; while(ap->sig!=NULL) ap=ap->sig; //Se realiza una copia del nodo en el elemento de la unión para poder ser transferido. elem.ap=*ap; //Es importante inicializar el campo a nullo elem.ap.sig=NULL; //Se envía el nodo MPI_Send(elem.mensaje, STRUCTSIZE, MPI_CHAR, param_bal->MPI_DEST, ELEMENTO, MPI_COMM_WORLD); //Se inicializa el campo del anterior a NULL while(aux->sig!=ap) aux=aux->sig; // Se elimina el nodo de la lista

68

if(aux!=ap) aux->sig=NULL; else param_bal->TDA=&aux_2; free((void *)ap); } Abre_candados(); } } } pthread_exit((void *)&vr); } /***** Él(los) proceso(s) receptor(es) reconstruye(n) el TDA que les es enviado *****/ void Recibe_TDA(void *datos) { int num_elem=0, i=0, fuente=0, vr=0, bandera=0; e_TDA elem; nodo *ap=NULL; MPI_Balance *param_bal=(MPI_Balance *)datos; MPI_Status estado; do { //Se realiza una prueba, para ver si se han recibido mensajes MPI_Iprobe(MPI_ANY_SOURCE, CANTIDAD, MPI_COMM_WORLD, &bandera, &estado); if(bandera)//Verificación de recepción de mensajes. {//Se indica al proceso principal que si hubo balance vr=1; //Obtención de la fuente que envío el mensaje. fuente=estado.MPI_SOURCE; //Recepción de la cantidad de elementos a recibir. MPI_Recv(&num_elem, 1, MPI_INT, fuente, CANTIDAD, MPI_COMM_WORLD, &estado); fprintf(stdout, "\n El proceso %d recibe señal de %d ---> datos a recibir %d\n",id, fuente, num_elem); //Se cierra el candado para garantizar la integridad. Cierra_candados(); for(i=0; i<num_elem; i++) { ap=(nodo *)malloc(sizeof(nodo)); if(ap!=NULL) { MPI_Recv(elem.mensaje, STRUCTSIZE, MPI_CHAR, fuente, ELEMENTO, MPI_COMM_WORLD, &estado); *ap=elem.ap; /***********Aquí el usuario pondrá su función para la inserción de la lista *****/ inserta_nodo(param_bal->TDA, ap); } else perror("Error... Memoria Insuficiente, imposible recibir los elementos..."); } //Se habré el candado nuevamente. Abre_candados(); } }while(!param_bal->MPI_SIGNAL_TERM); pthread_exit((void *)&vr);

69

} El código de dichas rutinas funciona de la misma manera que en el programa de la primera fase (hilos_2.c) pero ahora sobre el tipo de dato TDA lista. Se le incorporaron las rutinas: /***** Función que cierra los candados para garantizar la integridad de los datos. *****/ void Cierra_candados(void) { pthread_mutex_lock(&candado); pthread_mutex_lock(&candado_estructura); } /***** Función que libera los candados *****/ void Abre_candados(void) { pthread_mutex_unlock(&candado); pthread_mutex_unlock(&candado_estructura); }

Las cuales garantizan la integridad de los datos, esta mismas deberán ser invocadas en el código del usuario en el momento de realizar las operaciones sobre sus datos ya que no se deberá poder recibir y/o enviar éstos mientras se este operando sobre los mismos.

En la rutina de iniciación de balance se crea un hilo más, el cual funge como el monitor del sistema, no es objetivo de este proyecto desarrollar dicha rutina, pero se crea una que deberá actuar de manera muy similar a esta, al igual que en el caso anterior se toman las condiciones extremas, en las cuales se envían datos cada cierto tempo. El tiempo y los elementos a migrar son al azar así como el destinatario. Una vez determinados estos elementos los cuales son parte de una variable de tipo MPI_Balance, la cual le es pasada por referencia, se dará la señal para comenzar el envío de datos.

void Monitor(void *datos) { MPI_Balance *par_bal=(MPI_Balance *)datos; time_t tiempo; int count=0, long_lista=0, vr=0; //Se inicializa la semilla para realizar las acciones al azar. srand((unsigned)time(&tiempo)+id); //Verifica que el proceso no haya indicado el final de las operaciones. while(!par_bal->MPI_SIGNAL_TERM)

{ Cierra_candados(); //Determina el destino al azar. par_bal->MPI_DEST=rand()%proc; //Se obtiene el tamaño de la lista para, ver cuantos elementos se pueden enviar long_lista=longitud_TDA(*par_bal->TDA); par_bal->MPI_ELEM=rand()%(long_lista/2); //Da la señal para que el proceso enviador comience el envío de los datos sem_post(&signal); Abre_candados(); //Espera máximo 10 segundos antes de realizar otro envío sleep((rand()%5)+5); } pthread_exit((void *)&vr); }

70

Haciendo uso de estas rutinas de balance el código de la función principal quedaría como el listado “hilos_3.c” version1.

main(int argc, char *argv[]) { nodo *lista; //Estructura que contiene los elementos necesarios para llevar a cabo el balance de carga MPI_Balance elem_bal; //Rutinas de iniciación para MPI. MPI_Init (&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &id); MPI_Comm_size(MPI_COMM_WORLD, &proc); MPI_Get_processor_name(nombre, &long_nom); crea_lista(&lista); lista=obten_datos("/tmp/regis.txt"); //Creación del TDA a partir de un archivo. //Se inicializa el balance de carga MPI_Init_balance(&elem_bal,&lista); proceso(&elem_bal); //Se termina el balance de carga MPI_Finaliza_balance(&elem_bal); MPI_Finalize(); return 0; }

En este programa la rutina de proceso() lo único que realiza es la impresión de los datos cada cierto tiempo durante 30 ocasiones, para ver los listados completos de esta primera prueba ir al Anexo C 1ª versión .

5.2.2. hilo_3.c 2ª versión En esta fase del proyecto el problema a vencer son las líneas que hacen referencia al campo de la estructura, el cual es un apuntador al siguiente elemento y no necesariamente se llama de la forma que se llamo en el desarrollo del proyecto. Para esto hay que observar que las rutinas Envia_TDA y Recibe_TDA hacen uso dos rutinas para el manejo de la lista una es la “inserción de nodos” y la “eliminación de nodos” y una más cuyo objetivo es inicializar el campo al siguiente elemento a NULL. Estas tres funciones son iguales para cualquier TDA lista que sea manejado por las rutinas de balance. Para solucionar dicho problema se le agregan algunas rutinas al programa “scan.c” de la sección “Reconocimiento automático del TDA lista balanceable”, que nos auxiliaran a conocer el nombre del campo el cual es un apuntador al siguiente elemento de la lista. Las funciones implementadas en el programa “scan.c” son: /***** Esta función obtiene el nombre del campo, el cual es un apuntador a un elemento del mismo tipo, necesario para la creación del TDA lista *****/ void busca_ptr_sig(char *struc, char *ptr_sig) { char *aux, *aux2; aux=strtok(struc,";"); while(aux!=NULL) {

71

aux=strtok(NULL,";"); if(existe_asterisco(aux)) { aux2=strtok(aux,"*"); aux2=strtok(NULL,"*"); strcpy(ptr_sig,aux2); break; } } } /***** Verifica que en la línea se encuentre el * el cual es el indicador del campo que apunta al siguiente elemento en una lista. *****/ int existe_asterisco(char *ptr_sig) { int i=0, vr=0; while(ptr_sig[i]!='\0') if(ptr_sig[i++]=='*') { vr=1; break; } return vr; } Una vez encontrado el campo, a partir de un archivo llamado “MPI_lista.orig” generar el archivo “MPI_lista.c” el cual contiene las funciones mencionadas anteriormente. El listado completo del archivo “scan.c” se encuentra en el Anexo B “listados Segunda versión.” El contenido del archivo “MPI_lista.orig” es como sigue: /***** Archivo obtenido de la búsqueda realizada para la obtención de la estructura necesaria para la creación del TDA

lista *****/ #include "protos.h" /***** Inserción de nodo en la lista *****/ void inserta_nodo_lista_MPI(nodo **lista, nodo *elem) { nodo *ap=*lista; if(es_vacia(ap)) *lista=elem; else { while(ap->@!=NULL) ap=ap->@; ap->@=elem; } } /***** Elimina un nodo de la lista *****/ void elimina_nodo_lista_MPI(nodo **lista, nodo *elem) { nodo *ap=*lista, *aux=NULL;

72

if(!es_vacia(*lista)) { if(ap=elem) { aux=*lista; *lista=aux->@; free(aux); } else while(ap->@!=NULL) { if(ap->@==elem->@) { aux=ap->@; ap->sig=aux->@; free(aux); break; } ap=ap->@; } } } /***** Inicia el apuntador al siguiente elemento de la lista con NULL *****/ void Asigna_null_asig(nodo *ap) { ap->@=NULL; } El programa “scan” leerá este archivo y cuando encuentre el carácter @ lo sustituirá por el nombre del campo al siguiente elemento de la lista y el resultado lo guardará en el archivo “MPI_lista.c” el cual si existe será destruido. En el caso de la estructura utilizada en este caso el resultado es el siguiente: /***** Archivo obtenido de la búsqueda realizada para la obtención de la estructura necesaria para la creación del TDA

lista *****/ #include "protos.h" /***** Inserción de nodo en la lista *****/ void inserta_nodo_lista_MPI(nodo **lista, nodo *elem) { nodo *ap=*lista; if(es_vacia(ap)) *lista=elem; else { while(ap->sig!=NULL) ap=ap->sig; ap->sig=elem; } } /***** Elimina un nodo de la lista *****/ void elimina_nodo_lista_MPI(nodo **lista, nodo *elem) { nodo *ap=*lista, *aux=NULL;

73

if(!es_vacia(*lista)) { if(ap=elem) { aux=*lista; *lista=aux->sig; free(aux); } else while(ap->sig!=NULL) { if(ap->sig==elem->sig) { aux=ap->sig; ap->sig=aux->sig; free(aux); break; } ap=ap->sig; } } } /***** Inicia el apuntador al siguiente elemento de la lista con NULL *****/ void Asigna_null_asig(nodo *ap) { ap->sig=NULL; } Haciendo uso de esta herramienta, nuestras rutinas Envia_TDA y Recibe_TDA quedan de la siguiente forma, también es corregido el proceso de enviar los últimos nodos de la lista, ahora se envían los primeros: /***** En este primer acercamiento se envía campo por campo ****/ void Envia_TDA(void *datos) { int i=0, vr=0; nodo *ap=NULL, *aux=NULL, *aux_2=NULL; e_TDA elem; MPI_Balance *param_bal=(MPI_Balance *)datos; int longitud_lista=0; while(!param_bal->MPI_SIGNAL_TERM) { if(sem_trywait(&signal)==0) { //Se realiza una validación para no enviarse a sí mismo los datos y/o evitar enviar un mensaje innecesario if(param_bal->MPI_DEST!=id && param_bal->MPI_ELEM) {//Se indica al proceso principal que si hubo balance vr=1; fprintf(stdout,"\n proceso %d -----> Hilo envía %d datos a %d...\n",id, param_bal->MPI_ELEM, param_bal->MPI_DEST); //se cierra el candado para garantizar la integridad de los datos Cierra_candados(); //Se manda el mensaje que indica los elementos a migrar. MPI_Send(&param_bal->MPI_ELEM, 1, MPI_INT, param_bal->MPI_DEST, CANTIDAD, MPI_COMM_WORLD); for(i=0; i<param_bal->MPI_ELEM; i++)

74

{ ap=*param_bal->TDA; //Se realiza una copia del nodo en el elemento de la unión para poder ser transferido. elem.ap=*ap; //Es importante inicializar el campo a nullo Asigna_null_asig(&elem.ap); //Se envía el nodo MPI_Send(elem.mensaje, STRUCTSIZE, MPI_CHAR, param_bal->MPI_DEST, ELEMENTO, MPI_COMM_WORLD); //Se elimina el nodo de la lista elimina_nodo_lista_MPI(param_bal->TDA,ap->sig); } Abre_candados(); } } } pthread_exit((void *)&vr); } /***** Él(los) proceso(s) receptor(es) reconstruye(n) el TDA que les es enviado *****/ void Recibe_TDA(void *datos) { int num_elem=0, i=0, fuente=0, vr=0, bandera=0; e_TDA elem; nodo *ap=NULL; MPI_Balance *param_bal=(MPI_Balance *)datos; MPI_Status estado; do { //Se realiza una prueba, para ver si se han recibido mensajes MPI_Iprobe(MPI_ANY_SOURCE, CANTIDAD, MPI_COMM_WORLD, &bandera, &estado); if(bandera)//Verificación de recepción de mensajes. {//Se indica al proceso principal que si hubo balance vr=1; //Obtención de la fuente que envío el mensaje. fuente=estado.MPI_SOURCE; //Recepción de la cantidad de elementos a recibir. MPI_Recv(&num_elem, 1, MPI_INT, fuente, CANTIDAD, MPI_COMM_WORLD, &estado); fprintf(stdout, "\n El proceso %d recibe señal de %d ---> datos a recibir %d\n",id, fuente, num_elem); //Se cierra el candado para garantizar la integridad. Cierra_candados(); for(i=0; i<num_elem; i++) { ap=(nodo *)malloc(sizeof(nodo)); if(ap!=NULL) { MPI_Recv(elem.mensaje, STRUCTSIZE, MPI_CHAR, fuente, ELEMENTO, MPI_COMM_WORLD, &estado); *ap=elem.ap; inserta_nodo_lista_MPI(param_bal->TDA, ap); } else perror("Error... Memoria Insuficiente, imposible recibir los elementos..."); }

75

//Se abre el candado nuevamente. Abre_candados(); } }while(!param_bal->MPI_SIGNAL_TERM); pthread_exit((void *)&vr); }

5.3. Rutinas para el balance de carga (versión final)

Las rutinas encargadas del balance de carga hacen uso de los siguientes archivos: 1. scan.c: este es el código fuente encargado del reconocimiento automático para el balance de la

lista balanceable. 2. def_TDA.h (generado por el programa “scan”) 3. balance.c: archivo que contiene todas las rutinas de necesarias para el balance de carga. 4. MPI_lista.orig (archivo que contiene la estructura general de las funciones

inserta_nodo_lista_mpi(), elimina_nodo_lista_mpi() y Asiga_null_asig()) 5. MPI_lista.c (archivo generado a partir de “MPI_lista.orig” por el programa “scan”) 6. protos.h: este contiene la definición de las estructuras de datos y los prototipos utilizados pro las

rutinas de balance. Los listados de dichos archivos se pueden consultar en el Anexo D.

76

6. RESULTADOS

77

6. RESULTADOS

6.1. Desempeño del programa hilos_3.c 1ª versión

En esta versión se presento principalmente el siguiente problema, en una de las primeras versiones, una vez que era invocada la rutina MPI_Init_balance, al invocar a la rutina proceso() pasándole como argumento la dirección de la lista de la siguiente forma: nodo *lista; //Declaración de la lista. proceso(lista); //Invocación del proceso que maneja las operaciones sobre la lista. Se presentaba lo siguiente: si el hilo tenía que mandar ciertos elementos, que inicialmente eran tomados de la cabeza de la lista los elementos no se podían eliminar y causaban conflictos que eran arrastrados, esto se debe a que los hilos operan con un doble apuntador modificando la cabeza de la lista, por lo que la cabeza de la lista dejaba de ser la que se le pasaba al proceso, en un principio se decidió enviar a los últimos elementos. Pero esto no soluciona por completo el error, ya que ¿Qué pasa si se envía la lista por completo? pues la respuesta es sencilla, la lista no era eliminada y provocaba que los apuntadores se perdieran, marcando un numero de elementos inexistentes. Es como se toma la determinación de pararle la estructura completa a MPI_balance la cual contiene la cabeza de la lista que es manejada, aunque en realidad esto no es necesario bastaría con enviar el campo TDA de dicha estructura de la siguiente forma:

nodo *lista; //Declaración de la lista. MPI_Balance elem; MPI_Init_balance(&elem, &lista);

proceso(*elem.TDA); //Invocación del proceso que maneja las operaciones sobre la lista. Otro problema que se presenta es que en las rutinas Envia_TDA y Recibe_TDA existen instrucciones que hace referencia la campo de la estructura que apunta al siguiente elemento de la lista ligada, lo cual es un problema ya que se pretende que la rutina sea lo más general posible. Vea las líneas que se muestran a continuación y que son parte de la rutina de envío.

//Se obtiene el último elemento de la lista para su envío. ap=aux=*param_bal->TDA; while(ap->sig!=NULL) ap=ap->sig;

Esto provocaría que el usuario de la rutina tenga que modificar la misma para poder hacer uso del balance.

6.2. Desempeño del programa hilos_3.c 2ª versión

Esta versión no tiene mayores problemas que la saturación del canal de recepción de mensajes, ya que es probado en condiciones extremas, se puede presentar que algún nodo del cluster reciba varios mensajes de diferentes nodos, lo que provoca una saturación del buffer de recepción lo cual es un error y consecuentemente que el programa sea abortado por el sistema operativo. Se realizaron pruebas haciendo uso del envío sin bloqueo así como el envío sincrono pero el resultado es el mismo.

78

7. CONCLUSIONES Y PERSPECTIVAS

79

7. CONCLUSIONES Y PERSPECTIVAS En este proyecto se crearon unas rutinas para el balance de carga capaces de enviar y/o recibir registros (estructuras de datos del TDA lista), garantizando la integridad de los mismos. Estas rutinas sólo se encargan del envió y/o recepción de los registros, para realizar su trabajo requieren de un monitor que se encargué del momento, la cantidad de registros, además del origen y el destino de dichos registros, todo mediante macros definidas para el funcionamiento de dichas rutinas. El usuario de las rutinas para el Balance de Carga deberá hacer uso de unas rutinas creadas para garantizar la integridad de sus datos, estas rutinas son: Cierra_candados(), Abre_candados(), estas rutinas deben de ser usadas en secciones criticas y es responsabilidad del usuario determinar cuales son sus secciones criticas y de esa forma proteger sus datos ante una posible migración de los mismos.

La metodología empleada en este proyecto nos llevó a tomar diferentes opciones de cómo debían de ser migrados los nodos de un TDA, como parte del mismo se realizo un analizador léxico, capaz de identificar un registro. La función de este analizador es: una vez identificado el registro, éste deberá crear un alias del mismo registro, con el fin de que todas las rutinas diseñadas sean capaces de reconocer el tipo de dato que están manejando. Este analizador léxico fue creado a partir de la necesidad de conocer que tipo de dato se va a enviar de un nodo del cluster a otro.

Las rutinas de balance de carga fueron diseñadas a partir de pruebas realizadas a los diferentes modos de enviar un nodo de un TDA lista, cada una de las formas en que se puede realizar el envío fue implementada y fueron analizados los pros y los contras, sobre la base de estos se llegó a una versión final. Tomando además las siguientes consideraciones: Las rutinas generadas no debían involucrar la modificación de las mismas por las personas que hicieran uso de estas; deberían de ser capaces de soportar cualquier tipo de datos definidos por el usuario de las mismas; deberían de garantizar la integridad de los datos al migrar los nodos del TDA, es decir, deberían de evitar la perdida de los datos y/o incluso la duplicidad de los mismos; y sobre todo ser fáciles de utilizar, tan fáciles como llegar a realizar las llamadas de las mismas.

Estas rutinas de balance de carga, para su buen funcionamiento hacen uso de un monitor capaz de realizar una auditoria de los nodos del cluster, en cuanto a carga de procesamiento y a memoria, dicho monitor debe ser el encargado de determinar en que momento, cuantos nodos del TDA serán migrados y el nodo del cluster origen y el destino, además para garantizar que no halla perdida de datos, este monitor es el que debe determinar en que momento se han de terminar cada uno de los procesos corriendo. No es uno de los objetivos de este proyecto la creación de dicho monitor, pero, se creó una rutina que realiza dichas funciones sin realizar la auditoria de cada uno de los nodos del cluster, el momento, la cantidad de nodos del TDA y el nodo del cluster origen y destino son determinados al azar lo que lleva a un extremo la migración de datos, presentándose la saturación de los búferes de recepción si en un momento dado se migran datos de múltiples nodos del cluster aun un sólo nodo del mismo.

Las rutinas del balance de carga desarrolladas en este proyecto se encuentra dentro de un margen aceptable de operatividad, son confiables, no se presentan perdidas de datos en cuanto al envío y/o recepción de información, si no hay saturación del canal las comunicaciones no representan un tiempo muerto de procesamiento. Por otro lado en cuanto a los resultados no satisfactorios obtenidos con las pruebas realizadas, la saturación del canal se da en un cluster no dedicado, es un cluster que además de correr las aplicaciones en paralelo cada uno de sus nodos es utilizado como estación de trabajo, con toda la carga en comunicaciones que esto representa, como lo es el acceso a Internet, la

80

exportación de sesiones gráficas, etc. Así como los servicios utilizados por el sistema como lo son NIS, NFS entre otros y la inexistente administración de tareas del cluster; la saturación resulta obvia. Las rutinas representan una buena opción en el balance de carga dinámico, resultan lo más general posible para la migración de datos y son de fácil preparación para la utilización en proyectos. Tal vez no representen una buena opción en cuanto a la administración de clusters, pero si representan una buena opción en cuanto al desempeño de las aplicaciones paralelas que hagan uso de éstas. Además probablemente sea posible hacerlas totalmente genéricas con el uso de apuntadores a función, o con la programación orientada a objetos. Pueden hacerse mejoras de las mismas con facilidad.

81

8. BIBLIOGRAFÍA

82

8. BIBLIOGRAFIA & [MJ1995] H. M. Deitel, P. J. Deitel “Como programar en C/C++”. Segunda Edición. Editorial

Pearson Educación. Págs. 259-285, 317-346, 395-402, 467-478. Año 1995

& [AJ1994] Peter Aitken, Bradley Jones. “Aprendiendo C en 21 días” Editorial Pearson Educación. Págs. 189-206, 267-271, 272-276, 545-550, Año 1994

& [S2001] William Stallings. “Sistemas Operativos” 4a edición. Editorial Prentice Hall. Págs. 150-161, 163-165, 191-220, 231-235. Año 2001

& [1] Manuales en línea de Linux (man).

& [2] Apuntes de “Programación Paralela”

& [3] http://www-unix.mcs.anl.gov/mpi/.

& [4] http://www.mpi-forum.org/.

& [5] http://www.ldc.usb.ve/~ibanez/docencia/MPI/

83

9. ANEXOS

84

9. ANEXOS

9.1. Anexo A (Códigos Fuentes para la migración de datos)

Listado “protos.h” En este archivo se encuentran todos los prototipos así como la definición de las estructuras usadas para el desarrollo del la primera fase del proyecto. #include <stdlib.h> #include <stdio.h> #include <math.h> #include "mpi.h" #define COORDINADOR 0 /***** Variables globales utilizadas para la identificación de los procesos. *****/ int id, proc, long_nom; char nombre[50]; MPI_Status estado; typedef struct Registro nodo; struct Registro { char nombre[40]; unsigned matricula; int edad; char sexo; nodo *sig; }; /***** Prototipos para el manejo del TDA lista *****/ nodo *crea_lista(void); int es_vacia(nodo *lista); nodo *crea_nodo( unsigned matricula, char *nombre, int edad, char sexo); nodo *inserta_nodo(nodo *lista, nodo *elem); nodo *elimina_nodo(nodo *lista, nodo *elem); nodo *elimina_lista(nodo *lista); int longitud_TDA(nodo *lista); /***** Varias *****/ void Printf(nodo *lista); nodo *obten_datos(char *archivo); void valores_azar(int tot_proc, int tot_ele, int *destino, int *migrar);

85

Listado “operlis.c” En este apartado se presenta el contenido del archivo “operlis.c” el cual contiene las

operaciones que se utilizan en el desarrollo de este proyecto. No se pretende que el usuario haga uso de dichas funciones para la codificación de los programas que realice, el usuario deberá de implementar sus propias funciones para el manejo de la lista. #include "protos.h" /***** Inicializa la lista *****/ nodo *crea_lista(void) { return NULL; } /***** Verifica si la lista se encuentra vacía *****/ int es_vacia(nodo *lista) { if(lista==NULL) return 1; else return 0; } /**** Creación de nodo de la lista ******/ nodo *crea_nodo(unsigned matricula, char *nombre, int edad, char sexo) { nodo *ap=(nodo *)malloc(sizeof(nodo)); if(ap!=NULL) { ap->matricula=matricula; strcpy(ap->nombre, nombre); ap->edad=edad; ap->sexo=sexo; ap->sig=NULL; } else perror("Error... Memoria insuficiente"); return ap; } /***** Inserción de nodo en la lista *****/ nodo *inserta_nodo(nodo *lista, nodo *elem) { nodo *ap=lista; if(es_vacia(ap)) lista=elem; else { while(ap->sig!=NULL) ap=ap->sig; ap->sig=elem;

86

} return lista; } /***** Elimina un nodo de la lista *****/ nodo *elimina_nodo(nodo *lista, nodo *elem) { nodo *ap=lista; nodo *aux=NULL; if(!es_vacia(ap)) { if(ap->matricula==elem->matricula) { aux=ap; ap=ap->sig; free(aux); } else while(ap->sig!=NULL) { if(ap->sig->matricula==elem->matricula) { aux=ap->sig; ap->sig=aux->sig; free(aux); break; } ap=ap->sig; } } return lista; } /***** Elimina la lista completa *****/ nodo *elimina_lista(nodo *lista) { nodo *ap=lista; while(!es_vacia(lista)) { ap=lista; lista=elimina_nodo(lista, ap); } return lista; } /***** Calcula el numero de nodos del TDA para su posterior uso *****/ int longitud_TDA(nodo *lista) { int cont=0; nodo *ap=lista; while(!es_vacia(ap)) { cont++;

87

ap=ap->sig; }

return cont; }

Listado “ent_sal.c” En este apartado se encuentran las funciones utilizadas para la creación de la lista a partir de un

archivo, una función que se encarga del desplegado de la lista dándole cierto formato. EL archivo donde se encuentran tales funciones es “ent_sal.c”. Ninguna de estas funciones que serán usadas en el proyecto final, estas sólo sirven para el desarrollo del mismo. La obtención del TDA lista es a criterio de los usuarios del código para el balance de cargas. #include "protos.h" nodo *obten_datos(char *archivo) { char nombre[40], sexo, basura; int edad; unsigned matricula; nodo *ap=NULL; nodo *lista=crea_lista(); FILE *leer; leer = fopen (archivo,"r"); if (leer != NULL) { do { fscanf (leer, "%d", &matricula); fscanf (leer, "%[^\n]s", nombre); fscanf (leer, "%2d", &edad); fscanf (leer, "%c%*c", &sexo); ap=crea_nodo(matricula, nombre, edad, sexo); lista=inserta_nodo(lista, ap); }while (!feof(leer)); fclose(leer); } else perror("Error... No se pudor abrir el archivo"); return lista; } void Printf(nodo *lista) { nodo *ap=lista; printf("\n%10s | %-50s|%5s|%5s\n", "Matricula","Nombre", "Edad","Sexo"); printf("---------------------------------------------------------------------------\n"); while(ap!=NULL) { printf("%10u | %-50s|%5d|%5c\n", ap->matricula, ap->nombre, ap->edad, ap->sexo); ap=ap->sig; } }

88

Listado “val_azar.c” Otra función utilizada para la realización del proyecto es valores_azar, dicha función es utilizada para dar una simulación más cercana al proyecto final en conjunto, ya que el balance de carga es uno de los módulos, existe otro modulo que se encargará de determinar cuando el nodo se encuentre cargado y por tanto deba de migrarse su información a otro con menos carga, lo cual queda fuera de los objetivos del proyecto actual. Esta función genera valores al azar que le son pasados a las funciones de envío, se toman las precauciones para que dichos valores no estén dentro de los rangos permitidos. La función se encuentra dentro del archivo “val_azar.c”. #include "protos.h" /***** Esta función es utilizada para la creación de los parámetros que determinan a quien y cuanto se va a ser enviado, *****/ void valores_azar(int tot_proc, int tot_ele, int *destino, int *migrar) { time_t tiempo; srand((unsigned)time(&tiempo)); *destino=(rand()%tot_proc)+1; *migrar=(rand()%tot_ele)+1; }

89

Listado “camxcamp.c” /***** En esta primera versión el programa, el único encargado de crear el TDA a partir del archivo

es el proceso "Maestro" o "Coordinador" el cual se encargará de enviar elementos al azar de dicha estructura a un proceso igualmente al azar. El envío se realiza campo por campo, es decir, cada nodo del TDA es enviado uno por uno y a su vez cada campo de cada nodo, por lo que el proceso receptor, deberá reconstruir el TDA. Proyecto: camxcam.c ent_sal.c operlist.c val_azar.c *****/ #include "protos.h" nodo *Envia_TDA(nodo *lista, int destino, int num_elem); nodo *Recive_TDA(nodo *lista);

main(int argc, char *argv[]) { nodo *lista=crea_lista(); MPI_Init (&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &id); MPI_Comm_size(MPI_COMM_WORLD, &proc); MPI_Get_processor_name(nombre, &long_nom); if(id==COORDINADOR) { int destino=0, num_elem=0, lon_tda=0; printf("Soy el coordinador desde %s\n", nombre); lista=obten_datos("/tmp/regis.txt"); //Creación del TDA a partir de un archivo. Printf(lista); //Impresión del TDA lon_tda=longitud_TDA(lista); //Se prepara para migrar elementos valores_azar(proc, lon_tda, &destino, &num_elem); lista=Envia_TDA(lista, destino, num_elem); //Envía elementos printf("%d elementos son enviados a: %d\n", num_elem, destino); printf("Soy el coordinador desde %s\n", nombre); Printf(lista); //Función que imprime la lista } else { printf("\n Hola Mundo, soy el proceso %d, desde %s\n", id, nombre); lista=Recive_TDA(lista); if(!es_vacia(lista)) Printf(lista); //Función que imprime la lista printf("\n"); } MPI_Finalize(); return 0; } /***** En este primer acercamiento se envía campo por campo ****/ nodo *Envia_TDA(nodo *lista, int destino, int num_elem) {

90

int i=0, etiqueta=99, cero=0; int longitud=0; nodo *ap=lista; //Primero se manda el número de elementos a migrar for(i=1; i<proc; i++) { if(i==destino) MPI_Send(&num_elem, 1, MPI_INT, i, etiqueta, MPI_COMM_WORLD); else //Si se trata de alguien diferente al destino MPI_Send(&cero, 1, MPI_INT, i, etiqueta, MPI_COMM_WORLD); } for(i=0; i<num_elem; i++) { ap=lista; longitud=strlen(ap->nombre)+1; //longitud de la cadena // Se envía campo por campo MPI_Send(&ap->matricula, 1, MPI_UNSIGNED, destino, etiqueta, MPI_COMM_WORLD); MPI_Send(&longitud, 1, MPI_INT, destino, etiqueta, MPI_COMM_WORLD); // Se envía la longitud de la cadena antes de enviarla MPI_Send(&ap->nombre, longitud, MPI_CHAR, destino, etiqueta, MPI_COMM_WORLD); MPI_Send(&ap->edad, 1, MPI_INT, destino, etiqueta, MPI_COMM_WORLD); MPI_Send(&ap->sexo, 1, MPI_CHAR, destino, etiqueta, MPI_COMM_WORLD); // Se elimina del TDA el nodo enviado lista=lista->sig; free(ap); } return lista; } /***** Él(los) proceso(s) receptor(es) reconstruye(n) el TDA que les es enviado *****/ nodo *Recive_TDA(nodo *lista) { int num_elem=0, i=0, longitud=0; nodo *ap=NULL; unsigned matricula=0; char nombre[40], sexo; int edad; /*** Se recibe el numero de elementos a recibir ***/ MPI_Recv(&num_elem, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); printf("El mensaje recibido es: %d \n", num_elem); for(i=0; i<num_elem; i++) { MPI_Recv(&matricula, 1, MPI_UNSIGNED, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); // Se recibe la longitud del campo siguiente MPI_Recv(&longitud, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); MPI_Recv(nombre, longitud, MPI_CHAR, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); MPI_Recv(&edad, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); MPI_Recv(&sexo, 1, MPI_CHAR, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); // Reconstrucción del TDA

91

ap=crea_nodo(matricula, nombre, edad, sexo); lista=inserta_nodo(lista, ap); } return lista; }

Listado “empaketado.c” /***** En esta versión el programa, es el único encargado de crear el TDA a partir del archivo es el proceso "Maestro" o "Coordinador" el cual se encargara de enviar elementos al azar de dicha estructura a un proceso igualmente al azar. Para enviar los datos crea un paquete por cada nodo el que contiene toda la información, con esto se evita el envío de mensajes por campo de la estructura. Así es enviado un paquete por cada nodo EL proceso receptor se encarga de desempaquetar la información recibida, reconstruir el nodo y enlistarlo. Proyecto: empaketado.c ent_sal.c operlist.c val_azar.c *****/ #include "protos.h" nodo *Envia_TDA(nodo *lista, int destino, int num_elem); nodo *Recive_TDA(nodo *lista); main(int argc, char *argv[]) { nodo *lista=crea_lista(); MPI_Init (&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &id); MPI_Comm_size(MPI_COMM_WORLD, &proc); MPI_Get_processor_name(nombre, &long_nom); if(id==COORDINADOR) { int destino=0, num_elem=0, lon_tda=0; printf("Soy el coordinador desde %s\n", nombre); lista=obten_datos("/tmp/regis.txt"); //Creación del TDA a partir de un archivo. Printf(lista); //Impresión del TDA lon_tda=longitud_TDA(lista); //Se prepara para migrar elementos valores_azar(proc, lon_tda, &destino, &num_elem); lista=Envia_TDA(lista, destino, num_elem); //Envía elementos printf("%d elementos son enviados a: %d\n", num_elem, destino); printf("Soy el coordinador desde %s\n", nombre); Printf(lista); //Función que imprime la lista } else { printf("\n Hola Mundo, soy el proceso %d, desde %s\n", id, nombre); lista=Recive_TDA(lista); if(!es_vacia(lista)) Printf(lista); //Función que imprime la lista printf("\n"); }

92

MPI_Finalize(); return 0; } /***** En este acercamiento se crea un paquete de cada uno de los nodos y se envía el paquete ****/ nodo *Envia_TDA(nodo *lista, int destino, int num_elem) { int i=0, etiqueta=99, cero=0, posicion=0; int longitud=0; nodo *ap=lista; size_t tam=0; char *buffer; //Primero se manda el numero de elementos a migrar for(i=1; i<proc; i++) { if(i==destino) MPI_Send(&num_elem, 1, MPI_INT, i, etiqueta, MPI_COMM_WORLD); else //Si se trata de alguien diferente al destino MPI_Send(&cero, 1, MPI_INT, i, etiqueta, MPI_COMM_WORLD); } for(i=0; i<num_elem; i++) { ap=lista; longitud=strlen(ap->nombre)+1; //longitud de la cadena posicion=0; //Se inicializa el indicador de la posición en el buffer //Se calcula el tamaño de la memoria a solicitar tam=sizeof(int)+sizeof(char)*longitud+sizeof(unsigned)+sizeof(int)+sizeof(char); // También se empaqueta la longitud de la cadena para ser enviada buffer=(char *)malloc(tam); if(buffer!=NULL) { //Se envía el tamaño del paquete a ser enviado. MPI_Send(&tam, 1, MPI_INT, destino, etiqueta, MPI_COMM_WORLD); //Comienza el empaquetado de la información MPI_Pack(&longitud, 1, MPI_INT, buffer, tam, &posicion, MPI_COMM_WORLD); MPI_Pack(&ap->nombre, longitud, MPI_CHAR, buffer, tam, &posicion, MPI_COMM_WORLD); MPI_Pack(&ap->matricula, 1, MPI_UNSIGNED, buffer, tam, &posicion, MPI_COMM_WORLD); MPI_Pack(&ap->edad, 1, MPI_INT, buffer, tam, &posicion, MPI_COMM_WORLD); MPI_Pack(&ap->sexo, 1, MPI_CHAR, buffer, tam, &posicion, MPI_COMM_WORLD); //Fin del empaquetado. //Se envía el paquete. MPI_Send(buffer, posicion, MPI_PACKED, destino, etiqueta, MPI_COMM_WORLD); // Se elimina del TDA el nodo enviado lista=lista->sig; free(ap); free(buffer); } else { perror("Memoria Insuficiente..."); //Se envía un cero para identificar que hubo un error y se rompe el ciclo MPI_Send(&cero, 1, MPI_INT, destino, etiqueta, MPI_COMM_WORLD);

93

break; } } return lista; } /***** Él(los) proceso(s) receptor(es) desempaqueta(n) el TDA que les es enviado *****/ nodo *Recive_TDA(nodo *lista) { int num_elem=0, i=0, longitud=0, posicion=0; nodo *ap=NULL; unsigned matricula; char nombre[40], sexo; int edad; size_t tam; char *buffer; /*** Se recibe el numero de elementos a recibir ***/ MPI_Recv(&num_elem, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); printf("El mensaje recibido es: %d \n", num_elem); for(i=0; i<num_elem; i++) { posicion=0; //Se inicializa la posición en el buffer MPI_Recv(&tam, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); if(tam<0) //Si se recibe un cero es que hubo un error y se rompe el ciclo break; buffer=(char *)malloc(tam); if(buffer!=NULL) { //Se recibe el paquete. MPI_Recv(buffer, tam, MPI_PACKED, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); //Se comienza a desempaquetar // Se recibe la longitud del campo siguiente MPI_Unpack(buffer, tam, &posicion, &longitud, 1, MPI_INT, MPI_COMM_WORLD); MPI_Unpack(buffer, tam, &posicion, nombre, longitud, MPI_CHAR, MPI_COMM_WORLD); MPI_Unpack(buffer, tam, &posicion, &matricula, 1, MPI_UNSIGNED, MPI_COMM_WORLD); MPI_Unpack(buffer, tam, &posicion, &edad, 1, MPI_INT, MPI_COMM_WORLD); MPI_Unpack(buffer, tam, &posicion, &sexo, 1, MPI_CHAR, MPI_COMM_WORLD); // Reconstrucción del TDA ap=crea_nodo(matricula, nombre, edad, sexo); lista=inserta_nodo(lista, ap); free(buffer); } else perror("Memoria Insuficiente..."); } return lista; }

94

Listado “empaketado_b.c” /***** En esta versión el programa, es el único encargado de crear el TDA a partir del archivo es el proceso "Maestro" o "Coordinador" el cual se encargara de enviar elementos al azar de dicha estructura a un proceso igualmente al azar. Para enviar los datos crea un paquete que contiene toda la información de todos los nodos a ser migrados para evitar el envío de múltiples mensajes. EL proceso receptor se encarga de desempaquetar la información recibida reconstruir el nodo y enlistarlo Proyecto: empaketado.c ent_sal.c operlist.c val_azar.c *****/ #include "protos.h" nodo *Envia_TDA(nodo *lista, int destino, int num_elem); nodo *Recive_TDA(nodo *lista); size_t calcula_tam_buffer(nodo *lista, int num_elem); main(int argc, char *argv[]) { nodo *lista=crea_lista(); MPI_Init (&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &id); MPI_Comm_size(MPI_COMM_WORLD, &proc); MPI_Get_processor_name(nombre, &long_nom); if(id==COORDINADOR) { int destino=0, num_elem=0, lon_tda=0; printf("Soy el coordinador desde %s\n", nombre); lista=obten_datos("/tmp/regis.txt"); //Creación del TDA a partir de un archivo. Printf(lista); //Impresión del TDA lon_tda=longitud_TDA(lista); //Se prepara para migrar elementos valores_azar(proc, lon_tda, &destino, &num_elem); lista=Envia_TDA(lista, destino, num_elem); //Envia elementos printf("%d elementos son enviados a: %d\n", num_elem, destino); printf("Soy el coordinador desde %s\n", nombre); Printf(lista); //Función que imprime la lista } else { printf("\n Hola Mundo, soy el proceso %d, desde %s\n", id, nombre); lista=Recive_TDA(lista); if(!es_vacia(lista)) Printf(lista); //Función que imprime la lista printf("\n"); } MPI_Finalize(); return 0; }

95

/***** En este acercamiento se envía un paquete para todos los nodos del TDA lista ****/ nodo *Envia_TDA(nodo *lista, int destino, int num_elem) { int i=0, etiqueta=99, cero=0, posicion=0; int longitud=0; nodo *ap=lista; size_t tam=calcula_tam_buffer(lista, num_elem); char *buffer; //Primero se manda el número de elementos a migrar for(i=1; i<proc; i++) { if(i==destino) MPI_Send(&num_elem, 1, MPI_INT, i, etiqueta, MPI_COMM_WORLD); else //Si se trata de alguien diferente al destino MPI_Send(&cero, 1, MPI_INT, i, etiqueta, MPI_COMM_WORLD); } buffer=(char *) malloc(tam); if(buffer!=NULL) { ap=lista; //Se envía el tamaño del paquete a ser enviado. MPI_Send(&tam, 1, MPI_INT, destino, etiqueta, MPI_COMM_WORLD); //Este ciclo crea un solo paquete para todos los nodos. for(i=0; i<num_elem; i++) { ap=lista; longitud=strlen(ap->nombre)+1; //longitud de la cadena MPI_Pack(&longitud, 1, MPI_INT, buffer, tam, &posicion, MPI_COMM_WORLD); MPI_Pack(&ap->nombre, longitud, MPI_CHAR, buffer, tam, &posicion, MPI_COMM_WORLD); MPI_Pack(&ap->matricula, 1, MPI_UNSIGNED, buffer, tam, &posicion, MPI_COMM_WORLD); MPI_Pack(&ap->edad, 1, MPI_INT, buffer, tam, &posicion, MPI_COMM_WORLD); MPI_Pack(&ap->sexo, 1, MPI_CHAR, buffer, tam, &posicion, MPI_COMM_WORLD); // Se elimina del TDA el nodo enviado lista=lista->sig; free(ap); } //Se envía el paquete. MPI_Send(buffer, posicion, MPI_PACKED, destino, etiqueta, MPI_COMM_WORLD); free(buffer); //se libera el espacio asignado. } else { perror("Memoria Insuficiente..."); //Se envía un cero para indicar que hubo un error. MPI_Send(&cero, 1, MPI_INT, destino, etiqueta, MPI_COMM_WORLD); } return lista; }

96

/***** Él(los) proceso(s) receptor(es) desempaqueta(n) el TDA que les es enviado *****/ nodo *Recive_TDA(nodo *lista) { int num_elem=0, i=0, longitud=0, posicion=0; nodo *ap=NULL; unsigned matricula; char nombre[40], sexo; int edad; size_t tam=0; char *buffer; /*** Se recibe el numero de elementos a recibir ***/ MPI_Recv(&num_elem, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); printf("El mensaje recibido es: %d \n", num_elem); if(num_elem>0) MPI_Recv(&tam, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); if(tam>0) { buffer=(char *)malloc(tam); if(buffer!=NULL) { //Se recibe el paquete. MPI_Recv(buffer, tam, MPI_PACKED, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); //Se comienza a desempaquetar for(i=0; i<num_elem; i++) { // Se recibe la longitud del campo siguiente MPI_Unpack(buffer, tam, &posicion, &longitud, 1, MPI_INT, MPI_COMM_WORLD); MPI_Unpack(buffer, tam, &posicion, nombre, longitud, MPI_CHAR, MPI_COMM_WORLD); MPI_Unpack(buffer, tam, &posicion, &matricula, 1, MPI_UNSIGNED, MPI_COMM_WORLD); MPI_Unpack(buffer, tam, &posicion, &edad, 1, MPI_INT, MPI_COMM_WORLD); MPI_Unpack(buffer, tam, &posicion, &sexo, 1, MPI_CHAR, MPI_COMM_WORLD); // Reconstrucción del TDA ap=crea_nodo(matricula, nombre, edad, sexo); lista=inserta_nodo(lista, ap); } free(buffer); } else perror("Memoria Insuficiente..."); } return lista; } size_t calcula_tam_buffer(nodo *lista, int num_elem) { nodo *aux=lista; int i=0, longitud=0;

97

size_t tama=0; for(i=0; i<num_elem; i++) { longitud=strlen(aux->nombre)+1; tama+=sizeof(int)+sizeof(char)*longitud+sizeof(unsigned)+sizeof(int)+sizeof(char); aux=aux->sig; } return tama; }

98

Listado “uniones.c” /***** En esta versión el programa, es el único encargado de crear el TDA a partir del archivo es el proceso "Maestro" o "Coordinador" el cual se encargara de enviar elementos al azar de dicha estructura a un proceso igualmente al azar. El envío se realiza por medio de uniones, es decir, cada nodo del TDA es enviado uno por uno mediante el uso de una unión, el proceso receptor, solo deberá agregar a la lista el nodo recibido. Proyecto: uniones.c ent_sal.c operlist.c val_azar.c *****/ #include "protos.h" #define STRUCTSIZE sizeof(nodo) nodo *Envia_TDA(nodo *lista, int destino, int num_elem); nodo *Recive_TDA(nodo *lista); typedef union Nodos_TDA e_TDA; union Nodos_TDA { nodo ap; char mensaje[STRUCTSIZE]; }; main(int argc, char *argv[]) { nodo *lista=crea_lista(); MPI_Init (&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &id); MPI_Comm_size(MPI_COMM_WORLD, &proc); MPI_Get_processor_name(nombre, &long_nom); if(id==COORDINADOR) { int destino=0, num_elem=0, lon_tda=0; printf("Soy el coordinador desde %s\n", nombre); lista=obten_datos("/tmp/regis.txt"); //Creación del TDA a partir de un archivo. Printf(lista); //Impresión del TDA lon_tda=longitud_TDA(lista); //Se prepara para migrar elementos valores_azar(proc, lon_tda, &destino, &num_elem); lista=Envia_TDA(lista, destino, num_elem); //Envía elementos printf("%d elementos son enviados a: %d\n", num_elem, destino); printf("Soy el coordinador desde %s\n", nombre); Printf(lista); //Función que imprime la lista } else { printf("\n Hola Mundo, soy el proceso %d, desde %s\n", id, nombre); lista=Recive_TDA(lista); if(!es_vacia(lista)) Printf(lista); //Función que imprime la lista printf("\n");

99

} MPI_Finalize(); return 0; } /***** En esta versión se realiza el envío mediante el uso de uniones ****/ nodo *Envia_TDA(nodo *lista, int destino, int num_elem) { int i=0, etiqueta=99, cero=0; int longitud=0; e_TDA elem; nodo *ap=NULL; //Primero se manda el numero de elementos a migrar for(i=1; i<proc; i++) { if(i==destino) MPI_Send(&num_elem, 1, MPI_INT, i, etiqueta, MPI_COMM_WORLD); else //Si se trata de alguien diferente al destino MPI_Send(&cero, 1, MPI_INT, i, etiqueta, MPI_COMM_WORLD); } for(i=0; i<num_elem; i++) { ap=lista; strcpy(elem.ap.nombre, ap->nombre); elem.ap.matricula=ap->matricula; elem.ap.edad=ap->edad; elem.ap.sexo=ap->sexo; MPI_Send(elem.mensaje, STRUCTSIZE, MPI_CHAR, destino, etiqueta, MPI_COMM_WORLD); lista=lista->sig; free(ap); } return lista; } /***** Él(los) proceso(s) receptor(es) reconstruye(n) el TDA que les es enviado *****/ nodo *Recive_TDA(nodo *lista) { int num_elem=0, i=0, longitud=0; e_TDA elem; nodo *ap=NULL; /*** Se recibe el numero de elementos a recibir ***/ MPI_Recv(&num_elem, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); printf("El mensaje recibido es: %d \n", num_elem); for(i=0; i<num_elem; i++) { MPI_Recv(elem.mensaje, STRUCTSIZE, MPI_CHAR, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); ap=crea_nodo(elem.ap.matricula, elem.ap.nombre, elem.ap.edad, elem.ap.sexo); lista=inserta_nodo(lista, ap); } return lista; }

100

Listado “uniones_b.c” /***** En esta primera versión el programa, el único encargado de crear el TDA a partir del archivo es el proceso "Maestro" o "Coordinador" el cual se encargara de enviar elementos al azar de dicha estructura a un proceso igualmente al azar. El envío se realiza por medio de uniones, es decir, cada nodo del TDA es enviado uno por uno mediante el uso de una unión. La diferencia con el anterior es la forma de llenar los campos de la estructura, en este no hay que llenar campo por campo, esto hace el código más general, de esta forma no hay que meter en la codificación el llenado de la estructura en la unión para el envío. El proceso receptor, solo deberá agregar a la lista el nodo recibido. Proyecto: uniones_b.c ent_sal.c operlist.c val_azar.c *****/ #include "protos.h" #define STRUCTSIZE sizeof(nodo) nodo *Envia_TDA(nodo *lista, int destino, int num_elem); nodo *Recive_TDA(nodo *lista); typedef union Nodos_TDA e_TDA; union Nodos_TDA { nodo ap; char mensaje[STRUCTSIZE]; }; main(int argc, char *argv[]) { nodo *lista=crea_lista(); MPI_Init (&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &id); MPI_Comm_size(MPI_COMM_WORLD, &proc); MPI_Get_processor_name(nombre, &long_nom); if(id==COORDINADOR) { int destino=0, num_elem=0, lon_tda=0; printf("Soy el coordinador desde %s\n", nombre); lista=obten_datos("/tmp/regis.txt"); //Creación del TDA a partir de un archivo. Printf(lista); //Impresión del TDA lon_tda=longitud_TDA(lista); //Se prepara para migrar elementos valores_azar(proc, lon_tda, &destino, &num_elem); lista=Envia_TDA(lista, destino, num_elem); //Envía elementos printf("%d elementos son enviados a: %d\n", num_elem, destino); printf("Soy el coordinador desde %s\n", nombre); Printf(lista); //Función que imprime la lista } else { printf("\n Hola Mundo, soy el proceso %d, desde %s\n", id, nombre); lista=Recive_TDA(lista); if(!es_vacia(lista))

101

Printf(lista); //Función que imprime la lista printf("\n"); } MPI_Finalize(); return 0; } /***** En este primer acercamiento se envía campo por campo ****/ nodo *Envia_TDA(nodo *lista, int destino, int num_elem) { int i=0, etiqueta=99, cero=0; nodo *ap=NULL; e_TDA elem; //Primero se manda el numero de elementos a migrar for(i=1; i<proc; i++) { if(i==destino) MPI_Send(&num_elem, 1, MPI_INT, i, etiqueta, MPI_COMM_WORLD); else //Si se trata de alguien diferente al destino MPI_Send(&cero, 1, MPI_INT, i, etiqueta, MPI_COMM_WORLD); } for(i=0; i<num_elem; i++) { ap=lista; //Se realiza una copia del nodo en el elemento de la unión para poder ser transferido. elem.ap=*ap; //Es importante inicializar el campo a nulo elem.ap.sig=NULL; MPI_Send(elem.mensaje, STRUCTSIZE, MPI_CHAR, destino, etiqueta, MPI_COMM_WORLD); // Se elimina el nodo de la lista lista=lista->sig; free(ap); } return lista; } /***** Él(los) proceso(s) receptor(es) reconstruye(n) el TDA que les es enviado *****/ nodo *Recive_TDA(nodo *lista) { int num_elem=0, i=0, longitud=0; e_TDA elem; nodo *ap=NULL; /*** Se recibe el numero de elementos a recibir ***/ MPI_Recv(&num_elem, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); printf("El mensaje recibido es: %d \n", num_elem); for(i=0; i<num_elem; i++) { ap=(nodo *)malloc(sizeof(nodo)); if(ap!=NULL) { MPI_Recv(elem.mensaje, STRUCTSIZE, MPI_CHAR, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); *ap=elem.ap; lista=inserta_nodo(lista, ap);

102

} else perror("Memoria Insuficiente..."); } return lista; }

103

9.2. Anexo B (Códigos Fuentes para el Reconocimiento del TDA Lista)

Listado “scan.c” #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXCAD 20000 #define RE_END 0 //Registra Estructura Termina #define RL_SBE 1 //Registra Línea y Sigue Buscando Estructura #define RL_BNE 2 //Registra Línea y Busca Nueva Estructura #define NR_SBE 4 //No Registres y Sigue Buscando Estructura /***** Estructura auxiliar para la identificación del registro de los TDA's *****/ typedef struct estruct_reg reg; struct estruct_reg { char *str_reg; char *token; reg *sig; }; /***** Funciones para la búsqueda de la estructura *****/ reg *busca_estructuras(char *tda, FILE *flujo, reg *col_dat); char *obten_bloque(FILE *flujo); void descarta_funcion(FILE *flujo); /***** Funciones de verificación *****/ int existe(char *linea,reg *cola); int token_reg(char *linea, reg *cola); int dato_c(char *decl); int verifica_exist(char *linea, char *tda, char *nueva_str); int verifica_campos(char *estruc, reg *cola, char *ntok); /***** Funciones para el manejo de los TDA's utilizados para el registro *****/ reg *crea_nodo(char *linea, char *token); reg *encola(reg *cola, reg *ap); reg *registra_TDA(char *linea, char *aux, reg *col_dat, FILE *flujo); void crea_arout(reg *estructuras, FILE *salida, char *tda); main(int argc, char *argv[]) { FILE *flujo, *salida; reg *estructuras=NULL; if(argc>2) { if((flujo=fopen(argv[1],"r"))!=NULL) { printf("\t Escaneando archivo \"%s\" \n", argv[1]); printf("\t\t Buscando TDA --> %s... \n", argv[2]); printf("\t\t Creando archivo de salida...\n"); if((salida=fopen("./def_TDA.h","w"))!=NULL)

104

{ //La función busca la estructura y regresa un TDA con toda la información de la misma estructuras=busca_estructuras(argv[2], flujo, estructuras); //Se guardan las estructuras en un archivo y se cierran los flujos crea_arout(estructuras, salida, argv[2]); fclose(flujo); fclose(salida); } else perror("Error... No se puede crear el archivo de salida"); } else perror("Error... Al abrir el archivo, verifique ruta y nombre"); } else { if(argc==2) perror("Error... Argumentos insuficientes"); else perror("Error... sin argumentos en main()\n"); printf("\t Prueba con: %s <archivo.c> <tda>\n\n",argv[0]); printf("\t<archivo.c>: archivo fuente en donde se deberá buscar la estructura \n"); printf("\t <tda>: es el nombre de la estructura a ser buscada \n"); } return 0; } /********** Funciones que auxilian a la búsqueda del TDA *********/ //Esta función es la encargada de recorrer todo el archivo en busca del TDA //lo hace por bloques que pudiesen ser una estructura reg *busca_estructuras(char *tda, FILE *flujo, reg *col_dat) { char linea[MAXCAD]="", nueva_str[MAXCAD]="", aux[MAXCAD]; int vr=0, salir=0, k=0; fpos_t *inicio; reg *ap=NULL; strcpy(aux,tda); while(!feof(flujo)) { //La función regresa un bloque que pudiera ser una estructura strcpy(linea, obten_bloque(flujo)); // Busca en el bloque el tda que solicitado vr=verifica_exist(linea, aux, nueva_str); switch(vr) { case RE_END: //Esta opción indica que el TDA ha sido encontrado col_dat=registra_TDA(linea, aux, col_dat, flujo); salir=1; break;

105

case RL_SBE: //Esta opción indica que se trata de una redefinición, //pero se sigue buscando la misma estructura col_dat=registra_TDA(linea, aux, col_dat, flujo); salir=0; break; case RL_BNE: //Esta indica que se trata de una redefinición y se buscara la original col_dat=registra_TDA(linea, aux, col_dat, flujo); strcpy(aux, nueva_str); salir=0; break; default: //no se ha encontrado nada relacionado con la estructura break; } if(salir) break; } return col_dat; } //Esta función es la encargada de buscar en el archivo, lo hace por bloques que pudiesen ser //declaraciones de estructuras, sólo regresan los posibles candidatos. //Es capas de ignorar prototipos, archivos de inclusión y funciones. char *obten_bloque(FILE *flujo) { int llave=0, term_lin=0, paren_a=0, paren_c=0, i=0; char linea[MAXCAD]; /*El siguiente ciclo es capaz de encontrar bloques que puedan ser considerados como una estructura.*/ while(!feof(flujo)) { linea[i]=fgetc(flujo); switch(linea[i]) { //Ignora los archivos de cabecera case '#': while(!feof(flujo)) if(fgetc(flujo)=='\n') break; i=0; break; //verifica si no hay llaves abiertas para salir case ';': if(paren_a && paren_c)//Descarta los prototipos paren_a=paren_c=i=0; else { if(llave==0) term_lin=1; i++; } break; //Elimina los saltos de línea y tabuladores innecesarios case '\n': break; case '\t': break; //Registra si se han abierto o cerrado llaves case '{': if(paren_a && paren_c)

106

{ //Evita buscar la definición dentro de una función descarta_funcion(flujo); paren_a=paren_c=i=llave=0; } else llave++; i++; break; case '}': llave--; i++; break; //Registra si se encuentra posiblemente una función case '(': paren_a++; i++; break; case ')': paren_c++; i++; break; default: i++; } if(term_lin) //Pone el fin de línea { linea[i]='\0'; break; } } return linea; } //Esta función se encarga de eliminar lo que se considera como el cuerpo de la función void descarta_funcion(FILE *flujo) { int llave=1; char basura; while(!feof(flujo)) { switch(fgetc(flujo)) { case '{': llave++; break; case '}': llave--; break; default: break; } if(!llave) break; } } /****** Funciones que auxilian en la identificación, registro y verificación del TDA y sus campos *****/ //Esta función se encarga de verificar si la línea ya fue registrada, para evitar duplicarla int existe(char *linea, reg *cola) { reg *ap=cola; int vr=0, iguales=0; while(ap!=NULL) { iguales=strcmp(linea,ap->str_reg); if(iguales==0) { vr=1;

107

break; } ap=ap->sig; } return vr; } //Verifica si un token ya fue buscado, para evitar buscarlo nuevamente al verificar los campos de la estructura. int token_reg(char *linea, reg *cola) { reg *ap=cola; int vr=0; while(ap!=NULL) { vr=strcmp(linea,ap->token); if(vr==0) { vr=1; break; } ap=ap->sig; } return vr; } //Esta función es la encargada de verificar si el bloque que le es pasado //es el TDA buscado int verifica_exist(char *linea, char *tda, char *nueva_str) { int salida=NR_SBE,j=0,i=0; char typedef_[]="typedef"; //cadena para determinar si la estructura pasada es un redefinición. size_t tam_sub=strlen(typedef_), tam_cad=strlen(linea); //Esta función es la encargada de determinar si el TDA buscado se encuentra en //en el bloque, si no se encuentra regresa un NULL char *tipo=strstr(linea,tda); size_t tam_tipo=0; //Posiblemente se trata de la definición if(tipo!=NULL) { tam_tipo=strlen(tipo); //Verifica si se trata de una redefinición if(strstr(linea, typedef_)!=NULL) { //verifica si es el nombre de la estructura // o es la redefinición. if(tam_tipo-1==strlen(tda)) { for(i=tam_sub+1, j=0; i<tam_cad-tam_tipo-1; i++, j++) nueva_str[j]=linea[i]; nueva_str[i]='\0'; salida=RL_BNE; }

108

else { //Si la redefinición esta junto con la estructura if(strstr(linea,"{")) salida=RE_END; //Solamente se trata de la redefinición. else salida=RL_SBE; } } //La estructura ha sido encontrada. else { printf("\t Estructura encontrada \n\t"); printf("\t\t%s\n",linea); salida=RE_END; } } return salida; } //Verifica que los campos del TDA sean tipos de datos reconocidos una vez que esta ha sido encontrado, //si alguno de los campos no es reconocido realiza la búsqueda de este mismo int verifica_campos(char *estruc, reg *cola, char *ntok) { char *aux, *cadmod, *tipo; char delim[]=";"; int i=0, j=0, vr=1; //pide memoria para la realización de su trabajo cadmod=(char *)malloc(sizeof(char)*strlen(estruc)+1); tipo=(char *)malloc(sizeof(char)*strlen(estruc)+1); if(cadmod != NULL && tipo!=NULL) { //Busca el cuerpo de la estructura, para obtener los campos while(estruc[i++]!='{'); //Copia los campos de la estructura a una nueva cadena for(j=0; i<strlen(estruc)-2; j++, i++) cadmod[j]=estruc[i]; cadmod[j]='\0'; //Obtiene campo por campo mediante el delimitador ";" aux=strtok(cadmod, delim); while(aux!=NULL) { if(aux!=NULL) { i=0; //Este ciclo obtiene el tipo de dato de la declaración while(aux[i++]!=' ') tipo[i-1]=aux[i-1]; tipo[i-1]='\0'; if(!dato_c(tipo)) //verifica si se trata de un tipo de dato de C

109

{ //Verifica si se trata de una estructura ya registrada if(!token_reg(tipo, cola)) { //Copia el nuevo token para seguir buscando for(i=0; tipo[i]!='\0'; i++) ntok[i]=tipo[i]; vr=0; //Regresa un valor de error. break; } } } aux=strtok(NULL, delim); } } else perror("Error... Memoria insuficiente"); return vr; } //Determina si el tipo de dato que se le pasa es un tipo de dato de C int dato_c(char *decl) { char *tipo=NULL; if(strstr(decl,"char")!=NULL) return 1; if(strstr(decl,"int")!=NULL) return 1; if(strstr(decl,"unsigned")!=NULL) return 1; if(strstr(decl,"long")!=NULL) return 1; if(strstr(decl,"float")!=NULL) return 1; if(strstr(decl,"double")!=NULL) return 1; if(tipo==NULL) return 0; } /***** Funciones para el de los TDA utilizados en la búsqueda de los TDA's ****/ reg *crea_nodo(char *linea, char *token) { reg *ap=NULL; ap=(reg *)malloc(sizeof(ap)); if(ap!=NULL) { ap->str_reg=(char *)malloc(strlen(linea)+1); ap->token=(char *)malloc(strlen(token)+1); if(ap->str_reg!=NULL && ap->token!=NULL) { strcpy(ap->str_reg, linea); strcpy(ap->str_reg, linea);

110

ap->sig=NULL; } else perror("Error... Memoria insuficiente"); } else perror("Error... Memoria insuficiente"); return ap; } reg *encola(reg *cola, reg *ap) { reg *aux=cola; if(aux==NULL) cola=ap; else { while(aux->sig!=NULL) aux=aux->sig; aux->sig=ap; } return cola; } //Función encargada de registrar lo relacionado con la búsqueda //verifica primero si no ha sido registrada, para evitar duplicidad reg *registra_TDA(char *linea, char *aux, reg *col_dat, FILE *flujo) { reg *ap=NULL; int campo=1; //Verifica el registro de la linea if(!existe(linea, col_dat)) { ap=crea_nodo(linea, aux); col_dat=encola(col_dat, ap); } do { //Si alguno de los campos no existe se llama a la función para su búsqueda desde el inicio campo=verifica_campos(linea, col_dat, aux); if(!campo) { rewind(flujo); col_dat=busca_estructuras(aux, flujo, col_dat); } }while(campo==0); return col_dat; } //Función encargada de escribir en el archivo de salida el resultado de la búsqueda

111

void crea_arout(reg *estructuras, FILE *salida, char *tda) { reg *ap=NULL; if(estructuras!=NULL) { //Escribe un redefinición del TDA para que sea usado por el programa realizado //en la parte I fprintf(salida,"\n typedef struct %s nodo;\n", tda); do { ap=estructuras; fprintf(salida, "%s\n", ap->str_reg); estructuras=estructuras->sig; free(ap); }while(estructuras!=NULL); } else printf("La estructura no ha sido encontrada...\n"); }

112

9.3. Anexo C (Códigos Fuentes para Migración de datos compartidos con hilos)

Listado “hilos_1.c” /***** Programa que ejemplifica la forma de usar los hilos en MPI, el proceso 0 realiza el desplegado de los datos(arreglo

de enteros) en pantalla con un hilo, mientras otro espera un lapso de tiempo y pide al usuario el número de elementos a migrar al proceso 1, el cual como única función tiene la recepción de los datos.

El arreglo utilizado es global. archivo: hilos_1.c *****/ #include <semaphore.h> #include <pthread.h> #include <stdio.h> #include "mpi.h" //Prototipos de las funciones utilizadas void proceso(void *numero); void monitor(void *numero); void inicializa(int *arr); int id; int proc; int longitud; int hilo; char nombre[MPI_MAX_PROCESSOR_NAME]; pthread_mutex_t candado; //Candado utilizado para garantizar la integridad del arreglo. int arreglo[20]; main (int argc, char *argv[]) { int vr=0; int array[20]; pthread_t hilo1, hilo2; //Hilos utilizados por el Coordinador(proceso 0) int i=0; long num_dat; time_t semilla; MPI_Status estado; //Objeto para la verificación de la recepción de mensajes //Rutinas de iniciación para MPI MPI_Init (&argc, &argv); MPI_Comm_size(MPI_COMM_WORLD, &proc); MPI_Comm_rank(MPI_COMM_WORLD, &id); MPI_Get_processor_name(nombre, &longitud); switch(id) { case 0: //Proceso coordinador inicializa(arreglo); fprintf(stdout,"Proceso %d, desde %s\n", id, nombre); //Creación del hilo monitor encargado de migrar elementos del arreglo pthread_create(&hilo1, NULL, (void *)&monitor, (void *)1); //Creación del hilo que realiza el desplegado en pantalla pthread_create(&hilo2, NULL, (void *)&proceso, (void *)2); //Espera por la terminación de los hilos.

113

pthread_join(hilo1, (void *)&vr); pthread_join(hilo2, (void *)&vr); printf("Los hilos del proceso %s han terminado...\n", id); break; case 1: //Proceso receptor printf("\n"); fprintf(stdout,"Proceso %d, desde %s\n", id, nombre); //Iniciación del arreglo for(i=0;i<20; i++) array[i]=-1; //Recibe el mensaje con la cantidad de elementos que recibirá. MPI_Recv(&num_dat, 1, MPI_INT, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); //ciclo para la Recepción de los elementos del arreglo. for(i=0; i<num_dat; i++) MPI_Recv(&array[i], 1, MPI_INT, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &estado); //Desplegado del arreglo en este proceso. for(i=0; (array[i]!=-1 && i<20); i++) printf("%3d",array[i]); printf("\n\n"); break; default: break; //Otro proceso... } //Finalización del paralelismo. MPI_Finalize(); return 0; } /**** Iniciación del arreglo con valores al azar *****/ void inicializa(int *arr) { int i=0; time_t semilla; time(&semilla); //Iniciación de la semilla srand((unsigned)semilla); for(i=0;i<20;i++) arr[i]=rand()%10; } /***** Proceso encargado de la migración de los datos. Pide el numero de elementos del arreglo a ser enviados al proceso 1 y los envía *****/ void monitor(void *datos) { int hilo=(int)datos; int num_nodos=0, i=0, etiqueta=0; if(id==0) { sleep(5); //Lapso de espera antes de comenzar el envío pthread_mutex_lock(&candado); //Cierra el candado para garantizar la integridad de los datos. fprintf(stdout,"Hola soy el hilo %d\n",hilo); fprintf(stdout,"del proceso %d\n",id); fprintf(stdout,"Desde el procesador %s\n",nombre);

114

//Este ciclo valida que el usuario no exceda el límite del arreglo. do { printf("Dime cuantos nodos quieres migrar: "); scanf("%d", &num_nodos); }while(num_nodos<0 || num_nodos>20); printf("\n los elementos a migrar son %d\n",num_nodos); //Manda el mensaje con el número de elementos que enviará al proceso 1 MPI_Send(&num_nodos, 1, MPI_INT, 1, etiqueta, MPI_COMM_WORLD); //Envía cada uno de los elementos (envía los últimos). for(i=20-num_nodos; i< 20 ; i++) { MPI_Send(&arreglo[i], 1, MPI_INT, 1, etiqueta, MPI_COMM_WORLD); arreglo[i]=-1; //Borra el elemento del arreglo. } pthread_mutex_unlock(&candado); //Abre el candado. } pthread_exit((void *)hilo); } /***** Proceso encargado de imprimir el arreglo en pantalla cada 2 segundos, aquí se ve que el arreglo disminuye cuando se envían al proceso 1 *****/ void proceso(void *numero) { int i=0, count=0; int hilo=(int)numero; printf("\n Soy el hilo %d del procesador %s\n", hilo, nomb re); while(count<5) { pthread_mutex_lock(&candado); //Se cierra el candado para garantizar la integridad. for(i=0; (arreglo[i]!=-1 && i<20); i++) printf("%3d",arreglo[i]); printf("\n"); pthread_mutex_unlock(&candado); //Se habré el candado sleep(2); count ++; } pthread_exit((void *)hilo); }

115

Listado “hilos_2.c” /***** Programa que ejemplifica la forma de usar los hilos en MPI. Cada proceso inicializa el arreglo con valores al azar

posteriormente crea un par de hilos, el de envío y el de recepción y comienza el procesamiento de sus datos el cual consiste en la impresión del arreglo en un archivo con nombre igual a la maquina donde se encuentra corriendo y al proceso correspondiente, cada 2 segundos en 15 ocasiones. El hilo encargado del envío lo hace cada cierto tiempo al azar al igual que la cantidad de elemento que envía. El arreglo utilizado es global, archivo: hilos_2.c *****/

#include <pthread.h> #include <stdio.h> #include "mpi.h" #define CANTIDAD 0 #define ELEMENTO 1 //Prototipos de las funciones que el proceso necesita para el manejo de los datos void proceso(void); char *num_proc(int id); char da_digit(int num); void inicializa(int *arr); void valores_azar(int tot_proc, int tot_ele, int *destino, int *migrar); //Prototipos de las funciones necesarias para el envío y recepción. void Envia(void *num); void Recibe(void *salida); void MPI_Term_hilo(int *signal); int id; int proc; int longitud; char nombre[MPI_MAX_PROCESSOR_NAME]; pthread_mutex_t candado; //Candado para garantizar la exclusión mutua. int arreglo[100]; //Esta es la señal para la terminación de los hilos. int MPI_Signal_term_hilo=1; main (int argc, char *argv[]) { int vr_env=0, vr_rec=0, salir=0; pthread_t envio, recepcion; //hilo para el manejo de los datos MPI_Status estado; //Objeto para la verificación de la recepción de mensajes. int *signal=&MPI_Signal_term_hilo; //Rutinas de iniciación de MPI MPI_Init (&argc, &argv); MPI_Comm_size(MPI_COMM_WORLD, &proc); MPI_Comm_rank(MPI_COMM_WORLD, &id); MPI_Get_processor_name(nombre, &longitud); //Se inicializan los arreglos que posteriormente serán enviados inicializa(arreglo); //Se crean los hilos encargados del balance de carga. pthread_create(&envio, NULL, (void *)&Envia, (void *)1); pthread_create(&recepcion, NULL, (void *)&Recibe, (void *)salir);

116

//Función que opera con los datos. proceso(); //Crea la señal para la terminación de los hilos MPI_Term_hilo(signal); //Se espera la terminación de los hilos para el balance de carga. //Y se guarda el valor de retorno. pthread_join(envio,(void *)&vr_env); pthread_join(recepcion, (void *)&vr_rec); fprintf(stdout, "Proceso %d, desde %s ---->", id, nombre); if(vr_env && vr_rec) fprintf(stdout, " El balance ha terminado sin problemas.\n"); MPI_Finalize(); return 0; } /***** Esta función es utilizada para indicar a los hilos encargados del balance de la carga que terminen. *****/ void MPI_Term_hilo(int *signal) { *signal=0; } /***** Función encargada del envío de elementos del arreglo, se hace al azar *****/ void Envia(void *num) { int destino=0, num_elem=0; int vr=(int)num; int tam=0, i=0; time_t semilla; //Iniciación de la semilla. srand((unsigned) semilla +id); while(MPI_Signal_term_hilo) { sleep(rand()%10); //Espera un tiemp o al azar antes de realizar un envío valores_azar(proc,20,&destino,&num_elem); if(destino!=id && num_elem) { fprintf(stdout,"\n proceso %d -----> Hilo envía %d datos a %d...\n",id, num_elem, destino); //se cierra el candado para garantizar la integridad de los datos pthread_mutex_lock(&candado); //Se manda el mensaje que indica cuantos elementos se van a migrar. MPI_Send(&num_elem, 1, MPI_INT, destino, CANTIDAD, MPI_COMM_WORLD); //Ciclo encargado del envío de los elementos. //Se obtiene el tamaño actual del arreglo para enviar los últimos elementos. tam=calcula_tam(arreglo); for(i=tam-num_elem; i<tam; i++) { MPI_Send(&arreglo[i], 1, MPI_INT, destino, ELEMENTO, MPI_COMM_WORLD); arreglo[i]=-1; } //Se habré el candado para que el proceso que los opera pueda hacer uso de estos.

117

pthread_mutex_unlock(&candado); } } pthread_exit((void *)&vr); } void Recibe(void *salida) { int *termina=(int *)salida; int bandera=0, fuente=0, elem=0, i=0, basura=0, vr=0, tam=0; int count =0; MPI_Status estado; while(MPI_Signal_term_hilo) { //Se realiza una prueba, para ver si se han recibido mensajes MPI_Iprobe(MPI_ANY_SOURCE, CANTIDAD, MPI_COMM_WORLD, &bandera, &estado); if(bandera)//Verificación de recepción de mensajes. { //Obtención de la fuente que envío el mensaje. fuente=estado.MPI_SOURCE; //Recepción de la cantidad de elementos a recibir. MPI_Recv(&elem, 1, MPI_INT, fuente, CANTIDAD, MPI_COMM_WORLD, &estado); //Se cierra el candado para garantizar la integridad. pthread_mutex_lock(&candado); tam=calcula_tam(arreglo); //Obtención del numero de elementos en el arreglo. fprintf(stdout, "\n El proceso %d recibe señal de %d ---> datos a recibir %d\n",id, fuente, elem); for(i=0; i<elem; i++,tam++) { //Recepción de los elementos enviados. if(tam<100) MPI_Recv(&arreglo[tam], 1, MPI_INT, fuente, ELEMENTO, MPI_COMM_WORLD, &estado); //Esto garantiza que no se sobrepase del tamaño del arreglo, aunque provoca perdida de datos. else MPI_Recv(&basura, 1, MPI_INT, fuente, ELEMENTO, MPI_COMM_WORLD, &estado); } //Se habré el candado nuevamente. pthread_mutex_unlock(&candado); } } pthread_exit((void *)&vr); } /***** Esta función calcula el numero de elementos en el arreglo *****/ int calcula_tam(int *arr) { int i=0; for(i=0; (arr[i]!=-1 && i<100); i++); return i; }

118

/***** Función de iniciación para el arreglo *****/ void inicializa(int *arr) { int i=0; time_t semilla; time(&semilla); srand((unsigned)semilla+id); //Se crean valores aleatorios para el arreglo. for(i=0;i<20;i++) arr[i]=rand()%10; //El resto se inicia con un valor de -1 for(;i<100; i++) arr[i]=-1; } /***** Esta función es utilizada para la creación de los parámetros que determinan a quien y cuanto se va a ser enviado, *****/ void valores_azar(int tot_proc, int tot_ele, int *destino, int *migrar) { time_t tiempo; srand((unsigned)time(&tiempo)+id); *destino=(rand()%tot_proc); //Para que cada uno de los proceso envié sólo una cuarta parte de sus elementos *migrar=(rand()%(tot_ele/4)); } /***** Este es el proceso encargado de las operaciones de los datos, Las operaciones que realiza son la escritura del arreglo cada cierto tiempo, en un archivo con el nombre del procesador y el proceso correspondiente. *****/ void proceso(void) { int i=0, count=0; FILE *arch; char nom_arch[20]; //Estas tres funciones crean el nombre del archivo en el cual guardaran el arreglo cada cierto tiempo. strcpy(nom_arch,"./"); strcat(nom_arch,nombre); strcat(nom_arch,"_"); strcat(nom_arch,num_proc(id));//num_proc regresa el numero de proceso en una cadena. arch=fopen(nom_arch,"w"); if(arch!=NULL) { fprintf(arch,"Soy el Proceso:%d desde el procesador %s\n", id, nombre); while(count<15) { //El hilo encargado de la migración de los datos no debe poder hacerlo mientras //se este operando sobre los mismos. pthread_mutex_lock(&candado); for(i=0; (arreglo[i]!=-1 && i<100); i++) fprintf(arch,"%3d",arreglo[i]); fprintf(arch,"\n"); pthread_mutex_unlock(&candado);

119

sleep(2); count ++; } } } /***** Funciones auxiliares para la creación del nombre del archivo para la salida. *****/ /***** Recibe el numero de proceso y lo convierte a cadena para ser agregado al nomb re del archivo *****/ char *num_proc(int id) { char pross[4]; int dec=0, uni=0; pross[0]=da_digit(id/100); dec=id%100; pross[1]=da_digit(dec/10); uni=dec%10; pross[2]=da_digit(uni); pross[3]='\0'; return pross; } /***** Convierte números en caracteres *****/ char da_digit(int num) { char dig_let; switch(num) { case 0: dig_let='0'; break; case 1: dig_let='1'; break; case 2: dig_let='2'; break; case 3: dig_let='3'; break; case 4: dig_let='4'; break; case 5: dig_let='5'; break; case 6: dig_let='6'; break; case 7: dig_let='7'; break; case 8: dig_let='8'; break; case 9: dig_let='9'; break; default: break; } return dig_let; }

Listados “Primera versión” Es esta sección quedan establecidas las rutinas para el balance de carga, se incluyen los listados

de dichas rutinas y los listados de las rutinas necesarias para el desarrollo del programa de prueba, el cual maneja una lista de registros de alumnos, que es formada a partir de un archivo de texto. Las rutinas de balance sólo responden a la indicación de un hilo que les indica a donde y cuantos elementos se deberán migrar a otro nodo del cluster.

120

Listado “protos.h” #include <semaphore.h> //Este archivo de inclusión si será incluido en el proyecto final #include <pthread.h> //Este archivo de inclusión si será incluido en el proyecto final #include <stdlib.h> #include <stdio.h> #include <math.h> #include "mpi.h" //Este archivo de inclusión si será incluido en el proyecto final #include "def_TDA.h" //Este archivo de inclusión si será incluido en el proyecto final, //incluye la definición del TDAS que se va a utilizar. /***** Variables globales utilizadas para la identificación de los procesos. *****/ int id, proc, long_nom; char nombre[50]; #define CANTIDAD 0 #define ELEMENTO 1 #define COORDINADOR 0 #define STRUCTSIZE sizeof(nodo) /***** Estructura utilizada para lograr el balance del TDA *****/ typedef union Nodos_TDA e_TDA; union Nodos_TDA { nodo ap; char mensaje[STRUCTSIZE]; }; /***** Estructura de datos necesaria para que los hilos puedan manejar el TDA y la migración de datos a otros nodos del cluster *****/ typedef struct Parametros_Balance { nodo **TDA; int MPI_DEST; int MPI_ELEM; int MPI_SIGNAL_TERM; }MPI_Balance; sem_t signal; //Señal para indicar al hilo que envié los datos a otros nodos. pthread_t envio, recepcion, monitor; //hilo para el manejo de los datos pthread_mutex_t candado, candado_estructura; //Candado para garantizar la exclusión mutua. /***** Prototipos de las funciones encargadas del balance de la carga ****/ void MPI_Init_balance(MPI_Balance *par_bal, nodo **lista); void MPI_Finaliza_balance(MPI_Balance *par_bal); void Envia_TDA(void *datos); void Recibe_TDA(void *datos); void Monitor(void *datos); void Cierra_candados(void); void Abre_candados(void); /***** Estas funciones son obtenidas mediante el ejecutable scan de la sección 2 ****/

121

/****************************************************************************************************************/ /*Las siguientes funciones tendrán que ser declaradas por el usuario de la rutina de balance, no será necesario*/ /*que sean utilizadas las rutinas declaradas para esta prueba, y tampoco es necesario que sean incluidas en este*/ /*archivo de cabecera, éste sólo es una prueba */ /****************************************************************************************************************/ /***** Prototipos para el manejo del TDA lista *****/ void crea_lista(nodo **lista); int es_vacia(nodo *lista); nodo *crea_nodo( unsigned matricula, char *nombre, int edad, char sexo); void inserta_nodo(nodo **lista, nodo *elem); void elimina_nodo(nodo **lista, nodo *elem); void elimina_lista(nodo **lista); int longitud_TDA(nodo *lista); /***** Varias *****/ void Printf(nodo *lista, FILE *ap); nodo *obten_datos(char *archivo);

122

Listado “def_TDA.h” En este archivo se encuentra la definición de la estructura utilizada para la creación del TDA lista, se pretende que el usuario haga uso del programa “scan.c” de la sección “Búsqueda de una estructura” para la obtención del mismo, además se crea una redefinición de la estructura la cual es manejada por las rutinas de balance de carga para su trabajo. /***** Este archivo es obtenido con el ejecutable de la parte 2. El cual realiza una redefinición de la estructura para que

los hilos hagan uso de la misma *****/ typedef struct Registro nodo; struct Registro { char nombre[40]; unsigned matricula; int edad; char sexo; nodo *sig; };

Listado “balance.c” Este es el listado el cual contiene las rutinas necesarias para el balance de carga. /***** Esta es el archivo que lleva a cabo el balance de carga, no requiere mayores cambios por el usuario que los

indicados en la documentación misma, esto para darle mayor libertad al usuario de realizar sus funciones para el manejo del TDA. *****/

#include "protos.h" void MPI_Init_balance(MPI_Balance *par_bal, nodo **lista) { //Se inicia el semáforo el cual indicará el momento para comenzar el balance sem_init(&signal,0,0); //Iniciación de la estructura //Se indica la dirección de los datos que podrían ser enviados a otro proceso par_bal->TDA=lista; //Se inicia el parámetro destino, con un valor igual al proceso par_bal->MPI_DEST=id; //Se inicia el número de elementos a enviar par_bal->MPI_ELEM=0; //Se inicia la señal que indica a los hilos que terminen par_bal->MPI_SIGNAL_TERM=0; //Iniciación de los hilos para el balance pthread_create(&envio, NULL, (void *)&Envia_TDA, (void *)par_bal); pthread_create(&recepcion, NULL, (void *)&Recibe_TDA, (void *)par_bal); //Esta Función no va a ser necesaria para el uso en general //Este hilo es el encargado de determinar a quien, cuantos y en que momento le serán enviados datos pthread_create(&monitor, NULL,(void *)&Monitor,(void *)par_bal); } void MPI_Finaliza_balance(MPI_Balance *par_bal) {

123

int vr_env=0, vr_rec=0, vr_mon=0; //Se manda la señal a los hilos para que terminen su trabajo par_bal->MPI_SIGNAL_TERM=1; //Se espera la terminación de los hilos que realizan el balance de carga. //Y se guarda el valor de retorno. pthread_join(monitor,(void *)&vr_mon); pthread_join(envio,(void *)&vr_env); pthread_join(recepcion, (void *)&vr_rec); if(vr_env || vr_rec) fprintf(stdout, "Proceso %d, desde %s ----> si hubo balance \n", id, nombre); else fprintf(stdout, "Proceso %d, desde %s ----> no hubo balance \n", id, nombre); } /***** En este primer acercamiento se envía campo por campo ****/ void Envia_TDA(void *datos) { int i=0, vr=0; nodo *ap=NULL, *aux=NULL, *aux_2=NULL; e_TDA elem; MPI_Balance *param_bal=(MPI_Balance *)datos; while(!param_bal->MPI_SIGNAL_TERM) { if(sem_trywait(&signal)==0) { //Se realiza una validación para no enviarse a sí mismo los datos y/o evitar enviar un mensaje innecesario if(param_bal->MPI_DEST!=id && param_bal->MPI_ELEM) {//Se indica al proceso principal que si hubo balance vr=1; fprintf(stdout,"\n proceso %d -----> Hilo envía %d datos a %d...\n",id, param_bal->MPI_ELEM, param_bal->MPI_DEST); //se cierra el candado para garantizar la integridad de los datos Cierra_candados(); //Se manda el mensaje que indica los elementos a migrar. MPI_Send(&param_bal->MPI_ELEM, 1, MPI_INT, param_bal->MPI_DEST, CANTIDAD, MPI_COMM_WORLD); for(i=0; i<param_bal->MPI_ELEM; i++) { //Se obtiene el último elemento de la lista para su envío. ap=aux=*param_bal->TDA; while(ap->sig!=NULL) ap=ap->sig; //Se realiza una copia del nodo en el elemento de la unión para poder ser transferido. elem.ap=*ap; //Es importante inicializar el campo a nullo elem.ap.sig=NULL; //Se envía el nodo MPI_Send(elem.mensaje, STRUCTSIZE, MPI_CHAR, param_bal->MPI_DEST, ELEMENTO, MPI_COMM_WORLD); //Se inicializa el campo del anterior a NULL while(aux->sig!=ap) aux=aux->sig; // Se elimina el nodo de la lista

124

if(aux!=ap) aux->sig=NULL; else param_bal->TDA=&aux_2; free((void *)ap); } Abre_candados(); } } } pthread_exit((void *)&vr); } /***** Él(los) proceso(s) receptor(es) reconstruye(n) el TDA que les es enviado *****/ void Recibe_TDA(void *datos) { int num_elem=0, i=0, fuente=0, vr=0, bandera=0; e_TDA elem; nodo *ap=NULL; MPI_Balance *param_bal=(MPI_Balance *)datos; MPI_Status estado; do { //Se realiza una prueba, para ver si se han recibido mensajes MPI_Iprobe(MPI_ANY_SOURCE, CANTIDAD, MPI_COMM_WORLD, &bandera, &estado); if(bandera)//Verificación de recepción de mensajes. {//Se indica al proceso principal que si hubo balance vr=1; //Obtención de la fuente que envió el mensaje. fuente=estado.MPI_SOURCE; //Recepción de la cantidad de elementos a recibir. MPI_Recv(&num_elem, 1, MPI_INT, fuente, CANTIDAD, MPI_COMM_WORLD, &estado); fprintf(stdout, "\n El proceso %d recibe señal de %d ---> datos a recibir %d\n",id, fuente, num_elem); //Se cierra el candado para garantizar la integridad. Cierra_candados(); for(i=0; i<num_elem; i++) { ap=(nodo *)malloc(sizeof(nodo)); if(ap!=NULL) { MPI_Recv(elem.mensaje, STRUCTSIZE, MPI_CHAR, fuente, ELEMENTO, MPI_COMM_WORLD, &estado); *ap=elem.ap; /***********Aquí el usuario pondrá su función para la inserción de la lista *****/ inserta_nodo(param_bal->TDA, ap); } else perror("Error... Memoria Insuficiente, imposible recibir los elementos..."); } //Se habré el candado nuevamente. Abre_candados(); } }while(!param_bal->MPI_SIGNAL_TERM); pthread_exit((void *)&vr);

125

} /***** Función que cierra los candados para garantizar la integridad de los datos. *****/ void Cierra_candados(void) { pthread_mutex_lock(&candado); pthread_mutex_lock(&candado_estructura); } /***** Función que libera los candados *****/ void Abre_candados(void) { pthread_mutex_unlock(&candado); pthread_mutex_unlock(&candado_estructura); }

Listado “hilos_3.c” Este es el listado del programa de prueba utilizado para la creación de las rutinas de balance de carga. /***** Esta es una prueba con la versión final de la rutina de balance, la cual incluye el balance de cargas mediante hilos,

la forma en que se realiza el balance, es mediante el uso de uniones como se hizo en la versión ("uniones_b.c"). La forma de operar de este programa es similar a la versión anterior ("hilos_2.c").

Es decir, cada proceso obtiene su lista a partir de un archivo, después de unos lapsos de tiempo, se comenzara una simulación del balance de la carga, el momento del envió y el destino se hacen al azar. Cada proceso creará un archivo, en el cual imprime la lista, este proceso es el proceso de operaciones sobre los datos, en el cual se debe de garantizar la integridad de los mismos.

Los archivos que componen el proyecto en esta fase de prueba son: hilos_3.c balance.c operlis.c ent_sal.c protos.h *****/ #include "protos.h" /***** Prototipos auxiliares del proceso *****/ void proceso(MPI_Balance *elem); char *num_proc(int id); char da_digit(int num); main(int argc, char *argv[]) { nodo *lista; //Estructura que contiene los elementos necesarios para llevar a cabo el balance de carga MPI_Balance elem_bal; //Rutinas de iniciación para MPI. MPI_Init (&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &id); MPI_Comm_size(MPI_COMM_WORLD, &proc); MPI_Get_processor_name(nombre, &long_nom);

126

crea_lista(&lista); lista=obten_datos("/tmp/regis.txt"); //Creación del TDA a partir de un archivo. //Se inicializa el balance de carga MPI_Init_balance(&elem_bal,&lista); proceso(&elem_bal); //Se termina el balance de carga MPI_Finaliza_balance(&elem_bal); MPI_Finalize(); return 0; } void Monitor(void *datos) { MPI_Balance *par_bal=(MPI_Balance *)datos; time_t tiempo; int count=0, long_lista=0, vr=0; //Se inicializa la semilla para realizar las acciones al azar. srand((unsigned)time(&tiempo)+id); while(!par_bal->MPI_SIGNAL_TERM)//Verifica que el proceso no halla indicado el final de las operaciones. { Cierra_candados(); //Determina el destino al azar. par_bal->MPI_DEST=rand()%proc; //Se obtiene el tamaño de la lista para, ver cuantos elementos se pueden enviar long_lista=longitud_TDA(*par_bal->TDA); par_bal->MPI_ELEM=rand()%(long_lista/2); //Da la señal para que el proceso enviador comience el envío de los datos sem_post(&signal); Abre_candados(); //Espera máximo 10 segundos antes de realizar otro envío sleep((rand()%5)+5); } pthread_exit((void *)&vr); } /****** Este es el proceso encargado de las operaciones de los datos, Las operaciones que realiza son la escritura del arreglo cada cierto tiempo, en un archivo con el nombre del procesador y el proceso correspondiente. *****/ void proceso(MPI_Balance *elem) { int i=0, count=0; FILE *arch; char nom_arch[20]; //Estas tres funciones crean el nombre del archivo en el cual guardaran el arreglo cada cierto tiempo. strcpy(nom_arch,"./"); strcat(nom_arch,nombre); strcat(nom_arch,"_"); strcat(nom_arch,num_proc(id));//num_proc regresa el numero de proceso en una cadena. arch=fopen(nom_arch,"w"); if(arch!=NULL)

127

{ count=0; fprintf(arch,"Soy el Proceso:%d desde el procesador %s\n", id, nombre); while(count++<30) { //El hilo encargado de la migración de los datos no debe poder hacerlo mientras //se este operando sobre los mismos. fprintf(arch,"\n--------------------->iteración %d", count); //El usuario de las rutinas de balance deberá de implementar el candado en las operaciones de sus datos. Cierra_candados(); Printf(*elem->TDA, arch); fprintf(arch,"\t\t\t Número de elementos: %d\n",longitud_TDA(*elem->TDA)); Abre_candados(); sleep(2); } } else perror("Error no se pudo generar el archivo de salida..."); } /***** Funciones auxiliares para la creación del nombre del archivo para la salida. *****/ /***** Recibe el numero de proceso y lo convierte a cadena para ser agregado al nombre del archivo *****/ char *num_proc(int id) { char pross[4]; int dec=0, uni=0; pross[0]=da_digit(id/100); dec=id%100; pross[1]=da_digit(dec/10); uni=dec%10; pross[2]=da_digit(uni); pross[3]='\0'; return pross; } /***** Convierte números en caracteres *****/ char da_digit(int num) { char dig_let; switch(num) { case 0: dig_let='0'; break; case 1: dig_let='1'; break; case 2: dig_let='2'; break; case 3: dig_let='3'; break; case 4: dig_let='4'; break; case 5: dig_let='5'; break; case 6: dig_let='6'; break; case 7: dig_let='7'; break; case 8: dig_let='8'; break; case 9: dig_let='9'; break; default: break; }

128

return dig_let; }

129

Listado “operlis.c” En este archivo se encuentras las funciones necesarias para la operación de la lista, éstas sufrieron algunas modificaciones, fueron convertidas en procedimientos para que no tuviesen que regresar la lista como era el caso en la sección “Envío y Recepción de un nodo TDA lista”. /*** En este archivo se incluyen todas las funciones para el manejo de un TDA lista.

Por las situaciones que se presentan en la forma de enviar y recibir los datos, éstas deben ser procedimientos, es decir, deben de recibir la lista por referencia, para que pueda ser modificada sin tener que regresar la lista. ***/

#include "protos.h" /***** Inicializa la lista *****/ void crea_lista(nodo **lista) { *lista=NULL; } /***** Verifica si la lista se encuentra vacía *****/ int es_vacia(nodo *lista) { if(lista==NULL) return 1; else return 0; } /**** Creación de nodo de la lista ******/ nodo *crea_nodo(unsigned matricula, char *nombre, int edad, char sexo) { nodo *ap=(nodo *)malloc(sizeof(nodo)); if(ap!=NULL) { ap->matricula=matricula; strcpy(ap->nombre, nombre); ap->edad=edad; ap->sexo=sexo; ap->sig=NULL; } else perror("Error... Memoria insuficiente"); return ap; } /***** Inserción de nodo en la lista *****/ void inserta_nodo(nodo **lista, nodo *elem) { nodo *ap=*lista; if(es_vacia(ap)) *lista=elem; else { while(ap->sig!=NULL) ap=ap->sig; ap->sig=elem;

130

} } /***** Elimina un nodo de la lista *****/ void elimina_nodo(nodo **lista, nodo *elem) { nodo *ap=*lista, *aux=NULL; if(!es_vacia(*lista)) { if(ap->matricula==elem->matricula) { aux=*lista; *lista=aux->sig; free(aux); } else while(ap->sig!=NULL) { if(ap->sig->matricula==elem->matricula) { aux=ap->sig; ap->sig=aux->sig; free(aux); break; } ap=ap->sig; } } } /***** Elimina la lista completa *****/ void elimina_lista(nodo **lista) { nodo *ap=*lista; while(!es_vacia(*lista)) { ap=*lista; elimina_nodo(lista, ap); } *lista=NULL; } /***** Calcula el numero de nodos del TDA para su posterior uso *****/ int longitud_TDA(nodo *lista) { int cont=0; nodo *ap=lista; while(!es_vacia(ap)) { cont++; ap=ap->sig; } return cont; }

131

Listado “ent_sal.c” #include "protos.h" /***** Función encargada de crear el TDA lista a partir del archivo que se le pasa por parámetro.*/ nodo *obten_datos(char *archivo) { char nombre[40], sexo; int edad; unsigned matricula; nodo *ap=NULL; nodo *lista; FILE *leer; crea_lista(&lista); leer=fopen(archivo,"r"); if (leer!=NULL) { do { fscanf (leer, "%d", &matricula); fscanf (leer, "%[^\n]s", nombre); fscanf (leer, "%2d", &edad); fscanf (leer, "%c%*c", &sexo); ap=crea_nodo(matricula, nombre, edad, sexo); inserta_nodo(&lista, ap); }while (!feof(leer)); fclose(leer); } else perror("Error... No se pudor abrir el archivo"); return lista; } /***** Función encargada de la impresión en un archivo para que quede constancia del balance de carga *****/ void Printf(nodo *lista, FILE *arch) { nodo *ap=lista; fprintf(arch,"\n%10s | %-50s|%5s|%5s\n", "Matricula","Nombre", "Edad","Sexo"); fprintf(arch,"---------------------------------------------------------------------------\n"); while(ap!=NULL) { fprintf(arch,"%10u | %-50s|%5d|%5c\n", ap->matricula, ap->nombre, ap->edad, ap->sexo); ap=ap->sig; } }

132

Listados “Segunda Versión” Estos son los listados de las rutinas de balance de carga y las del programa de prueba, con las modificaciones hechas para la primera versión. Para los listados de algunos de los archivos no hay diferencia por lo que no son incluidos, sólo se hace la referencia de que no hubo cambio alguno.

Listado “protos.h” No hay cambio, ver listado primera versión.

Listado “def_TDA.h” No hay cambio, ver listado primera versión.

Listado “balance.c” /***** Esta es el archivo que lleva a cabo el balance de carga, no requiere mayores cambios por el usuario que los


#include "protos.h" void MPI_Init_balance(MPI_Balance *par_bal, nodo **lista) { //Se inicia el semáforo el cual indicará el momento para comenzar el balance sem_init(&signal,0,0); //Iniciación de la estructura //Se indica la dirección de los datos que podrían ser enviados a otro proceso par_bal->TDA=lista; //Se inicia el parámetro destino, con un valor igual al proceso par_bal->MPI_DEST=id; //Se inicia el número de elementos a enviar par_bal->MPI_ELEM=0; //Se inicia la señal que indica a los hilos que terminen par_bal->MPI_SIGNAL_TERM=0; //Iniciación de los hilos para el balance pthread_create(&envio, NULL, (void *)&Envia_TDA, (void *)par_bal); pthread_create(&recepcion, NULL, (void *)&Recibe_TDA, (void *)par_bal); //Esta Función no va a ser necesaria para el uso en general //Este hilo es el encargado de determinar a quien, cuantos y en que momento le serán enviados datos pthread_create(&monitor, NULL,(void *)&Monitor,(void *)par_bal); } void MPI_Finaliza_balance(MPI_Balance *par_bal) { int vr_env=0, vr_rec=0, vr_mon=0; //Se manda la señal a los hilos para que terminen su trabajo par_bal->MPI_SIGNAL_TERM=1; //Se espera la terminación de los hilos que realizan el balance de carga. //Y se guarda el valor de retorno.

133

pthread_join(monitor,(void *)&vr_mon); pthread_join(envio,(void *)&vr_env); pthread_join(recepcion, (void *)&vr_rec); if(vr_env || vr_rec) fprintf(stdout, "Proceso %d, desde %s ----> si hubo balance \n", id, nombre); else fprintf(stdout, "Proceso %d, desde %s ----> no hubo balance \n", id, nombre); } /***** En este primer acercamiento se envía campo por campo ****/ void Envia_TDA(void *datos) { int i=0, vr=0; nodo *ap=NULL, *aux=NULL, *aux_2=NULL; e_TDA elem; MPI_Balance *param_bal=(MPI_Balance *)datos; int longitud_lista=0; while(!param_bal->MPI_SIGNAL_TERM) { if(sem_trywait(&signal)==0) { //Se realiza una validación para no enviarse a sí mismo los datos y/o evitar enviar un mensaje innecesario if(param_bal->MPI_DEST!=id && param_bal->MPI_ELEM) {//Se indica al proceso principal que si hubo balance vr=1; fprintf(stdout,"\n proceso %d -----> Hilo envia %d datos a %d...\n",id, param_bal->MPI_ELEM, param_bal->MPI_DEST); //se cierra el candado para garantizar la integridad de los datos Cierra_candados(); //Se manda el mensaje que indica los elementos a migrar. MPI_Send(&param_bal->MPI_ELEM, 1, MPI_INT, param_bal->MPI_DEST, CANTIDAD, MPI_COMM_WORLD); for(i=0; i<param_bal->MPI_ELEM; i++) { ap=*param_bal->TDA; //Se realiza una copia del nodo en el elemento de la unión para poder ser transferido. elem.ap=*ap; //Es importante inicializar el campo a nullo elem.ap.sig=NULL; //Se envía el nodo MPI_Send(elem.mensaje, STRUCTSIZE, MPI_CHAR, param_bal->MPI_DEST, ELEMENTO, MPI_COMM_WORLD); //Se elimina el nodo de la lista elimina_nodo_lista_MPI(param_bal->TDA, ap->sig); } Abre_candados(); } } } pthread_exit((void *)&vr); } /***** Él(los) proceso(s) receptor(es) reconstruye(n) el TDA que les es enviado *****/ void Recibe_TDA(void *datos) {

134

int num_elem=0, i=0, fuente=0, vr=0, bandera=0; e_TDA elem; nodo *ap=NULL; MPI_Balance *param_bal=(MPI_Balance *)datos; MPI_Status estado; do { //Se realiza una prueba, para ver si se han recibido mensajes MPI_Iprobe(MPI_ANY_SOURCE, CANTIDAD, MPI_COMM_WORLD, &bandera, &estado); if(bandera)//Verificación de recepción de mensajes. {//Se indica al proceso principal que si hubo balance vr=1; //Obtención de la fuente que envío el mensaje. fuente=estado.MPI_SOURCE; //Recepción de la cantidad de elementos a recibir. MPI_Recv(&num_elem, 1, MPI_INT, fuente, CANTIDAD, MPI_COMM_WORLD, &estado); fprintf(stdout, "\n El proceso %d recibe señal de %d ---> datos a recibir %d\n",id, fuente, num_elem); //Se cierra el candado para garantizar la integridad. Cierra_candados(); for(i=0; i<num_elem; i++) { ap=(nodo *)malloc(sizeof(nodo)); if(ap!=NULL) { MPI_Recv(elem.mensaje, STRUCTSIZE, MPI_CHAR, fuente, ELEMENTO, MPI_COMM_WORLD, &estado); *ap=elem.ap; inserta_nodo_lista_MPI(param_bal->TDA, ap); } else perror("Error... Memoria Insuficiente, imposible recibir los elementos..."); } //Se abre el candado nuevamente. Abre_candados(); } }while(!param_bal->MPI_SIGNAL_TERM); pthread_exit((void *)&vr); } void Cierra_candados(void) { pthread_mutex_lock(&candado); pthread_mutex_lock(&candado_estructura); } void Abre_candados(void) { pthread_mutex_unlock(&candado); pthread_mutex_unlock(&candado_estructura); }

Listado “Hilos_3.c” No hay cambio, ver listado primera versión.

135

Listado “operlis.c” No hay cambio, ver listado primera versión.

Listado “ent_sal.c” No hay cambio, ver listado primera versión.

Listado “MPI_lista.c”

Este archivo contiene las funciones de inserción y eliminación de nodos las cuales son llamadas en algún momento por las rutinas de balance de carga, se pretende que éste sea obtenido a partir del programa “scan” el cual fue modificado para la generación de estas funciones en esta sección. /***** Archivo obtenido de la búsqueda realizada para la obtención de la estructura necesaria para la creación del TDA

lista *****/ #include "protos.h" /***** Inserción de nodo en la lista *****/ void inserta_nodo_lista_MPI(nodo **lista, nodo *elem) { nodo *ap=*lista; if(es_vacia(ap)) *lista=elem; else { while(ap->sig!=NULL) ap=ap->sig; ap->sig=elem; } } /***** Elimina un nodo de la lista *****/ void elimina_nodo_lista_MPI(nodo **lista, nodo *elem) { nodo *ap=*lista, *aux=NULL; if(!es_vacia(*lista)) { if(ap=elem) { aux=*lista; *lista=aux->sig; free(aux); } else while(ap->sig!=NULL) { if(ap->sig==elem->sig) { aux=ap->sig; ap->sig=aux->sig; free(aux); break; }

136

ap=ap->sig; } } }

137

Listado “scan.c” Esta es la versión final del programa “scan” el cual es capaza obtener el nombre del campo en la estructura el cual es el apuntador al siguiente elemento. #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXCAD 20000 #define RE_END 0 //Registra Estructura t Termina #define RL_SBE 1 //Registra Linea y Sigue Buscando Estructura #define RL_BNE 2 //Regis tra Linea y Busca Nueva Estructura #define NR_SBE 4 //No Registres y Sigue Buscando Estructura /***** Estructura auxiliar para la identificación del registro de los TDA's *****/ typedef struct estruct_reg reg; struct estruct_reg { char *str_reg; char *token; reg *sig; }; /***** Funciones para la búsqueda de la estructura *****/ reg *busca_estructuras(char *tda, FILE *flujo, reg *col_dat); char *obten_bloque(FILE *flujo); void descarta_funcion(FILE *flujo); /***** Funciones de verificación *****/ int existe(char *linea,reg *cola); int token_reg(char *linea, reg *cola); int dato_c(char *decl); int verifica_exist(char *linea, char *tda, char *nueva_str); int verifica_campos(char *estruc, reg *cola, char *ntok); int existe_asterisco(char *ptr_sig); /***** Funciones para el manejo de los TDA's utilizados para el registro *****/ reg *crea_nodo(char *linea, char *token); reg *encola(reg *cola, reg *ap); reg *registra_TDA(char *linea, char *aux, reg *col_dat, FILE *flujo); void crea_arout(reg *estructuras, FILE *salida, char *tda); void busca_ptr_sig(char *struc, char *ptr_sig); void crea_func(char *ptr_sig); main(int argc, char *argv[]) { FILE *flujo, *salida; reg *estructuras=NULL; if(argc>2) { if((flujo=fopen(argv[1],"r"))!=NULL) { printf("\t Escaneando archivo \"%s\" \n", argv[1]); printf("\t\t Buscando TDA --> %s... \n", argv[2]);

138

printf("\t\t Creando archivo de salida...\n"); if((salida=fopen("./def_TDA.h","w"))!=NULL) { //La función busca la estructura y regresa un TDA con toda la información de la misma estructuras=busca_estructuras(argv[2], flujo, estructuras); //Se guardan las estructuras en un archivo y se cierran los flujos crea_arout(estructuras, salida, argv[2]); fclose(flujo); fclose(salida); } else perror("Error... No se puede crear el archivo de salida"); } else perror("Error... Al abrir el archivo, verifique ruta y nombre"); } else { if(argc==2) perror("Error... Argumentos insuficientes"); else perror("Error... sin argumentos en main()\n"); printf("\t Prueba con: %s <archivo.c | archivo.h> <tda>\n\n",argv[0]); printf("\t<archivo.c | archivo.h>: archivo fuente en donde se deberá buscar la estructura \n"); printf("\t <tda>: es el nombre de la estructura a ser buscada \n"); } return 0; } /********** Funciones que auxilian a la búsqueda del TDA *********/ //Esta función es la encargada de recorrer todo el archivo en busca del TDA //lo hace por bloques que pudiesen ser una estructura reg *busca_estructuras(char *tda, FILE *flujo, reg *col_dat) { char linea[MAXCAD]="", nueva_str[MAXCAD]="", aux[MAXCAD]; int vr=0, salir=0, k=0; fpos_t *inicio; reg *ap=NULL; strcpy(aux,tda); while(!feof(flujo)) { //La función regresa un bloque que pudiera ser una estructura strcpy(linea, obten_bloque(flujo)); // Busca en el bloque el tda que solicitado vr=verifica_exist(linea, aux, nueva_str); switch(vr) { case RE_END: //Esta opción indica que el TDA ha sido encontrado col_dat=registra_TDA(linea, aux, col_dat, flujo);

139

salir=1; break; case RL_SBE: //Esta opción indica que se trata de una redefinición, //pero se sigue buscando la misma estructura col_dat=registra_TDA(linea, aux, col_dat, flujo); salir=0; break; case RL_BNE: //Esta indica que se trata de una redefinición y se buscara la original col_dat=registra_TDA(linea, aux, col_dat, flujo); strcpy(aux, nueva_str); salir=0; break; default: //no se ha encontrado nada relacionado con la estructura break; } if(salir) break; } return col_dat; } //Esta función es la encargada de buscar en el archivo, lo hace por bloques que pudiesen ser //declaraciones de estructuras, sólo regresa los posibles candidatos. //Es capas de ignorar prototipos, archivos de inclusión y funciones. char *obten_bloque(FILE *flujo) { int llave=0, term_lin=0, paren_a=0, paren_c=0, i=0; char linea[MAXCAD]; /*El siguiente ciclo es capaz de encontrar bloques que puedan ser considerados como una estructura.*/ while(!feof(flujo)) { linea[i]=fgetc(flujo); switch(linea[i]) { //Ignora los archivos de cabecera case '#': while(!feof(flujo)) if(fgetc(flujo)=='\n') break; i=0; break; //verifica si no hay llaves abiertas para salir case ';': if(paren_a && paren_c)//Descarta los prototipos paren_a=paren_c=i=0; else { if(llave==0) term_lin=1; i++; } break; //Elimina los saltos de línea y tabuladores innecesarios case '\n': break; case '\t': break;

140

//Registra si se han abierto o cerrado llaves case '{': if(paren_a && paren_c) { //Evita buscar la definición dentro de una función descarta_funcion(flujo); paren_a=paren_c=i=llave=0; } else llave++; i++; break; case '}': llave--; i++; break; //Registra si se encuentra posiblemente una función case '(': paren_a++; i++; break; case ')': paren_c++; i++; break; default: i++; } if(term_lin) //Pone el fin de linea { linea[i]='\0'; break; } } return linea; } //Esta función se encarga de eliminar lo que se considera como el cuerpo de la función void descarta_funcion(FILE *flujo) { int llave=1; char basura; while(!feof(flujo)) { switch(fgetc(flujo)) { case '{': llave++; break; case '}': llave--; break; default: break; } if(!llave) break; } } /****** Funciones que auxilian en la identificación, registro y verificación del TDA y sus campos *****/ //Esta función se encarga de verificar si la linea ya fue registrada, para evitar duplicarla int existe(char *linea, reg *cola) { reg *ap=cola; int vr=0, iguales=0; while(ap!=NULL) { iguales=strcmp(linea,ap->str_reg); if(iguales==0)

141

{ vr=1; break; } ap=ap->sig; } return vr; } //Verifica si un token ya fue buscado, para evitar buscarlo nuevamente al verificar los campos de la estructura. int token_reg(char *linea, reg *cola) { reg *ap=cola; int vr=0; while(ap!=NULL) { vr=strcmp(linea,ap->token); if(vr==0) { vr=1; break; } ap=ap->sig; } return vr; } //Esta función es la encargada de verificar si el bloque que le es pasado //es el TDA buscado int verifica_exist(char *linea, char *tda, char *nueva_str) { int salida=NR_SBE,j=0,i=0; char typedef_[]="typedef"; //cadena para determinar si la estructura pasada es un redefinición. size_t tam_sub=strlen(typedef_), tam_cad=strlen(linea); //Esta función es la encargada de determinar si el TDA buscado se encuentra en //en el bloque, si no se encuentra regresa un NULL char *tipo=strstr(linea,tda); size_t tam_tipo=0; //Posiblemente se trata de la definición if(tipo!=NULL) { tam_tipo=strlen(tipo); //Verifica si se trata de una redefinición if(strstr(linea, typedef_)!=NULL) { //verifica si es el nombre de la estructura // o es la redefinición. if(tam_tipo-1==strlen(tda)) { for(i=tam_sub+1, j=0; i<tam_cad-tam_tipo-1; i++, j++) nueva_str[j]=linea[i];

142

nueva_str[i]='\0'; salida=RL_BNE; } else { //Si la redefinición esta junto con la estructura if(strstr(linea,"{")) salida=RE_END; //Solamente se trata de la redefinición. else salida=RL_SBE; } } //La estructura ha sido encontrada. else { printf("\t Estructura encontrada \n\t"); printf("\t\t%s\n",linea); salida=RE_END; } } return salida; } //Verifica que los campos del TDA sean tipos de datos reconocidos una vez que esta ha sido encontrado, //si alguno de los campos no es reconocido realiza la búsqueda de este mismo int verifica_campos(char *estruc, reg *cola, char *ntok) { char *aux, *cadmod, *tipo; char delim[]=";"; int i=0, j=0, vr=1; //pide memoria para la realización de su trabajo cadmod=(char *)malloc(sizeof(char)*strlen(estruc)+1); tipo=(char *)malloc(sizeof(char)*strlen(estruc)+1); if(cadmod != NULL && tipo!=NULL) { //Busca el cuerpo de la estructura, para obtener los campos while(estruc[i++]!='{'); //Copia los campos de la estructura a una nueva cadena for(j=0; i<strlen(estruc)-2; j++, i++) cadmod[j]=estruc[i]; cadmod[j]='\0'; //Obtiene campo por campo mediante el delimitador ";" aux=strtok(cadmod, delim); while(aux!=NULL) { if(aux!=NULL) { i=0; //Este ciclo obtiene el tipo de dato de la declaración while(aux[i++]!=' ')

143

tipo[i-1]=aux[i-1]; tipo[i-1]='\0'; if(!dato_c(tipo)) //verifica si se trata de un tipo de dato de C { //Verifica si se trata de una estructura ya registrada if(!token_reg(tipo, cola)) { //Copia el nuevo token para seguir buscando for(i=0; tipo[i]!='\0'; i++) ntok[i]=tipo[i]; vr=0; //Regresa un valor de error. break; } } } aux=strtok(NULL, delim); } } else perror("Error... Memoria insuficiente"); return vr; } //Determina si el tipo de dato que se le pasa es un tipo de dato de C int dato_c(char *decl) { char *tipo=NULL; if(strstr(decl,"char")!=NULL) return 1; if(strstr(decl,"int")!=NULL) return 1; if(strstr(decl,"unsigned")!=NULL) return 1; if(strstr(decl,"long")!=NULL) return 1; if(strstr(decl,"float")!=NULL) return 1; if(strstr(decl,"double")!=NULL) return 1; if(tipo==NULL) return 0; } /***** Funciones para el de los TDA utilizados en la búsqueda de los TDA's ****/ reg *crea_nodo(char *linea, char *token) { reg *ap=NULL; ap=(reg *)malloc(sizeof(ap)); if(ap!=NULL) { ap->str_reg=(char *)malloc(strlen(linea)+1); ap->token=(char *)malloc(strlen(token)+1); if(ap->str_reg!=NULL && ap->token!=NULL)

144

{ strcpy(ap->str_reg, linea); strcpy(ap->str_reg, linea); ap->sig=NULL; } else perror("Error... Memoria insuficiente"); } else perror("Error... Memoria insuficiente"); return ap; } reg *encola(reg *cola, reg *ap) { reg *aux=cola; if(aux==NULL) cola=ap; else { while(aux->sig!=NULL) aux=aux->sig; aux->sig=ap; } return cola; } //Función encargada de registrar lo relacionado con la búsqueda //verifica primero si no ha sido registrada, para evitar duplicidad reg *registra_TDA(char *linea, char *aux, reg *col_dat, FILE *flujo) { reg *ap=NULL; int campo=1; //Verifica el registro de la linea if(!existe(linea, col_dat)) { ap=crea_nodo(linea, aux); col_dat=encola(col_dat, ap); } do { //Si alguno de los campos no existe se llama a la función para su búsqueda desde el inicio campo=verifica_campos(linea, col_dat, aux); if(!campo) { rewind(flujo); col_dat=busca_estructuras(aux, flujo, col_dat); } }while(campo==0); return col_dat; }

145

//Función encargada escribir en el archivo de salida el resultado de la búsqueda void crea_arout(reg *estructuras, FILE *salida, char *tda) { reg *ap=NULL; int encon_ptr_sig=0; char ptr_sig[20]=""; if(estructuras!=NULL) { //Escribe un redefinición del TDA para que sea usado por el programa realizado //en la parte I fprintf(salida,"\n typedef struct %s nodo;\n", tda); do { ap=estructuras; fprintf(salida, "%s\n", ap->str_reg); if(!encon_ptr_sig) { encon_ptr_sig=existe_asterisco(ap->str_reg); if(encon_ptr_sig) { busca_ptr_sig(ap->str_reg, ptr_sig); printf("\t El apuntador al siguiente nodo es: %s\n",ptr_sig); } } estructuras=estructuras->sig; free(ap); }while(estructuras!=NULL); crea_func(ptr_sig); } else printf("La estructura no ha sido encontrada...\n"); } /***** Verifica que en la línea se encuentre el * el cual es el indicador del campo que apunta al siguiente elemento en una lista. *****/ int existe_asterisco(char *ptr_sig) { int i=0, vr=0; while(ptr_sig[i]!='\0') if(ptr_sig[i++]=='*') { vr=1; break; } return vr; } /***** Esta función obtiene el nombre del campo, el cual es un apuntador a un elemento del mismo tipo, necesario para la creación del TDA lista *****/ void busca_ptr_sig(char *struc, char *ptr_sig)

146

{ char *aux, *aux2; aux=strtok(struc,";"); while(aux!=NULL) { aux=strtok(NULL,";"); if(existe_asterisco(aux)) { aux2=strtok(aux,"*"); aux2=strtok(NULL,"*"); strcpy(ptr_sig, aux2); break; } } } /***** Esta función crea el archivo que contiene las funciones para la inserción y eliminación de nodos que son llamadas por las funciones Envia_TDA y Recibe_TDA respectivamente *****/ void crea_func(char *ptr_sig) { FILE *fuente, *salida; char caracter; fuente=fopen("./MPI_lista.orig","rb"); //Archivo que contiene la estructura principal de las funciones. salida=fopen("./MPI_lista.c","wb"); if(fuente!=NULL && salida!=NULL) { while(!feof(fuente)) { fread(&caracter, sizeof(char), 1, fuente); //El carácter @ indica que este será substituido por el campo que es un apuntador if(caracter!='@') fwrite(&caracter, sizeof(char), 1, salida); else fwrite(ptr_sig, sizeof(char),strlen(ptr_sig),salida); } fseek(salida,-1,SEEK_END); //Esta ultima escritura es para evitar que sea repetido el ultimo carácter, //es posible que no sea necesaria, si se tiene problemas se deberá comentar. caracter=' '; fwrite(&caracter, sizeof(char), 1, salida); fclose(fuente); fclose(salida); } else perror("No se puede crear el archivo de salida necesario para el manejo del TDA lista...."); }

147

9.4. Anexo D (Códigos Fuentes Versión final)

Listado “protos.h” #include <semaphore.h> #include <pthread.h> #include "mpi.h" #include "def_TDA.h" //Este archivo de inclusión si será incluido en el proyecto final, //incluye la definición del TDAS que se va a utilizar. #define CANTIDAD 0 #define ELEMENTO 1 #define COORDINADOR 0 #define STRUCTSIZE sizeof(nodo) /***** Estructura utilizada para lograr el balance del TDA *****/ typedef union Nodos_TDA e_TDA; union Nodos_TDA { nodo ap; char mensaje[STRUCTSIZE]; }; /***** Estructura de datos necesaria para que los hilos puedan manejar el TDA y la migración de datos a otros nodos del cluster *****/ typedef struct Parametros_Balance { nodo **TDA; int MPI_DEST; int MPI_ELEM; int MPI_SIGNAL_TERM; }MPI_Balance; sem_t signal; //Señal para indicar al hilo que envié los datos a otros nodos. pthread_t envio, recepción, monitor; //hilo para el manejo de los datos pthread_mutex_t candado, candado_estructura; //Candado para garantizar la exclusión mutua. /***** Prototipos de las funciones encargadas del balance de la carga ****/ void MPI_Init_balance(MPI_Balance *par_bal, nodo **lista); void MPI_Finaliza_balance(MPI_Balance *par_bal); void Envia_TDA(void *datos); void Recibe_TDA(void *datos); void Monitor(void *datos); void Cierra_candados(void); void Abre_candados(void); void Inicia_balance(void); /***** Funciones obtenidas con el programa scan de la sección 2 *****/ void inserta_nodo_lista_MPI(nodo **lista, nodo *elem); void elimina_nodo_lista_MPI(nodo **lista, nodo *elem);

148

void Asigna_null_asig(nodo *ap);

Listado “MPI_lista.orig” /***** Archivo obtenido de la búsqueda realizada para la obtención de la estructura necesaria para la creación del TDA

lista *****/ #include "protos.h" /***** Inserción de nodo en la lista *****/ void inserta_nodo_lista_MPI(nodo **lista, nodo *elem) { nodo *ap=*lista; if(es_vacia(ap)) *lista=elem; else { while(ap->@!=NULL) ap=ap->@; ap->@=elem; } } /***** Elimina un nodo de la lista *****/ void elimina_nodo_lista_MPI(nodo **lista, nodo *elem) { nodo *ap=*lista, *aux=NULL; if(!es_vacia(*lista)) { if(ap=elem) { aux=*lista; *lista=aux->@; free(aux); } else while(ap->@!=NULL) { if(ap->@==elem->@) { aux=ap->@; ap->sig=aux->@; free(aux); break; } ap=ap->@; } } } /***** Inicia el apuntador al siguiente elemento de la lista con NULL *****/ void Asigna_null_asig(nodo *ap) { ap->@=NULL; }

149

Listado “balance.c” /***** Esta es el archivo que lleva a cabo el balance de carga, no requiere mayores cambios por el usuario que los


#include "protos.h" void MPI_Init_balance(MPI_Balance *par_bal, nodo **lista) { //Se inicia el semáforo el cual indicará el momento para comenzar el balance sem_init(&signal,0,0); //Iniciación de la estructura //Se indica la dirección de los datos que podrían ser enviados a otro proceso par_bal->TDA=lista; //Se inicia el parámetro destino, con un valor igual al proceso par_bal->MPI_DEST=0; //Se inicia el número de elementos a enviar par_bal->MPI_ELEM=0; //Se inicia la señal que indica a los hilos que terminen par_bal->MPI_SIGNAL_TERM=0; //Iniciación de los hilos para el balance pthread_create(&envio, NULL, (void *)&Envia_TDA, (void *)par_bal); pthread_create(&recepcion, NULL, (void *)&Recibe_TDA, (void *)par_bal); //Esta Función no va a ser necesaria para el uso en general //Este hilo es el encargado de determinar a quien, cuantos y en que momento le serán enviados datos pthread_create(&monitor, NULL,(void *)&Monitor,(void *)par_bal); } void MPI_Finaliza_balance(MPI_Balance *par_bal) { int vr_env=0, vr_rec=0, vr_mon=0; //Se manda la señal a los hilos para que terminen su trabajo par_bal->MPI_SIGNAL_TERM=1; //Se espera la terminación de los hilos que realizan el balance de carga. //Y se guarda el valor de retorno. pthread_join(monitor,(void *)&vr_mon); pthread_join(envio,(void *)&vr_env); pthread_join(recepcion, (void *)&vr_rec); } /***** En este primer acercamiento se envía campo por campo ****/ void Envia_TDA(void *datos) { int i=0, vr=0; nodo *ap=NULL, *aux=NULL, *aux_2=NULL; e_TDA elem; MPI_Balance *param_bal=(MPI_Balance *)datos; int longitud_lista=0; while(!param_bal->MPI_SIGNAL_TERM)

150

{ if(sem_trywait(&signal)==0) { //Se realiza una validación para no enviarse a sí mismo los datos y/o evitar enviar un mensaje innecesario if(param_bal->MPI_DEST!=id && param_bal->MPI_ELEM) {//Se indica al proceso principal que si hubo balance vr=1; //se cierra el candado para garantizar la integridad de los datos Cierra_candados(); //Se manda el mensaje que indica los elementos a migrar. MPI_Send(&param_bal->MPI_ELEM, 1, MPI_INT, param_bal->MPI_DEST, CANTIDAD, MPI_COMM_WORLD); for(i=0; i<param_bal->MPI_ELEM; i++) { ap=*param_bal->TDA; //Se realiza una copia del nodo en el elemento de la unión para poder ser transferido. elem.ap=*ap; //Es importante inicializar el campo a nullo Asigna_null_asig(&elem.ap); //Se envía el nodo MPI_Send(elem.mensaje, STRUCTSIZE, MPI_CHAR, param_bal->MPI_DEST, ELEMENTO, MPI_COMM_WORLD); //Se elimina el nodo de la lista elimina_nodo_lista_MPI(param_bal->TDA, ap->sig); } Abre_candados(); } } } pthread_exit((void *)&vr); } /***** Él(los) proceso(s) receptor(es) reconstruye(n) el TDA que les es enviado *****/ void Recibe_TDA(void *datos) { int num_elem=0, i=0, fuente=0, vr=0, bandera=0; e_TDA elem; nodo *ap=NULL; MPI_Balance *param_bal=(MPI_Balance *)datos; MPI_Status estado; do { //Se realiza una prueba, para ver si se han recibido mensajes MPI_Iprobe(MPI_ANY_SOURCE, CANTIDAD, MPI_COMM_WORLD, &bandera, &estado); if(bandera)//Verificación de recepción de mensajes. {//Se indica al proceso principal que si hubo balance vr=1; //Obtención de la fuente que envío el mensaje. fuente=estado.MPI_SOURCE; //Recepción de la cantidad de elementos a recibir. MPI_Recv(&num_elem, 1, MPI_INT, fuente, CANTIDAD, MPI_COMM_WORLD, &estado); //Se cierra el candado para garantizar la integridad. Cierra_candados(); for(i=0; i<num_elem; i++) {

151

ap=(nodo *)malloc(sizeof(nodo)); if(ap!=NULL) { MPI_Recv(elem.mensaje, STRUCTSIZE, MPI_CHAR, fuente, ELEMENTO, MPI_COMM_WORLD, &estado); *ap=elem.ap; inserta_nodo_lista_MPI(param_bal->TDA, ap); } else perror("Error... Memoria Insuficiente, imposible recibir los elementos..."); } //Se habré el candado nuevamente. Abre_candados(); } }while(!param_bal->MPI_SIGNAL_TERM); pthread_exit((void *)&vr); } void Cierra_candados(void) { pthread_mutex_lock(&candado); pthread_mutex_ lock(&candado_estructura); } void Abre_candados(void) { pthread_mutex_unlock(&candado); pthread_mutex_unlock(&candado_estructura); } void Inicia_balance(void) { sem_post(&signal); }

152

Listado “scan.c” #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXCAD 20000 #define RE_END 0 //Registra Estructura t Termina #define RL_SBE 1 //Registra Línea y Sigue Buscando Estructura #define RL_BNE 2 //Registra Línea y Busca Nueva Estructura #define NR_SBE 4 //No Registres y Sigue Buscando Estructura /***** Estructura auxiliar para la identificación del registro de los TDA's *****/ typedef struct estruct_reg reg; struct estruct_reg { char *str_reg; char *token; reg *sig; }; /***** Funciones para la búsqueda de la estructura *****/ reg *busca_estructuras(char *tda, FILE *flujo, reg *col_dat); char *obten_bloque(FILE *flujo); void descarta_funcion(FILE *flujo); /***** Funciones de verificación *****/ int existe(char *linea,reg *cola); int token_reg(char *linea, reg *cola); int dato_c(char *decl); int verifica_exist(char *linea, char *tda, char *nueva_str); int verifica_campos(char *estruc, reg *cola, char *ntok); int existe_asterisco(char *ptr_sig); /***** Funciones para el manejo de los TDA's utilizados para el registro *****/ reg *crea_nodo(char *linea, char *token); reg *encola(reg *cola, reg *ap); reg *registra_TDA(char *linea, char *aux, reg *col_dat, FILE *flujo); void crea_arout(reg *estructuras, FILE *salida, char *tda); void busca_ptr_sig(char *struc, char *ptr_sig); void crea_func(char *ptr_sig); main(int argc, char *argv[]) { FILE *flujo, *salida; reg *estructuras=NULL; if(argc>2) { if((flujo=fopen(argv[1],"r"))!=NULL) { printf("\t Escaneando archivo \"%s\" \n", argv[1]); printf("\t\t Buscando TDA --> %s... \n", argv[2]); printf("\t\t Creando archivo de salida...\n"); if((salida=fopen("./def_TDA.h","w"))!=NULL)

153

{ //La función busca la estructura y regresa un TDA con toda la información de la misma estructuras=busca_estructuras(argv[2], flujo, estructuras); //Se guardan las estructuras en un archivo y se cierran los flujos crea_arout(estructuras, salida, argv[2]); fclose(flujo); fclose(salida); } else perror("Error... No se puede crear el archivo de salida"); } else perror("Error... Al abrir el archivo, verifique ruta y nombre"); } else { if(argc==2) perror("Error... Argumentos insuficientes"); else perror("Error... sin argumentos en main()\n"); printf("\t Prueba con: %s <archivo.c | archivo.h> <tda>\n\n",argv[0]); printf("\t<archivo.c | archvio.h>: archivo fuente en donde se deberá buscar la estructura \n"); printf("\t <tda>: es el nombre de la estructura a ser buscada \n"); } return 0; } /********** Funciones que auxilian a la búsqueda del TDA *********/ //Esta función es la encargada de recorrer todo el archivo en busca del TDA //lo hace por bloques que pudiesen ser una estructura reg *busca_estructuras(char *tda, FILE *flujo, reg *col_dat) { char linea[MAXCAD]="", nueva_str[MAXCAD]="", aux[MAXCAD]; int vr=0, salir=0, k=0; fpos_t *inicio; reg *ap=NULL; strcpy(aux,tda); while(!feof(flujo)) { //La función regresa un bloque que pudiera ser una estructura strcpy(linea, obten_bloque(flujo)); // Busca en el bloque el tda que solicitado vr=verifica_exist(linea, aux, nueva_str); switch(vr) { case RE_END: //Esta opción indica que el TDA ha sido encontrado col_dat=registra_TDA(linea, aux, col_dat, flujo); salir=1; break;

154

case RL_SBE: //Esta opción indica que se trata de una redefinición, //pero se sigue buscando la misma estructura col_dat=registra_TDA(linea, aux, col_dat, flujo); salir=0; break; case RL_BNE: //Esta indica que se trata de una redefinición y se buscara la original col_dat=registra_TDA(linea, aux, col_dat, flujo); strcpy(aux, nueva_str); salir=0; break; default: //no se ha encontrado nada relacionado con la estructura break; } if(salir) break; } return col_dat; } //Esta función es la encargada de buscar en el archivo, lo hace por bloques que pudiesen ser //declaraciones de estructuras, sólo regresa los posibles candidatos. //Es capas de ignorar prototipos, archivos de inclusión y funciones. char *obten_bloque(FILE *flujo) { int llave=0, term_lin=0, paren_a=0, paren_c=0, i=0; char linea[MAXCAD]; /*El siguiente ciclo es capaz de encontrar bloques que puedan ser considerados como una estructura.*/ while(!feof(flujo)) { linea[i]=fgetc(flujo); switch(linea[i]) { //Ignora los archivos de cabecera case '#': while(!feof(flujo)) if(fgetc(flujo)=='\n') break; i=0; break; //verifica si no hay llaves abiertas para salir case ';': if(paren_a && paren_c)//Descarta los prototipos paren_a=paren_c=i=0; else { if(llave==0) term_lin=1; i++; } break; //Elimina los saltos de línea y tabuladores innecesarios case '\n': break; case '\t': break; //Registra si se han abierto o cerrado llaves case '{': if(paren_a && paren_c)

155

{ //Evita buscar la definición dentro de una función descarta_funcion(flujo); paren_a=paren_c=i=llave=0; } else llave++; i++; break; case '}': llave--; i++; break; //Registra si se encuentra posiblemente una función case '(': paren_a++; i++; break; case ')': paren_c++; i++; break; default: i++; } if(term_lin) //Pone el fin de línea { linea[i]='\0'; break; } } return linea; } //Esta función se encarga de eliminar lo que se considera como el cuerpo de la función void descarta_funcion(FILE *flujo) { int llave=1; char basura; while(!feof(flujo)) { switch(fgetc(flujo)) { case '{': llave++; break; case '}': llave--; break; default: break; } if(!llave) break; } } /****** Funciones que auxilian en la identificación, registro y verificación del TDA y sus campos *****/ //Esta función se encarga de verificar si la línea ya fue registrada, para evitar duplicarla int existe(char *linea, reg *cola) { reg *ap=cola; int vr=0, iguales=0; while(ap!=NULL) { iguales=strcmp(linea,ap->str_reg); if(iguales==0) { vr=1;

156

break; } ap=ap->sig; } return vr; } //Verifica si un token ya fue buscado, para evitar buscarlo nuevamente al verificar los campos de la estructura. int token_reg(char *linea, reg *cola) { reg *ap=cola; int vr=0; while(ap!=NULL) { vr=strcmp(linea,ap->token); if(vr==0) { vr=1; break; } ap=ap->sig; } return vr; } //Esta función es la encargada de verificar si el bloque que le es pasado //es el TDA buscado int verifica_exist(char *linea, char *tda, char *nueva_str) { int salida=NR_SBE,j=0,i=0; char typedef_[]="typedef"; //cadena para determinar si la estructura pasada es un redefinición. size_t tam_sub=strlen(typedef_), tam_cad=strlen(linea); //Esta función es la encargada de determinar si el TDA buscado se encuentra en //en el bloque, si no se encuentra regresa un NULL char *tipo=strstr(linea,tda); size_t tam_tipo=0; //Posiblemente se trata de la definición if(tipo!=NULL) { tam_tipo=strlen(tipo); //Verifica si se trata de una redefinición if(strstr(linea, typedef_)!=NULL) { //verifica si es el nombre de la estructura // o es la redefinición. if(tam_tipo-1==strlen(tda)) { for(i=tam_sub+1, j=0; i<tam_cad-tam_tipo-1; i++, j++) nueva_str[j]=linea[i]; nueva_str[i]='\0'; salida=RL_BNE;

157

} else { //Si la redefinición esta junto con la estructura if(strstr(linea,"{")) salida=RE_END; //Solamente se trata de la redefinición. else salida=RL_SBE; } } //La estructura ha sido encontrada. else { printf("\t Estructura encontrada \n\t"); printf("\t\t%s\n",linea); salida=RE_END; } } return salida; } //Verifica que los camp os del TDA sean tipos de datos reconocidos una vez que esta ha sido encontrado, //si alguno de los campos no es reconocido realiza la búsqueda de este mismo int verifica_campos(char *estruc, reg *cola, char *ntok) { char *aux, *cadmod, *tipo; char delim[]=";"; int i=0, j=0, vr=1; //pide memoria para la realización de su trabajo cadmod=(char *)malloc(sizeof(char)*strlen(estruc)+1); tipo=(char *)malloc(sizeof(char)*strlen(estruc)+1); if(cadmod != NULL && tipo!=NULL) { //Busca el cuerpo de la estructura, para obtener los campos while(estruc[i++]!='{'); //Copia los campos de la estructura a una nueva cadena for(j=0; i<strlen(estruc)-2; j++, i++) cadmod[j]=estruc[i]; cadmod[j]='\0'; //Obtiene campo por campo mediante el delimitador ";" aux=strtok(cadmod, delim); while(aux!=NULL) { if(aux!=NULL) { i=0; //Este ciclo obtiene el tipo de dato de la declaración while(aux[i++]!=' ') tipo[i-1]=aux[i-1]; tipo[i-1]='\0';

158

if(!dato_c(tipo)) //verifica si se trata de un tipo de dato de C { //Verifica si se trata de una estructura ya registrada if(!token_reg(tipo, cola)) { //Copia el nuevo token para seguir buscando for(i=0; tipo[i]!='\0'; i++) ntok[i]=tipo[i]; vr=0; //Regresa un valor de error. break; } } } aux=strtok(NULL, delim); } } else perror("Error... Memoria insuficiente"); return vr; } //Determina si el tipo de dato que se le pasa es un tipo de dato de C int dato_c(char *decl) { char *tipo=NULL; if(strstr(decl,"char")!=NULL) return 1; if(strstr(decl,"int")!=NULL) return 1; if(strstr(decl,"unsigned")!=NULL) return 1; if(strstr(decl,"long")!=NULL) return 1; if(strstr(decl,"float")!=NULL) return 1; if(strstr(decl,"double")!=NULL) return 1; if(tipo==NULL) return 0; } /***** Funciones para el de los TDA utilizados en la búsqueda de los TDA's ****/ reg *crea_nodo(char *linea, char *token) { reg *ap=NULL; ap=(reg *)malloc(sizeof(ap)); if(ap!=NULL) { ap->str_reg=(char *)malloc(strlen(linea)+1); ap->token=(char *)malloc(strlen(token)+1); if(ap->str_reg!=NULL && ap->token!=NULL) { strcpy(ap->str_reg, linea);

159

strcpy(ap->str_reg, linea); ap->sig=NULL; } else perror("Error... Memoria insuficiente"); } else perror("Error... Memoria insuficiente"); return ap; } reg *encola(reg *cola, reg *ap) { reg *aux=cola; if(aux==NULL) cola=ap; else { while(aux->sig!=NULL) aux=aux->sig; aux->sig=ap; } return cola; } //Función encargada de registrar lo relacionado con la búsqueda //verifica primero si no ha sido registrada, para evitar duplicidad reg *registra_TDA(char *linea, char *aux, reg *col_dat, FILE *flujo) { reg *ap=NULL; int campo=1; //Verifica el registro de la linea if(!existe(linea, col_dat)) { ap=crea_nodo(linea, aux); col_dat=encola(col_dat, ap); } do { //Si alguno de los campos no existe se llama a la función para su búsqueda desde el inicio campo=verifica_campos(linea, col_dat, aux); if(!campo) { rewind(flujo); col_dat=busca_estructuras(aux, flujo, col_dat); } }while(campo==0); return col_dat; }

160

//Función encargada escribir en el archivo de salida el resultado de la búsqueda void crea_arout(reg *estructuras, FILE *salida, char *tda) { reg *ap=NULL; int encon_ptr_sig=0; char ptr_sig[20]=""; if(estructuras!=NULL) { //Escribe un redefinición del TDA para que sea usado por el programa realizado //en la parte I fprintf(salida,"\n typedef struct %s nodo;\n", tda); do { ap=estructuras; fprintf(salida, "%s\n", ap->str_reg); if(!encon_ptr_sig) { encon_ptr_sig=existe_asterisco(ap->str_reg); if(encon_ptr_sig) { busca_ptr_sig(ap->str_reg, ptr_sig); printf("\t El apuntador al siguiente nodo es: %s\n",ptr_sig); } } estructuras=estructuras->sig; free(ap); }while(estructuras!=NULL); crea_func(ptr_sig); } else printf("La estructura no ha sido encontrada...\n"); } /***** Verifica que en la línea se encuentre el * el cual es el indicador del campo que apunta al siguiente elemento en una

lista. *****/ int existe_asterisco(char *ptr_sig) { int i=0, vr=0; while(ptr_sig[i]!='\0') if(ptr_sig[i++]=='*') { vr=1; break; } return vr; } /***** Esta función obtiene el nombre del campo, el cual es un apuntador a un elemento del mismo tipo, necesario para la

creación del TDA lista *****/ void busca_ptr_sig(char *struc, char *ptr_sig) {

161

char *aux, *aux2; aux=strtok(struc,";"); while(aux!=NULL) { aux=strtok(NULL,";"); if(existe_asterisco(aux)) { aux2=strtok(aux,"*"); aux2=strtok(NULL,"*"); strcpy(ptr_sig, aux2); break; } } } /***** Esta función crea el archivo que contiene las funciones para la inserción y eliminación de nodos que son llamadas por las funciones Envia_TDA y Recibe_TDA respectivamente *****/ void crea_func(char *ptr_sig) { FILE *fuente, *salida; char caracter; fuente=fopen("./MPI_lista.orig","rb"); //Archivo que contiene la estructura principal de las funciones. salida=fopen("./MPI_lista.c","wb"); if(fuente!=NULL && salida!=NULL) { while(!feof(fuente)) { fread(&caracter, sizeof(char), 1, fuente); //El carácter @ indica que este será substituido por el campo que es un apuntador if(caracter!='@') fwrite(&caracter, sizeof(char), 1, salida); else fwrite(ptr_sig, sizeof(char),strlen(ptr_sig),salida); } fseek(salida,-1,SEEK_END); //Esta ultima escritura es para evitar que sea repetido el ultimo carácter, //es posible que no sea necesaria, si se tiene problemas se deberá comentar. caracter=' '; fwrite(&caracter, sizeof(char), 1, salida); fclose(fuente); fclose(salida); } else perror("No se puede crear el archivo de salida necesario para el manejo del TDA lista...."); }

162

9.4. Anexo E

Manual de usuario “Rutinas de Balance” Para hacer uso de las rutinas de balance se deberán seguir los siguientes pasos.

Como primer paso se debe correr el programa “scan” pasándole como argumentos el nombre del archivo en donde se encuentra declarada la estructura a buscar, y el nombre de dicha estructura, a continuación se presenta un ejemplo de este procedimiento. Supongamos que tenemos la siguiente estructura en el archivo “def_structura.h”

typedef struct Registro Nodo; struct Registro { char nombre[40]; unsigned matricula; int edad; char sexo; Nodo *sig; }; Para que el programa “scan” genere los archivos correspondientes sólo se deberá dar alguna de

las siguientes instrucciones desde la línea de comandos. $: ./scan def_estructura.c Nodo; $: ./scan def_estructura.c Registro; El resultado de estas instrucciones es la misma, para el archivo “def_TDA.h” es: typedef struct Nodo nodo typedef struct Registro Nodo; struct Registro{char nombre[40];unsigned matricula; int edad; char sexo; Nodo *sig;}; En el caso del archivo “MPI_lista.c” el resultado es: /***** Archivo obtenido de la búsqueda realizada para la obtención de la estructura necesaria para la creación del TDA lista *****/ #include "protos.h" /***** Inserción de nodo en la lista *****/ void inserta_nodo_lista_MPI(nodo **lista, nodo *elem) { nodo *ap=*lista; if(es_vacia(ap)) *lista=elem; else { while(ap->sig!=NULL) ap=ap->sig; ap->sig=elem; } } /***** Elimina un nodo de la lista *****/ void elimina_nodo_lista_MPI(nodo **lista, nodo *elem) { nodo *ap=*lista, *aux=NULL;

163

if(!es_vacia(*lista)) { if(ap=elem) { aux=*lista; *lista=aux->sig; free(aux); } else while(ap->sig!=NULL) { if(ap->sig==elem->sig) { aux=ap->sig; ap->sig=aux->sig; free(aux); break; } ap=ap->sig; } } } /***** Inicia el apuntador al siguiente elemento de la lista con NULL *****/ void Asigna_null_asig(nodo *ap) { ap->sig=NULL; } Una vez obtenidos ambos archivos para hacer uso de las rutinas en el código de nuestra

aplicación se deberá declarar una variable de tipo MPI_Balance, al llamar a las rutinas de balance esta variable deberá ser pasada por referencia al igual que la lista que deberá ser declarada de la siguiente forma:

MPI_Balance var; Nodo *lista; //Rutinas de iniciación de MPI. MPI_Init (&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &id); MPI_Comm_size(MPI_COMM_WORLD, &proc); MPI_Get_processor_name(nombre, &long_nom); /* Aquí va el código de creación de la lista */ /* Aquí va la llamada al monitor, el cual se encargar de censar la carga del nodo del cluster */ //Se realiza las llamadas a la rutina que comienza el balance MPI_Init_balance(&var, &lista); /* Código que hace uso de la lista, hay que recordar que ha estas alturas ya no se debe manejar la variable lista para

el manejo de la misma sino el campo de la estructura el cual es: *var.TDA */

//Se terminan los cálculos se llama a la terminación de del balance MPI_Finaliza_balanceo(&var); MPI_Finaleze(); El monitor deberá cumplir con las siguientes características:

1. Deberá recibir como argumento una variable de tipo MPI_Balance creada en este proyecto.

164

2. Deberá realizar la llamada a las rutinas Abre_candados() y Cierra_candados() para garantizar la integridad de los datos en caso de hacer uso de la lista, como lo sería ver la cantidad de elementos de la lista.

3. Deberá de hacer la llamada a la rutina Inicia_balance(), la cual da la señal para que rutina de envío comience la migración de datos. Hay que recordar que el usuario deberá de realizar las invocaciones a las rutinas

Abre_candados() y Cierra_candados() para garantizar la integridad de los datos, él deberá determinar cual es la sección critica de su código para realizar tales invocaciones. Lo único que tiene que tomar en cuenta es que las rutinas de balance agregan y/o eliminan nodos del TDA lista.

El paso siguiente es la compilación y el enlazado del ejecutable para compilar se deberá además de incluir los fuentes del proyecto que se este trabajando, los fuentes “balance.c” y “MPI_lista.c” y para poder enlazarlos se deberá de agregar la opción -lpthread además de la necesarias para la compilación de nuestro fuente, por ejemplo, vea la siguiente forma:

$:mpicc –o ejecutable mi_codigo.c balance.c MPI_lista.c -lpthread Es importante resaltar que como el código del usuario ya cuenta con la definición de la estructura utilizada para la creación del TDA lista, al incluir los archivos “balance.c” y/o “MPI_lista.c” estos incluyen en su archivo de inclusión al archivo “def_TDA.h” el cual también contendrá la definición de la estructura antes mencionada resultado del escaneo del programa “scan” la definición de dicho archivo deberá ser comentada para poder compilar el proyecto con las rutinas de balance de carga.

165

9.5. Anexo F

Manual de usuario programa “scan” El programa es muy sencillo de utilizar. Tan solo hay que realizar la llamada desde la línea de comandos de la siguiente forma: $: ./scan <archivo.c|archivo.h> <TDA> Si no es llamado de la esta forma el archivo desplegara un mensaje de error y una pequeña ayuda de cómo ejecutar el programa, por ejemplo: si tenemos el siguiente archivo “estructura.h”, con el siguiente contenido. struct Reg_Alumno { int clave; char nombre[30]; int edad; char sexo; char direc; struct Reg_Alumno *sig; }; Además el programa crea una línea extra, la cual es una redefinición del tipo de dato encontrado al término del escaneo utilizado en el programa de la primera parte, dicha redefinición es para el uso de las funciones necesarias para la migración de los datos. Para realizar el escaneo con el programa la forma de hacerlo es: $: ./scan estructura.h Reg_Alumno De tal forma que el resultado del ejemplo anterior es el archivo “def_TDA.h” con el siguiente contenido. typedef struct Reg_Alumno nodo;

struct Reg_Alumno{int clave; char nombre[30];int edad; char sexo; char direc; struct Reg_Alumno *sig;};

proyectos de investigación i y ii - 148.206.53.84148.206.53.84/tesiuami/uami10920.pdf · asesor:...

Documents