Download Implementación de una librer´ıa de colecciones genéricas en Java
Document related concepts
no text concepts found
Transcript
FACULTADE DE INFORMÁTICA Departamento de Electrónica e Sistemas Proxecto de Fin de Carreira de Enxeñerı́a Técnica en Informática de Sistemas Implementación de una librerı́a de colecciones genéricas en Java para computación paralela Autor: Jorge Fernández Fabeiro Tutor: Diego Andrade Canosa Director: Basilio Bernardo Fraguela Rodrı́guez A Coruña, 15 de julio de 2009 Especificación Tı́tulo: Implementación de una librerı́a de colecciones genéricas en Java para computación paralela Clase: Proyecto de investigación y desarrollo Autor : Jorge Fernández Fabeiro Tutor : Diego Andrade Canosa Director : Basilio Bernardo Fraguela Rodrı́guez Tribunal : Diego Andrade Canosa Manuel Carlos Arenaz Silva Guillermo López Taboada Fecha de lectura: 15 de julio de 2009 Calificación: i Un espı́ritu noble “ensanchece” al hombre más pequeño Jebediah Springfield iii Agradecimientos En primer lugar me gustarı́a agradecer a los profesores Diego Andrade Canosa y Basilio Bernardo Fraguela Rodrı́guez el haberme dado la oportunidad de realizar este proyecto, ası́ como toda la ayuda prestada a lo largo de estos meses. Asimismo, estos cuatro años no habrı́an sido lo mismo sin el apoyo de todos aquellos compañeros de facultad en un principio, y buenos amigos después, que a lo largo de este tiempo me han acompañado en los buenos momentos y soportado en los malos. Como serı́a complicado nombrar a todos, al menos me gustarı́a hacer mención especial a Francisco Javier Álvarez, Iván Cores y Diego Darriba por haber compartido conmigo sus experiencias sobre qué es y cómo se debe afrontar un Proyecto Final de Carrera. Por último, y en absoluto por ello menos importante, agradezco a mis padres todo el cariño y confianza depositados en mı́ a lo largo de estos años, dándoles gracias sobre todo por haberme inculcado valores como la constancia en el trabajo y el afán de superación, sin los que habrı́a sido imposible llegar hasta aquı́. A todos, de nuevo, muchas gracias. v Resumen Las nuevas familias de procesadores comerciales introducen un número cada vez mayor de núcleos que comparten un mismo sistema de memoria. Ésto da lugar a la necesidad de que los programadores conozcan cómo aprovechar las capacidades de estos sistemas empleando lenguajes, extensiones de lenguajes o librerı́as para la paralelización de sus aplicaciones. Existe especial interés en mejorar el proceso de paralelización de lenguajes ampliamente extendidos en la industria como Java mediante la implementación de librerı́as que faciliten la labor del programador. El objetivo del presente proyecto es la construcción de una librerı́a que implementa una colección genérica sobre la que se pueden realizar diversas operaciones en paralelo, ası́ como definir otras nuevas mediante el uso de interfaces de Java. Con esta librerı́a se trata de minimizar el esfuerzo que el programador tiene que realizar para explotar las capacidades computacionales de los nuevos procesadores multinúcleo. Palabras clave Colecciones, Genericidad, Java, Multinúcleo, Orientación a Objetos, Paralelismo vii Índice general 1. Introducción 1 1.1. Estado del arte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1. Paradigmas de organización de sistemas paralelos . . . . . . . . . 2 1.1.2. Programación multithreading . . . . . . . . . . . . . . . . . . . . 3 1.1.3. Paralelización de tareas vs. paralelización de datos . . . . . . . . 4 1.2. Objetivos del proyecto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3. Metodologı́a de desarrollo . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4. Estructura de la presente memoria . . . . . . . . . . . . . . . . . . . . . 6 2. Paralelismo en Java 9 2.1. Hilos de ejecución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2. Threading en Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3. Implementación nativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3.1. Ciclo de vida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3.2. Planificación y prioridades . . . . . . . . . . . . . . . . . . . . . . 14 2.3.3. Sincronización . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4. Paquete java.util.concurrent . . . . . . . . . . . . . . . . . . . . . . 17 2.4.1. Colecciones seguras . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4.2. Planificación avanzada . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4.3. Sincronización avanzada . . . . . . . . . . . . . . . . . . . . . . . 23 2.4.4. Gestión de threads a bajo nivel . . . . . . . . . . . . . . . . . . . 26 ix ÍNDICE GENERAL x 3. Programación genérica en Java 29 3.1. Programación genérica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2. Implementación nativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.2.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2.2. Clases genéricas . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.2.3. Wildcards y métodos genéricos . . . . . . . . . . . . . . . . . . . 33 3.3. Genericidad avanzada . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.3.1. Uso combinado de código genérico y antiguo . . . . . . . . . . . 36 3.3.2. Observaciones importantes . . . . . . . . . . . . . . . . . . . . . 37 4. Paquete ParallelCollections 39 4.1. Problema objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.1.1. Operaciones a implementar . . . . . . . . . . . . . . . . . . . . . 40 4.2. Implementación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.2.1. Estructura de datos . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.2.2. Gestión de threads . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.2.3. Operaciones paralelas . . . . . . . . . . . . . . . . . . . . . . . . 45 4.2.4. Interfaz del conjunto paralelo . . . . . . . . . . . . . . . . . . . . 50 5. Evaluación 55 5.1. Programas de prueba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 5.1.1. SalaryIncrease . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 5.1.2. AirControl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.1.3. ShortestPath . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.2. Estudio de programabilidad . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.2.1. Programabilidad de los códigos de ejemplo . . . . . . . . . . . . 66 5.3. Análisis de rendimiento y escalabilidad . . . . . . . . . . . . . . . . . . . 67 5.3.1. SalaryIncrease . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.3.2. AirControl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.3.3. ShortestPath . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 ÍNDICE GENERAL xi 6. Conclusiones 75 6.1. Resumen del trabajo realizado . . . . . . . . . . . . . . . . . . . . . . . 75 6.2. Objetivos alcanzados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 6.3. Trabajo futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 6.3.1. Mejora de la genericidad . . . . . . . . . . . . . . . . . . . . . . . 76 6.3.2. Incorporación de nuevas operaciones . . . . . . . . . . . . . . . . 77 6.3.3. Aplicación en entornos más realistas . . . . . . . . . . . . . . . . 77 A. Manual de usuario/programador 79 A.1. Creación de estructuras . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 A.2. Manipulación de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 A.3. Operaciones paralelas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 A.4. Advertencias y comentarios . . . . . . . . . . . . . . . . . . . . . . . . . 85 A.4.1. Cierre del thread pool . . . . . . . . . . . . . . . . . . . . . . . . 85 A.4.2. Documentación de la librerı́a . . . . . . . . . . . . . . . . . . . . 86 Índice de figuras 2.1. Diagrama de estados del ciclo de vida de un thread . . . . . . . . . . . . 12 3.1. Jerarquı́a del framework de colecciones de Java . . . . . . . . . . . . . . 30 3.2. Ejemplo de uso explı́cito del cast en las colecciones de Java . . . . . . . 31 3.3. Ejemplo de uso de las colecciones genéricas de Java . . . . . . . . . . . . 31 3.4. Extracto de la definición genérica de las interfaces List e Iterator . . 32 3.5. Definición genérica de Collection con wildcards y métodos genéricos . 35 3.6. Firma del método genérico copy() de Collection . . . . . . . . . . . . 35 4.1. Esqueleto del código para la gestión de threads . . . . . . . . . . . . . . 44 4.2. Ejemplo de uso del método apply() y la interfaz Application . . . . . 46 4.3. Ejemplo de uso del método reduce() y la interfaz Reduction . . . . . . 47 4.4. Ejemplo de uso del método select() y la interfaz Comparator . . . . . 48 4.5. Ejemplo de uso del método map() y la interfaz Mapping . . . . . . . . . 48 4.6. Ejemplo de uso del método relation() y la interfaz Relationship . . 49 4.7. Atributos y constructores de la clase ParallelSet . . . . . . . . . . . . 50 4.8. Métodos de configuración de la clase ParallelSet . . . . . . . . . . . . 51 4.9. Firma de los métodos de operación de ParallelSet . . . . . . . . . . . 52 4.10. Firma de los métodos de manipulación de elementos de ParallelSet . . 53 5.1. Subida de sueldo de un conjunto de empleados usando un pool de threads 56 5.2. Algoritmo de funcionamiento de AirControl . . . . . . . . . . . . . . . 58 5.3. Algoritmo de búsqueda de aristas iniciales de ShortestPath . . . . . . . 60 5.4. Variante A para búsqueda de aristas conectadas de ShortestPath . . . 61 xiii xiv ÍNDICE DE FIGURAS 5.5. Variante B para búsqueda de aristas conectadas de ShortestPath . . . 62 5.6. Algoritmo de recorrido inverso del camino localizado por ShortestPath 63 5.7. Aceleración de AirControl sobre un nodo “c1” de 8 núcleos . . . . . . . 68 5.8. Aceleración de AirControl sobre un nodo “c2” de 24 núcleos . . . . . . 70 5.9. Aceleración de ShortestPath1 sobre un nodo “c1” de 8 núcleos . . . . . 71 5.10. Aceleración de ShortestPath1 sobre un nodo “c2” de 24 núcleos . . . . 72 A.1. Instanciación de un ParallelSet utilizando el constructor por defecto . 80 A.2. Instanciación de una ParallelList mediante el constructor parametrizado 80 A.3. Uso de los métodos de manipulación de datos de ParallelList . . . . . 81 A.4. Ejemplo de uso del método apply() y la interfaz Application . . . . . 82 A.5. Ejemplo de uso del método reduce() y la interfaz Reduction . . . . . . 82 A.6. Ejemplo de uso del método select() y la interfaz Comparator . . . . . 83 A.7. Ejemplo de uso del método map() y la interfaz Mapping . . . . . . . . . 83 A.8. Ejemplo de uso del método relation() y la interfaz Relationship . . 84 Índice de tablas 5.1. Lı́neas de código de los problemas de ejemplo con y sin ParallelCollections 66 5.2. Tiempos en milisegundos de AirControl para 8 núcleos . . . . . . . . . 68 5.3. Tiempos en milisegundos de AirControl para 8, 16, 32 y 64 núcleos sobre “c1” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.4. Tiempos en milisegundos de AirControl para 24 núcleos . . . . . . . . 69 5.5. Tiempos en milisegundos de ShortestPath1 para 8 núcleos . . . . . . . 71 5.6. Tiempos en milisegundos de ShortestPath1 para 24 núcleos . . . . . . 72 5.7. Tiempos en milisegundos de ShortestPath1 para 24, 32, 48 y 64 núcleos sobre “c2” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv 73 Capı́tulo 1 Introducción La Ley de Moore, formulada por el co-fundador de Intel, Gordon E. Moore, en 1965, predijo que el número de transistores que es posible integrar en un mismo circuito se duplicarı́a cada año[1]. Esta ley, que sigue vigente, ha permitido elevar el nivel de integración de transistores en una misma oblea de silicio hasta alcanzar las actuales tecnologı́as de 45 nm. Sin embargo, a más transistores integrados mayor es el calor a disipar y por tanto, más complicado resulta aumentar la frecuencia de reloj de estos circuitos. Esta situación ha limitado notablemente el desarrollo de los procesadores basados en un sólo núcleo. Por esta razón la idea que se está imponiendo en los últimos años es integrar un número creciente de núcleos en el mismo chip, dando lugar a lo que se ha dado en llamar procesadores multinúcleo. A comienzos de la actual década, los fabricantes de procesadores lanzaron sus primeros diseños de este tipo, como por ejemplo las arquitecturas POWER4 de IBM o Xeon de Intel, dedicadas ambas a servidores y sistemas embebidos. Con el paso de los años, esta tecnologı́a ha ocupado todos los segmentos de mercado, irrumpiendo en los equipos domésticos (Core 2 de Intel, Athlon X2 de AMD...) o en sistemas de entrenimiento (Cell, utilizado en la PlayStation 3 de Sony). Por otra parte, estos avances en el diseño de procesadores se ven limitados si los programas a ejecutar sobre los mismos no se aprovechan de la existencia de varios núcleos. 1 2 1. Introducción En el peor de los casos, y siempre que el sistema operativo correspondiente lo soporte, es posible correr sobre cada núcleo una aplicación diferente. Sin embargo, resulta deseable que aquellas aplicaciones con mayores necesidades computacionales (procesamiento gráfico, cálculos matemáticos de gran envergadura, tratamiento de grandes conjuntos de datos...) aprovechen la existencia de varios núcleos para realizar su trabajo más rápidamente. 1.1. Estado del arte A continuación se realiza una breve presentación de las principales tecnologı́as utilizadas actualmente tanto en la organización de sistemas paralelos como en la implementación de código para dichos sistemas. 1.1.1. Paradigmas de organización de sistemas paralelos Dentro de los sistemas de procesamiento paralelo existen dos grandes paradigmas de organización: memoria compartida y memoria distribuida. En el caso de los sistemas de memoria compartida, cada procesador tiene acceso a toda la memoria y se encuentran igualmente comunicados con ella por medio de un bus común, de manera que las operaciones de lectura y escritura tienen exactamente las mismas latencias. Como principales inconvenientes destacan los riesgos del acceso simultáneo a memoria, ya que pueden aparecer problemas de concurrencia si dos procesadores acceden a una misma región; ası́ como la poca escalabilidad de procesadores, al existir la posibilidad de que se forme un cuello de botella en el acceso a memoria si el número de éstos resulta excesivo. Sin embargo cuenta con una importante ventaja: resulta más fácil programar en estos sistemas que en los de memoria distribuida[2]. Este proyecto se enmarca en este tipo de sistemas. En los sistemas de memoria distribuida cada procesador tiene su propia memoria local, de manera que la única forma de compartir información entre ellos es enviando mensajes, es decir, si un procesador requiere los datos contenidos en la memoria de 1.1. Estado del arte 3 otro procesador, deberá enviar un mensaje solicitándolos. La gran ventaja de estos sistemas es su gran escalabilidad; por el contrario, el acceso remoto a datos ubicados en el sistema de memoria de otro procesador resulta más lento y la programación puede complicarse demasiado[2]. 1.1.2. Programación multithreading El requisito a cumplir por cualquier código paralelo es que éste aproveche los recursos proporcionados por los nuevos procesadores multinúcleo. En estos procesadores normalmente cada núcleo tiene los primeros niveles de caché privados, compartiéndose entre varios núcleos el resto de niveles de la caché y de la jerarquı́a de memoria. Para conseguir el aprovechamiento deseado, el código debe poder ejecutarse en diferentes threads o hilos de ejecución, de manera que cada núcleo se encargue de las tareas correspondientes a cada uno de ellos. La mayorı́a de lenguajes no contemplan la existencia de varios hilos de ejecución y éstos deben ser creados mediante llamadas a librerı́as especiales cuya implementación depende del sistema operativo subyacente, siendo el ejemplo más representativo el de C y del C++. Aunque en los sistemas basados en UNIX pueden utilizarse las funcionalidades multihilo proporcionadas por la interfaz POSIX1 [3], existen otras interfaces de programación de aplicaciones que se abstraen tanto del lenguaje como del sistema operativo utilizado. Ejemplo de ello es la API OpenMP[4][5], que permite la programación paralela, multiplataforma y de memoria compartida en C, C++ y Fortran sobre numerosas arquitecturas y sistemas, Unix y Windows inclusive. Definido conjuntamente por un grupo de grandes fabricantes y comercializadores de software y hardware, OpenMP es un modelo portable y escalable que proporciona una interfaz simple y flexible para el desarrollo de aplicaciones paralelas para un amplio rango de sistemas. Sin embargo, otros lenguajes como Delphi y, sobre todo, Java, incorporan en su diseño caracterı́sticas expresamente creadas para permitir a los programadores escri1 Acrónimo de “Portable Operating System Interface for UNIX” 4 1. Introducción bir código paralelo. En posteriores capı́tulos se presentarán y explicarán las distintas posibilidades que ofrece el lenguaje Java en lo que a programación multithreading respecta. Aunque teniendo un especial cuidado a la hora de gestionar las tareas no deberı́a resultar problemático el uso de las funcionalidades nativas del lenguaje para la implementación del paralelismo en la colección, se ha preferido utilizar algunas de las herramientas avanzadas incluidas en el paquete java.util.concurrent, puesto que correctamente utilizadas dotan al código de una especial robustez y seguridad ante eventuales problemas de concurrencia. 1.1.3. Paralelización de tareas vs. paralelización de datos Existen diferentes lenguajes, extensiones de lenguajes y librerı́as que intentan facilitar la programación para sistemas multinúcleo. Existen dos vertientes principales: el paralelismo de datos, en la que se aplica una misma operación de forma simultánea sobre conjuntos de datos diferentes; y el paralelismo de tareas, donde cada tarea se divide en varias subtareas que son ejecutadas simultáneamente en diferentes núcleos[6]. La clave de la paralelización de tareas reside en la división del trabajo en diferentes tareas que son asignadas directamente a hilos de ejecución “fı́sicos”, sobre cuya planificación solamente decide el sistema operativo. Recientemente han aparecido los Intel Threading Building Blocks o Intel TBBs[7]. Esta nueva librerı́a implementa el paralelismo mediante la definición de tareas que pueden ejecutarse concurrentemente, las cuales son asignadas por un planificador a los threads fı́sicos disponibles. En caso de que el número de éstos sea mayor que el de tareas a ejecutar, es posible aprovechar los recursos ociosos subdividiendo alguna de dichas tareas. Por otra parte, la paralelización a nivel de datos se basa en la creación de tareas que realizan una misma operación sobre diferentes fragmentos de un conjunto de datos. Realmente este enfoque es una particularización del anterior, ya que nada impide a los sistemas basados en paralelización de tareas el aplicar una misma operación a diferentes fragmentos de datos. Actualmente, una de las extensiones basadas en este paradigma es 1.2. Objetivos del proyecto 5 la librerı́a HTA, acrónimo de Hierarchically Tiled Arrays[8], cuyo objetivo es el diseño de tipos de datos que faciliten la creación de aplicaciones basadas en tiles utilizando lenguajes orientados a objetos. Una HTA es un array dividido en tiles2 o secciones separadas por lı́neas de partición (partition lines). Cada sección puede ser un array al uso u otra HTA, dotando al tipo de dato de un marcado carácter recursivo. Las ideas principales de esta expresión del paralelismo son mejorar la localidad de los accesos y facilitar al programador la explotación del paralelismo de forma transparente[6]. 1.2. Objetivos del proyecto Los procesadores multinúcleo se han convertido en la arquitectura dominante en los computadores modernos, mientras que el lenguaje de programación Java es uno de los más extendidos actualmente gracias a caracterı́sticas como ser orientado a objetos, multiplataforma y eminentemente orientado a Internet gracias a sus capacidades para la implementación de aplicaciones cliente-servidor. Partiendo de estas premisas el presente proyecto realiza las siguientes aportaciones: Implementación de una librerı́a de colecciones genéricas sobre cuyos datos se puedan realizar diferentes operaciones como aplicaciones de funciones, mapeos, selecciones u obtención de relaciones entre diferentes conjuntos de datos. Dicha librerı́a pretende servir de apoyo a los programadores a la hora de aprovechar las capacidades de los procesadores multinúcleo y la computación paralela. Evaluación de códigos de prueba implementados con la nueva librerı́a centrándose en dos aspectos: • Programabilidad: comparación respecto a colecciones nativas de Java a las que se dota de funcionalidades paralelas. • Rendimiento: comparación respecto a versiones secuenciales de las operaciones realizadas, ası́ como análisis de la escalabilidad del código. 2 Palabra inglesa que literalmente significa baldosas o tejas 6 1. Introducción 1.3. Metodologı́a de desarrollo La metodologı́a de desarrollo empleada puede clasificarse como basada en el modelo incremental, reduciendo ası́ los riesgos asociados al desarrollo de sistemas grandes y complejos. En una primera fase se ha creado el núcleo de la librerı́a implementando la estructura de datos a utilizar y sus operaciones básicas, para después, en cada ciclo de trabajo, incorporar nuevas funcionalidades a la misma en forma de diferentes operaciones paralelas. Cada una de estas fases, a su vez, constituye un ciclo de desarrollo prácticamente completo, ya que para cada una de ellas se pasó por las etapas de análisis, diseño, implementación y prueba de la nueva funcionalidad. 1.4. Estructura de la presente memoria El resto de la presente memoria se estructura en los siguientes capı́tulos: Capı́tulo 2: Paralelismo en Java Esta sección introduce algunos conceptos básicos acerca de la computación paralela y, sobre todo, la programación multihilo desde un punto de vista general, ası́ como detalles de su implementación en Java. Capı́tulo 3: Programación genérica en Java En esta sección se explican brevemente los conceptos básicos relacionados con la programación genérica, y más en concreto sobre su implementación en el lenguaje de programación Java. Capı́tulo 4: Paquete ParallelCollections Este capı́tulo describe la principal aportación del presente proyecto, el paquete de colecciones paralelas ParallelCollections, comentándose las diferentes fases de su ciclo de desarrollo. Capı́tulo 5: Evaluación Capı́tulo donde se explican las pruebas realizadas una vez finalizada la implemen- 1.4. Estructura de la presente memoria 7 tación de la librerı́a, las cuales pueden dividirse en dos grandes grupos: pruebas de rendimiento y estudios de programabilidad, ası́ como los códigos utilizados para ello. Capı́tulo 6: Conclusiones Finalmente se realiza un pequeño resumen del trabajo realizado y se plantean diferentes lı́neas de trabajo futuro de cara a la ampliación y mejora de la librerı́a. Adicionalmente, en el apéndice A se incluye un manual de usuario donde el programador puede consultar cómo realizar algunas operaciones básicas paralelas empleado la librerı́a ParallelCollections. Capı́tulo 2 Paralelismo en Java El presente capı́tulo desarrolla las diferentes alternativas existentes en Java para la implementación de código paralelo, centrándose en el mecanismo natural que ofrece Java para ello, el uso de múltiples threads o hilos de ejecución. Antes de entrar en detalles acerca de qué herramientas son necesarias y cómo se utilizan en la programación de código paralelo, se realiza una breve introducción al lenguaje de programación Java. El lenguaje de programación Java, desarrollado originalmente por James Gosling, fue publicado en 1995 como componente principal de la plataforma Java de Sun Microsystems. Gran parte de la sintaxis procede de C y C++, pero su modelo de objetos es más simple y dispone de menos funcionalidades a bajo nivel, además de estar más limitadas[9]. Las principales caracterı́sticas de Java son su orientación a objetos, no derivada de ningún otro lenguaje; ser distribuido, permitiendo la creación de aplicaciones orientadas a su uso en red; y ser a la vez compilado e interpretado, compilado porque a partir del código Java se generan ficheros bytecode de clase e interpretado porque dichos ficheros pueden ser ejecutados en cualquier máquina virtual de Java, independientemente de la arquitectura del sistema. 9 10 2. Paralelismo en Java 2.1. Hilos de ejecución Prácticamente todos los sistemas operativos modernos se basan en el concepto de proceso como unidad básica independiente de trabajo. Sin embargo, gracias al uso de threads o hilos de ejecución es posible encapsular múltiples actividades dentro de un mismo proceso. Por este y otros motivos que se explicarán a continuación, a menudo los threads son conocidos como procesos ligeros. Al igual que los procesos, los threads son caminos concurrentes e independientes de ejecución dentro de un programa, teniendo cada uno de ellos su propia pila, contador de programa y variables locales. Sin embargo, los threads de un proceso están menos aislados entre sı́ de lo que estarı́an varios procesos separados. Comparten memoria, manejadores de ficheros y otras variables de estado del proceso que los contiene. Un proceso puede soportar varios threads, los cuales aparentemente se ejecutan de forma simultánea y ası́ncrona entre ellos. Luego se verá que esto no siempre es cierto, siendo la correcta sincronización de diferentes hilos de ejecución uno de los grandes problemas que el programador se encuentra a la hora de implementar código paralelo. Múltiples threads dentro de un mismo proceso comparten el mismo espacio de direcciones de memoria, lo que quiere decir que pueden acceder a las mismas variables y objetos, y que ubican objetos en el mismo heap o montı́culo. Si bien ésto facilita el intercambio de información entre threads, es muy importante vigilar que no interfieren unos en el trabajo de otros, ya que interferencias no deseadas o controladas pueden derivar en problemas de rendimiento o incluso de ejecución[10][11][12]. 2.2. Threading en Java Si bien a lo largo de los años ha habido diferentes lenguajes de programación que, de una forma u otra, han ido implementando capacidades multihilo, Java fue el primer lenguaje de propósito general en el que estas funcionalidades se incluyeron como parte del lenguaje. 2.3. Implementación nativa 11 A estas funcionalidades nativas incorporadas en Java desde sus primeras versiones, ha de sumarse el paquete java.util.concurrent, ası́ como otros subpaquetes auxiliares que, desde la versión 1.5 del JDK1 proporcionan toda una serie de clases y mecanismos complejos para ser utilizados en la implementación de aplicaciones concurrentes: nuevas utilidades de sincronización a bajo nivel, mejoras en la seguridad y gestión de threads, clases concurrentes de alto rendimiento (thread pools, colecciones concurrentes, semáforos, latches, barreras...), etc[13][14][15]. Ambas implementaciones, en conjunto, convierten al lenguaje Java en una potente herramienta de programación concurrente que, entre otras cosas, permite crear interfaces gráficas más eficientes, separar más explı́citamente si cabe las operaciones de E/S del resto de la lógica de los programas y, lo que es más importante en el ámbito de este proyecto, exprimir las potencialidades de los sistemas multiprocesador y/o multinúcleo. 2.3. Implementación nativa Una sola clase, la clase Thread, resulta suficiente para soportar la implementación básica del threading de Java, proporcionando todas las funcionalidades necesarias para realizar trabajos más o menos sencillos con diferentes hilos de ejecución. Asimismo, y para evitar posibles ambigüedades de aquı́ en adelante, cabe diferenciar entre dos entidades estrechamente relacionadas que suelen recibir el nombre de hilo o thread. Por una parte está el hilo en ejecución, que es el que realiza el trabajo y suele ser creado por el sistema operativo; y su representación como objeto de clase Thread, que es utilizado por la JVM para control del primero. También es importante destacar que todo programa en Java cuenta con al menos un hilo, el principal. 2.3.1. Ciclo de vida La figura 2.1 refleja los diferentes estados por los que puede pasar un thread desde su creación hasta su finalización, ası́ como las posibles transiciones entre los mismos. 1 Java Development Kit 12 2. Paralelismo en Java Figura 2.1: Diagrama de estados del ciclo de vida de un thread Creación Existen dos formas diferentes de crear hilos adicionales al principal: mediante herencia de la clase Thread o implementación de la interfaz Runnable, los cuales se resumen de la siguiente manera: Herencia de la clase Thread: Es el método más sencillo, basándose simplemente en hacer que la clase cuyo código se desea ejecutar en un hilo independiente extienda a Thread y sobrecargue su método run(), quien verdaderamente implementa la operación u operaciones a realizar por el hilo. A cambio de la sencillez, se sacrifica la posibilidad de que la clase herede directamente de otra, pues Java no permite explı́citamente la herencia múltiple. Implementación de la interfaz Runnable: Esta opción obliga a que la clase a ejecutar en otro hilo implemente la interfaz Runnable y su método abstracto run(), que al igual que en el caso anterior, es el encargado de llamar a las operaciones que se pretende sean ejecutadas por el hilo en cuestión. La gran ventaja del uso de la interfaz Runnable en lugar de la herencia es que no se impide que la clase en cuestión extienda a otra de ser necesario. A continuación se describe cómo poner en ejecución uno de estos hilos. 2.3. Implementación nativa 13 Ejecución y parada Si bien el trabajo que se realiza al ordenar la ejecución de un hilo es el mismo en ambos casos2 , la forma en que éste se realiza difiere ligeramente dependiendo de cuál de los dos métodos de creación se haya empleado a la hora de generar el nuevo thread. Si el nuevo hilo ha sido creado mediante herencia de la clase Thread, bastará con llamar al método start(), heredado de la superclase. En cambio, si se ha optado por utilizar la interfaz Runnable, es necesario instanciar un objeto Thread pasando como parámetro al constructor dicha interfaz o la clase que la implemente, para posteriormente llamar al método start() de dicha instancia. El método complementario a start() es stop(), que detiene completamente el thread iniciado con el primero. Es importante destacar que una vez realizada la llamada a stop(), el thread detenido no es recuperable, lanzándose una excepción de la clase IllegalThreadStateException en caso de que se intente llamara a start() de nuevo. La llamada a start() se corresponde con la transición de los estados Start a Runnable representados en la figura 2.1, mientras que la llamada a stop() equivale al paso de Runnable a Stop. Además de por su detención explı́cita con stop(), un hilo finalizará su ejecución si su método run() termina o si alguna de sus instrucciones lanza una Exception o un Error no capturados con el try-catch correspondiente. Asimismo, cuando todos los threads de un programa finalizan, el programa sale. Suspensión y reinicio Como ya se ha explicado en el apartado anterior, una vez detenido un hilo éste no es recuperable. Sin embargo, no se puede dejar un thread continuamente en ejecución, ya que agotarı́a el tiempo de CPU asignado al proceso que lo contiene y no permitirı́a lanzar otros hilos asociados a ese mismo proceso. A este efecto existen los métodos 2 Se llama al método run() 14 2. Paralelismo en Java sleep()/interrupt(), yield() y suspend()/resume(). Estos métodos se corresponden con las transiciones entre los estados Runnable, Running y Blocked del diagrama 2.1. En el caso de sleep(), su funcionamiento es el esperado intuitivamente: duerme la ejecución del thread durante un determinado perı́odo de tiempo pasado como parámetro. El hilo que haya reemplazado al “durmiente” puede despertar a este último mediante el método interrupt(), que a su vez lanzará una InterruptedException que advertirá al mismo que ha sido reactivado por una interrupción y no por haber agotado el tiempo de espera. Existe un método similar a sleep(), yield(), que detiene el hilo actual temporalmente para que otros threads puedan ejecutarse. Pese a su aparente sencillez, utilizar sleep() no es la forma más adecuada de trabajar si lo que se desea implementar es la respuesta a un evento concreto, algo muy común en el diseño de interfaces gráficas. Para ello deben utilizarse suspend() y su complementario resume(), que suspenden de forma temporal y reinician la ejecución del hilo. 2.3.2. Planificación y prioridades Una vez estudiadas las herramientas que permiten controlar la ejecución de los diferentes hilos contenidos en un determinado proceso, resulta conveniente analizar cómo reparte Java los recursos de sistema entre todos ellos. Para realizar esta tarea la JVM3 cuenta con el llamado Thread Scheduler4 , cuyo funcionamiento se detalla a continuación. Dos son los datos que el planificador revisa para cada thread, su prioridad y su flag daemon, partiendo de la regla básica de que si solamente se encuentran listos para ejecución hilos con el flag daemon activo la JVM debe cerrarse. Respecto a la prioridad, el comportamiento es el esperado, ejecutándose antes los threads cuanto mayor sea su prioridad. El rango de la misma va de 1 a 10, siendo 1 la mayor, 10 la menor y 5 la 3 4 Java Virtual Machine Literalmente, planificador de hilos 2.3. Implementación nativa 15 normal y valor por defecto. A aquellos hilos que además de tener el flag daemon activo tengan una prioridad relativamente baja se les conoce como daemon threads, y suelen emplearse para proporcionar servicios básicos a diferentes programas (el ejemplo más representativo es el recolector de basura o garbage collector de la JVM). Asimismo, dependiendo del sistema operativo subyacente la planificación de threads se realizará o no de forma apropiativa. Cuando la planificación es apropiativa, se asigna a cada hilo un “cuanto de tiempo”, de manera que una vez agotado el mismo el thread queda en suspensión hasta que le vuelva a ser concedida la CPU y sea reiniciado con resume(). Si la planificación es no apropiativa, el hilo en ejecución no abandona la CPU hasta que finaliza, a no ser que se llame explı́citamente a yield() para que otro thread en espera se reinicie. Por el contrario, si lo que se desea es que un hilo quede en espera hasta que otro finalice, puede utilizarse el método join(). 2.3.3. Sincronización Como ya se ha comentado en secciones anteriores, uno de los puntos clave a la hora de programar correctamente código paralelo reside en la correcta sincronización de las operaciones a realizar por los diferentes threads. Además, para que resulte útil contar con varios hilos dentro de un mismo programa debe existir alguna forma de comunicación o compartición de datos entre los mismos. Formas de comunicación La forma más sencilla de conseguir esto es mediante la compartición de variables, y para ello es estrictamente necesario asegurar que los valores se propagan correctamente entre los varios hilos del programa, ası́ como prevenir que los mismos puedan observar o trabajar con estados intermedios inconsistentes de dichas variables o incluso sobreescribirse el trabajo mutuamente. Java proporciona dos modificadores para evitar la realización de accesos ilegales o peligrosos a aquellas variables o regiones de código 16 2. Paralelismo en Java a las que acompañen: synchronized: Asegura que solamente un thread ejecute de forma simultánea una sección protegida de código que se ha de ejecutar atómicamente (es decir, funciona como un sistema de exclusión mutua o mutex), ası́ como que los cambios realizados por un hilo sean visibles para los demás. Si no se utiliza, es muy probable que la planificación de hilos haga que los datos a tratar queden en un estado inconsistente. volatile: Su uso es más sencillo que el de synchronized, pero solamente es válido para controlar el acceso a instancias concretas de variables primitivas5 , no clases. Básicamente, cuando una variable es declarada volatile, cualquier cambio en ella es escrito directamente en memoria principal, sorteando la escritura en caché. Esto hace que todos los hilos vean un mismo valor para la variable en un instante concreto. El acceso a las variables debe sincronizarse siempre que un hilo vaya a leer una variable modificada por otro o bien si se va a modificar una variable que posteriormente pueda ser leı́da por otro hilo. En cuanto a la consistencia del programa, el código debe sincronizarse de forma que desde el punto de vista del resto de threads la operación se realice de forma atómica, es decir, o se realizan todos los cambios asociados a la misma o ninguno de ellos. De todas maneras, existen determinadas situaciones en las que no es necesaria la sincronización explı́cita en el código, ya que es la propia JVM la que se encarga de ella internamente. Dentro de estas situaciones se incluyen: datos inicializados estáticamente utilizando el modificador static, variables finales, etc. Fallos de sincronización El problema más representativo derivado de un error o falta de sincronización es el llamado “abrazo mortal” o deadlock, el cual sucede cuando dos hilos se quedan a la espera de que el otro realice una determinada operación. Un ejemplo básico de ello 5 Variables de tipo int, boolean, etc. 2.4. Paquete java.util.concurrent 17 es un programa en que dos threads, denotados por T1 y T2, bloqueen dos objetos diferentes O1 y O2, de manera que T1 bloquea O1 mientras espera por O2, el cual es bloqueado por T2 mientras espera por O1. Esta situación es la referida por Dijkstra6 en su conocido “problema de la cena de los filósofos”. Existen diversos mecanismos para prevenir la aparición de interbloqueos, pero ocurre que la mayorı́a de dichas soluciones son difı́cilmente aplicables en la práctica: impedir el acceso exclusivo a recursos o que un hilo se apropie de un recurso que necesita pueden provocar que el sistema entre en estados inconsistentes, incluso en determinadas situaciones podrı́an seguir ocurriendo deadlocks. La solución más sencilla es establecer una condición de espera circular, de manera que un hilo solamente puede poseer un recurso un momento concreto. 2.4. Paquete java.util.concurrent Como ya se ha comentado, una de las novedades incorporadas al lenguaje en su versión 5.0 fue el paquete java.util.concurrent, compuesto por toda una serie de clases útiles para la creación de programas concurrentes más o menos complejos. Además del paquete propiamente dicho se añadieron otros dos subpaquetes destinados a tareas concretas, java.util.concurrent.atomic y java.util.concurrent.locks. Las principales caracterı́sticas de los mismos pueden resumirse como sigue: java.util.concurrent: Este paquete incluye pequeños frameworks estándar extensibles por el programador, ası́ como algunas clases que proporcionan funcionalidades útiles que de otra manera resultarı́an tediosas y complicadas de implementar. java.util.concurrent.atomic: Pequeño conjunto de herramientas que da soporte a operaciones concurrentes seguras y libres de bloqueos. Básicamente son clases que amplı́an y mejoran el concepto de variable volatile proporcionado por la implementación nativa. 6 Edsger Wybe Dijkstra (1930-2002), cientı́fico de la computación de origen holandés. 18 2. Paralelismo en Java java.util.concurrent.locks: Framework formado por interfaces y clases que flexibilizan las condiciones de bloqueo y sincronización propias de la implementación original, a expensas de complicar ligeramente la sintaxis del código. 2.4.1. Colecciones seguras Desde la versión 1.2 del Java Development Kit el lenguaje Java incluye el framework Collections, caracterizado por representar con gran flexibilidad las colecciones de objetos a través de las interfaces List, Set y Map. Como se comenta en el apartado anterior, el paquete java.util.concurrent añade un conjunto de nuevas colecciones concurrentes seguras cuyo propósito es proporcionar al programador una alternativa segura a las colecciones básicas y con mejor rendimiento y escalabilidad. La problemática de los iteradores Sin duda una de las grandes comodidades que proporcionan las colecciones básicas de java.util es la posibilidad de recorrer las mismas de forma sencilla mediante objetos Iterator (o mediante estructuras tipo foreach, que facilitan el trabajo más aún al crear y recorrer el iterador de forma completamente automática). El problema aparece cuando se desea utilizar estos iteradores en programas concurrentes, ya que en el momento de su creación asumen que la colección no va a ser modificada mientras no se termine de recorrer, lanzando una excepción del tipo ConcurrentModificationException en caso de intentar cualquier cambio. Por este motivo este tipo de iteradores son conocidos como iteradores fail-fast. Por el contrario, las colecciones seguras de java.util.concurrent implementan otro tipo de iteradores, los weakly consistent iterators7 , los cuales aseguran entre otras cosas no devolver ningún elemento dos veces en una misma iteración. 7 Iteradores débilmente consistentes, en inglés 2.4. Paquete java.util.concurrent 19 Descripción y funcionamiento de las colecciones El paquete java.util.concurrent incorpora las siguientes colecciones seguras como equivalentes a las correspondientes colecciones básicas de java.util: CopyOnWriteArrayList: Si se desea implementar una lista basada en arrays que sea segura a nivel de thread basta con utilizar Vector o encapsular un ArrayList con Collections.synchronizedList(). Sin embargo, en el fondo se está trabajando con colecciones básicas, de modo que los iteradores que las recorran serán fail-fast. Para evitar este problema existe CopyOnWriteArrayList, que lo soluciona creando copias del array subyacente cada vez que éste es modificado por inserciones o borrados, de manera que el iterador siempre mantiene su copia intacta mientras recorre la colección. CopyOnWriteArraySet: De caracterı́sticas similares a la anterior, esta colección resulta útil si se desea trabajar con la semántica propia de un Set. ConcurrentHashMap: Aunque es posible implementar un Map seguro mediante HashTable o encapsulando un HashMap con Collections.synchronized(), esta solución no resulta suficiente para obtener una colección totalmente concurrente, ya que además de la cuestión del iterador fail-fast análoga a los casos anteriores, aparecen problemas de escalabilidad y rendimiento al forzar que un único hilo pueda acceder a la misma. Para ello se incorpora ConcurrentHashMap, que permite lecturas y escrituras concurrentes en casi todas las ocasiones, además de proporcionar un iterador libre de ConcurrentModificationExceptions. Además de las anteriores, java.util.concurrent incorpora otro tipo de colecciones que aprovechan ciertas mejoras aplicadas en la JDK 1.5 al framework Collections en lo que a estructuras de datos FIFO8 se refiere: ConcurrentLinkedQueue: Es común servirse de una LinkedList para implementar una lista o cola de tareas pendientes, sin embargo esta estructura ofrece funcionalidades que no suelen ser empleadas en dichos casos. Por este motivo se 8 First In - First Out; literalmente, el primero en entrar es el primero en salir 20 2. Paralelismo en Java incluyó la interfaz Queue, mucho más sencilla y eficiente que List al permitir únicamente insertar y eliminar objetos. La implementación concurrente de este tipo de colección corresponde a la clase ConcurrentLinkedQueue, una cola FIFO rápida, segura a nivel de thread y no bloqueante. Interfaz BlockingQueue: Las colas pueden estar limitadas o no, de manera que si se intenta eliminar un objeto de una cola limitada vacı́a o bien añadir otro a una llena, la operación falla. Sin embargo, a veces es mejor hacer que el hilo que realiza dicha operación se bloquee en lugar de fallar y tener que recuperarse de dicho fallo, resultando en una forma mucho más elegante de gestionar los recursos a disposición de una cola. De entre las diversas clases de colección de java.util.concurrent que implementan esta interfaz cabe destacar SynchronousQueue, que no es propiamente una cola, pero facilita la sincronización entre hilos cooperativos. 2.4.2. Planificación avanzada Para ilustrar las diferencias entre la planificación básica que ofrece la implementación nativa de threading que incorpora Java y la planificación avanzada que implementa java.util.concurrent se toma el ejemplo de un servidor que a medida que recibe peticiones genera nuevos threads para atenderlas. Aparentemente parece algo sencillo y efectivo, sin embargo, si la carga es lo suficientemente elevada, puede suceder que se creen más hilos que los que puede gestionar el propio sistema operativo sobre el que corre el servidor. Superar este lı́mite, que no siempre es conocido ni coincide en todos los sistemas, provoca que la aplicación falle y Java lance un OutOfMemoryError. Planificación con thread pools Crear un nuevo hilo para cada petición no es una mala práctica en sı́ misma, es más, es la solución natural al problema de gestionar varias peticiones. La cuestión reside en cómo limitar cuántas de estas peticiones se van a gestionar a un tiempo, puesto 2.4. Paquete java.util.concurrent 21 que si se intenta atender demasiadas, es altamente probable que aparezcan problemas de rendimiento y escalabilidad, incluso de memoria, como se comenta en el apartado inmediatamente anterior. El mecanismo clásico utilizado en este tipo de situaciones se compone de una cola de tareas y una colección de hilos que las atiendan, de manera que dicha colección de threads o thread pool va desencolando tareas a medida que se completan las anteriores. Además de desaparecer el problema derivado de una posible sobrecarga de peticiones, se consigue mejorar el rendimiento y la escalabilidad del programa, puesto que se elimina el retraso introducido en la creación de nuevos threads para cada tarea. El framework Executor java.util.concurrent no solamente incluye diversas y flexibles implementaciones para los thread pools, sino que cuenta con Executor, todo un framework para la gestión de aquellas tareas implementadas mediante interfaces Runnable. El núcleo de Executor lo constituye la interfaz homónima, la cual solamente implementa un método, execute(), y recibe como parámetro la tarea a ejecutar por el mismo en forma de interfaz Runnable. La principal ventaja de Executor es que se consigue desacoplar el envı́o de las diferentes tareas de la polı́tica que ha de seguir la ejecución de las mismas. De esta manera la interfaz Executor solamente se encarga de la tarea a ejecutar (mediante un Runnable), mientras se programa en la clase que implementa a Executor la polı́tica de ejecución correspondiente (limitación de colas, tamaño del pool, prioridades, etc.). Muchas de las clases contenidas en java.util.concurrent que implementan Executor lo hacen a través de la subinterfaz ExecutorService, que además de encargarse de la tarea propiamente dicha trata los detalles acerca del ciclo de vida de la misma. Como se acaba de comentar, son varias las clases de java.util.concurrent que implementan Executor (directamente o a través de ExecutorService), cada una con 22 2. Paralelismo en Java su propia polı́tica de ejecución. Estas polı́ticas no son más que la forma de establecer cuándo y en qué hilo correrá determinada tarea, de qué recursos de sistema podrá disponer y qué se debe hacer ante una posible sobrecarga de trabajo. Sin embargo, estas clases tienen la peculiaridad de que no se instancian llamando a los respectivos constructores, sino mediante una serie de métodos factorı́a estáticos contenidos en la clase Executors: Executors.newCachedThreadPool(): Crea un pool de tamaño ilimitado que reutiliza aquellos hilos previamente creados cuando se encuentran disponibles. Si no hay ninguno, crea uno nuevo y lo añade al pool; por otra parte, si en un plazo de 60 segundos un thread no es utilizado, éste es finalizado y eliminado. Executors.newFixedThreadPool(int n): Crea un pool que reutiliza un conjunto fijo de n threads que atienden tareas procedentes de una cola compartida ilimitada. En caso de que alguno de los hilos falle, es reemplazado por uno nuevo para que sea posible asumir las tareas subsiguientes. Executors.newSingleThreadPool(): Difiere de los dos anteriores en que solamente cuenta con un thread, de manera que se asegura la ejecución estrictamente secuencial de una cola ilimitada de tareas. En concreto, los dos primeros métodos factorı́a de la lista anterior devuelven instancias de la clase ThreadPoolExecutor, de la cual se pueden modificar gran cantidad de detalles. Para ello debe usarse una versión de dichos métodos que acepte como argumento una interfaz ThreadFactory, la cual ha de ser implementada por el objeto factorı́a encargado de construir los threads a incluir en un thread pool. Definiendo adecuadamente dicho objeto, pueden crearse hilos con nombres descriptivos, daemon threads, clasificarlos por grupos o establecer una prioridad concreta para cada uno de ellos. Asimismo, existe la posibilidad de extender ThreadPoolExecutor para ası́ sobreescribir los métodos beforeExecute() y afterExecute(), con los que es posible añadir tareas de instrumentación, registro, temporización, etc. 2.4. Paquete java.util.concurrent 23 Por último, es importante reseñar que si bien la principal motivación del framework Executor es desacoplar el lanzamiento de tareas de la polı́tica de ejecución de las mismas, existen determinados casos en los que la forma de programar el código asume implı́citamente la polı́tica a seguir, de modo que la implementación del Executor correspondiente debe ser consistente con ella. Algunas de estas situaciones serı́an la espera sı́ncrona de varios hilos para completarse, en la que serı́a posible entrar en deadlock si el tamaño del pool es insuficiente para admitir un nuevo hilo por cuya finalización estén esperando el resto de threads; o un grupo de threads que trabajen de forma cooperativa, de modo que es necesario contar con un pool lo suficientemente grande como para atender todos los hilos. Future y CompletionService A mayores de la combinación del framework Executor y los diferentes tipos de thread pools, java.util.concurrent ofrece otras funcionalidades interesantes para la planificación avanzada de tareas con las interfaces Future y CompletionService: Future: Esta interfaz permite representar tareas que pueden haberse completado, estar en ejecución o bien a la espera de la misma. De esta manera es posible cancelar una tarea incompleta, preguntar por su estado e incluso obtener sus resultados o esperar su devolución. La clase que implementa Future, FutureTask, también implementa Runnable, de modo que un Executor admitirı́a una instancia de la misma como tarea a ejecutar. CompletionService: Esta interfaz dota a los servicios de ejecución del aspecto de una cola, de forma que el procesado de las tareas puede separarse de su ejecución. CompletionService incluye, entre otros métodos, submit() para enviar tareas y la pareja take()/poll() para consultar cuál es la siguiente tarea completada. 2.4.3. Sincronización avanzada Otro grupo de clases interesantes para la programación multihilo ofrecidas por el paquete java.util.concurrent son aquellas destinadas a la sincronización de threads, 24 2. Paralelismo en Java es decir, a la coordinación y control del flujo de ejecución de uno o varios hilos. Semáforos La clase de java.util.concurrent que implementa un semáforo clásico de Dijkstra, es la clase Semaphore. Funciona como se espera que lo haga un semáforo de este tipo, es decir, controla el acceso a determinada variable mediante una cantidad fija de “permisos” que pueden ser solicitados y devueltos por diferentes hilos de ejecución. En este caso, cuando un thread llama al método acquire() de una instancia de Semaphore puede suceder que obtenga uno de estos “permisos” si hay alguno disponible, o bien se bloquee hasta que quede alguno libre. Es importante reseñar que el semáforo no es consciente de qué hilos poseen los “permisos”, siendo la aplicación en sı́ la que debe encargarse de devolverlos al semáforo o cederlos a otro thread convenientemente. Existe un caso especial de semáforo muy utilizado en programación concurrente, se trata del mutex. Consiste en un semáforo de exclusión mutua9 , es decir, un semáforo que concede a un único hilo el permiso para acceder a determinado recurso. Como ya se verá, su comportamiento es muy similar al de los locks, pero con la importante ventaja sobre éstos de que permite que un hilo diferente al que accede al recurso libere el semáforo, resultando muy útil en situaciones donde es necesario recuperarse de un deadlock. CyclicBarrier La clase CyclicBarrier implementa una ayuda a la sincronización consistente en un “punto de encuentro” que un conjunto de threads debe alcanzar antes de continuar la ejecución del programa. El adjetivo “cı́clico” se debe a que las instancias de esta clase son reutilizables, de manera que cuando todos los threads alcanzan la barrera ésta se reinicia. 9 De ahı́ el nombre “mutex”: Mutual exclusion 2.4. Paquete java.util.concurrent 25 Se instancia pasando como parámetro al constructor una variable entera que determina el número de hilos del grupo a controlar, los cuales deben notificar su llegada mediante CyclicBarrier.await(), método que en su primera llamada bloquea la ejecución y no la reinicia hasta que todos los hilos lo han llamado. De todos modos, es posible establecer un timeout de espera de modo que si algún hilo no llega, se considere rota la barrera lanzándose una BrokenBarrierException. CountdownLatch La clase CountdownLatch tiene un comportamiento similar a CyclicBarrier, en tanto en cuanto ambas se utilizan como herramientas de coordinación de un grupo de hilos sobre el que se ha repartido la computación de un problema. Las principales diferencias residen en que sus instancias no son reutilizables y que se separan las fases de llegada y espera de los threads. Mientras que CyclicBarrier actúa como una simple barrera que no se levanta hasta que todos los hilos la alcanzan, CountdownLatch únicamente exige a los hilos que controla que notifiquen su llegada decrementando su contador interno, sin establecer ningún tipo de bloqueo sobre la ejecución del programa. En este caso, la capacidad de bloqueo la posee el método CountdownLatch.await(), el cual puede ser llamado por cualquier hilo y tiene como función esperar a que el contador del latch alcance valor 0. Como se puede intuir, los CountdownLatch son útiles para la implementación de soluciones a problemas descomponibles en partes, y es precisamente por este motivo por el que son el principal sistema de sincronización empleado en el presente proyecto. Un ejemplo de ello serı́a la selección de elementos de un conjunto que cumplan una determinada condición: se subdivide el conjunto en partes y sobre cada una de ellas el correspondiente hilo hace las comprobaciones oportunas. Este caso de uso, junto con todos los demás, se explican de forma detallada en los apartados dedicados al diseño e implementación del paquete ParallelCollections. 26 2. Paralelismo en Java Exchanger La clase Exchanger funciona de manera similar a una CyclicBarrier para dos hilos cooperativos, con la funcionalidad añadida de que ambos threads pueden intercambiar10 información cuando alcanzan la barrera. Un caso de uso muy tı́pico es la gestión de lecturas y escrituras de dos hilos sobre un mismo buffer de memoria; por ejemplo, un hilo escritor que obtiene comandos de red a través de un socket y otro lector que se encarga de su interpretación, de manera que cuando ambos alcanzan la barrera, se intercambian entre sı́. 2.4.4. Gestión de threads a bajo nivel Tal y como se comenta en el apartado sobre la implementación de threading nativa de Java, el lenguaje incorpora la sincronización de hilos a través de la palabra clave synchronized, mediante la cual se pueden definir secciones crı́ticas de código. Si bien el uso de dicha funcionalidad nativa no presenta problema alguno en los casos más generales, existen determinadas situaciones en las que aplicaciones avanzadas pueden ver perjudicado su rendimiento si la utilizan. Por este motivo java.util.concurrent incorpora la interfaz Lock, a través de la cual es posible implementar diferentes comportamientos de bloqueo tales como esperas por tiempo, interrumpibles, bloqueo por encuesta, etc. ReentrantLock La clase ReentrantLock implementa la interfaz Lock conservando el comportamiento y semántica de los bloqueos nativos pero añadiendo nuevas capacidades. La más destacable es una importante mejora en la escalabilidad del código respecto del uso de los bloques synchronized en las mismas situaciones, lo que conlleva mejoras en el rendimiento del programa. ReentrantLock cuenta con un único gran inconveniente, ya que existe la posibilidad de olvidarse de liberar el bloqueo, algo imposible con synchronized al realizarlo la JVM de forma automática. 10 To exchange: intercambiar 2.4. Paquete java.util.concurrent 27 Condition De la misma manera que la interfaz Lock es la generalización de la sincronización nativa, la interfaz Condition generaliza la funcionalidad implementada por los métodos wait(), notify() y notifyAll() de la clase Object a través de los equivalentes await(), signal() y signalAll(), con la ventaja añadida de que pueden crearse tantas variables de condición como instancias de Lock se tengan. ReadWriteLock Otra situación bastante común en programación concurrente es el llamado “problema de los lectores-escritores”, ejemplificación del uso de estructuras de datos en las que la frecuencia de operaciones de lectura es muy superior a la de operaciones de escritura. En estos casos resulta más eficiente utilizar un sistema de bloqueo que, pese a ser ligeramente más complicado que el ofrecido por ReentrantLock, permite que varios hilos accedan a la estructura para leer sin perjuicio de que sea necesario el acceso en exclusiva al recurso para realizar modificaciones. De esta manera se ofrece un rendimiento mucho mayor en las lecturas sin arriesgarse a que surjan problemas de modificaciones concurrentes en las escrituras. El paquete java.util.concurrent proporciona esta funcionalidad a través de la interfaz ReadWriteLock y su implementación en la clase ReentrantReadWriteLock. Variables atómicas Otra de las grandes novedades incorporadas en java.util.concurrent son las clases concurrentes Atomic (AtomicInteger, AtomicLong...), wrapper classes11 para los tipos primitivos que exponen las mejoras realizadas a bajo nivel en la Máquina Virtual de Java en lo que a operaciones de lectura-modificación-escritura se refiere. Prácticamente todos los bloqueos utilizados en las clases del paquete se implementan mediante ReentrantLock, que a su vez utiliza las clases Atomic. La utilización de estas “clases envoltorio” permiten aprovechar la inclusión en la mayorı́a de los procesadores 11 Clases envoltorio: añaden funcionalidades propias de objetos a tipos primitivos 28 2. Paralelismo en Java actuales de primitivas para, entre otras, este tipo de operaciones, resultando ası́ mucho más cómodo escribir código concurrente de alto rendimiento, libre de esperas y bloqueos. Capı́tulo 3 Programación genérica en Java Una de las grandes novedades incluidas por la comunidad de desarrollo de Java en la versión 1.5 del Java Development Kit fue la posibilidad de programar de forma genérica. Esta caracterı́stica, presente de una u otra forma desde hace tiempo en lenguajes como C++ o C# dota a Java de una potencia si cabe aún mayor, sobre todo en lo que al tratamiento de colecciones de datos se refiere. Es precisamente en este último aspecto en el que este proyecto se centra, poniéndolo en conjunción con las funcionalidades paralelas del lenguaje para obtener una librerı́a de colecciones genéricas capaces de procesar información de forma paralela. Una vez presentados los distintos métodos existentes para la extracción del paralelismo en Java, a continuación se explica de forma más o menos detallada qué es la programación genérica y cómo la utiliza dicho lenguaje. 3.1. Programación genérica La programación genérica es un tipo de programación que se centra en los algoritmos antes que en los datos manipulados, consiguiendo ası́ la generalización de las funciones utilizadas y conviertiéndolas en código ampliamente reutilizable. Para alcanzar estos objetivos se busca parametrizar lo máximo posible el desarrollo del programa, evitando detalles concretos. La biblioteca de funciones conseguida con esta manera de 29 30 3. Programación genérica en Java programar permite que la implementación de esos algoritmos pueda servir para más programas que otras más concretas; y también que aplicando pocos cambios sobre las mismas, éstas realicen acciones diferentes. Los programas genéricos o politı́picos son programas parametrizados en la estructura de los datos que manipulan. Este mecanismo de parametrización permite escribir programas que pueden trabajar sobre una importante clase de diferentes estructuras de datos, liberando ası́ al programador de escribir código adicional de similar funcionalidad cada vez que se quiera manipular una estructura de datos diferente. Esto simplifica enormemente el trabajo de construcción y mantenimiento de los sistemas de software ya que los programas se pueden adaptar automáticamente a cambios en la representación de los datos, reduciendo de esta manera el impacto de los cambios. 3.2. Implementación nativa Como ya se ha comentado en la introducción del presente capı́tulo, una de las principales extensiones añadidas a Java en su JDK 1.5 fue la llamada programación genérica o genericidad, cuyo objetivo básico es la abstracción de los tipos de datos. Si bien esto supone una mayor comodidad a la hora de escribir código para infinidad de problemas diferentes, no hay duda de que donde más se aprovechan todas sus ventajas Figura 3.1: Jerarquı́a del framework de colecciones de Java 3.2. Implementación nativa 31 es en su uso en las clases del framework de colecciones, cuya estructura puede revisarse en la figura 3.1. Es por esto por lo que se utilizarán algunas de estas clases para la ejemplificación de su uso. 3.2.1. Introducción Antes de la incorporación de la genericidad al lenguaje, el tratamiento de los datos almacenados en estructuras de la jerarquı́a Collections requerı́a de toda la atención del programador al no asegurar el compilador el tipo de dato de los objetos añadidos o extraı́dos de las mismas. Los métodos encargados de manipular los elementos de estas colecciones solamente aseguran que dichos objetos son de la superclase Object, necesitando de un cast explı́cito a la clase concreta a la que realmente pertenecen, algo que puede derivar en errores de ejecución si no realiza correctamente esta asignación[16]. 1 List listaEnteros = new LinkedList ( ) ; 2 listaEnteros . add ( new Integer ( 0 ) ) ; 3 Integer x = ( Integer ) listaEnteros . iterator ( ) . next ( ) ; 4 String st = ( String ) listaEnteros . iterator ( ) . next ( ) ; Figura 3.2: Ejemplo de uso explı́cito del cast en las colecciones de Java 1 List<Integer> listaEnteros = new LinkedList<Integer >() ; 2 listaEnteros . add ( new Integer ( 0 ) ) ; 3 Integer x = listaEnteros . iterator ( ) . next ( ) ; 4 String st = listaEnteros . iterator ( ) . next ( ) ; Figura 3.3: Ejemplo de uso de las colecciones genéricas de Java El fragmento de código de la figura 3.2 ejemplifica la situación antes comentada. Las dos primeras lı́neas hacen lo esperado, se define una nueva lista enlazada a la que se añade un entero con valor 0. Los problemas aparecen en las dos siguientes, ya que ambas son legales a efectos de compilación, pero la última provocará un error en tiempo 32 3. Programación genérica en Java de ejecución al intentar convertir un objeto que realmente es de clase Integer en un String. El código de la figura 3.3 muestra cómo se realizarı́an estas mismas operaciones utilizando genericidad. La novedad surge con el tipado explı́cito de la lista, como puede observarse en la primera lı́nea de código. Con esta modificación, tanto add() como iterator() trabajan únicamente1 con objetos Integer, de modo que la última lı́nea será ilegal y generará un error en tiempo de compilación. En resumen, la genericidad dota de mayor robustez y legibilidad al código al ser el propio compilador el que asegura la corrección de tipos del programa allá donde se empleen las clases genéricas. 3.2.2. Clases genéricas 1 public interface List<E> { 2 void add ( E x ) ; 3 Iterator<E> iterator 4 } 5 public interface Iterator<E> { 6 E next ( ) ; 7 boolean hasNext ( ) ; 8 } Figura 3.4: Extracto de la definición genérica de las interfaces List e Iterator Las clases genéricas se definen de forma similar a las clases convencionales, con la salvedad de los llamados parámetros formales de tipo, que van entre < y > y suelen aparecer, con ciertas excepciones, donde en condiciones normales se utilizarı́an tipos ordinarios. Para ilustrar la diferencia entre la definición de ambas clases compárense los extractos de las interfaces List e Iterator incluidos en la figura 3.4. 1 Más adelante se verá que esta limitación no es tan estricta. 3.2. Implementación nativa 33 La E entre < y > representa el parámetro formal de tipo, cuyas ocurrencias en el código son sustituidas por el argumento real de tipo a la hora de invocar a las clases con un tipo genérico determinado: en el caso de los ejemplos del apartado anterior, List<Integer>. Sin embargo, y pese a lo intuitivo que pueda resultar, no es del todo correcto pensar que List<Integer> sea una versión de List en la que todas las apariciones de E son reemplazadas por Integer. El motivo de esto es que las declaraciones genéricas solamente se compilan una vez y son almacenadas en un único fichero .class, es decir, no existen varias clases Java diferentes según el tipo que se pase a la “plantilla”2 genérica, sino que estos parámetros formales de tipo funcionan de manera similar a los argumentos que se pasan a los métodos convencionales. Otra de las caracterı́sticas de las clases genéricas que pueden llegar a desafiar la intuición del programador está relacionada con la herencia, ya que partiendo, por ejemplo, de una clase Empleado que herede de Persona y una clase genérica G, no se cumple que G<Empleado> sea subclase de G<Persona>. De todas maneras, en el siguiente apartado se introducen la gestión de jerarquı́as de clases genéricas mediante las wildcards. 3.2.3. Wildcards y métodos genéricos Wildcard types Antes de la introducción de la genericidad, la forma de representar un objeto de clase desconocida era declarándolo como de clase Object, raı́z del árbol de jerarquı́a de clases del lenguaje. Sin embargo, y a causa de lo que se acaba de comentar en el apartado anterior, con el uso de código genérico esta idea deja de ser aplicable, motivo por el cual se introdujeron los tipos wildcard, signados por ? y que representan eso mismo, objetos de clase desconocida. Con esta modificación, allı́ donde aparezca una declaración genérica del estilo G<?>, 2 Precisamente por ese motivo no es una plantilla al uso, como las incluidas en lenguajes como C#. 34 3. Programación genérica en Java podrá pasarse cualquier clase G con el argumento real de tipo que se desee (por ejemplo, G<Integer>), si bien surgen una serie de limitaciones derivadas del desconocimiento de la clase utilizada. En concreto, en el caso de las colecciones declaradas como Collection<?> no es posible añadir elementos directamente, ya que deberı́an ser de un subtipo de ?, algo que por definición no existe (con la excepción de null, que pertenece a todas las clases). Para solucionar este problema existen las wildcards limitadas superior e inferiormente: Wildcards limitadas superiormente: Tienen el formato <? extends G>, representando objetos de clase desconocida pero que el compilador asegura que heredan de G o son la propia G. Resultan útiles, por ejemplo, cuando se desea recorrer una lista de objetos de clases diferentes pero con una misma clase padre, como podrı́a ser una lista de Figuras que contenga objetos Circulo, Cuadrado o Rectangulo. Wildcards limitadas inferiormente: Son el caso complementario al anterior y tienen el formato <? super G>. El compilador asegura que pese a tratarse de una clase desconocida, siempre se tratarán objetos de clase G o de una clase situada por encima en la jerarquı́a. Métodos genéricos Resulta evidente que la definición de clases genéricas debe permitir la definición de métodos que aprovechen la posibilidad de trabajar con objetos de clases diferentes según sea necesario, es decir, clases genéricas que permitan la implementación de métodos genéricos. Un método genérico no deja de ser un método que puede recibir uno o varios parámetros de tipo, con la ventaja añadida de que no es necesario establecer argumentos reales para dichos parámetros. Es el propio compilador el que se encarga de escogerlos 3.2. Implementación nativa 35 basándose en los tipos de datos de los argumentos que se pasan al método, quedándose además con el argumento de tipo más especı́fico que resulte correcto. Wildcard types vs. métodos genéricos 1 interface Collection<E>{ 2 public boolean containsAll ( Collection <?> c ) ; 3 public boolean addAll ( Collection <? extends E> c ) ; 4 } 5 interface Collection<E>{ 6 public <T> boolean containsAll ( Collection <?> c ) ; 7 public <T extends E> boolean addAll ( Collection<T> c ) ; 8 } Figura 3.5: Definición genérica de Collection con wildcards y métodos genéricos Una vez presentadas ambas posibilidades, es lógico que surja la duda acerca de cuál ellas utilizar según en qué situaciones. Considérense a modo de ejemplo las dos declaraciones de la interfaz Collection incluidas en la figura 3.5, escritas utilizando wildcards y métodos genéricos respectivamente. En este caso, el tipo de retorno de los métodos no depende del parámetro de tipo de la clase ni de cualquier otro argumento del método, de modo que el argumento de tipo sirve únicamente como soporte del polimorfismo, es decir, permite utilizar varios tipos de argumentos reales para poder llamar al método desde lugares diferentes. En estas situaciones en que lo se busca es trabajar con un subtipado más flexible, es preferible el uso de wildcards. 1 public static <T> void copy ( List<T> dest , List <? extends T> src ) ; Figura 3.6: Firma del método genérico copy() de Collection 36 3. Programación genérica en Java De todas maneras, es totalmente legal y válido emplear wildcards y métodos genéri- cos conjuntamente. Ejemplo de ello es el método copy() de Collections, cuya firma se incluye en la figura 3.6. 3.3. 3.3.1. Genericidad avanzada Uso combinado de código genérico y antiguo Como se puede suponer, uno de los grandes inconvenientes que presenta la genericidad en Java es que, al tratarse de una funcionalidad implementada en una de sus últimas actualizaciones, ya existen millones de lı́neas de código escritas empleando versiones anteriores, las cuales además no pueden ser convertidas de un dı́a para otro. Tipos raw Para permitir la compatibilidad de código antiguo respecto de código nuevo escrito empleando programación genérica, se introdujeron los llamados tipos raw, ya comentados someramente en apartados anteriores y que, básicamente, consisten en el uso de clases o interfaces que admiten argumentos de tipo, como podrı́a ser Collection, sin dichos parámetros. En aquellas ocasiones en que se prescinde de la programación genérica, sin embargo, no funcionan como clases sin parámetro de tipo, sino que lo hacen como clases cuyo argumento real de tipo es desconocido, es decir, como si se tratase de <?>. De esta manera se permite la integración de código programado según las diferentes versiones a cambio de flexibilizar la correción de tipos que el compilador proporcionarı́a de emplearse únicamente genericidad. Pese al peligro inherente que esto supone, el propio compilador avisa mediante los llamados unchecked warnings de la presencia de asignaciones en las que no pueda asegurar plenamente la corrección de tipos esperada. 3.3. Genericidad avanzada 37 Erasure Como se puede leer en el apartado inmediatamente anterior, el compilador se sirve de los llamados unchecked warnings para advertir al programador de que existen asignaciones cuya corrección de tipos no es plena. Sin embargo, la seguridad e integridad de tipos de la JVM nunca se encuentran en riesgo en este tipo de situaciones. Esto es ası́ gracias a que la genericidad está implementada de manera que, si se combinan clases programadas con y sin ella, el compilador se deshace de toda la informacion relacionada con la misma: las clases parametrizadas pierden los argumentos de tipo y en aquellos lugares donde éstos se utilicen son reemplazados por el lı́mite superior de la variable (normalmente Object), además de insertarse los casts apropiados allı́ donde el tipado no resulte correcto. Es precisamente a causa de borrar toda la información referente a la programación genérica por lo que esta forma de proceder es conocida como erasure3 . 3.3.2. Observaciones importantes Como se ha venido comentando a lo largo del capı́tulo, una de las grandes dificultades que plantea la programación genérica, sobre todo a aquellos desarrolladores acostumbrados a trabajar con otros lenguajes cuya genericidad se basa en plantillas y estructuras similares, es que no funciona exactamente como el aspecto del código y el comportamiento de los programas puede dar lugar a pensar. En este apartado se explican algunos de estos pequeños pero importantes detalles. Compilación única Si se compara la salida obtenida mediante el método getClass() de Object para dos colecciones genéricas con distinto parámetro de tipo (como un ArrayList<Integer> y un ArrayList<String>, por ejemplo), puede pensarse que el resultado será falso, ya que dichas colecciones contienen elementos de clases diferentes (Integer y String). 3 To erase: borrar 38 3. Programación genérica en Java Sin embargo, y a causa de que las clases genéricas solamente se compilan una vez y se guardan en un único fichero .class, la comparación devolverá true, ya que ambas colecciones son de la misma clase ArrayList. Arrays genéricos El tipo de elemento de un array no puede ser una variable de tipo o un tipo parametrizado, a no ser que se trate de una wildcard no limitada, aunque sı́ es posible declarar tipos de arrays cuyo tipo de elemento se encuentre dentro de alguno de estos casos. La razón de esta importante restricción reside en que los arrays son estructuras cuyo tipo y tamaño se establece en tiempo de compilación, momento en que se desconoce el argumento real de tipo que se utilizará durante la ejecución del programa. Capı́tulo 4 Paquete ParallelCollections En este capı́tulo se explica todo el proceso de desarrollo del paquete de colecciones paralelas ParallelCollections. La metodologı́a empleada en el proceso ha sido de tipo incremental, de modo que en cada fase de este proceso se han ido incorporando nuevas funcionalidades. En concreto se procederá a detallar el ciclo de trabajo seguido (análisis, diseño e implementación) para cada uno de los incrementos que constituyen la librerı́a, desde las primeras aproximaciones hasta la versión final. En primer lugar se introduce el problema que se pretende resolver con la implementación de ParallelCollections, ası́ como las operaciones paralelas soportadas por las colecciones de la librerı́a. Posteriormente se detallan los pasos seguidos para cada fase del desarrollo incremental: estructuración de los datos, gestión del paralelismo, implementación de las operaciones e interacción con las colecciones de la librerı́a. 4.1. Problema objetivo Antes de comenzar la explicación del proceso que ha dado lugar a la librerı́a de colecciones ParallelCollections, resulta conveniente recordar el objetivo inicial del presente proyecto: implementar una librerı́a de colecciones genéricas que, mediante la implementación paralela de diversas operaciones estándar, faciliten la programación de sistemas multinúcleo. 39 40 4. Paquete ParallelCollections 4.1.1. Operaciones a implementar Las operaciones paralelas básicas que la librerı́a de colecciones debe soportar son las siguientes: Aplicación Sea un conjunto de datos de tipo T y una función f: T → T que realiza alguna modificación sobre elementos de dicho tipo, la operación de aplicación se define como el resultado de aplicar dicha función f sobre todos los elementos del conjunto. Reducción Sea un conjunto de datos de tipo T y una función de combinación r: (T, T ) → T , se define la operación de reducción como el resultado de combinar todos los elementos del conjunto para obtener un único valor de retorno, también de tipo T. Selección Sea un conjunto de datos de tipo T y una función booleana f: T → true/f alse, se define la operación de selección como la aplicación de dicha función booleana a todos los elementos del conjunto, generando un subconjunto con todos aquellos elementos para los que el valor devuelto por la función haya resultado true. Mapeo Sea un conjunto de datos de tipo T y una función f: T → S que realiza una operación cualquiera sobre elementos de tipo T devolviendo nuevos elementos, bien del mismo tipo o de otro diferente S, la operación de mapeo se define como el resultado de aplicar dicha función f sobre todos los elementos del conjunto. Producto cartesiano Dados dos conjuntos X e Y, se conoce por producto cartesiano X x Y al conjunto de pares (x,y) tal que X x Y = {(x, y)|x ∈ X ∧ y ∈ Y }. En el caso que nos ocupa, el 4.2. Implementación 41 resultado de realizar el producto cartesiano entre dos conjuntos de datos s1 y s2 de tipo T consiste en un nuevo conjunto de pares de elementos tales que el primero pertenece a s1 y el segundo a s2. Relación entre conjuntos La relación entre dos conjuntos consiste en una particularización del producto cartesiano de los mismos, puesto que el resultado de esta operación es un conjunto de pares a cuyos elementos se exige que cumplan una determinada condición, que es la que los relaciona. Aunque su planteamiento puede ser completamente arbitrario, existen una serie de propiedades que se pueden considerar notables. Dado un conjunto A y una relación R : A → A, se define: Reflexividad: R reflexiva ⇐⇒ ∀x ∈ A, (x, x) ∈ R. Simetrı́a: R simétrica ⇐⇒ ∀x, y ∈ A, (x, y) ∈ R ⇔ (y, x) ∈ R. Antisimetrı́a: R antisimétrica ⇐⇒ ∀x, y ∈ A, (x, y) ∈ R → (y, x) ∈ / R. 4.2. Implementación El paquete ParallelCollections proporciona dos clases de colección diferentes, ParallelSet<T> y ParallelList<T>, ambas basadas en la semántica de la interfaz Set<T> y cuyo estudio puede dividirse en tres partes: estructura interna de datos, gestión del paralelismo e implementación de las operaciones paralelas. 4.2.1. Estructura de datos Los datos se distribuyen en el conjunto paralelo como una colección de subcolecciones. El principal motivo de esta división ha sido el poder abrir la posibilidad de que distintos núcleos trabajen simultáneamente sobre distintas partes del conjunto de datos, algo que se consigue utilizando esta organización. La eliminación del reparto explı́cito de los datos entre los distintos hilos de ejecución facilita la implementación de las diferentes operaciones paralelas, ya que no es necesario utilizar parámetros para 42 4. Paquete ParallelCollections determinar los lı́mites de los subconjuntos correspondientes a cada thread. La implementación de esta idea se basa en la combinación de varios tipos de colecciones nativas de Java. Como contenedor de los subconjuntos se utiliza un ArrayList al tratarse de una estructura indexada y dinámica, obteniendo ası́ un acceso rápido y unı́voco a cada una de las partes del conjunto paralelo. Por defecto, el número de subconjuntos en que se divide la colección coincide con el número de núcleos disponibles del procesador1 , si bien este parámetro puede ser modificado en el momento de la instanciación de la clase. Además, si las necesidades del problema o las caracterı́sticas del sistema donde se ejecuta el programa cambian, es posible modificar el número de subconjuntos llamando al método disponible a tal efecto. ParallelList y la problemática del código hash En la clase ParallelSet2 , la operación de inserción distribuye los nuevos elementos entre los distintos subconjuntos HashSet de acuerdo al resultado de calcular el módulo entre su código hash y el número de partes en que está dividida la colección. Por defecto, Java calcula el hashcode de los objetos a partir del valor de todos sus atributos, de manera que cualquier modificación sobre un elemento implica modificar su código hash. Por otra parte, la propia documentación oficial de la API del lenguaje comenta la peculiar forma que Java tiene de tratar las modificaciones sobre los elementos de colecciones basadas en hash, como es el caso de HashSet. En concreto advierte que, de usar objetos mutables como elementos de un conjunto, no se asegura comportamiento especı́fico alguno en caso de que un objeto experimente modificaciones que afecten al resultado de las comparaciones con equals()[17]. Esto provoca que Java deje de reconocer como elementos del conjunto a aquellos objetos que hayan sufrido modificaciones en sus atributos sin haber sido previamente eliminados y vueltos a insertar. Por esta razón, y para mantener la especificación antes comentada acerca de la 1 2 Variable del entorno de ejecución accesible mediante Runtime.getRuntime().avaliableProcessors() Para aligerar la redacción, se prescindirá de las referencias al parámetro genérico de las colecciones 4.2. Implementación 43 distribución de los elementos según su hashcode, la operación de aplicación implementada en ParallelSet redistribuye los elementos entre los subconjuntos de acuerdo a los nuevos códigos hash derivados de las modificaciones realizadas. Como este problema sólo afecta al rendimiento de la operación de aplicación, no supone mayor inconveniente utilizar ParallelSet para la implementación de colecciones donde no se realice dicha operación o la complejidad de la misma no sea muy elevada. Para aquellos otros casos en que el rendimiento resulte importante, se proponen las siguientes alternativas: Uso de la colección paralela ParallelList: Utiliza una estructura de datos basada en subcolecciones ArrayList, quedando libre por tanto del problema de la modificación de sus elementos. En este caso la distribución de los elementos sólo respeta el código hash inmediatamente después de su inserción, ya que una vez modificados ésta ya no se asegura. Sobrecarga del método hashcode() de Object en la clase de los elementos a insertar: Si dichos objetos cuentan con alguna clave identificativa u otro tipo de atributo que el programador asegure que nunca vaya a ser modificado, puede sobrecargarse el método que obtiene el código hash para que éste solamente se calcule a partir de dichos atributos invariantes. 4.2.2. Gestión de threads En una operación paralela, cada hilo se encargará de procesar simultáneamente una subcolección del conjunto. Como además el número de subconjuntos es conocido y relativamente fijo, se creyó conveniente la utilización de una estructura de tamaño determinado para la gestión de los diferentes threads, escogiendo los thread pools de java.util.concurrent por adaptarse sus caracterı́sticas al problema que nos ocupa: la realización de operaciones simultáneamente constituye un conjunto de tareas que deben finalizarse en su totalidad para poder continuar con la ejecución del programa. 44 4. Paquete ParallelCollections 1 private ArrayList<Set<T>> subsets ; // Supóngase i n i c i a l i z a d a y con d a t o s 2 ... 3 // Se d e f i n e un t h r e a d p o o l de tamaño f i j o 4 ExecutorService pool = new Executors . newFixedThreadPool ( this . subsets . size () ) ; 5 // Se d e f i n e un c o n t a d o r de v a l o r e l número de s u b c o n j u n t o s 6 final CountDownLatch counter = new CountDownLatch ( this . subsets . size ( ) ) ; 7 for ( final Set<T> subset : subsets ) { 8 // Se d e f i n e l a t a r e a y s e e n vı́ a a l p o o l 9 this . pool . submit ( new Runnable ( ) { 10 public void run ( ) { 11 // OPERACION A REALIZAR SOBRE EL SUBCONJUNTO 12 operacion ( subset ) ; 13 // Decremento d e l c o n t a d o r 14 counter . countDown ( ) ; 15 } 16 }) ; 17 } 18 // Se e s p e r a a l a f i n a l i z a c i ó n de t o d o s l o s h i l o s 19 try { 20 counter . await ( ) ; 21 } 22 catch ( InterruptedException ex ) { 23 24 ex . printStackTrace ( ) ; } 25 } Figura 4.1: Esqueleto del código para la gestión de threads 4.2. Implementación 45 Por defecto, el tamaño del thread pool coincide con el número de subconjuntos de la colección, que también coincide por defecto con el del número de núcleos del sistema. De esta manera es teóricamente posible atender a un tiempo todas las tareas de una misma operación, si bien esto no suele ocurrir ya que para Java siempre existe un hilo activo, el thread principal, encargado de controlar el flujo del programa en ejecución. De todas maneras, el programador puede definir un tamaño de pool diferente a la hora de instanciar una nueva colección. La plantilla de código de la figura 4.1 aproxima la implementación del proceso de gestión de threads utilizado en la clase ParallelSet. Una vez definidas las estructuras de control de los hilos de ejecución (lı́neas 4-6), se envı́an mediante el método submit() del pool las interfaces Runnable que representan la tarea a realizar sobre cada subconjunto (lı́neas 9-16). Como puede verse en la lı́nea 14, el método run() de la interfaz también incluye la instrucción de decremento del CountDownLatch. El valor de este contador es inicializado al número de subconjuntos existentes, de manera que cuando todos los hilos han llamado a countdown() dicho contador alcanza el valor 0 y desbloquea la ejecución previamente puesta en espera con await(). Esta última operación podrı́a lanzar una InterruptedException si alguno de los hilos es interrumpido por alguna razón, si bien esto es algo que en condiciones normales no deberı́a suceder. Estas instrucciones de espera y control se encuentran en el try-catch comprendido entre las lı́neas 19 y 24. 4.2.3. Operaciones paralelas Cada una de las operaciones paralelas del catálogo se implementa usando su correspondiente método en la clase ParallelSet. Dichos métodos incluyen el esqueleto de código de la figura 4.1 antes comentado, además de la correspondiente tarea a realizar sobre el subconjunto en cuestión. Mientras que la paralelización de las operaciones se realiza desde la clase, las operaciones propiamente dichas deben ser especificadas por el programador cumpliendo una interfaz diferente según la operación a realizar. 46 4. Paquete ParallelCollections Seguidamente se enumera, para cada operación, la interfaz correspondiente junto con una breve descripción de su funcionamiento, ası́ como algunos ejemplos de uso sobre un hipotético conjunto de empleados representado por ParallelSet<Employee> staff, variable definida en la lı́nea 2 de la figura 4.2. Para más información el programador puede consultar el manual de usuario incluido en el apéndice A, donde se incluyen explicaciones más detalladas acerca del uso y funcionamiento de estas operaciones. Aplicación (Apply) 1 // Conjunto p a r a l e l o de empleados 2 ParallelSet<Employee> staff = new ParallelSet<Employee >() ; 3 // I n t e r f a z que implementa l a f u n c i ó n a a p l i c a r 4 Application<Employee> newIncome = new Application<Employee >() { 5 public void apply ( Employee element ) { 6 element . setIncome ( Math . round ( element . getIncome ( ) ∗(1+ percentage / 1 0 0 ) ) ); 7 } 8 }; 9 // E j e c u c i ó n de l a o p e r a c i ó n 10 staff . apply ( newIncome ) ; Figura 4.2: Ejemplo de uso del método apply() y la interfaz Application Utiliza Application<T>, que cuenta con el método void apply(T element) que implementa la función a aplicar sobre cada uno de los elementos, proceso que se realiza de forma secuencial simultáneamente sobre todos los subconjuntos. En la figura 4.2 se muestra un ejemplo de uso en el que se incrementa el sueldo un porcentaje parametrizable percentage a todos los empleados de una empresa. En este ejemplo la función a aplicar es implementada por la interfaz de las lı́neas 4 a 8. 4.2. Implementación 47 Reducción (Reduce) 1 Reduction<Employee> empleadoMejorPagado = new Reduction<Employee >() { 2 public Employee reduce ( Employee a , Employee b ) { 3 if ( a . getIncome ( )>b . getIncome ( ) ) 4 return a ; 5 else 6 return b ; 7 } 8 public Employee neutral ( ) { 9 return new Employee ( 0 , 0 ) ; 10 } 11 } ; 12 Employee mejorPagado = staff . reduce ( empleadoMejorPagado ) ; Figura 4.3: Ejemplo de uso del método reduce() y la interfaz Reduction En la figura 4.3 puede observarse que Reduction<T> se compone de dos métodos, T reduce(T a, T b) para aplicar la reducción sobre un par de elementos y T neutral() para definir el elemento neutro de la operación. En este caso, la reducción implementada en la interfaz de las lı́neas 1 a 11 selecciona el empleado con mayor sueldo, de modo que al final del algoritmo se obtiene el empleado que más cobra de toda de la plantilla. En concreto, reduce(a,b) va combinando todos los elementos del conjunto, siendo el primer par de parámetros el formado por el valor de retorno de neutral() y el primer elemento extraı́do del conjunto. Una vez calculada esa reducción, el resultado de la misma se combina con el siguiente elemento extraı́do, y ası́ sucesivamente hasta obtener la reducción de todo el conjunto. Este proceso es realizado de forma simultánea en cada uno de los subconjuntos, mediante el uso del método private T subsetReduction(Reduction<T> op, Collection<T> subset), que devuelve para cada uno de ellos la reducción implementada en la interfaz Reduction<T> op. Una vez obtenida la reducción de cada subconjunto, se agrupan esos valores y se vuelve a llamar a subsetReduction para obtener el resultado final de la operación. 48 4. Paquete ParallelCollections Selection (Select) 1 Comparator<Employee> sueldoMayor1500 = new Comparator<Employee >() { 2 public boolean hit ( Employee element ) { 3 return element . getIncome > 1 5 0 0 ; 4 } 5 }; 6 ParallelSet<Employee> staffMayor1500 = staff . select ( sueldoMayor1500 ) ; Figura 4.4: Ejemplo de uso del método select() y la interfaz Comparator El método boolean hit(T element) de Comparator<T>, implementado en las lı́neas 1 a 5 del código de ejemplo de la figura 4.4, comprueba si se cumple o no para cada elemento la condición de selección establecida. En este caso, dicha condición es que el empleado cobre más de 1.500 euros. Mapeo (Map) 1 Mapping<Double , Employee> mapeoSueldos = new Mapping<Double , Employee >() { 2 public Double map ( Employee element ) { 3 return element . getIncome ( ) ; 4 } 5 }; 6 ParallelSet<Double> sueldos = staff . map ( mapeoSueldos ) ; Figura 4.5: Ejemplo de uso del método map() y la interfaz Mapping El método S map(T element) incluido en Mapping<S,T> realiza la operación que se desee implementar sobre cada uno de los elementos del conjunto, devolviendo el resultado de la misma en un objeto de clase S. En el ejemplo de la figura 4.5, el método map() de la interfaz (lı́neas 2-4) simplemente extrae el sueldo de cada empleado. Nótese la diferencia de tipos entre los elementos del conjunto (clase Employee) y los objetos devueltos por la operación (clase Double). 4.2. Implementación 49 Relación entre listas (Relation) 1 Relationship<Employee , Employee> mejorPagadoQue = new Relationship<Employee , Employee >() { 2 public boolean isReflexive ( ) { 3 return false ; 4 } 5 public boolean isSymmetric ( ) { 6 return false ; 7 } 8 public boolean areRelated ( Employee e1 , Employee e2 ) { 9 return e1 . getIncome ( ) > e2 . getIncome ( ) ; 10 } 11 public boolean reflexCond ( Employee e1 , Employee e2 ) { 12 return e1 . equals ( e2 ) ; 13 } 14 } ; 15 ParallelSet<Pair<Employee , Employee>> paresMejorPagadoQue = staff . relation ( staff , mejorPagadoQue ) ; Figura 4.6: Ejemplo de uso del método relation() y la interfaz Relationship La relación entre dos listas es definida por la interfaz Relationship<T,S>, que cuenta con cuatro métodos: boolean isReflexive(): Sirve para definir la relación como reflexiva o no. boolean isSymmetric(): Sirve para definir la relación como simétrica o no. boolean areRelated(T e1, S e2): Condición que relaciona los elementos de un par. boolean reflexCond(T e1, S e2): Condición de reflexión, para relaciones de listas del mismo tipo normalmente es e1.equals(e2). Si bien la mayorı́a de las relaciones a calcular suelen implicar listas de un mismo tipo de dato T, con la inclusión de un segundo tipo S se busca dar soporte a posibles 50 4. Paquete ParallelCollections cruces de conjuntos con elementos de tipos diferentes, aunque en ese caso perderı́a todo su sentido hablar de pares simétricos. En el ejemplo de la figura 4.6 se obtiene un conjunto de pares tales que el primer empleado del par cobra más que el segundo empleado. Esta relación no es reflexiva (véase el valor de retorno false en la lı́nea 3) ni simétrica (lı́nea 6), ya que un empleado nunca puede cobrar más que sı́ mismo y tampoco es posible que si un empleado A cobra más que uno B, se pueda dar a la vez la situación inversa. 4.2.4. Interfaz del conjunto paralelo Al implementar la interfaz Set<T>, el conjunto paralelo interactúa con el resto de clases a través de los métodos que dicha interfaz exige, ası́ como a través de los métodos correspondientes a las operaciones soportadas. Además, la clase proporciona dos constructores y métodos de configuración de los parámetros de ejecución de las colecciones. Constructores 1 // A t r i b u t o s 2 private ArrayList<Set<T>> subsets ; 3 private int thread_pool_size ; 4 private ExecutorService pool ; 5 // C o n s t r u c t o r e s 6 public ParallelSet ( ) 7 public ParallelSet ( int _threads , int _subsets ) Figura 4.7: Atributos y constructores de la clase ParallelSet Se proporcionan dos constructores, uno por defecto y otro parametrizado, reflejados en las lı́neas 6 y 7 de la figura 4.7. El constructor por defecto crea un nuevo conjunto paralelo con igual número de subconjuntos que de threads en el pool. Esta cantidad coincide a su vez con el número de núcleos disponibles en el sistema, tal y como se 4.2. Implementación 51 comenta en los apartados 4.2.1 y 4.2.2. En cambio, el constructor parametrizado permite al programador adaptar estos valores a las condiciones del programa que desee implementar. Métodos de configuración 1 // Métodos de c o n f i g u r a c i ó n 2 public void changePoolSize ( int new_num_threads ) 3 public void changeSubsetsNumber ( int new_num_subsets ) Figura 4.8: Métodos de configuración de la clase ParallelSet Los parámetros de trabajo del conjunto paralelo (número de subconjuntos y tamaño del thread pool) también pueden ser modificados sin necesidad de volver a crear una nueva instancia de la colección pasando como parámetros al constructor las nuevas condiciones. Para ello pueden utilizarse los métodos referidos en las lı́neas 2 y 3 de la figura 4.8, que modifican respectivamente el tamaño del pool y el número de subconjuntos. La utilización de cualquiera de estas dos instrucciones de configuración implica detener la ejecución de todos las las tareas enviadas al thread pool. Además, en el caso de changeSubsetsNumber(), se reorganizarı́an todos los elementos entre el nuevo número de subconjuntos, proceso que resulta costoso si la colección de elementos tiene un tamaño considerable. Operaciones paralelas La figura 4.9 contiene las firmas de todas las operaciones paralelas implementadas (lı́neas 2-8), ası́ como la de los métodos secuenciales equivalentes de las mismas, programados a efectos comparativos (lı́neas 10-14). Obsérvese el detalle de que todas las interfaces y resto de parámetros empleados en los métodos paralelos deben estar acompañados por el modificador final, que asegura la inmutabilidad de la variable a la que acompaña durante la ejecución de cada tarea. 52 4. Paquete ParallelCollections 1 // O p e r a c i o n e s p a r a l e l a s 2 public void apply ( final Application<T> op ) 3 public T reduce ( final Reduction<T> op ) 4 public <S> ParallelSet<S> map ( final Mapping<S , T> op ) 5 public ParallelSet<T> select ( final Comparator<T> fc ) 6 public <S> ParallelSet<Pair<T , S>> processCartesianProduct ( final ParallelSet<S> other , final Relationship<T , S> rel , final boolean reflex , final boolean sym , final ParallelSet<Pair<T , S>> product ) 7 public <S> ParallelSet<Pair<T , S>> relation ( final ParallelSet<S> other , final Relationship<T , S> rel , final ParallelSet<Pair<T , S>> product ) 8 public void shutdownPool ( ) 9 // E q u i v a l e n t e s s e c u e n c i a l e s de l a s o p e r a c i o n e s 10 public void sequentialApply ( final Application<T> op ) 11 public T sequentialReduce ( Reduction<T> op ) 12 public <S> ParallelSet<S> sequentialMap ( Mapping<S , T> op ) 13 public <S> ParallelSet<Pair<T , S>> sequentialProcessCartesianProduct ( ParallelSet<S> other , Relationship<T , S> rel , boolean reflex , boolean sym , ParallelSet<Pair<T , S>> product ) 14 public <S> ParallelSet<Pair<T , S>> sequentialRelation ( final ParallelSet<S> other , final Relationship<T , S> rel , ParallelSet<Pair<T , S>> product ) Figura 4.9: Firma de los métodos de operación de la clase ParallelSet<T> Métodos de manipulación de elementos Finalmente, en la figura 4.10 se listan los métodos de manipulación de elementos de la colección. Nótese que se respeta la especificación propia de un conjunto, puesto que los métodos add() y remove() no hacen referencia alguna a ı́ndices o posiciones. Ası́ mismo no existe ningún método que permita el acceso ni modificación indexados a ningún elemento, siendo el uso de un Iterator (lı́nea 5) o de un foreach la única manera de recorrer los elementos de la colección. Son también importantes los métodos para la gestión de colecciones, reflejados en las lı́neas 10 a 13 de la figura 4.10, y que permiten con una sola operación añadir a, eliminar de o mantener en el conjunto todos los elementos contenidos en la colección especificada. 4.2. Implementación 53 1 // Métodos de m a n i p u l a c i ó n de e l e m e n t o s 2 public int size ( ) 3 public boolean isEmpty ( ) 4 public boolean contains ( Object o ) 5 public Iterator<T> iterator ( ) 6 public Object [ ] toArray ( ) 7 public <T> T [ ] toArray ( T [ ] a ) 8 public boolean add ( T e ) 9 public boolean remove ( Object o ) 10 public boolean containsAll ( Collection <?> c ) 11 public boolean addAll ( Collection <? extends T> c ) 12 public boolean retainAll ( Collection <?> c ) 13 public boolean removeAll ( Collection <?> c ) 14 public void clear ( ) Figura 4.10: Firma de los métodos de manipulación de elementos de la clase ParallelSet<T> Capı́tulo 5 Evaluación La evaluación del paquete ParallelCollections implementado ha sido realizada desde dos puntos de vista: programabilidad y rendimiento obtenido. La evaluación de la mejora de programabilidad se centra en analizar hasta qué punto se ha conseguido facilitar la implementación de operaciones paralelas utilizando las capacidades de java.util.concurrent, mientras que en las pruebas de rendimiento se ha comparado, para diferentes programas, los resultados de la versión paralela implementada mediante la librerı́a y una versión secuencial de cada código. Asimismo, se ha ido comprobado la evolución del rendimiento a medida que crece el número de núcleos disponibles. 5.1. Programas de prueba Para la realización de las diferentes pruebas que conforman la evaluación de la librerı́a ParallelCollections se han implementado y utilizado los siguientes programas de ejemplo: 5.1.1. SalaryIncrease El ejemplo de aplicación de funciones planteado en el apartado 4.2.3 e incluido en la figura 4.2 sirve de muestra acerca de cómo el uso de la librerı́a ParallelCollections 55 56 5. Evaluación 1 // L i s t a n a t i v a 2 ArrayList<Employee> staff ; 3 // Pool de t h r e a d s y c o n t a d o r de c o n t r o l 4 int thread_pool_size ; 5 ExecutorService pool = Executors . newFixedThreadPool ( thread_pool_size ) ; 6 final CountDownLatch counter = new CountDownLatch ( thread_pool_size ) ; 7 ... 8 // A p l i c a c i ó n de l a f u n c i ó n usando e l p o o l 9 int paso_bucle = staff . size ( ) / thread_pool_size ; 10 int div_entera = staff . size ( ) % thread_pool_size ; 11 if ( div_entera !=0) 12 paso_bucle = paso_bucle +1; 13 for ( int i =0;i<thread_pool_size ; i++){ 14 pool . submit ( new Runnable ( ) { 15 public void run ( ) { 16 int inicio = paso ∗ hilo ; 17 int fin = inicio+paso −1; 18 for ( int i=inicio ; i<=fin ; i++){ 19 if ( i<staff . size ( ) ) { 20 Employee e = staff . get ( i ) ; 21 e . setIncome ( e . getIncome ( ) ∗(1+ percentage / 1 0 0 ) ) ; 22 } 23 } 24 counter . countdown ( ) ; 25 26 } }) ; 27 } 28 try { 29 counter . await ( ) ; 30 } catch ( InterruptedException ex ) { 31 ex . printStackTrace ( ) ; 32 } 33 pool . shutdown ( ) ; Figura 5.1: Subida de sueldo de un conjunto de empleados usando un pool de threads 5.1. Programas de prueba 57 facilita el trabajo del programador que quiere sacar el máximo rendimiento a su máquina multinúcleo en comparación con el threading nativo. En dicho ejemplo se aplicaba sobre un ParallelSet de empleados una función que aumentaba el sueldo de cada uno, utilizando para ello la operación paralela apply() de la librerı́a y una interfaz Application<Employee> que incrementa el sueldo en un porcentaje parametrizable percentage, tal como puede verse en la lı́nea 6 del ejemplo de la figura 4.2. Realizar esta misma operación utilizando directamente un thread pool sobre una colección nativa de Java requiere escribir un código similar al de la figura 5.1, que implementa el siguiente algoritmo: 1. Cálculo de las partes en que se divide el conjunto para su reparto entre los distintos threads del pool (Lı́neas 8-12) 2. Operación de aplicación (lı́neas 13 a 33): Se definen interfaces Runnable, cuyos métodos run aplican la subida de sueldo (lı́neas 18-23) a la parte que los parámetros de las lı́neas 16 y 17 delimitan. Cada una de estas interfaces es enviada como tarea al pool mediante la instrucción submit() de la lı́nea 14. Una vez que todas las tareas han ejecutado la instrucción de decremento del contador de la lı́nea 24, éste desbloquea la ejecución del programa pausada con la llamada await() de la lı́nea 29. Finalmente se cierra el thread pool con el método shutdown() (lı́nea 33). Puede verse que el código de la figura 5.1 es ostensiblemente más largo que el que se obtiene utilizando la librerı́a, quedando comprobado que con el uso del paquete ParallelCollections se reduce el código necesario para la realización de operaciones paralelas. 5.1.2. AirControl El programa implementado en Examples.AirControl consiste en una abstracción relativamente sencilla de las operaciones necesarias para gestionar el tráfico de aeronaves 58 5. Evaluación 1 // Avión 2 class Plane { 3 int currentX , currentY 4 int predX , predY 5 int velx , vely 6 } 7 8 // E s p a c i o aé r e o y v a r i a b l e s de c o n t r o l 9 ParallelSet<Plane> espacio 10 int dangerDist , maxCoord , numPlanes 11 12 // P e l i g r o de c o l i s i o n 13 boolean peligro ( Plane p1 , plane p2 ) { 14 return ( p1 . predX−p2 . predX ) ˆ2+( p1 . predY−p2 . predY ) ˆ 2 ) < ( dangerDist ) ˆ2 15 } 16 17 // PASO 1 : P r e d i c c i ó n 18 Foreach Plane : espacio { 19 set predX = currentY + velX 20 set predY = currentY + velY 21 } 22 23 // PASO 2 : C á l c u l o de l a s p o s i b l e s c o l i s i o n e s 24 Foreach Pair ( p1 , p2 ) not equals nor symmetric 25 add ( p1 , p2 ) to listacolisiones if peligro ( p1 , p2 ) 26 } Figura 5.2: Algoritmo de funcionamiento de AirControl 5.1. Programas de prueba 59 que sobrevuelan una zona áerea. Dos son las entidades que definen el problema: por una parte la zona aérea a controlar, representada como un cuadrado y modelada por una colección paralela; y por otra, un conjunto de aviones que recorren la zona y que se caracterizan por su posición y por la velocidad a la que vuelan. Problema El objetivo principal es evitar las colisiones entre aeronaves, estableciendo para ello dos parámetros de seguridad: una velocidad máxima y una distancia mı́nima entre aparatos. La idea básica es calcular, de acuerdo a su posición y velocidad actuales, la predicción de movimiento de cada avión antes de que éste se desplace, de forma que cruzando las predicciones obtenidas se obtenga qué pares de aeronaves violan la distancia de seguridad. Algoritmo El algoritmo presentado en la figura 5.2 consta de los siguientes pasos: 1. Cálculo de la predicción de movimiento para todos los aviones: Resultado de sumar posición (currentX,currentY) y velocidad (velX,velY), obteniendo un punto futuro (predX,predY), cálculo que se realiza en las lı́neas 19 y 20 de la figura 5.2 para todos los aviones del espacio, como marca el bucle definido en la lı́nea 18. Utilizando las operaciones paralelas de la librerı́a, estos cálculos pueden realizarse con apply() y una interfaz Application<Plane> que implemente el cálculo de la predicción para cada avión. 2. Cruce de las predicciones generadas: En la figura 5.2, este paso supone la ejecución del foreach definido en la lı́nea 23. En dicho bucle se determina para cada par de aviones si éstos violan la distancia de seguridad, establecida en la variable de control distDanger de la lı́nea 10. Estos cálculos pueden ser realizados utilizando la operación relation() de la librerı́a paralela y una interfaz Relationship<Plane,Plane> para dar forma a la relación, que es reflexiva y simétrica. 60 5. Evaluación 5.1.3. ShortestPath Los códigos contenidos en Examples.ShortestPath modelan un mapa de aristas sobre el que es posible comprobar, mediante dos algoritmos diferentes, la existencia de caminos entre un par de puntos. En este caso el problema viene definido por el conjunto de aristas a recorrer, modelado por una colección paralela. Dichas aristas, además de los puntos de origen y destino, se caracterizan por una profundidad, que es la distancia desde el punto de origen del camino a buscar y la arista considerada, y una marca de procesado. Las lı́neas 2 a 6 de la figura 5.3 muestran la definición de la clase Edge que modela las aristas. Problema El objetivo principal consiste en localizar, en caso de que exista, un camino entre dos puntos dados, con la condición de que dicho camino sea el más corto posible. La idea básica reside en ir buscando, desde aquellas aristas cuyo origen coincide con el punto de partida, otras que conecten con ellas, y ası́ sucesivamente hasta localizar un 1 // A r i s t a 2 class Edge { 3 int source , destination 4 int depth 5 boolean mark 6 } 7 // A r i s t a i n i c i a l 8 my_edge = searched_edge ; 9 my_edge . depth = 1 ; 10 // Marcado d e l primer n i v e l 11 Foreach edge : edge_list { 12 set edge . depth = 1 , if edge . source == my_edge . source 13 set final_edge = edge , if also edge . destination = my_edge . destination 14 } Figura 5.3: Algoritmo de búsqueda de aristas iniciales de ShortestPath 5.1. Programas de prueba 61 1 // Búsqueda de b o r d e s c o n e c t a d o s 2 // V a r i a n t e A: Fuerza b r u t a 3 while final_edge not found { 4 Edge p = any edge in set with p . mark==0 and p . depth==my_edge . depth 5 if p not found then 6 7 break else { 8 set p . mark = 1 ; 9 set my_edge . source = p . destination ; 10 incr my_edge . depth ; 11 Foreach edge { 12 set depth = my_edge . depth , if edge . source==my_edge . source 13 set final_edge = edge , if also edge . destination==my_edge . destination 14 } 15 decr my_edge . depth ; 16 } 17 incr my_edge . depth ; 18 } Figura 5.4: Variante A del algoritmo de búsqueda de aristas conectadas de ShortestPath 62 5. Evaluación 1 // Búsqueda de b o r d e s c o n e c t a d o s 2 // V a r i a n t e B: Cruce de l i s t a s 3 while final_edge not found { 4 Edge p = any edge in edge_list with p . mark==0 and p . depth==my_edge . depth 5 if p not found then 6 7 break else { 8 Foreach Pair ( e1 , e2 ) : edge_list , not equals { 9 if e1 . depth==my_edge . depth and e1 . destination==e2 . source and e2 . depth==0 then { 10 set e2 . depth=my_edge . depth+1 11 set final_edge=e2 , if e2 . destination==final_destination 12 } 13 } 14 incr current_depth 15 incr my_edge . depth 16 } 17 } Figura 5.5: Variante B del algoritmo de búsqueda de aristas conectadas de ShortestPath 5.1. Programas de prueba 63 1 // R e c o r r i d o i n v e r s o d e l camino 2 if final_edge not found 3 END : Path not found 4 else 5 while my_edge . depth >0 { 6 print final_edge 7 decr my_edge . depth 8 if my_edge . depth >0 then 9 Edge final_edge = any edge in edge_list with edge . depth==my_edge . depth and edge . destination==final_edge . source ) 10 11 } } Figura 5.6: Algoritmo de recorrido inverso del camino localizado por ShortestPath borde cuyo destino sea el punto final de la búsqueda. Para ello se ha implementado un algoritmo con dos variantes que revisan las aristas de acuerdo a unas mismas condiciones, pero utilizando operaciones diferentes durante el proceso de búsqueda. En concreto, mientras que la primera variante recorre todas las aristas del mapa intentando seleccionar las siguientes en cada iteración, la segunda implementa una relación que descarta en cada paso gran cantidad de bordes no conectados. Ambos algoritmos se ayudan de una arista auxiliar my edge que es inicializada en las lı́neas 8 y 9 del código de la figura 5.3, y que es utilizada para almacenar los sucesivos niveles de profundidad que se van alcanzado durante la ejecución (variable my edge.depth) ası́ como los puntos de origen y destino a comprobar en cada iteración. Algoritmo 1. Localización de las artistas con origen en el punto de partida. En este proceso, desarrollado en la figura 5.3, el bucle de la lı́neas 11 a 14 recorre todo el mapa buscando y marcando aquellas aristas cuyo punto de partida coincida con el inicio del camino (lı́nea 12), además de controlar si alguna de dichas aristas es la final 64 5. Evaluación (lı́nea 13). Para el marcado de las aristas puede emplearse la operación apply() de la librerı́a. 2. Búsqueda de las aristas conectadas con las marcadas en el paso anterior. Las figuras 5.4 y 5.5 muestran las dos variantes planteadas en esta parte del algoritmo: Variante A (figura 5.4): Mientras existan aristas sin marcar y de profundidad my edge.depth (condición comprobada en las lı́neas 4 a 6), se marcan aquellas que parten de alguno de los puntos finales de las seleccionadas en el paso anterior (lı́nea 8). Las aristas buscadas con la instrucción de la lı́nea 4 pueden ser seleccionadas con la operación select(). Finalmente, en caso de que no se haya alcanzado el punto de destino, se pasa a procesar las aristas de profundidad siguiente. Variante B (figura 5.5): Las instrucciones de las lı́neas 8 a 13 calculan el producto cartesiano de todas las aristas sin marcar y de profundidad my edge.depth, previamente seleccionadas según la condición de la lı́nea 4, con las del resto del mapa. De dicho producto se extraen aquellos pares cuya primera arista tenga por punto inicial alguno de los puntos finales de las aristas seleccionadas en el paso anterior. La obtención de las aristas conectadas puede realizarse utilizando la operacion relation() de la librerı́a, utilizando la condición antes comentada como condición de la relación. 3. Repetición del proceso anterior para la profundidad siguiente hasta localizar una arista que sea final. En el caso de la variante A, el control de profundidad se realiza mediante el incremento y decremento de my edge.depth en las lı́neas 10, 15 y 17 de la figura 5.4. En la variante B, este proceso se lleva a cabo en la lı́nea 14 de la figura 5.5. 4. Una vez alcanzado el final se recorre el camino inversamente para identificar cada arista marcada. En este paso, reflejado en la figura 5.6, se realiza el trabajo inverso al de los pasos 2 y 3: partiendo de la última arista se va decrementando la profundidad en la lı́nea 7 y se localiza de entre todas las aristas de dicha profundidad aquella que pertenezca al camino (lı́nea 9). Esta condición serı́a la 5.2. Estudio de programabilidad 65 adecuada para una hipotética implementación paralela con select(). Para finalizar, el proceso se repite hasta alcanzar la arista inicial (condición de salida del bucle de la lı́nea 5), que fue marcada como procesada y de profundidad 1 al principio del algoritmo. 5.2. Estudio de programabilidad Uno de los principales objetivos de este proyecto es proveer al programador de herramientas que faciliten la programación de aplicaciones paralelas para sistemas multinúcleo. Para comprobarlo se han planteado una serie de pruebas en las que se compara la implementación de un programa de ejemplo utilizando las clases proporcionadas por la librerı́a ParallelCollections con otra versión paralelizada de forma manual: Versión con ParallelCollections: Estas implementaciones se sirven directamente de las clases y métodos proporcionados por ParallelCollections para la realización de operaciones paralelas sobre las colecciones de datos. Versión manual: Estas versiones manipulan directamente colecciones de datos sobre las que se utilizan de forma explı́cita las funcionalidades de threading proporcionadas por el paquete java.util.concurrent. Con esta comparación se pretende poner de manifiesto la mayor facilidad de programación que supone el uso de la librerı́a sobre la gestión explı́cita de la paralelización. Como la facilidad de programación es un concepto relativamente subjetivo, para realizar estas pruebas se comparará el número de lı́neas de código necesarias para la implementación de ambas versiones, utilizando para estas mediciones las herramientas SLOCCount, que a continuación se presentan. SLOCCount SLOCCount es un conjunto de herramientas diseñadas para el conteo de lı́neas de código fuente1 fı́sicas en sistemas software potencialmente grandes y que se encuentra 1 De ahı́ SLOC, Source Lines Of Code 66 5. Evaluación disponible bajo licencia GPL2 . Desarrollado por David A. Wheeler y originariamente destinado a la medición del código de una distribución GNU/Linux completa, puede utilizarse para la evaluación del tamaño de cualquier sistema software[18]. Los resultados generados por el programa, además del número de SLOCs de los ficheros fuente analizados contienen un pequeño análisis basado en COCOMO3 , un modelo matemático empı́rico utilizado para la estimación de costes de software. Dichos costes se calculan tanto a partir de las SLOCs como de otros atributos de software, hardware y desarrollo definidos en el propio modelo, devolviendo valores en unidades tales como salarios mensuales y horas de trabajo por hombre. 5.2.1. Programabilidad de los códigos de ejemplo A continuación se adjuntan los resultados de realizar este mismo tipo de prueba con el código de los programas de ejemplo comentados al principio del presente capı́tulo. Para cada problema se han procesado con SLOCCount las dos versiones antes comentadas, una basada en la librerı́a ParallelCollections y otra que utiliza directamente colecciones nativas de Java y thread pools de java.util.concurrent. Problema ParallelCollections java.util.concurrent Reducción SalaryIncrease 16 47 66 % AirControl 31 86 64 % ShortestPath1 45 122 63 % ShortestPath2 62 117 47 % Tabla 5.1: Lı́neas de código de los problemas de ejemplo con y sin ParallelCollections Las cifras presentadas en la tabla 5.1 concuerdan con la afirmación realizada a este mismo respecto en el apartado 5.1.1, manteniéndose la reducción de código en las soluciones a los problemas planteados utilizando ParallelCollections. 2 3 GNU General Public License COnstructive COst MOdel 5.3. Análisis de rendimiento y escalabilidad 5.3. 67 Análisis de rendimiento y escalabilidad Si algo se espera de una estructura de datos que soporte la realización de operaciones paralelas sobre sus elementos, evidentemente se trata de que, en lı́neas generales, se aprecie una mejora del rendimiento respecto de sus implementaciones equivalentes en forma secuencial cuando se ejecutan sobre sistemas multinúcleo. Ası́ mismo, resulta de interés comprobar cómo responde la librerı́a al aumento de recursos a su disposición, es decir, a su ejecución en procesadores con un elevado número de núcleos. Para ello se han planteado una serie de pruebas de rendimiento con las que se pretende analizar el aprovechamiento que la librerı́a hace de los recursos a medida que estos crecen, tanto a nivel software (subconjuntos y threads) como hardware (núcleos y memoria principal). Este conjunto de pruebas ha sido ejecutado en el clúster “NM” del Departamento de Electrónica y Sistemas de la Universidade da Coruña, sobre el que corre un sistema operativo Linux CentOS 5.1 de 64 bits con kernel 2.6.18 y un Java Runtime Environment de versión 1.6.0 07. En concreto se han utilizado los siguientes tipos de nodo: Nodo “c1”: 8 núcleos repartidos en 2 procesadores Intel Xeon Quad-core E5440 a 2,83 GHz y un total de 16 GB de memoria RAM. Nodo “c2”: 24 núcleos repartidos en 4 procesadores Intel Xeon Hexa-core E7450 a 2,40 GHz y un total de 32 GB de memoria RAM. 5.3.1. SalaryIncrease Los códigos de prueba planteados en el ejemplo SalaryIncrease no han sido incluidos en la evaluación de rendimiento debido a que la carga computacional de las operaciones que en ellos se realizan no resulta suficiente como para obtener mejoras de rendimiento respecto de implementaciones secuenciales del problema. 68 5. Evaluación 5.3.2. AirControl Para las simulaciones con el programa de control áereo se han definido zonas de dimensiones ocupadas por 50000 aviones capaces de volar a una velocidad máxima de 31 y estableciendo como distancia de seguridad 15 unidades. En cada ejecución se ha ido modificando de manera creciente el número de threads disponibles en el pool, variando su tamaño en intervalos de potencias de 2. Todos los tiempos reflejados en esta sección se encuentran en milisegundos y han sido resultado de obtener la media de 10 ejecuciones en las condiciones antes descritas. Modo Secuencial 1 thread 2 threads 4 threads 8 threads Tiempo (ms) 63224 72694 26792 9442 5279 Tabla 5.2: Tiempos de ejecución de AirControl en milisegundos sobre un nodo “c1” Rendimiento de AirControl ejecutado en c1 (8 núcleos) 16 14 Aceleración obtenida 12 10 8 6 4 2 0 1 2 3 4 5 Número de threads 6 7 8 Figura 5.7: Aceleración obtenida para AirControl sobre un nodo “c1” de 8 núcleos En la tabla 5.2 puede comprobarse que los tiempos de ejecución se van reduciendo 5.3. Análisis de rendimiento y escalabilidad 69 notablemente a medida que se aumenta el número de threads disponibles en el pool. A partir de dichos tiempos se ha construido la gráfica de la figura 5.7, en la cual se puede comprobar cómo la colección paralela aprovecha los recursos disponibles a medida que éstos crecen, puesto que se obtienen aceleraciones cercanas a las óptimas, representadas por la lı́nea roja. Esto es ası́ salvo en el caso de 1 thread, ya que la carga de trabajo es la misma que para el caso secuencial, pero añadiendo la creación y lanzamiento de un nuevo thread, lo que hace que el tiempo total de la operación sea ligeramente superior. Modo 8 threads 16 threads 32 threads 64 threads Tiempo (ms) 5279 5123 4620 3974 Tabla 5.3: Tiempos de ejecución de AirControl en milisegundos sobre un nodo “c1” para 8, 16, 32 y 64 núcleos Ası́ mismo, la tabla 5.3 muestra la evolución del rendimiento para un número de threads y subcolecciones superior al de núcleos del nodo. Los datos muestran cómo, en este caso, también se obtienen mejoras en el rendimiento al reducirse ligeramente los tiempos de ejecución. Modo Secuencial 1 thread 2 threads Tiempo (ms) 67137 77542 40943 4 threads 8 threads 16 threads 24 threads 11949 5434 3317 2229 Tabla 5.4: Tiempos de ejecución de AirControl en milisegundos sobre un nodo “c2” de 24 núcleos Tanto de la tabla 5.4 como de la gráfica de la figura 5.8, que reflejan respectivamente los tiempos medios y la aceleración obtenidos para la ejecución de AirControl sobre el nodo “c2” de 24 núcleos, pueden deducirse conclusiones similares a las propuestas a partir de los resultados arrojados por la ejecución de AirControl sobre el nodo de 70 5. Evaluación Rendimiento de AirControl ejecutado en c2 (24 núcleos) 35 30 Aceleración obtenida 25 20 15 10 5 0 0 5 10 15 20 Número de threads 25 30 35 Figura 5.8: Aceleración obtenida para AirControl sobre un nodo “c2” de 24 núcleos 8 núcleos. Por una parte, a mayor número de threads mayor rendimiento; por otra, sigue sucediendo el mismo fenómeno de ralentización para la ejecución con un único hilo a causa de realizarse el mismo trabajo que en secuencial y, además, la creación y lanzamiento del thread. 5.3.3. ShortestPath Para las simulaciones realizadas con el programa de localización de caminos se han generado de forma aleatoria mapas de 100.000 aristas sobre los que se han insertado un camino conocido de 400 pasos entre los puntos 5 y 2000. Al igual que en las pruebas de AirControl, en cada ejecución se ha ido modificando de manera creciente el número de threads disponibles en el pool, variando su tamaño en intervalos de potencias de 2. Todos los tiempos reflejados se encuentran en milisegundos y han sido resultado de obtener la media de 10 ejecuciones en las condiciones antes descritas. 5.3. Análisis de rendimiento y escalabilidad 71 ShortestPath1 Modo Secuencial 1 thread 2 threads 4 threads 8 threads Tiempo (ms) 12730 17757 12076 8340 5162 Tabla 5.5: Tiempos de ejecución de ShortestPath1 en milisegundos sobre un nodo “c1” de 8 núcleos Rendimiento de ShortestPath1 ejecutado en c1 (8 núcleos) 8 7 Aceleración obtenida 6 5 4 3 2 1 0 1 2 3 4 5 Número de threads 6 7 8 Figura 5.9: Aceleración obtenida para ShortestPath1 sobre un nodo “c1” de 8 núcleos La tabla 5.5 y la gráfica 5.9 reflejan respectivamente los tiempos medios y la aceleración obtenidas para la ejecución de ShortestPath sobre el nodo “c1” de 8. Analizando estos datos puede verse que con el aumento del tamaño de pool el rendimiento no escala tan bien como sucede en el caso de AirControl. Aunque los tiempos de ejecución siguen disminuyendo, lo hacen en menor medida; y la aceleración obtenida, aunque importante, se aleja notablemente de la óptima representada en rojo en la gráfica. 72 5. Evaluación Modo Secuencial 1 thread 2 threads Tiempo (ms) 9207 10044 7217 4 threads 8 threads 16 threads 24 threads 4577 4115 2467 1376 Tabla 5.6: Tiempos de ejecución de ShortestPath1 en milisegundos sobre un nodo “c2” de 24 núcleos Rendimiento de ShortestPath1 ejecutado en c2 (24 núcleos) 25 Aceleración obtenida 20 15 10 5 0 0 5 10 15 Número de threads 20 25 Figura 5.10: Aceleración obtenida para ShortestPath1 sobre un nodo “c2” de 24 núcleos La tabla 5.6 y la gráfica 5.10, construidas a partir de los datos obtenidos para la ejecución sobre 24 núcleos, muestran información similar a la que resulta para 8, observándose también un menor aumento del rendimiento a medida que crece el tamaño de pool. 5.3. Análisis de rendimiento y escalabilidad 73 Modo 24 threads 32 threads 48 threads 64 threads Tiempo (ms) 5593 4291 2349 2124 Tabla 5.7: Tiempos en milisegundos de ShortestPath1 para 24, 32, 48 y 64 núcleos sobre “c2” Para la toma de tiempos de la tabla 5.7 se ha utilizado un nuevo conjunto de aristas generado aleatoriamente, por ello los tiempos para 24 hilos de las tablas 5.6 y 5.7 difieren. De los datos de la tabla puede desprenderse que el uso de un thread pool y de un número de subcolecciones mayores que el número de núcleos del nodo supone una mejora importante en el rendimiento, reduciéndose notablemente el tiempo de ejecución del algoritmo. ShortestPath2 El tiempo necesario para localizar y subsanar diversos errores en las implementaciones comparativas en secuencial de los casos de prueba anteriores han impedido la realización de un estudio completo de rendimiento de la librerı́a para su uso con el segundo algoritmo del camino más corto. Capı́tulo 6 Conclusiones A continuación se presentan las conclusiones resultantes del trabajo desarrollado hasta la obtención del paquete ParallelCollections junto con diferentes posibilidades de continuación y mejora del presente proyecto. 6.1. Resumen del trabajo realizado Con la implementación de la presente librerı́a se ha conseguido obtener un paquete de colecciones Java que soportan operaciones paralelas, facilitando ası́ al programador la tarea de crear aplicaciones que puedan aprovechar las capacidades de los procesadores multinúcleo. Para alcanzar este objetivo, ha sido necesario estudiar previamente qué opciones ofrece el lenguaje de programación Java para la extracción del paralelismo, ası́ como las diferentes peculiaridades de las clases nativas del framework Collections en que se basan las colecciones genéricas implementadas. Una vez conseguida una implementación estable y funcional de la librerı́a, se ha procedido al análisis de su rendimiento y programabilidad utilizando diversos ejemplos de prueba que en cierto modo aproximan posibles casos reales de utilización del paquete ParallelCollections. 75 76 6. Conclusiones 6.2. Objetivos alcanzados Los resultados reflejados en el capı́tulo 5 certifican que se han alcanzado los principales objetivos de este proyecto: Implementación de un paquete de clases de colección sobre las que es posible realizar una serie de operaciones de forma paralela, aprovechando ası́ la presencia de varios núcleos en el sistema. La librerı́a implementada facilita la programación paralela de sistemas multinúcleo sin necesidad de realizar un gran esfuerzo de programación ni aprendizaje del funcionamiento de dicho tipo de sistemas. En lı́neas generales la librerı́a implementada supone una mejora de respecto de otras implementaciones, tanto en facilidad de programación como en aprovechamiento satisfactorio de la presencia de varios procesadores. 6.3. Trabajo futuro Esta sección se proponen una serie de modificaciones y/o añadidos que dotarı́an a la librerı́a implementada de una mayor robustez y seguridad de utilización. 6.3.1. Mejora de la genericidad La mayorı́a de las clases e interfaces del paquete incorporan genericidad mediante el uso de parámetros formales de tipo. Esta aproximación, aunque ha facilitado enormemente la escritura del código, puede plantear algunos problemas a la hora de crear colecciones susceptibles de incoporar elementos de clases diferentes pero con una superclase común. Para ello debe revisarse la posibilidad de añadir también wildcards1 , tanto normales como acotadas, en la definición de tipos y clases genéricas. 1 Véase apartado 3.2.3. 6.3. Trabajo futuro 6.3.2. 77 Incorporación de nuevas operaciones Partiendo de la base que proporciona ParallelCollections, existen una serie de añadidos al mismo que pueden resultar de interés, destacando la incorporación de nuevas operaciones, ya que las soportadas por las colecciones del paquete se reducen a aquellas más elementales e intuitivamente paralelizables. Sin embargo, existen muchas otras operaciones más complejas con posibilidad de ser implementadas. Un ejemplo de ello serı́a el framework MapReduce de Google, dedicado al procesamiento y generación de grandes conjuntos de datos. Para su utilzación el programador especifica una función de mapeo encargada de procesar pares clave-valor, resultando otro conjunto intermedio de pares. Una vez obtenido dicho conjunto se aplica sobre sus elementos una función de reducción que reúne todos los valores intermedios asociados a una misma clave intermedia. Esta forma de programar, que supone la paralelización automática de las operaciones para su ejecución en grandes clústeres, permite a programadores sin experiencia en sistemas paralelos y/o distribuidos servirse de forma fácil y rápida de los recursos que éstos ofrecen[19]. 6.3.3. Aplicación en entornos más realistas Los ejemplos básicos planteados utilizando la clase Employee ası́ como los programas descritos en el capı́tulo de pruebas, aunque adecuados para un análisis general del aprovechamiento de recursos por parte de las operaciones paralelas implementadas, no suponen una gran carga de trabajo y sólo son parcialmente representativos de los patrones de paralelismo y de las cargas de trabajo que pueden encontrarse en entornos reales de trabajo. Serı́a recomendable incorporar otros códigos que, aún basándose en las operaciones elementales incluidas en las colecciones paralelas, supongan mayores cargas computacionales y hagan un uso más intensivo de los diferentes núcleos del procesador. Apéndice A Manual de usuario/programador El presente capı́tulo constituye el manual de usuario de la librerı́a de colecciones ParallelCollections. A continuación se repasa brevemente cómo funcionan las colecciones paralelas de esta librerı́a proporcionando pequeñas explicaciones, con sus correspondientes ejemplos de código, con las que el usuario puede instanciar sus propias colecciones ası́ como insertar y eliminar elementos de las mismas. Posteriormente, se presentan de manera sencilla las operaciones paralelas implementadas y cómo pueden personalizarse mediante el paso de interfaces. Finalmente, se incluyen una serie de advertencias y comentarios que el programador futuro usuario de la librerı́a debe tener en cuenta para evitar problemas relacionados con las estructuras que gestionan los threads. A.1. Creación de estructuras Para la instanciación de nuevas colecciones se proporcionan dos constructores, uno por defecto y otro parametrizado. Mientras que el constructor por defecto crea una nueva colección con tantos subconjuntos como núcleos haya disponibles en el sistema y un thread pool de igual tamaño, la versión parametrizada permite definir estos parámetros manualmente. Las figuras A.1 y A.2 ejemplifican ambos casos mediante la instanciación de conjuntos paralelos de números enteros: 79 80 A. Manual de usuario/programador 1 ParallelSet<Integer> conjunto_por_defecto = new ParallelSet<Integer >() ; Figura A.1: Instanciación de un ParallelSet utilizando el constructor por defecto 1 ParallelList<Integer> listaparametrizada = new ParallelList<Integer >() ; Figura A.2: Instanciación de una ParallelList mediante el constructor parametrizado A.2. Manipulación de datos Una vez detalladas las opciones existentes para la instanciación de nuevas colecciones paralelas, se procede a detallar cómo manipular datos con las mismas. Como se puede comprobar en el apartado 4.2.4, las clases de colecciones de ParallelCollections implementan los métodos exigidos por la interfaz Set1 , entre los que se encuentran los siguientes: boolean add(T e): Intenta añadir un elemento e al conjunto, devolviendo un valor lógico según haya sido posible o no. void clear(): Vacı́a de elementos el conjunto. boolean contains(Object o): Comprueba si un objeto o forma parte del conjunto. boolean isEmpty(): Comprueba si el conjunto está vacı́o o no. Iterator<T> iterator(): Devuelve un iterator con el que se pueden recorrer los elementos del conjunto. boolean remove(Object o): Intenta eliminar el elemento Object o al conjunto, devolviendo un valor lógico según haya sido posible o no. int size(): Obtiene el número de elementos del conjunto paralelo. 1 Para mayor detalle, revisar el apartado arriba referido y los Javadoc oficial del API y adjunto del paquete. A.3. Operaciones paralelas 1 // Se d e f i n e un c o n j u n t o de empleados 2 ParallelSet<Employee> staff = new ParallelList<Employee >() ; 81 3 4 // Se añaden dos empleados ya c r e a d o s e1 y e2 5 staff . add ( e1 ) ; 6 stadd . add ( e2 ) ; 7 8 // Se imprimen l o s empleados de l a l i s t a con un i t e r a d o r 9 Iterator<Employee> iter = staff . iterator ( ) ; 10 while ( iter . hasNext ) { 11 12 System . out . println ( iter . next ( ) ) ; } Figura A.3: Uso de los métodos de manipulación de datos de ParallelList En la figura A.3 puede observarse que la interfaz de las clases se utiliza de la misma manera que la de cualquier otra colección de Java, permitiendo añadir y eliminar elementos, recorrer las listas, etc. A.3. Operaciones paralelas ParallelCollections incorpora a sus colecciones algunas de las operaciones más empleadas en procesamiento paralelo, ası́ como la versión secuencial equivalente para cada una de ellas. A continuación se explica, mediante diferentes explicaciones basadas en los ejemplos de código planteados en el apartado 4.2.3 de la memoria, cómo utilizar este conjunto de operaciones. Apply En el ejemplo de la figura A.4 se calculan los nuevos sueldos de los empleados de una empresa si se les aplica una subida del 3 %. Para ello se define la interfaz Application<Employee> sueldoNuevo (lı́neas 1-5), implementando el cálculo en cuestión en su método apply() (lı́nea 3). Finalmente se llama al método del conjunto paralelo asociado a la operación (apply(), lı́nea 6). 82 A. Manual de usuario/programador 1 Application<Employee> sueldoNuevo = new Application<Employee >() { 2 public void apply ( Employee element ) { 3 element . setIncome ( Math . round ( element . getIncome ( ) ∗ 1 . 0 3 ) ) ; 4 } 5 }; 6 staff . apply ( sueldoNuevo ) ; Figura A.4: Ejemplo de uso del método apply() y la interfaz Application Reduce 1 Reduction<Employee> empleadoMejorPagado = new Reduction<Employee >() { 2 public Employee reduce ( Employee a , Employee b ) { 3 if ( a . getIncome ( )>b . getIncome ( ) ) 4 return a ; 5 else 6 return b ; 7 } 8 public Employee neutral ( ) { 9 return new Employee ( 0 , 0 ) ; 10 } 11 } ; 12 Employee best_paid = staff . reduce ( empleadoMejorPagado ) ; Figura A.5: Ejemplo de uso del método reduce() y la interfaz Reduction En el ejemplo de la figura A.5 se muestra cómo utilizar una interfaz Reduction (lı́neas 1-11). Por una parte, el método reduce() implementado en las lı́neas 2 a 7 del código va combinando pares de empleados de acuerdo a la reducción implementada, seleccionando en este caso el que más cobra de los dos. Por otra, el método neutral() (lı́neas 8-11) se hace necesario para comenzar el proceso, permitiendo ası́ que el primer empleado extraı́do del conjunto forme un par con el neutro de la operación y sea, por tanto, tenido en cuenta la hora de obtener el resultado final. A.3. Operaciones paralelas 83 Select 1 Comparator<Employee> sueldoMayor1500 = new Comparator<Employee >() { 2 public boolean hit ( Employee element ) { 3 return element . getIncome > 1 5 0 0 ; 4 } 5 }; 6 ParallelSet<Employee> staffMayor1500 = staff . select ( sueldoMayor1500 ) ; Figura A.6: Ejemplo de uso del método select() y la interfaz Comparator La figura A.6 muestra un ejemplo de uso de la interfaz Comparator para realizar una operación select(). En concreto, se desea seleccionar qué empleados de una empresa cobran más de 1.500 euros. Para ello se implementa en las lı́neas 1 a 5 una interfaz Comparator que comprueba mediante el método hit() si el sueldo de cada empleado supera la cantidad establecida en la lı́nea 3. Una vez definida la interfaz, ésta es pasada como parámetro al método select() del conjunto para generar el resultado de la selección, que se almacena en otro conjunto paralelo definido a tal efecto. Map 1 Mapping<Double , Employee> listaSueldos = new Mapping<Double , Employee >() { 2 public Double map ( Employee element ) { 3 return element . getIncome ( ) ; 4 } 5 }; 6 ParallelSet<Double> incomes = staff . map ( listaSueldos ) ; Figura A.7: Ejemplo de uso del método map() y la interfaz Mapping En la figura A.7 se ha implementado una operación de mapeo consistente en extraer los sueldos cobrados por todos los empleados de la plantilla. En este caso, la 84 A. Manual de usuario/programador interfaz Mapping<Double,Employee> listaSueldos (lı́neas 1-5) obtiene el sueldo de cada empleado, que luego se almacena en un nuevo conjunto paralelo listaSueldos (lı́nea 6). Como la operación realizada tiene como resultado objetos de clase diferente a del conjunto, la declaración de la interfaz necesita dos parámetros de tipo; el del conjunto, Employee y el de los valores a devolver, Double. Relation 1 Relationship<Employee , Employee> mejorPagadoQue = new Relationship<Employee , Employee >() { 2 public boolean isReflexive ( ) { 3 return false ; 4 } 5 public boolean isSymmetric ( ) { 6 return false ; 7 } 8 public boolean areRelated ( Employee e1 , Employee e2 ) { 9 return e1 . getIncome ( ) > e2 . getIncome ( ) ; 10 } 11 public boolean reflexCond ( Employee e1 , Employee e2 ) { 12 return e1 . equals ( e2 ) ; 13 } 14 } ; 15 ParallelSet<Pair<Employee , Employee>> paresMejorPagadoQue = staff . relation ( staff , mejorPagadoQue ) ; Figura A.8: Ejemplo de uso del método relation() y la interfaz Relationship El fragmento de código de la figura A.8 muestra un ejemplo de uso de la operación relation(). En concreto, genera una lista de pares <Employee,Employee> tales que el primer empleado del par cobre más que el segundo. Para el cálculo de esta relación se implementa la interfaz mejorPagadoQue, de tipo Relationship<Employee,Employee> A.4. Advertencias y comentarios 85 (lı́neas 1-14). La relación propiamente dicha la establece el método areRelated(), que comprueba si los elementos de un par cumplen la condición deseada, utilizando el resto de métodos de la interfaz para determinar sus propiedades. Con isReflexive() e isSymmetric() (lı́neas 2 y 5) el programador determina si la relación a calcular es reflexiva y/o simétrica. En el caso concreto de mejorPagadoQue sucede que un empleado no puede estar relacionado consigo mismo (no puede cobrar más que sı́ mismo) y que si un empleado e1 cobra más que otro e2, es imposible que se dé la relación en sentido contrario. reflexCond() implementa la condición para que un par sea reflexivo. La mayorı́a de relaciones calculadas serán entre conjuntos del mismo tipo, de manera que los pares asociados a una relación reflexiva serán aquellos en los que el primer elemento y el segundo sean iguales. Por este motivo el método reflexCond() normalmente se implementa tal y como aparece en la lı́nea 14. Una vez completada la definición de la relación a calcular, con su condición y sus propiedades, se llama al método relation() del conjunto paralelo pasando como parámetros la lista con la que se desean cruzar los datos (en este caso la misma) y la interfaz Relationship correspondiente (mejorPagadoQue). Esta operación es llamada por la instrucción ejecutada en la lı́nea 16 del código, resultando un conjunto paralelo de elementos <Pair<Employee,Employee>> con los pares de empleados que cumplen la relación. A.4. Advertencias y comentarios Para finalizar este manual, se realizan una serie de advertencias y recordatorios de importancia acerca del uso del paquete ParallelCollections. A.4.1. Cierre del thread pool Los thread pools proporcionados por los métodos factorı́a del framework Executors necesitan ser cerrados explı́citamente una vez dejen de utilizarse; de no hacerse, una 86 A. Manual de usuario/programador vez finalizada la última operación paralela éste permanecerá a la espera de más tareas en forma de threads de forma indefinida, bloqueando la ejecución de todo el programa. Para evitar esto, basta con llamar al método shutdownPool() de la colección, que a su vez llama al método shutdown() del pool, el cual detiene de forma segura y ordenada el funcionamiento de esta estructura. A.4.2. Documentación de la librerı́a Ya para terminar, recordar al programador y futuro usuario de este paquete Java que tiene a su disposición un CD con el código y las fuentes tanto de la librerı́a ParallelCollections como de los ejemplos implementados, ası́ como toda la documentación de las mismas en formato Javadoc. Además puede compilar y ejecutar los ejemplos de prueba comentados en la presente memoria generando los correspondientes ejecutables en formato JAR tal y como se explica en el fichero README incluido en la distribución. Bibliografı́a [1] Moore, G. E., “Cramming more components onto integrated circuits.” Disponible en: ftp://download.intel.com/museum/Moores_Law/Articles-Press_ Releases/Gordon_Moore_1965_Article.pdf, 1965. [2] Garcı́a, A., Delgado, J. J., and Castañeda, S., “Metodologı́as de paralelización.” Disponible en: http://telematica.cicese.mx/computo/super/ cicese2000/paralelo/, 2002. [3] Butenhof, D. R., Programming with POSIX Threads. Boston, Massachusetts: Addison-Wesley, 1997. [4] Chandra, R., Dagum, L., Kohr, D., Maydan, D., McDonald, J., and Menon, R., Parallel programming in OpenMP. San Francisco, California: Morgan Kaufmann, 2001. [5] “OpenMP: About OpenMP.” Disponible en: http://openmp.org/wp/ about-openmp/, 2004. [6] Andrade, D., Fraguela, B. B., Brodman, J., and Padua, D., “Task-parallel versus data-parallel library-based programming in multicore systems,” 2009. [7] Reinders, J., Intel Threading Building Blocks. Sebastopol, California: O’Reilly, primera ed., 2007. [8] University of Illinois at Urbana-Champaign, “Hierarchically Tiled Arrays.” Web oficial del proyecto: http://polaris.cs.uiuc.edu/hta/index.html, 2008. 87 88 BIBLIOGRAFÍA [9] Gosling, J. and McGilton, H., “The Java Language Environment white paper.” Disponible en: http://java.sun.com/docs/white/langenv/index.html, 1996. [10] Lea, D., Concurrent programming in Java design, principles and patterns. Reading, Massachusetts: Addison-Wesley, segunda ed., 2000. [11] Drake, D. G., “Introduction to Java threads: A quick tutorial on how to implement threads in Java.” Disponible en: http://www.javaworld.com/javaworld/ jw-04-1996/jw-04-threads.html, 1996. [12] Goetz, B., “Introduction to Java threads.” Disponible bajo registro en: http: //www.ibm.com/developerworks/edu/j-dw-javathread-i.html, 2002. [13] Goetz, B., Java Concurrency in Practice. Upper Saddle River, New Jersey: Addison-Wesley, 2008. [14] Oaks, S. and Wong, H., Java Threads. Sebastopol, California: O’Reilly, tercera ed., 2004. [15] Goetz, B., “Concurrency in JDK 5.0.” Disponible bajo registro en: http://www. ibm.com/developerworks/edu/j-dw-java-concur-i.html, 2004. [16] Bracha, G., “Generics in the Java Programming Language.” Disponible en: http: //java.sun.com/j2se/1.5/pdf/generics-tutorial.pdf, 2004. [17] Sun Microsystems, “Set Interface. Java 6 API Specification.” Disponible en: http://java.sun.com/javase/6/docs/api/java/util/Set.html, 2008. [18] Wheeler, D. A., “SLOCCount User’s Guide.” Disponible en: http://www. dwheeler.com/sloccount/sloccount.html, 2004. [19] Dean, J. and Ghemawat, S., “MapReduce: Simplified Data Processing on Large clusters.” Disponible en: http://labs.google.com/papers/mapreduce-osdi04. pdf, 2004.