Casandra

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA INFORMÁTICA GRADO EN INGENIERÍA DE COMPUTADORES CASANDRA Realizado por Daniel Segura Ruiz Tutorizado por José Antonio Montenegro Montes Departamento Lenguajes y Ciencias de la Computación UNIVERSIDAD DE MÁLAGA MÁLAGA, septiembre de 2016 Fecha defensa: El Secretario del Tribunal Resumen: El carácter arbitrario del comienzo, duración y dificultad de las actividades que acompañan al ejercicio discente afecta al rendimiento del alumno al tener que invertir un tiempo en la gestión y planificación de dichas tareas por tener que acomodarlas a su planificación diaria. Con la intención de facilitar dicha tarea se desarrolló originalmente esta aplicación Android, que permitía a un usuario potencial planificar su tiempo con los siguientes elementos: - Un horario semanal con las horas de docencia y los intervalos de tiempo disponible para trabajar. - Una lista de tareas con un carácter periódico o esporádico (es decir con una carga de trabajo expresada en horas totales de dedicación necesaria y con una fecha límite determinada). - Una agenda a lo largo de la cual desarrollar la planificación, con la fecha de inicio y fin del curnso en que se realizan las tareas. Con esta información, se elaboraba una gestión del tiempo basada en algoritmos de planificación de procesos como RMS, DMS y EDF, que resultaron adecuados para la elaboración de planificaciones sencillas. El objetivo de éste trabajo es dotar a la aplicación de unas planificaciones de mayor calidad teniendo en cuenta las preferencias del usuario y desarrollar las posibles mejoras que brindaba usando las preferencias horarias del usuario como heurístico para disponer de un juicio de valor de las planificaciones y así poder ajustar el resultado a sus gustos mediante técnicas de I.A. como CSP (Problemas de satisfacción de restricciones), hacer la interfaz de usuario más cómoda e intuitiva y añadir componente lúdico al seguimiento de las tareas realizadas, premiando el trabajo constante mediante una valoración periódica de la progresión y cumplimiento de las tareas Palabras claves: Android, Planificación, Tareas Abstract: The arbitrary nature of onset, duration and difficulty of the activities that learning implies, affects student performance as the student has to invest their time in planning and management of these tasks in order to accommodate them to their daily planning. This Android application was originally developed with the intention of facilitating this task by allowing a potential user to plan their time with the following elements: - A weekly schedule with teaching hours and time intervals available for work. - A list of tasks with a newspaper or sporadic (i.e. with a workload expressed as a number of hours of dedication required and with a certain deadline). - A calendar along which planning happens, with start and end date those of the course whithin which tasks are performed. With this information, a time management was made based on process scheduling algorithms such as RMS, DMS and EDF, which were found suitable for making simple schedules. The aim of this work is to provide higher quality schedules taking user preferences into acount and develop and using them as a heuristic to provide a way to evaluate schedules and adjust the results to their preferences using AI techniques like CSP (Constraint Satisfaction Problems), make the interface more intuitive and user-friendly and add a gaming component to the tracking of completed tasks, rewarding the ongoing work by a periodic assessment of the progress and fulfillment of the tasks. Keywords: Android , Scheduling, Tasks . ´ Indice 1. Introducci´on 9 1.1. Motivaci´on.................................... 9 1.2. Objetivos .................................... 9 1.3. Vocabulario ................................... 12 1.4. Aplicaciones existentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.5. Equipamiento utilizado para el trabajo . . . . . . . . . . . . . . . . . . . . 13 2. Descripci´on general de la aplicaci´on 14 2.1. Requisitos de aplicaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.1. Agenda ................................. 14 2.1.2. Horario o Plantilla Semanal . . . . . . . . . . . . . . . . . . . . . . 14 2.1.3. Intervalos de una plantilla semanal . . . . . . . . . . . . . . . . . . 14 2.1.4. Intervalos planificados . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.1.5. Tareas.................................. 15 2.1.6. Motor de planificaci´on . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.7. Contexto de planificaci´on . . . . . . . . . . . . . . . . . . . . . . . . 17 2.1.8. Uniendolaspiezas ........................... 19 2.2. Flujodedatos.................................. 20 3. Algoritmos de planificaci´on 21 3.1. Tabla comparativa algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.1.1. El algoritmo RMS ........................... 23 3.1.2. El algoritmo DMS ........................... 25 3.1.3. El algoritmo EDF ........................... 26 3.2. Adaptaci´on de algoritmos de planificaci´on . . . . . . . . . . . . . . . . . . 27 3.3. Problemas de satisfacci´on de restricciones (CSP)............... 30 3.3.1. Terminolog´ıa y conceptos elementales . . . . . . . . . . . . . . . . . 30 3.3.2. Definici´on de un problema CSP .................... 31 3.3.3. Restricciones .............................. 32 3.3.4. T´ecnicas................................. 32 3.4. Inclusi´on de t´ecnicas CSP en las planificaciones . . . . . . . . . . . . . . . 34 3.5. Librer´ıa de planificaci´on Optaplanner ..................... 38 3.5.1. Modelar el problema . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.5.2. Configurar un Solver . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.5.3. Inicializar el problema . . . . . . . . . . . . . . . . . . . . . . . . . 41 7 4. Dise˜no 43 4.1. Patronesdedise˜no ............................... 43 4.1.1. El patr´on Data Access Object ..................... 43 4.1.2. Utilizaci´on del patr´on Data Access Object en nuestra aplicaci´on . . 44 4.1.3. El patr´on Policy/strategy ........................ 46 4.1.4. Utilizaci´on de Strategy en nuestra aplicaci´on . . . . . . . . . . . . . 47 4.2. Dise˜nodeobjetos................................ 50 4.2.1. El paquete casandra.android . . . . . . . . . . . . . . . . . . . . . . 50 4.2.2. El paquete es.uma.casandra.core . . . . . . . . . . . . . . . . . . . . 51 4.2.3. El paquete es.uma.casandra.bbdd . . . . . . . . . . . . . . . . . . . 52 4.3. Metodolog´ıa de trabajo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.3.1. Fasedean´alisis ............................. 53 4.3.2. Fasededise˜no.............................. 53 4.3.3. Fase de codificaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.3.4. Fasedepruebas............................. 53 4.3.5. Fase de correcci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 5. Herramientas utilizadas 55 5.1. Latex....................................... 55 5.2. Control versiones del c´odigo fuente . . . . . . . . . . . . . . . . . . . . . . 55 5.3. GityAndroidStudio.............................. 58 5.4. Inkscape..................................... 60 5.5. SQlite ...................................... 61 5.6. Android ..................................... 63 6. Conclusi´on 74 6.1. Testsderendimiento .............................. 74 6.2. Uso de librer´ıa Optaplaner . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 6.3. Conclusiones acad´emicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 6.4. Posiblesmejoras................................. 77 A. Manual de usuario 79 A.1.Interfazdeusuario ............................... 80 A.2.Definirtareas .................................. 82 A.3. Definir horario y tiempos libres en la Agenda . . . . . . . . . . . . . . . . . 88 A.4.Planificar .................................... 95 A.5. Confirmaci´on de Tareas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 A.6.Opcionesdelmen´u ...............................102 Bibliograf´ıa 103 8 Cap´ıtulo 1 1. Introducci´on 1.1. Motivaci´on En el marco de las ense˜nanzas regladas, se hace patente la necesidad de una metodolog´ıa a la hora de afrontar con mesura y buena salud el conjunto de obligaciones que se van a ir sucediendo a lo largo del per´ıodo de aprendizaje. Por lo general no es suficiente una simple enumeraci´on de las actividades que se desarrollar´an en horarios fijos, sino que es necesaria una planificaci´on del tiempo disponible tras ´estas para realizar las tareas y afianzar conocimientos, es decir, para el correcto aprovechamiento de los contenidos. El car´acter heterog´eneo del comienzo, duraci´on y dificultad de las actividades que suelen acompa˜nar al ejercicio discente, se puede convertir en un escollo que poco o nada tiene que ver con el objetivo de la ense˜nanza en s´ı, pero que repercute en el alumno, al tener que invertir el preciado tiempo disponible, en la gesti´on y planificaci´on de dichas tareas, al tener necesariamente que acomodarlas a su vida diaria. Este proyecto surge de la intenci´on de facilitar dicha tarea y ayudar en la medida de lo posible a un uso m´as eficaz del tiempo del alumno, es decir, pretendemos automatizar el proceso de planificaci´on del trabajo del alumno, que as´ı pierda el menor tiempo posible en la gesti´on del tiempo, ya que haciendo uso de la planificaci´on resultante de la ejecuci´on del programa (que en esta mejora pretende ser la m´as cercana a sus preferencias en cuanto a horarios de estudio) resulte un plan satisfactorio para llevar a cabo todas sus tareas a tiempo. Se ha elegido seguir desarrollando la aplicaci´on que originalmente se elabor´o como proyecto final de carrera, ya que brindaba muchas posibilidades interesantes de mejora. La plataforma de desarrollo seguir´a siendo Android, por resultar adecuado un dispositivo port´atil para planificar tus tareas tanto en el centro de estudio como en el hogar, adem´as dicha plataforma cuenta con una gran variedad de herramientas de desarrollo gratuitas y es ampliamente utilizada por la comunidad a la que se dirige la aplicaci´on, lo que nos permite llegar a un gran n´umero de potenciales usuarios. 1.2. Objetivos La aplicaci´on original permiti´o que un usuario potencial (un alumno de ense˜nanza reglada) planificara su tiempo de estudio usando los siguientes elementos Un horario escolar con las horas de docencia impartidas al alumno y los intervalos 9 Cap´ıtulo 1 1.2 Objetivos de tiempo disponible para que ´este trabaje a lo largo de una semana (cuya mejor planificaci´on posible es nuestro objetivo). Una serie de tareas que pod´ıan tener un car´acter o bien peri´odico (aquella que implique dedicarle un tiempo concertado a una tarea con una cadencia establecida durante todo el per´ıodo de validez del calendario), o espor´adico (una carga de trabajo expresada en horas a ser realizado en el tiempo libre expresado en el horario escolar del usuario antes de una determinada fecha). Un calendario escolar oAgenda, que marcaba los deadlines de las tareas espor´adicas, y que tambi´en impone una fecha de inicio y fin del curso, a lo largo de cual desarrollar´an las tareas peri´odicas. Con la informaci´on suministrada previamente, se elaboraba una gesti´on del tiempo basada en algoritmos de planificaci´on de procesos como RMS, DMS y EDF, que finalmente resultaron ´utiles para la elaboraci´on de planificaciones sencillas. El objetivo principal de ´este proyecto es dotar a la aplicaci´on de unas planificaciones de mayor calidad, ya que si bien era posible obtenerlas ´estas no ten´ıan en cuenta las preferencias del usuario. Se dota a los intervalos horarios disponibles del usuario de informaci´on cualitativa y de este modo poder usar las preferencias del usuario en cuanto a la elecci´on de determinados intervalos horarios frente a otros, para poder hacer valoraci´on de las planificaciones, y usar dicha informaci´on como heur´ıstico para suministrar una planificaci´on resultante ajustada a sus gustos, abordando el problema con t´ecnicas como las empleadas para la resoluci´on de Problemas de satisfacci´on de restricciones (CSP). De este modo, ahora cuando se introduzca un intervalo de tiempo disponible para trabajar, tambi´en se deber´a suministrar informaci´on acerca de cu´an agradable resulta ese intervalo, generando finalmente (aneja a el horario escolar) una prelaci´on de intervalos a ser utilizados, ´util a nuestro enfoque de dar una planificaci´on de calidad. Se mejora la interfaz de usuario, haci´endola m´as c´omoda e intuitiva, buscando reducir el n´umero de pulsaciones y procurando una presentaci´on escueta y precisa de contenidos, para ello se ha incluido un navigation drawer (men´u contextual que permite navegar c´omodamente atajando a las distintas secciones principales de la aplicaci´on). Se ha mejorado el contraste de los gr´aficos para procurar una lectura m´as agradable. 10 Cap´ıtulo 1 1.2 Objetivos Se a˜nade un componente l´udico; la aplicaci´on realiza un seguimiento de las tareas tras la planificaci´on inicial de las tareas, as´ı que cada vez que se acceda a la aplicaci´on, ´esta eval´ua el estado de realizaci´on de las mismas y, si es necesario, replanificar´a o exigir´a cambios en caso de que no sea planificable con las condiciones actuales; la parte de ludificaci´on premia el trabajo constante, mediante una valoraci´on peri´odica de la progresi´on de las diferentes tareas y el cumplimiento de sus deadlines (fechas l´ımite para su realizaci´on). El objetivo es motivar el compromiso mediante la captura del inter´es del estudiante e incentivar la constancia (haciendo uso del instinto intr´ınseco del ser humano por el gusto al juego), la ludificaci´on, definida en sentido amplio, es “el proceso de definir los elementos comprendidos en los juegos que los hace divertidos y motivan a los jugadores a seguir jugando, y usar esos mismos elementos en un contexto ajeno al juego para influenciar el comportamiento” Otra mejora es la posibilidad de compartir los horarios, la aplicaci´on permite importar y exportar un horario determinado, de modo que se puedan difundir de un modo sencillo un esquema horario que posteriormente los destinatarios pueden adaptar a sus gustos o necesidades. De este modo ser´ıa trivial enviar a un conjunto de alumnos los horarios de las asignaturas y que cada uno de los alumnos adaptara dicho horario incorporando ´unicamente las horas que tienen disponibles a lo largo de la semana que les vinieran bien para trabajar en las materias. Se pueden transmitir mediante cualquier v´ıa, ya sea correo electr´onico paso de mensajes con aplicaciones de mensajer´ıa, gestores de ficheros de Android, descarga desde alguna url, etc . . . En cuanto a los avisos y eventos de las tareas planificadas, cabe se˜nalar que el resultado de las planificaciones la aplicaci´on las integra en la plataforma utilizando la API de Android Calendar Provider, generando eventos de calendario para los trabajos a realizar, de ´este modo toda la funcionalidad cualquier aplicaci´on que trabaje contra el calendario de la plataforma es aplicable a los resultados de la planificaci´on, no obstante, la aplicaci´on realiza una serie de funciones b´asicas sobre estos resultados, es decir permite eliminar todos los eventos en caso de que se quiera deshacer la planificaci´on actual, y tambi´en se encarga de actualizar los mismos cuando se hacen replanificaciones en el seguimiento de las tareas de manera autom´atica. 11 Cap´ıtulo 1 1.3 Vocabulario 1.3. Vocabulario A continuaci´on se precisar´a el significado de algunos t´erminos utilizados a lo largo del texto. Tareas (el car´acter de la tarea podr´a ser peri´odico o espor´adico): •Peri´odicas: Una tarea peri´odica ser´a aquella que implique dedicarle un tiempo concertado a una tarea con una cadencia establecida (e.g. practicar 3 horas diarias con un instrumento), se pedir´an su frecuencia (qu´e d´ıas de la semana se llevar´a a cabo) y su duraci´on. •Espor´adicas: En una tarea espor´adica se indicar´a el tiempo total necesario para completar la tarea, que la aplicaci´on posteriormente se encargar´a de distribuir adecuadamente para la consecuci´on del objetivo antes de que acabe su plazo.(e.g. 150 horas para superar la asignatura de c´alculo ´o 3 horas para trabajo de Asignatura de Tecnolog´ıa, etc . . . ) Plazo: Hay en realidad dos intervalos de fechas que nos interesan. •Agenda: El intervalo de fechas sobre las que tienen sentido las planificaciones (e.g. un semestre, un curso) •Tareas: Si la tarea es espor´adica ser´a el d´ıa de comienzo y el d´ıa de finalizaci´on de la tarea. Si es peri´odica heredar´a los l´ımites de la agenda y se planificar´a a lo largo de toda la extensi´on de ´esta. Duraci´on: para las tareas de car´acter espor´adico se les indicar´a tanto el tiempo estimado para la finalizaci´on de la tarea en horas (e.g. 400 horas para arrostrar la asignatura de c´alculo) como , opcionalmente, el intervalo de tiempo razonable diario, ya que a determinadas tareas, s´olo tiene sentido dedicarle un tiempo adecuado (en un d´ıa, un per´ıodo demasiado peque˜no ser´ıa insuficiente para haber entrado en materia y uno excesivo resultar´ıa insostenible). Caso de no indicar un tiempo razonable diario, se le da libertad a la aplicaci´on para planificar la tarea como mejor convenga en las horas disponibles para el trabajo individual de ese d´ıa de la agenda. Si se indica un tiempo l´ımite esto implica que en un mismo d´ıa no se planificar´an m´as horas de esa tarea aunque fuese posible Preferencia: A los intervalos disponibles para realizar tareas, se les puede asignar una preferencia que es el indicador del intervalo (de los disponibles a lo largo de la semana que mejor conviene al usuario), hay cuatro grados posibles que se marcan en la creaci´on de un intervalo, desde una estrella (no quiero trabajar en este horario si es posible) hasta cuatro estrellas (es el horario id´oneo) 12 Cap´ıtulo 2 2.1 Requisitos de aplicaci´on 2.1.8. Uniendo las piezas La idea es que un usuario defina un marco de tiempo (que hemos llamado agenda) y pueda conjugar tantos horarios (plantillas semanales) como necesite, as´ı tendremos una agenda con un conjunto de plantillas semanales seleccionables, de las que s´olo una ser´a la activa. Con esos dos elementos una agenda ser´a capaz en el futuro de suministrar al planificador de tareas una lista de intervalos de tiempo disponibles, as´ı ´este solo tendr´a que preocuparse, en principio, de ir consumiendo dicho tiempo a su elecci´on. Por otro lado tenemos las tareas que son la otra parte necesaria al planificador para realizar su funci´on de distribuir el tiempo libre extra´ıdo de la agenda entre las tareas teniendo en cuenta las preferencias del usuario en ´estas como m´aximo tiempo seguido, deadlines, etc. En este punto hemos alimentado un planificador con tareas yagenda y: o bien obtenemos una planificaci´on v´alida, o nos informar´ıa de que no es posible la misma, pero a´un nos queda contemplar el hecho de que ocurran imprevistos y las tareas no se vayan llevando a cabo, entonces utilizamos el mecanismo del contexto de planificaci´on para evaluar lo hecho realmente hasta la fecha y en caso necesario volver a lanzar planificaciones con los datos de las tareas actualizados. 19 Cap´ıtulo 2 2.2 Flujo de datos 2.2. Flujo de datos Procuraremos mostrar con muy pocos elementos la informaci´on requerida por la aplicaci´on y el tratamiento que se da a los datos en el sistema desde un alto nivel de abstracci´on Usaremos para ello un diagrama de flujo de datos de alto nivel Figura [2], en el que ya se plasman los procesos que describen el proceso principal. Figura 2: Flujo de datos de la aplicaci´on Figura 3: Elementos del grafo Figura [2] Este tipo de acercamiento al an´alisis del problema nos ha servido para en primer lugar tener una idea m´as cercana a la realidad de la implementaci´on de nuestra aplicaci´on, y adem´as tambi´en facilita una posterior reflexi´on acerca de las distintas posibilidades de desarrollo [3]. 20 Cap´ıtulo 3 3. Algoritmos de planificaci´on El planificador (scheduler) es un componente funcional muy importante de los sistemas operativos, y esencial en los sistemas operativos de tiempo real. Su misi´on consiste en repartir el tiempo disponible de un microprocesador entre todos los procesos que est´an disponibles para su ejecuci´on. Todo sistema operativo gestiona los programas mediante el concepto de proceso. En un instante dado, en el ordenador pueden existir diversos procesos listos para ser ejecutados, sin embargo, solamente uno de ellos puede ser ejecutado (en cada microprocesador). De ah´ı la necesidad de que una parte del sistema operativo gestione, de una manera equitativa, qu´e proceso debe ejecutarse en cada momento para hacer un uso eficiente del procesador En los sistemas operativos en tiempo real, su comportamiento se caracteriza por garantizar que todo programa se ejecutar´a dentro de un l´ımite m´aximo de tiempo. El planificador debe comportarse de manera que esto sea cierto para cualquier proceso. Expresado en t´erminos de la Teor´ıa de la Planificaci´on de Tareas de Tiempo Real (o Real-Time Scheduling Theory) [4] define Prop´osito Satisfacer las restricciones temporales de las m´ultiples tareas de un sistema inform´atico en tiempo real. Procedimiento Planificar los recursos del sistema (CPUs) de acuerdo a ciertos algoritmos, de tal manera que la temporizaci´on del sistema sea predecible, comprensible y mantenible. En estos casos, la finalidad del planificador es balancear o equilibrar la carga del procesador, impidiendo que un proceso monopolice el procesador o que sea privado de los recursos de la m´aquina. En entornos de tiempo real, como los dispositivos para el control autom´atico en la industria (por ejemplo, robots), el planificador tambi´en impide que los procesos se paren o interrumpan a otros que esperan que se realicen ciertas acciones. Su labor resulta imprescindible para mantener el sistema estable y funcionando. Existen distintos niveles de planificaci´on (basados en la frecuencia con la que se realiza cada uno), en los sistemas operativos de prop´osito general, existen tres tipos de planificadores. 21 Cap´ıtulo 3 Planificador a corto plazo: tambi´en denominados dispatcher oshort term scheduler, es el que se ha descrito previamente, siendo tambi´en el m´as importante. Planificador a medio plazo (mid term scheduler) est´a relacionado con aquellos procesos que no se encuentran en memoria principal (memoria virtual). Su misi´on es mover procesos entre memoria principal y disco (lo que se conoce como swapping) Planificador a largo plazo (long term scheduler) es el encargado de introducir nuevos procesos en el sistema y de finalizarlos. Hay numerosas y variadas pol´ıticas de planificaci´on, a continuaci´on se enumeran algunas aunque lo habitual es utilizar pol´ıticas mixtas. Round-robin Round-robin con pesos Prioridades mon´otonas en frecuencia (RMS (Rate-monotonic scheduling)) EDF (Earliest deadline first scheduling) o Menor tiempo de respuesta primero FIFO Tambi´en conocido como FCFS “First Come, First Served” SJF Shortest Job First CFS Completely Fair Scheduler (´o Planificador Completamente Justo) SRT Shortest Remaining Time SPT Shortest Process Time Planificaci´on mediante colas multinivel Es habitual que se mezclen, es decir, podr´ıa ser que el planificador a corto plazo utilice round-robin, mientras que el planificador a largo plazo use varias colas FIFO y cada una de esas colas corresponda a una prioridad diferente. Desde una perspectiva diferente existen dos tipos de algoritmos de planificaci´on Expropiativos :´ Estos generan planificaciones en las que se puede cambiar la CPU de una tarea a otra en cualquier momento si as´ı lo desea el planificador No expropiativos : Los no expropiativos permiten que se ejecute el proceso hasta que acabe su trabajo. Es decir, una vez les llega el turno de ejecutarse, no dejar´an libre la CPU hasta que terminen o se bloqueen. 22 Cap´ıtulo 3 3.1 Tabla comparativa algoritmos 3.1. Tabla comparativa algoritmos Figura 4: Peque˜no esquema de los algoritmos de Scheduling De entre todos los posibles algoritmos de Scheduling disponibles, hemos elegido los algoritmos RMS ,DMS yEDF que procederemos a analizar posteriormente. El criterio de elecci´on de dichos algoritmos es: En primer lugar el hecho de que los algoritmos deb´ıan ser para sistemas monoprocesador, debido a que un ser humano no es capaz de realizar varias tareas de aprendizaje simult´anemente El segundo es que entre los algoritmos elegidos deb´ıan estar tanto los que usen prioridades din´amicas (por ejemplo EDF) como aquellos que utilicen prioridades est´aticas (como RMS oDMS) Todos los algoritmos deben permitir la planificaci´on expulsiva (es decir que se puede cambiar la ejecuci´on de una tarea a otra en cualquier momento si as´ı lo desea el planificador), debido a que las tareas a realizar por el alumno tendr´an unos tiempos l´ımite de trabajo cont´ınuo y necesitarmos cambiar de tarea para continuar el tiempo de estudio con otra. Los tres algoritmos elegidos cumplen estas propiedades. 3.1.1. El algoritmo RMS Es un algoritmo que utiliza prioridades est´aticas (las prioridades de todos los procesos permanecen constantes a lo largo del tiempo). Habr´ıa que puntualizar el hecho de que usualmente se realiza (err´oneamente) una asignaci´on de prioridades est´aticas de acuerdo con la importancia que se atribuye al proceso, 23 Cap´ıtulo 3 3.1 Tabla comparativa algoritmos y ´este m´etodo de asignaci´on de prioridades no es ´optimo (el algoritmo se dice ´optimo si en el caso de existir una soluci´on, la encuentra) y puede conducir a fallos en el tiempo de respuesta de alg´un proceso, incluso en el caso en que el procesador est´e poco utilizado. As´ı que la importancia subjetiva no es uno de los criterios v´alidos para la asignaci´on de las prioridades a los procesos que forman el sistema en tiempo real. Se puede comprobar que bajo determinadas condiciones, la asignaci´on de prioridades de forma que el proceso con menor per´ıodo tenga mayor prioridad, es ´optima. Este tipo de planificaci´on se denomina Asignaci´on Monot´onica en Frecuencia (RMS), y es ´optima para prioridades est´aticas, es decir, si un sistema con prioridades est´aticas tiene alguna planificaci´on admisible (una planificaci´on admisible es aquella que respeta las restricciones temporales (deadlines) de todas las tareas, ya sea con sus tiempos de c´omputo m´aximos (tiempo real duro) o con sus tiempos medios (tiempo real suave), la RMS encontrar´a una planificaci´on admisible. Se define el factor de utilizaci´on del procesador como la fracci´on de tiempo que ´este est´a ocupado ejecutando procesos. Este valor viene dado por la siguiente expresi´on: U=Xci pi (1) Siendo ciel tiempo de c´omputo del proceso y pisu periodo. Se dice que un sistema utiliza completamente el procesador si la planificaci´on RMS es admisible, y cualquier incremento en el tiempo de c´omputo de un proceso hace que la planificaci´on sea inadmisible. Como Rms es ´optimo, si no es posible ninguna planificaci´on admisible con Rms, no hay ninguna otra planificaci´on con prioridad est´atica que sea admisible. Se define Factor de Utilizaci´on Garantizado para nprocesos (UGn) , como el valor m´ınimo del factor de utilizaci´on entre los correspondientes a todos los sistemas en tiempo real con nprocesos que utilizan completamente el procesador. Como se trata de un valor m´ınimo, puede haber casos de sistemas de tiempo real en los que sea posible alcanzar factores de utilizaci´on mayores que el garantizado. El sentido de este valor es que se garantiza que exista una planificaci´on admisible siempre que: U≤UGn(2) Se puede demostrar que para el caso de la planificaci´on Rms UGn=n(21 n−1) (3) 24 Cap´ıtulo 3 3.1 Tabla comparativa algoritmos Y para valores grandes de n, esto tiende al logaritmo neperiano de dos l´ım n→∞ UGn≃ln 2 ≃0,69 (4) De ah´ı se deduce que Rms es admisible cuando se cumple que U < 0,7 , es decir, Rms es admisible cuando el factor de utilizaci´on del procesador es menor que el 70 %, para un n´umero de procesos alto. Se puede demostrar que si no existieran restricciones sobre el tiempo de respuesta, se podr´ıa obtener una planificaci´on admisible para cualquier conjunto de procesos que verificaran la condici´on: U≤1 Sin embargo, la exigencia de respetar los tiempos de respuesta especificados limita el factor de utilizaci´on m´aximo a un valor menor que la unidad. Por tanto, s´olo se puede asegurar que existe una planificaci´on admisible con prioridad est´atica si el factor de utilizaci´on es inferior a 0.7 . No obstante, en algunos casos, se pueden alcanzar valores m´as altos del factor de utilizaci´on. [4] 3.1.2. El algoritmo DMS En este caso, no hay diferencias sustanciales con respecto al algoritmo RMS, en este caso el algoritmo DMS (Deadline Monotonic Scheduling) de asignaci´on de prioridades est´aticas, se basa en el criterio de asignar dichas prioridades a cada una de las tareas de acuerdo a su deadline. A la tarea con el deadline m´as cercano le ser´a asignada la mayor prioridad. Esta pol´ıtica de asignaci´on de prioridades es ´optima para un conjunto de tareas espor´adicas o peri´odicas que cumplan con el siguiente modelo. Todas las tareas han de tener deadlines menores o iguales que su m´ınimo per´ıodo Todas las tareas tienen tiempos de ejecuci´on en el peor caso, que ser´an menores o iguales a sus deadlines Todas las tareas son independientes y ninguna bloquear´a la ejecuci´on de otra (por ejemplo accediendo a recursos compartidos mutuamente excluyentes mutually exclusive shared resources) Ninguna tarea puede suspenderse de modo aut´onomo Consideraremos que no consume recursos ni el lanzar una tarea (release time), ni tampoco el intercambiar la ejecuci´on de una tarea por otra 25 Cap´ıtulo 3 3.1 Tabla comparativa algoritmos 3.1.3. El algoritmo EDF Es un algoritmo de planificaci´on din´amica, esto conlleva varios factores la planificaci´on din´amica es m´as flexible. es necesaria para ciertos tipos de sistemas. permite contemplar diversos escenarios. no es estable. es un tema abierto de investigaci´on. En concreto, nuestro algoritmo utiliza el deadline de las tareas como la base para tomar decisiones de planificaci´on. El m´etodo de planificaci´on por prioridad al deadline m´as cercano (Edf Earlier Deadline First) consiste en asignar en cada instante la prioridad m´as alta al proceso cuyo tiempo l´ımite est´a m´as pr´oximo. El tiempo l´ımite de un proceso Pien un instante tes el valor: Li(t) = ai(t) + ri(5) Donde ai(t) es el instante en que se ha producido la ´ultima activaci´on del proceso Pi a´un no satisfecha en tyries el tiempo m´aximo de respuesta admisible para el proceso. Si Pino tiene ninguna activaci´on pendiente en t, se supone que Li(t) = ∞, por tanto, el proceso que se ejecuta en el instante tes aquel cuyo valor de Li(t) es m´ınimo. Se asume que el plazo absoluto de una tarea es fijo y constante durante el tiempo de vida de la tarea. Cuando se utiliza el algoritmo Edf se exige que todas las tareas cumplan con sus plazos. Esta condici´on puede verificarse previamente si conocemos todos los par´ametros de las tareas que habr´a en el sistema. La carga de trabajo del sistema es est´atica si los par´ametros no cambian, o puede ser din´amica si nuevas tareas van llegando al sistema, de modo que cada nueva incorporaci´on que se realice conlleva un nuevo test de planificabilidad, en este caso U < 1 [4]. Se pueden garantizar el cumplimiento de los deadlines si: U= n X n=1 ci pi (6) 26 Cap´ıtulo 3 3.2 Adaptaci´on de algoritmos de planificaci´on Un ejemplo del efecto de la utilizaci´on del algoritmo podr´ıa ser, dadas unas tareas de ejemplo con las siguientes caracter´ısticas Figura 5: Datos del algoritmo EDF Ofrecer´ıa esta planificaci´on Figura 6: Ejemplo de uso del algoritmo Edf 3.2. Adaptaci´on de algoritmos de planificaci´on El hecho de que existan algoritmos de uso tan com´un como los planificadores en el mundo de los sistemas operativos, (de vital importancia sobre todo los empleados en sistemas operativos de tiempo real, en los cuales se garantiza que las tareas han de ser ejecutadas antes de un determinado tiempo l´ımite), hace pensar que quiz´as podr´ıan ser herramientas ´utiles para otro tipo de reparto de recursos, en vez de tiempo de CPU tiempo libre de un usuario. En general, todo sistema operativo gestiona sus programas mediante el concepto de proceso, en un instante dado, en el ordenador pueden existir diversos procesos listos para ser ejecutados, al igual que en un instante dado un estudiante puede disponer de varias tareas pendientes, y del mismo modo, si determinados procesos de un sistema en tiempo real requieren ser realizados antes de un tiempo l´ımite, as´ı ocurre tambi´en con las tareas del estudiante. Si en el caso de los planificadores para sistemas monoprocesador s´olo un proceso puede ser ejecutado a la vez, en el caso del estudiante s´olo una tarea puede ser llevada a cabo simult´aneamente, el modo en el que se repartan las tareas pendientes es precisamente 27 Cap´ıtulo 3 3.2 Adaptaci´on de algoritmos de planificaci´on determinado por el algoritmo de scheduling utilizado. Estos algoritmos cuidan mucho la gesti´on de los recursos disponibles, han de ser extremadamente eficientes ya que su uso es tan intensivo por parte del n´ucleo del sistema operativo que podr´ıan degradar el rendimiento de todo el sistema. Esta es una cualidad muy interesante, porque las plataformas m´oviles disponen de muchas limitaciones, usar este tipo de algoritmos redundar´a en una mayor vida ´util de la bater´ıa y unos buenos tiempos de respuesta. El tiempo de un alumno que est´e siendo v´ıctima de una ense˜nanza reglada suele estar marcado por un conjunto de horas designadas por la instituci´on en las que se tendr´an que realizar una serie de actividades y otros tiempos que habr´a de reservarse el alumno para el estudio y el trabajo. El tiempo reservado por el propio alumno para el trabajo en casa ser´a el equivalente al tiempo de CPU disponible, es decir su mas preciado recurso como estudiante y el tiempo que deber´a dedicar a tareas y estudio ser´an los procesos que habr´an de ser finalizados antes de que lleguen determinados deadlines como son fechas de ex´amenes y de entregas de trabajos. Con estos mimbres la aplicaci´on necesitar´a Un horario compuesto de las horas de trabajo de la instituci´on (esto es opcional pero la representaci´on posterior en la agenda del dispositivo queda m´as coherente y completa) y adem´as horas disponibles para estudio designadas por el alumno Un conjunto de tareas (espor´adicas) que habr´an de ser finalizadas antes de un plazo (e.g. dedicar un tiempo determinado a un tema de una asignatura antes de su evaluaci´on), o peri´odicas (aquellas que ser´an repetidas ciertos d´ıas de la semana a lo largo de toda la extensi´on del calendario) Como (por fortuna), las personas no somos m´aquinas ni nuestros cerebros CPU’s, hay ciertas condiciones (humanitarias) que se pueden exigir a las tareas como el hecho de que no se est´e trabajando de manera continuada cierta materia m´as de un determinado tiempo, o la preferencia de unas horas o d´ıas frente a otros a la hora de acometer tareas. De este modo los distintos algoritmos de planificaci´on podr´an hacer su trabajo, si bien es cierto que algunas condiciones como la optimalidad de los algoritmos se podr´ıan ver mermadas por las opciones adicionales a˜nadidas por los usuarios a la realizaci´on de las tareas, como el tiempo m´aximo continuado para una tarea en concreto, o el hecho de que 28 Cap´ıtulo 3 3.4 Inclusi´on de t´ecnicas CSP en las planificaciones y simplemente se devolv´ıa la primera soluci´on que resolviera el algoritmo de scheduling elegido (algoritmo modificado para satisfacer las restricciones anteriormente expuestas). Figura 7: Seleccion optimalidad del intervalo Ahora podemos tratar de enfrentarnos al problema de tener en cuenta la calidad de dicha soluci´on de la siguiente manera: cuando el usuario est´a elaborando un horario, a la hora de introducir un intervalo de tiempo disponible para realizar tareas se le solicita que informe adem´as de su grado de conveniencia a la hora de emplear ese tiempo para trabajar, as´ı podemos disponer de una prelaci´on de intervalos de tiempo de trabajo a la hora de planificar tareas de acuerdo las preferencias de trabajar en dichas franjas horarias por parte del usuario. Bien, una vez captadas las preferencias por determinadas franjas temporales del alumno, se ha tratado de aprovechar dicha informaci´on utilizando las t´ecnicas de CSP En primer lugar hay que tener en cuenta que se puede establecer un sencillo test de planificabilidad (algoritmo que permite saber si puede existir una planificaci´on del tipo deseado para un conjunto de tareas) si consideramos el sumatorio de tiempo disponible en la agenda y la suma de los tiempos consumidos por las tareas para una determinada agenda. La representaci´on de nuestro CSP podr´ıa ser la siguiente, nuestro conjunto de variables Xes el conjunto de todos los intervalos disponibles para trabajar en una semana de una agenda ordenados con el uso horario habitual Del dominio de dichas variables es 0 o 1 (CSP binario ) Cel conjunto de restricciones es bastante complejo, pero deviene finalmente del resultado del motor de planificaci´on En primer lugar nuestra variables son X={x1, x2, . . . , xn}siendo nel n´umero de intervalos disponibles a lo largo de la semana, tendr´an un valor pertenecientes al dominio 35 Cap´ıtulo 3 3.4 Inclusi´on de t´ecnicas CSP en las planificaciones D={0,1}cuyo significado es si dicho intervalo ser´a tenido en cuenta para la planificaci´on s´ı se usar´a (= 1) o no se usar´a (= 0). El orden en el cual las variables son asignadas durante la b´usqueda puede tener un impacto significativo en el tama˜no del espacio de b´usqueda, en nuestro caso utilizaremos la t´ecnica CSP de generar y testear de la siguiente manera: 1. En el estado inicial del problema que representaremos como el conjunto de intervalos S={x1, . . . , xn}con aridad igual a los intervalos disponibles para trabajar ordenados de lunes a viernes de la ma˜nana a la tarde, donde se ubicar´a el valor asignado a cada variable que ser´a el valor del dominio 1 ´unicamente en aquellas posiciones en las que el intervalo tenga la mayor preferencia por parte del usuario, es decir el que m´as le guste para trabajar. Ejemplo Si un horario tuviera cuatro intervalos a la semana disponibles para el trabajo del alumno y s´olo el primero tuviera la m´axima calificaci´on por parte del usuario el estado inicial se representar´ıa como S0={1,0,0,0} 2. La fase de generaci´on consiste en ir construyendo las distintas tuplas asign´andole en orden de preferencia del usuario el valor del dominio 1 a aquellos intervalos disponibles que coincidan con el grado de preferencia evaluado. i.e: primero se ir´an poniendo a 1 los intervalos horarios de cuatro estrellas luego los de cuatro estrellas y los de tres y as´ı hasta que en el ´ultimo caso tengamos activados todos los intervalos. 3. La fase de testeo consiste en la llamada al motor de planificaci´on con el conjunto de intervalos dado, con un test de planificabilidad se puede descartar iniciar la planificaci´on simplemente con el sumatorio del tiempo disponible y el tiempo que se necesita para las tareas sin tener en cuenta las restricciones; si es factible se inicia la planificaci´on con un horario que realmente es un subconjunto del suministrado por el usuario, pero el subconjunto m´as favorable posible, conforme vayan fallando las planificaciones debido a que no cumplan con restricciones “m´as finas”que la del test de planificabilidad, se ir´a generando otra tupla que insertar´a los intervalos del siguiente nivel (menos agradables para el usuario) hasta que finalmente se de con la planificaci´on que haga el menor uso posible de los intervalos m´as desagradables para el usuario y cumpla los deadlines o devuelva el mensaje de error informando de en qu´e fecha y con qu´e tarea ha fallado la planificaci´on solicitando una relajaci´on de las condiciones iniciales del problema, bien disminuyendo la duraci´on, el n´umero 36 Cap´ıtulo 3 3.4 Inclusi´on de t´ecnicas CSP en las planificaciones de tareas, el tiempo m´aximo permitido para que se trabaje de forma continuada en ellas o aumentando el tiempo disponible de estudio De este modo, se aumenta el tiempo necesario para la planificaci´on pero se hace en una serie de pasos discretos, como mucho tantos como intervalos disponibles de trabajo tenga un alumno a lo largo de la semana, que siempre ser´a un n´umero discreto y peque˜no, a mayor cantidad de intervalos menor duraci´on de estos, luego antes se descartar´a la planificaci´on en caso de no fuese admisible y se pasar´a a evaluar otra con mayor n´umero de intervalos. Con este enfoque, dada la velocidad de ejecuci´on del planificador base no hay un aumento sensible del tiempo de ejecuci´on de las planificaciones en los casos evaluados y hay gran diferencia en el resultado de la planificaci´on, mucho m´as cercana a las preferencias del usuario. Hay que objetar que el planificador no es ´optimo (un planificador es ´optimo si, existiendo una planificaci´on del tipo deseado, encuentra dicha planificaci´on siempre) ya que tanto la expulsi´on de tareas por exceder el tiempo m´aximo de dedicaci´on elegido por el usuario, como el orden en el que se insertan las tareas, que puede producir (como efecto lateral del orden fijado de asignaci´on de tareas en los intervalos disponibles) una suerte de fragmentaci´on interna que pudiera ser menor con alguna permutaci´on del orden de asignaci´on de tareas para cada intervalo (ya que ´estas tambi´en tienen una duraci´on m´ınima, no tendr´ıan sentido asignaciones de 10’ al final de un d´ıa) rompen esa propiedad. Haber tenido en cuenta esas caracter´ısticas lastrar´ıa los tiempos de c´omputo debido al hecho de que habr´ıamos de tener en cuenta las permutaciones a la entrada de los intervalos disponibles de las tareas, elevando la complejidad algor´ıtmica y obteniendo un beneficio dudoso ya que s´olo con planificaciones muy ajustadas se podr´ıa obtener alg´un beneficio. 37 Cap´ıtulo 3 3.5 Librer´ıa de planificaci´on Optaplanner 3.5. Librer´ıa de planificaci´on Optaplanner Tomando como punto de partida los problemas planteados en el apartado anterior cabe pensar si convendr´ıa la utilizaci´on de Frameworks disponibles de acceso p´ublico y gratuito como Optaplanner (desarrollada bajo el auspicio de la compa˜nia RedHat). OptaPlanner (Figura 8) es un Constraint Satisfaction Solver, es decir posee un motor de planificaci´on que permite optimizar la planificaci´on de recursos. Resuelve los problemas cl´asicos de los CSP asignar un conjunto limitado de recursos limitados (empleados, activos, tiempo y dinero) para proporcionar productos o servicios a los clientes, rutas para veh´ıculos, turnos de los empleados de turnos, planificaci´on de trabajo, etc. . . Figura 8: Funcionalidad general Optaplanner [6] Es un motor de planificaci´on ligero, escrito ´ıntegramente en Java, y que, en principio, permite a los programadores resolver problemas de optimizaci´on de un modo eficaz. OptaPlanner seg´un reza en su propaganda oculta al programador sofisticados algoritmos de optimizaci´on y heur´ıstica. Es software Open Source, y est´a publicado bajo la licencia Apache Software. Ante las ventajas que presenta el uso de un API, no reinventar la rueda, el hecho de ser un c´odigo mucho m´as estable y testado y que en principio tiene el soporte de un equipo 38 Cap´ıtulo 3 3.5 Librer´ıa de planificaci´on Optaplanner de desarrollo que lo mejora con el tiempo, merece la pena intentar integrar esta API en nuestra aplicaci´on. Para ello se hizo uso de este Framework en una nueva rama Git para tratar de establecer una comparativa con nuestra aplicaci´on y tambi´en ver cuan apropiada resultaba para integrarlo en una plataforma como Android. El proceso fue el siguiente, la resoluci´on de un problema con Optaplanner consta de cinco pasos 1. Modelar el problema, en este caso como una clase que implemente la interfaz Solution 2. Configurar un Solver que es el encargado de modelar una estrategia de resoluci´on del problema 3. Inicializar los par´ametros del problema 4. Aplicar el m´etodo Solver.solve(problema) 5. Obtener la mejor solucion del m´etodo anterior con Solver.getBestSolution(); 3.5.1. Modelar el problema Para representar el problema crearemos una clase OptaplannerSolution esto es, que contenga la lista de intervalos de plantilla semanal con sus preferencias as´ı como la agenda y la lista de tareas package es.uma.casandra.optaplanner; import org.optaplanner.core.api.domain.solution.PlanningSolution; import org.optaplanner.core.api.domain.solution.Solution; import org ... .core.api.score.buildin.hardsoftlong.HardSoftLongScore; import java.util.Collection; @PlanningSolution public class OptaplannerSolution implements Solution<HardSoftScore> { ... } Optaplanner provee m´ultiples implementaciones de Score pues es con puntuaciones con lo que estima la calidad de las soluciones ofrecidas, de entre todas ellas elegimos la HardSoftScore para de este modo poder penalizar con hard scores el incumplimiento de 39 Cap´ıtulo 3 3.5 Librer´ıa de planificaci´on Optaplanner las restricciones duras y descartar esa soluci´on y con soft scores la utilizaci´on de los intervalos peor valorados por el usuario, pero permitir que el resultado siga siendo v´alido. public class CasandraScoreCalculator implements EasyScoreCalculator<OptaplannerSolution> { @Override public HardSoftScore calculateScore(OptaplannerSolution sol) { ... //Calculamos las penalizaciones por violar restricciones duras: for(Tarea t:listaTmpTareas){ //La duracion que no ha entrado en la planificacion if(t.getDuracion()>0){ hardScore-= t.getDuracion(); } } //Calculamos las penalizaciones por violar restricciones blandas; for(IntervaloPlantillaSemanal i: listaIntervalos){ if(i.getSeleccionado()){ softScore+=i.getValoracion()-5; } } return HardSoftScore.valueOf(hardScore,softScore); } } 3.5.2. Configurar un Solver Configurar un Solver por permite definir la estrategia o algoritmo de resoluci´on. El API de Optaplaner nos permite configurarlo mediante un fichero de configuraci´on xml que ser´a indicado a la clase factor´ıa SolverFactory public static final String SOLVER_CONFIG = "es/uma/casandra/optaplanner/CasandraSolverConfig.xml"; ... Y ´este ser´ıa parte del fichero de configuraci´on <?xml version="1.0" encoding="UTF-8"?> <solver> <solutionClass>es.uma.casandra.optaplanner.OptaplannerSolution</solutionClass> <entityClass>es.uma.casandra.core.agenda.IntervaloPlantillaSemanal</entityClass> 40 Cap´ıtulo 3 3.5 Librer´ıa de planificaci´on Optaplanner <scoreDirectorFactory> <scoreDefinitionType>HARD_SOFT</scoreDefinitionType> <easyScoreCalculatorClass>es.uma.casandra.optaplanner.CasandraScoreCalculator </easyScoreCalculatorClass> </scoreDirectorFactory> ... </solver> La clase Solver puede utilizar varios algoritmos de optimizaci´on encadenados. A cada uno de los algoritmos que aparecen en el xml los denomina phase, para la prueba vamos a usar dos tipos de b´usqueda De las implementaciones que nos ofrece optaplanner vamos a utilizar un algoritmo de busqueda exhaustiva, y otro de b´usqueda local <!--Fases de busqueda Exhaustiva--> <exhaustiveSearch> <exhaustiveSearchType>BRUTE_FORCE</exhaustiveSearchType> </exhaustiveSearch> .... <!--Fases de busqueda Local--> <localSearch> <localSearchType>HILL_CLIMBING</localSearchType> <termination> <millisecondsSpentLimit>100</millisecondsSpentLimit> </termination> </localSearch> 3.5.3. Inicializar el problema Vamos a usar un horario con un n´umero creciente de intervalos a lo largo de una semana. Los atributos de predilecci´on de un intervalo horario en concreto ser´a seleccionado pseudoaleatoriamente mediante Math.random() de la librer´ıa de Java. Este horario ser´a aplicado sobre la agenda de una semana en la que se planificar´an tareas por valor de la mitad del tiempo disponible. for(int numIntervalos = 7; numIntervalos< 70; numIntervalos +=1){ 41 Cap´ıtulo 3 3.5 Librer´ıa de planificaci´on Optaplanner CSPHoraio datos = generarDatos(numIntervalos, new GeneradorPreferencias() { @Override public int generarPreferenciaUsuario() { return (int) Math.round(Math.random() * 5); } }); Agenda agenda = datos.agenda; List<IntervaloPlantillaSemanal> horario = datos.horario; List<TareaEsporadica> tareas = datos.tareas; resolverOptaplanner(agenda, tareas, horario, SOLVER_CONFIG_BUSQUEDA_EXHAUSTIVA); resolverOptaplanner(agenda, tareas, horario, SOLVER_CONFIG_BUSQUEDA_LOCAL); resolverCasandra(agenda, tareas, horario); } public static void resolverOptaplanner(Agenda agenda,List<TareaEsporadica> tareas, List<IntervaloPlantillaSemanal> horario, String solverXml){ OptaplannerSolution csp = new OptaplannerSolution(); csp.setAgenda(agenda); csp.setListaTareas(tareas); csp.setListaIntervalos(horario); Solver solver = SolverFactory.createFromXmlResource(solverXml).buildSolver(); long ini = System.nanoTime(); solver.solve(csp); long fin = System.nanoTime(); OptaplannerSolution sol = (OptaplannerSolution) solver.getBestSolution(); loguear(solverXml,horario,ini,fin,sol.getScore()); } 42 Cap´ıtulo 4 4. Dise˜no 4.1. Patrones de dise˜no Los patrones de dise˜no buscan: Proporcionar cat´alogos de elementos reutilizables en el dise˜no de sistemas software. Evitar la reiteraci´on en la b´usqueda de soluciones a problemas ya conocidos y solucionados anteriormente. Formalizar un vocabulario com´un entre dise˜nadores. Estandarizar el modo en que se realiza el dise˜no. Facilitar el aprendizaje de las nuevas generaciones de dise˜nadores condensando conocimiento ya existente. En Casandra hemos optado por hacer uso de patrones de dise˜no en varios apartados de la aplicaci´on que exponemos a continuaci´on [7], [8]. 4.1.1. El patr´on Data Access Object Un Data Access Object (DAO, Objeto de Acceso a Datos) es un componente de software que suministra una interfaz com´un entre la aplicaci´on y uno o m´as dispositivos de almacenamiento de datos, tales como una base de datos o un archivo. Figura 9: Representaci´on del patr´on Data Access Object fuente: “http://www.corej2eepatterns.com/Patterns2ndEd/DataAccessObject.htm” No todo son ventajas a la hora de utilizar este patr´on, mostramos los pros y contras a continuaci´on ventajas : La ventaja de usar objetos de acceso a datos es que cualquier objeto de negocio (aquel que contiene detalles espec´ıficos de operaci´on o aplicaci´on) no requiere conocimiento directo del destino final de la informaci´on que manipula. 43 Cap´ıtulo 4 4.1 Patrones de dise˜no Los Objetos de Acceso a Datos DAO pueden usarse en Java para aislar a una aplicaci´on de la tecnolog´ıa de persistencia Java subyacente (API de persistencia Java). Utilizar Objetos de Acceso de Datos redunda en que la tecnolog´ıa subyacente puede ser actualizada o cambiada sin necesidad de cambiar otras partes de la aplicaci´on. desventajas : La flexibilidad tiene un coste. Cuando se a˜naden DAO’s a una aplicaci´on, la complejidad adicional de usar otra capa de persistencia incrementa la cantidad de c´odigo ejecutado durante tiempo de ejecuci´on. La configuraci´on de las capas de persistencia requiere en la mayor´ıa de los casos mucho trabajo. Las aplicaciones cr´ıticas con el rendimiento no deber´ıan usar este patr´on. 4.1.2. Utilizaci´on del patr´on Data Access Object en nuestra aplicaci´on El uso de este patr´on nos ha ofrecido varios beneficios para la persistencia de datos : Ha separado el acceso a los datos de la l´ogica de la aplicaci´on Oculta la API con la que se accede a los datos Centraliza todos los accesos a los datos en un capa independiente Cuando trabajamos con DAO, trabajamos en un mundo desconectado, donde nuestros datos deben persistir en objetos. Por lo tanto, cuando se realiza una operaci´on, abrimos la conexi´on a la base de datos, se ejecuta el comando, y si es una operaci´on de lectura, se vuelca el contenido hacia una estructura de datos y se cierra la conexi´on. Los DTO (Data Transfer Object) o tambi´en denominados VO (Value Object) son utilizados por DAO para transportar los datos desde la base de datos hacia la capa del modelo de la aplicaci´on y viceversa. En una aplicaci´on, hay tantos DAO’s como modelos. Es decir, en nuestra base de datos relacional, por cada tabla, tenemos un DAO. 44 Cap´ıtulo 4 4.2 Dise˜no de objetos Figura 14: El paquete casandra.android El resto de componentes se encuentran dividido en paquetes en funci´on de los objetos para los que intentan recabar o mostrar informaci´on Para las tareas del usuario (es.uma.casandra.tarea) La agenda (es.uma.casandra.agenda) Y el estado actual de la planificaci´on con es.uma.casandra.planificar, y es.uma.casandra.replanificar) 4.2.2. El paquete es.uma.casandra.core Como ya dijimos, es donde se encuentran las clases con que se modelan los elementos b´asicos de nuestra aplicaci´on, se compone de tres subpaquetes, tarea, planificacion y agenda. En el paquete es.uma.casandra.core.tarea contiene la clase Tarea y dos especificaciones de la misma que utilizamos en nuestros algoritmos de planificaci´on. El paquete es.uma.casandra.core.planificacion contiene las implementaciones de los algoritmos, as´ı como una clase ContextoPlanificacion, que intenta encapsular toda la informaci´on necesaria para recrear una planificaci´on y adem´as implementa los m´etodos necesarios para realizar un mecanismo de confirmaci´on del seguimiento de una planificaci´on existente. El paquete es.uma.casandra.core.agenda contiene las clases necesarias para presentar la agenda de un estudiante de un modo adecuado a nuestros algoritmos de planificaci´on, as´ı como varios m´etodos de utilidades para tratar el tiempo. 51 Cap´ıtulo 4 4.3 Metodolog´ıa de trabajo 4.2.3. El paquete es.uma.casandra.bbdd Este paquete contiene por un lado la clase CasandraDbHelper que es una extensi´on de la clase SQLiteOpenHelper suministrada por Android y es el punto principal de comunicaci´on del resto de la aplicaci´on con SQLite, pues es la responsable de obtener un objeto SqliteDatabase. Por otro lado tenemos una clase Adapter para cada tabla del modelo de datos, que contiene por una parte las sentencias DDL de definici´on de su tabla asociada para que sean utilizadas en el momento de la creaci´on de la base de datos por CasandraDbHelper, y por otra parte contiene una interfaz para permitir el acceso a los datos utilizando el patr´on Data Access Object tal y como viene comentado en el apartado de Patrones de dise˜no de la memoria a tal fin. 4.3. Metodolog´ıa de trabajo Para el desarrollo de nuestro proyecto, se ha optado por seguir las pautas de un modelo de desarrollo cl´asico de software. Seguir una metodolog´ıa de desarrollo, ayuda a organizar las actividades y conducir al proyecto de manera paulatina y l´ogica, hacia su finalizaci´on. Hemos usado un paradigma de ingenier´ıa del software basado en el desarrollo en cascada, estructurando el desarrollo de la aplicaci´on en un conjunto de fases de trabajo: fase de an´alisis: Se analizan y detectan las necesidades del sistema. fase de dise˜no: en la que nos planteamos c´omo vamos a resolver el problema. fase de codificaci´on: mediante la cual construimos la soluci´on. fase de pruebas: donde comprobamos que el producto es el deseado y que est´a bien construido. fase de correcci´on: donde se corrigen los errores. Vamos a pasar a comentar cada una de las fases de forma m´as detallada a continuaci´on 52 Cap´ıtulo 4 4.3 Metodolog´ıa de trabajo Figura 15: Modelo en cascada 4.3.1. Fase de an´alisis En esta fase se analizaron las necesidades a cubrir para los usuarios finales de la aplicaci´on, para determinar qu´e objetivos debe cubrir. De esta fase se obtuvo una identificaci´on completa de los requisitos a cubrir sin entrar en detalles de implementaci´on de las mismas. 4.3.2. Fase de dise˜no Se obtiene la descripci´on de la estructura global del sistema y la especificaci´on de lo que debe hacer cada una de sus partes, as´ı como la manera en que se combinan unas con otras. Es la fase en donde se realizan los algoritmos necesarios para el cumplimiento de los requerimientos del usuario as´ı como tambi´en los an´alisis necesarios para saber qu´e herramientas usar en la etapa de Codificaci´on. 4.3.3. Fase de codificaci´on Es la fase en donde se implementa el c´odigo fuente, desarrollando e integrando las distintas actividades que formar´an parte de la aplicaci´on, as´ı como la elaboraci´on del contenido gr´afico, la base de datos, etc ... haciendo en el proceso multitud de pruebas y ensayos para corregir errores. 4.3.4. Fase de pruebas En la fase de validaci´on, se comprobar´a que hemos construido lo que realmente se pretend´ıa en la fase de an´alisis y que cumple su funci´on. 53 Cap´ıtulo 4 4.3 Metodolog´ıa de trabajo 4.3.5. Fase de correcci´on En ´esta pen´ultima fase, se corregir´an todos los errores detectados en la fase de pruebas, y se a˜nadir´an mejoras en requisitos no funcionales en la medida de lo posible. 54 Cap´ıtulo 5 5. Herramientas utilizadas 5.1. Latex Para la redacci´on de la memoria se ha optado por la herramienta L A T EX ,los motivos que han llevado a esta elecci´on son los siguientes Es estable y multiplataforma. Latex permite redactar f´acilmente documentos estructurados, lo que da uniformidad y ayuda a una correcta ilaci´on de contenidos Controla en todo momento la numeraci´on y las referencias cruzadas. Construye ´ındices de contenidos, tablas o figuras. Ajusta los tama˜nos y tipos de letras seg´un la parte del documento en que se hallen. En cuanto a los inconvenientes, debido al uso en el anterior proyecto, buena parte de los inconvenientes del uso de L A T EX se ven atenuados, la curva de aprendizaje es menor al contar con un esquema v´alido de uso desde el primer momento de la redacci´on y se est´a familiarizado con los errores de compilaci´on y el entorno de ”desarrollo”, que a su vez automatiza el proceso de compilaci´on del texto. 5.2. Control versiones del c´odigo fuente El c´odigo de partida lo desarrollamos bajo el paraguas de un control de versiones distribuido, en concreto Git. Los motivos de uso de un SVC (System Version Control) es la flexibilidad a la hora del desarrollo ya que se gestionan f´acilmente los diversos cambios que se realizan sobre los elementos del software desarrollado y la configuraci´on del mismo, almacenando una versi´on, revisi´on o edici´on de un producto, en el estado en el que se encuentra dicho producto en un momento dado de su desarrollo o modificaci´on. A lo largo de esta ampliaci´on y mejora del software original se ha hecho un uso intensivo de esta herramienta, testando en distintas ramas de desarrollo dise˜nos nuevos de interfaz, soluciones alternativas en partes cr´ıticas del programa y la integraci´on de diferentes Apis. Para la realizaci´on del proyecto se ha elegido Git, tanto para el c´odigo fuente de la aplicaci´on Android, como para la elaboraci´on de la memoria. Si bien cualquiera de los diferentes sistemas de control de c´odigo fuente habr´ıa satisfecho nuestras necesidades para este proyecto, hemos elegido Git debido a que: 55 Cap´ıtulo 5 5.2 Control versiones del c´odigo fuente Es c´odigo abierto y gratuito. Es muy popular, y hay multitud de documentaci´on de calidad disponible Trabajar con ramas (branchs) es sencillo: Si se te ocurre una nueva caracter´ıstica, creas una nueva rama y comienzas a trabajar inmediatamente, saltar entre distintas ramas o fusionar ramas de nuevo con la principal no entra˜na mucha dificultad. Te permite almacenar (Stash) los cambios en tu rama actual, hacer trabajo en otra rama, comprobar los cambios y volver a la rama donde hicistes el stash. Git tiene integridad Todo en Git es verificado mediante una suma de comprobaci´on (checksum mediante un hash SHA-1) antes de ser almacenado, y es identificado a partir de ese momento mediante dicha suma. Esto significa que es imposible cambiar los contenidos de cualquier archivo o directorio sin que Git lo sepa. Esta funcionalidad est´a integrada en Git al m´as bajo nivel y es parte integral de su filosof´ıa. No puedes perder informaci´on durante su transmisi´on o sufrir corrupci´on de archivos sin que Git lo detecte. Git generalmente s´olo a˜nade informaci´on: Cuando realizas acciones en Git, casi todas ellas s´olo a˜naden informaci´on a la base de datos de Git. Es muy dif´ıcil conseguir que el sistema haga algo que no se pueda deshacer, o que de alg´un modo borre informaci´on. Como en cualquier SVC, puedes perder o estropear cambios que no has confirmado todav´ıa; pero despu´es de confirmar una instant´anea en Git, es muy dif´ıcil de perder, especialmente si env´ıas (push) tu base de datos a otro repositorio con regularidad. 56 Cap´ıtulo 5 5.2 Control versiones del c´odigo fuente Figura 16: Sistema control versiones distribuido fuente: Imagen tomada del libro “Pro Git, el libro oficial de Git” El dise˜no de Git se bas´o en BitKeeper y en Monotone, y resulta de la experiencia del dise˜nador de Linux, Linus Torvalds, manteniendo una enorme cantidad de c´odigo distribuida y gestionada por mucha gente, que incide en numerosos detalles de rendimiento, y de la necesidad de rapidez en una primera implementaci´on. Entre las caracter´ısticas m´as relevantes se encuentran: Fuerte apoyo al desarrollo no lineal: por ende rapidez en la gesti´on de ramas y mezclado de diferentes versiones. Git incluye herramientas espec´ıficas para navegar y visualizar un historial de desarrollo no lineal. Una presunci´on fundamental en Git es que un cambio ser´a fusionado mucho m´as frecuentemente de lo que se escribe originalmente, conforme se pasa entre varios programadores que lo revisan. Gesti´on distribuida: al igual que Darcs,BitKeeper,Mercurial,SVK,Bazaar yMonotone, Git le da a cada programador una copia local del historial del desarrollo entero, y los cambios se propagan entre los repositorios locales. Los cambios se importan como ramas adicionales y pueden ser fusionados en la misma manera que se hace con la rama local. Los almacenes de informaci´on pueden publicarse por HTTP, FTP, rsync o mediante un protocolo nativo, ya sea a trav´es de una conexi´on TCP/IP simple o a trav´es de cifrado SSH. Gesti´on eficiente de proyectos grandes: dada la rapidez de gesti´on de diferencias entre archivos, entre otras mejoras de optimizaci´on de velocidad de ejecuci´on. Todas 57 Cap´ıtulo 5 5.3 Git y Android Studio las versiones previas a un cambio determinado, implican la notificaci´on de un cambio posterior en cualquiera de ellas a ese cambio (denominado autenticaci´on criptogr´afica de historial). Los renombrados se trabajan bas´andose en similitudes entre ficheros: aparte de nombres de ficheros, pero no se hacen marcas expl´ıcitas de cambios de nombre con base en supuestos nombres ´unicos de nodos de sistema de ficheros, lo que evita posibles, y posiblemente desastrosas, coincidencias de ficheros diferentes en un ´unico nombre.[9] En la elecci´on original de un CVS se realiz´o una comparativa entre los distintos productos accesibles para desempe˜nar la tarea y realmente cualquiera de los analizados hubiera a priori satisfecho nuestras necesidades. (a) Subversion (b) Bazaar (c) Darcs (d) Git Figura 17: CVS’s valorados 5.3. Git y Android Studio Android Studio, es el nuevo IDE para desarrollo de aplicaciones en Android, es un entorno maduro que est´a en desarrollo por parte de Google en colaboraci´on con los propietarios del entorno IntelliJ sobre el que se basa, y ha desplazado a Eclipse que era de facto la antigua plataforma de desarrollo. Android Studio viene preparado para trabajar con m´ultiples SVC, entre ellos Git, as´ı como asistentes para configurar una cuenta en alg´un repositorio como www.github.com owww.bitbucket.org (el que ha sido nuestra elecci´on, debido a que ´este ´ultimo permit´ıa los repositorios privados). As´ı, con los par´ametros de nuestra cuenta en bitbucket.org, configuramos Android Studio para que pudiera conectarse con el servidor y mantener sincronizado el avance del proyecto. De este modo dispondremos de toda la funcionalidad de Git, pero de forma integrada con nuestro entorno de desarrollo, y adem´as teniendo un repositorio Git siempre sincronizado con todas las ventajas que conlleva como copia de respaldo del trabajo realizado sobre la que puedes ”navegar” a lo largo de toda la evoluci´on del mismo. 58 Cap´ıtulo 5 5.3 Git y Android Studio Figura 18: Ejemplo real de uso Git en entorno Android Studio 5.3.1. Gimp Gimp ha sido una herramienta muy ´util para la captura y tratamiento de los bocetos elaborados para el dise˜no de la aplicaci´on, ya que fueron realizados expresamente para la aplicaci´on y se tuvo que tratar las im´agenes desde el boceto a l´apiz hasta el gr´afico final que forma parte del programa. Gimp (GNU Image Manipulation Program) es un programa de edici´on de im´agenes digitales en forma de mapa de bits, tanto dibujos como fotograf´ıas. Es un programa libre y gratuito. Forma parte del proyecto GNU y est´a disponible bajo la Licencia p´ublica general (GPL) de GNU. Es un programa de manipulaci´on de im´agenes que ha ido evolucionando a lo largo del tiempo, ha ido soportando nuevos formatos, sus herramientas son m´as potentes, adem´as funciona con extensiones o plugins yscripts Gimp permite el tratado de im´agenes en capas, para poder modificar cada objeto de la imagen en forma totalmente independiente a las dem´as capas en la imagen, tambi´en pueden subirse o bajarse de nivel las capas para facilitar el trabajo en la imagen, la imagen final puede guardarse en el formato xcf de Gimp, que soporta capas, o en un formato plano sin capas, como png, bmp, gif, jpg, . . . Posee tambi´en muchas herramientas y filtros para la manipulaci´on de los colores y el aspecto de las im´agenes, como enfoque y desenfoque, eliminaci´on o adici´on de manchas, sombras, mapeado de colores as´ı como un men´u con un cat´alogo de efectos y tratamientos de las im´agenes. 59 Cap´ıtulo 5 5.4 Inkscape 5.4. Inkscape Es un editor de gr´aficos en formato vectoriales SVG (que son imagenes digitales formadas por objetos geom´etricos independientes como segmentos, pol´ıgonos, arcos, . . . , cada uno de ellos definido por distintos atributos matem´aticos de forma, de posici´on, de color, .. . ) , gratuito, libre y multiplataforma. Las caracter´ısticas de SVG soportadas incluyen formas b´asicas, trayectorias, texto, canal alfa, transformaciones, gradientes, edici´on de nodos, exportaci´on de svg apng, agrupaci´on de elementos, etc. Tiene como objetivo proporcionar a los usuarios una herramienta libre de c´odigo abierto de elaboraci´on de gr´aficos en formato vectorial escalable (SVG) que cumpla completamente con los est´andares XML, SVG yCSS2. En combinaci´on con las herramientas anteriormente expuestas se puede obtener una correcta integraci´on de las im´agenes (elaboradas por nosotros para este proyecto) de una manera homog´enea, desde un conjunto de esbozos a l´apiz como estos Figura 19: Im´agenes elaboradas para el proyecto a´un sin tratar fuente: Fotograf´ıa dibujos originales para proyecto 60 Cap´ıtulo 5 5.6 Android El n´ucleo act´ua como una capa de abstracci´on entre el hardware y el resto de las capas de la arquitectura. El desarrollador no accede directamente a esta capa, sino que debe utilizar las librer´ıas disponibles en capas superiores. De esta forma tambi´en nos evitamos el hecho de quebrarnos la cabeza para conocer las caracter´ısticas precisas de cada tel´efono. Si necesitamos hacer uso de la c´amara, el sistema operativo se encarga de utilizar la que incluya el tel´efono, sea cual sea. Para cada elemento de hardware del tel´efono existe un controlador (o driver) dentro del kernel que permite utilizarlo desde el software. El kernel tambi´en se encarga de gestionar los diferentes recursos del tel´efono (energ´ıa, memoria, etc.) y del sistema operativo en s´ı: procesos, elementos de comunicaci´on (networking), etc. 5.6.2. Bibliotecas Android incluye un conjunto de bibliotecas de C/C++ usadas por varios componentes del sistema. Estas caracter´ısticas se exponen a los desarrolladores a trav´es del marco de trabajo de aplicaciones (framework de Android; algunas son: System C library (implementaci´on biblioteca C est´andar) Webkit (navegador) Bibliotecas multimedia (formatos de audio, imagen y v´ıdeo) OpenGl (motor gr´afico) SSL (cifrado de comunicaciones) FreeType (fuentes de texto) SQLite (Base de datos) Se sit´ua justo sobre el kernel la componen las bibliotecas nativas de Android. Est´an escritas en CoC++ y compiladas para la arquitectura hardware espec´ıfica del tel´efono. Estas normalmente est´an hechas por el fabricante, quien tambi´en se encarga de instalarlas en el dispositivo antes de ponerlo a la venta. El objetivo de las librer´ıas es proporcionar funcionalidad a las aplicaciones para tareas que se repiten con frecuencia, evitando tener que codificarlas cada vez y garantizando que se llevan a cabo de la forma ”m´as eficiente”. 67 Cap´ıtulo 5 5.6 Android 5.6.3. Runtime Desde la versi´on 5.0 de Android 5.0 la m´aquina virtual Dalvik ha sido sustituida por ART, los beneficios en cuanto a rendimiento de esta nueva m´aquina virtual logran reducir el tiempo de ejecuci´on hasta en un 33 %. Dalvik era la antigua m´aquina virtual de Android, en la que cada aplicaci´on corre su propio proceso, con su propia instancia de la m´aquina virtual Dalvik,Dalvik fue escrito de forma que un dispositivo pudiera arrancar m´ultiples m´aquinas virtuales de forma eficiente y ejecutar archivos en el formato Dalvik Executable (.dex), el cual est´a optimizado para un uso muy eficiente de la memoria.Dalvik era una variaci´on de la m´aquina virtual de Java, por lo que no es compatible con el bytecode Java.Java se usa ´unicamente como lenguaje de programaci´on, y los ejecutables que se generan con el SDK de Android tienen la extensi´on .dex que era espec´ıfica para Dalvik, y por ello no podemos correr aplicaciones Java en Android ni viceversa La principal diferencia entre Dalvik yART, reside en que Dalvik ejecuta una maquina virtual interpretando el c´odigo al tiempo que se inicia la aplicaci´on. En cambio, ART b´asicamente compila las aplicaciones antes de que sean ejecutadas. Lo que significa que una primera instalaci´on de una determinada aplicaci´on llevar´a mucho m´as tiempo, y que las aplicaciones ocupar´an m´as espacio del internal storage, pero al mismo tiempo, ya que las aplicaciones estar´an completamente compiladas; tan pronto como est´en instaladas en el sistema el tiempo que llevar´a abrir la aplicaci´on ser´a muy inferior al de hacerlo con la m´aquina virtual Dalvik, y adem´as habr´ıa otra ventaja derivada de esto, como la parte de compilaci´on ha sido llevada a cabo solo una vez (en la instalaci´on de la aplicaci´on) la carga del procesador es menor lo que redunda en una mejor vida de la bater´ıa y un mejor rendimiento global del sistema. Una peque˜na comparativa entre Dalvik yArt quiz´as arroje un poco de luz [10]. 68 Cap´ıtulo 5 5.6 Android Dalvik Art Usa el enfoque Just-In-Time (o JIT) (es grosso modo una compilaci´on de partes del c´odigo seg´un se necesita y suelen formar parte de un int´erprete). Lo cual redunda en un menor espacio de almacenamiento requerido, pero en un mayor tiempo de carga de las aplicaciones Usa un enfoque (Ahead-Of-Time (AOT)), el cual compila la aplicaci´on en el momento en que son instaladas, obteniendo como resultado unos mejores tiempos de carga y un menor uso del procesador (ya que s´olo se compila una vez) La Cach´e se va construyendo a lo largo del tiempo, luego los tiempos de arranque son m´as r´apidos La Cache es construida en el arranque, luego reiniciar el dispositivo requiere de un tiempo significativamente mayor Trabaja mejor con dispositivos que dispongan de poca memoria interna, ya que el espacio ocupado es menor Consume mucha m´as memoria interna, ya que almacena las aplicaciones compiladas adem´as de los APKs Cuadro 1: Comparativa m´aquinas virtuales Dalvik yArt 5.6.4. Framework Los desarrolladores tienen acceso completo a los mismos API’s del framework usados por las aplicaciones base. La arquitectura est´a dise˜nada para simplificar la reutilizaci´on de componentes; cualquier aplicaci´on puede publicar sus capacidades y cualquier otra aplicaci´on puede luego hacer uso de esas capacidades (sujeto a reglas de seguridad del framework). Este mismo mecanismo permite que los componentes sean reemplazados por el usuario. La siguiente capa est´a formada por todas las clases y servicios que utilizan directamente las aplicaciones para realizar sus funciones. La mayor´ıa de los componentes de esta capa son bibliotecas Java que acceden a los recursos de las capas anteriores a trav´es de la m´aquina virtual Dalvik. Siguiendo el diagrama encontramos: Activity Manager: Se encarga de administrar la pila de actividades de nuestra aplicaci´on as´ı como su ciclo de vida. Windows Manager: Se encarga de organizar lo que se mostrar´a en pantalla. B´asicamente crea las superficies en la pantalla que posteriormente pasar´an a ser ocupadas por las actividades. Content Provider: Esta librer´ıa es muy interesante porque crea una capa que encapsula los datos que se compartir´an entre aplicaciones para tener control sobre c´omo se accede a la informaci´on. Views: En Android, las vistas son los elementos que nos ayudar´an a construir las interfaces de usuario: botones, cuadros de texto, listas y hasta elementos m´as avanzados como un navegador web o un visor de Google Maps. 69 Cap´ıtulo 5 5.6 Android Notification Manager: Engloba los servicios para notificar al usuario cuando algo requiera su atenci´on mostrando alertas en la barra de estado. Un dato importante es que esta biblioteca tambi´en permite jugar con sonidos, activar el vibrador o utilizar los led’s del tel´efono (si los tuviese). Package Manager: Esta biblioteca permite obtener informaci´on sobre los paquetes instalados en el dispositivo Android, adem´as de gestionar la instalaci´on de nuevos paquetes. Con paquete nos referimos a la forma en que se distribuyen las aplicaciones Android, estos contienen el archivo .apk, que a su vez incluyen los archivos 1.dex con todos los recursos y archivos adicionales que necesite la aplicaci´on, para facilitar su descarga e instalaci´on. Telephony Manager: Con esta librer´ıa podremos realizar llamadas o enviar y recibir SMS/MMS, aunque no permite reemplazar o eliminar la actividad que se muestra cuando una llamada est´a en curso. Resource Manager: Con esta librer´ıa podremos gestionar todos los elementos que forman parte de la aplicaci´on y que est´an fuera del c´odigo, es decir, cadenas de texto traducidas a diferentes idiomas, im´agenes, sonidos o layouts. Location Manager: Permite determinar la posici´on geogr´afica del dispositivo Android mediante GPS o redes disponibles y trabajar con mapas. Sensor Manager: Nos permite manipular los elementos de hardware del tel´efono como el aceler´ometro, giroscopio, sensor de luminosidad, sensor de campo magn´etico, br´ujula, sensor de presi´on, sensor de proximidad, sensor de temperatura, etc. C´amara: Con esta librer´ıa podemos hacer uso de la(s) c´amara(s) del dispositivo para tomar fotograf´ıas o para grabar v´ıdeo. Multimedia: Permiten reproducir y visualizar audio, v´ıdeo e im´agenes en el dispositivo. 5.6.5. Aplicacion La capa superior de la de pila software la forman las aplicaciones. En esta capa conviven todas las aplicaciones del dispositivo, tanto las que tienen interfaz de usuario como las que no, tanto las nativas (programadas en C o C++) como las programadas en Java y tanto las que vienen de serie con el dispositivo como las instaladas por el usuario. Aqu´ı est´a tambi´en la aplicaci´on principal del sistema: Inicio (Home), tambi´en llamada a veces lanzador (launcher), porque es la que permite ejecutar otras aplicaciones proporcionando la lista de aplicaciones instaladas y mostrando diferentes escritorios donde se 70 Cap´ıtulo 5 5.6 Android pueden colocar accesos directos a aplicaciones o incluso peque˜nas aplicaciones incrustadas (o widgets), que son tambi´en aplicaciones de esta capa. Lo principal a tener en cuenta de esta arquitectura es que todas las aplicaciones, ya sean las nativas de Android (proporcionadas por Google), las que incluye de serie el fabricante del tel´efono o las que instala despu´es el usuario utilizan el mismo marco de aplicaci´on para acceder a los servicios que proporciona el sistema operativo . Esto implica dos cosas: Podemos crear aplicaciones que usen los mismos recursos que usan las aplicaciones nativas (nada est´a reservado o inaccesible) Podemos reemplazar cualquiera de las aplicaciones del tel´efono por otra de nuestra elecci´on. Este es el verdadero potencial de Android y lo que lo diferencia de su competencia: un gran control por parte del usuario del software que se va a ejecutar en su dispositivo m´ovil [11],[12]. 5.6.6. Modelo de datos Android aporta sus propios conceptos para almacenar y compartir datos entre aplicaciones, aunque en ´ultima instancia dichos conceptos se terminen implementando mediante enfoques tradicionales (en la mayor´ıa de los casos). Disponemos de : Sistema de Archivos Tanto internos de la aplicaci´on como externos por medio de la compatibilidad con tarjetas SD SQLite Una base de datos relacional (SQLite), que no tiene todas las funciones de los productos de base de datos cliente/servidor comerciales, pero ofrece todo lo necesario para almacenamiento local de datos, a la vez que resulta r´apida y sencilla de utilizar. SharedPreferences Es el objeto que permite almacenar el estado global de la aplicaci´on, se pueden crear privadas de la aplicaci´on o hacerlas accesibles para otras aplicaciones. Se accede a ella a trav´es del contexto (Context) desde el que se trabaje, muchas clases de Android tienen una referencia a Context (e.g. Activity o Service) 71 Cap´ıtulo 5 5.6 Android Uri Un enfoque basado en URI para compartir datos entre aplicaciones denominado Content Provider, como cada aplicaci´on se ejecuta en su propio proceso (normalmente), y los archivos y datos que almacena no son accesibles para otras aplicaciones, ´esta es una buena manera de compartir, consultar, a˜nadir, actualizar o eliminar informaci´on entre distintas aplicaciones. En nuestra aplicaci´on se ha hecho uso de los Content Provider, sobre todo a la hora de utilizar la gesti´on del calendario con una parte de la API proporcionada por Google Calendar Provider, perteneciente a la Android Open Source Project (AOSP), luego no es de c´odigo cerrado y no estamos encadenados a ninguna aplicaci´on en concreto. Esto implica que pr´acticamente cualquier aplicaci´on que gestione calendarios en Android podr´a visualizar los resultados de las planificaciones). Adem´as, esto nos permite almacenar los intervalos resultantes de las planificaciones como eventos de un calendario que se integra de manera natural con los dem´as calendarios que hallan en el sistema (si bien con elementos distintivos como el color en el que aparece el evento, nombre, etc. . . ), luego las aplicaciones de agenda de Android pueden mostrar los eventos de todos los calendarios integrados de manera homog´enea. e.g. en un mismo d´ıa aparecer´an tanto el resultado de las planificaciones de nuestra aplicaci´on como otros eventos introducidos por el usuario y otras aplicaciones La herramienta de almacenamiento de datos que utilizamos con mayor profusi´on es la base de datos SQLite, por la naturaleza de la aplicaci´on hemos considerado que es la mejor soluci´on para tratar adecuadamente la no despreciable cantidad de informaci´on que puede llegar a generar. El modelo relacional es el de la figura 24 72 Cap´ıtulo 5 5.6 Android Figura 24: Modelo de datos de la aplicaci´on BBDD SQLite 73 Cap´ıtulo 6 6. Conclusi´on 6.1. Tests de rendimiento Para evaluar el rendimiento de la aplicaci´on, se ha procedido a ejecutar una serie de tests que emulan peticiones que ser´ıan de uso com´un a la aplicaci´on, variando el n´umero de tareas, intervalos de tiempo disponible, y duraci´on de las mismas para los distintos motores de planificaci´on disponibles. Se cre´o un c´odigo Java que obten´ıa los promedios de 50 ejecuciones consecutivas de los tres motores de planificaci´on (Rms,Dms,Edf ) aplicados sobre tareas espor´adicas de 5 horas de duraci´on intentando planificar de manera sucesiva 5, 10, 20 y 50 tareas en una plantilla semanal cuyos intervalos disponibles para trabajar estaban distribuidos en fragmentos de 60 minutos, a lo largo de toda la semana. Grosso modo parte del fragmento de c´odigo utilizado para testar los tiempos de respuesta ser´ıa ´este private static long medir(IPlanificador algoritmo, Integer nTareas, Integer dTareas, Integer nIntervalos, Integer dIntervalos) { Calendar cal = new GregorianCalendar(); Agenda agenda = new Agenda(...); List<IntervaloPlantillaSemanal> plantilla = new ArrayList<IntervaloPlantillaSemanal>(); for(DIASSEMANA d : diasDeLaSemana){ ... plantilla.add(new IntervaloPlantillaSemanal(d, ini, cal.getTime(), "free" ,true, 5)); ... } agenda.asignaIntervalosPlantillaSemanal(plantilla); List<Tarea> tareas = new ArrayList<Tarea>(); for(long i=0; i< nTareas; i++){ 74 Cap´ıtulo 6 6.1 Tests de rendimiento tareas.add(new TareaEsporadica(i, "tarea"+i, dTareas, dIntervalos, iniAgenda, finAgenda)); } long ini = System.nanoTime(); try { algoritmo.planificar(agenda, tareas); } long fin = System.nanoTime(); return fin-ini; } Para obtener la duraci´on se hac´ıa una llamada a System.nanoTime() antes y despu´es de la ejecuci´on de cada algoritmo en cada una de las 50 iteraciones acumulando el resultado para hacer el promedio. Para las pruebas se utiliz´o una m´aquina virtual de Java java-7-openjdk-armhf ejecutando la aplicaci´on desde la linea de comandos en un equipo con un procesador ARM Cortex-A8 800MHz y sistema operativo Debian GNU/linux jessie/sid desde consola. Con los siguientes resultados mostrados en la figura 25 5 10 20 50 0 0,50 1,0 1,5 2,0 2,5 3,0 Tiempo promedio de ejecución de los algoritmos DMS RMS EDF Número de tareas Segundos Figura 25: Gr´afica de tiempos promediados para los distintos motores de planificaci´on 75 Cap´ıtulo 6 6.2 Uso de librer´ıa Optaplaner N´umero de tareas Promedio DMS Promedio RMS Promedio EDF 5 Tareas 0,40707” 0,40666” 0,43150” 10 Tareas 0,86023” 0,85885” 0,92299” 20 Tareas 1,38599” 1,38345” 1,51861” 50 Tareas 2,30011” 2,29361” 2,71523” Con estos datos se puede apreciar que el algoritmo con asignaci´on de prioridades din´amicas (EDF) requiere un mayor tiempo de CPU debido a que adem´as de hacer un reparto (en funci´on de las prioridades) de las tareas por cada intervalo disponible, debe ordenar tras cada intervalo ya planificado la lista de tareas con sus nuevas prioridades (en funci´on de cuan cercana est´e cada una de su deadline correspondiente, como exige dicho algoritmo), en la gr´afica se aprecia ese coste adicional, tanto mayor cuanto m´as tareas haya. 6.2. Uso de librer´ıa Optaplaner De los siguientes resultados de rendimiento sobre la elecci´on de los intervalos adecuados para las planificaciones teniendo en cuenta las preferencias del usuario efectuadas en [8] se puede deducir que: Figura 26: Comparativa asignacion intervalos En igualdad de condiciones, es decir con b´usqueda local los tiempos obtenidos por nuestro desarrollo y por Optaplanner son equivalentes, el reparto es casi inmediato, Casandra usa el heur´ıstico de conocer qu´e intervalos son los deseados por el usuario y genera intervalos en funci´on de dicha informaci´on haciendo pr´acticamente un reparto en un orden de tiempo lineal y Optaplanner lo resuelve usando la misma informaci´on pero con 76 Anexo A.2 Definir tareas Para insertar una tarea podemos utilizar el bot´on ’Nueva Tarea’ que aparece en la parte inferior. Figura 30: Manual - Introducir tarea peri´odica ´ Esta puede ser de dos tipos peri´odica o espor´adica, la captura anterior se refiere a la peri´odica ya que as´ı se ha hecho la elecci´on en el apartado seleccione el tipo de tarea. Se le pone un nombre, y se le indica tambi´en el tiempo que durar´a. 83 Anexo A.2 Definir tareas Figura 31: Manual - Elegir d´ıas de la semana para tarea peri´odica Esto significa que esta tarea se planificar´a a lo largo de los l´ımites de la agenda, los d´ıas elegidos (aparece una ventana de di´alogo que nos permite elegir qu´e dias de la semana la vamos a realizar) Es la opci´on adecuada para definir aquellas tareas como hacer ejercicio, o practicar con alg´un instrumento, que no tienen una cantidad de horas para ser terminadas. Una vez hecha la elecci´on se pulsar´a el bot´on insertar tarea. Y ya formar´a parte del conjunto de tareas de tu aplicaci´on. 84 Anexo A.2 Definir tareas El otro tipo son las tareas espor´adicas, estas requieren algo m´as de informaci´on como una fecha de inicio, de finalizaci´on (ambas se introducen pulsando las fechas que aparecen a ambos lados de “<TAREA>”) y la cantidad de tiempo estimado para la realizaci´on total de la tarea, por ello var´ıa un poco la interfaz de entrada de datos, resultando Figura 32: Manual - Introducir tarea espor´adica El tiempo introducido en este tipo de tareas (al igual que en las peri´odicas) es muy importante, si no se lograra reunir el total del tiempo estimado para la realizaci´on de la tarea antes de la fecha de finalizaci´on de la misma, la aplicaci´on reaccionar´a diciendo que la planificaci´on no es factible con los datos introducidos, pero eso se ver´a en el apartado A.4 planificar. 85 Anexo A.2 Definir tareas Una vez se hayan introducido una serie de tareas en nuestra aplicaci´on, el acceso al apartado de tareas, muestra un listado de las mismas, y el mismo bot´on de inserci´on de nueva tarea en la parte inferior de la pantalla del dispositivo. A continuaci´on se puede ver un ejemplo con datos de prueba. Figura 33: Manual - Listado tareas con inserciones Lo primero a destacar es que ahora, aparte del nombre de la tarea, en la columna de la derecha, aparecen dos tipos de datos, y estos tipos de datos vienen en funci´on del tipo de tarea de que se trate Si es una tarea espor´adica aparece una fracci´on que indica la cantidad de tiempo que efectivamente se lleva realizado de la tarea en total, es decir tiempo trabajado tiempo total de la tarea e.g. 0 tiempo total de la tarea en una tarea que est´a por comenzar Si se trata de una tarea peri´odica aparecen una serie de letras que no son m´as que las iniciales de los d´ıas de la semana en que se espera que tal tarea se lleve a cabo 86 Anexo A.2 Definir tareas Figura 34: Manual - Edici´on y borrado en el listado de tareas En esta ventana, se pueden editar y borrar las tareas a nuestro antojo sin m´as que mantener una pulsaci´on larga sobre el elemento de la lista deseado, y aparecer´a el siguiente men´u Cuando existe una planificaci´on en curso, nos aparece la opci´on adicional de incluir la tarea seleccionada en la planificaci´on, como se muestra en la figura. 87 Anexo A.3 Definir horario y tiempos libres en la Agenda A.3. Definir horario y tiempos libres en la Agenda Figura 35: Manual - Agenda vac´ıa de horarios La primera vez que se entra en la Agenda, en la parte inferior de la pantalla ocurre lo mismo que cuando se accede a Tareas, que no existe ning´un horario aun y muestra la lista vac´ıa, pero la parte superior, se pueden definir los l´ımites temporales de la Agenda. 88 Anexo A.3 Definir horario y tiempos libres en la Agenda Para cambiar los l´ımites de la agenda, s´olo hay que efectuar una pulsaci´on larga sobre la fecha que viene por defecto, si se hace una pulsaci´on normal aparece un bocadillo en pantalla explicando qu´e hacer para cambiar la fecha. Figura 36: Manual - Agenda creaci´on de un nuevo horario Si se quiere a˜nadir un nuevo horario, hay que pulsar el texto + Insertar horario y se acceder´a a otra actividad que nos va a pedir el nombre del horario 89 Anexo A.3 Definir horario y tiempos libres en la Agenda Figura 37: Manual - Agenda con horarios insertados Una vez introducido e insertado (pulsando el bot´on de Introducir nuevo horario, se volver´a al men´u principal de Agenda, donde ahora en el listado aparecer´an todos los horarios que se hayan introducido. 90 Anexo A.3 Definir horario y tiempos libres en la Agenda Figura 38: Manual - Insertar intervalo horario con agenda activa El siguiente paso, una vez insertado un nombre para un horario, es precisamente hacer el horario, esto es introducir una serie de intervalos de tiempo, de dos tipos, Aquellos intervalos que est´an fijados por obligaciones (e.g. clases) Aquellos intervalos de tiempo en los que se pueden realizar trabajos, estudiar, etc. . . 91 Anexo A.3 Definir horario y tiempos libres en la Agenda Figura 39: Manual - Insertar intervalo horario con agenda no activa Para introducir cualquiera de estos intervalos, primero hay que pulsar de la lista de horarios aquel en el que se quiera trabajar. Y entraremos en la siguiente actividad, que es la inserci´on de intervalos horarios por cada d´ıa de la semana. Cuando se accede a un horario reci´en creado, ´este aun no contiene intervalos. En esta ventana se pueden observar varias cosas, la primera son los d´ıas de la semana que aparecen en la parte superior de la ventana, al deslizarnos sobre este men´u nos permitir´a movernos a lo largo de los dias de una semana e introducir los intervalos de tiempo para un d´ıa en concreto. Justo bajo los d´ıas de la semana aparece un texto que dice que ´este es un horario activo, como la aplicaci´on permite introducir tantos horarios como se considere oportuno (pero no tiene sentido (en principio) planificar tareas sobre m´as de un horario a la vez), en todo momento s´olo habr´a un horario activo a la vez. Cuando se genera un horario nuevo, se convierte por defecto en el horario activo y si hubiera alg´un otro activo en ese momento dejar´ıa de estarlo. Si se accede a un horario que no es activo este mensaje lo indicar´ıa diciendo ¿Quieres que sea ´este el horario activo para la agenda? , si se pulsa sobre el texto, lo haremos el horario activo de nuestra aplicaci´on. 92 Anexo A.4 Planificar Figura 46: Manual - Resultado de una planificaci´on El resultado a la hora de visualizarlo con el calendario de Android (probablemente variar´a seg´un la aplicaci´on que se utilice y la versi´on de la misma) y se tendr´a acceso a la funcionalidad que aporte dicha aplicaci´on. Si la planificaci´on ha tenido ´exito, entonces nuestra aplicaci´on saltar´a a la aplicaci´on que tenga en su dispositivo para visualizar calendarios a la fecha en la que est´e el primer intervalo planificado introducido. Siempre podr´a acceder a su calendario y ver esta planificaci´on, (aunque ´estas planificaciones pueden ir cambiando con el tiempo ver apartado siguiente), y se podr´an hacer las operaciones habituales con los eventos de un calendario normal de Android. 99 Anexo A.4 Planificar Figura 47: Manual - No se puede planificar Si la planificaci´on no ha tenido ´exito, es decir hemos tenido o muy poco tiempo disponible o demasiada carga de trabajo, en tal caso saltar´a un di´alogo de aviso con una serie de sugerencias y una ventana que indica qu´e tarea ha vencido su fecha de expiraci´on. 100 Anexo A.5 Confirmaci´on de Tareas A.5. Confirmaci´on de Tareas Figura 48: Manual - Procrastinar tareas Una vez hecha una planificaci´on, se har´a un seguimiento de las tareas a ver si se est´an llevando a cabo o no a lo largo del tiempo, es decir: Cada vez que se accede a la aplicaci´on se comprueba la fecha actual del sistema y la fecha en la que se accedi´o por ´ultima vez a la aplicaci´on, con el intervalo de tiempo calculado entre la ´ultima vez que se accedi´o a la aplicaci´on y el d´ıa de hoy se mira qu´e tareas deben estar hechas (acumula el tiempo de cada intervalo planificado para cada una de las tareas en este tiempo), y se pregunta al usuario al entrar si las ha hecho o no. Esto se hace mostrando al usuario la lista de tareas de modo que seleccione aquellas que realmente ha llevado a cabo. Con esta nueva informaci´on el sistema recalcula la planificaci´on actualizando los eventos del calendario de manera autom´atica. Otra cosa a tener en cuenta es que en el men´u inicial el bot´on de Planificar, una vez hecha una planificaci´on cambia su estado a Ver planificaci´on de modo que cuando se acceda a la aplicaci´on y ya haya una planificaci´on en marcha se pueda simplemente consultar. 101 Anexo A.6 Opciones del men´u A.6. Opciones del men´u Figura 49: Manual - Men´u de opciones Estas son todas las opciones que aparecen al pulsar el bot´on de men´u del dispositivo electr´onico. A continuaci´on describiremos brevemente el funcionamiento de cada una Eliminar planificaci´on actual Si se quiere lanzar una nueva planificaci´on y descartar la existente, elija esta opci´on Ver tareas fijas en Calendario Esta opci´on hace que en el calendario de la aplicaci´on no solo se muestre las tareas planificadas, sino que tambi´en aparezcan las fijas Datos de ejemplo Introduce unos cuantos datos de ejemplo, para explorar la aplicaci´on sin necesidad de ir insertando informaci´on Borrar Calendarios Elimina los eventos generados en el calendario de la aplicaci´on. Usar con precauci´on, para que vuelvan a aparecer habr´ıa que lanzar de nuevo una planificaci´on Eliminar BBDD sirve para resetear el estado de la aplicaci´on, eliminar´a absolutamente toda la informaci´on de tareas horarios y planificaciones, debe usarse con mucha precauci´on 102 Referencias [1] Inc. Any.do. http://www.any.do/, 2016. App Android Any.do. [2] Alex Baker. https://play.google.com/store/apps/details?id=org.tasks, 2016. App Android Astrid. [3] Trish Sarson Chris Gane. Structured systems analysis : tools and techniques. PrenticeHall, first edition, 1979. [4] Juan Antonio Fern´andez Madrigal. Planificaci´on de tareas en sistemas en tiempo real. Departamento de Ingenier´ıa de Sistemas y Autom´atica, Universidad de M´alaga, 2010. [5] Roque Mar´ın Morales Jos´e T Palma M´endez. Inteligencia Artificial. McGraw Hill, first edition, 2008. [6] Red Hat. http://www.optaplanner.org/, 2016. Optaplanner. [7] Ralph Johnson y John Vlissides Erich Gamma, Richard Helm. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley Professional, first edition, 1994. [8] Elisabeth Freeman Erich Freeman. Head First Design Patterns. O’Reilly, first edition, 2004. [9] Scott Chacon. Pro Git. Apress, first edition, 2009. [10] Aatif Khan. What is art? http://www.addictivetips.com/android/art-vs-dalvikandroid-runtime-environments-explained-compared/, 2014. [11] Aurora Rodr´ıguez. http://androideity.com, 2016. Aurora Rodr´ıguez. [12] Google. http://developer.android.com, 2016. Android Developers.