10. Gestión de memoria y recolector de basura. Este capítulo aborda uno de los aspectos mas críticos acerca del funcionamiento de la maquina virtual de la plataforma J2ME, la gestión de memoria. La criticidad de esta función radica en que la limitación en memoria que caracteriza a los sistemas móviles. Es necesario que la ocupación en memoria de la que haga uso la maquina virtual sea la mínima posible y que además las tareas relativas a dicha gestión de memoria sean lo más rápidas posibles.´ Uno de los aspectos mas relevantes en la gestión de memoria es el recolector de basura que es el módulo encargado de escanear la memoria ocupada por la KVM para ver si esta siendo usada por ella y poder liberar en caso de que no sea así. En este capítulo primeramente se ofrece una visión global de la gestión de memoria en los sistemas informáticos, los distintas técnicas que se emplean y los problemas que se pueden presentar. Posteriormente se tratarán las dos tareas principales de gestión de memoria: • •

Reserva de memoria. Recolector de basura.

La reserva de memoria es la operación por la cual se toma parte de la memoria virtual disponible en el sistema operativo para uso de una aplicación. Existen diversas técnicas para ello entre ellas: • • •

First Fit. Buddy System. Suballocators.

En cuanto a la recolección de basura, implica la reutilización automática de la memoria. Es decir, que el programador no se tiene que preocupar por liberar la memoria de un objeto cuando este no se este usando sino que es una tarea automática. En al actualidad hay multitud de algoritmos diferentes de recolección de basura entre los cuales cabe destacar: •

Recolectores de traza (Tracing collectors): o Recolector de marcas (Mark-Sweep collection). o Recolector de copias (Copying collection). o Recolector incremental (Incremental collection). o Recolector conservador (Conservative collection).

•

Contadores de referencias (Referente counts): o Contador simple de referencias (Simple referente counting). o Contador diferido de referencias (Deferred referente counting). o Contador de referencias de 1 bit (One-bit referente counting). o Contador de referencias por pesos (Weighted referente counting).

Particularizando, la maquina virtual de la plataforma J2ME emplea para alojar los objetos en memoria el algoritmo de mejor aproximación (first fit) y como recolector de basura un recolector de marcas. Así se vera como se implementan dichos algoritmos en la KVM y como es posible configurar de forma sencilla su funcionamiento.

10.1. Introducción. La gestión de memoria es un complejo campo dentro de la ingeniería informática actual, es por ello que se han desarrollado multitud de técnicas distintas orientadas a mejorar su eficiencia. Algunas plataformas tales como el antiguo MS-DOS o Windows utilizan sistemas específicos de gestión de memo ria en ocasiones más complejos y menos genéricos. La gestión de memoria normalmente se divide en tres áreas de actuación si bien los límites entre dichas áreas suele ser difuso y en ocasiones inexistente: • • •

Hardware. Sistema operativo. Aplicación informática.

En la mayoría de los sistemas de información actuales las tres áreas se encuentran presentes en mayor o menor medida formando una serie de capas que interconectan el nivel aplicación que los usuarios ejecutan con el hardware de la plataforma que soporta las aplicaciones. Si bien normalmente cuando se habla de gestión de memoria se hace referencia a la gestión de memoria a nivel de aplicación informática. La gestión de memoria a nivel hardware concierne de forma exclusiva a los dispositivos electrónicos que sirven de almacenamientos tales como discos duros, compact-disc, memory usb… También se incluyen en este apartado las memorias RAM y la memoria cache de los terminales informáticos. Los sistemas operativos utilizan una memoria en la cual alojan los distintos programas que se ejecutan por petición del usuario y los eliminan de la memoria cuando terminan de ejecutarse. El sistema operativo mantiene por encima de la memoria física una memoria virtual que simula dos aspectos: • •

La computadora tiene más memoria de la que realmente tiene. Los programas usan toda la memoria de la computadora.

10.2. Gestión de memoria en programas informáticos. La gestión de memoria a nivel de aplicación implica aportar la memoria que necesaria para los objetos y las estructuras de datos de los programas a partir de un conjunto de recursos limitados y ofertados por el sistema operativo. Además se ha de asegurar que dicha memoria es reciclada cuando ya no es demandada.

Dado que prácticamente la totalidad de las aplicaciones informáticas no pueden predecir de forma razonable la memoria futura que necesitara, esta reserva y gestión de memoria es una tarea que debe recaer en un componente también software externo. Existen dos componentes que implican este sistema de gestión informática: • •

Ubicador: alojamiento en memoria. Recolector: reciclado de memoria.

Cuando un programa requiere un bloque de memoria, el gestor de memoria software debe alojar dicho bloque de memoria en la memoria virtual que el sistema operativo pone a su disposición. Esta es la tarea que desempeña el ubicador, del cual existen múltiples implementaciones. Cuando los bloques de memoria ya han sido alojados pero los datos que contienen no son requeridos en el entorno de ejecución del usuario estos bloques deben ser reciclados para ser empleados en otro punto del entorno. Esta es la tarea que desempeña el recolector. Básicamente existen 2 aproximaciones al reciclado de memoria: • •

Gestión manual: el programador decide cuando debe ser reciclada la memoria y como. Gestión automática: el gestor de memoria del sistema realiza el reciclado de la memoria.

La gestión de memoria ya sea manual o automática implica una serie de algoritmos complejos de optimización y rendimiento acotados por una serie de limitaciones a saber entre las que se encuentran: • • •

Ocupación CPU: tiempo de proceso de CPU que conlleva la ejecución del recolector. Tiempo entre ejecuciones: tiempo que transcurre entre ejecuciones de colector. Ocupación de memoria: espacio en memoria necesario para la administración y fragmentación de memoria tanto interna como externa.

•

10.3. Principales problemas en la gestión de memoria. El problema principal que tiene que solventar cualquier gestor de memoria esta relacionado se encuentra cuando tras haber ocupado parte de la memoria con ciertos datos esta debe ser liberada para que se pueda volver a reutilizar. Esta es una tarea que puede parecer bastante sencilla pero que en la realidad es muy compleja y que ha venido constituyendo un campo de estudio amplio por si solo. En una situación ideal la mayoría de los programadores no deberían preocuparse por situaciones derivadas de la gestión de memoria. Desafortunadamente existen muchas situaciones y formas por las cuales una pobre práctica de gestión de memoria puede afectar a la robustez y velocidad

de los programas independientemente de que el lenguaje usado para construirlo soporte gestión manual o automática de memoria. Algunos de los problemas típicos con los cuales nos podemos encontrar son: •

Liberación prematura o pérdida de puntero : denominado en nomenclatura inglesa dangling pointer se produce cuando se libera la memoria asociada a un objeto determinado cuando aun existen en el marco de ejecución del programa referencias a él. Esto provoca normalmente un error fatal que acaba con la ejecución del programa informático o bien con un funcionamiento claramente anómalo. Esta es una situación que se suele dar cuando se emplea gestión de memoria manual.

•

Fuera de memoria: denominado memory leak se da cuando un programa demanda de forma continuada y seguida mas memoria agotando la memoria disponible en el sistema. Este problema suele estar relacionado con deficiencias en la programación de las aplicaciones o inadaptación de las mismas al hardware en el que se ejecutan.

•

Fragmentación externa : esta situación se da cuando la memoria tiene muchos bloques pequeños de memoria libres intercalados con otro bloques mayores aún en uso. De esta forma si el programa informático demanda una cierta cantidad de memoria mayor de trozo libre de mayor tamaño presente y el gestor de memoria no es capaz de reorganizar la memoria se da la sensación al usuario de que el dispositivo no tiene suficiente memoria cuando no es el caso.

•

Localización pobre de referencias : este problema esta fuertemente relacio nado con la forma en la cual el hardware y los sistemas operativos actuales gestionan la memoria. Cuanto mas cercano estén entre sí los accesos consecutivos a memoria mejor es el rendimiento de dichos accesos. Es por ello que el gestor de memoria debe procurar agrupar lo mas cerca posible en memoria aquellos objetos que sean accesible cercanos en tiempo de ejecución, algo que no siempre se da.

•

Diseño inflexible: este problema esta derivado de la solución adoptada a la hora de implementar el gestor de memoria. Y es que muchos gestores de memoria parten de una serie de suposiciones fijas tales como tamaños de bloques de memoria, patrones de referencias o tiempo de vida de objetos. Si estos supuestos son erróneos o no se adaptan a la memoria a controlar el rendimiento del gestor de memoria disminuye.

•

Interfaces de conexión en sistema complejos : si los objetos que componen el programa informático han de pasar a través de distintos módulos las interfaces que regulan estos pasos deben también gestionar su propia memoria. En muchos casos esa gestión recae en uno de los módulos lo cual puede provocar problemas de inconsistencia en la estructura de memoria.

10.4. Gestión manual de memoria.

La gestión de memoria manual es aquella en la cual el programador tiene control directo sobre la memoria que debe ser reciclada. Normalmente esto se logra mediante llamadas a funciones de gestión de zonas de memoria (por ejemplo la funciones malloc y calloc en C) o bien por construcciones implícitas del lenguaje que afectan a la pila de ejecución como son las variables locales. La clave en la gestión de memoria manual es que es el programador el que debe decidir donde, cuando y como se ha de reciclar cierta cantidad de memoria sin que el gestor de memoria tome nunca esta decisión. Las ventajas que ofrece la gestión manual de memoria son: • •

El programador sabe en cada momento en que estado esta la memoria. Algunos gestores de memoria manual funcionan mejor que los automáticos siempre y cuando el programador haga un buen uso de él. Las principales y más numerosas desventajas son:

• • • •

El programador necesita repetir gran cantidad de código para gestionar la memoria. La gestión de memoria ocupa una parte significativa de cualquier modulo que se desarrolle tanto en esfuerzo de desarrollo como en rendimiento. Normalmente la gestión manual de memoria requiere una sobretasa de memoria por objeto. Los errores derivados de la gestión de memoria son comunes y de consecuencias fatales para el producto final que se pretende obtener.

Es muy común para lo s programadores cuando se enfrentan ante un gestor de memoria manual deficiente o inadecuado generar código para duplicar el comportamiento del gestor llegando incluso alojar grandes bloques en memoria y dividirlos para ser usados eficientemente o bien para reciclar bloques internamente. Esto es lo que se conoce como suballocators (subalojadores), mediante ellos se pueden aprovechar conocimientos especiales acerca del programa que se pretende desarrollar y su comportamiento. Estos suballocators facilitan la labor del programador encapsulando la tareas de gestión de memoria si bien al final resultan s ineficientes a no ser que sean desarrollados por verdaderos expertos que conozcan la memoria hardware y software que se esta empleando. Los siguientes lenguajes de programación usan actualmente gestión manual de memoria si bien poseen extensiones para la gestión de memoria bastante conservadores (menos eficientes y mas seguras): C, C++, Algol,Cobol,Fortran,Pascal.

10.5. Gestión automática de memoria. La gestión automática de memoria se puede considerar en realidad como un servicio, una parte de un lenguaje de programación o una extensión del mismo que automáticamente recicla la memoria que un programa no va a volver a usar. Los gestores automáticos (también conocidos como recolectores de basura o simplemente recolectores) usualmente hacen su trabajo reciclan aquellos objetos que no son

alcanzables desde ninguna variable del programa, es decir objetos a los cuales no apunta ningún puntero). Las principales ventajas de la gestión automática de memoria son: • • • •

El programador se libera de todas las tareas de gestión de memoria. Las diferencias entre distintos módulos son claras (no hay que preocuparse de la memoria compartida entre ambos módulos). Hay muy pocos errores relacionados con la memoria. La gestión de memoria suele ser más eficiente.

Las pocas desventajas que ofrece este método son: • •

La memoria que es alcanzable desde alguna parte del programa se mantiene aun cuando no vaya a ser usada más. Los gestores automáticos de memoria tienen limitada disponibilidad.

Existen muchas maneras de desarrollar recolectores automáticos de memoria de los cuales veremos los más extendidos. La mayor parte de los lenguajes de programación actuales y mas en uso emplean este tipo de recolectores: Java, Basic, Dylan, Erlang, Haskell, JavaScript, Lisp, ML, Modula-3, Perl, Postcript lenguaje, Prolog, Phyton, Scheme,…

10.6. Ubicador de memoria (memory allocator). La ubicación de memoria es el proceso de asignar bloques de memoria a un usuario ante una petición del mismo. Típicamente el ubicador recibe la memoria desde el sistema operativo como un número pequeño de largos bloques de memoria que debe dividir en bloques mas pequeños para satisfacer las peticiones (normalmente de tamaños reducidos) de lo usuarios a través de los programas que estos ejecutan. Existen múltiples implementaciones posibles de un ubicador de memoria entre las cuales podemos destacar: • • •

Primera aproximación (first fit). Sistema de cooperación (buddy system). SubUbicadores (suballocators).

Veamos a continuación de forma resumida una explicación de cómo opera cada uno de ellos.

10.6.1.

First Fit.

En el algoritmo de mejor aproximación el ubicador guardar una lista de los bloques de memoria libres que existen (conocida como lista libre). De forma que cuando recibe una petición de un bloque de memoria recorre la lista libre hasta encontrar un bloque que satisfaga la demanda de memoria. Si el bloque de memoria es sensiblemente mayor del requerido normalmente se divide en dos bloques: uno que es entregado al usuario que hizo la petición y el otro se queda en la lista de bloques de memoria libres. Este algoritmo funciona razonablemente bien y asegura que las ubicaciones se realizan rápidamente. En su integración con el recolector de basura hay diversas opciones atendiendo a la forma en que los bloques de memoria reciclados se añaden a la lista: •

Memory location: este método no es muy rápido pero soporta eficientemente la unión en la lista libre de bloques adyacentes (denominados bloques coalescence). Este método reduce por tanto la fragmentación y puede llegar a mejorar las localizaciones de referencia en memoria.

Figura 10.1: Algoritmo first fit básico.

•

Increasing size: este método es equivalente al anterior con la salvedad de que en la búsqueda de bloques de memoria en la lista libre se escoja siempre el bloque cuyo tamaño sea más cercano al requerido. Cono este método el bloque que queda en la lista es demasiado pequeño para ser usado de nuevo.

Figura 10.2: Algoritmo best first fit.

•

Decreasing size: este método es el contrario del anterior buscando en la lista libre el bloque de memoria mayor disponible. Este método mejora la fragmentación externa pero la ubicación es extremadamente rápida.

Figura 10.3: Algoritmo worst first fit.

•

Increasing time since last use: este método es el que ofrece mayor velocidad a la hora de añadir bloques de memoria reciclados a la lista libre puesto que son añadidos al principio de la lista. Esto mejora notablemente la localización de referencias (puesto que los bloques usados conjuntamente en alguna operación no quedan repartidos por toda la memoria) pero puede llevar una situación anómala de fragmentación externa.

10.6.2.

Buddy System.

En un sistema de este tipo el ubicador únicamente ubicará bloques de cierto tamaño y emplea para ello múltiples listas de segmentos libres una por cada tamaño de bloque permitido. Los tamaños permitidos son usualmente potencias de dos o forman parte de secuencias de Fibonacci por lo que cualquier bloque excepto los mas pequeños pueden ser divididos en bloques mas pequeños de tamaños permitidos. Cuando el ubicador recibe una petición de memoria este redondea el tamaño de memoria requerido al tamaño permitido más próximo y devuelve el primer bloque de memoria libre de la lista correspondiente. Si la lista correspondiente esta vacía, el ubicador divide un bloque de mayor tamaño de alguna lista disponible y devuelve al usuario uno de los bloques alojando el restante en la lista apropiada. Cuando los bloques son reciclados, debe existir algún módulo adicional que una los bloques de memoria adyacentes en un bloque de mayor tamaño y que se corresponda con alguna de las listas disponibles. Para hacer esta tarea más sencilla las listas de bloques libres son ordenadas internamente en base a la dirección de los segmentos de memoria que contienen. Se puede ver un ejemplo de este mecanismo en la siguiente figura:

Segmento de memoria libre antes de ser ocupado

Segmento depués de alojar 8Kb

Segmento después de alojar 10Kb; notar que se genera un espacio inservible de 6kb

Figura 10.4: Algoritmo buddy system.

Un sistema de ubicación de este tipo puede trabajar muy bien o muy mal dependiendo de cómo los tamaños de los bloques permitidos interactúan con los segmentos típicos de memoria de las peticiones que normalmente llegan al ubicador. El redondeo que se hace al recibir la petición de memoria para adaptarla a uno de los tamaños permitidos suele provocar una cierta pérdida de memoria denominada

fragmentación interna. Cuanto mayor sea el número de tamaños de bloques permitidos menor será la fragmentación interna.

10.6.3.

Suballocators.

Existen muchos ejemplos de aplicaciones que incluyen código adicional para la gestión de memoria, este código es lo que se conoce como suballocators. Un suballocator obtiene largos segmentos de memoria dividiéndolos y gestionando su entrega a la aplicación que hizo la petición de memoria. Los motivos que llevan a implementar este tipo de módulos son: • • •

Solucionar deficiencias encontradas en el gestor de memoria propio del lenguaje usado. Adaptar la gestión de memoria a las características específicas de una aplicación o un conjunto de ellas. Ofrecer servicios añadidos no presentes en el gestor de memoria.

En general, este tipo de métodos suele ser menos eficiente que tener un único gestor de memoria bien diseñado y con una interfaz flexible. Además al hacer que el gestor de memoria este dividido en capas (usualmente 2) se potencia la probabilidad de que se generen errores.

La mayor parte de las aplicaciones tienen uno o dos tamaños fijos de segmentos de memoria que son los que mayoritariamente son demandados. Uno de los suballocators más comunes consiste precisamente en filtrar los bloques de memoria que ofrece el gestor a la aplicación de forma que a la aplicación le lleguen segmentos siempre del mismo tamaño lo cual reduce enormemente la fragmentación externa. Sin embargo el manejo de estos módulos puede resultar muy peligroso en el caso en que los requerimientos específicos de la memoria varían, pues si se mantiene el mismo suballocator puede dar lugar a graves pérdidas de memoria o incluso provocar daños en el hardware.

10.7. Recolector de memoria (garbage collector). Existen múltiples implementaciones para la recolección de zonas de memoria que no estén en uso dentro del marco de los gestores automáticos de memoria. Básicamente consiste en determinar que bloques de memoria no son referenciados en un programa. Podemos establecer una clasificación de las implementaciones más comunes: •

Recolectores de traza (Tracing collectors): o Recolector de marcas (Mark-Sweep collection). o Recolector de copias (Copying collection). o Recolector incremental (Incremental collection).

o Recolector conservador (Conservative collection). •

Contadores de referencias (Referente counts): o Contador simple de referencias (Simple referente counting). o Contador diferido de referencias (Deferred referente counting). o Contador de referencias de 1 bit (One-bit referente counting). o Contador de referencias por pesos (Weighted referente counting).

Hay que tener en cuenta que existen técnicas híbridas generadas por combinación de uno o más de las técnicas básicas de recolección de basura. De entre todos estos tipos de recolectores de basura la maquina virtual java genérica emplea varios de ellos todos encuadrados en la familia de los tracing collectors. Por ello explicaremos brevemente el funcionamiento de los tracing collectors más comunes.

10.7.1.

Mark-Sweep Collection.

En un algoritmo mark-sweep de recolección de memoria, el colector examina las variables del programa que se esta ejecutando y cualquier bloque de memoria que sea referenciado en algún momento es añadido a una lista de objetos a examinar. Para cada uno de los objetos presentes en la lista se fija una bandera (mark) en el bloque para indicar que aun es referenciado y por tanto no ha de eliminarse de memoria. Además se añade a la lista cualquier otro objeto que contenga referencias a estos primeros objetos añadidos y que no hayan sido marcados aún. De esta forma todos los objetos accesibles desde el entorno de ejecución del programa quedan marcados. En una segunda fase, el colector examina la memoria en busca de segmentos que no han sido marcados. Si encuentra alguno lo devuelve al ubicador para que vuelva a usarlo. Por ejemplo supongamos que tenemos el siguiente caso:

Figura 10.5: Ejemplo de referencias.

En la figura, el bloque es directamente accedido desde una variable de programa, y los bloques 2 y 3 son accedidos de forma indirecta. Los bloques 4 y 5 no pueden ser alcanzados desde el programa. El primer paso sería marcar el bloque 1 y almacenar en una lista los bloques 2 y 3 para ser procesados posteriormente. El segundo paso sería marcar el bloque 2. El tercer paso es marcar el bloque 3 pero no debería recordar que el bloque 2 ya había sido marcado. En la segunda fase del algoritmo (sweep) el recolector ignorará los bloques marcados (1,2,3) y reciclara el resto (4,5).

El uso de este algoritmo tiene 2 claras desventajas: • •

Tiene que escanear la memoria completa en uso antes de que esta sea liberada. Tiene que ejecutarse el algoritmo de forma completa ya que si es interrumpido puede dar lugar a problemas de convergencia de memoria.

Si un sistema requiere una respuesta en tiempo real o interactiva, entonces este algoritmo mark-sweep puede no resultar muy eficiente, aún así existen muchas variantes de este algoritmo.

10.7.2.

Copying collector.

Este es otro algoritmo de recolección de basura basado en el uso de trazas. Después de que muchos bloques de memoria han sido alojados y liberados repetidas veces pueden ocurrir dos problemas: •

La memoria en uso esta profundamente divida en pequeños segmentos, lo cual provoca que no podamos alojar grandes segmentos de memoria que han de ser separados en segmentos más pequeños. Esto es conocido como fragmentación externa.

•

La memoria en uso esta muy dispersada a lo largo de la memoria completa lo cual provoca un bajo rendimiento de la memoria virtual o memoria cache de los sistemas operativos más comunes. Este problema es conocido como localización pobre de referencias.

Una técnica que puede solventar ambos problemas es el algoritmo copying collector. Un recolector de basura que emplee este algoritmo puede mover bloques de memoria ya alojados a lo largo de la memoria completa y ajustar las referencias a dicho bloque a la nueva localización del mismo. Esta es una técnica muy potente y que además puede ser combinada con otros tipos de algoritmos de recolección de basura como por ejemplo con el algoritmo mark-sweep.

Figura 10.6: Algoritmo copying collector.

Las principales desventajas del algoritmo copying collector son: • • • •

Es difícil combinarlos con los colectores incrementales (que veremos mas adelante) debido a que todas la referencias deben ser ajustadas de forma consistente. Es difícil combinarlo con los colectores conservativos (que veremos mas adelante) debido a que las referencias no pueden ser ajustadas de forma privada por cada tarea de sistema. Es necesario de forma temporal un almacenamiento extra de memoria cuando coexisten la copia antigua de un bloque que se va a mover y la copia nueva del mismo. El procedimiento de copiar bloques de un lugar a otro de la memoria conlleva un cierto proceso de CPU extra.

10.7.3.

Incremental collection.

Los algoritmos de recolección de basura mas antiguos estaban obligados a que durante la ejecución de los mismos no pudieran ser interrumpidos. Esto provocaba que sistemas interactivos tuvieran que interrumpirse mientras se recolectaba basura en la memoria, haciendo de la presencia del recolector de basura un inconveniente mas que una ventaja. Afortunadamente, existes técnicas modernas conocidas como incremental collection que permiten al recolector de basura ser ejecutado en una serie de fases de pequeña duración para que entre fases el programa pueda seguir ejecutándose. En este contexto, el programa que usa y modifica los bloques es conocido como mutator.

Mientras el colector de basura esta determinando que bloques de memoria son alcanzables por el mutator, este se encuentra ocupado alojando o modificando bloques de memoria.

Figura 10.7: Alojar bloques de memoria durante la reclamación de recolector.

10.7.4.

Conservative garbage collection.

Aunque el primer recolector de basura fue inventado en 1958, han sido diseñados e implementados sin la posibilidad del uso de recolectores de basura. Normalmente es bastante complejo el poder añadir un recolector de basura a este tipo de sistemas, pero existe una técnica denominada conservative garbage collection que puede ser usada en estos casos. El problema usual con este tipo de lenguajes es que no son capaces de proveer al recolector de basura con información fiable de la estructuras almacenadas en la memoria con lo cual el recolector de basura no puede saber lo que es un puntero y lo que no lo es. Un recolector de basura conservativo asume que cualquier dato puede ser un puntero, de esta forma el recolector realiza una búsqueda en memoria de un dato que pueda parecer un puntero y realiza una copia de dicho puntero en una zona de memoria donde impedir que sea reciclado.

Advertir que dado que el recolector no conoce a ciencia cierta que localizaciones de memoria contienen punteros, no puede ser combinado con algoritmos copying collectors. El algoritmo copying collector necesita conocer donde están los punteros para poder actualizarlos cuando los bloques en memoria han sido movidos.

Si bien este algoritmo parece muy sencillo y parece que puede originar que grandes cantidades de memoria queden sin reciclar en la práctica no es así, sobre todo si se mejora el algoritmo con algunos refinamientos.

10.8. Gestión de memoria KVM. 10.8.1.

Introducción.

La KVM al igual que la maquina virtual Java genérica usa como lenguaje de programación Java que soporta gestión automática de memoria, de hecho es probablemente el gestor de memoria mas conocido en la actualidad un referente para todos los demás. Para la ubicación de objetos en memoria de entre los distintos algoritmos que hemos comentado en apartados anteriores la KVM emplea el de mejor aproximación y para la recolección de basura emplea un complejo algoritmo de tipo mark-and-sweep.

10.8.2. Mapeo en memoria de objetos y gestión de memoria. Previo a la explicación del funcionamiento del recolector de basura de la KVM conviene estudiar como se guardan en memoria los objetos que emplean los programas java que ejecuta la maquina virtual. Cada objeto alojado en memoria va precedido de una cabecera que provee información detallada acerca del tipo y tamaño del objeto en cuestión. La longitud de la cabecera es de 1 palabra (32 bits). De esta forma los objetos se almacenan en memoria guardando una estructura como la siguiente:

Figura 10.8: Representación objetos KVM.

donde: • •

gc Header: cabecera de información de objeto. Class ptr: puntero al objeto.

•

Mhc field: código de monitorización.

Un aspecto importante a reseñar es la ausencia de un manejador de objetos lo cual lleva al uso de referencias de memoria directas a diferencia del resto de implementaciones de la JVM en las cuales se emplean referencias a memoria indirectas. Derivado de esta estructura de almacenaje de objetos se impone que solo se pueden usar punteros a posiciones de memoria que este precedidas por la correspondiente cabecera del objeto que estamos referenciando. Por ello no se pueden emplear punteros a campos de datos dentro de un objeto directamente. Esta restricción supone una importante simplificación en el proceso de recolección de basura. La cabecera de información que llevan todos los objetos es una estructura de 32 bits que como hemos dicho contiene importante información de administración. En particular, la cabecera del objeto almacena el tamaño del objeto, su tipo y otros dos bits más de configuración (Static y Mark bits):

Figura 10.9: Cabecera de los objetos KVM.

La longitud especificada en la cabecera es la del objeto al que esta asociado excluyendo la propia cabecera y en bloques de 4 bytes, de forma queda una longitud de 1 indica que el objeto tiene 8 bytes: 4 bytes de cabecera + 4 bytes del objeto en si. El campo tipo de la cabecera mantiene información acerca del tipo del objeto que como veremos mas adelante es empleado por el recolector de basura para escanear los campos de datos correctamente. El Static bit se emplea únicamente para implementaciones de la KVM sobre la Palm. En antiguas implementaciones de la KVM este bit indicaba en caso de que estuviera activo que el objeto estaba alojado en memoria estática y que por lo tanto no puede ser movido. El Mark bit se emplea para marcar los objetos desde el recolector de basura cuando este opera sobre la memoria. Este es el bit de marcado que se emplea en los algoritmos mark-and-sweep de recolección de basura. Dicha cabecera se representa mediante una estructura denominada headerStruct que tiene 4 enteros: Struct headerStruct{ Int size :24; Int type :6; Int markBit :1;

Int staticBit

:1;

}; El recolector de basura mantiene además una lista enlazada de la memoria libre en el dispositivo en la cual se ejecuta la maquina virtual y basada en memoria segmentada. Cada segmento de memoria libre es precedido por una cabecera con los dos campos siguientes: • •

Size: la cantidad de memoria del segmento. Next: puntero al siguiente segmento libre.

El campo size es de 1 palabra de 32 bits y la forma de almacenar la información en él es similar al que se emplea en la cabecera de los objetos y que hemos comentado en la sección anterior. De esta forma solo los 24 bits superiores son empleados mientras que los 6 inferiores han de valer 0 para que la palabra pueda ser reconocida como un campo de una cabecera. Este campo size refleja el tamaño de segmento excluyéndose al mismo. El último segmento de memoria tiene como valor de puntero 0 para cerrar la lista. Estos segmentos libres de memoria tienen un tamaño mínimo de 2 palabras de 2 bits debido a que es el tamaño mínimo necesario para alojar en el un objeto, de tal manera que cualquier espacio de memoria menor de 64 bits es combinado con otros segmentos hasta alcanzar el tamaño mínimo. En la práctica eso sucede en contadas ocasiones. Estos segmentos de memoria se representan en el código mediante una estructura denominada chunkStruct: Struct chunkStruct{ Long size; CHUNK next; }; La gestión y mapeo de objetos en memoria de entre las empleadas por los diferentes sistemas y que se han comentado en el apartado 2 de este capítulo es el de primera aproximación (first fit) debido a varios motivos entre ellos: • • •

Baja carga de procesado. Funcionamiento razonablemente eficiente. Asignación rápida de memoria.

Estos motivos redundan en una ocupación menor del tiempo del procesador además de una necesidad de recursos menor por parte del mismo esencial en los dispositivos móviles hacia los cuales esta dirigido la KVM.

10.8.3.

Algoritmos de recolección de basura.

La versión 1.3 JDK (la maquina virtual de Java genérica) incluye tres técnicas de recolección de basura y la versión 1.4.1 incluye hasta seis técnicas distintas y una

docena de comandos para controlar esta gestión de memoria. Cada una de estas técnicas usa una estrategia para identificación y reclamación de objetos perdidos diferente y la interacción con el usuario también es diferente. Esto es debido a que diferentes tipos de aplicaciones tienen diferentes requerimientos de recolección de basura, así una aplicación en tiempo real requiere pausas de recolección muy frecuentes y de corta duración mientras que una aplicación de desarrollo estándar puede tolerar pausas más largas e impredecibles a favor de una mejora de la salida que ofrece el programa al usuario. El recolector de basura original de la KVM esta basado en un depurado copying collector de Cheney presentado en Septiembre de 1970. Este colector emplea un algoritmo iterativo para recorrer objetos lo que lo hace que disminuya la carga de procesado frente a los colectores que emplean algoritmos recursivos. Sin embargo también tenía los problemas típicos de los copying collectors y es que requiere el doble de espacio en memoria respecto a la que el programa Java a gestionar ocupa. Evidentemente este último aspecto va en contraposición de la filosofía de reducción de memoria que persigue la KVM. Precisamente para lograr que la KVM no ocupara tanto espacio en memoria se opto por la implementación de un nuevo recolector de basura en su versión 1.0. Este colector esta basado en un algoritmo mark-sweep, estático y directo. Desde la versión 1.0 de la KVM el colector no mueve los objetos por lo que es mucho más simple que el copying collector original de copia comentado en el párrafo anterior. Sin embargo la fragmentación de memoria del nuevo colector provoca que haya mas riesgo de que la máquina virtual se quede sin memoria. Finalmente en la versión 1.0.2 de la KVM se ha añadido un nuevo recolector y compresor de basura mucho mas preciso y que puede ser activado o desactivado mediante la macroconstante ENABLE_HEAP_COMPACTION..

10.8.4. Implementación de Sun de las operaciones de gestión y mapeo de memoria. Procederemos a comentar de forma exhaustiva la solución que la KVM de Sun adopta para localizar los objetos de los programas Java que se ejecutan en la memoria virtual del sistema en el cual se ejecuta. Cuando se ejecuta un programa Java en la maquina virtual se van creando una serie de objetos en tiempo de ejecución con un código que debe ser accesible posteriormente desde otros puntos del programa. Es por ello que este objeto debe ser alojado en la memoria virtual de la plataforma sobre la que opera. Para alojar estos objetos en la implementación que estamos estudiando se emplean las rutinas de bajo nivel malloc y calloc muy comunes en lenguajes que requieren gestión de memoria manual como hemos comentado en la introducción de este capítulo. Las implementaciones específicas de Sun de estas operaciones son: cell* mallocObject(long size, GCT_ObjectType type) cell* callocObject(long size, GCT_ObjectType type)

Ambas reciben como parámetros el tamaño del objeto en palabras de memoria (32 bits) y el tipo de objeto según el colector de basura para el cual queremos hacer la reserva de memoria. Igualmente ambas operaciones devuelven un puntero a la primera palabra de la zona de memoria reservada en caso de éxito o bien genera un error fatal en caso de error. La única diferencia entre ambas es que callocObject inicializa la región de memoria con zeros para lo cual hace uso de la función de sistema memset: memset(result, 0, size next, thisChunk = thisChunk->next)

{ //iteraciones sobre lista de segmentos libres }

o En cada uno de los segmentos se calcula la diferencia de tamaño entre el segmento en cuestión y la memoria que se desea reservar: long overhead = SIZE(thisChunk->size) + HEADERSIZE - size;

o El criterio a la hora de determinar si el segmento es suficientemente grande es el tamaño estándar de cabecera de los objetos. Si la diferencia de tamaño antes calculada es mayor o igual que el umbral (HEADERSIZE) se modifica el tamaño del segmento con la memoria que se quiere reservar y se devuelve el puntero a dicho segmento saliendo de la iteración. El segmento se mantiene dentro de la lista enlazada de segmentos libres para que pueda seguir usándose por otros objetos: thisChunk->size = (overhead - HEADERSIZE) result);

A continuación se invoca al recolector de basura indicándole que necesita un espacio en memoria igual al tamaño total de la memoria para así asegurarnos que liberara suficiente espacio en memoria: garbageCollect(AllHeapEnd - AllHeapStart);

Si el tamaño de memoria liberada no supera un límite que es: newPermanentSpace < (cell *)FirstFreeChunk + 2 * HEADERSIZE

se genera un error fatal indicando que no hay suficiente memoria libre para asignar como memoria estática. Si hay suficiente memoria el tamaño de memoria estática libre (newFreeSize) que se ha generado es: newPermanentSpace - (cell *)FirstFreeChunk – HEADERSIZE

o Se inicializa dicho espacio de memoria pues es un método de tipo calloc y se fija el tamaño del primer segmento de memoria libre en el tamaño de memoria estática calculada: memset(newPermanentSpace, 0,PTR_DELTA(CurrentHeapEnd, newPermanentSpace));

o Finalmente se realiza una llamada a la función callocObject que ya puede realizar la reserva de memoria de la forma estándar tomando el primer segmento de la lista enlaza de segmentos de memoria libre pues hemos ajustado su tamaño al necesario en la reserva de memoria del objeto. Se devuelve el puntero a la zona de memoria que se puede emplear para almacenar el objeto estático. o Si no se supera el tamaño de memoria estática actual simplemente se devuelve el puntero a la zona de memoria donde es puede alojar el objeto sin inicializar dicha zona de memoria. 10.8.4.1.

Funciones auxiliares de gestión de memoria.

En la implementación de la KVM que estamos estudiando se emplean una serie de funciones para objetivos auxiliares como puede ser operaciones de debug. Así por ejemplo tenemos las funciones getObjectSize que devuelve el tamaño de un objetos en palabras de memoria o getObjectType que devuelve el tipo GCT de un objeto, ambas funciones consultando la cabecera del objeto en cuestión. Otro tipo de funciones auxiliares que se pueden encuadrar en esta categoría son las relacionadas con operaciones de debug y así tenemos las operaciones getObjectTypyStr que a partir de un tipo de objeto GCT devuelve la cadena de caracteres que lo identifica como tal y printObject que vuelca al log del sistema el contenido de un objeto. El módulo de gestión de los y errores de la KVM es tratado en un capítulo diferente dada su gran incidencia y significado en el funcionamiento de la maquina virtual.

10.8.5. Implementación de Sun de las operaciones de inicialización de memoria. Llegados a este punto y habiendo visto como los objetos Java que de generar e un programa son alojados en la memoria dinámica o estática según sea el caso cabe preguntarse acerca del estado inicial de la memoria y de todas las referencias y punteros que se emplean en las operaciones de gestión de memoria que se han estudiando en el apartado anterior. Además tan importante como la inicialización de la memoria es disponer de un mecanismo para tratar esta memoria una vez que la maquina virtual deja de ejecutarse. Este mecanismo debe ser capaz de liberar la memoria que se había empleado y dejarla en el estado anterior a la inicialización.

El mecanismo de inicialización del gestor de memoria de la KVM se recoge en la función InitializeMemoryManagement y se realiza en tres fases: • • •

Reserva inicial de la memoria. Inicialización de las marcas de los objetos raíz, marcas que serán empleadas por el algoritmo mark and sweep de recolección de basura. Inicialización de la memoria que requiere un mecanismo adicional de borrado.

Esta mecanismo es lanzado automáticamente al iniciar la maquina virtual dentro del método KVM_Start (). Como ya hemos comentado en la introducción el algoritmo de recolección de basura mark and sweep se basa en establecer marcas sobre aquellos objetos que aun sean referenciados dentro del marco de ejecución del programa. Como veremos mas adelante la implementación de Sun para la KVM mantiene una lista enlazada de los distintos objetos raíces de los programas que están ejecutándose en la maquina virtual que se denomina GlobalRoots. Cada uno de los elementos de esta lista esta formado por una estructura del tipo: typedef union cellOrPointer { cell cell; cell *cellp; cell **cellpp; /* For global roots */ /* Occasionally needed by GC */ char *charp; char **charpp; } cellOrPointer;

es decir se compone de la dirección del propio objeto, un puntero al mismo y un puntero a puntero a dicha dirección. Estos objetos son los puntos iniciales del árbol del cual parten el resto de objetos. De esta manera al inicializar el gestor de memoria se añaden a esta lista dos elementos que son: •

La lista donde se recogen todos los hilos de ejecución: GlobalRoots[index++].cellpp = (cell **)&AllThreads;

•

La lista de los objetos a los cuales se deben aplicar un mecanismo adicional de borrado, operación que se lleva a cabo al finalizar el gestor de memoria como veremos mas adelante: GlobalRoots[index++].cellpp = (cell **)&CleanupRoots;

En cuanto a la reserva inicial de la memoria genérica que constituye la primera fase del proceso de InitializeMemoryManagement se encuentra recogido en la función InitializeHeap(). Esta función reserva una cierta cantidad de memoria inicial de la siguiente forma:

•

Tomando el tamaño de memoria que necesita ya su valor por defecto o un valor pasado por línea de comandos al iniciar la maquina virtual se reserva la memoria haciendo uso de una implementación particular de la plataforma: cell *allocateHeap(long *sizeptr, void **realresultptr)

Sea cual sea la plataforma objetivo esta función devuelve el puntero a la zona de memoria reservada o null en caso de que no haya sido posible en cuyo caso se genera un error fatal indicando al usuario que no hay suficiente memoria para inicializar la maquina virtual. •

Se actualiza las referencias CurrentHeap y CurrentHeapEnd (puntero al inicio y fin de la memoria de la KVM) a la zona de memoria reservada, referencias que son empleadas tanto por el recolector de basura como el gestor de hilos de la KVM.

•

Dado que estamos inicializando la memoria tenemos que marcar esta memoria reservada por la maquina virtual en el sistema como memoria libre para la propia maquina virtual. Esto se realiza actualizando FirstFreeChunk (variable que referencia al primer elemento de memoria libre disponible) con el puntero devuelto por la función allocateHeap y con el tamaño de toda la memoria reservada.

•

Como ya se comento anteriormente existe una memoria estática o permanente cuyo mecanismo de reserva implica también un autocrecimiento del mismo en base a las necesidades en cada momento. Ese espacio de memoria permanente va desde CurrentHeapEnd hasta AllHeapEnd (que nos marca el final de la memoria que es accesible por la KVM) e inicialmente ambos límites coinciden por el mecanismo de autocrecimiento ya comentado.

10.8.5.1.

Parametrización de la inicialización de memoria.

Si bien el mecanismo de inicialización de memoria es cerrado si que se puede modificar tanto el rendimiento del mismo como el tamaño de la memoria inicial a reservar. Como ya se ha comentado e capítulos anteriores dentro del fichero main.h se recogen una serie de opciones para parametrizar mecanismo como este que nos ocupa en este apartado. Así podemos modificar: •

•

tamaño por defecto de memoria necesaria para arrancar la maquina virtual. El valor en esta implementación es 65024 bytes si bien puede ser modificado mediante la directiva adecuada o a través de la línea de comandos al arrancar la maquina virtual. CHUNKY_HEAP: esta opción permite a la maquina virtual poder alojar la memoria de la que hace uso en distintos segmentos de memoria no consecutivos lo cual es muy útil en dispositivos con grandes limitaciones de memoria pues permite una mejor ocupación de la misma. El valor por defecto es desactivado, en caso de ser activado no se inicializa la DEFAULTHEAPSIZE:

referencia FisrFreeChunk puesto que la memoria a reservar ya no ha de ser consecutiva.

10.8.6. Implementación de Sun de las operaciones de finalización de la memoria. Como ya hemos comentado en el apartado anterior la maquina virtual de Java y por lo tanto también la KVM debe de incorporar un mecanismo para liberar la memoria virtual de la plataforma sobre la que se ejecuta una vez que la KVM vaya a finalizar su ejecución. Este mecanismo se encuentra recogido en la función FinalizeMemoryManagement.

Este mecanismo es genérico para cualquier plataforma y versión de la KVM que se emplee y es ejecutado dentro de método KVM_Cleanup que se ejecuta justo antes de finalizar la maquina virtual sea cual sea el estado en que esta termine. Sin embargo mediante un mecanismo callback de funciones la versión 1.0.3 de la KVM puede provee una forma de aplicar un algoritmo de liberación de recursos especial dentro de este mecanismo de liberación de memoria. Este mecanismo se basa en un registro previo de las rutinas nativas (funciones callback) que se emplearan como mecanismo extra de liberación de memoria.

10.8.6.1.

Registro de rutinas especiales de borrado de memoria.

Antes de estudiar el mecanismo de finalización de memoria se explicara de forma detallada la operación: void registerCleanup(INSTANCE_HANDLE instanceH, CleanupCallback cb)

que realiza el registro de las funciones nativas de liberación de memoria que se desee aplicar para una instancia de un objeto: •

•

Primero se comprueba cada uno de los objetos raíz que se reservaron en el momento de inicialización de memoria para este mecanismo extra de liberación de memoria. Y para cada uno de estos objetos se comprueba si son compatibles con la función de callback que se desea aplicar y es pasada como parámetro. En caso negativo, es decir no existe ningún objeto para el cual este asociado esta función de callback hemos de crear un objeto raíz asociado a ella junto con sus lista de punteros a objetos que deriven de él y se le asocia la función de callback que se esta registrando:

size = SIZEOF_WEAKPOINTERLIST(CLEANUP_ARRAY_SIZE); list = (WEAKPOINTERLIST)callocObject(size, GCT_WEAKPOINTERLIST);

list->length = CLEANUP_ARRAY_SIZE; list->finalizer = cb; list->data[CLEANUP_ARRAY_SIZE *)unhand(instanceH);

1].cellp

=

(cell

Inicialmente como se puede observar se crean una serie de objetos asociados a este objeto raíz, este número viene dado por el parámetro CLEANUP_ARRAY_SIZE cuyo valor por defecto es 3. Sin embargo este valor se puede aumentar en el caso en el se empleen con la esta versión de la KVM muchas funciones nativas de borrado de memoria. • Una vez creado el objeto raiz nuevo se añade el puntero a este a la lista de objetos CleanupRoots que mantiene una lista de todos los objetos raíces que tienen registrado una función de callback. • Pudiera haberse dado el caso de que ya existiese un elemento raíz en CleanupRoots con la función de callback asociada en cuyo caso se tendría que añadir a este nodo raiz la instancia del objeto para la cual queremos registrar la función nativa. Se recorre la lista asociada de objetos a este elemento raiz hasta encontrar un eleme nto de la lista libre ( es decir un puntero a null), en ese caso se actualiza la referencia de ese puntero a el puntero a nuestro objeto quedando registrado este para la función nativa asociada al objeto raíz correspondiente: ptr = &list->data[0].cellp; endptr = ptr + list->length; for ( ; ptr < endptr; ptr++) { if (*ptr == NULL) { *ptr = (cell *)unhand(instanceH); }

•

•

Adicionalmente si la opción del recolector de basura de alto rendimiento esta habilitada (EXCESSIVE_GARBAGE_COLLECTION) se invoca a este para que libere memoria que haya podido quedar ocupada por algún objeto residual. Por último nos podemos encontrar con el caso de que aun existiendo un elemento raíz con la función de callback que estamos registrando no hay espacio libre en su lista de punteros asociados para el objeto en cuestión que estamos tratando de asociar a la rutina de liberación de memoria. En este caso se crea una lista de punteros nueva asociada a este objeto de tamaño mayor (marcado por el parámetro de configuración de la KVM CLEANUP_ARRAY_GROW ) pero con la misma función nativa asociada y es la pasa como parámetro a la rutina que estamos estudiando: int oldLength = list->length; int newLength = oldLength + CLEANUP_ARRAY_GROW; WEAKPOINTERLIST newList = (WEAKPOINTERLIST)callocObject(SIZEOF_WEAKPOINTERLIST(newLen gth), GCT_WEAKPOINTERLIST); newList->length = newLength; newList->finalizer = cb; list = (WEAKPOINTERLIST)CleanupRoots->data[i].cellp; CleanupRoots->data[i].cellp = (cell *)newList;

se realiza la copia de la lista antigua a la nueva añadiendo al final de la misma el objeto en cuestión para el cual queríamos hacer el registro de la función: memcpy(newList->data, list->data, oldLength data[newLength 1].cellp = (cell *)unhand(instanceH);

10.8.6.2.

Mecanismo de finalización de gestión de memoria.

El mecanismo de finalización de la memoria empleada por la KVM en su ejecución completa una serie de pasos que son: •

Dado que cuando se arranca este algoritmo ya no existe ningún hilo de ejecución activo es necesario para poder invocar las funciones callback antes mencionadas simular la existencia de un hilo de ejecución: CurrentThread = MainThread;

•

Se recorren cada uno de los elementos raíz de la lista CleanupRoots (que como vimos mantiene todos los objetos raíz del sistema susceptibles de aplicarse una rutina especial de borrado) y para cada uno de ellos se recupera el puntero a la función finalizer, función que se encarga de realizar el borrado especial y creada por un usuario externo a Sun.

•

Para cada elemento raíz anteriormente extraída se recorre la lista asociada de objetos a los cuales se ha de aplicar la función nativa asociada y para cada elemento no nulo de dicha lista se le aplica la función nativa.

•

Una vez aplicado los mecanismo de liberación de memoria nativos de la implementación particular que se haga de la KVM se recorre el árbol de referencias de objetos globalRoots y para cada uno de los elementos raíces de este árbol se actualiza la referencia del puntero del mismo a null, es decir se liberan todas las referencias que pudieran existir a objetos creados durante la ejecución de la maquina virtual.

•

Una vez liberadas las referencias se libera toda la memoria virtual empleada por la KVM mediante la función FinalizeHeap que no es más que una interfaz para otra función freeHeap. Este última función recibe como parámetro la zona de memoria a liberar y es una implementación cuyo prototipo se encuentra recogido en machine_md.h. Esta función por lo tanto depende de la plataforma a la cual vaya dirigida esta implementación de la KVM y es particular de ella.

•

Por último se ha de liberar la memoria estática que se haya reservado (de la forma que ya hemos comentado anteriormente) durante la ejecución de los programas Java en la KVM. Esta liberación de memoria se realiza en el método FinalizeStaticMemory que de igual forma que en la fase anterior solo es una interfaz para el método: void freeVirtualMemory_md(void *address, long size)

y que como es de imaginar conlleva una implementación dependiente de la plataforma destino donde se ejecutara la maquina virtual (Windows, Unix,…).

10.8.7. Estructuración de memoria en funcionamient o normal. La estructuración que la KVM hace de la memoria que emplea queda de la siguiente forma:

Figura 10.10: Estructuración memoria KVM.

10.8.8.

Implementación de Sun del recolector de basura.

En este apartado trataremos de estudiar de forma detallada una implementación real, estudiaremos la implementación de Sun MicroSystem. El código fuente

correspondiente a la implementación del recolector de basura genérico se encuentra recogido en los ficheros garbage.h y garbage.c. Este recolector fue revisado en la versión 1.0.3 con la corrección de cierto número de errores, incorporación de un mecanismo nativo de limpieza de memoria y ciertas modificaciones derivadas del nuevo código de monitorización/sincronización incluido en la versión 1.0.3. Para la gestión de la basura la KVM emplea tipos específicos de objetos estableciendo una clasificación de los objetos comunes en base a su tratamiento desde el recolector de basura: • • • • • •

GCT_FREE: objetos virtuales no ubicados en memoria. GCT_NOPOINTERS: objetos que no apuntan a ninguna zona de memoria y que por lo tanto pueden ser ignorados durante el proceso de recolección. GCT_INSTANCE,GCT_ARRAY,GCT_OBJECTARRAY: objetos genéricos de Java que pueden tener punteros a clases o zonas de memoria que pueden variar. GCT_METHODTABLE: solo es aplicable en el caso en el cual se tengan raíces estáticas y es una estructura que almacena una lista de punteros a métodos de una clase específica ( para acceso estático a los mismos). GCT_POINTERLIST,GCT_EXECSTACK,GCT_THREAD,GCT_MON ITOR: objetos internos de la maquina virtual que pueden tener punteros a clases o zonas de memoria que pueden variar. GCT_WEAKPOINTERLIST: objetos que son invocados por referencias débiles lo que en lenguaje Java se puede traducir por objetos cuyo valor es NULL y que por tanto no serán invocados desde el código de ejecución del programa Java.

El algoritmo de recolección de basura que se emplea en la KVM (mark and sweep) se implementa en la función garbageCollect dentro del fichero garbage.c y que analizamos a continuación y cuyo prototipo es: void garbageCollect(int moreMemory);

Este algoritmo es ejecutado como ya hemos comentado anteriormente periódicamente para comprobar si hay memoria que liberar. El algoritmo se desarrolla en unas fases bien delimitadas: 10.8.8.1.

Comprobación del estado de ejecución del colector de basura.

if (gcInProgress != 0) { /* * Circular invocation of GC should not be allowed. */ fatalVMError(KVM_MSG_CIRCULAR_GC_INVOCATION); } gcInProgress++;

La variable gcInProgress de ámbito global nos indica si el colector esta en funcionamiento, en cuyo caso se eleva una excepción de error fatal que detiene la

ejecución de la maquina virtual. (El tratamiento de errores se encuentra recogido en el capítulo 7). Además se procede a la actualización de la variable global indicativa del estado en ejecución del colector. 10.8.8.2.

Detención ejecución métodos asíncronos.

Mediante esta fase se realiza una espera activa hasta que todas las operaciones de entrada/salida hayan finalizado. Se puede obtener una descripción detallada de las operaciones de hilos en el capítulo 9.

10.8.8.3.

Comprobación integridad de memoria.

En este punto se realiza una comprobación acerca del estado correcto del mapeo de objetos en memoria centrándose en la correcta formación de la cabecera de los objetos comprobando que cada uno de los objetos tiene asociado un tipo GCT válido y que los bits de la cabecera tienen una configuración correcta haciendo uso de las macros ISMARKED y FREECHUNCK. En el caso en cual la verificación sea errónea se eleva una excepción indicativa de la corrupción de los datos de la zona de memoria sobre la cual se esta aplicando el algoritmo de recolección de basura. 10.8.8.4.

Inicio generación logs.

Se inicia el proceso de generación de logs asociado al algoritmo de recolección de basura: #if INCLUDEDEBUGCODE if ((tracegarbagecollection || tracegarbagecollectionverbose) && !TERSE_MESSAGES) { Log->startGC(); } #endif

Todo lo concerniente a la gestión de logs y aspectos de depuración se encuentran recogidos en el capitulo 13. 10.8.8.5.

Comprobación de memoria libre a priori.

Antes de proceder con la ejecución del algoritmo de recolección de basura se ha de verificar el espacio libre de memoria que existe lo cual se realiza mediante el método memoryFree(): CHUNK thisChunk = FirstFreeChunk; long available = 0; for (; thisChunk != NULL; thisChunk = thisChunk->next) { available += (thisChunk->size >> TYPEBITS) + HEADERSIZE; } return available * CELL;

Como se puede observar, se toma la lista enlazada que representa la memoria disponible por la maquina virtual (thisChunk) e inicializada convenientemente en el inicio de la ejecución de la KVM. Se recorre dicha lista enlazada tomando el tamaño de cada objeto incluida la cabecera del mismo. Finalmente se multiplica dicho tamaño por la constante que indica el tamaño del mismo para obtener la memoria libre en bytes. Esta operación solo se ejecuta en modo de depuración. 10.8.8.6.

Salvaguarda del entorno de ejecución.

Mediante la función storeExecutionEnvironment se guarda en la estructura correspondiente al hilo de ejecución actual tres registros de la maquina virtual que son el contador temporal de almacenamiento, puntero al marco de ejecución y el puntero a la pila de ejecución. 10.8.8.7.

Ejecución del algoritmo de recolección de basura.

Esta fase comprende la ejecución en bruto del algoritmo de recolección implementado en el método garbageCollectForReal. 10.8.8.8.

Restauración del entorno de ejecución.

Se procede a la restauración del entorno de ejecución previamente guardado mediante el método LoadExecutionEnvironment. 10.8.8.9.

Comprobación de memoria libre a posteriori.

Nuevamente se calcula el espacio libre de memoria después de haber aplicado sobre este el mecanismo de recolección de basura.

10.8.9. Implementación de Sun del algoritmo mark-andsweep de recolección de basura. Como hemos comentado el mecanismo de recolección de basura real se implementa en la función garbageCollectForReal cuyo código esta disponible en el fichero collector.c siendo la función garbageCollect una interfaz de preparación para esta como acabamos de comentar. También hemos comentando en la introducción de este capítulo que entre los múltiples algoritmos de recolección de basura empleados en la actualidad la KVM emplea una versión del algoritmo mark-and-sweep. Este algoritmo de ejecuta en dos fases: una primera fase donde se marcan todos los objetos que aun son accesibles desde el programa o hilo que se esta ejecutando y una segunda en la que se eliminan los que no son están marcados:

Figura 10.11: Resumen algoritmo mark-sweep. El algoritmo citado comienza realizando la búsqueda y marcado de los distintos objetos que interactúan con el recolector de basura: • • •

Marcado de objetos raíces del sistema (rootObjects). Marcado de objetos derivados (hijos) de los objetos raíces (childrenObjects). Marcado de objetos raíces registrados con mecanismos nativos de liberación de memoria (CleanUpRoots).

El código que realiza esta tarea es: CHUNK firstFreeChunk; long maximumFreeSize; markRootObjects(); markNonRootObjects(); markWeakPointerLists();

Una vez realizado el marcado se procede a realizar una fragmentación de la memoria virtual reservada para la maquina virtual durante su proceso de inicialización (sweepTheHeap). Esta tarea consiste en escanear la memoria para actualizar la lista FreeChunk y en particular la referencia al primer elemento de la misma. Esta lista como ya hemos comentado anteriormente almacena las referencias a los segmentos de memoria libre para uso de los programas Java: firstFreeChunk = sweepTheHeap(&maximumFreeSize);

Ante esta fragmentación de memoria nos podemos encontrar con dos resultados. Si como resultado de la fragmentación la cantidad de memoria libre obtenida (maximumFreeSize) es menor que el tamaño de memoria necesario (realSize) y que es pasado como parámetro al recolector de basura en su invocación se procede a realizar una condensación de la memoria actual (compactTheHeap) ocupada por los distintos objetos creados en el marco de ejecución de la KVM. Esta condensación de la memoria

solo estará activa si la configuración de la maquina virtual así lo permite (opción ENABLE_HEAP_COMPACTION del fichero de configuración main.h): breakTableStruct currentTable; cell* freeStart = compactTheHeap(¤tTable, firstFreeChunk);

Una vez finalizada la condensación de memoria se procede a actualizar y recolocar tanto los objetos raíces como el resto de objetos: if (currentTable.length > 0) { updateRootObjects(¤tTable); updateHeapObjects(¤tTable, freeStart); }

Si la referencia a la primera zona de memoria libre devuelto por compactTheHeap es válido (es decir esta dentro del rango de memoria disponible) se actualiza la referencia a la primera zona de memoria libre. En cambio si el puntero no es válido lo cual es indicativo de que no hay memoria disponible se actualiza a NULL la referencia antes mencionada: if (freeStart < CurrentHeapEnd - 1) { firstFreeChunk = (CHUNK)freeStart; firstFreeChunk->size = (CurrentHeapEnd - freeStart - HEADERSIZE) next = NULL; } else { firstFreeChunk = NULL; }

Veamos a continuación en profundidad el desarrollo específico de cada una de las fases comentadas anteriormente y que forman parte del algoritmo de recolección de basura que emplea la KVM. 10.8.9.1.

Marcado de objetos raíces del sistema(markRootObjects).

El proceso de búsqueda de objetos raíces actualmente activos en el entorno de ejecuc ión de la maquina virtual y su marcado como tal es un proceso relativamente complejo que interactúa con diversos módulos de la KVM. Este proceso es invocado por medio del método markRootObjects. El proceso comienza por recorrer los objetos raíces presentes en la lista destinada a agruparlos GlobalRoots y mediante la macro MARK_OBJECT_IF_NON_NULL se marca el objeto indicando por lo tanto que no puede ser eliminado por el recolector de basura. Algo similar se realiza a continuación para la lista de objetos raíces temporales y para la lista de objetos con funciones nativas asociadas (ya sean estos objetos hilos de ejecución, instancias de objetos o arrays genéricos). De esta forma nos aseguramos que todos los objetos presentes en ambas listas y añadidos a ellas desde otros puntos de ejecución de la maquina virtual están convenientemente marcados. El marcado del objeto se realiza como ya vimos

actualizando el markbit de la cabecera del objeto y mediante la macro MARK_OBJECT_IF_NON_NULL: ptr = &GlobalRoots[0]; endptr = ptr + GlobalRootsLength; for ( ; ptr < endptr; ptr++) { MARK_OBJECT_IF_NON_NULL(*(ptr->cellpp)); } ptr = &TemporaryRoots[0]; endptr = ptr + TemporaryRootsLength; for ( ; ptr < endptr; ptr++) { cellOrPointer location = *ptr; if (location.cell == -1) { /* Actual Location is ptr[1], base is ptr[2] */ MARK_OBJECT_IF_NON_NULL(ptr[2].cellpp); ptr += 2; } else { MARK_OBJECT_IF_NON_NULL(*(location.cellpp)); } }

#if ASYNCHRONOUS_NATIVE_FUNCTIONS { int i; for (i = 0 ; i < ASYNC_IOCB_COUNT ; i++) { ASYNCIOCB *aiocb = &IocbRoots[i]; MARK_OBJECT_IF_NON_NULL(aiocb->thread); MARK_OBJECT_IF_NON_NULL(aiocb->instance); MARK_OBJECT_IF_NON_NULL(aiocb->array); } } #endif

El uso y empleo de funciones nativas de la plataforma de desarrollo en la maquina virtual conlleva aspectos importantes que afectan al rendimiento de la maquina virtual tanto en espacio como en velocidad de ejecución. Es por ello que es uno de los aspectos que hacen a la KVM distinta de la JVM genérica y se encuentra documentado en el capítulo 10. Si la maquina virtual ha sido compilada y ejecutada activando la opción ROMIZING que permite el uso un prelinkado de ciertas clases en el inicio de ejecución de la maquina virtual, se recorre la memoria estática donde se almacenan estas clases precargadas y se marcan cada uno de los objetos. Esto se debe a que estos objetos especiales deben mantenerse durante toda la ejecución de la maquina virtual ya que ese es el motivo por el cual fueron cargados al inicio. La precarga de objetos incluido dentro del JavaCodeCompact se encuentra documentado en el capítulo 18.

Otro de los elementos presentes en la KVM que deben ser marcados por defecto es la HashTable InternStringTable la cual se emplea para guardar y resolver las asociaciones entre la implementación de Java a nivel de usuario para las cadenas de caracteres (String) y la implementación a bajo nivel (mediante un puntero a carácter y un tamaño de cadena). Entonces se recorre cada uno de los elementos de la hash

obteniendo para cada uno de ellos la instancia de objeto String asociado y se marca el monitor asociado a dicho objeto mediante la func ión checkMonitorAndMark: stringTable = InternStringTable; if (ROMIZING || stringTable != NULL) { int count = stringTable->bucketCount; while (--count >= 0) { INTERNED_STRING_INSTANCE instance = (INTERNED_STRING_INSTANCE)stringTable->bucket[count]; for ( ; instance != NULL; instance = instance->next) { checkMonitorAndMark((OBJECT)instance); } } }

El uso de monitores asociado a cada objeto esta relacionado con la gestión de hilos, tema muy extenso que será tratado en un capítulo posterior. Tan solo explicar que estos monitores son marcados pues mantienen información acerca de un entorno de ejecución y de todos los objetos relacionados o activos en él. Si el objeto no tuviera un monitor asociado no se marcaría este ya que ello implica que ese objeto no es accesible desde ningún hilo de ejecución y por lo tanto puede ser eliminado por el recolector de basura. El mecanismo de marcado de un monitor es el siguiente: if (OBJECT_HAS_REAL_MONITOR(object)) { cell *heapSpace = CurrentHeap; cell *heapSpaceEnd = CurrentHeapEnd; MONITOR monitor = OBJECT_MHC_MONITOR(object); MARK_OBJECT(monitor); }

es decir, el monitor se marca con el bit correspondiente de su cabecera pues es como cualquier otro objeto solo que no tiene objetos cuya definición de clases hereden de el. La macro OBJECT_MHC_MONITOR se emplea para obtener el monitor asociado a un objeto en cuestión que le es pasada como parámetro. Además de el elemento InternStringTable que contiene todas las cadenas de caracteres activas en el entorno de ejecución de la maquina virtual existe otra hashtable que almacena el conjunto de clases existentes en el sistema junto con toda su información y que se denomina ClassTable. Todas estas clases deben ser marcadas pues deben ser accesibles por la KVM para las distintas operaciones que se han de realizar los objetos o instancias de estas clases. Por lo tanto mediante la macro FOR_ALL_CLASSES se recorre cada una de las clases y se marca el monitor correspondiente a la misma si existe de forma similar a como se hizo con las cadenas de caracteres. Si la clase en cuestión cuyo monitor se esta marcando con la función es en realidad un array de clases se obtiene la instancia de la clase o array y se marca dentro de esa instancia todos los objetos asociados a ellas. La gestión de clases y objetos Java así como su representación es tratada en el capítulo 8. En ese capítulo se comento que un array de clases es en realidad una clase con una serie de clases incluidas dentro de ella. Estas subclases eran por ejemplo el hilo de ejecución que inicializa la clase, el conjunto de variables, los campos estáticos etc. y se han de marcar el monitor respectivo en caso de que este exista: checkMonitorAndMark

if (ROMIZING || ClassTable != NULL) { FOR_ALL_CLASSES(clazz) checkMonitorAndMark((OBJECT)clazz); if (!IS_ARRAY_CLASS(clazz)) { INSTANCE_CLASS iclazz = (INSTANCE_CLASS)clazz; POINTERLIST statics = iclazz->staticFields; METHODTABLE methodTable = iclazz->methodTable; MARK_OBJECT_IF_NON_NULL(iclazz->initThread); if (clazz->accessFlags & ACC_ROM_CLASS) { continue; } if (USESTATIC) { MARK_OBJECT_IF_NON_NULL(iclazz->constPool); MARK_OBJECT_IF_NON_NULL(iclazz->ifaceTable); MARK_OBJECT_IF_NON_NULL(iclazz->fieldTable); MARK_OBJECT_IF_NON_NULL(iclazz->methodTable); } if (statics != NULL) { int count = statics->length; while (--count >= 0) { MARK_OBJECT_IF_NON_NULL(statics>data[count].cellp); } } if (iclazz->status == CLASS_VERIFIED) { continue; } FOR_EACH_METHOD(thisMethod, methodTable) /* Mark the bytecode object alive for non-native methods */ if (!(thisMethod->accessFlags & ACC_NATIVE)) { checkValidHeapPointer((cell *) thisMethod>u.java.stackMaps.verifierMap); MARK_OBJECT_IF_NON_NULL(thisMethod>u.java.stackMaps.verifierMap); } END_FOR_EACH_METHOD } END_FOR_ALL_CLASSES

El proceso de marcado de objetos raíces del sistema finaliza con el marcado de los distintos hilos de ejecución activos recorriendo cada uno de ellos y marcando el static bit de la cabecera de cada uno pues los hilos no son mas que objetos con las mismas propiedades que el resto de los objetos. Adicionalmente para cada uno de los hilos activos se marca el objeto JavaThread asociado que lleva información acerca del hilo y la pila de ejecución de dicho hilo. Esto último se realiza por medio de la función markThreadStack : for (thread = AllThreads; thread != NULL; thread = thread>nextAliveThread){ MARK_OBJECT(thread);

if (thread->javaThread != NULL) { MARK_OBJECT(thread->javaThread); } if (thread->stack != NULL) { markThreadStack(thread); } }

Este método markThreadStack recorre la pila de ejecución y marca todos los objetos que son alcanzables desde ella para que el colector de basura al ejecutarse no los elimine del sistema. 10.8.9.2.

Marcado de objetos derivados(markNonRootObjects)

En el algoritmo de recolección de basura después de haber marcado como objetos útiles y activos los objetos raíces actualmente presentes se procede a marcar el resto de objetos que hacen referencias a estos teniendo en cuenta que se han de marcar tanto los objetos directos como aquellos derivados de estos últimos que también hace referencias a estos. Ya veremos que para conseguir esta búsqueda de referencias indirectas se hace uso de la recursividad como mecanismo más rentable. Para la gestión de estos objetos derivados de los objetos raíz se emplea una cola circular auxiliar deferredObjectTable de tamaño para 40 objetos donde se van almacenando de forma temporal los distintos objetos que hay que escanear de forma recursiva para encontrar referencias a él, cola que es inicializada al invocar desde el recolector de basura este proceso de marcado de objetos hijos. De esta forma se recorre cada uno de los objetos ubicados en memoria y en caso de encontrar algún objeto en cuya cabecera el bit de marcado esta activo se invoca el método markChildren que es el encargado de marcar todos los objetos que hagan referencia a él ya sean de forma directa o de forma indirecta. do { WeakPointers = NULL; initializeDeferredObjectTable(); for (scanner = CurrentHeap; scanner < endScanPoint; scanner += SIZE(*scanner) + HEADERSIZE) { if (ISMARKED(*scanner)) { cell *object = scanner + 1; /* See markChildren() for comments on the arguments */ markChildren(object, object, MAX_GC_DEPTH); } } if (ENABLEPROFILING) { scans++; } /* This loop runs exactly once in almost all cases */ } while (deferredObjectTableOverflow);

Como se puede comprobar este proceso se ejecuta de forma iterativa sobre la memoria completa y una única vez iterando de forma recursiva (mediante el método

markChildren) sobre cada uno de los objetos hasta que todos los objetos que posean referencias a él hayan sido marcados. El proceso de marcado de objetos derivados de uno dado se realiza como hemos dicho a través del método recursivo markChildren cuyo prototipo es: static void markChildren(cell* object, cell* limit, int remainingDepth)

Este método recibe como parámetros un puntero al objeto del cual hemos de buscar referencias a él, el puntero a la zona de memoria desde la cual se ha de empezar la búsqueda y el máximo número de veces que esta función puede llamarse de forma recursiva. Hay que destacar un aspecto importante y es que la recursividad es un mecanismo que si bien mejora notablemente el rendimiento de algunas aplicaciones también puede provocar el efecto contrario en determinadas condiciones de carrera. Dada la filosofía que mantiene la KVM en cuanto a optimización esta función recursiva se ha implementado de forma que haga uso de la recursividad en el menor número de casos posibles. Veamos a continuación paso por paso el algoritmo que emplea la KVM. En primer lugar se hace uso de tres macros de configuración. Básicamente cada una de las macros realiza las siguientes operaciones: • • • •

Comprueba si el puntero al objeto que reciben como parámetro es válido(es decir si forma parte de la memoria). Obtiene la cabecera del objeto y se consulta para ver si esta marcado. En caso de no estar marcado, se marca el objeto. Con este nuevo objeto marcado se vuelve a llamar de forma recursiva a markChildren pero pasándole como parámetro este objeto o bien se añade a la cola de objetos a examinar si es que se ha superado un límite de iteraciones recursivas establecido.

La primera macro es: #define MARK_AND_RECURSE(child) \ if (inHeapSpaceFast(child)) { cell _tmp_ = OBJECT_HEADER(child); if (!ISKEPT(_tmp_)) { OBJECT_HEADER(child) = _tmp_ | MARKBIT; if ((cell*)child < limit) { RECURSE((cell *)child); } } }

\ \ \ \ \ \ \ \

y se emplea para marcar un objeto derivado cuando se cree que no es necesario que al volver a ejecutar markChildren se recorra la cola de objetos buscando mas objetos que hagan referencias a él.

La segunda macro de configuración es la siguiente: #define MARK_AND_TAIL_RECURSE(child) if (inHeapSpaceFast(child)) { cell _tmp_ = OBJECT_HEADER(child); if (!ISKEPT(_tmp_)) { OBJECT_HEADER(child) = _tmp_ | MARKBIT; if ((cell*)child < limit) { if (nextObject != NULL) { RECURSE(nextObject); } nextObject = (cell *)(child); } } }

\ \ \ \ \ \ \ \ \ \ \ \

y se emplea para marcar un objeto derivado pero al contrario que la macro anterior se fuerza a que en la siguiente paso recursivo por la función markChildren se vuelva a recorrer la cola para ver si hay mas objetos referenciados a él. Esta segunda macro es útil cuando iteramos sobre matrices de objetos por ejemplo: La última de las macros de configuración es: #define MARK_AND_TAIL_RECURSEX(child) if (inHeapSpaceFast(child)) { cell _tmp_ = OBJECT_HEADER(child); if (!ISKEPT(_tmp_)) { OBJECT_HEADER(child) = _tmp_ | MARKBIT; if ((cell*)child < limit) { nextObject = (cell *)(child); } } }

\ \ \ \ \ \ \ \ \

que opera igual a la anterior pero no fuerza la recursividad y que por tanto se aplica cuando estamos seguros de no haber llamado previamente a la macro MARK_AND_TAIL_RECURSE. Como vemos esta última macro acaba con la recursividad de búsqueda de referencias sobre el objeto en cuestión. Existe aún una última macro auxiliar invocada por las tres anteriores y es la siguiente: #define RECURSE(child) if (remainingDepth < 0) { putDeferredObject(child); } else { markChildren(child, limit, remainingDepth); }

\ \ \ \ \

Que como se puede observar vuelve a llamar a la función markChildren si es que hay espacio suficiente en la pila de ejecución. Y es que pese a ser una función recursiva se limita el numero de veces que puede ser invocada para así no provocar una excesiva pérdida de rendimiento. Así como se puede observar si el número de funciones recursivas en curso supera un límite establecido por defecto en 40 (remainingDepth) se almacena el objeto en la cola auxiliar deferredObjectTable mediante el método

putDeferredObjectTable para que sea examinado una vez que toda la memoria haya sido escaneada. El proceso de búsqueda esta implementado en forma de un bucle infinito y del cual el punto de ejecución del algoritmo se sale solo cuando se cumplen una serie de condiciones. De esta forma este bucle itera para un determinado objeto tantas veces como haga falta hasta encontrar todos los objetos que lo referencian de forma directa. Y mediante la recursividad se buscan posteriores referencias en los objetos derivados de estos encontrados, así se consiguen encontrar todas las referencias al objeto tanto directas como indirectas. En cada iteración del bucle se aísla un objeto obteniéndose el tipo GCT del mismo y mediante un selector de tipos se opera según la naturaleza de este. Por cada iteración sobre cada objeto que hay en memoria se comprueba al final de la iteración si el siguiente objeto es nulo, si no lo es se actualizaría el puntero al objeto en estudio para que apuntara al siguiente objeto. Si fuera nulo es decir ya hemos recorrido toda la memoria examinando objetos nos encontramos con dos rutas: • •

Que no haya mas objetos en la cola deferredObjectTable que como ya hemos comentado almacena objetos sobre los que se ha de operar y por lo tanto finalice el proceso de búsqueda y marcado de objetos derivados. Que haya algún objeto almacenado en la cola deferredObjectTable en cuyo caso se obtiene de él el primer objeto mediante el método getDeferredObject y se actualiza el puntero al objeto en estudio para que en la siguiente iteración se repita el proceso para este objeto.

Si el objeto es una instancia simple de una clase (GCT_INSTANCE) se procede de la siguiente forma: • • • • •

Se comprueba si existe un monitor asociado al objeto y se marca en caso de que este exista. Se itera sobre cada uno de los campos del objeto comprobando si alguno de ellos es un puntero a otro objeto. Si se encuentra un puntero a otro objeto se ejecuta la macro MARK_AND_TAIL_RECURSE pasándole como parámetro dicho puntero para que vuelva a buscar a partir de ese objeto. Se actualiza el puntero al objeto a inicial para que apunte a la superclase de la cual hereda repitiéndose el mismo proceso descrito. Una vez que hemos llegado a la jerarquía mas alta en el nivel de clases se seguiría con la ejecución del método markChildren por el siguiente objeto en la memoria.

Si el objeto es de clase GCT_ARRAY, es decir una matriz de tipos básicos simplemente se marca el correspondiente pues no hay punteros a objetos asociados a él. Si el objeto es de GCT_POINTERLIST, es decir una lista de punteros se recorre la lista invocando para cada puntero la macro MARK_AND_TAIL_RECURSE.

Si el objeto es del tipo GCT_WEAKPOINTERLIST, que como ya se ha comentado con anterioridad son objetos nulos y por tanto no se realiza una búsqueda de los objetos hijos asociados ni se marca el objeto. Si se ha llegado a este punto es porque el objeto en cuestión estaba marcado como activo por lo tanto lo único que se hace en este caso es actualizar los punteros para ser marcados posteriormente por causa de otras referencias auxiliares (por ejemplo un situación de NullPointerException provocada por el código del programador). Esta actualización es simplemente añadir a la lista enlazada gcReserved (que contiene todos los punteros de débiles referencias). Si el objeto es del tipo GCT_OBJECTARRA Y (una matriz de objetos Java) al igual que en los casos anteriores el primer paso es marcar el monitor asociado para la gestión adecuada de multihilos de ejecución. Se recorre cada uno de los punteros a objetos de la matriz y se le aplica la macro MARK_AND_TAIL_RECURSE. Como podemos ver este tratamiento es similar al de la lista de punteros y de hecho ambos emplean la misma macro markArray para recorrer la matriz. Si el objeto es del tipo GCT_METHODTABLE se recorren cada uno de los métodos almacenados en la lista y para cada uno de ellos en el caso en que el método corresponda a código nativo (ACC_NATIVE) del sistema se marca tanto el objeto de memoria que almacena el código del método como el manejador de excepciones asociado al método. Para obtener un análisis detallado de las distintas estructuras a bajo nivel que emplea la KVM así como las operaciones mas comunes con ellas se recomienda la lectura del capítulo 6. Si el objeto es de cualquiera de los tipos GCT_MONITOR, GCT_NOPOINTERS y GCT_THREAD no se realiza ninguna acción. Para el monitor de objetos no hace falta marcarlo puesto que este es marcado si se ha marcado algún objeto que lo use, para el segundo objeto al no tener punteros a otros objetos no es necesario marcarlo y no hay objetos que caigan de él. Finalmente para los hilos de ejecución hay que tener en cuenta que al ser estos objetos raíces del sistema (pues a partir de ellos se crean el resto de objetos Java) son marcados junto con el resto de objetos raíces. Para los objetos del tipo GCT_EXECSTACK, ya hemos visto que la pila de ejecución se marca a través del método markThreadStack dentro del marcado de objetos raíces. Evidentemente si el objeto que se esta escaseando no pertenece a ninguno de los tipos válidos se genera un error fatal: fatalVMError(KVM_MSG_BAD_DYNAMIC_HEAP_OBJECTS_FOUND);

Una vez que toda la memoria ha sido examinada y que en la cola de objetos deferredObject no hay objetos a examinar se termina el proceso que estudiamos en este apartado. Una vez visto todo el proceso de búsqueda y marcado de objetos raíces del sistema se puede observar que para lograr la optimización de esta función recursiva se han recurrido a tres restricciones: •

Solo se realiza búsqueda y marcado recursivo para aquellos objetos que estén localizados en memoria por debajo del límite pasado como parámetro (limit).

• •

•

Esto impide que se retroceda en memoria para buscar en objetos que ya han sido examinados con anterioridad. Si se prevé que solo exista un objeto hijo el cual hay que seguir para marcar se itera sobre este objeto hijo únicamente y no de forma recursiva sobre todos los objetos donde se haga referencia al objeto pasado como parámetro. Solo se permite a la pila de ejecución que va almacenando las distintas llamadas recursivas aumentar hasta una profundidad limitada. Si al iterar sobre un objeto superamos este límite ese objeto es guardado en la cola de objetos referenciados deferred object y se vuelve a iterar sobre esta cola una vez que la pila de ejecución vuelva a tener profundidad cero y/o se llegue al último objeto en memoria a escanear Si se produce una saturación de la cola deferred object habrá que recurrir a múltiples iteraciones sobre la memoria con la consiguiente pérdida de rendimiento si bien este es un caso que en raras ocasiones se produce. Dichas múltiples iteraciones se producen a nivel de la función markNonRootObjects.

10.8.9.3.

Fragmentación memoria virtual(sweepTheHeap).

Una de las tareas que se realizan durante el proceso de recolección de basura a lo largo de la memoria es la fragmentación de la memoria. Mediante este proceso se realiza una reordenación de la información que la KVM dispone de la memoria disponible. Esta información como ya se sabe esta almacenada en la lista la enlazada FreeChunk. El código correspondiente a la fragmentación se encuentra recogido en el método sweepTheHeap que recibe como parámetro el máximo tamaño libre que se precisa): • Se realiza un escáner de la memoria comprobando cuales son los objetos activos. Al final del escaneo hemos obtenido un puntero lastLive que nos indica cual es el último objeto activo en memoria. cell *lastLive; while (scanner < endScanPoint && ISKEPT(*scanner)) { *scanner &= ~MARKBIT; scanner += SIZE(*scanner) + HEADERSIZE; } lastLive = scanner;

•

Seguidamente se termina de realizar el escáner de la memoria iterando sobre los objetos que no están activos: while (scanner < endScanPoint && !ISKEPT(*scanner)) { scanner += SIZE(*scanner) + HEADERSIZE; }

•

Si se ha llegado al final de la memoria y además dicho final coincide con el puntero lastLive no hay memoria libre y se devuelve un puntero a NULL indicándolo.

•

Si se ha llegado al final de la memoria pero el último puntero no coincide con lastLive es decir hay objetos no activos al final de la memoria (y por tanto se puede reutilizar esa memoria) se calcula el tamaño de memoria libre y se actualiza la lista enlazada FreeChunk: thisFreeSize = (scanner - lastLive - 1); //tamaño libre newChunk = (CHUNK)lastLive; //referencia a una nueva zona de

memoria newChunk->size = thisFreeSize next; // se inserta en la lista if (thisFreeSize > maximumFreeSize) { maximumFreeSize = thisFreeSize; //se actualiza el tamaño de memoria libre }

Como vemos también se actualiza el puntero al tamaño de memoria libre que le fue pasado como parámetro al valor real si es que este es mayor que el solicitado. 10.8.9.4.

Condensación de memoria (compactTheHeap).

El prototipo de esta operación es la siguiente: static cell* compactTheHeap(breakTableStruct *currentTable, CHUNK firstFreeChunk)

Mediante esta operación se trata de analizar los objetos presentes en memoria para podar agrupar los objetos activos en una zona de memoria formada por direcciones consecutivas. Es decir tratamos de eliminar los espacios libres en memoria que quedan entre objetos activos. Como se puede observar esta función recibe dos parámetros: • •

currentTable: estructura del tipo breakTableStruct que almacena direcciones de memoria de ruptura. Es decir marca las direcciones de memoria ocupadas por objetos activos tales que no le siguen algún objeto activo. fisrtFreeCunk: la referencia a la primera zona libre de memoria actual y accesible por el módulo encargado de alojar en memoria los objetos entre otros.

La forma de operar sería recorrer la memoria completa y en cada iteración se realizan las siguientes tareas: •

Se actualizan las referencias (live y liveEnd) que nos indicaran la zona de memoria inicial donde se encuentran todos los objetos activos todo ello a partir del puntero a primera zona de memoria libre (la referencia freeChunk inicializada al principio del método a firstFreeChunk):

live = scanner; if (freeChunk != NULL) { liveEnd = (cell *)freeChunk; scanner = liveEnd + SIZE(*liveEnd) + HEADERSIZE; freeChunk = freeChunk->next; } else { liveEnd = scanner = currentHeapEnd; }

•

Si es la primera vez que se itera no hay nada que copiar aún ya que solo tenemos un conjunto de objetos activos en la zona de memoria actual (chunk) , por lo que se actualiza la referencia de copyTarget a liveEnd punto a partir del cual hay que copiar los objetos: if (count < 0) { copyTarget = liveEnd; }

•

En la segunda iteración en memoria simplemente se mueven los objetos activos a la zona de memoria indicada por copyTarget que inicialmente esta apuntando al principio de la memoria y la tabla de direcciones de ruptura debe apuntar al final de la zona de memoria activa: int i; for (i = 0; i < liveSize; i += CELL) { CELL_AT_OFFSET(copyTarget, i) = CELL_AT_OFFSET(live, i); } table = (breakTableEntryStruct*)scanner - 1;

•

Para las siguientes iteraciones se calcula el tamaño que ocupan los objetos no activos (extraSize) y mediante la función auxiliar slideObject se desplazan los objetos activos justo después de la referencia copyTarget: int extraSize = PTR_DELTA(scanner, liveEnd); table = slideObject(copyTarget, live, liveSize, extraSize, table, count, &lastRoll);

De esta forma por cada iteración vamos agrupando los objetos activos en la zona de memoria que hay a continuación de la referencia copyTarget. •

Cada vez que hay movimientos de objetos se va registrando dicho movimiento añadiendo una entrada a la tabla de direcciones de ruptura que marca los saltos en memoria que se están produciendo: table[count].address = live; table[count].offset = PTR_DELTA(live, copyTarget);

•

Se actualiza la referencia copyTarget para la siguiente iteración: copyTarget = PTR_OFFSET(copyTarget, liveSize);

•

Se comprueba al final de cada iteración a través de las zonas de memoria se comprueba que el puntero que se emplea para escanear (scanner) la memoria no ha desbordado la memoria virtual disponible situación que se usa a su vez para indicar que ya hemos terminado de compactar toda la memoria: if (scanner >= currentHeapEnd) { if (INCLUDEDEBUGCODE && scanner > currentHeapEnd) { fatalVMError(KVM_MSG_SWEEPING_SCAN_WENT_PAST_HEAP_TOP); } break; }

•

Por último se reordena los elementos de la tabla de direcciones de ruptura pues por el complejo mecanismo de movimientos de objetos que emplea el algoritmo slideObject puede ser que la tabla no tenga sus elementos ordenados adecuadamente. Además se actualiza la tabla de direcciones de ruptura global que se emplea para otras operaciones en el recolector como la actualización de objetos en memoria después de aplicar la operación compactTheHeap: if (lastRoll > 0) { sortBreakTable(table, lastRoll); } currentTable->table = table; currentTable->length = count + 1;

•

Finalmente se devuelve copyTarget que esta apuntando a la primera zona de memoria libre disponible.

10.9. Parámetros de configuración. El módulo de gestión de memoria como ya hemos mencionado en anteriores ocasiones es posiblemente uno de los módulos mas críticos que integran la maquina virtual de las plataforma J2ME. De hecho, para este módulo existen una gran cantidad de parámetros. Tenemos los siguientes parámetros para la gestión de memoria: •

DEFAULHEAPSIZE: se emplea apara especificar el tamaño por defecto de la memoria que empleara la KVM. Evidentemente un aumento de este tamaño provoca que la maquina virtual pueda ocupar mayor memoria pero esto provoca que la operación del recolector de basura aumente su latencia.

•

INLINECACHESIZE: especifica el tamaño de memoria que la KVM emplea como memoria cache para la generación de bytecodes rápidos como se vera en el capítulo dedicado al intérprete de la maquina virtual.

•

STACKCHUNKSIZE: especifica el tamaño que tendrá cada uno de los segmentos que forman la pila de ejecución de los hilos de la maquina virtual.

Este parámetro esta mas relacionado con el módulo de gestión de marcos de ejecución que con el recolector de basura. •

STRINGBUFFERSIZE: tamaño en bytes de memoria estática que la KVM emplea para las operaciones con cadenas de caracteres.

Para la configuración del recolector de basura propiamente dicho tenemos los siguientes parámetros: •

EXCESSIVE_GARBAGE_COLLECTION: esta opción como ya hemos visto a lo largo del capítulo es la que permite activar un algoritmo de recolección de basura que si bien es mas lento permite realizar un recorrido mas completo a lo largo de la memoria y examinarlo mas en profundidad. Esto provoca como es lógico una optimización de la memoria ocupada pero un rendimiento inferior en el recolector de basura.

10.10. ¿Es necesario tener en cuenta el funcionamiento del recolector de basura cuando se diseña software? Cuando se desarrollan aplicaciones en las plataformas J2EE, J2SE o cualquier otro tipo de plataformas que no usen Java pero que no estén limitadas por el sistema operativo normalmente no se tiene en cuenta el funcionamiento del recolector de basura. Precisamente esta es una de las funciones que realiza el recolector de basura: hacer que el proceso de liberar la memoria que ya no este usando para ser reutilizada debe ser transparente al usuario. Sin embargo si tenemos que desarrollar aplicaciones para la plataforma J2ME o en la plataforma .NET o cualquier otra orientada a dispositivos de amplia movilidad el uso de memoria es muy importante. Dado que la memoria disponible esta muy reducida se ha de procurar ocupar la menor memoria posible, tarea que debe realizar el recolector de basura. Dado que no podemos controlar directamente el funcionamiento del colector si debemos al menos conocer como funciona para que los diseños de nuestras aplicaciones se adapten a dicho funcionamiento en la medida de lo posible. Llegando un poco más lejos, podemos decir que a la hora de diseñar cualquier aplicación y sobre todo a la hora de implementar y programar dicho diseño si se tiene en cuenta el funcionamiento del recolector de basura y en particular la temporización del mismo se aporta un valor añadido al producto final nada despreciable reflejado en el aumento del rendimiento de la aplicación.

10.11. Conclusiones. En esta capítulo se ha estudiado la forma en la que la maquina virtual gestiona la memoria del sistema operativo de que dispone para ejecutar los programas Java. Inicialmente se ha introducido al lector en la perspectiva de la gestión de memoria en los sistemas informáticos. Así se han introducido una serie de conceptos básicos en la gestión de memoria como son las distintas técnicas de reserva de memoria y de

recolección de memoria inactiva desde el punto de vista de una aplicación que se esta ejecutando. Particularizando en la KVM, se ha estudiado en primer lugar la forma en la que la maquina virtual mapea los objetos en memoria, destacando que los elementos que básicamente conforman el objeto son: • • •

Cabecera del objeto. Mantiene información acerca del tipo y longitud del objeto así como bits de marcado empleados por el recolector de basura. Puntero a la clase del objeto. Monitor. Campo empleado para el sincronismo de objetos en programas Java multihilo.

Igualmente se ha mostrado como la maquina virtual mantiene en forma de lista enlazada registrados cada uno de los segmentos de memoria libre. Dicha lista es referenciada como chunkStruct. Presentadas las estructuras de datos que se emplean para mapear objetos en memoria se han introducido las dos operaciones básicas para reserva de objetos en memoria: mallocObject y callocObject. Ambas operaciones implementan de forma similar el algoritmo de primera aproximación solo que la segunda operación inicializa el objeto en memoria reservado. En la implementación del algoritmo de reserva de memoria se realizan los siguientes pasos: • • •

Se calcula el tamaño del objeto y se invoca al recolector de basura para que libere memoria antes de ubicar el objeto. Con dicho tamaño se busca en la lista de segmentos libres, actualizada por el recolector de basura cada vez que este es ejecutado, un segmento en el cual se pueda alojar un objeto. Si se encuentra un segmento en el cual solo hay espacio libre para el objeto en cuestión se aloja esta en dicho segmento pero se elimina de la lista de segmentos libres este que se ha ocupado en su totalidad.

En caso de que no existiera un segmento libre para ubicar el objeto antes de reportar a usuario el error de falta de memoria se invoca al recolector de basura para tratar de obtener memoria libre. Existe un variante para alojar objetos en memoria, es el método por el cual la KVM ubica en memoria los objetos permanentes. La diferencia con el método anterior es que en este último la memoria no es liberada hasta el proceso de finalización de la maquina virtual. Por otro lado, como se ha comentado anteriormente el recolector de basura de la KVM emplea un sencillo algoritmo mark-sweep. Cada vez que se invoca el recolector de basura se ejecutan las siguientes tareas: •

Análisis de la memoria para el marcado de los objetos. Esta es posiblemente la fase más importante pues en ella se analiza la memoria y se marcan los objetos que pueden o no ser liberados de memoria. De esta forma, los objetos raíces del sistema y sus derivados son marcados en la cabecera de los mismos.

•

•

Posteriormente mediante un mecanismo complejo se realiza una fragmentación de la memoria. Si como resultado de esta fragmentación la memoria liberada es menor que la memoria necesaria y que puede ser pasada como parámetro opcional al recolector, se invoca una operación de condensación de la memoria (compactTheHeap). Tras haber compactado la memoria, se repite el proceso de marcado de objetos actualizando las marcas ya presentes en los objetos y quedando la lista de segmentos libres actualizada.

El proceso de marcado de los objetos del sistema se ha podido comprobar en el capítulo como es realmente complejo y crítico. Los objetos tales como los hilos cuando son instanciados, automáticamente se añaden a la lista de objetos raíces y en el proceso de marcado de objetos raíces del recolector de basura son recorridos y vueltos a marcar por seguridad. De esta forma siempre son marcados los objetos que implementan hilos activos en el sistema, los objetos de sistema tales como String y el objeto principal que se ejecuta cuando se arranca la maquina virtual. El siguiente paso en el marcado de los objetos es obtener todos aquellos objetos que hagan referencia a los objetos raíces y marcarlos como objetos derivados que no han de ser ser borrados por el recolector de basura. Para cada uno de estos objetos derivados se analiza la memoria en busca de objetos que hagan referencia a este y en caso de encontrarlos se añaden a una lista de objetos a examinar. Posteriormente se recorre esta lista repitiendo el proceso y marcando así todos los objetos que estén aun referenciados. Con los objetos ya marcados se procede a la liberación mediante la función compactTheHeap de los objetos que no están marcados. Tener en cuenta que el proceso de marcado de objetos es un proceso pseudo-recursivo y que por lo tanto tiene un consumo de recursos muy elevado. Adicionalmente se han estudiado en el capítulo las operaciones de inicio y finalización del sistema de gestión de memoria. Mediante la operación de inicialización se hace una reserva inicial de la memoria con el tamaño por defecto que es especificado como parámetro de configuración de la maquina virtual. La finalización de la memoria implica liberar la memoria asociada a los objetos que se encuentren marcados y por tanto activos en ese momento.