Download Implementación de una librer´ıa de colecciones genéricas en Java

100

101

102

103

104

105

106

Document related concepts

no text concepts found

Transcript

FACULTADE DE INFORMÁTICA
Departamento de Electrónica e Sistemas
Proxecto de Fin de Carreira de Enxeñerı́a Técnica en Informática
de Sistemas
Implementación de una librerı́a de colecciones
genéricas en Java para computación paralela
Autor: Jorge Fernández Fabeiro
Tutor: Diego Andrade Canosa
Director: Basilio Bernardo Fraguela Rodrı́guez
A Coruña, 15 de julio de 2009
Especificación
Tı́tulo:
Implementación de una librerı́a de colecciones genéricas en Java para computación paralela
Clase:
Proyecto de investigación y desarrollo
Autor :
Jorge Fernández Fabeiro
Tutor :
Diego Andrade Canosa
Director :
Basilio Bernardo Fraguela Rodrı́guez
Tribunal :
Diego Andrade Canosa
Manuel Carlos Arenaz Silva
Guillermo López Taboada
Fecha de lectura:
15 de julio de 2009
Calificación:
i
Un espı́ritu noble “ensanchece” al hombre más pequeñ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 años no habrı́an sido lo mismo sin el apoyo de todos aquellos
compañeros de facultad en un principio, y buenos amigos después, que a lo largo de
este tiempo me han acompañado en los buenos momentos y soportado en los malos.
Como serı́a complicado nombrar a todos, al menos me gustarı́a hacer mención especial
a Francisco Javier Álvarez, Iván Cores y Diego Darriba por haber compartido conmigo
sus experiencias sobre qué es y cómo se debe afrontar un Proyecto Final de Carrera.
Por último, y en absoluto por ello menos importante, agradezco a mis padres todo
el cariño y confianza depositados en mı́ a lo largo de estos años, dándoles gracias sobre
todo por haberme inculcado valores como la constancia en el trabajo y el afán de superació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 número cada vez
mayor de núcleos que comparten un mismo sistema de memoria. Ésto da lugar a la necesidad de que los programadores conozcan cómo aprovechar las capacidades de estos
sistemas empleando lenguajes, extensiones de lenguajes o librerı́as para la paralelización de sus aplicaciones. Existe especial interés en mejorar el proceso de paralelización
de lenguajes ampliamente extendidos en la industria como Java mediante la implementación de librerı́as que faciliten la labor del programador.
El objetivo del presente proyecto es la construcción de una librerı́a que implementa
una colección gené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 multinúcleo.
Palabras clave
Colecciones, Genericidad, Java, Multinúcleo, Orientación a Objetos, Paralelismo
vii
Índice general
1. Introducción
1
1.1. Estado del arte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.1.1. Paradigmas de organización de sistemas paralelos . . . . . . . . .
2
1.1.2. Programación multithreading . . . . . . . . . . . . . . . . . . . .
3
1.1.3. Paralelización de tareas vs. paralelizació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 ejecución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.2. Threading en Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.3. Implementación nativa . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.3.1. Ciclo de vida . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.3.2. Planificación y prioridades . . . . . . . . . . . . . . . . . . . . . .
14
2.3.3. Sincronización . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.4. Paquete java.util.concurrent . . . . . . . . . . . . . . . . . . . . . .
17
2.4.1. Colecciones seguras . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.4.2. Planificación avanzada . . . . . . . . . . . . . . . . . . . . . . . .
20
2.4.3. Sincronización avanzada . . . . . . . . . . . . . . . . . . . . . . .
23
2.4.4. Gestión de threads a bajo nivel . . . . . . . . . . . . . . . . . . .
26
ix
ÍNDICE GENERAL
x
3. Programación genérica en Java
29
3.1. Programación genérica . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
3.2. Implementación nativa . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
3.2.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
3.2.2. Clases genéricas
. . . . . . . . . . . . . . . . . . . . . . . . . . .
32
3.2.3. Wildcards y métodos genéricos . . . . . . . . . . . . . . . . . . .
33
3.3. Genericidad avanzada . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
3.3.1. Uso combinado de código gené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. Implementación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
4.2.1. Estructura de datos . . . . . . . . . . . . . . . . . . . . . . . . .
41
4.2.2. Gestión de threads . . . . . . . . . . . . . . . . . . . . . . . . . .
43
4.2.3. Operaciones paralelas . . . . . . . . . . . . . . . . . . . . . . . .
45
4.2.4. Interfaz del conjunto paralelo . . . . . . . . . . . . . . . . . . . .
50
5. Evaluació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 códigos de ejemplo
. . . . . . . . . . . .
66
5.3. Análisis de rendimiento y escalabilidad . . . . . . . . . . . . . . . . . . .
67
5.3.1. SalaryIncrease . . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
5.3.2. AirControl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
5.3.3. ShortestPath . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
Í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. Incorporación de nuevas operaciones . . . . . . . . . . . . . . . .
77
6.3.3. Aplicación en entornos más realistas . . . . . . . . . . . . . . . .
77
A. Manual de usuario/programador
79
A.1. Creación de estructuras . . . . . . . . . . . . . . . . . . . . . . . . . . .
79
A.2. Manipulació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. Documentación de la librerı́a . . . . . . . . . . . . . . . . . . . .
86
Í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 genéricas de Java . . . . . . . . . . . .
31
3.4. Extracto de la definición genérica de las interfaces List e Iterator . .
32
3.5. Definición genérica de Collection con wildcards y métodos genéricos .
35
3.6. Firma del método genérico copy() de Collection . . . . . . . . . . . .
35
4.1. Esqueleto del código para la gestión de threads . . . . . . . . . . . . . .
44
4.2. Ejemplo de uso del método apply() y la interfaz Application . . . . .
46
4.3. Ejemplo de uso del método reduce() y la interfaz Reduction . . . . . .
47
4.4. Ejemplo de uso del método select() y la interfaz Comparator . . . . .
48
4.5. Ejemplo de uso del método map() y la interfaz Mapping . . . . . . . . .
48
4.6. Ejemplo de uso del método relation() y la interfaz Relationship . .
49
4.7. Atributos y constructores de la clase ParallelSet . . . . . . . . . . . .
50
4.8. Métodos de configuración de la clase ParallelSet . . . . . . . . . . . .
51
4.9. Firma de los métodos de operación de ParallelSet . . . . . . . . . . .
52
4.10. Firma de los métodos de manipulació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 búsqueda de aristas iniciales de ShortestPath . . . . . . .
60
5.4. Variante A para búsqueda de aristas conectadas de ShortestPath . . .
61
xiii
xiv
ÍNDICE DE FIGURAS
5.5. Variante B para búsqueda de aristas conectadas de ShortestPath . . .
62
5.6. Algoritmo de recorrido inverso del camino localizado por ShortestPath
63
5.7. Aceleración de AirControl sobre un nodo “c1” de 8 núcleos . . . . . . .
68
5.8. Aceleración de AirControl sobre un nodo “c2” de 24 núcleos . . . . . .
70
5.9. Aceleración de ShortestPath1 sobre un nodo “c1” de 8 núcleos . . . . .
71
5.10. Aceleración de ShortestPath1 sobre un nodo “c2” de 24 núcleos . . . .
72
A.1. Instanciación de un ParallelSet utilizando el constructor por defecto .
80
A.2. Instanciación de una ParallelList mediante el constructor parametrizado 80
A.3. Uso de los métodos de manipulación de datos de ParallelList . . . . .
81
A.4. Ejemplo de uso del método apply() y la interfaz Application . . . . .
82
A.5. Ejemplo de uso del método reduce() y la interfaz Reduction . . . . . .
82
A.6. Ejemplo de uso del método select() y la interfaz Comparator . . . . .
83
A.7. Ejemplo de uso del método map() y la interfaz Mapping . . . . . . . . .
83
A.8. Ejemplo de uso del método relation() y la interfaz Relationship . .
84
Índice de tablas
5.1. Lı́neas de código de los problemas de ejemplo con y sin ParallelCollections 66
5.2. Tiempos en milisegundos de AirControl para 8 núcleos . . . . . . . . .
68
5.3. Tiempos en milisegundos de AirControl para 8, 16, 32 y 64 núcleos
sobre “c1” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
5.4. Tiempos en milisegundos de AirControl para 24 núcleos . . . . . . . .
69
5.5. Tiempos en milisegundos de ShortestPath1 para 8 núcleos . . . . . . .
71
5.6. Tiempos en milisegundos de ShortestPath1 para 24 núcleos . . . . . .
72
5.7. Tiempos en milisegundos de ShortestPath1 para 24, 32, 48 y 64 núcleos
sobre “c2” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
xv
73
Capı́tulo 1
Introducción
La Ley de Moore, formulada por el co-fundador de Intel, Gordon E. Moore, en
1965, predijo que el número de transistores que es posible integrar en un mismo circuito se duplicarı́a cada año[1]. Esta ley, que sigue vigente, ha permitido elevar el nivel
de integración de transistores en una misma oblea de silicio hasta alcanzar las actuales
tecnologı́as de 45 nm. Sin embargo, a más transistores integrados mayor es el calor a
disipar y por tanto, más complicado resulta aumentar la frecuencia de reloj de estos
circuitos. Esta situación ha limitado notablemente el desarrollo de los procesadores basados en un sólo núcleo.
Por esta razón la idea que se está imponiendo en los últimos años es integrar un
número creciente de núcleos en el mismo chip, dando lugar a lo que se ha dado en
llamar procesadores multinúcleo. A comienzos de la actual década, los fabricantes de
procesadores lanzaron sus primeros diseñ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 años, esta tecnologı́a ha ocupado todos los segmentos
de mercado, irrumpiendo en los equipos domé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 diseño de procesadores se ven limitados si los programas a ejecutar sobre los mismos no se aprovechan de la existencia de varios núcleos.
1
2
1. Introducción
En el peor de los casos, y siempre que el sistema operativo correspondiente lo soporte,
es posible correr sobre cada núcleo una aplicación diferente. Sin embargo, resulta deseable que aquellas aplicaciones con mayores necesidades computacionales (procesamiento
gráfico, cálculos matemáticos de gran envergadura, tratamiento de grandes conjuntos
de datos...) aprovechen la existencia de varios núcleos para realizar su trabajo más
rápidamente.
1.1.
Estado del arte
A continuación se realiza una breve presentación de las principales tecnologı́as utilizadas actualmente tanto en la organización de sistemas paralelos como en la implementación de código para dichos sistemas.
1.1.1.
Paradigmas de organización de sistemas paralelos
Dentro de los sistemas de procesamiento paralelo existen dos grandes paradigmas
de organizació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 común, de manera que las operaciones de lectura y escritura tienen exactamente
las mismas latencias. Como principales inconvenientes destacan los riesgos del acceso
simultáneo a memoria, ya que pueden aparecer problemas de concurrencia si dos procesadores acceden a una misma regió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 número de éstos resulta excesivo. Sin embargo cuenta con una importante ventaja:
resulta más fá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 única forma de compartir informació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, deberá enviar un mensaje solicitá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 más lento y la programación puede
complicarse demasiado[2].
1.1.2.
Programación multithreading
El requisito a cumplir por cualquier código paralelo es que éste aproveche los recursos proporcionados por los nuevos procesadores multinúcleo. En estos procesadores
normalmente cada núcleo tiene los primeros niveles de caché privados, compartiéndose
entre varios núcleos el resto de niveles de la caché y de la jerarquı́a de memoria. Para
conseguir el aprovechamiento deseado, el código debe poder ejecutarse en diferentes
threads o hilos de ejecución, de manera que cada nú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 ejecución y
éstos deben ser creados mediante llamadas a librerı́as especiales cuya implementación
depende del sistema operativo subyacente, siendo el ejemplo má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
programació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 programació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
diseño caracterı́sticas expresamente creadas para permitir a los programadores escri1
Acrónimo de “Portable Operating System Interface for UNIX”
4
1. Introducción
bir código paralelo. En posteriores capı́tulos se presentarán y explicarán las distintas
posibilidades que ofrece el lenguaje Java en lo que a programación multithreading respecta. Aunque teniendo un especial cuidado a la hora de gestionar las tareas no deberı́a resultar problemático el uso de las funcionalidades nativas del lenguaje para la
implementación del paralelismo en la colección, se ha preferido utilizar algunas de las
herramientas avanzadas incluidas en el paquete java.util.concurrent, puesto que
correctamente utilizadas dotan al código de una especial robustez y seguridad ante
eventuales problemas de concurrencia.
1.1.3.
Paralelización de tareas vs. paralelización de datos
Existen diferentes lenguajes, extensiones de lenguajes y librerı́as que intentan facilitar la programación para sistemas multinúcleo. Existen dos vertientes principales:
el paralelismo de datos, en la que se aplica una misma operación de forma simultánea
sobre conjuntos de datos diferentes; y el paralelismo de tareas, donde cada tarea se
divide en varias subtareas que son ejecutadas simultáneamente en diferentes núcleos[6].
La clave de la paralelización de tareas reside en la división del trabajo en diferentes
tareas que son asignadas directamente a hilos de ejecución “fı́sicos”, sobre cuya planificació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 definició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 número de éstos sea mayor que el de tareas a ejecutar, es posible aprovechar los
recursos ociosos subdividiendo alguna de dichas tareas.
Por otra parte, la paralelización a nivel de datos se basa en la creación de tareas
que realizan una misma operación sobre diferentes fragmentos de un conjunto de datos.
Realmente este enfoque es una particularización del anterior, ya que nada impide a los
sistemas basados en paralelización de tareas el aplicar una misma operació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, acrónimo de Hierarchically Tiled Arrays[8], cuyo objetivo es el diseño
de tipos de datos que faciliten la creació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 partición (partition lines). Cada sección puede ser un array al
uso u otra HTA, dotando al tipo de dato de un marcado carácter recursivo. Las ideas
principales de esta expresión del paralelismo son mejorar la localidad de los accesos y
facilitar al programador la explotación del paralelismo de forma transparente[6].
1.2.
Objetivos del proyecto
Los procesadores multinúcleo se han convertido en la arquitectura dominante en
los computadores modernos, mientras que el lenguaje de programación Java es uno de
los más extendidos actualmente gracias a caracterı́sticas como ser orientado a objetos,
multiplataforma y eminentemente orientado a Internet gracias a sus capacidades para la
implementación de aplicaciones cliente-servidor. Partiendo de estas premisas el presente
proyecto realiza las siguientes aportaciones:
Implementación de una librerı́a de colecciones genéricas sobre cuyos datos se
puedan realizar diferentes operaciones como aplicaciones de funciones, mapeos,
selecciones u obtenció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 multinúcleo y la computación paralela.
Evaluación de códigos de prueba implementados con la nueva librerı́a centrándose
en dos aspectos:
• Programabilidad: comparación respecto a colecciones nativas de Java a las
que se dota de funcionalidades paralelas.
• Rendimiento: comparación respecto a versiones secuenciales de las operaciones realizadas, ası́ como análisis de la escalabilidad del código.
2
Palabra inglesa que literalmente significa baldosas o tejas
6
1. Introducció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 núcleo de la librerı́a implementando la
estructura de datos a utilizar y sus operaciones básicas, para despué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 prácticamente
completo, ya que para cada una de ellas se pasó por las etapas de análisis, diseño,
implementació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 sección introduce algunos conceptos básicos acerca de la computación paralela y, sobre todo, la programación multihilo desde un punto de vista general,
ası́ como detalles de su implementación en Java.
Capı́tulo 3: Programación genérica en Java
En esta sección se explican brevemente los conceptos básicos relacionados con la
programación genérica, y más en concreto sobre su implementación en el lenguaje
de programación Java.
Capı́tulo 4: Paquete ParallelCollections
Este capı́tulo describe la principal aportación del presente proyecto, el paquete
de colecciones paralelas ParallelCollections, comentándose las diferentes fases
de su ciclo de desarrollo.
Capı́tulo 5: Evaluación
Capı́tulo donde se explican las pruebas realizadas una vez finalizada la implemen-
1.4. Estructura de la presente memoria
7
tación de la librerı́a, las cuales pueden dividirse en dos grandes grupos: pruebas de
rendimiento y estudios de programabilidad, ası́ como los códigos utilizados para
ello.
Capı́tulo 6: Conclusiones
Finalmente se realiza un pequeño resumen del trabajo realizado y se plantean
diferentes lı́neas de trabajo futuro de cara a la ampliación y mejora de la librerı́a.
Adicionalmente, en el apéndice A se incluye un manual de usuario donde el programador puede consultar cómo realizar algunas operaciones bá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 implementación de código paralelo, centrándose en el mecanismo natural que ofrece
Java para ello, el uso de múltiples threads o hilos de ejecución. Antes de entrar en detalles acerca de qué herramientas son necesarias y cómo se utilizan en la programación
de código paralelo, se realiza una breve introducción al lenguaje de programación Java.
El lenguaje de programació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 más simple y dispone de menos funcionalidades a bajo nivel, además de estar más
limitadas[9].
Las principales caracterı́sticas de Java son su orientación a objetos, no derivada de
ningún otro lenguaje; ser distribuido, permitiendo la creación de aplicaciones orientadas
a su uso en red; y ser a la vez compilado e interpretado, compilado porque a partir del
código Java se generan ficheros bytecode de clase e interpretado porque dichos ficheros
pueden ser ejecutados en cualquier máquina virtual de Java, independientemente de la
arquitectura del sistema.
9
10
2. Paralelismo en Java
2.1.
Hilos de ejecución
Prácticamente todos los sistemas operativos modernos se basan en el concepto de
proceso como unidad básica independiente de trabajo. Sin embargo, gracias al uso de
threads o hilos de ejecución es posible encapsular múltiples actividades dentro de un
mismo proceso. Por este y otros motivos que se explicarán a continuación, a menudo
los threads son conocidos como procesos ligeros.
Al igual que los procesos, los threads son caminos concurrentes e independientes de
ejecució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 está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 simultánea y ası́ncrona entre ellos. Luego se verá que esto no siempre es
cierto, siendo la correcta sincronización de diferentes hilos de ejecución uno de los
grandes problemas que el programador se encuentra a la hora de implementar código
paralelo. Mú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 ésto facilita el
intercambio de informació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 ejecución[10][11][12].
2.2.
Threading en Java
Si bien a lo largo de los años ha habido diferentes lenguajes de programación que,
de una forma u otra, han ido implementando capacidades multihilo, Java fue el primer
lenguaje de propósito general en el que estas funcionalidades se incluyeron como parte
del lenguaje.
2.3. Implementació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 versión 1.5 del JDK1 proporcionan toda una serie de clases y
mecanismos complejos para ser utilizados en la implementación de aplicaciones concurrentes: nuevas utilidades de sincronización a bajo nivel, mejoras en la seguridad y
gestión de threads, clases concurrentes de alto rendimiento (thread pools, colecciones
concurrentes, semáforos, latches, barreras...), etc[13][14][15].
Ambas implementaciones, en conjunto, convierten al lenguaje Java en una potente
herramienta de programación concurrente que, entre otras cosas, permite crear interfaces gráficas más eficientes, separar más explı́citamente si cabe las operaciones de E/S
del resto de la lógica de los programas y, lo que es más importante en el ámbito de este
proyecto, exprimir las potencialidades de los sistemas multiprocesador y/o multinúcleo.
2.3.
Implementación nativa
Una sola clase, la clase Thread, resulta suficiente para soportar la implementación
básica del threading de Java, proporcionando todas las funcionalidades necesarias para
realizar trabajos más o menos sencillos con diferentes hilos de ejecución.
Asimismo, y para evitar posibles ambigüedades de aquı́ en adelante, cabe diferenciar
entre dos entidades estrechamente relacionadas que suelen recibir el nombre de hilo o
thread. Por una parte está el hilo en ejecución, que es el que realiza el trabajo y suele
ser creado por el sistema operativo; y su representación como objeto de clase Thread,
que es utilizado por la JVM para control del primero. Tambié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 creación hasta su finalizació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
Creación
Existen dos formas diferentes de crear hilos adicionales al principal: mediante herencia de la clase Thread o implementación de la interfaz Runnable, los cuales se resumen
de la siguiente manera:
Herencia de la clase Thread: Es el método más sencillo, basándose simplemente en hacer que la clase cuyo código se desea ejecutar en un hilo independiente
extienda a Thread y sobrecargue su método run(), quien verdaderamente implementa la operació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 múltiple.
Implementación de la interfaz Runnable: Esta opción obliga a que la clase
a ejecutar en otro hilo implemente la interfaz Runnable y su mé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 cuestión. La gran ventaja
del uso de la interfaz Runnable en lugar de la herencia es que no se impide que
la clase en cuestión extienda a otra de ser necesario.
A continuación se describe cómo poner en ejecución uno de estos hilos.
2.3. Implementación nativa
13
Ejecución y parada
Si bien el trabajo que se realiza al ordenar la ejecución de un hilo es el mismo en
ambos casos2 , la forma en que éste se realiza difiere ligeramente dependiendo de cuál
de los dos métodos de creació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, bastará con
llamar al mé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
parámetro al constructor dicha interfaz o la clase que la implemente, para posteriormente llamar al método start() de dicha instancia. El mé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, lanzándose una excepción de la clase IllegalThreadStateException en caso de
que se intente llamara a start() de nuevo.
La llamada a start() se corresponde con la transició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.
Además de por su detención explı́cita con stop(), un hilo finalizará su ejecución si
su mé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.
Suspensión y reinicio
Como ya se ha explicado en el apartado anterior, una vez detenido un hilo éste no
es recuperable. Sin embargo, no se puede dejar un thread continuamente en ejecució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 métodos
2
Se llama al método run()
14
2. Paralelismo en Java
sleep()/interrupt(), yield() y suspend()/resume(). Estos mé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
ejecución del thread durante un determinado perı́odo de tiempo pasado como parámetro.
El hilo que haya reemplazado al “durmiente” puede despertar a este último mediante
el método interrupt(), que a su vez lanzará una InterruptedException que advertirá al mismo que ha sido reactivado por una interrupción y no por haber agotado el
tiempo de espera. Existe un mé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 más adecuada de
trabajar si lo que se desea implementar es la respuesta a un evento concreto, algo muy
común en el diseño de interfaces gráficas. Para ello deben utilizarse suspend() y su
complementario resume(), que suspenden de forma temporal y reinician la ejecución
del hilo.
2.3.2.
Planificación y prioridades
Una vez estudiadas las herramientas que permiten controlar la ejecución de los diferentes hilos contenidos en un determinado proceso, resulta conveniente analizar có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 continuación.
Dos son los datos que el planificador revisa para cada thread, su prioridad y su flag
daemon, partiendo de la regla básica de que si solamente se encuentran listos para ejecución hilos con el flag daemon activo la JVM debe cerrarse. Respecto a la prioridad,
el comportamiento es el esperado, ejecutá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. Implementación nativa
15
normal y valor por defecto.
A aquellos hilos que además de tener el flag daemon activo tengan una prioridad
relativamente baja se les conoce como daemon threads, y suelen emplearse para proporcionar servicios básicos a diferentes programas (el ejemplo más representativo es el
recolector de basura o garbage collector de la JVM).
Asimismo, dependiendo del sistema operativo subyacente la planificación de threads
se realizará o no de forma apropiativa. Cuando la planificación es apropiativa, se asigna
a cada hilo un “cuanto de tiempo”, de manera que una vez agotado el mismo el thread
queda en suspensión hasta que le vuelva a ser concedida la CPU y sea reiniciado con
resume(). Si la planificación es no apropiativa, el hilo en ejecució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 método join().
2.3.3.
Sincronización
Como ya se ha comentado en secciones anteriores, uno de los puntos clave a la
hora de programar correctamente código paralelo reside en la correcta sincronización
de las operaciones a realizar por los diferentes threads. Además, para que resulte útil
contar con varios hilos dentro de un mismo programa debe existir alguna forma de
comunicación o compartición de datos entre los mismos.
Formas de comunicación
La forma más sencilla de conseguir esto es mediante la compartició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 realización de accesos ilegales o peligrosos a aquellas variables o regiones de código
16
2. Paralelismo en Java
a las que acompañen:
synchronized: Asegura que solamente un thread ejecute de forma simultánea
una sección protegida de código que se ha de ejecutar atómicamente (es decir,
funciona como un sistema de exclusión mutua o mutex), ası́ como que los cambios realizados por un hilo sean visibles para los demás. Si no se utiliza, es muy
probable que la planificación de hilos haga que los datos a tratar queden en un
estado inconsistente.
volatile: Su uso es más sencillo que el de synchronized, pero solamente es
válido para controlar el acceso a instancias concretas de variables primitivas5 , no
clases. Básicamente, cuando una variable es declarada volatile, cualquier cambio en ella es escrito directamente en memoria principal, sorteando la escritura
en caché. 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 código debe
sincronizarse de forma que desde el punto de vista del resto de threads la operación
se realice de forma ató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 sincronización explı́cita en el código, ya que es la propia JVM
la que se encarga de ella internamente. Dentro de estas situaciones se incluyen: datos
inicializados estáticamente utilizando el modificador static, variables finales, etc.
Fallos de sincronización
El problema más representativo derivado de un error o falta de sincronizació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 operación. Un ejemplo bá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 situación es la referida por Dijkstra6
en su conocido “problema de la cena de los filósofos”.
Existen diversos mecanismos para prevenir la aparición de interbloqueos, pero ocurre que la mayorı́a de dichas soluciones son difı́cilmente aplicables en la prá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 solución más sencilla es establecer
una condició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 versión 5.0 fue el paquete java.util.concurrent, compuesto por toda una serie de clases
útiles para la creación de programas concurrentes más o menos complejos. Además
del paquete propiamente dicho se añ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 pequeños frameworks estándar extensibles por el programador, ası́ como algunas clases que proporcionan funcionalidades útiles que de otra manera resultarı́an tediosas y complicadas de implementar.
java.util.concurrent.atomic: Pequeño conjunto de herramientas que da soporte a operaciones concurrentes seguras y libres de bloqueos. Básicamente son
clases que amplı́an y mejoran el concepto de variable volatile proporcionado
por la implementación nativa.
6
Edsger Wybe Dijkstra (1930-2002), cientı́fico de la computación de origen holandés.
18
2. Paralelismo en Java
java.util.concurrent.locks: Framework formado por interfaces y clases que
flexibilizan las condiciones de bloqueo y sincronización propias de la implementación original, a expensas de complicar ligeramente la sintaxis del código.
2.4.1.
Colecciones seguras
Desde la versió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 través de las interfaces List, Set y Map. Como se comenta en el apartado
anterior, el paquete java.util.concurrent añade un conjunto de nuevas colecciones
concurrentes seguras cuyo propósito es proporcionar al programador una alternativa
segura a las colecciones básicas y con mejor rendimiento y escalabilidad.
La problemática de los iteradores
Sin duda una de las grandes comodidades que proporcionan las colecciones bá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 más aún
al crear y recorrer el iterador de forma completamente automática).
El problema aparece cuando se desea utilizar estos iteradores en programas concurrentes, ya que en el momento de su creación asumen que la colección no va a
ser modificada mientras no se termine de recorrer, lanzando una excepció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
ningún elemento dos veces en una misma iteración.
7
Iteradores débilmente consistentes, en inglés
2.4. Paquete java.util.concurrent
19
Descripción y funcionamiento de las colecciones
El paquete java.util.concurrent incorpora las siguientes colecciones seguras como equivalentes a las correspondientes colecciones bá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 está trabajando con colecciones básicas, de modo que los iteradores que las recorran
serán fail-fast. Para evitar este problema existe CopyOnWriteArrayList, que lo
soluciona creando copias del array subyacente cada vez que éste es modificado
por inserciones o borrados, de manera que el iterador siempre mantiene su copia
intacta mientras recorre la colección.
CopyOnWriteArraySet: De caracterı́sticas similares a la anterior, esta colección
resulta útil si se desea trabajar con la semántica propia de un Set.
ConcurrentHashMap: Aunque es posible implementar un Map seguro mediante
HashTable o encapsulando un HashMap con Collections.synchronized(), esta
solución no resulta suficiente para obtener una colección totalmente concurrente,
ya que además de la cuestión del iterador fail-fast análoga a los casos anteriores, aparecen problemas de escalabilidad y rendimiento al forzar que un único
hilo pueda acceder a la misma. Para ello se incorpora ConcurrentHashMap, que
permite lecturas y escrituras concurrentes en casi todas las ocasiones, además de
proporcionar un iterador libre de ConcurrentModificationExceptions.
Ademá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 comú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
incluyó la interfaz Queue, mucho más sencilla y eficiente que List al permitir
únicamente insertar y eliminar objetos. La implementación concurrente de este
tipo de colección corresponde a la clase ConcurrentLinkedQueue, una cola FIFO
rá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 añadir otro
a una llena, la operación falla. Sin embargo, a veces es mejor hacer que el hilo que realiza dicha operación se bloquee en lugar de fallar y tener que recuperarse de dicho fallo, resultando en una forma mucho más elegante de gestionar los recursos a disposición de una cola. De entre las diversas clases de colección de java.util.concurrent que implementan esta interfaz cabe destacar
SynchronousQueue, que no es propiamente una cola, pero facilita la sincronización entre hilos cooperativos.
2.4.2.
Planificación avanzada
Para ilustrar las diferencias entre la planificación básica que ofrece la implementación nativa de threading que incorpora Java y la planificació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 má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 aplicación falle y
Java lance un OutOfMemoryError.
Planificación con thread pools
Crear un nuevo hilo para cada petición no es una mala práctica en sı́ misma, es
más, es la solución natural al problema de gestionar varias peticiones. La cuestión reside en cómo limitar cuá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 clásico utilizado en este tipo de situaciones se compone de una cola
de tareas y una colección de hilos que las atiendan, de manera que dicha colección de
threads o thread pool va desencolando tareas a medida que se completan las anteriores.
Ademá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 creació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
gestión de aquellas tareas implementadas mediante interfaces Runnable. El núcleo de
Executor lo constituye la interfaz homónima, la cual solamente implementa un método, execute(), y recibe como pará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 ejecució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 ejecución correspondiente (limitación de colas, tamaño del pool, prioridades, etc.).
Muchas de las clases contenidas en java.util.concurrent que implementan Executor
lo hacen a través de la subinterfaz ExecutorService, que ademá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 través de ExecutorService), cada una con
22
2. Paralelismo en Java
su propia polı́tica de ejecución. Estas polı́ticas no son más que la forma de establecer
cuándo y en qué hilo correrá determinada tarea, de qué recursos de sistema podrá disponer y qué 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 métodos factorı́a estáticos contenidos en la clase
Executors:
Executors.newCachedThreadPool(): Crea un pool de tamaño ilimitado que reutiliza aquellos hilos previamente creados cuando se encuentran disponibles. Si
no hay ninguno, crea uno nuevo y lo añade al pool; por otra parte, si en un plazo
de 60 segundos un thread no es utilizado, é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 ejecución estrictamente
secuencial de una cola ilimitada de tareas.
En concreto, los dos primeros mé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 versión de dichos mé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 métodos beforeExecute() y afterExecute(), con los que es posible
añadir tareas de instrumentación, registro, temporización, etc.
2.4. Paquete java.util.concurrent
23
Por último, es importante reseñar que si bien la principal motivación del framework Executor es desacoplar el lanzamiento de tareas de la polı́tica de ejecución de las
mismas, existen determinados casos en los que la forma de programar el código asume
implı́citamente la polı́tica a seguir, de modo que la implementació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 tamaño del pool es insuficiente para admitir un nuevo hilo por cuya finalización esté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 combinación del framework Executor y los diferentes tipos de
thread pools, java.util.concurrent ofrece otras funcionalidades interesantes para la
planificación avanzada de tareas con las interfaces Future y CompletionService:
Future: Esta interfaz permite representar tareas que pueden haberse completado,
estar en ejecució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 devolución. La clase que implementa Future, FutureTask,
tambié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 ejecución del aspecto de
una cola, de forma que el procesado de las tareas puede separarse de su ejecución.
CompletionService incluye, entre otros métodos, submit() para enviar tareas y
la pareja take()/poll() para consultar cuál es la siguiente tarea completada.
2.4.3.
Sincronización avanzada
Otro grupo de clases interesantes para la programación multihilo ofrecidas por el
paquete java.util.concurrent son aquellas destinadas a la sincronización de threads,
24
2. Paralelismo en Java
es decir, a la coordinación y control del flujo de ejecución de uno o varios hilos.
Semáforos
La clase de java.util.concurrent que implementa un semáforo clásico de Dijkstra, es la clase Semaphore. Funciona como se espera que lo haga un semá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 ejecución.
En este caso, cuando un thread llama al mé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 reseñar que el
semáforo no es consciente de qué hilos poseen los “permisos”, siendo la aplicación en
sı́ la que debe encargarse de devolverlos al semáforo o cederlos a otro thread convenientemente.
Existe un caso especial de semáforo muy utilizado en programación concurrente, se
trata del mutex. Consiste en un semáforo de exclusión mutua9 , es decir, un semáforo
que concede a un único hilo el permiso para acceder a determinado recurso. Como
ya se verá, su comportamiento es muy similar al de los locks, pero con la importante
ventaja sobre éstos de que permite que un hilo diferente al que accede al recurso libere
el semáforo, resultando muy útil en situaciones donde es necesario recuperarse de un
deadlock.
CyclicBarrier
La clase CyclicBarrier implementa una ayuda a la sincronización consistente en
un “punto de encuentro” que un conjunto de threads debe alcanzar antes de continuar
la ejecució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 ésta
se reinicia.
9
De ahı́ el nombre “mutex”: Mutual exclusion
2.4. Paquete java.util.concurrent
25
Se instancia pasando como parámetro al constructor una variable entera que determina el número de hilos del grupo a controlar, los cuales deben notificar su llegada
mediante CyclicBarrier.await(), método que en su primera llamada bloquea la ejecució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 algún hilo no llega, se considere
rota la barrera lanzándose una BrokenBarrierException.
CountdownLatch
La clase CountdownLatch tiene un comportamiento similar a CyclicBarrier, en
tanto en cuanto ambas se utilizan como herramientas de coordinación de un grupo de
hilos sobre el que se ha repartido la computació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 actúa como una simple barrera que no se levanta hasta que todos los hilos la alcanzan, CountdownLatch únicamente exige a los hilos que
controla que notifiquen su llegada decrementando su contador interno, sin establecer
ningún tipo de bloqueo sobre la ejecución del programa. En este caso, la capacidad de
bloqueo la posee el método CountdownLatch.await(), el cual puede ser llamado por
cualquier hilo y tiene como función esperar a que el contador del latch alcance valor 0.
Como se puede intuir, los CountdownLatch son útiles para la implementación de
soluciones a problemas descomponibles en partes, y es precisamente por este motivo
por el que son el principal sistema de sincronización empleado en el presente proyecto.
Un ejemplo de ello serı́a la selección de elementos de un conjunto que cumplan una
determinada condició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 demás, se explican de forma detallada en los apartados dedicados al diseño e
implementació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 añadida de que ambos threads pueden intercambiar10
información cuando alcanzan la barrera. Un caso de uso muy tı́pico es la gestió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 través de un socket y otro lector que se
encarga de su interpretación, de manera que cuando ambos alcanzan la barrera, se
intercambian entre sı́.
2.4.4.
Gestión de threads a bajo nivel
Tal y como se comenta en el apartado sobre la implementación de threading nativa
de Java, el lenguaje incorpora la sincronización de hilos a través de la palabra clave
synchronized, mediante la cual se pueden definir secciones crı́ticas de código. Si bien
el uso de dicha funcionalidad nativa no presenta problema alguno en los casos má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 travé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 semántica de los bloqueos nativos pero añadiendo nuevas capacidades. La
más destacable es una importante mejora en la escalabilidad del có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 único gran inconveniente, ya que existe la posibilidad de olvidarse de liberar el bloqueo, algo imposible con
synchronized al realizarlo la JVM de forma automática.
10
To exchange: intercambiar
2.4. Paquete java.util.concurrent
27
Condition
De la misma manera que la interfaz Lock es la generalización de la sincronización
nativa, la interfaz Condition generaliza la funcionalidad implementada por los métodos wait(), notify() y notifyAll() de la clase Object a través de los equivalentes
await(), signal() y signalAll(), con la ventaja añadida de que pueden crearse
tantas variables de condición como instancias de Lock se tengan.
ReadWriteLock
Otra situación bastante común en programación concurrente es el llamado “problema de los lectores-escritores”, ejemplificació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 más eficiente utilizar un sistema de bloqueo que,
pese a ser ligeramente má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 través de la interfaz ReadWriteLock y su implementación
en la clase ReentrantReadWriteLock.
Variables ató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 Máquina Virtual
de Java en lo que a operaciones de lectura-modificación-escritura se refiere.
Prácticamente todos los bloqueos utilizados en las clases del paquete se implementan
mediante ReentrantLock, que a su vez utiliza las clases Atomic. La utilización de estas
“clases envoltorio” permiten aprovechar la inclusión en la mayorı́a de los procesadores
11
Clases envoltorio: añ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
más cómodo escribir código concurrente de alto rendimiento, libre de esperas y bloqueos.
Capı́tulo 3
Programación genérica en Java
Una de las grandes novedades incluidas por la comunidad de desarrollo de Java
en la versión 1.5 del Java Development Kit fue la posibilidad de programar de forma
gené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 aún mayor, sobre todo
en lo que al tratamiento de colecciones de datos se refiere.
Es precisamente en este último aspecto en el que este proyecto se centra, poniéndolo
en conjunción con las funcionalidades paralelas del lenguaje para obtener una librerı́a
de colecciones genéricas capaces de procesar información de forma paralela. Una vez
presentados los distintos métodos existentes para la extracción del paralelismo en Java,
a continuación se explica de forma más o menos detallada qué es la programación
genérica y cómo la utiliza dicho lenguaje.
3.1.
Programación genérica
La programación genérica es un tipo de programación que se centra en los algoritmos antes que en los datos manipulados, consiguiendo ası́ la generalización de las
funciones utilizadas y conviertiéndolas en código ampliamente reutilizable. Para alcanzar estos objetivos se busca parametrizar lo máximo posible el desarrollo del programa,
evitando detalles concretos. La biblioteca de funciones conseguida con esta manera de
29
30
3. Programación genérica en Java
programar permite que la implementación de esos algoritmos pueda servir para más
programas que otras más concretas; y también que aplicando pocos cambios sobre las
mismas, éstas realicen acciones diferentes.
Los programas genéricos o politı́picos son programas parametrizados en la estructura de los datos que manipulan. Este mecanismo de parametrización permite escribir
programas que pueden trabajar sobre una importante clase de diferentes estructuras de
datos, liberando ası́ al programador de escribir código adicional de similar funcionalidad cada vez que se quiera manipular una estructura de datos diferente. Esto simplifica
enormemente el trabajo de construcción y mantenimiento de los sistemas de software ya
que los programas se pueden adaptar automáticamente a cambios en la representación
de los datos, reduciendo de esta manera el impacto de los cambios.
3.2.
Implementación nativa
Como ya se ha comentado en la introducción del presente capı́tulo, una de las
principales extensiones añadidas a Java en su JDK 1.5 fue la llamada programación
genérica o genericidad, cuyo objetivo básico es la abstracción de los tipos de datos. Si
bien esto supone una mayor comodidad a la hora de escribir código para infinidad de
problemas diferentes, no hay duda de que donde más se aprovechan todas sus ventajas
Figura 3.1: Jerarquı́a del framework de colecciones de Java
3.2. Implementació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 utilizarán algunas de estas clases para la
ejemplificación de su uso.
3.2.1.
Introducción
Antes de la incorporación de la genericidad al lenguaje, el tratamiento de los datos
almacenados en estructuras de la jerarquı́a Collections requerı́a de toda la atención
del programador al no asegurar el compilador el tipo de dato de los objetos añadidos o extraı́dos de las mismas. Los mé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 ejecución si no realiza correctamente esta asignació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 genéricas de Java
El fragmento de código de la figura 3.2 ejemplifica la situación antes comentada.
Las dos primeras lı́neas hacen lo esperado, se define una nueva lista enlazada a la que
se añade un entero con valor 0. Los problemas aparecen en las dos siguientes, ya que
ambas son legales a efectos de compilación, pero la última provocará un error en tiempo
32
3. Programación genérica en Java
de ejecución al intentar convertir un objeto que realmente es de clase Integer en un
String.
El código de la figura 3.3 muestra có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 código. Con esta modificación, tanto add() como
iterator() trabajan únicamente1 con objetos Integer, de modo que la última lı́nea
será ilegal y generará un error en tiempo de compilación.
En resumen, la genericidad dota de mayor robustez y legibilidad al código al ser
el propio compilador el que asegura la corrección de tipos del programa allá donde se
empleen las clases genéricas.
3.2.2.
Clases gené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 definición genérica de las interfaces List e Iterator
Las clases genéricas se definen de forma similar a las clases convencionales, con la
salvedad de los llamados pará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 definición de ambas clases compárense
los extractos de las interfaces List e Iterator incluidos en la figura 3.4.
1
Más adelante se verá que esta limitación no es tan estricta.
3.2. Implementación nativa
33
La E entre < y > representa el parámetro formal de tipo, cuyas ocurrencias en el
código son sustituidas por el argumento real de tipo a la hora de invocar a las clases
con un tipo gené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 versión de List en la que todas las apariciones de E son reemplazadas por Integer.
El motivo de esto es que las declaraciones genéricas solamente se compilan una vez
y son almacenadas en un único fichero .class, es decir, no existen varias clases Java
diferentes según el tipo que se pase a la “plantilla”2 genérica, sino que estos parámetros formales de tipo funcionan de manera similar a los argumentos que se pasan a los
métodos convencionales.
Otra de las caracterı́sticas de las clases genéricas que pueden llegar a desafiar la intuición del programador está relacionada con la herencia, ya que partiendo, por ejemplo,
de una clase Empleado que herede de Persona y una clase genérica G, no se cumple que
G<Empleado> sea subclase de G<Persona>. De todas maneras, en el siguiente apartado se introducen la gestión de jerarquı́as de clases genéricas mediante las wildcards.
3.2.3.
Wildcards y métodos genéricos
Wildcard types
Antes de la introducción de la genericidad, la forma de representar un objeto de
clase desconocida era declarándolo como de clase Object, raı́z del á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 código gené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 modificación, allı́ donde aparezca una declaración genérica del estilo G<?>,
2
Precisamente por ese motivo no es una plantilla al uso, como las incluidas en lenguajes como C#.
34
3. Programación genérica en Java
podrá 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 añadir elementos directamente, ya que deberı́an ser de
un subtipo de ?, algo que por definición no existe (con la excepció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 ú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 tratarán objetos de clase G o de una clase
situada por encima en la jerarquı́a.
Métodos genéricos
Resulta evidente que la definición de clases genéricas debe permitir la definición
de métodos que aprovechen la posibilidad de trabajar con objetos de clases diferentes
según sea necesario, es decir, clases genéricas que permitan la implementación de métodos genéricos.
Un método genérico no deja de ser un método que puede recibir uno o varios parámetros de tipo, con la ventaja añadida de que no es necesario establecer argumentos
reales para dichos parámetros. Es el propio compilador el que se encarga de escogerlos
3.2. Implementación nativa
35
basándose en los tipos de datos de los argumentos que se pasan al método, quedándose
además con el argumento de tipo más especı́fico que resulte correcto.
Wildcard types vs. métodos gené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: Definición genérica de Collection con wildcards y métodos genéricos
Una vez presentadas ambas posibilidades, es lógico que surja la duda acerca de cuál
ellas utilizar según en qué situaciones. Considérense a modo de ejemplo las dos declaraciones de la interfaz Collection incluidas en la figura 3.5, escritas utilizando wildcards
y métodos genéricos respectivamente.
En este caso, el tipo de retorno de los métodos no depende del parámetro de tipo de
la clase ni de cualquier otro argumento del método, de modo que el argumento de tipo
sirve únicamente como soporte del polimorfismo, es decir, permite utilizar varios tipos
de argumentos reales para poder llamar al método desde lugares diferentes. En estas
situaciones en que lo se busca es trabajar con un subtipado má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 método genérico copy() de Collection
36
3. Programación genérica en Java
De todas maneras, es totalmente legal y válido emplear wildcards y métodos genéri-
cos conjuntamente. Ejemplo de ello es el método copy() de Collections, cuya firma
se incluye en la figura 3.6.
3.3.
3.3.1.
Genericidad avanzada
Uso combinado de código gené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
últimas actualizaciones, ya existen millones de lı́neas de código escritas empleando versiones anteriores, las cuales además no pueden ser convertidas de un dı́a para otro.
Tipos raw
Para permitir la compatibilidad de código antiguo respecto de código nuevo escrito
empleando programación genérica, se introdujeron los llamados tipos raw, ya comentados someramente en apartados anteriores y que, básicamente, consisten en el uso de
clases o interfaces que admiten argumentos de tipo, como podrı́a ser Collection, sin
dichos parámetros.
En aquellas ocasiones en que se prescinde de la programación genérica, sin embargo,
no funcionan como clases sin pará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 integración de código programado según las diferentes versiones
a cambio de flexibilizar la correción de tipos que el compilador proporcionarı́a de emplearse ú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 correcció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 correcció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 está 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 éstos se utilicen son reemplazados por el lı́mite superior de la variable (normalmente Object), además de insertarse los casts apropiados
allı́ donde el tipado no resulte correcto.
Es precisamente a causa de borrar toda la información referente a la programación
gené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 programación gené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 código y
el comportamiento de los programas puede dar lugar a pensar. En este apartado se
explican algunos de estos pequeños pero importantes detalles.
Compilación única
Si se compara la salida obtenida mediante el método getClass() de Object para dos
colecciones genéricas con distinto parámetro de tipo (como un ArrayList<Integer>
y un ArrayList<String>, por ejemplo), puede pensarse que el resultado será falso,
ya que dichas colecciones contienen elementos de clases diferentes (Integer y String).
3
To erase: borrar
38
3. Programación genérica en Java
Sin embargo, y a causa de que las clases genéricas solamente se compilan una vez y
se guardan en un único fichero .class, la comparación devolverá true, ya que ambas
colecciones son de la misma clase ArrayList.
Arrays gené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 razón de esta importante restricción reside en que los arrays son estructuras cuyo
tipo y tamaño se establece en tiempo de compilación, momento en que se desconoce el
argumento real de tipo que se utilizará durante la ejecució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 procederá a detallar el ciclo de trabajo seguido
(análisis, diseño e implementación) para cada uno de los incrementos que constituyen
la librerı́a, desde las primeras aproximaciones hasta la versión final.
En primer lugar se introduce el problema que se pretende resolver con la implementació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: estructuración de los datos, gestión del paralelismo,
implementación de las operaciones e interacción con las colecciones de la librerı́a.
4.1.
Problema objetivo
Antes de comenzar la explicació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 genéricas que, mediante la
implementación paralela de diversas operaciones estándar, faciliten la programación de
sistemas multinúcleo.
39
40
4. Paquete ParallelCollections
4.1.1.
Operaciones a implementar
Las operaciones paralelas básicas que la librerı́a de colecciones debe soportar son
las siguientes:
Aplicación
Sea un conjunto de datos de tipo T y una función f: T → T que realiza alguna
modificación sobre elementos de dicho tipo, la operación de aplicación se define como
el resultado de aplicar dicha función f sobre todos los elementos del conjunto.
Reducción
Sea un conjunto de datos de tipo T y una función de combinación r: (T, T ) → T ,
se define la operación de reducción como el resultado de combinar todos los elementos
del conjunto para obtener un único valor de retorno, también de tipo T.
Selección
Sea un conjunto de datos de tipo T y una función booleana f: T → true/f alse, se
define la operación de selección como la aplicación de dicha función booleana a todos
los elementos del conjunto, generando un subconjunto con todos aquellos elementos
para los que el valor devuelto por la función haya resultado true.
Mapeo
Sea un conjunto de datos de tipo T y una función f: T → S que realiza una operación
cualquiera sobre elementos de tipo T devolviendo nuevos elementos, bien del mismo tipo
o de otro diferente S, la operación de mapeo se define como el resultado de aplicar dicha
funció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. Implementació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.
Relación entre conjuntos
La relación entre dos conjuntos consiste en una particularización del producto cartesiano de los mismos, puesto que el resultado de esta operación es un conjunto de pares
a cuyos elementos se exige que cumplan una determinada condició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
relación R : A → A, se define:
Reflexividad: R reflexiva ⇐⇒ ∀x ∈ A, (x, x) ∈ R.
Simetrı́a: R simétrica ⇐⇒ ∀x, y ∈ A, (x, y) ∈ R ⇔ (y, x) ∈ R.
Antisimetrı́a: R antisimétrica ⇐⇒ ∀x, y ∈ A, (x, y) ∈ R → (y, x) ∈
/ R.
4.2.
Implementación
El paquete ParallelCollections proporciona dos clases de colección diferentes,
ParallelSet<T> y ParallelList<T>, ambas basadas en la semántica de la interfaz
Set<T> y cuyo estudio puede dividirse en tres partes: estructura interna de datos,
gestión del paralelismo e implementación de las operaciones paralelas.
4.2.1.
Estructura de datos
Los datos se distribuyen en el conjunto paralelo como una colección de subcolecciones. El principal motivo de esta división ha sido el poder abrir la posibilidad de
que distintos núcleos trabajen simultáneamente sobre distintas partes del conjunto de
datos, algo que se consigue utilizando esta organización. La eliminación del reparto
explı́cito de los datos entre los distintos hilos de ejecución facilita la implementación
de las diferentes operaciones paralelas, ya que no es necesario utilizar parámetros para
42
4. Paquete ParallelCollections
determinar los lı́mites de los subconjuntos correspondientes a cada thread.
La implementación de esta idea se basa en la combinació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 dinámica, obteniendo ası́ un acceso rápido
y unı́voco a cada una de las partes del conjunto paralelo. Por defecto, el número de
subconjuntos en que se divide la colección coincide con el número de núcleos disponibles del procesador1 , si bien este parámetro puede ser modificado en el momento de la
instanciación de la clase. Además, si las necesidades del problema o las caracterı́sticas
del sistema donde se ejecuta el programa cambian, es posible modificar el número de
subconjuntos llamando al método disponible a tal efecto.
ParallelList y la problemática del código hash
En la clase ParallelSet2 , la operación de inserción distribuye los nuevos elementos
entre los distintos subconjuntos HashSet de acuerdo al resultado de calcular el módulo
entre su código hash y el número de partes en que está dividida la colección.
Por defecto, Java calcula el hashcode de los objetos a partir del valor de todos
sus atributos, de manera que cualquier modificación sobre un elemento implica modificar su código hash. Por otra parte, la propia documentació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 razón, y para mantener la especificación antes comentada acerca de la
1
2
Variable del entorno de ejecución accesible mediante Runtime.getRuntime().avaliableProcessors()
Para aligerar la redacción, se prescindirá de las referencias al parámetro genérico de las colecciones
4.2. Implementación
43
distribución de los elementos según su hashcode, la operación de aplicación implementada en ParallelSet redistribuye los elementos entre los subconjuntos de acuerdo a
los nuevos códigos hash derivados de las modificaciones realizadas.
Como este problema sólo afecta al rendimiento de la operación de aplicación, no supone mayor inconveniente utilizar ParallelSet para la implementación de colecciones
donde no se realice dicha operació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 colección paralela ParallelList: Utiliza una estructura de datos basada en subcolecciones ArrayList, quedando libre por tanto del problema de la
modificación de sus elementos. En este caso la distribución de los elementos sólo
respeta el código hash inmediatamente después de su inserción, ya que una vez
modificados ésta ya no se asegura.
Sobrecarga del mé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 método que obtiene el código hash para que éste solamente se
calcule a partir de dichos atributos invariantes.
4.2.2.
Gestión de threads
En una operación paralela, cada hilo se encargará de procesar simultáneamente
una subcolección del conjunto. Como además el número de subconjuntos es conocido
y relativamente fijo, se creyó conveniente la utilización de una estructura de tamaño
determinado para la gestión de los diferentes threads, escogiendo los thread pools de
java.util.concurrent por adaptarse sus caracterı́sticas al problema que nos ocupa:
la realización de operaciones simultáneamente constituye un conjunto de tareas que
deben finalizarse en su totalidad para poder continuar con la ejecución del programa.
44
4. Paquete ParallelCollections
1 private ArrayList<Set<T>> subsets ; // Supó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 tamañ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 nú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 ó 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 código para la gestión de threads
4.2. Implementación
45
Por defecto, el tamaño del thread pool coincide con el número de subconjuntos de la
colección, que también coincide por defecto con el del número de núcleos del sistema.
De esta manera es teóricamente posible atender a un tiempo todas las tareas de una
misma operació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 ejecución.
De todas maneras, el programador puede definir un tamaño de pool diferente a la hora
de instanciar una nueva colección.
La plantilla de código de la figura 4.1 aproxima la implementación del proceso de
gestión de threads utilizado en la clase ParallelSet. Una vez definidas las estructuras
de control de los hilos de ejecución (lı́neas 4-6), se envı́an mediante el mé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 método run() de la interfaz también incluye
la instrucción de decremento del CountDownLatch. El valor de este contador es inicializado al número de subconjuntos existentes, de manera que cuando todos los hilos han
llamado a countdown() dicho contador alcanza el valor 0 y desbloquea la ejecución
previamente puesta en espera con await(). Esta última operación podrı́a lanzar una
InterruptedException si alguno de los hilos es interrumpido por alguna razó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 catálogo se implementa usando su correspondiente método en la clase ParallelSet. Dichos métodos incluyen el esqueleto de
código de la figura 4.1 antes comentado, además de la correspondiente tarea a realizar
sobre el subconjunto en cuestión. Mientras que la paralelización de las operaciones se
realiza desde la clase, las operaciones propiamente dichas deben ser especificadas por
el programador cumpliendo una interfaz diferente según la operación a realizar.
46
4. Paquete ParallelCollections
Seguidamente se enumera, para cada operación, la interfaz correspondiente junto
con una breve descripción de su funcionamiento, ası́ como algunos ejemplos de uso sobre un hipotético conjunto de empleados representado por ParallelSet<Employee>
staff, variable definida en la lı́nea 2 de la figura 4.2.
Para más información el programador puede consultar el manual de usuario incluido en el apéndice A, donde se incluyen explicaciones más detalladas acerca del uso y
funcionamiento de estas operaciones.
Aplicació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 ó 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 ó n de l a o p e r a c i ó n
10 staff . apply ( newIncome ) ;
Figura 4.2: Ejemplo de uso del método apply() y la interfaz Application
Utiliza Application<T>, que cuenta con el método void apply(T element) que
implementa la función a aplicar sobre cada uno de los elementos, proceso que se realiza
de forma secuencial simultá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 función a
aplicar es implementada por la interfaz de las lı́neas 4 a 8.
4.2. Implementación
47
Reducció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 método reduce() y la interfaz Reduction
En la figura 4.3 puede observarse que Reduction<T> se compone de dos métodos, T
reduce(T a, T b) para aplicar la reducción sobre un par de elementos y T neutral()
para definir el elemento neutro de la operación. En este caso, la reducció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 más cobra de toda de la plantilla.
En concreto, reduce(a,b) va combinando todos los elementos del conjunto, siendo el primer par de parámetros el formado por el valor de retorno de neutral() y
el primer elemento extraı́do del conjunto. Una vez calculada esa reducción, el resultado de la misma se combina con el siguiente elemento extraı́do, y ası́ sucesivamente
hasta obtener la reducción de todo el conjunto. Este proceso es realizado de forma
simultánea en cada uno de los subconjuntos, mediante el uso del método private T
subsetReduction(Reduction<T> op, Collection<T> subset), que devuelve para
cada uno de ellos la reducción implementada en la interfaz Reduction<T> op. Una
vez obtenida la reducción de cada subconjunto, se agrupan esos valores y se vuelve a
llamar a subsetReduction para obtener el resultado final de la operació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 método select() y la interfaz Comparator
El método boolean hit(T element) de Comparator<T>, implementado en las
lı́neas 1 a 5 del código de ejemplo de la figura 4.4, comprueba si se cumple o no para
cada elemento la condición de selección establecida. En este caso, dicha condición es
que el empleado cobre má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 método map() y la interfaz Mapping
El método S map(T element) incluido en Mapping<S,T> realiza la operació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 método
map() de la interfaz (lı́neas 2-4) simplemente extrae el sueldo de cada empleado. Nótese
la diferencia de tipos entre los elementos del conjunto (clase Employee) y los objetos
devueltos por la operación (clase Double).
4.2. Implementación
49
Relació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 método relation() y la interfaz Relationship
La relación entre dos listas es definida por la interfaz Relationship<T,S>, que
cuenta con cuatro métodos:
boolean isReflexive(): Sirve para definir la relación como reflexiva o no.
boolean isSymmetric(): Sirve para definir la relación como simétrica o no.
boolean areRelated(T e1, S e2): Condición que relaciona los elementos de un
par.
boolean reflexCond(T e1, S e2): Condición de reflexió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 inclusió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 simétricos.
En el ejemplo de la figura 4.6 se obtiene un conjunto de pares tales que el primer
empleado del par cobra más que el segundo empleado. Esta relación no es reflexiva
(véase el valor de retorno false en la lı́nea 3) ni simétrica (lı́nea 6), ya que un empleado
nunca puede cobrar más que sı́ mismo y tampoco es posible que si un empleado A cobra
más que uno B, se pueda dar a la vez la situación inversa.
4.2.4.
Interfaz del conjunto paralelo
Al implementar la interfaz Set<T>, el conjunto paralelo interactúa con el resto
de clases a través de los métodos que dicha interfaz exige, ası́ como a través de los
métodos correspondientes a las operaciones soportadas. Además, la clase proporciona
dos constructores y métodos de configuración de los parámetros de ejecució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 número de subconjuntos que de threads en el pool. Esta cantidad
coincide a su vez con el número de núcleos disponibles en el sistema, tal y como se
4.2. Implementació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.
Métodos de configuración
1 // Métodos de c o n f i g u r a c i ó n
2 public void changePoolSize ( int new_num_threads )
3 public void changeSubsetsNumber ( int new_num_subsets )
Figura 4.8: Métodos de configuración de la clase ParallelSet
Los parámetros de trabajo del conjunto paralelo (número de subconjuntos y tamaño
del thread pool) también pueden ser modificados sin necesidad de volver a crear una
nueva instancia de la colección pasando como parámetros al constructor las nuevas condiciones. Para ello pueden utilizarse los métodos referidos en las lı́neas 2 y 3 de la figura
4.8, que modifican respectivamente el tamaño del pool y el número de subconjuntos.
La utilización de cualquiera de estas dos instrucciones de configuración implica
detener la ejecución de todos las las tareas enviadas al thread pool. Además, en el
caso de changeSubsetsNumber(), se reorganizarı́an todos los elementos entre el nuevo
número de subconjuntos, proceso que resulta costoso si la colección de elementos tiene
un tamañ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 métodos secuenciales equivalentes de las mismas,
programados a efectos comparativos (lı́neas 10-14). Obsérvese el detalle de que todas
las interfaces y resto de parámetros empleados en los métodos paralelos deben estar
acompañados por el modificador final, que asegura la inmutabilidad de la variable a
la que acompaña durante la ejecució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 métodos de operación de la clase ParallelSet<T>
Métodos de manipulación de elementos
Finalmente, en la figura 4.10 se listan los métodos de manipulación de elementos
de la colección. Nótese que se respeta la especificación propia de un conjunto, puesto
que los métodos add() y remove() no hacen referencia alguna a ı́ndices o posiciones.
Ası́ mismo no existe ningún método que permita el acceso ni modificación indexados
a ningún elemento, siendo el uso de un Iterator (lı́nea 5) o de un foreach la única
manera de recorrer los elementos de la colección. Son también importantes los métodos
para la gestión de colecciones, reflejados en las lı́neas 10 a 13 de la figura 4.10, y que
permiten con una sola operación añadir a, eliminar de o mantener en el conjunto todos
los elementos contenidos en la colección especificada.
4.2. Implementación
53
1 // Métodos de m a n i p u l a c i ó 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 métodos de manipulación de elementos de la clase ParallelSet<T>
Capı́tulo 5
Evaluación
La evaluación del paquete ParallelCollections implementado ha sido realizada
desde dos puntos de vista: programabilidad y rendimiento obtenido.
La evaluación de la mejora de programabilidad se centra en analizar hasta qué punto se ha conseguido facilitar la implementació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 versión paralela implementada mediante la librerı́a y una versión secuencial de cada código. Asimismo, se ha
ido comprobado la evolución del rendimiento a medida que crece el número de núcleos
disponibles.
5.1.
Programas de prueba
Para la realización de las diferentes pruebas que conforman la evaluación de la librerı́a ParallelCollections se han implementado y utilizado los siguientes programas
de ejemplo:
5.1.1.
SalaryIncrease
El ejemplo de aplicación de funciones planteado en el apartado 4.2.3 e incluido en la
figura 4.2 sirve de muestra acerca de cómo el uso de la librerı́a ParallelCollections
55
56
5. Evaluació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 ó n de l a f u n c i ó 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 máximo rendimiento a su máquina multinúcleo en comparación con el threading nativo.
En dicho ejemplo se aplicaba sobre un ParallelSet de empleados una función que
aumentaba el sueldo de cada uno, utilizando para ello la operació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 operación utilizando directamente un thread pool sobre una
colección nativa de Java requiere escribir un código similar al de la figura 5.1, que
implementa el siguiente algoritmo:
1. Cálculo de las partes en que se divide el conjunto para su reparto entre los distintos
threads del pool (Lı́neas 8-12)
2. Operación de aplicación (lı́neas 13 a 33): Se definen interfaces Runnable, cuyos
métodos run aplican la subida de sueldo (lı́neas 18-23) a la parte que los parámetros de las lı́neas 16 y 17 delimitan. Cada una de estas interfaces es enviada como
tarea al pool mediante la instrucción submit() de la lı́nea 14. Una vez que todas
las tareas han ejecutado la instrucción de decremento del contador de la lı́nea 24,
éste desbloquea la ejecución del programa pausada con la llamada await() de la
lı́nea 29. Finalmente se cierra el thread pool con el método shutdown() (lı́nea 33).
Puede verse que el código de la figura 5.1 es ostensiblemente más largo que el que
se obtiene utilizando la librerı́a, quedando comprobado que con el uso del paquete
ParallelCollections se reduce el código necesario para la realización de operaciones
paralelas.
5.1.2.
AirControl
El programa implementado en Examples.AirControl consiste en una abstracción
relativamente sencilla de las operaciones necesarias para gestionar el tráfico de aeronaves
58
5. Evaluación
1 // Avió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 aé 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 ó n
18 Foreach Plane : espacio {
19
set predX = currentY + velX
20
set predY = currentY + velY
21 }
22
23 // PASO 2 : C á 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 áerea. Dos son las entidades que definen el problema: por
una parte la zona aérea a controlar, representada como un cuadrado y modelada por
una colección paralela; y por otra, un conjunto de aviones que recorren la zona y que
se caracterizan por su posición y por la velocidad a la que vuelan.
Problema
El objetivo principal es evitar las colisiones entre aeronaves, estableciendo para ello
dos parámetros de seguridad: una velocidad máxima y una distancia mı́nima entre
aparatos. La idea básica es calcular, de acuerdo a su posición y velocidad actuales,
la predicción de movimiento de cada avión antes de que éste se desplace, de forma
que cruzando las predicciones obtenidas se obtenga qué pares de aeronaves violan la
distancia de seguridad.
Algoritmo
El algoritmo presentado en la figura 5.2 consta de los siguientes pasos:
1. Cálculo de la predicción de movimiento para todos los aviones: Resultado
de sumar posición (currentX,currentY) y velocidad (velX,velY), obteniendo
un punto futuro (predX,predY), cá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 cálculos pueden
realizarse con apply() y una interfaz Application<Plane> que implemente el
cálculo de la predicción para cada avión.
2. Cruce de las predicciones generadas: En la figura 5.2, este paso supone
la ejecución del foreach definido en la lı́nea 23. En dicho bucle se determina
para cada par de aviones si éstos violan la distancia de seguridad, establecida
en la variable de control distDanger de la lı́nea 10. Estos cálculos pueden ser
realizados utilizando la operación relation() de la librerı́a paralela y una interfaz
Relationship<Plane,Plane> para dar forma a la relación, que es reflexiva y
simétrica.
60
5. Evaluación
5.1.3.
ShortestPath
Los có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 colección paralela. Dichas aristas, ademá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 definició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 condición de que dicho camino sea el más corto posible. La
idea bá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 búsqueda de aristas iniciales de ShortestPath
5.1. Programas de prueba
61
1 // Bú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 búsqueda de aristas conectadas de ShortestPath
62
5. Evaluación
1 // Bú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 bú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 bú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 búsqueda. En concreto, mientras que la primera variante recorre todas
las aristas del mapa intentando seleccionar las siguientes en cada iteración, la segunda
implementa una relació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 código de la figura 5.3, y que es utilizada para almacenar los
sucesivos niveles de profundidad que se van alcanzado durante la ejecución (variable
my edge.depth) ası́ como los puntos de origen y destino a comprobar en cada iteración.
Algoritmo
1. Localizació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), además de controlar si alguna de dichas aristas es la final
64
5. Evaluación
(lı́nea 13). Para el marcado de las aristas puede emplearse la operación apply()
de la librerı́a.
2. Bú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 (condició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 instrucción de la lı́nea 4
pueden ser seleccionadas con la operació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 según la condició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 obtención de las aristas conectadas
puede realizarse utilizando la operacion relation() de la librerı́a, utilizando
la condición antes comentada como condición de la relación.
3. Repetició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 ú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 condición serı́a la
5.2. Estudio de programabilidad
65
adecuada para una hipotética implementación paralela con select(). Para finalizar, el proceso se repite hasta alcanzar la arista inicial (condició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 programación de aplicaciones paralelas para sistemas multinúcleo. Para comprobarlo se han planteado una serie de pruebas en las que se compara
la implementación de un programa de ejemplo utilizando las clases proporcionadas por
la librerı́a ParallelCollections con otra versión paralelizada de forma manual:
Versión con ParallelCollections: Estas implementaciones se sirven directamente de las clases y métodos proporcionados por ParallelCollections para la
realización de operaciones paralelas sobre las colecciones de datos.
Versió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 comparación se pretende poner de manifiesto la mayor facilidad de programación que supone el uso de la librerı́a sobre la gestión explı́cita de la paralelización. Como la facilidad de programación es un concepto relativamente subjetivo, para
realizar estas pruebas se comparará el número de lı́neas de código necesarias para la
implementación de ambas versiones, utilizando para estas mediciones las herramientas
SLOCCount, que a continuación se presentan.
SLOCCount
SLOCCount es un conjunto de herramientas diseñadas para el conteo de lı́neas de
código fuente1 fı́sicas en sistemas software potencialmente grandes y que se encuentra
1
De ahı́ SLOC, Source Lines Of Code
66
5. Evaluación
disponible bajo licencia GPL2 . Desarrollado por David A. Wheeler y originariamente
destinado a la medición del código de una distribución GNU/Linux completa, puede
utilizarse para la evaluación del tamaño de cualquier sistema software[18].
Los resultados generados por el programa, además del número de SLOCs de los
ficheros fuente analizados contienen un pequeño análisis basado en COCOMO3 , un
modelo matemático empı́rico utilizado para la estimació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 códigos de ejemplo
A continuación se adjuntan los resultados de realizar este mismo tipo de prueba con
el có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
Reducción
SalaryIncrease
16
47
66 %
AirControl
31
86
64 %
ShortestPath1
45
122
63 %
ShortestPath2
62
117
47 %
Tabla 5.1: Lı́neas de código de los problemas de ejemplo con y sin ParallelCollections
Las cifras presentadas en la tabla 5.1 concuerdan con la afirmación realizada a
este mismo respecto en el apartado 5.1.1, manteniéndose la reducción de código en las
soluciones a los problemas planteados utilizando ParallelCollections.
2
3
GNU General Public License
COnstructive COst MOdel
5.3. Análisis de rendimiento y escalabilidad
5.3.
67
Análisis de rendimiento y escalabilidad
Si algo se espera de una estructura de datos que soporte la realizació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 multinúcleo.
Ası́ mismo, resulta de interés comprobar cómo responde la librerı́a al aumento de
recursos a su disposición, es decir, a su ejecución en procesadores con un elevado número de nú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
(núcleos y memoria principal).
Este conjunto de pruebas ha sido ejecutado en el clúster “NM” del Departamento de
Electrónica y Sistemas de la Universidade da Coruñ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 versión 1.6.0 07. En concreto se han utilizado los siguientes tipos de nodo:
Nodo “c1”: 8 nú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 nú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 códigos de prueba planteados en el ejemplo SalaryIncrease no han sido incluidos
en la evaluació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. Evaluación
5.3.2.
AirControl
Para las simulaciones con el programa de control áereo se han definido zonas de
dimensiones ocupadas por 50000 aviones capaces de volar a una velocidad máxima de
31 y estableciendo como distancia de seguridad 15 unidades.
En cada ejecución se ha ido modificando de manera creciente el número de threads
disponibles en el pool, variando su tamaño en intervalos de potencias de 2. Todos los
tiempos reflejados en esta secció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 ejecució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: Aceleración obtenida para AirControl sobre un nodo “c1” de 8 núcleos
En la tabla 5.2 puede comprobarse que los tiempos de ejecución se van reduciendo
5.3. Análisis de rendimiento y escalabilidad
69
notablemente a medida que se aumenta el número de threads disponibles en el pool. A
partir de dichos tiempos se ha construido la gráfica de la figura 5.7, en la cual se puede
comprobar cómo la colección paralela aprovecha los recursos disponibles a medida que
éstos crecen, puesto que se obtienen aceleraciones cercanas a las ó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 añadiendo la creación y lanzamiento de un
nuevo thread, lo que hace que el tiempo total de la operación sea ligeramente superior.
Modo
8 threads
16 threads
32 threads
64 threads
Tiempo (ms)
5279
5123
4620
3974
Tabla 5.3: Tiempos de ejecución de AirControl en milisegundos sobre un nodo “c1” para 8,
16, 32 y 64 núcleos
Ası́ mismo, la tabla 5.3 muestra la evolución del rendimiento para un número de
threads y subcolecciones superior al de núcleos del nodo. Los datos muestran cómo, en
este caso, también se obtienen mejoras en el rendimiento al reducirse ligeramente los
tiempos de ejecució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 ejecución de AirControl en milisegundos sobre un nodo “c2” de 24
núcleos
Tanto de la tabla 5.4 como de la gráfica de la figura 5.8, que reflejan respectivamente
los tiempos medios y la aceleración obtenidos para la ejecución de AirControl sobre el
nodo “c2” de 24 núcleos, pueden deducirse conclusiones similares a las propuestas a
partir de los resultados arrojados por la ejecución de AirControl sobre el nodo de
70
5. Evaluació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: Aceleración obtenida para AirControl sobre un nodo “c2” de 24 núcleos
8 núcleos. Por una parte, a mayor número de threads mayor rendimiento; por otra,
sigue sucediendo el mismo fenómeno de ralentización para la ejecución con un único
hilo a causa de realizarse el mismo trabajo que en secuencial y, además, la creación y
lanzamiento del thread.
5.3.3.
ShortestPath
Para las simulaciones realizadas con el programa de localizació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 ejecución se ha ido modificando
de manera creciente el número de threads disponibles en el pool, variando su tamañ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. Aná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 ejecución de ShortestPath1 en milisegundos sobre un nodo “c1” de 8
nú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: Aceleración obtenida para ShortestPath1 sobre un nodo “c1” de 8 núcleos
La tabla 5.5 y la gráfica 5.9 reflejan respectivamente los tiempos medios y la aceleración obtenidas para la ejecución de ShortestPath sobre el nodo “c1” de 8. Analizando
estos datos puede verse que con el aumento del tamaño de pool el rendimiento no escala tan bien como sucede en el caso de AirControl. Aunque los tiempos de ejecución
siguen disminuyendo, lo hacen en menor medida; y la aceleración obtenida, aunque
importante, se aleja notablemente de la óptima representada en rojo en la gráfica.
72
5. Evaluació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 ejecución de ShortestPath1 en milisegundos sobre un nodo “c2” de 24
nú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: Aceleración obtenida para ShortestPath1 sobre un nodo “c2” de 24 núcleos
La tabla 5.6 y la gráfica 5.10, construidas a partir de los datos obtenidos para
la ejecución sobre 24 núcleos, muestran información similar a la que resulta para 8,
observándose también un menor aumento del rendimiento a medida que crece el tamaño
de pool.
5.3. Aná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 nú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 número de subcolecciones mayores que el número de núcleos del nodo supone una
mejora importante en el rendimiento, reduciéndose notablemente el tiempo de ejecució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
realización de un estudio completo de rendimiento de la librerı́a para su uso con el
segundo algoritmo del camino más corto.
Capı́tulo 6
Conclusiones
A continuación se presentan las conclusiones resultantes del trabajo desarrollado
hasta la obtención del paquete ParallelCollections junto con diferentes posibilidades
de continuación y mejora del presente proyecto.
6.1.
Resumen del trabajo realizado
Con la implementació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 multinúcleo. Para alcanzar este objetivo, ha sido necesario estudiar previamente
qué opciones ofrece el lenguaje de programación Java para la extracción del paralelismo,
ası́ como las diferentes peculiaridades de las clases nativas del framework Collections
en que se basan las colecciones genéricas implementadas.
Una vez conseguida una implementación estable y funcional de la librerı́a, se ha
procedido al análisis de su rendimiento y programabilidad utilizando diversos ejemplos
de prueba que en cierto modo aproximan posibles casos reales de utilizació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:
Implementación de un paquete de clases de colección sobre las que es posible
realizar una serie de operaciones de forma paralela, aprovechando ası́ la presencia
de varios núcleos en el sistema.
La librerı́a implementada facilita la programación paralela de sistemas multinúcleo
sin necesidad de realizar un gran esfuerzo de programació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 programación como en aprovechamiento satisfactorio de la presencia de varios procesadores.
6.3.
Trabajo futuro
Esta sección se proponen una serie de modificaciones y/o añadidos que dotarı́an a
la librerı́a implementada de una mayor robustez y seguridad de utilización.
6.3.1.
Mejora de la genericidad
La mayorı́a de las clases e interfaces del paquete incorporan genericidad mediante
el uso de parámetros formales de tipo. Esta aproximación, aunque ha facilitado enormemente la escritura del código, puede plantear algunos problemas a la hora de crear
colecciones susceptibles de incoporar elementos de clases diferentes pero con una superclase común. Para ello debe revisarse la posibilidad de añadir también wildcards1 ,
tanto normales como acotadas, en la definición de tipos y clases genéricas.
1
Véase apartado 3.2.3.
6.3. Trabajo futuro
6.3.2.
77
Incorporación de nuevas operaciones
Partiendo de la base que proporciona ParallelCollections, existen una serie de
añadidos al mismo que pueden resultar de interés, destacando la incorporación de nuevas operaciones, ya que las soportadas por las colecciones del paquete se reducen a
aquellas más elementales e intuitivamente paralelizables. Sin embargo, existen muchas
otras operaciones más complejas con posibilidad de ser implementadas.
Un ejemplo de ello serı́a el framework MapReduce de Google, dedicado al procesamiento y generación de grandes conjuntos de datos. Para su utilzación el programador
especifica una funció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 función de reducción que reúne todos los valores intermedios asociados
a una misma clave intermedia. Esta forma de programar, que supone la paralelización
automática de las operaciones para su ejecución en grandes clústeres, permite a programadores sin experiencia en sistemas paralelos y/o distribuidos servirse de forma fácil y
rápida de los recursos que éstos ofrecen[19].
6.3.3.
Aplicación en entornos más realistas
Los ejemplos básicos planteados utilizando la clase Employee ası́ como los programas
descritos en el capı́tulo de pruebas, aunque adecuados para un análisis general del
aprovechamiento de recursos por parte de las operaciones paralelas implementadas,
no suponen una gran carga de trabajo y só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 códigos que, aún basándose en
las operaciones elementales incluidas en las colecciones paralelas, supongan mayores
cargas computacionales y hagan un uso más intensivo de los diferentes núcleos del
procesador.
Apéndice A
Manual de usuario/programador
El presente capı́tulo constituye el manual de usuario de la librerı́a de colecciones
ParallelCollections.
A continuación se repasa brevemente cómo funcionan las colecciones paralelas de
esta librerı́a proporcionando pequeñas explicaciones, con sus correspondientes ejemplos
de có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 có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.
Creación de estructuras
Para la instanciación de nuevas colecciones se proporcionan dos constructores, uno
por defecto y otro parametrizado. Mientras que el constructor por defecto crea una nueva colección con tantos subconjuntos como núcleos haya disponibles en el sistema y un
thread pool de igual tamaño, la versión parametrizada permite definir estos parámetros
manualmente. Las figuras A.1 y A.2 ejemplifican ambos casos mediante la instanciación
de conjuntos paralelos de números enteros:
79
80
A. Manual de usuario/programador
1
ParallelSet<Integer> conjunto_por_defecto = new ParallelSet<Integer >() ;
Figura A.1: Instanciación de un ParallelSet utilizando el constructor por defecto
1
ParallelList<Integer> listaparametrizada = new ParallelList<Integer >() ;
Figura A.2: Instanciación de una ParallelList mediante el constructor parametrizado
A.2.
Manipulación de datos
Una vez detalladas las opciones existentes para la instanciación de nuevas colecciones paralelas, se procede a detallar cómo manipular datos con las mismas. Como se puede comprobar en el apartado 4.2.4, las clases de colecciones de ParallelCollections
implementan los métodos exigidos por la interfaz Set1 , entre los que se encuentran los
siguientes:
boolean add(T e): Intenta añadir un elemento e al conjunto, devolviendo un
valor lógico segú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 está 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 lógico según haya sido posible o no.
int size(): Obtiene el nú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 añ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 métodos de manipulació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 colección de Java, permitiendo añadir y eliminar
elementos, recorrer las listas, etc.
A.3.
Operaciones paralelas
ParallelCollections incorpora a sus colecciones algunas de las operaciones más
empleadas en procesamiento paralelo, ası́ como la versión secuencial equivalente para
cada una de ellas. A continuación se explica, mediante diferentes explicaciones basadas
en los ejemplos de código planteados en el apartado 4.2.3 de la memoria, có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 cálculo en cuestión en su método apply() (lı́nea 3). Finalmente se llama al método del conjunto
paralelo asociado a la operació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 mé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 método reduce() y la interfaz Reduction
En el ejemplo de la figura A.5 se muestra cómo utilizar una interfaz Reduction
(lı́neas 1-11). Por una parte, el método reduce() implementado en las lı́neas 2 a 7 del
código va combinando pares de empleados de acuerdo a la reducción implementada,
seleccionando en este caso el que más cobra de los dos. Por otra, el mé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 operació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 método select() y la interfaz Comparator
La figura A.6 muestra un ejemplo de uso de la interfaz Comparator para realizar
una operación select(). En concreto, se desea seleccionar qué empleados de una empresa cobran más de 1.500 euros.
Para ello se implementa en las lı́neas 1 a 5 una interfaz Comparator que comprueba
mediante el método hit() si el sueldo de cada empleado supera la cantidad establecida
en la lı́nea 3. Una vez definida la interfaz, ésta es pasada como parámetro al método
select() del conjunto para generar el resultado de la selecció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 método map() y la interfaz Mapping
En la figura A.7 se ha implementado una operació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 operación realizada tiene como resultado objetos de clase diferente a del
conjunto, la declaración de la interfaz necesita dos pará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 método relation() y la interfaz Relationship
El fragmento de código de la figura A.8 muestra un ejemplo de uso de la operación
relation(). En concreto, genera una lista de pares <Employee,Employee> tales que
el primer empleado del par cobre más que el segundo. Para el cálculo de esta relación se
implementa la interfaz mejorPagadoQue, de tipo Relationship<Employee,Employee>
A.4. Advertencias y comentarios
85
(lı́neas 1-14). La relación propiamente dicha la establece el método areRelated(), que
comprueba si los elementos de un par cumplen la condición deseada, utilizando el resto de métodos de la interfaz para determinar sus propiedades. Con isReflexive() e
isSymmetric() (lı́neas 2 y 5) el programador determina si la relación a calcular es
reflexiva y/o simétrica.
En el caso concreto de mejorPagadoQue sucede que un empleado no puede estar
relacionado consigo mismo (no puede cobrar más que sı́ mismo) y que si un empleado e1 cobra más que otro e2, es imposible que se dé la relación en sentido contrario.
reflexCond() implementa la condición para que un par sea reflexivo. La mayorı́a de
relaciones calculadas serán entre conjuntos del mismo tipo, de manera que los pares
asociados a una relación reflexiva serán aquellos en los que el primer elemento y el
segundo sean iguales. Por este motivo el método reflexCond() normalmente se implementa tal y como aparece en la lı́nea 14.
Una vez completada la definición de la relación a calcular, con su condición y sus propiedades, se llama al método relation() del conjunto paralelo pasando como parámetros la lista con la que se desean cruzar los datos (en este caso la misma) y la interfaz
Relationship correspondiente (mejorPagadoQue). Esta operación es llamada por la
instrucción ejecutada en la lı́nea 16 del código, resultando un conjunto paralelo de elementos <Pair<Employee,Employee>> con los pares de empleados que cumplen la
relació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 mé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 última operación paralela éste permanecerá a la espera de más tareas
en forma de threads de forma indefinida, bloqueando la ejecución de todo el programa.
Para evitar esto, basta con llamar al método shutdownPool() de la colección, que a
su vez llama al método shutdown() del pool, el cual detiene de forma segura y ordenada
el funcionamiento de esta estructura.
A.4.2.
Documentación de la librerı́a
Ya para terminar, recordar al programador y futuro usuario de este paquete Java que tiene a su disposición un CD con el código y las fuentes tanto de la librerı́a
ParallelCollections como de los ejemplos implementados, ası́ como toda la documentación de las mismas en formato Javadoc. Ademá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 distribució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 Castañeda, S., “Metodologı́as de paralelizació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
BIBLIOGRAFÍ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.

Top subcategories

Top subcategories

Top subcategories

Top subcategories

Top subcategories

Top subcategories

Top subcategories

Download Implementación de una librer´ıa de colecciones genéricas en Java