Universidad de Costa Rica Escuela d e Ciencias de la Computación e Informática
Trabajo final de graduación para optar por el grado de Licenciatura en Ciencias de la Computación e Informática Modalidad de proyecto
tdderive:Sistema distribuido débilmente acoplado para el
descubrimiento de conocimiento
Elaborado por: Alessandro Cordero Salazar alessco~ecci.ucr.ac.cr. Carné 931 192
Profesor director: Ronald Argüe110 Venegas
[email protected]. Ciudad Universitaria Rodrigo Facio Diciembre, 2006
tdderive:Sistema distribuido débilmente acoplado
para el descubrimiento de conocimiento Este proyecto de graduación ha sido aceptado como requerimiento parcial para optar por el grado de Licenciatura en Ciencias de la Computación e Informática.
Director
TFG /
-\
,
/
, , / / c ( < ( c
/' (
(
;
J
(-
Pofesora Ileana A l p i a r Arias, M.Sc
/-
Profesor "
sola Murillo, M.Sc
Profesor Vladimir Lara Villagrán, Ph.D Presidente del Tribunal v lector
Profesór Francisco ~ r r o f Mora, i M.Sc Lector
Sustentante
Dedicatoria A mis padres, Ana Celia y Víctor Hugo, por todo su apoyo y comprensión, pero sobre todo por su inspirador ejemplo de lucha y tenacidad.
Reconocimientos Muchas gracias a Ronald Argüe110 por su dedicada y oportuna guía y su generosa ayuda durante el desarrollo del proyecto, así como también pos permitirme estudiar a fondo y utilizar su aplicacii~nd e minería de datos. Muchas gracias a Ileana Alpízar y a Edgar Casasola por sus observaciones sinceras, objetivas y siempre trascendentes no solamente para mejorar este proyecto sino también para tomarlas en cuenta en futuras investigaciones. Quiero agradecer profundamente a todos aquellos que alguna vez promovieron y formaron parte del Programa de Investigación en Bases d e Datos de la ECCI, tanto estudiantes asistentes como profesores. Sin dicho programa de investigación este proyecto no hubiera sido posible.
A Vladimir Lara quiero agradecerle la oportunidad de permitirme instruir algunos cursos de programación de la ECCI, pues esta actividad me enseñó a apreciar la utilidad de la aplicación de patrones de software. El desarrollo de este proyecto fue largo y durante el mismo muchas personas me motivaron a seguir adelante y a no perder ni ánimos ni objetivos. Entre ellos se encuentran mis entonces alumnos de programación y de investigación de operaciones, mis entonces compañeros de coro y muchos compañeros de Universidad para la Paz, y a ellos, en esta mención final, les quiero agradecer por todo su apoyo.
Tabla de contenidos 1 Introducción 1.1 El proyecto tdderive 1.1.1Campo de estudio del proyecto 1.1.2Justificación del proyecto 1.2 Objetivos del proyecto 1.3 Alcances y limitaciones 1.4 Acerca de este documento 2 Metodología empleada en el desarrollo del proyecto 2.1 Método del estudio del dominio de conocimiento 2.1.1 Parte teórica 2.1.2 Parte práctica 2.2 Método de la formulación del problema 2.3 Método de diseño 2.4 Método de implementación 2.5 Método de pruebas 2.6 Aplicación de los métodos 2.6.1 Aplicación del método del estudio del dominio de conocimiento 2.6.2 Aplicación del método de la formulación del problema 2.6.3 Aplicación del método de diseño 2.6.4 Aplicación del método de implementación 2.6.5 Aplicación del método de pruebas 2.6.6 Casos de prueba Experimento 1: Un trabajo con un servidor Experimento 2: Un trabajo con cuatro servidores Experimento 3: Un trabajo erróneo con dos servidores Experimento 4: Seis trabajos con ocho servidores Experimento 5: Siete trabajos con ocho servidores y dos de ellos h e r a repentinamente Experimento 6: Siete trabajos con ocho servidores y uno de ellos fuera temporalmente 3 Análisis del problema y su solución
3.1 Estrategias del procesamiento de dderive 3.1.1 Implementación de árboles de decisión 3.1.2 Mecanismo de derivación de árboles de decisión 3.1.3 Trabajo colaborativo para generar árboles de decisión 3.2 El diseño de dderive 3.3 Características y problemas de dderive 3.4 Solución: tdderive, sus propiedades y decisiones de diseño 3.4.1 Decisiones de diseño
4 Diseño básico de tdderive 4.1 Arquitectura básica del sistema 4.1.1 Principales componentes del procesamiento de tdderive 4.2 Detalles del diseño 5 Organización de la información en tddenve 5.1 Soporte para la coordinación de tareas y la discriminación de su calidad 5.1.1 Entidades para la coordinación 5.1.2 Entidades para la discriminación de la calidad 5.1.3 Relaciones entre las entidades de la coordinación de tareas del sistema y discriminación de la calidad 5.2 Soporte para los protocolos de recuperación 5.3 Soporte para el balance de carga 5.3.1 Entidades del balance de carga 5.3.2 Relaciones entre las entidades del balance de carga 5.4 Objetos de información y el componente admin.repositorio 5.5 Objetos de información de cada subsistema de tdderive
6 Diseño de las comunicaciones 6.1 Patrón Aceptador-Conector: para el intercambio de mensajes 6.1.1 Componentes del patrón Aceptador-Conector y sus interacciones 6.2 Patrón Objeto Activo: para el acceso a objetos remotos 6.2.1 Componentes del patrón Objeto Activo y sus interacciones 6.2.2 Componentes del patrón Objeto Activo y su relación con componentes del patrón Acep tador-Conector 6.3 Objetos de información participantes en el subsistema de comunicaciones 7 Diseño de la administración de recursos de tdderive 7.1 Políticas de administración 7.1.1 Balance de carga hidrodinárnico (Política a) 7.1.2 Retardo en la ejecución local (Política (S) 7.1.3 Discriminación de la calidad del procesamiento externo (Política 71) 7.1.4 Indicadores para las políticas de administración 7.1.5 Modelo de planificación del procesador y sus componentes 7.2 Mecanismos de administración y gestión de tareas 7.2.1 Modelo de identificación de procesos 7.2.2 Modelo de ejecución de procesos y sus componentes 7.2.3 Gestión de la aplicación y modelo de recuperación de fallos
8 Diseño del subsistema de aplicaciones de tdderive 8.1 Características de una aplicacióii soportable por tdderive
8.2 Componentes para el soporte de una aplicación 8.2.1 Interacciones entre los componentes 8.3 La aplicación del sistema distribuido: dderive 9 Aspectos importantes de la implementación de tdderive 9.1 Aspectos generales 9.1.1 Anatomía de procesos computacionales en el funcionamiento del sistema 9.1.2 Estructuras de datos básicas utilizadas 9.1.3 Patrones arquitectónicos y de diseño utilizados 9.1.4 Configuración del sistema 9.2 Aspectos relacionados con el subsistema de comunicaciones 9.2.1 Determinación de u n domiriio de balance y la escalabilidad del sistema 9.2.2 Clases del subsistema d e comunicaciones 9.2.3 Por hacer en el subsistema de comunicaciones 9.3 Aspectos relacionados con el subsistema de información 9.3.1 Clases del subsistema d e información 9.3.2 Por hacer en el subsistema de información 9.4 Aspectos relacionados con el subsistema de administración 9.4.1 Algoritmo d e planificación d e tareas 9.4.2 Mecanismos para la determinación de las cargas funcional y de aplicación 9.4.3 Clases del subsistema de administración 9.4.4 Por hacer en el subsistema d e admlliistración 9.5 Aspectos relacionados con el subsistema de aplicaciones 9.5.1 Asignación de cargas de aplicación a las tareas, su división y la unión de sus resultados 9.5.2 Exportación e importación de subtrabajos 9.5.3 Recuperación de fallos 9.5.4 Retorno de resultados 9.5.5 Clases del subsistema de aplicación 9.5.6 Problemas encontrados en la implementación del subsistema de aplicaciones 9.5.7 Por hacer en el subsistema de aplicaciones
10 Comprobaciones del sistema tdderive y Conclusiones 10.1 Ejecución d e los casos de prueba Experimento 1: Un trabajo con un servidor Experimento 2: Un trabajo con cuatro servidores Experimento 3: Un trabajo erróneo con dos servidores Experimento 4: Seis trabajos con ocho servidores Experimento 5: Siete trabajos con ocho servidores y dos de ellos fuera repentinamente Experimento 6: Siete trabajos con ocho servidores y uno de ellos fuera temporalmente 10.2 Conclusiones
183 184 186 187 189
11 Resumen técnico del sistema tddeiive
195
12 Bibliografía
201
A Documentación del sistema de minería de datos dderive A.l Documentación de dderive y otras herramientas relacionadas A.2 Documentación propia del sistema dderive 214 B Depuración en la salida del sistema de minería de datos ddenve B.l Salidas de la derivación de u n árbol de decisión utilizando determinación con una distribución de probabilidad uniforme 215 B.2 Salidas de la derivación de u n árbol de decisión utilizando la determinación de primer orden 220 230 B.3 Interpretación de los resultados 232 B.4 División de las tareas de dderive
C Cálculos de los indicadores para las políticas de administración de tdderive C.l Capacidad de una computadora de referencia C.l.l Cálculo de la capacidad de una computadora C.2 Carga funcional de una computadora de referencia C.2.1 Cálculo de la carga funcional C.3 Carga de aplicación de una computadora de referencia C.3.1 Cálculo de la carga de aplicación
233 233 234 235 236 237 237
D Solicitud de una aplicación al servidor tdderive, su protocolo y configuración del cliente 239 D.l Protocolo para el inicio de una aplicación D.2 Ejemplo de un mensaje de solicit-ud D.3 Respuesta de la aplicación D.4 Configuración del cliente E Ejecución del sistema tdderive y configuración de sus valores iniciales E.1 Archivos binarios necesitados E.2 Archivos de configuración E.3 Ejemplo de las configuraciones locales y globales de tdderive E.4 Ejemplo de cómo iniciar la operación del servidor tdderive F Guiones para la creación y destrucción de la base de datos de tdderive F.l Guión para la creación de la base de datos F.2 Guión para la destrucción de la base de datos
G Archivos de configuración, resultados y ejecución de los casos de prueba
262
H Bitácoras de los experimentos 273 H.l Experimento 1: Un trabajo con un servidor 273 H.2 Experimento 2: Un trabajo con cuatro servidores 273 H.3 Experimento 3: Un trabajo erróneo con dos servidores 275 H.4 Experimento 4: Seis trabajos con ocho servidores 275 H.5 Experimento 5: Siete trabajos con ocho servidores y dos de ellos fuera repentinamente283 H.6 Experimento 6: Siete trabajos con ocho servidores y uno de ellos fuera temporalmente 290
Índice de figuras Figura 1.1 Campos de estudio más relevantes asociados con el presente proyecto. Figura 2.1: componentes que generan registros de bitácora y sus eventos Figura 2.2 Topología del sistema distribuido empleado en los casos de prueba Figura 3.1: Jerarquía funcional de dderive. Figura 3.2: Archivo de entrada para dderive Figura 3.3 Árbol de decisión para recomendar ir a jugar tenis. [MITCH97] Figura 3.4 Computación colaborativa utilizando un sistema de archivos compartido en dderive. Figura 3.5 Componentes del programa dderive Figura 3.6 Colaboración en el trabajo de dderive: inicio de una aplicación de minería de datos Figura 3.7 Funciones administrativas de tdderive Figura 3.8 Funciones de aplicación de tdderive Figura 4.1 Capas de la arquitectura de tdderive Figura 4.2 Componentes de las capas de administración y minería de datos (encargados de suministrar la minería de datos). Figura 4.3 Composición del cliente y del servidor de tdderive. Figura 5.1 Entidades para la coordinación de tareas y la estrategia de discriminación de la calidad. Figura 5.2 Entidades para los protocolos de recuperación. Figura 5.3 Entidades para el balance de carga y la estrategia de retardo en la ejecución. Figura 6.1 Patrón Aceptador-Conector aplicado a tdderive. Figura 6.2 Patrón Objeto Activo aplicado a tdderive. Figura 6.3 Patrón Objeto Activo utilizando el patrón Aceptador-Conector aplicados a tdderive. Figura 7.1 Componentes de admin y de minería. Figura 7.2 La planificación de eventos. Figura 7.3 Identificación de procesos Figura 7.4 Protocolo del inicio de una tarea y su finalización. Figura 7.5 Detalle de la exportación de archivos y su correspondiente importación en el objeto coordinador.
Figura 7.6 Pro tocolo de consumación de una tarea en tdderive.
138
Figura 7.7 Detalle de la exportación de archivos y su correspondiente importación en el 143 sistema iniciador. Figura 8.1 Componentes específicos de la aplicación de tdderive.
147
Figura 9.1 Dependencia entre los principales recursos de software, desde el p ~ i n t od e vista 152 de la construcción de tdderive. Figura 9.2 Anatomía de procesos de ttlderive.
154
Figura 9.3 Subsistema de comunicaciones completo.
161
Figura 9.4 Susbsistema de información completo y subsistema de administraciói-i 163 mostrando sus componentes relacionados. Figura 9.5 Componentes del subsistema d e administración.
170
Figura 9.6 Componentes del subsistema de aplicación. Figura 9.7 Subsistemas de administración y de aplicaciones. Figura B.l Contenido de tenis.txt Figura B.2 Contenido de DL000000010001. Figura B.3 Contenido de DL000000010002. Figura B.4 Contenido de DL00000002. Figura B.5 Contenido de DL000000030001. Figura B.6 Contenido de DL000000030002. Figura B.7 Contenido de DL000000010001. Figura B.8 Contenido d e DL000000010002. Figura B.9 Contenido de DL0000000100030001. Figura B.10 Contenido d e DL0000000100030002. Figura B.ll Contenido de DL000000020001. Figura B.12 Contenido de DL000000020002. Figura B. 13 Contenido d e DL0000000200030001. Figura B.14 Contenido de DL0000000200030002. Figura B.15 Contenido de DL0000000300030001. Figura B.16 Contenido de DL0000000300030002.
230
Índice de tablas Tabla 3.1 Decisiones para recomendar si se juega tenis.[blITCH97] Tabla 7.1 Acciones a realizar por el planificador del subsistema de administración, dado un evento del componente lector. Tabla 7.2 Indicaciones para un despachador provenientes de un planificador u otro despachador intermediario. Tabla 10.1 Experimento 4: Cantidad de subtrabajos por servidor Tabla 10.2 Experimento 5: Cantidad de subtrabajos por servidor Tabla 10.3 Experimento 6: Cantidad de subtrabajos por servidor Tabla C.l Indicadores de la capacidad de una computadora y su cálculo. Tabla C.2 Indicadores de la carga funcional y su cálculo. Tabla C.3 Indicadores de la carga de aplicación y su cálculo.
Índice de listados Listado 2.1: Inicio del servicio de bitácora de tdderive
31
Listado 2.2: Inicio de servidores tdderive
32
Listado 2.3: Ejecución de clientes tdderive
33
Listado 2.4: Comparación de los resultados de dderive y tdderive
34
Listado 3.1: Algoritmo inducción.[ A R G U E ~ ~ ]
para
la
derivación
distribuida
de
subárboles
de
49
Listado 3.2 Algoritmo para la derivacion distribuida de subárboles de inducción, adaptado para su implementación como sistema de procesamiento paralelo [ARGUEO~].
51
Listado 7.1: Algoritmo para retardar la ejecución de un subtrabajo en el servidor
102
Listado 7.2: Algoritmo para encontrar la carga de aplicación adiciona! permitida.
116
Resumen Se presenta el desarrollo y descripción inicial de un sistema distribuido débilmente acoplado llamado t d d e r i v e , el cual se encarga de plaiiificar el procesailiiei~to paralelo de uno o varios trabajos de minería de datos. Aunque el proyecto inicialmente propicia la planificación distribuida de una aplicación de minería de datos particular, llamada dcierive, ofrece la capacidad de favorecer el procesamiento de cualquier aplicación o servicio cuyos trabajos se puedan dividir en subtrabajos de ejecución paralela.
1 Introducción En esta primera década del tercer milenio, el concepto de sistema inforrnático se puede encontrar materializado de muchas formas; sin embargo las que más se distinguen son aquellas en las cuales ya no se necesita que una sola computadora sea la responsable del apoyo a las actividades del usuario, pues se trata de minimizar el contacto entre la persona y el sistema informático; particularmente, a través de sistemas de software que utilizan recursos remotos y computación colaborativa; así como de otros sistemas de software que no necesitan mucha información aportada por el usuario para realizar lo que se desea exactamente, para lo cual se emplean estrategias de transparencia para así aprovechar información sobre el contexto y ambiente en el que el usuario se desenvuelve, sin discriminar acerca de si el usuario es una persona u otro sistema computacional. Los sistemas computacionales evolucionan según el ritmo de las necesidades y exigencias de los usuarios, hacia un ente meta que le brinda al usuario cada vez menos incomodidades, más facilidades y mayor agilidad en el desarrollo de sus actividades. Al mirar los resultados de esta evolución es evidente la infinidad de interfaces para el acceso de los usuarios así como la gran gama de maneras con las que los trabajos se pueden realizar, y por supuesto, y aún más interesante son las distintas influencias y repercusiones de estos sistemas sobre las distintas sociedades humanas. Si se contempla el procesamiento computacional, del cual aquí se describe la solución a u n problema concreto, tenemos que para realizar una tarea del usuario no solamente es necesario aprovechar oportunamente los recursos locales (con referencia a la ubicación geográfica del sistema que hospeda la interfaz a la cual el usuario accede), sino que se requiere maximizar el aprovechamiento correcto y oportuno de los recursos de cómputo remotos. Cada recurso
remoto
es
seleccionable
a
partir
de
criterios
de
idoneidad
"inteligentemente" determinados en algún lugar del sistema computacional,
definiendo automáticamente tiempos de respuesta límites así como niveles de calidad para las características especiales de lo que quiere realizar el usuario como parte de su quehacer. Así como muchos programas poseen características de apertura hacia otros, con lo cual se busca cierta armonía y cooperación mutua, otros programas, quizá una cantidad enorme y mayoritaria, no han sido diseñados para componer un sistema de servicios más acorde con las complejas exigencias y necesidades de los usuarios. En virtud de ello, este proyecto está dedicado a encontrar y construir una forma de aprovechar aquellas aplicaciones que tienen cierta limitación, las cuales cumpliendo ciertos requisitos pueden brindarse ante el usuario como parte de un sistema de información moderno. Como se dijo inicialmente, los sistemas computacionales pueden apoyar diversos procesos de la actividad humana, en los cuales la toma de decisiones no es excepción. En un proceso de descubrimiento de conocimiento se tiene como resultado información para realizar las mejores decisiones. Una de las estrategias más comunes utilizada en la toma de decisiones la realizan aquellas organizaciones que recolectan datos sobre sus actividades cotidianas; por ejemplo, sobre tratamientos clínicos o transacciones comerciales. Esta estrategia se llama minería de datos y con ella se obtiene conocimiento con el que se pueden sustentar las decisiones organizacionales. La institución interesada en una minería de datos debe ser capaz de recolectar los datos generados, así como de prepararlos, poner en marcha la minería de datos, evaluar sus resultados y determinar si el proceso debe repetirse con alguna corrección, o en su defecto, si el resultado se puede interpretar. Los resultados externan patrones que pueden ayudar a destacar reglas o
pronósticos sobre los entes cuyos datos fueron recolectados, es decir, conocimiento implícito en las actividades. Aunque se puede obtener conocimiento predecible, los hallazgos pueden ir más allá y llegar a brindar conocimiento sobre elementos d e los que ni se sospechaba su importancia dentro de las actividades cotidianas y sus eventos coyunturales asociados. Una aplicación de minería de datos particular es d d e r i v e , desarrollada por J.R. Argüello y S. Chakravarthy en 1996. Esta aplicación tiene el objetivo de mostrar cómo la teoría de la determinación de Argüello [ A R G U E ~se~ puede ] aplicar a la minería de datos, en la cual la aplicación práctica es generar árboles de inducción de decisiones de una forma incremental al explotar el procesamiento múltiple de su algoritmo. En términos más prácticos, la aplicación d d e r i v e es una herramienta que facilita el descubrimiento de conocimiento en grandes bases de datos. Esta aplicación tiene una limitación: necesita u n fuerte acoplamiento de infraestructura computacional mientras brinda procesamiento en paralelo en múltiples computadoras. Concretamente su procesamiento necesita que los datos de entrada, intermedios y de salida residan en un mismo sistema de archivos; de manera que todas las computadoras participantes en una minería de datos deben compartir u n mismo sistema de archivos. Además de lo anterior, el usuario de la minería de datos necesita realizar labores muy especializadas en forma no automatizada si desea que varias computadoras se involucren en el procesamiento de su tarea. Se da con ello u n problema de comodidad para el usuario encargado de la minería de datos que debe enfrentarse a la necesidad de encontrar pronto conocimiento útil para la toma de decisiones. Más técnicamente hablando, la complejidad de configurar y administrar el múltiple
procesamiento
es
proporcional
al
número
de
procesos
computacionales participantes en él. Este proyecto, llamado tdderive en honor a dderive y a su objetivo de brindar procesamiento paralelo, se relaciona con el estudio de cómo diseñar e implementar una solución moderna, de bajo acople en la infraestructura computacional y de administración de procesamiento transparente, a aplicaciones de procesamiento incremental, que definidas dentro de cierto enmarque tecnológico no pueden trascender sus aportes que han justificado muchos años de esfuerzo en su desarrollo.
1.1 EL PROYECTO tdderive A finales de los años ochenta, los diseñadores de sistemas operativos y de aplicaciones, introdujeron plataformas de sistemas intermedios, middlewnre, para suplir las necesidades de intercomunicación y coexistencia entre aplicaciones, ubicadas en redes empresariales o redes multipropósito extensas
como
Internet,
para
así
compartir
distintos
recursos
computacionales [SEICM97]. Entre los recursos que las aplicaciones alcanzan por medio de la red, se encuentran los procesadores de computadoras remotas, recurso disponible para el procesamiento distribuido del trabajo de una aplicación [BLOOM92]. A partir de entonces, la rápida evolución de esta tecnología ha provocado un fuerte incremento en la demanda de aplicaciones distribuidas, que reúnan las condiciones apropiadas para la operación oportuna, de alto desempeño y disponibilidad, escalable, segura y confiable [GOSCI92]. En particular, t dder i ve provee a dder ive de características de distribución de procesamiento, transparencia de la distribución y tolerancia a fallos. Al
realizar esta propuesta se han considerado distintas opciones tecnológicas para sistemas intermedios, así se incluye la tecnología de monitoreo de procesamiento de transacciones (PTM), la teci~ología de invocación a procedimientos remotos sincrónicos (RPC), la tecnología orientada a mensajes (MOM) y la tecnología basada en facilitadores de solicitudes a objetos (ORB) [SEICM97]. Con todas estas opciones se pueden construir sistemas computacionales distribuidos capaces de trabajar como si fueran aplicaciones locales mientras trabajan en forma distribuida, asimismo con la capacidad de balancear la carga de procesamiento, mantener la disponibilidad, compartir recursos distribuidos, prevenir bloqueos indefinidos en la concurrencia y brindar protección y seguridad; factores que se encuentran ausentes en el diseño de los típicos sistemas centralizados [SEICM97]. Este proyecto muestra cómo unir ciertas tecnologías para construir aplicaciones distribuidas tales como t d d e r i v e , especialmente que permitan a aplicaciones de cómputo
incremental como
dde r i ve
aprovechar
los
recursos
de
procesamiento remoto de una forma inteligente y sin que se necesite la intervención humana.
1.1.1 Campo de estudio del proyecto Para la construcción de t d d e r i v e se ha seguido un procedimiento que involucra estudios sobre las áreas de descubrimiento de conocimiento y sistemas distribuidos, así como una exploración a tecnologías de sistemas intermedios con las que generalmente se implantan aplicaciones distribuidas débilmente acopladas.
Ciencias de la computación Tecnología de bases de datos Aprendizaje de máquinas Minería de datos -
-
%k
-
Sistemas distribuidos
Figzr rn 1.1 Cnmpos de estudio mhs relevnntes asocindos con el presente proyecto. En la construcción de un sistema de servicios moderno muchas disciplinas pueden resultar involucradas y es por este hecho que el proyecto t d d e r i v e directamente puede interesar a aquellas personas que están continua o latentemente inrnersas en campos como el aprendizaje de máquinas, las bases de datos, la estadística, la distribución de procesamiento y la visualización de datos distribuidos, especialmente si su punto de vista se enfoca en el estado de la práctica de sus disciplinas respectivas. Todos esos campos intervienen en el desarrollo de t d d e r i v e , sin embargo se han enfatizado las áreas de los sistemas distribuidos y de la minería de datos (puestos en el primer plano de la figura y más resaltados que los otros) teniendo en cuenta que la profundización en otros campos, como el de la visualización, puede ser aplicada en proyectos posteriores.
1.1.2 Justificación del proyecto El proyecto es relevante debido al énfasis en la construcción de sistemas informáticos
distribuidos
y
no
tanto
en
sistemas
centralizados.
Particularmente, brinda una aplicación distribuida para la planificación de procesos computacionales, t dde r ive, que permite una mejor organización y control de los recursos computacionales que se emplean en la solución de un problema de descubrimiento de conocimiento, en un ambiente de computación colaborativa. Tal forma de organización estuvo fuera de los objetivos de la aplicación de minería d d e r i v e , y a partir de ahora el despliegue de t d d e r i v e no solamente es capaz de acoger y beneficiar al procesamiento distribuido controlado de d d e r i v e , sino que es capaz de extenderse para otros procesamientos computacionales similares.
1.2 OBJETIVOS DEL PROYECTO El objetivo general que el proyecto se propone alcanzar es el siguiente: Construir una herramienta distribuida débilmente acoplada que utilice la aplicación d d e r i v e para el descubrimiento de conocimiento. Esta aplicación ha de llamarse t dde r i v e . Más concretamente se tienen los siguientes objetivos específicos. 1. Diseñar e implementar la aplicación t d d e r i v e , que debe tener las
siguientes características: (a) Proveer la íuncionalidad de la aplicación dde ri ve (b) Distribuir la carga de trabajo en forma automática entre diferentes procesadores. (c) Ofrecer tolerancia a fallas y recuperación de consistencia. (d) Brindar transparencia de la distribución ante el usuario. (e) Soportar procesamiento distribuido en distintos sistemas operativos.
(f) Basar la comunicación en canales de transferencia de mensajes sincrónicos, asincrónicos e invocación a procedimientos remotos. 2. Producir u n documento sobre cómo se construyó el sistema distribuido t dde r i v e partiendo de la aplicación dde r i v e .
El segundo objetivo específico puntualizado se plasma con el presente documento.
1.3 ALCANCES Y LIMITACIONES Desde una perspectiva gerencial, es deseable la aplicación de herramientas de minería de datos como d d e r i v e , específicamente en el ámbito de la investigación institucional. El problema se concentra en brindar a d d e r i v e una mejor organización en su procesamiento con el empleo de t d d e r i v e y de esta forma lograr alcanzar las características de distribución computacional propuestas como objetivo. Así, t c i d e r i v e se concibe como una herramienta especializada en la distribución de la carga de trabajo de la aplicación dde r ive. Concretamente, t d d e r i v e permite que la aplicación pueda funcionar en forma distribuida de
una forma "inteligente", de manera que se aprovechen automatizadamente los procesadores de otras computadoras. El despliegue del programa tdderive se limita a una plataforma de hardware y software débilmente acoplados, es decir, sobre u n sistema de computadoras de propósito general, independientes y conectadas en red, con la capacidad de interactuar y compartir recursos utilizando los sistemas operativos Microsoft Windozos 2000, Linux y Solaris. Esto deja fuera de consideración sistemas computacionales más especializados y exclusivos.
La funcionalidad de t d d e r i v e , al igual que lo hace d d e r i v e , respeta la estrategia de descubrimiento de conocimiento conocida como árboles de inducción, implantada por Ronald Argüello y Sharma Chakravarthy
[ARGUE~B] .
1.4 ACERCA DE ESTE DOCUMENTO Este documento describe el sistema t d d e r i v e y presenta el procedimiento utilizado para desarrollarlo como la solución a los problemas de d d e r i v e . Se pretende que al final el lector comprenda el método de construcción de t dde r i v e , conozca la confomación del sistema, aprenda cómo evaluarlo y
pueda extraer material que le sirva en proyectos similares.
2 Metodología empleada en el
desarrollo del proyecto El proceso de investigación del proyecto siguió las recomendaciones
planteadas en su propuesta, mas, como es natural, especialmente durante la evolución de un estudio deductivo, se encontraron necesidades de conocimiento que no fueron anticipadas y que motivaron la ampliación de los temas de investigación y la modificación de la metodología, la cual se puntualiza en este capítulo. Se elaboraron los siguientes procedimientos: 1. Método del estudio del dominio de conocimiento 2. Método de la formulación del problema 3. Método del diseño
4. Método de implementación 5. Método de pruebas
A continuación se describe cada uno de estos procedimientos, sus relaciones
y la forma en que se aplicaron.
2.1 MÉTODO DEL
ESTUDIO DEL DOMINIO DE CONOCIMIENTO
En el estudio del problema y su solución, debe centrarse un proceso deductivo que lleve a la descripción de los detalles concretos de sus partes y a la descripción del dominio de conocimiento en el que ambos se enmarcan. Este procedimiento tiene dos partes, una teórica y otra práctica que le complementa; su objetivo es brindar el conocimiento básico para tratar el
2 Metodología empleada
eii
el desarrollo del proyecto 11
problema y dar con su solución.
2.1.1 Parte teórica La parte teórica de este método enfoca los contextos correspondientes de las aplicaciones d d e r i v e , y t d d e r i v e , específicamente, la minería de datos y los sistemas distribuidos. El estudio en ambos contextos empieza de lo general y se profundiza progresivamente. El primer asunto por resolver es comprender la aplicación d d e r i v e . Los ejes sobre los cuales su profundización teórica camina son el entendimiento de los algoritmos y las estructuras utilizados en la minería de datos en general y las necesidades de distribución que éstos presentan y que permitirán delimitar las características de dde r i v e y definir las responsabilidades de t dde r i v e . Mientras se está realizando el estudio de minería de datos se puede empezar a realizar el que corresponde a los sistemas distribuidos. El tratamiento de este segundo tema no debe profundizarse hasta conocer las necesidades de distribución de dde r i ve, las cuales se concretan una vez que el problema ha sido formulado, pero sí necesita el complemento de la parte práctica para explorar los sistemas intermedios que permiten la computación colaborativa, e identificar tanto características que se pueden aprovechar en la solución como problemas que deben enfrentarse en su consecución.
2.1.2 Parte práctica Concretamente, la parte práctica tiene el objetivo de obtener conocimiento capaz de alimentar el diseño e implementación futuros del proyecto, así como de complementar el contexto teórico con problemas concretos, sin estar directamente relacionados con la solución de t dde r i v e , sino más bien con la
2 Metodología empleada cii el desarrollo del proyecto 12
concreción del contexto de los sistemas intermedios o middlewtrre. Se deben explorar varias vías para la implementación de computación colaborativa mediante el desarrollo de ejemplos básicos de concurrencia, hilos, sincronización, comunicación entre procesos locales y remotos y su conectividad y trabajo en paralelo, tanto en plataformas POSIX (por ejemplo, Linux u otros basados en U N I X ) como en Micvosofi Windows. Es importante modularizar las funciones, clases o componentes que se necesitan en estos ejemplos. Además deben depurarse los programas en sus correspondientes plataformas, sea en ambientes POSIX o Micvosoft Witzdows, sea en escenarios de procesamiento computacional centralizados o distribuidos. Esto permitirá la identificación de diferencias en las distintas situaciones, lo cual ayudará en las decisiones del diseño del sistema y en la selección de los recursos para su construcción.
2.2 MÉTODO DE LA F O R M U L A C I ~ NDEL
PROBLEMA
Con el objetivo de delimitar el problema y formularlo junto con su solución se ha seguido un procedimiento que consta de diagnosticar dderive y recolectar y analizar soluciones a problemas similares. Este método complementa el estudio del dominio del conocimiento, pues permite enfocar los estudios sobre problemas que alguien más ha tratado y que deben enfrentarse en el desarrollo del proyecto. Debe llegarse a:
+ Comprender el contexto en el que un usuario final utiliza al sistema dderive. +
Identificar el modelo matemático de dde r i ve, particularmente sus estructuras y algoritmos.
2 Metodología e m p l e a d a eii el desarrollo del proyecto 13
+ Analizar la implementación de la aplicación dderive y el empleo que la misma hace de los recursos computacionales. +
Identificar las características que dderive otorga a su usuario final.
Esta labor implica el uso de la aplicación clder i VP y la ejecución de varias de sus funciones y observar sus resultados, tanto los que percibe el usuario, así como los efectos sobre los recursos computacionales. En todo caso, se pretende encontrar problemas en el uso de los recursos computacionales e inconvenientes para el usuario cuando se desea aprovechar el múltiple procesamiento. Así, los objetivos del proyecto, presentados
en la
introducción, se justificarán con los inconvenientes que se encuentren en (siderive.
Para la mejor comprensión del problema deben incorporarse a este procedimiento los resultados del estudio del dominio de conocimiento, se espera el surgimiento de necesidades de exploración y de conocimiento más concretas. De esta forma se progresará en la identificación de los problemas y en el tratamiento que les corresponde. Esta búsqueda de soluciones no deberá ser exhaustiva, lo cual no debe significar que tdderive deba ser capaz de regirse solamente por una estrategia de solución única. Los métodos de diseño e implementación deben permitir que tdderive sea lo suficientemente flexible como para que posteriormente se implementen otras soluciones.
2.3 MÉTODO DE DISEÑO El diseño de tdderive incorpora la solución a varios problemas especializados y por ello se prevé que el sistema tenga que integrar muchos
2 Metodología empleada en el desarrollo del proyccto 14
componentes con distintos objetivos. Debido a ello se debe emplear una representación de diseño que permita ver al sistema completo y que permita ver el detalle de cualquiera de sus componentes, incluyendo sus interacciones cuando cualquier función del sistema esté en marcha. Esta representación debe ser apoyada por una estructura de documentación que permita especificar los recursos de cada componente. Luego de hallar una forma de representarlo, el diseño se debe enmarcar dentro las decisiones de la formulación del problema. Cada componente que se obtenga debe especificarse así como las asociaciones e interacciones entre ellos. Esta conformación de componentes y relaciones debe aprovechar la existencia de patrones que hayan sido utilizados para resolver problemas de diseño similares. Específicamente, deben encontrarse patrones bien documentados y adaptarlos al contexto de t dderive . Esto no quiere decir que todo componente debe derivarse del estudio de los patrones, en su lugar, la intención es que los patrones ayuden a aclarar las relaciones y colaboraciones entre los diferentes componentes del sistema.
2.4 MÉTODO
DE IMPLEMENTACI~N
El proceso de implementación debe iniciar una vez que el diseño de una parte integral o módulo de tdderive haya sido concluido. Más específicamente, debe empezarse en aquella parte del sistema cuyo detalle esté completamente definido, así como el de las interfaces de sus componentes asociados. Además se requiere que las bibliotecas de software que se empleen se adquieran sin costo alguno y que cuenten con la respectiva documentación y tutoriales.
2 Metodología empleada cii el desarrollo del proyecto 15
Al iniciar la programación de un componente de t d d e r i v e , cada uno de sus recursos debe ser documentado, y se debe obtener, al final de la programación del sistema, un solo documento que reúna la especificación de todos los componentes. En la propia actividad de programación se deben emplear al máximo los recursos estándar que brinda el ambiente de programación, como por ejemplo contenedores, estructuras de búsqueda, estructuras de múltiple asociación, etc. En la programación también debe tratarse de adaptar a los componentes de t d d e r i v e estrategias recomendadas en la documentación de los patrones de diseño o arquitectura. En la implementación deben proveerse facilidades para observar la ejecución del sistema y sus reacciones a distintos casos de prueba. La finalidad es permitir un seguimiento controlado del comportamiento para el cual el sistema distribuido ha sido diseñado e implementado. Cada uno de los módulos con los que se ha construido t d d e r i v e debe ser documentado, indicando sus principales características de implementación, sus clases y los aspectos que pueden ser mejorados.
2.5 MÉTODO DE PRUEBAS El
procedimiento de pruebas
tiene
el
objetivo de comprobar
el
comportamiento del sistema distribuido t d d e r i v e como un ente íntegro en un ambiente de computación colaborativa. La aplicación de este método debe dar información a los investigadores para que t d d e r i v e pueda ser comparado con otros proyectos similares, incluyendo otras versiones de t d d e r i v e cuyos componentes incorporen otras soluciones a los problemas.
2 Metodología empleada e11el desarrollo del proyecto 16
Primero deben haber pruebas enfocadas por componente. Es así como antes de dar por terminada la programación de un componente debe comprobarse que sus funciones se brinden de manera correcta. Con este fin, aparte de las funciones especializadas hechas públicas a otros componentes de t d d e r i v e , un componente se debe estar claramente provisto de un recurso de pruebas que sea independiente de cualquier otro componente. Esta comprobación debe involucrar perturbaciones sobre el ambiente de computación colaborativa sobre el cual t d d e r i v e trabaja. Así como es necesaria una comprobación individualizada por componente, debe facilitarse la comprobación de las principales operaciones del sistema distribuido en conjunto, especialmente aquellas que se vinculan con los objetivos del proyecto. Esta verificación del comportamiento del sistema, particularmente sobre sus respuestas a distintos disturbios en su entorno de ejecución, debe ser apoyado por un mecanismo de bitácora que registre cómo han actuado sus componentes en conjunto, en distintos casos de prueba.
2.6 APLICACI~N DE LOS MÉTODOS El resto del documento describe el procedimiento del desarrollo del proyecto. Las siguientes secciones presentan cómo fue desarrollado cada método y el resto del documento presenta el detalle del resultado de cada uno de ellos.
2 Metodología empleada en el desarrollo del proyecto 17
2.6.1 Aplicación del método del estudio del dominio de
conocimiento 2.6.1.1 Realización de los estudios teóricos El proyecto se inició con un estudio comprensivo sobre el área del descubrimiento de conocimiento, colitemplando la minería de datos principalmente. La bibliografía de Mitchell, Berson y Smith, y Han y Kamber ([MITCH97], [BERSM97] y [HANKAOO] respectivamente), conformó el marco teórico propicio para fundamentar un estudio más avanzado sobre las estructuras y algoritmos de la aplicación dderive. Para comprender los detalles del procesamiento de esta aplicación se ampliaron detalles con la Teoría de la Determinación de J.R. Argüe110 ( [ A R G u E ~ ~y] )su explicación ), sobre extensiones a algoritmos d e árboles de decisión ( [ A R G u E ~ ~ ]lectura en la cual se expone el algoritmo que sigue dderive para realizar la minería de datos. Estas dos últimas lecturas sirvieron como base de la observación bajo la cual se somete dderive en el método de la formulación del problema. Paralelamente a este estudio deductivo, se inició un estudio general sobre el área de la computación colaborativa, con u n ligero enfoque sobre los sistemas distribuidos y más particularmente sobre aspectos generales de algunos objetivos que deben ser alcanzados por tdderive como sistema distribuido débilmente acoplado, entre los que se encuentran:
+ la transparencia en la distribución de los recursos coinputacionales;
+ la distribución dinámica, flexible y escalable del procesamiento; + la tolerancia a fallos y la recuperación de la consistencia. Bibliografía del Software Engineering Institute ([SEICM97]),
Tanenbaum
2 Metodología cmpleíida cn el desarrollo del proyecto 18
([TANEN96]), Coulouris, Dollimore y Kindberg ([CODOKOI]) y Bloomer ([BLOOM92]) no solamente ayudó la introducción de los temas anteriores sino que colaboró con su proíundización en el método de la formulación del problema. Como la variada bibliografía referenciaba diversos conceptos relacionados con sistemas distribuidos desde varios pmtos de vista, se necesitó encontrar una integración de conceptos, escenarios y problemáticas de implementación potenciales. Debido a ello se realizó un estudio comprensivo sobre sistemas distribuidos basado en el Modelo de Referencia para el Procesamiento Distribuido Abierto ([ISOIT95]),estándar internacional de OS1 que tiene el fin de ayudar a describir modelos de sistemas distribuidos, el cual explica a los desarrolladores las características y problemas que se pueden enfrentar al construir un sistema de procesamiento distribuido y las propiedades deseables que un sistema de este tipo debería reunir.
2.6.1.2 Exploración práctica realizada La exploración práctica inició probando software intermedio convencional de computación colaborativa sobre infraestructura computacional débilmente acoplada. Es así como se programó en C la mayor parte de la práctica recomendada por los Robbins ([ROBBI97]),la cual tiene el fin de explotar las funciones
de
concurrencia,
comunicación
y
control
de
procesos
computacionales que brindan los sistemas estándar POSIX. Al realizar experimentos de invocación a procedimientos remotos (RPC) se utilizó el libro de Bloomer ([BLOOM92]),que brinda una explicación más completa de la preparación de los ambientes computacionales que debe hacerse para RPC. Estas primeras exploraciones prácticas íueron realizadas en los laboratorios
2 Metodología empleada en el desarrollo dcl proyecto 19
de la Escuela de Ciencias de la Computación e Informática de la Universidad de Costa Rica (ECCI), sobre sistemas operativos Linrrx (computadora Orion) y Solaris (computadoras Sol y Mercurio). La cobertura de pruebas sobre sistemas operativos se abrió a Windows 2000 cuando por medio de wiízsockets se programaron sistemas de prueba concordantes con los estándares POSIX. Además se empezó a utilizar compiladores dedicados a la programación transportable, Cygu~iny Mingw32 para programar para Windou~s98 y 2000 lo mismo hecho para sistemas operativos POSIX. Luego el lenguaje de programación cambió a C++y se empezó a utilizar sus correspondientes bibliotecas para la programación transportable en los distintos sistemas operativos. La tecnología de comunicación de los primeros programas consistía en sockets, y luego se experimentó con CORBA, empleando específicamente MICO, para la invocación a métodos de objetos remotos. Al entrar en tecnología CORBA se descubrió la facilidad de brindar y administrar servicios por medio de objetos, de manera que se inició la exploración de esta técnica en Jnva. Se necesitó el apoyo de los dos tutoriales básicos del lenguaje Jnva brindados por sus proveedores oficiales y del libro de Lea ([LEAOl]), del cual se aprovechó la explicación de cómo crear y administrar
hilos
de
procesamiento
computacional
y
permitir
su
concurrencia. Java era u n lenguaje de programación que el desarrollador de este proyecto no conocía, así que construyó un módulo de contenedores protegidos para la concurrencia, los cuales se comportaban como las tablas del modelo relacional, el cual fue ampliamente probado y utilizado en los experimentos
2 Metodología empleada e11el desarrollo del proyecto 20
exploratorios. Este primer proyecto de Jnvn se desarrolló sobre u n sistema Windows 98 y fue puesto en marcha sobre los sistemas Windows 2000 y Linux de la ECCI sin ningún problema. No fue posible realizar esta exploración en las máquinas Solaris porque su software no estaba actualizado. Con la ayuda de los manuales de Sun Microsysterns ([SUNMI99a] y [SUNMI99b]), se hicieron experimentos de computación colaborativa en Java que utilizaban sockets, invocación a métodos de objetos remotos (RMI), e invocación a objetos nativos (JNI). Estos programas se probaron en las plataformas Windows 98 y 2000 y Linux. Luego de terminar los pequeños proyectos de computación colaborativa en Javn, se dio por terminada la fase exploratoria por los leguajes de programación y el middleware que tenían disponible. Hizo falta explorar la tecnología .Net, conocimiento de la cual en esos tiempos no era suficientemente difundido ni sus herramientas fácilmente disponibles.
2.6.2 Avlicación del método de la formulación del vroblema El método de estudio del dominio de conocimiento sirvió de insumo para analizar la aplicación dderive desde los puntos de vista matemático y computacional, así como también las interacciones con los usuarios y los recursos computacionales cuando la aplicación se ejecuta de manera aislada y en múltiple procesamiento. Se identificaron sus principales funciones, su composición y las interacciones entre los componentes que la articulan. Estas observaciones, entre otras, se analizan en el capítulo 3 de este documento.
A partir de tal análisis se identificaron los problemas de dderive y, al
2 Metodología empleada en el desarrollo del proyecto 21
mismo tiempo, las características y propiedades que se pueden aprovechar en la búsqueda de una solución. Estos resultados confirman la necesidad de construir t d d e r i v e para resolver sus problemas, entre los que se destacan: la
ausencia de la
administración automatizada de
recursos,
específicamente la de procesamiento computacional; la ausencia de transparencia ante el usuario del procesamiento múltiple; y la falta de mecanismos que permitan la provisión confiable del servicio de minería de datos. El estudio complementario sobre el área de sistemas distribuidos se canalizó en esas tres vertientes, y el trabajo de Goscinski ([GOSCI92]) resultó fundamental para iniciar y avanzar en la profundización de cada una de ellas. Su trabajo permitió reconocer los recursos que se debían administrar y dio luz sobre varias formas de lograrlo de manera transparente y confiable, las cuales llevaron a los estudios de Willebeek-Lemair y Reeves que se concentraban en técnicas generales para el balance de carga dinámico y su composición ([WILRE93]), que a su vez llevaron a los estudios de Hui y Chanson sobre modelos para implementar el balance de carga y recomendaciones para favorecer tales implementaciones en ambientes heterogéneos ([HUICH96], [HUICH99a]y [HUICH99b]). El trabajo teórico de Goscinski también llevó a la profundización del conocimiento sobre cómo se conforma un sistema distribuido consistente y confiable, y en esta vertiente se llegó al trabajo de 0szu ([oszuM~~]),sobre técnicas de confiabilidad en protocolos distribuidos, y se introdujo al trabajo de Colouris, Dollimore y Kindberg ([CODOKOI]),especializado en esquemas
2 Metodología empleada en el desarrollo del proyccto 22
de fallos y excepciones a nivel de comunicaciones. Estos estudios teóricos permitieron hallar soluciones concretas a los problemas señalados, así como conocimiento sobre otros todavía más concretos. Algunas de estas aplicaciones han sido descritas por los mismos autores, tales como BALANCE, UTOPIA, NEST y V-system ([HUCCL95], [ZZHWD93] y [GOSCI92]), y ayudaron a enmarcar y a expresar los problemas de dder i v e y su solución t dde r ive.Así mismo se aprovechó un estudio sobre patrones ampliamente utilizados para resolver concurrencia y relaciones entre objetos distribuidos en una red, basado en el trabajo de Schmidt, Stal, Rohnert y Buschmann ([SCSRBOO]).Todo este material fue utilizado para formular la solución al problema, la cual se brinda en el capítulo 3 de este documento.
2.6.3 Aplicación del método de diseño Por ser promovido por la comunidad de desarrolladores de software como un lenguaje estándar completo, se seleccionó a UML como el lenguaje de representación del diseño de t dde r ive. Se aprovechó la explicación de Fowler ([FOWLE99]) para aprender a hacer diagramas de clases, de interacción, de estados y de actividades. El diseño incorporó también, en su expresión, modelos relacionales para definir los objetos persistentes y modelos de capas para mostrar la relación entre los módulos de t dde r i ve. En el diseño se agruparon por función los problemas por resolver. Se encontraron estos tres grandes grupos funcionales: provisión de comunicaciones; administración distribuida de procesos; y
2 Metodología empleada en el desarrollo del proyecto 23
provisión de aplicaciones o servicios. El diseño de cada uno de esos grupos se encargó de resolver sus problemas específicos y siguió un proceso iterativo y gradual. En la elaboración del diseño se aplicó la orientación a objetos y se utilizaron varios patrones que fueron adaptados a los problemas particulares de tdderive. Cuando se alcanzó la solidez del diseño de cada componente de tdderive, es decir cuando el diseño propio y el de las otras partes relacionadas estaba concluido, se procedió a su implementación. El diseño fundamental del sistema se presenta en el capítulo 4 y sus cuatro capítulos siguientes exponen su detalle. El primer grupo funcional que se resolvió fue el de la provisión de comunicaciones. En su elaboración se utilizaron los patrones de eventos Aceptndor-Conectov y de concurrencia Objeto Activo, recolectados, especificados y explicados por Schmidt, Stal, Rohnert y Buschrnann ([SCSRBOO]), y el modelo de excepciones recomendado por Colouris, Dollimore y Kindberg ([CODOKOI]). Luego se diseñaron los grupos funcionales de administración y provisión de servicios, para los cuales se utilizó el texto de Goscinski ([GOSCI92])como base para obtener sus componentes y las responsabilidades de éstos. Otros varios textos se utilizaron para diseñar problemas específicos, referencia de los cuales se hace en la documentación del diseño.
2.6.4 Aplicación del método de implementación Como varias iteraciones del proyecto involucraron implementación luego de la verificación del diseño de sus componentes, el progreso de su construcción
2 Metodología empleada en el desarrollo del proyecto 24
involucró activamente una herramienta de software, llamada Eclipse, que se combinó con el lenguaje Jnva y cuyo resultado organizó los módulos del proyecto y sus recursos de tal forma que sus especificaciones y esquemas estuvieron a mano y siempre actualizados. Así mismo, esta herramienta garantizó que cada cambio posterior que fuese hecho a un módulo de una iteración tempranera, se desencadenara hacia los módulos de las demás iteraciones. Esta herramienta permitió que el diseño se mantuviera actualizado, dinámico y controlado. En el capítulo 9 de este documento se describen los aspectos más destacados de la
implementación, desde la
disposición de procesos e hilos
computacionales hasta la descripción de cada módulo de tdderive y los problemas encontrados en su implementación.
2 Metodología empleada en el dc5arrollo del proyecto 25
rograma nicla inicio ermina inicio nicia final ermina final ecibe solicitud tarea: ecibe subtrabajo a planificar: : ecibe subtrabajo terminado: : ecibe subtrabajo sigue vivo: : lmacena conexión: uerto:
alaiiceador uerto: oiitrolador ivide y obtiene riuevo subtrabajo: : ne subtrabajos: íidTarea> rra unión de subtrabajos: esalmacena conexióri: ermina y devuelve archivo de salida: cidTarea> .ermina sin archivo de salida: laiiificador etiene subtrabajo: : jecuta subtrabajo: : ndica subtrabajo sigue vivo: : xporta hacia: subtrabajo: : orioce vecino::: ector ctiva planificación
E5
E
Figura 2.1: componentes que genernn registros de bitíícorn y sus eventos
2.6.5 Aplicación del método de pruebas Conforme se construía cada módulo, se programó una clase llamada P r u e b a s , la cual sirve para probar los recursos del módulo y su interacción
con otros módulos asociados. En cada módulo, cada método estático de esta clase contenía la prueba sobre una o varias funcionalidades y se trató de preservarlas y evitar su borrado.
2 Metodología empleada en el desarrollo del proyecto 26
Con el fin de comprobar que el sistema cumple con sus objetivos y para darle seguimiento a su comportamiento, se programó, para cada evento importante del sistema distribuido, una descarga en una bitácora centralizada. El servicio de bitácora es independiente de los servidores t dde r ive.
2.6.5.1 Acciones registradas en la bitácora de tdderive La bitácora centralizada sigue la estructura descrita a continuación. Los eventos que se registran en ella se resumen en la figura 2.1. Todas las indicaciones utilizan el formato:
en el cual, los dos primeros componentes indican la fecha y la hora en que la acción se reportó al servicio de bitácora. En el tercero va el nombre del objeto responsable y en el cuarto una breve descripción de la acción. Como la bitácora es centralizada, el tercer componente incluye el alias del servidor t dde r ive al cual le corresponde la acción que se puntualiza.
Las siguientes acciones se comunican al servicio de bitácora.
Inicio del sistema Esta acción se indica cuando se inicia la ejecución de un servidor de t dderive en un nodo. La fase de inicio involucra dos acciones relacionadas
inás que también se registran en bitácora: cuando el inicio falla y cuando el inicio termina. En la bitácora se escribe lo siguiente, dependiendo del evento: ;;nombreservidor(programa);inicia inicio ;;nombceservidor(programa);erra inicio < f e c h a > ; < h o r a > ; n o m b r e s e r v i d o r ( p r o g r a m d ) ; e r m i n a inicio
Al inicio también se indica en la bitácora cuales puertos corresponden al
2 Metodología empleada
eii
el de5arrollo del proyecto 27
componente despachador y al componente balanceador. ;;nombreservidor(despachador);puerto:;;nombreservidor(programa);ncafinal ;;nombreservidor(programa);termina final
Recepción de un trabajo por parte del usuario Cuando tdderive recibe la solicitud de un trabajo encargado por u n usuario, esta acción se registra en la bitácora con la siguiente información: ;;nombreservidor(despachador);recibe solicitud
tarea:
donde i d T d r e a corresponde a la identificación de la tarea asignada por la instancia de t dde r i v e que atendió la solicitud.
División de una tarea y obtención de sus subtrabajos La bitácora recibe registros de la siguiente especie cuando una tarea es dividida en subtrabajos: ;;nombreservidor(controlador);divide y obtiene nuevo subtrabajo::
donde idSubt r a b a j o es la identificación del subtrabajo. Este registro se escribe por cada subtrabajo creado.
2 Metodología empleada en el desarrollo del proyecto 28
Unión de resultados de subtrabajos y conformación de la respuesta Cuando en una instancia de tdderive u n subtrabajo es unido a los demás subtrabajos con los cuales va a conformar una respuesta, se indica lo siguiente en la bitácora.
Si ocurre u n error en la unión, escribe ;;nomb~-eservido ( c o t r o a d o r )e r r a unión de subtrabajos:
Almacenamiento y desalmacenamiento de la conexión con el programa usuario Al recibirse la solicitud de una tarea por parte del usuario, se registra lo siguiente en la bitácora:
Cuando se desalmacena la conexión con el usuario que solicitó una tarea, para utilizarla como canal del envío de la respuesta al usuario, se agrega a la bitácora el siguiente registro:
Recepción de un subtrabajo para planificar su ejecución Cuando una instancia de tdderive recibe la migración de u n subtrabajo proveniente de otra instancia, escribe lo siguiente en la bitácora: ;;nombreservidor(despachador);recibe subtrabajo a
planificar::
2 Metodología empleada en el desarrollo del proyecto 29
Inicio de la ejecución de un subtrabajo Cada vez que en una instancia de t d d e r i v e se inicia la ejecución de u n subtrabajo, a la bitácora entra u n registro con el siguiente formato: ;;nombr-eservidor(planificador);e] ecuta
subtrabajo: AIIKOLTD txt
(d) 51 no fuiicioiia, qecute el siguiente comaiido de Wlnrlorc5 o su equivalente en sistemas POSIX for "O" in (IIESULTADOS\*) d o priiitdt "ov >> AIIBOLTD tut 7 Abra y observe los archivos DIRDD/AKBOLDDtxt DIIICLI/ARBOLTD txt para la comparación de resultados
y
(a) Verifique que la raíl del archivo AIiKOLDD txt esté presente en el archivo AIIBOLTD txt (b) En el archivo AIIKOLDD, para cada subárbol quc parta dc la rai/
identificada previamente, realice lo siguiente Busque que haya un subárbol semejante en el archivo AIIKOLTD Iievise q u las ~ relaciones padre-hijo de cada nodo de AIIBOLDD esté eii AIIBOLTD (c) Si en el paso 7 c no se eiicontraroti difereiicias o faltantcs el árbol que form0 tdderlve es el mismo generado por dderlve 8. Fin.
2.6.6 Casos de prueba Los siguientes casos de prueba siguen la configuración que se muestra en el anexo
G.
En
esta
configuración,
particularmente
la
del
archivo
admin g 1oba 1 .xml se declara un sistema de colaboración que consiste de 8 servidores t d d e r i v e que trabajan en dos computadoras cuyos 113s son 192.168.0.4 (siete servidores) y 192.168.0.1 (un servidor).
'-1
Figtirn 2.2 Topologín del sistemn distribtrido emplmdo en los cnsos de przrebn
2 Metodología e m p l c a d a en el dcsarrollo del proyecto 36
La configuración de los casos de prueba utiliza la topología de servidores de la figura 2.2. En estos casos de prueba los servidores t d . 1 y t d . 6 se utilizan como coordinadores de trabajos, ambos trabajan en distintos sistemas operativos: t d . 1 en una computadora WindowsXP sobre lntel Pentium L? y t d .6 en una computadora Linux sobre Pentiurn II.
A continuación se presentan los experimentos que se utilizan para comprobar si el sistema implementado cumple con los objetivos planteados. Cada experimento usa uno o dos trabajos de minería de datos. La minería de datos sobre la tabla tenis.data es llamada trabajo 1 y la minería de datos sobre la tabla zoo.data se llama trabajo 2. Los árboles que la minería de datos debe generar se presentan en el anexo G. En este anexo también se presentan los guiones que activan cada programa, sea cliente, servidor de bitácoras o servidor del sistema distribuido.
Experimento 1: Un trabaio con un servidor Descripción del experimento Este experimento presenta las interacciones más simples del sistema distribuido, en el cual un servidor debe resolver solamente un trabajo. Además se comprueban algunos objetivos específicos del proyecto, a saber: Objetivo a comprobar
Comprobación
1.a I'roveer la funcionalidad d e dderlve
El archivo d e respuesta debe contener la descripción d e un Arbol d e decisiones
1.d Brindar transparencia d e la distribución ante el usuario
El usuario n o debe percibir que la respuesta tue procesada por un sistema distribuido, específicamente si trabajaron uno o más servidores.
Protocolo del experimento Para llevar a cabo el experimento se deben seguir los siguientes pasos. Todos
2 Metodología empleada en el desarrollo del proyecto 37
los guiones y archivos de configuración empleados en la comprobación se muestran en el anexo G. 1. Tniciar el servidor t d . 1 mediante la ejecución del guión t d. 1.b a t .
2. Iniciar el trabajo 1mediante la ejecución del guión c 1i en te . 1 .ba t.
Verificación de resultados del experimento Se debe verificar si el archivo resultante del experimento da como resultado el árbol del trabajo 1 presentado en el anexo G. En esta comparación debe ejecutarse el procedimiento del listado 2.6, a partir del paso 6.b. El resultado del experimento se presenta en el capítulo 10 y su bitácora se muesta en la sección H.1.
Exverimento 2: Un trabaio con cuatro servidores Descripción del experimento Este experimento presenta las interacciones que cuatro servidores realizan para atender un Único trabajo de minería de datos. Se comprueban los siguientes objetivos específicos del proyecto: Objetivo a comprobar
Comprobación 1
1.a Proveer la funcionalidad d e dderive
El archivo d e respuesta debe contener la descripción d e un árbol d e decisiones.
1.b Distribuir la carga d e trabajo en forma automática entre diferentes procesadores
En la bitácora se debe notar la participación d e varios servidores intercambiándose subtrabajos automáticamente.
1.d Brindar transparencia d e la distribución ante el usuario
El usuario no debe percibir que la respuesta fue procesada por un sistema distribuido, específicamente si trabajaron uno o más servidores.
1.f Basar la comunicación en canales d e transferencia d e mensajes sincrónicos, asincrónicos e invocación a
En la bitácora s e debe observar la comunicación asincrónica, cuando los servidores no esperan por respuestas, sino que siguen su marcha d e manera 1
-
2 Metodología empleada eti el desarrollo del proyecto 38
procedimientos remotos
independiente. Además, en la bitácora debe observarse la comunicación sincrónica cuando el cliente espera la respuesta del servidor.
Protocolo del experimento Para llevar a cabo el experimento se deben seguir los siguientes pasos. Todos los guiones y archivos de configuración empleados en la comprobación se
muestran en el anexo G. 1. Iniciar el servidor t d . 1 mediante la ejecución del guión t d . 1.ba t.
2. Iniciar el servidor t d . 2 mediante la ejecución del guión t d . 2 .b a t . 3. Iniciar el servidor t d . 3 mediante la ejecución del guión t d . 3 .b a t . 4. Iniciar el servidor t d . 6 mediante la ejecución del guión t d . 6 .b a t .
5. Iniciar el trabajo 1mediante la ejecución del guión c ? i ent e . 1 .ba c .
Verificación de resultados del experimento Se debe verificar si el archivo resultante del experimento da como resultado el árbol del trabajo 1 presentado en el anexo G. En esta comparación debe ejecutarse el procedimiento del listado 2.6, a partir del paso 6.b. Además, los resultados se pueden comparar contra los resultados obtenidos en el experimento 1. En la bitácora deben observarse las interacciones entre los componentes del sistema distribuido. El resultado del experimento se presenta en el capítulo 10 y su bitácora se muesta en la sección H.2.
Experimento 3: Un trabaio erróneo con dos servidores Descripción del experimento Este experimento presenta dos servidores que deben resolver un trabajo
2 Metodología empleada e11el desarrollo del proyccto 39
erróneo y uno válido. Objetivo a comprobar
Comprobación
1.c Ofrecer tolerancia a fallas y recuperación d e consistencia
El usuario debe recibir como respuesta un archivo indicando error y el sistema distriubido sigue trabajando sin sufrir por el problema.
Protocolo del experimento Para llevar a cabo el experimento se deben seguir los siguientes pasos. Todos los guiones y archivos de configuración empleados en la comprobación se muestran en el anexo G. 1. Iniciar el servidor t d . 1 mediante la ejecución del guión t d . 1.ba t 2. Iniciar el servidor t d . 6 mediante la ejecución del guión t d . 6 .ba t. 3. Iniciar el trabajo E mediante la ejecución del guión cl i e n t e . e .b a t . 4. Lniciar el trabajo 1 mediante la ejecución del guión c 1i en t e . 1.ba t .
Verificación de resultados del experimento Deben haber dos archivos comprimidos: RESULTADO.ZIP y RESULTADO.ZIP, donde es la hora en que se solicitó el trabajo. Uno de ellos contiene un archivo indicando error y el otro tiene un resultado que se puede revisar como se hace en el experimento 2. El resultado del experimento se presenta en el capítulo 10 y su bitácora se muesta en la sección H.3.
Experimento 4: Seis trabaios con ocho servidores Descripción del experimento Este experimento presenta las interacciones que ocho servidores llevan a cabo
2 Metodología empleada e11el desarrollo del proyecto 40
para resolver seis trabajos. Objetivo a comprobar
Comprobación
1.a Proveer la funcionalidad d e dderive
Los archivos d e respuesta deben contener la descripción d e los árbol d e decisión respectivos.
1 b Distribuir la carga d e trabajo en forma automática entre diferentes procesa dores
En la bitjcora se debe indicar la participación d e varios servidores y su intercambio automático d e subtrabajos 1
1.d Brindar transparencia d e la distribución ante el usuario 1.f Basar la comunicación en canales d e transferencia d e mensajes sincrónicos, asincrónicos e invocación a y rocedimientos remotos
El usuario no debe percibir que las respuestas fueron procesadas por un sistema distribuido, específicamente si trabajaron uno o m i s servidores. En la bitácora débese observar la comunicacióii asincrónica, cuando los servidores no esperan por respuestas, sino que siguen su marcha d e manera independiente. Además, en la bitácora debe observarse la , comunicación sincrónica cuando el cliente espera la respuesta del servidor.
Protocolo del experimento Para llevar a cabo el experimento se deben seguir los siguientes pasos. Todos los guiones y archivos de configuración empleados en la comprobación se muestran en el anexo G. 1. Ejecutar los guiones t d . l . b a t , t d . 2 . b a t , t d . 3 . b a t , t d . 4 . b a t , t d . 5 . bat, t d . 6 . bat, t d . 7 . b a t
y
td. 8.bat.
2. Iniciar el trabajo 1 tres veces mediante la ejecución del guión
cliente. l . b a t . 3. Iniciar el trabajo 2 tres veces mediante la ejecución del guión
cliente.2 . bat:.
Verificación de resultados del experimento Se debe verificar si los seis archivos resultantes del experimento dan como
2 Metodología empleada cn el desarrollo del proyecto 41
resultado los árboles de los trabajos 1 y 2. En esta comparación debe ejecutarse el procedimiento del listado 2.6, a partir del paso 6.b. Además, los resultados se pueden comparar contra los resultados obtenidos en el experimento 1. En la bitácora deben observarse las interacciones entre los componentes del sistema distribuido. El resultado del experimento se presenta en el capítulo 10 y su bitácora se muesta en la sección H.4.
Experimento 5: Siete trabajos con ocho servidores y dos de ellos fuera repentinamente Descripción del experimento Este experimento contempla lo acaecido cuando el sistema distribuido atiende siete trabajos de minería de datos y ocurren fallas en dos de los ocho servidores que participan en la minería. Objetivo a comprobar
Comprobación
1 c Ofrecer tolerancia a fallas y recuperación d e consistencia
El usuario debe recibir como respuesta los respectivos archivos d e resultados d e las minerías d e datos. 1
1 .d Brindar transparencia d e la distribución ante el usuario
El usuario no debe percibir que las respuestas f u e r o n procesadas por u n sistema distribuido, específicamente si trabajaron uno o mhs servidores.
Protocolo del experimento Para llevar a cabo el experimento se deben seguir los siguientes pasos. Todos los guiones y archivos de configuración empleados en la comprobación se muestran en el anexo G. 1. Ejecutar los guioi-ies td. l.bat, td.l.bat, td. 3.bat, td. 4 .bat, td. 5.bat, td. 6.bat, td. 7 .bat y td. 8.bat.
2. Iniciar el trabajo 1 tres veces mediante la ejecución del guión
2 Metodología empleada en el desarrollo del proyecto 42
c l i e n t e . 1. b a t .
3. Iniciar el trabajo 2 tres veces mediante la ejecución del guión cliente. 2. bat.
4. Detener luego de cuatro minutos los servidores t d . 2 y t d. 8.
5. Iniciar el trabajo 1 mediante la ejecución del guión c 1i e n t e . 1 .ba t.
Verificación de resultados del experimento Debe verificarse si los siete archivos resultantes del experimento dan como resultado los árboles de los trabajos 1 y 2. En esta comparación debe ejecutarse el procedimiento del listado 2.6, a partir del paso 6.b. Además, los resultados se pueden comparar contra los resultados obtenidos en el experimento 1. En la bitácora deben observarse las interacciones entre los componentes del sistema distribuido. El resultado del experimento se presenta en el capítulo 10 y su bitácora se muesta en la sección H.5.
Experimento 6: Siete trabajos con ocho servidores y uno de ellos fuera temporalmente Descripción del experimento Este experimento enfoca el comportamiento del sistema cuando habiendo iniciado seis trabajos de minería de datos en ocho servidores participantes, uno de ellos falla y se reintegra al procesamiento de minería. -
Objetivo a comprobar
Comprobación
1.c Ofrecer tolerancia a fallas y recuperación d e consistencia
El servidor que queda fuera d e servicio se debe reintegrar a las planificaciones del sistema distribuido
1
2 Metodología empleada en el desarrollo del proyecto 43
Protocolo del experimento Para llevar a cabo el experimento se deben seguir los siguientes pasos. Todos los guiones y archivos de configuración empleados en la comprobación se muestran en el anexo G. 1. Ejecutar los guj.ones t d . l.bat, td.2.bat, td.3.bat, td.4.bat, td. 5 .bat,td. 6 .bat,td. 7 .bat
y td. 8 .bat.
2. Iniciar el trabajo 1 tres veces mediante la ejecución del guión
cliente. l.bat. 3. Iniciar el trabajo 2 tres veces mediante la ejecución del guión cliente. 2.bat.
4. Detener luego de cuatro minutos al servidor td. 3. 5. Ejecutar el guión td . 3 .ba t.
6. Ejecutar el guión cliente. 2 . bat.
Verificación de resultados del experimento Debe verificarse si los siete archivos resultantes del experimento dan como resultado los árboles de los trabajos 1 y 2. En esta comparación debe ejecutarse el procedimiento del listado 2.6, a partir del paso 6.b. Además, los resultados se pueden comparar contra los resultados obtenidos en el experimento 1. En la bitácora deben observarse las interacciones entre los componentes del sistema distribuido. El resultado del experimento se presenta en el capítulo 10 y su bitácora se muesta en la sección H.6.
3 Análisis del problema y su solución El principal objetivo del programa d d e r i v e es demostrar cómo se puede utilizar la teoría matemática de la determinación para generar, de manera incremental, árboles de decisión a partir de grandes colecciones de datos dispuestos tabularmente, favoreciéndose del múltiple procesamiento. Desde una perspectiva más práctica, d d e r i v e se encarga de descubrir patrones que guíen la toma de decisiones a partir de grandes cantidades de datos; esta responsabilidad es parte de todo un proceso de descubrimiento de conocimiento. El usuario final encuentra en d d e r i v e las siguientes funciones:
+ Generación de un árbol de inducción al emplear una de varias estrategias para la selección del mejor atributo: la determinación de primer y segundo orden, la entropía y el índice gini. + Información sobre el uso de d d e r i v e . + Generación de un árbol a partir de un proceso que organice el
multiprocesamiento. + Agregación
de
procesos
de
generación
de
árboles
para
el
multiprocesamiento local. Las dos últimas opciones, de bajo nivel, se necesitan para que un usuario logre el múltiple procesamiento. Si el usuario requiere que el múltiple procesamiento se realice en más de una computadora, éste necesita verificar si los datos están al alcance de las computadoras participantes, además de agregar los procesos computacionales de generación que desee en cada
3 Análisis del problema y su sol~ición 45
computadora. Una vista completa de las funciones de d d e r i v e se brinda en la figura 3.1.
I unciones rel.1cionad.i~ con 1.i minería dr d , i t < i ~
I
f o r r a r un .irbol d c deci-ión hinarlo utili/.indo particion d e di).
ví.i\
Indicar iin valor d e iorte p.ir.1 podar L Tur entropiu
-
cii
Iiigar d c dcterminaci¿>ii
Indicar nombre d e ard e cnir.ida
I s.ir el índice gini c n lugar del d e dctrrrn~nnciMlhillZblrepcprlnn
7 + n n m i ~ ~trrmur fi~ Y 2 W U'PUnifirn*vM
AI>MINMINAPPIIB~~-~~
ii
-,\l>Mtvwrbomqnuim
-'4Dhili\lAPPFu P o r q ~ u r i u i
-
-
-
-
1-. L -\h.--
-
-
-
--&q
13
$.WMINAPPISU~
-
~
PWrwf-~cn
ZDHIVPOI
t
I
1 /
I
~mna;
AuMIYPOLVdvradDl
-.
-
.
P~i11_Lmibrnlea hilil~ias
J
>W h U I A P P C u n P r u i h I%wu~ruprx,rn
4
-
=y
41)MIU\I~Plkrpchador
'a-1
bAl>hllYAPlVl~~ty~
II>MIVinwrpln i i m p q ~ ~ I i ~ a n ~ e U ~ n ~ P i
-F
rin25 # # # # # w 2 /
This 1s ignored, (end of codes) The next is a strirg variable w a r A substring from 2 to 3 of each string of lenght 4 is taken cf each value. If lenght is not equal 4 , nothing is done a r! 3 4
A Documentación del sistema de minería de datos ddcrivc 207
$ the atribute values are considered as floats and rounded to the nearest integer.
#n the attribute val~ues will be divided by 10 n (n=1,2,3). Missing values (0) are not recoded.
to
the
Every example inust dppedr witli ttie vdlues ln the order shown for the attribute names. So far, there 1s no option for default values or mlssing values. Each value is taken on its own. If you have a way to flnd out that a value 1S
mlssing i by form3t or by the use of separator between fields), take a look to the convert program. 3.
The induction mechanism.
The system employs a basic lnduction algori+hm similar to Quinlan's ID3 and provldes structures similar to Utgoff ' s ITI algorithm. The main procedures are derivation of the declsion tree, testlng or training the resultlng tree against test data ard tree reorganlzation. It can be used ~ncremental, derivlng the tree for a small set of data and then adding instantes (one or a few at the time) until the final tree for a whole set of data is found; hope with a minimum amount of work thanks to the reorganization procedure. It can be uspd non-incremental, derlvlng the decision tree for the whole input data file. A pruning method based on the determination criterion is implemented with the optlon P or by slmpLe evidence or support per class uslng the option E. Run the program with the only option -h to find out about other options. The ability of the determlnatlon criterion for selecting attributes and to extract meaningful decision trees was documented in ([Arguello, V6,95, 96, 97,951 ) .
In addition, the algorithm lncludes the posslbllity of
A Doc~imcntnci6ndcl 5i5tc.ma d e m~iicrínd e dato5 dderive 208
several processes (or processors ) cooperating in the induction task. It creates subfiles of the original input. file; those files are then used for other processes to induce the decision tree equivalently. ?hus, the nain process wiil have those decision trees ready to incorporate in
the original one. The general procedure
does the followinq:
1- Read lnput flle: count frequency of occurrence of every class value wlth every attribute value 2 - Apply range compresion where it was
specified. 3- Compute measures (determlnations) for every value and average those for every attrlbutc usin3 tke relative number of occurrences of every value w~th respect to the total. 4- Select the best attribute and split t,he inl:~:.;~
file accordingly, creating a subfile for every attribute value. Those subfiles can be processed for the same algorithm running concurrently 5- For every subfile that has nnt yet processfd, derive the subtree and a;tach to the root
selected. For processed flles, the algorithm will read t hem and attach to the tree flle when sailng or printlng
4.
out the decislon tree. The options for the programs.
4 .l.
The dderive program:
Use: dderive [ - [bdefghimrsuvwDFGTPSTVj j [-en. n! [-n99] [-pn] [-tn] [-En] [-Mn] [-T99991 [-f] where -h to display a
brief help.
-d: to debug, display more information for the programmer. Activates option -v. Default, no debuy. -e: to use entropy lnstead of deterrnlnatlon (default).
A Documentaciói~del sistema d t miticría de datos dderive 209
-1:
to see the lnput data prlnted out into the
screen. -S:
To save the tree ln output
file.
(same
name
of ~ n p u tfile wlth extension .dtf) -v:
to trace the process for the user v ~ s u a l ~ z a t ~ i ~ n
of ~ h a tis happening. Default, no trace.
-w: to display t.he tree into the
screen.
Default,
no display. -cn.n:
denote
to prune the tree when determination
1S
higher or equal to n.n
.
Default: 0.99
-pn: denote the process identification (n) for subfile generation. Must be unique for every process. -tn: for concurrent processes, the number of microseconds that the program must walt before checking the current directory for addltional Input data files. -ffilename:
fllename
1s the input data flle name.
1f
this 1s not specifled, the program assumes a multiprocess optioc, i.e., this process will run concurrently trying to tielp other similar process to solve the task. 4.2.
The dttest program:
Use: dttest [-h] fllename>] [-m] [-r]
cases flle>]
[-t is the test cases file. Fail cases will be left in a file with test f ilename and extension .fail and the tree when saved will be with extension .dtf The Reorganization program:
4.3.
Use: dtReor [-heswuvXMT] [-~99.91 sal~da.completa.uniforme.c~ord~nador.txt 2>&1 Ulstributed tree inductlon: v5.V (c) Jose R. Arguello,1996, 1997, 1998
[email protected] Limited version to 70 x 200 Estimated memory required : 40064000 locking: tenis.txt getname: file DLOOOO
Index: level: O =Observaclon, Vlsta- exterior, Temperatura, Humedad, Viento, * Jugar-tenls, Mask: 111111 Value list: 1 1 1 1 1 O ; Class: O Value list: 2 1 1 1 2 0 ; Class: O Value list: 3 2 1 1 1 1 ; Class: 1 Value list: 4 3 2 1 1 1 ; Class: 1 Value list: 5 3 3 2 1 1 ; Class: 1 Value llst: 6 3 3 2 2 O ; Class: O Value llst: 7 2 3 2 2 1 ; Class: 1 Value llst: 8 1 2 1 1 O ; Class: O Value list: 9 1 3 2 1 1 ; Class: 1 Value list: 10 3 2 í 1 1 ; Class: 1 Value list: 11 1 2 2 2 1 ; Class: 1 Value llst: 12 2 2 3 2 1 ; Class: 1 Value list: 13 2 1 2 1 1 ; Class: 1 Value list: 14 3 2 1 2 O ; Class: O Actual size: 1293 0, 5 ; 1, 9 ; # local classes: 2 Det: 0.444444: 1 Computing deter. for Tree O Best attribute Vista_-exterlor 0.555556 New Mask: 121111 getname: file DTOOOOOOO1 locking: DTOOOOOOOl getname: flle DL00000002 l o ~ k ~ n gDL00000002 : getname: file DTOOOOOOO3 locking: DT00000003 Reading Input . . writing subfile DTOOOOOOOl data:69: 1 1 1 1 1 10 char written flushlnq.. .writlng subfile DT30000001
H Dcpuraci6n en la salida del sistema dc minería de datos ddcr~ve 216
data:S2: 2 1 10 char written flushlng. . .writing subfile data: 95: 3 2 10 char written flushing.. .wrlting subfile data:10U: 4 3 10 char wrltten flushlng . . .writing subflle data:121: 5 3 10 char wrltten flushing. . .writing subflle data:134: 6 3 10 char wrltten flushing. . .writing subfile data:147: 7 2 10 char written flushlng . . .wrltlng subflle data:160: S 1 10 char written flushing.. .wrlting subfile data:173: 9 1 10 char wrltten flushlng.. .wrltlng subf lle data:lS6: 10 11 char written flushing.. .writing subfile data:200: 11 11 char wrltten flushing.. .writlng subflle data:214: 12 11 char written flushing.. .writing subfile data:228: 13 11 char written flushing.. .writing subfile data:242: 14 11 char written flushing.. unlockinq subflle tree DTOOOOOOOl unlocking : DT00000001.lck Computlng deter. for Tree 2 Leave : 1, 1 (4) unlocking subflle tree DL00000002 unlocking : DL00000002.lck
B Depuraci6n en la salida del sistema de mint,ria de datos dderive 217
unlocking subflle tlee DT00000003 unlocking : DT00000003.lck Reserving memory: 5997905 Accurn. size: 2092 locklng: DT00000003 Reading: 'DT00000003' Actual slze: 906 0, 2 ; 1, 3 ; # local classes: 2 Det: 0.333333: 1 Computlng deter. for Tree 3 Best attrlbute Viento 1 New Mask: 121121 getname: flle DL000000030001 locklng: DL000000030301 getname: file DL000300030002 locking: DL000000030002 Reading Input . . Index open . . wrlting subfile DL000000030001 data:l: 4 2 1 1 1 S char written flushing.. .wrltlng subfile DL000000030001 data:l: 5 3 2 1 1 S char written flushing.. .writing subfile DL000000030002 data:l: 6 3 2 2 O S char written flushlng.. .wrlting subfile DL000000030001 data:l: 10 2 2 1 1 9 char written flushing.. .writing subfile DLC~00000030002 data:l: 14 2 1 2 O 9 char written flushing.. Computing deter. for Tree 1 Leave : 1, 1 ( 3 ) unlocking subfile tree DL000000030001 unlocking : DL000000030001. lck Computing deter. for Tree 2 Leave : o, 1 (2)
unlocklng subfile tree DL000000030002 unlocklng : DL000000030002.lck Reservlng mernory: 2140020 Accum. size: 4152 Subtree a level: 1 Vientn, 1 (5) 1---[ 1, 1 ] --->Ir 1 (3)
B Depuracióii en la salida del sistema dc miiicria de datos ddcrivc 218
eot unlocking : DT00000003.lck Reserving memory: 5995818 Accum. size: 4152 locklng: DTOOOOOOOl DT0000000l.dtf already done! Subtree a level: O Vista-exterior, 0.555556 (14) - - - [ 1, 1 ] --->Dt Elle: DT00000001.dtf l 1---[ 2, 2 ] --->i, 1 (4)
eot unlocking : tenis.txt.lck Remaining files eop
El siguiente listado es la salida del proceso participante derivando el árbol de decisión con una distribución de probabilidad uniforme. S dderlve.exe -v -d - E -pool -1 -u -S > sal~da.completa.uniforme.participantel.tt 2>&1 Dlstributed tree ~nductlon: v5.S (c) Jose R. Arguello, 1996, 1997, 1998 ]
[email protected] Llmlted version to 70 x 200 Estimated memory required : 40064000 getname: file DLOOOO locking: DTOOOOOOOi DTOOOOOOOl
Index: DTOOOOOOOl level: O =Observacion, Temperatura, Humedad, Viento, *Jugar-tenis, Mask: 11111 Vaiue list: 1 1 1 1 O ; Class: O Value llst: 2 1 1 2 O ; Class: O Value list: 8 2 1 1 O ; Class: O Value list: 9 3 2 1 1 ; Class: 1 Value iist: 11 2 2 2 1 ; Class: i Actual size: 949 0, 3 ; 1, 2 ; # local classes: 2 Det: 0.333333: O Computing deter. for Tree 1 Best attrlbute Humedad 1 New Mask: 11211 getname: file DLOOOOOOOlOOO1 locking: D L O O O O O O O ~ O I I O ~ getname: flle DL000000010002
B Depuración en la salida del sistema de minería d e datos ddcrivc 219
locking: DL000000010002 Reading Input . . Index open . . Index eof . . wrlting subfile DLOOOOOOOlOOOl data:l: 1 1 1 1 0 S char wrltten flushing.. .wrltlng subfile DLOOOOOOOlOOOl data:l: 2 1 1 2 O V char written flushing.. .writing subfile DLOOOOOOOlOOOl data:l: U 2 1 1 0 S char wrltten flushlng.. .writing subfile UL030000010002 data:l: 9 3 2 1 1 S char wrltten flushing.. .writing subfile DL000000010002 data:l: 11 2 2 2 1 9 char written flushing.. Computing deter. for Tree 1 Leave : 0, 1 (3) unlocking subfile tree DLOOOOOOOlOOOl unlocking : DLO00000010001.lck Computing deter. for Tree 2 Leave : 1, 1 (2)
unlocking subfile tree DL000000010002 unlocking : DL00000C~O10002.lck Reserving memory: 5997569 Accum. size: 2131 Subtree a level: O Humedad, 1 (5) I---[ 1, 1 ] --->O, 1 (3) I
8
1---[
2, 2 ] --->1, 1 (2)
eot unlocking : DT00000001.lck Remalning files
Este proceso generó cinco archivos con el contenido mostrado por las figuras B.2, B.3, B.4, B.5 y B.6. Los primeros dos archivos fueron generados por el proceso participante (DL000000010001 y ~L000000010002).Los demás archivos fueron generados por el proceso coordinador.
R Depuración en la salida del cisterna de minería de datos dderivc 220
=Observaclon Temperatura Vlento *Jugar-tenis l 1 1 0 2 1 2 0 S 2 1 0
Figura B.2 Contenido de D L 0 0 0 0 0 0 3 1 0 0 0 1 .
=Observacion Temperatura Viento *Jugar-tenls 9 3 1 1 1 1 2 2 1
Figura B.3 Contenido de D L 0 0 0 0 0 0 0 1 0 0 0 2 .
-0bservacion Temperatura Humedad Vlento *Jugar-tenls 3 1 1 1 1 7 3 2 2 1 1 2 2 1 2 1 1 3 1 2 1 1
Figura B.4 Contenido de D L ~ 0 0 0 0 0 0 0 2 .
=Observacion Temperatura Humedad *Jugar-tenis 4 2 1 1 5 3 2 1 1 0 2 2 1
Figura B.5 Contenido de D L 0 0 0 0 0 0 0 3 0 0 0 1 .
=Observacion Temperatura Humedad *Jugar-tenis 6 3 2 0 1 4 2 1 0
Figura B.6 Contenido de DL0000 0 0 0 3 0 0 0 2 .
El siguiente listado es la salida del proceso coordinador en la derivación de un árbol de decisión utilizándolo con una determinación de primer orden. salida.completa.nou~~iforme.coordinador.txt2>&1 Distributed tree induction: v5.E ( c ) Jose R. hrguello, 1996, 1997, 1998
B DepuraciOii en la salida del sistema de minería de datos dderivc 221
Limlted version to 70 x 200 Estimated memory reqJired : 40064000 locking: tenis.txt getname: file DLOOOO Index: level: 0 =Observacion, Vista-exterior, Temperatura, Humedad, Viento, "Jugar-tenis, Mask: 111111 Value list: 1 1 1 1 1 0 ; Class: 0 Value llst: 2 1 1 1 2 O ; Class: 0 Value list: 3 2 1 1 1 1 ; Class: 1 Value list: 4 3 2 1 1 1 ; Class: 1 Value list: 5 3 3 2 1 1 ; Class: 1 Value llst: 6 3 3 2 2 O ; Class: 0 Value list: 7 2 3 2 2 1 ; Class: 1 Value llst: V 1 2 1 1 0 ; Class: 0 Value list: 9 1 3 2 1 1 ; Class: 1 Value list: 10 3 2 2 1 1 ; Class: 1 Value list: 11 1 2 2 2 1 ; Class: 1 Value 11st: 12 2 2 1 2 1 ; Class: 1 Value llst: 13 2 1 2 1 1 ; Class: 1 Value list: 14 3 2 1 2 0 ; Class: O Actual size: 1295 0, 5 ; 1, 9 ; # local classes: 2 Det: 0.444444: 1 Computlng deter. for Tree 0 Best attrlbute Humedad 0.541667 New Mask: 111211 getname: file DTOOOOOOO1 locking: DTOOOOOOOl getname: file DT00000002 locklng: DT00000002 Reading Input . . writlng s u b f ~ l eDTOCOOOOOl data:69: 1 1 L 1 1 10 char written flushing.. .writing subfile DTC~OOOOOOl data:82: 2 1 1 1 2 10 char written flushing.. .writing subfile DTC~OOOOOOl data:95: 3 2 1 1 1 10 char written flushing.. .writing cubflle DTOOOOOOOl 7 data:10V: 4 3 1 1 10 char wrltten flushing.. .wrlting subflle DT00000002 data:121: 5 3 3 2 1 10 char written flushing.. .writing subfile DT00000002 data:134: 6 3 3 2 2 10 char written flushing.. .writing subfile DT00000002 data:147: 7 2 3 2 2 1 10 char wrltten
H Depuracióii en la salida del sistema de minería de datos dderivc, 222
flushing.. .writing subfile data: 160: 5 1 10 char written flushing.. .writlng subflle data:173: 9 1 10 char written flushing.. .writing subfile data:156: 10 11 char written flushing.. .writing subfile data:200: 11 11 char written flushlng.. .wrltlng subfile data:214: 12 11 char written flushing.. .writing subfile data:228: 13 11 char written flushing.. .writlng subflle data:242: 14 11 char written flushing..
DTOOOO000l 2 1
1
0
DT00000002 3 2
1
1
DT00000002 3 2
2
1
DTOC~OOOOOl 2 2
1
2
DTOC1000002 2 1
2
1
DTOCOOOOOl 3 2
1
2
DT00000002 1 2
unlocking subflle tree DTOOOOOOOl unlocking : DTOOOO0OCl.lck unlocklng subfile tree DT00000002 unlocking : DTOOOOOOC2.lck Reserving mernory: 59S8754 Accum. s ~ z e :1246 locking: DTOOOOOOOl DT00000001.dtf alreaoy done' locklng: DT00000002 Reading: 'DT00000002' Actual size: 1014 0, 1 ; 1, 6 ; # local classes: 2 Det: 0.533333: 1 Computing deter. for Tree 2 Best attrlbute Temperatura 0.509524 New Mask: 112211 getnarne: file DL000000020001 locking: DL000000020001 getnarne: file DL000000020002 locking: DL000000020002 getname: file DT000000020003 l o c k ~ n g :DT000000020003 Readlng Input . . Index open . . wrltlng subfile DT000000020003 data:l: 5 3 3 1 1 8 char written flushlng.. .writing subfile DT000000020003 data:l: 6 3 3 2 0 5 char wrltten
B Depuración cn la salida del sistema de minería de datos dderive 223
flushing.. .writing subfile DT000000020003 data:l: 7 2 3 2 1 V char wrltten flushing.. . w r ~ t l n gsubfile DT000000020003 data:l: 9 1 3 1 1 V char written flushing.. .writing subflle DL000000020002 data:l: 10 3 2 1 1 9 char wrltten flushlng.. .writlng subfile DLOOOOOOOL0002 data:l: 11 1 2 2 1 9 char wrltten ~ . f l u s h ng. .writing subfile DL000000020001 data:l: 13 2 1 1 1 9 char written flushing.. Computing deter. for Tree 1 Leave : 1, 1 (1)
unlocking subfile tree DL000000020001 unlocking : DL000000020001.lck Computing deter. for Tree 2 Leave : 1, 1 (2)
unlocking subfile tree DL000000020002 unlocklng : DL000000020002.lck unlocking subfile tree DT000000020003 unlocklng : DT000000020003.lck Recervlng memory: 5993170 Accum. size: 6530 locking: DT000000020003 Reading: 'DT000000020003' Actual size: 766 0, 1 ; 1, 3 ; # loca- classes: 2 Det: 0.666667: 1 Computing deter. for Tree 3 Best attribute Vista exterlor 0.5 New Mask: 122211 getname: file DL0000000200030001 locking: DL0000000200030001 getname: flle DL0000000200030002 locking: DL0000000200030002 getname: file DT0000000200030003 lockirg: DT0000000200030003 Readlng Input . . Index open . . Index good . . writing subfile DT0000000200030003 data:l: 5 3 1 1 6 char wrltten flushing..
H Depuración en la salida del sistema dc minería dc datos ddcrive 224
. w r ~ t i n gsubflle DT0000000200030003 data:l: 6 3 2 0 6 char wrltten flushing.. .wrlting subflle DL0000000200030002 data:l: 7 2 2 1 6 char written flushing.. .writing subfile DL0000000200030001 data:l: 9 1 1 1 6 char written flushing.. Computing deter. for Tree 1 Leave : 1, 1 (1) unlocklng subfile tree DL0000000200030001 unlocklng : DL0000000200030001.1ck Computing deter. for Tree 2 Leave : 1, 1 (1) unlocking subflle tree DL0000000200030002 unlocklng : DL0000000300030002.1ck unlock-ng subfile tree DT0000000200030003 unlocklng : DT0000000700030003.1ck Reservlng memory: 3423174 Accum. size: 5324 locklng: DT0000000200030003 Readlng: 'DT0000000200030003' Actual size: 495 0, 1 ; 1, 1 ; # local classes: 2 Det: 0: 0 Computlng deter. for Tree 3 Best attribute Viento 1 New Mask: 122221 getname: flle DL00000002000300030001 locklng: DL00000002000300030001 getname: file DL00000002000300030002 locklng: DL00000002000300030002 Reading Input . . Index open . . Index good . . writing subflle DL00000002000300030001 data:l: 5 1 1 4 char written flushing.. .writlng subflle DL00000002000300030002 data:l: 6 2 O 4 char written flushing.. Computing deter. for Tree 1 Leave:
1, 1 (1)
H DcpuraciOii en la salida del sistema de miiiería de datos dderive 225
unlock~ng : DL000000020003000300Ol.lck Compilting deter. for Tree 2 Leave : o, 1 (1) unlocking subflle tree DL00000002000300030002 unlocklng : DL00000002000300030002.1ck Subtree a level: 3 Viento, 1 (2) 1---[ 1, 1 ] --->1, 1 (1)
eot unlocklng : DT0000000200030003.1ck Subtree a level: 2 Vista-exterior, 0.5 (4) 1---[ 1, 1 1 --->1, 1 (1)
eot unlocking : DT000000020003.lck Subtree a level: 1 Temperatura, 0.509524 (7) 1---[ 1, 1 1 --->1, 1 (1) l 1---[ 2, 2 ] --->1, 1 (2)
1 ---[
3, 3 ] --->Vista-exterior, 0.5 (4) 1---[ 1, 1 1 --->1, 1 (1)
eot unlocking : DT00000002.lck Subtree a level: O Humedad, 0.541667 (14) - - - [ 1, 1 1 --->Dt Elle: DT00000001.dtf
1 1---[ 2, 2 ] --->Temperatura, 0.509524 (7)
i? Depuracihn en la salida del sistema de minería de datos ddcrive 226
eot unlocking : tenis. txt-.lck Remaining files e OP
El siguiente listado es la salida del proceso participante derivando el árbol de decisión con una determinación de primer orden. $ dderive.exe -v -d -F -pool -1 -S > salida.cornpleta.nouniforme.participantel.txt 2 > & 1 Dlstributed tree in3uction: v5.8 (c) Jose R. Arguello,1996, 1997, 1998
[email protected] Limited version to 70 x 200 Estimated memory required : 40064000 getname: file DLOOOO locking: DTOOOOOOOl DTOOOOOOOl
Index: DTOOOOOOOl level: O =Observacion, Vista_-exterior, Temperatura, Viento, +Jugar-- tenis, Mask: 11111 Value list: 1 1 1 1 O ; Class: O Value list: 2 1 1 2 O ; Class: O Value list: 3 2 1 1 1 ; Class: 1 Value list: 4 3 2 1 1 ; Class: 1 Value list: 8 1 2 1 O ; Class: O Value list: 12 2 2 2 1 ; Class: 1 Value list: 14 3 2 2 O ; Class: O Actual size: 9V9 0, 4 ; 1, 3 ; # local classes: 2 Det: 0.25: O Computing deter. for Tree 1 Best attribute Vista-exterior 0.714286 New Mask: 12111 getname: file DLOOOOOOOlOOOl
B Depuración en la salida del sistema de minería dc datos dderive 227
locklng: DLOOOOOOO1OOOl getname: file DL000000010002 locklng: DL000000010002 getname: file DT000030010003 locklng: DT000000010003 Reading Input . . Index open . . Index eof . . writing subfile DLOOOOOOOlOOOl data:l: 1 1 1 1 O 8 char written flushing.. .writlng subfile DLOCOOOOOlOOOl data:l: 2 1 1 2 O 8 char written flushing. . .wrlting subfile DL000000010002 data:l: 3 2 1 1 1 U char wrltten f lushing . . . w r ~ t l n gsubflle DT000000010003 data:l: 4 3 2 1 1 U char wrltten flushing.. .writing subfile DLOOOOOOOlOOOl 8 char written flushing.. .writing subfile DL000000010002 data:l: 12 2 2 2 1 9 char written flushlng.. .writing subfile DT000000010003 data:l: 14 3 2 2 O 9 char written flushlng..
Computing deter. for Tree 1 Leave : o, 1 ( 3 ) unlocklng subfile tree DLOOOOOOOlOOOl unlocking : DL000000010001.lck Computing deter. for Tree 2 Leave : 1, 1 (21 unlocklng subflle tree DL000000010002 unlocking : DL000000010002.lck unlocking subfile tree DT000000010003 unlocklng : DT000000010003.lck Reserving memory: 7997829 Accum. s ~ z e :2171 locking: DT0000000 10003 Reading: 'DT000000010003' Actual size: 617 0, 1 ; 1, 1 ; # local classes: 2 Det: 0: 0 C o m p u t ~ n gdeter. f3r Tree 3
B Depuraci6n en la salida del sistema de miileria dc datos dderive 228
Best attribute Viento 1 New Mask: 12121 getname: flle DL0000000100030001 locklng: DL0000000100030001 getname: flle DL0000000100030002 locking: DL0000000100030002 Reading Input . . Index open . . Index good . . writing subfile DL0000000100030001 data:l: 4 2 1 1 6 char written flushing.. .writing subfile DL0000000100030002 data:l: 14 2 2 0 7 char written flushing.. Computing deter. for Tree 1 Leave : 1, 1 (1)
unlocking subfile tree DL0000000100030001 unlocking : DL0000000100030001.1ck Computing deter. for Tree 2 Leave : 0, 1 (1) unlocking subfile tree DL0000000100030002 unlocking : DL0000000100030002.1ck Reserving memory: 1712322 ' ~ c c u m .size: 3514 Subtree a level: 1 Viento, 1 (2) 1---[ i, 1 1 --->1, 1 (1)
eot unlocking : DT000000010003.lck Subtree a level: O Vista-exterior, 0.714286 (7) 1 ---[ L , 1 ] --->o, 1 (3)
eot unlocking : DT00000001.lck Remalnlng files
H Depuración en la salida del sistema d e minería d e datos ddcrive 229
Este proceso generó diez archivos con el contenido mostrado por las figuras B.7, B.8, B.9, B.lO, B.11, B.12, B.13, B.14, B.15 y B.16. Los primeros cuatro
archivos fueron generados por el proceso participante (archivos del DL00000001000? al DL0000000100030002). Los demás archivos fueron
generados por el proceso coordinador. =Observacion Temp?ratura Viento *Jugar-tenis 1 1 1 0 2 1 2 0 8 2 1 0
Figura B.7 Contenido de DLOOOOOOOl 0001. -0bservacion TemperatLIrd Viento *Jugar-tenls 3 1 1 1
Figuro B.8 Contenido de DLO O O O O O O1 O O 02.
=Observacion Temperatura *Jugar-tenis 4 2 1
Figura H.9 Contenido de DLOOOOOO01 OOO3OOG1.
-0bservacion Temperatura *Jugar-tenls 14 2 O
Figura B.10 Contenido de DLOOOOO0010003O002.
-0bcervacion Vlsta-exterlor Viento *Jugar-ten15 1 3 2 1 1
Figura B.11 Contenido de DLOOOOOO020001.
B Depuracihn eii la salida del sistema dc minería de datos dderive 230
=Observaclon Vista-exterior Viento *Jugar-tenis 1 0 3 1 1 1 1 1 2 1
Figura B.12 Coíztenido de DL000000020002.
Figura B.13 Contenido de DL0000000200C30001.
=Observaclon Viento *Jugar-tenis 7 2 1
Figura B.14 Contenido de DL0000000200030002.
=Observaclon *Juqar-tenls 5 1
Figura B.15 Contenido de DL0000000300030001.
Figura B.16 Contenido de DL0000000300030002.
La opción -p de dderive provoca que un proceso busque un arcl-~ivode entrada con u n nombre especial. Tal archivo de entrada debe tener un nombre que siga el patrón de la expresión regular DT [ O - 9] *. Luego de encontrar ese archivo se siguen los mismos pasos de u n proceso iniciado con la opción -f.14 14 Los archivos con el prefijo DT son subárboles que pueden contener hojas (archivos d e prefijo IIL) u otros subárboles.
B Depuracií~nen la salida del sistema de miiiería de datos ddtrive 231
La opción -f de d d e r i v e hace a un proceso responsable de la búsqueda del mejor atributo de la tabla contenida en el archivo indicado. El procesamiento no inicia si el archivo tiene un acompañante homónimo bajo el mismo directorio y con sufijo . lck. Si el procesamiento inicia se bloquea el archivo, para crear uno homónimo con el sufijo indicado y luego de encontrar el mejor atributo para la tabla, el proceso se encarga de realizar su partición según la clasificación dictada por los valores del atributo, dejando evidencia persistente de cada clasificación encontrada en un archivo con el patrón indicado por la expresión regular DT [ O- 91 *. Estos nuevos archivos no quedan bloqueados por sufijos . lck. El proceso genera este tipo de archivos hasta completar el hallazgo de nuevas clases según el mejor atributo. Luego de lo cual el proceso busca wi archivo de entrada cuyo nombre siga el patrón de la expresión regular mencionada anteriormente para realizar este mismo procesamiento hasta no hallar más clases ni archivos que procesar. En todos los experimentos realizados, ilustrados por los dos de las secciones anteriores, lo anterior quedó reflejado: Mientras u n proceso coordinador dividía un archivo y lo bloqueaba, el proceso participante dividía un archivo libre. Más concretamente, mientras el coordinador tenía bloqueado el archivo
t eri i S .t x t con el archivo t e n i S .txt . lc k, generó primero el archivo temporal
DT00000001, luego
el archivo DLOOOOOOCl2
y luego
el
DT00000003. Mientras generaba cada uno de los anteriores archivos los
mantenía bloqueados y al finalizar la generación de uno, los desbloqueaba. Es decir, cuando el coordinador terminó la generación del archivo DT 00 0 0 0 0 0 1, lo desbloqueó, permitiendo así al proceso participante realizar el trabajo
B Depuración en la salida del sistema d e minería dc datos dderive 232
sobre el archivo mientras terminaba la generación de DL0 0000002 y de DT00000003.
El proceso participante, al trabajar sobre el archivo DT 00000001,generó los archivos DLOOOOOOOlOOOl y
DL000000010002
en el caso de la
determinación con distribución de probabilidad uniforme, y los archivos DL000000010001, DL000000010002 y DT000000010003 en el caso de la
determinación de primer orden. Mientras el proceso coordinador trabajaba sobre sus datos, el proceso participante realizaba lo mismo con los suyos. Aunque no se tiene u n sentido de propiedad de los archivos, los procesos compiten por bloquear de primero un archivo libre.
B.4 D I V I S IDE ~N LAS TAREAS DE DDERIVE Una tarea de dderive se presenta ante tdderive como u n archivo de entrada. Los rasgos de dderive que fueron presentados son muy importantes para conocer cómo dividir una tarea en subtrabajos más pequeños: que u n proceso de dderive realice su trabajo sobre el archivo de la tarea hasta alcanzar u n nivel de profundidad determinado a partir del cual se detenga el proceso dderive para repartir los subconjuntos de datos resultantes a otras computadoras, según lo organice el planificador del servidor.
C Cálculos de los indicadores para las políticas de administración de tdderive t d d e r i v e es un sistema distribuido que realiza decisiones según el estado
de sus propias labores y del estado del sistema que lo hospeda. Las decisiones de cada una de las computadoras que hospedan instancias interactuantes de t d d e r i v e colaboran en la consecución de una justicia global y de un mejor
rendimiento de las computadoras en forma individual (políticas a, (S, y y). Con el fin de llevar a cabo tales decisiones, se debe calcular la capacidad de la computadora, la carga funcional de la computadora y la carga de aplicación de la computadora; indicadores que fueron destacados en el capítulo 8 sobre el diseño de la administración del sistema. En este anexo son presentados definiciones y ejemplos de cada uno de los anteriores valores que indican la capacidad y carga de una computadora.
C.l CAPACIDAD DE UNA COMPUTADORA DE REFERENCIA Una computadora de referencia y con capacidad 1,O es aquella que tenga las siguientes características: m
Tipo de buses: PC.
m
Cantidad de microprocesadores: 1.
m
Reloj de microprocesadores: 400.
m
Memoria: 128.
m
Disco para t d d e r i v e : 1024.
C Cálculos de los indicadores para las políticas de administracióii de tddcrive 234
e Vecinas en t d d e r i v e : 5.
Con base en una referencia se establecen los siguientes pesos de las características y parámetros para determinar la capacidad de cualquier computadora. Estos pesos y características deben ser únicos para todo el sistema, pero debe tenerse la capacidad de modificarlos en forma global, de manera que sea factible encontrar valores que mejor ajusten en un sistema particular. Todo peso y parámetro es apoyado por el componente admin.info para su respaldo permanente, en la entidad "pesos~umbrales~globales".
Pesos PESO-MICRO: 55'X). e PESO-RAM: 25%.
PESO-DISCO: 10%. e PESO-VECINAS: 10%.
Parámetros
e PARM-MEM-BASE: 128.
e DISCO-BASE: 1024. e VECINAS-BASE: 4.
C.1.1 Cálculo de la capacidad de una computadora La capacidad de una computadora se calcula de la siguiente manera, según
(I Cálculos de los indicadores para las políticas de admiiiistracií>iide tdderive
235
las definiciones anteriores:
capacidad
1
ihusr.~ tipo = ~\.~,XL.1/)01Ii,Si~i'IH(;.l l'I~O.iíEIlI~~ ',,ll?(;. 1 .\l. 1.Y + 1 +i.rciniis u.su(1ii.s . I~L,YO;Y!I 11.1s vtTcinli.s clititiri~d 1 --rnt>in lihrt. - I'fi,'LYO S BL\ 1 1 -.\ll..:\ 1 /,ll~RI< .\ 1I.Y l -rii.vco lihrr 1'1i.YO /)I,Y('O I - u~st.c ) L¡BI?F .MI.\.
l
r
fiincionnl
+capact~iad
+
j
+
1
La tabla siguiente muestra un ejemplo del cálculo de la carga funcional d e varias computadoras.
C Cálculos de los indicadores para las políticas de administración de tddcrive 237
Rubro
CPU Promedio de carga
Peso Computadora Kefei-encia
50,00subh.
espera ) ')
.sttl~tr r.~p1~1.11. /'I org.hsq1db1jdb~Driver jdbc:hsqldb:info/adminbd configs/create~db.txt