Programación Avanzada, Concurrente y Distribuida

Diego Rodríguez-Losada González Pablo San Segundo Carrillo

Rodríguez-Losada & San Segundo, 2009. Programación Avanzada, Concurrente y Distribuida

2

Universidad Politécnica de Madrid -UPM

Rodríguez-Losada & San Segundo, 2009. Programación Avanzada, Concurrente y Distribuida

3

PRÓLOGO

7

PARTE I. Desarrollo de una aplicación distribuida y concurrente en LINUX 1. EDICIÓN, COMPILACIÓN, Y DEPURACIÓN DE UNA APLICACIÓN C/C++ BAJO LINUX

11

1.1. 1.2. 1.3. 1.4. 1.5. 1.6. 1.7. 1.8. 1.9. 1.10. 1.11. 1.12. 1.13. 1.14. 1.15.

11 12 12 15 15 16 17 17 19 20 21 22 23 24 25

INTRODUCCIÓN LOGIN EN MODO TEXTO MANEJO DE ARCHIVOS Y DIRECTORIOS EN MODO TEXTO. EL EDITOR DE TEXTO DESARROLLO C/C++ EN LINUX EN MODO TEXTO EL PROCESO DE CREACIÓN DE UN EJECUTABLE LAS HERRAMIENTAS DE DESARROLLO EL COMPILADOR GCC MAKEFILE Y LA HERRAMIENTA MAKE TIPOS DE ERROR DEPURACIÓN DE LA APLICACIÓN. CREACIÓN DE UN SCRIPT DESARROLLO EN UN ENTORNO GRAFICO EJERCICIO PRÁCTICO EJERCICIO PROPUESTO

2. INTRODUCCIÓN A LOS SISTEMAS DISTRIBUIDOS. COMUNICACIÓN POR SOCKETS

27

2.1. 2.2. 2.3. 2.3.1 2.3.2 2.4. 2.4.1 2.4.2 2.5. 2.6. 2.6.1 2.6.2 2.7.

27 28 29 30 32 35 36 38 42 44 44 45 45

OBJETIVOS SISTEMA DISTRIBUIDO SERVICIOS DE SOCKETS EN POSIX PROGRAMA CLIENTE SERVIDOR ENCAPSULACIÓN DE UN SOCKET EN UNA CLASE C++ ENVÍO DE MÚLTIPLES MENSAJES CONEXIONES MÚLTIPLES. ESTRUCTURA DE FICHEROS TRANSMITIENDO EL PARTIDO DE TENIS CONEXIÓN ENVÍO DE DATOS EJERCICIOS PROPUESTOS

Universidad Politécnica de Madrid -UPM

Rodríguez-Losada & San Segundo, 2009. Programación Avanzada, Concurrente y Distribuida

4

3. COMUNICACIONES Y CONCURRENCIA

47

3.1. 3.2. 3.3. 3.3.1 3.4. 3.5. 3.6. 3.7. 3.8. 3.9. 3.10.

47 49 49 50 51 52 53 55 56 56 57

INTRODUCCIÓN REQUISITOS FUNCIONAMIENTO DE GLUT LANZANDO UN HILO ESTRUCTURA DEL SERVIDOR MÚLTIPLES CONEXIONES SIMULTANEAS MOSTRAR LOS CLIENTES CONECTADOS RECEPCIÓN COMANDOS MOVIMIENTO GESTIÓN DESCONEXIONES FINALIZACIÓN DEL PROGRAMA EJERCICIO PROPUESTO

4. COMUNICACIÓN Y SINCRONIZACIÓN INTERPROCESO

59

4.1. 4.2. 4.3. 4.4. 4.5. 4.6.

59 60 61 62 64 68

INTRODUCCIÓN EL PROBLEMA DE LA SINCRONIZACION COMUNICACIÓN INTERPROCESO TUBERÍAS CON NOMBRE MEMORIA COMPARTIDA EJERCICIOS PROPUESTOS

PARTE II. Programación avanzada 5. PROGRAMACIÓN DE CÓDIGO EFICIENTE

73

5.1. 5.2. 5.3. 5.4. 5.5. 5.5.1 5.5.2 5.5.3 5.5.4 5.5.5 5.6. 5.6.1 5.6.2 5.6.3 5.7. 5.8.

73 77 77 78 79 79 80 83 85 86 87 87 88 90 93 95

INTRODUCCIÓN MODOS DE DESARROLLO TIPOS DE OPTIMIZACIONES VELOCIDAD DE EJECUCIÓN ALGUNAS TÉCNICAS CASOS FRECUENTES BUCLES GESTIÓN DE MEMORIA TIPOS DE DATOS TÉCNICAS EN C++ CASOS PRÁCTICOS ALGORÍTMICA VS. MATEMÁTICAS GENERACIÓN DE NÚMEROS PRIMOS PRE-COMPUTACIÓN DE DATOS OBTENIENDO PERFILES (PROFILING) DEL CÓDIGO CONCLUSIONES

Universidad Politécnica de Madrid -UPM

Rodríguez-Losada & San Segundo, 2009. Programación Avanzada, Concurrente y Distribuida 6. SERIALIZACIÓN DE DATOS 6.1. 6.2. 6.3. 6.3.1 6.3.2 6.4. 6.4.1 6.4.2 6.5.

5 97

INTRODUCCIÓN REPRESENTACIÓN OBJETOS EN MEMORIA SERIALIZACIÓN EN C CON FORMATO (TEXTO) SIN FORMATO (BINARIA) SERIALIZACIÓN EN C++ CON FORMATO (TEXTO) SIN FORMATO (BINARIA) CONCLUSIONES

97 102 103 104 104 107 108 111 112

7. BÚSQUEDAS EN UN ESPACIO DE ESTADOS MEDIANTE RECURSIVIDAD

113

7.1. 7.2. 7.2.1 7.2.2 7.2.3 7.3. 7.4.

INTRODUCCIÓN 113 115 BÚSQUEDA PRIMERO EN PROFUNDIDAD 116 TERMINOLOGÍA 116 ESTRUCTURAS DE DATOS 117 ANÁLISIS 119 BÚSQUEDA PRIMERO EN ANCHURA METODOLOGÍA GENERAL DE RESOLUCIÓN DE UN PROBLEMA DE BÚSQUEDA MEDIANTE COMPUTACIÓN 120 7.5. IMPLEMENTACIÓN DE UNA BÚSQUEDA DFS MEDIANTE RECURRENCIA 121 122 7.5.1 LA PILA DE LLAMADAS 124 7.5.2 BÚSQUEDA DFS COMO RECURSIÓN

8. EJECUCIÓN DISTRIBUIDA DE TAREAS

133

8.1. 8.2. 8.2.1 8.2.2 8.2.3 8.3. 8.3.1 8.3.2 8.3.3 8.3.4 8.4. 8.4.1 8.4.2 8.4.3 8.5. 8.5.1

133 134 134 135 136 138 139 140 141 145 147 147 148 148 153 153

INTRODUCCIÓN EL PROBLEMA DE LAS N-REINAS HISTORIA CARACTERÍSTICAS 2ESTRUCTURAS DE DATOS IMPLEMENTACIÓN CENTRALIZADA DESCRIPCIÓN ESTRUCTURAS DE DATOS CONTROL DE LA BÚSQUEDA ALGORITMO DE BÚSQUEDA IMPLEMENTACIÓN DISTRIBUIDA ARQUITECTURA CLIENTE-SERVIDOR PROTOCOLO DE COMUNICACIÓN IMPLEMENTACIÓN DEL CLIENTE IMPLEMENTACIÓN DEL SERVIDOR COMUNICACIÓN CON EL CLIENTE

Universidad Politécnica de Madrid -UPM

Rodríguez-Losada & San Segundo, 2009. Programación Avanzada, Concurrente y Distribuida

6

Universidad Politécnica de Madrid -UPM

Rodríguez-Losada & San Segundo, 2009. Programación Avanzada, Concurrente y Distribuida

7

PRÓLOGO Generalmente la formación en informática de un ingeniero (industrial, automática, telecomunicaciones o similar) comienza por la programación estructurada, en lenguajes como C o Matlab, y luego se complementa con Programación Orientada a Objetos (POO) e Ingeniería del Software, con Análisis y Diseño Orientados a Objetos, UML, etc. Sin embargo, existen una serie de técnicas y tecnologías software que escapan del alcance de los anteriores cursos. La programación de tareas concurrentes, los sistemas distribuidos, la programación de código eficiente o algorítmica avanzada son temas que quedan a menudo relegados, y sin embargo son muy necesarios en tareas de ingeniería industrial, comunicaciones y similares. Este libro trata de cubrir dichos aspectos, de una manera práctica y aplicada. La primera parte desarrolla una aplicación gráfica distribuida: un típico juego de computador en red. En esta aplicación se requiere el uso de comunicaciones por red (con sockets), así como la utilización de técnicas de programación concurrente con multi-proceso y multi-hilo, de una manera que esperamos que sea atractiva y motivadora para el lector. El desarrollo se realiza en Linux (Posix), presentando una introducción al manejo básico, desarrollo y depuración con herramientas GNU como g++, make y gdb. El código de soporte para estos capítulos se encuentra en www.elai.upm.es La segunda parte cubre algunos tópicos genéricos avanzados como la programación de código eficiente, la serialización de datos, la recurrencia o la computación distribuida, tópicos que muchas veces están íntimamente relacionados con los anteriores.

Universidad Politécnica de Madrid -UPM

Rodríguez-Losada & San Segundo, 2009. Programación Avanzada, Concurrente y Distribuida

8

Universidad Politécnica de Madrid -UPM

Rodríguez-Losada & San Segundo, 2009. Programación Avanzada, Concurrente y Distribuida

9

Parte I. Desarrollo de una aplicación distribuida y concurrente en LINUX

Universidad Politécnica de Madrid -UPM

Rodríguez-Losada & San Segundo, 2009. Programación Avanzada, Concurrente y Distribuida

11

1.

EDICIÓN, COMPILACIÓN, Y DEPURACIÓN DE UNA APLICACIÓN C/C++ BAJO LINUX 1.1. INTRODUCCIÓN En este primer tema realizamos una aproximación al SO operativo linux, y fundamentalmente al desarrollo de aplicaciones en C/C++, desarrolladas, depuradas y ejecutadas en un computador con Linux. Aunque el objetivo de este curso es el aprendizaje de programación concurrente y sistemas distribuidos, en este primer tema nos ceñiremos al trabajo de desarrollo convencional en linux, para aprender tanto el desarrollo sin interfaz grafica de ventanas, como algunas de las herramientas graficas. También se manejaran algunos comandos o mandatos básicos de linux para crear, editar y manejar archivos, y se introducirá el uso de las herramientas de desarrollo básico como son gcc, g++, make y gdb. Este tema comienza por la descripción de los comandos básicos para trabajar en modo texto, para después desarrollar y depurar una pequeña aplicación ejemplo en modo texto. Por ultimo, se trabajara en modo grafico, completando un código ya avanzado para terminar con el juego del tenis que funcione en modo local, para dos jugadores, esto es, los dos jugadores utilizan el mismo teclado y la misma pantalla.

Universidad Politécnica de Madrid -UPM

Rodríguez-Losada & San Segundo, 2009. Programación Avanzada, Concurrente y Distribuida

12

Figura 1-1. Objetivo del capítulo: Desarrollo del juego del Tenis en modo local

1.2. LOGIN EN MODO TEXTO Aunque el computador arranque en modo grafico, la primera parte de esta práctica se va a desarrollar en modo texto. Para ello cámbiese del terminal grafico al primer terminal de texto, mediante la correspondiente combinación de teclas (Ctrl+Alt+F1) Entrar en la cuenta de usuario correspondiente. Consejo: Aunque dispongas de la contraseña de administrador es absolutamente recomendable no utilizarla para trabajar normalmente. En caso de que seas el administrador del sistema, crea una cuenta de usuario normal para realizar la práctica. Probar a realizar el login en los distintos terminales virtuales (saliendo luego con el comando exit de los que no se vayan a utilizar)

1.3. MANEJO DE ARCHIVOS Y DIRECTORIOS EN MODO TEXTO. Para familiarizarse con el manejo de archivos y directorios en linux se va a crear la siguiente estructura de archivos, en la que los archivos de texto contienen el texto “Hola que tal”: /home/usuario/ |------------->carpeta1 |

|------->subcarpeta11

|

|

|

|------->archivo1.txt

|------->archivo11.txt

|------------->carpeta2 |------->archivo2.txt Universidad Politécnica de Madrid -UPM

Rodríguez-Losada & San Segundo, 2009. Programación Avanzada, Concurrente y Distribuida

13

Utilizar y explorar los comandos y opciones siguientes: Tabla 1-1. Comandos básicos consola linux

Comando pwd ls

Acción muestra el directorio actual muestra el contenido del directorio actual

mkdir [directorio]

crea el directorio con el nombre dado cambia al directorio que indica la ruta correspondiente concatena el fichero a salida estándar

cd [ruta] cat [fichero]

chmod usuario+permiso [fichero] rm [archivo]

cp [origen] [destino] mv [origen] [destino] rmdir [directorio] exit o logout

cambia los permisos (r=read, w=write, x=execute) a usuario (a=all, o=others, u=user, g=group) Borra el archivo

Copia el archivo o archivos origen al destino seleccionado Mueve el archivo o archivos origen al destino seleccionado Borra el directorio, que previamente debe estar vacío Termina la sesión (salir)

Opciones -a (muestra todos los archivos, incluidos ocultos) –l, muestra detalles de los archivos

‘-‘ significa entrada estándar. Para crear un archivo se puede redireccionarla de la siguiente forma cat >”nombre_fichero.txt”

-r = borra recursivamente el directorio seleccionado (OJO, usar con mucha precaución)

También sirve para renombrar un archivo

Universidad Politécnica de Madrid -UPM

Rodríguez-Losada & San Segundo, 2009. Programación Avanzada, Concurrente y Distribuida

14

Tabla 1-2. Caracteres comodin (wildcars)

* ?

Una cadena de caracteres cualesquiera Un carácter cualquiera Tabla 1-3. Directorios importantes

. .. cd

Directorio actual Directorio superior Vuelve al directorio inicial raiz del usuario “\home\usuario”

Opcion

Tabla 1-4. Ayuda

Comando man [comando] comando info [comando] whatis [comando]

función Muestra las paginas “man” del comando seleccionado Muestra una ayuda breve del comando al que se aplica Muestra las paginas “info” del comando al que se aplica Busca en una base de datos descripciones cortas del comando

Opcion --help -h

Tabla 1-5. Ayudas del shell bash

Teclas Tab

Tab+Tab Arrow Up Arrow Down

función Autocompletar, rellena el nombre del comando o archivo según las posibles opciones que conozca Muestra todas las opciones que tiene autocompletar Sube en la historia de comandos Baja en la historia de comandos

Opcion

Una vez creada la estructura, quitar el permiso de escritura al archivo11.txt e intentar concatenarle la cadena “Muy bien gracias”. Volver a reinstaurar el permiso y repetir la operación. Borrar primero el archivo2.txt y luego la carpeta2. Borrar a continuación todo el árbol de la carpeta1. Universidad Politécnica de Madrid -UPM

Rodríguez-Losada & San Segundo, 2009. Programación Avanzada, Concurrente y Distribuida

15

1.4. EL EDITOR DE TEXTO Se va a utilizar el editor “vi” o “vim” para crear y modificar los archivos de código fuente necesarios, por ser el editor incluido por defecto en linux, y del que conviene tener al menos unas nociones básicas que nos permitan sacarnos de un apuro en caso de necesidad. Para crear un archivo nuevo en la carpeta actual teclear: vi [fichero] Si el archivo no existe lo crea y si existe lo abre para editar. vi tiene dos modos de funcionamiento: •

Modo comando: cada tecla realiza una función específica (borrar, mover…) Este es el modo por defecto al arrancar el editor.

•

Modo inserción: cada tecla inserta el carácter correspondiente en el texto. Para entrar en este modo se debe pulsar la tecla “i” y para salir de él se debe pulsar “Esc”.

Operaciones básicas •

:w graba el archivo al disco

•

:q salir de editor

•

:q! salir del editor sin grabar los cambios (forzar la salida)

•

:wq grabar y salir

1.5. DESARROLLO C/C++ EN LINUX EN MODO TEXTO Vamos a construir una aplicación con dos ficheros fuente, que muestre por pantalla una tabla de senos de varios ángulos. Para ello seguiremos los siguientes pasos: 1. Verificar mediante “pwd” que se encuentra en el directorio de usuario adecuado 2. Crear una carpeta “pract1” que va a contener los archivos de la práctica, y cambiar el directorio actual a la misma 3. Crear los archivos fuente siguientes:

Universidad Politécnica de Madrid -UPM

Rodríguez-Losada & San Segundo, 2009. Programación Avanzada, Concurrente y Distribuida /* * */

16

archivo: principal.c

#include #include “misfunc.h” int main(void) { int i; for(i=0;i