Procedimiento y aparato para mejorar el rendimiento de recuperación de espacio inutilizado usando memoria caché de la traza de pila.

Un procedimiento de recuperación automática de objetos de espacio inutilizado,

que comprende:efectuar (220) la enumeración de un conjunto de raíces en una pila de un hilo;

obtener (240) un conjunto de raíces combinando referencias obtenidas a partir de enumeración del conjuntode raíces para todos los hilos;

trazar (250) objetos operativos que se pueden alcanzar a partir de referencias en el conjunto de raíces; y

recuperar (260) espacio de almacenamiento ocupado por objetos distintos de los objetos operativos; y

caracterizado por:

la realización (220) de la enumeración del conjunto de raíces en una pila de un hilo por:

almacenamiento en una memoria caché de la traza de pila (140) información de traza de pila de tramas depila;

uso de la información de traza almacenada en la memoria caché de la traza de pila (140) sin desenrolladoadicional de la pila si la información de traza que se inicia a partir de una trama se almacena en caché en lamemoria caché de la traza de pila (140); y la modificación de la memoria de traza de pila para almacenar encaché la información de traza nueva o actualizada si la información de traza que se inicia a partir de unatrama no se almacena en caché, o si la información de traza de pila ha cambiado desde la últimaenumeración de pila

Procedimiento y aparato para mejorar el rendimiento de recuperación de espacio inutilizado usando memoria caché de la traza de pila Reserva de propiedad intelectual

Una porción de la divulgación del presente documento de patente contiene materiales que están sometidos a protección de propiedad intelectual. El propietario de la propiedad intelectual no tiene objeción en la reproducción de facsímiles tanto del documento de patente como de la divulgación de patente, como figura en los archivos y registros de patentes de la Oficina de Patentes y Marcas, pero, por el contrario, se reserva todos los derechos de propiedad intelectual.

Antecedentes

1. Campo La presente invención se refiere en general a la recuperación de espacio inutilizado, y más específicamente, a la enumeración del conjuntos de raíces en un procedimiento de recuperación de espacio inutilizado.

2. Descripción La función de recuperación de espacio inutilizado, es decir, la recuperación automática de almacenamiento informático, es encontrar objetos de datos que ya no se usan y hacer que su espacio esté disponible para su reutilización por programas en ejecución. La recuperación de espacio inutilizado es importante para evitar complicaciones innecesarias e interacciones sutiles creadas para la asignación explícita de almacenamiento, para reducir la complejidad de depuración de programas, y de este modo favorecer una programación totalmente modular y aumentar la portabilidad de aplicaciones de software. Debido a su importancia, la recuperación de espacio inutilizado se está convirtiendo en parte integrante de entornos de tiempo de ejecución controlados.

El funcionamiento básico de un recuperador de espacio inutilizado puede comprender tres fases, En la primera fase, se pueden identificar todas las referencias directas a objetos de los programas actualmente en ejecución para todas las amenazadas. Estas referencias se denominan raíces, o juntas un conjunto de raíces, y un procedimiento de identificación de todas tales referencias pueden denominarse enumeración del conjunto de raíces. En la segunda fase, se pueden buscar todos los objetos que se pueden alcanzar desde el conjunto de raíces ya que estos objetos se pueden usar en el futuro. Un objeto que se puede alcanzar desde cualquier referencia en el conjunto de raíces es considerado un objeto operativo; de otro modo se considera un objeto de espacio inutilizado. Un objeto que se puede alcanzar desde un objeto operativo también está operativo. El procedimiento para encontrar todos los objetos operativos que se pueden alcanzar desde el conjunto de raíces pueden denominarse como trazado de objetos (o marcado y exploración) . En la tercera fase, el espacio de almacenamiento de objetos de espacio inutilizados puede ser recuperado (recuperación de espacio inutilizado) . Esta fase puede ser llevada a cabo bien por un recuperador de espacio inutilizado o una aplicación en ejecución (normalmente denominado mutador) . En la práctica, estas tres fases, especialmente las dos últimas fases, pueden intercalarse funcionalmente o temporalmente y una técnica de recuperación puede depender en gran medida de una técnica de trazado de objetos operativos. Dependiendo de donde se produzca la enumeración del conjunto de raíces, la enumeración del conjunto de raíces se puede denominar enumeración del conjunto de raíces de registro (en lo sucesivo enumeración de registro) enumeración del conjunto de raíces de montón (en lo sucesivo enumeración de montón) , o enumeración del conjunto de raíces de pila (en lo sucesivo enumeración de pila) . En comparación con la enumeración de pila, las sobrecargas producidas por la enumeración del conjunto de raíces en otras zonas de almacenamiento son habitualmente pequeñas en una aplicación típica y pueden ignorarse.

Cuando se ejecuta espacio de almacenamiento libre por debajo de un límite, se puede utilizar la recuperación de espacio inutilizado y se pueden suspender todas las amenazas para que de este modo la enumeración del conjunto de raíces para cada amenaza pueda empezar (para recuperación de espacio inutilizado concurrente, algunas amenazas no pueden suspenderse para utilizar la enumeración del conjunto de raíces) . Para la enumeración de pila para una amenaza, la trama de pila (en la pila de hilo) donde está suspendido el hilo se convierte en una trama actual a partir de la cual puede empezar la enumeración de pila. Todas las referencias vivas en la trama actual pueden ser identificadas y enumeradas. Después de enumerar la trama actual, la siguiente trama de pila (es decir, una trama de interlocutores) en una pila de llamadas se convierte en una trama actual en la que las referencias vivas pueden ser identificadas. Este procedimiento, que se denomina desenrollado, sigue hasta que todas las tramas en una cadena de llamadas son encaminadas y enumeradas.

Un mecanismo de desenrollado de pila implicado en la enumeración de pila en un recuperador de espacio inutilizado desenrolla o encamina tramas de pila de una pila de llamadas, una trama a la vez, para identificar referencias actualmente activas; es decir referencias para formar un conjunto de raíces. Para algunas aplicaciones, especialmente las que tienen un gran número de hilos y una cadena de llamadas profunda por hilo, el desenrollado de pila incurre en una sobrecarga importante de tiempo de ejecución para la recuperación de espacio inutilizado. Cuando más amenas hay, y cuanto más profunda es la cadena de llamadas por hilo, mayor es la sobrecarga de tiempo de ejecución que se puede usar. Por lo tanto, es deseable mejorar la eficiencia de enumeración de pila reduciendo la sobrecarga producida por el desenrollado de la pila.

El documento US 2003/0126352 divulga tal recuperación de espacio inutilizado de desenrollado de pila.

El documento US 6523141 divulga un procedimiento y un aparato para detectar e informar de fugas de memoria asociadas a un sistema operativo. Un procedimiento para identificar una sección de memoria asignada dinámicamente que no puede liberarse explícitamente incluye el procesamiento de información asociada al fallo de un sistema operativo y la identificación de un sitio de llamada que está asociado a la sección de la memoria asignada dinámicamente usando la información.

Breve descripción de los dibujos Las características y ventajas de la presente invención se pondrán de manifiesto a partir de la siguiente descripción detallas de la presente invención en los que:

La figura 1 representa un esquema de alto nivel de un sistema de tiempo de ejecución controlado a modo de ejemplo usando al menos una memoria caché de la traza de pila para mejorar el rendimiento de recuperación de espacio inutilizado, según una realización de la presente invención. La figura 2 es un diagrama de flujo a modo de ejemplo de un procedimiento de alto nivel en el que se usa una memoria caché de la traza de pila durante la enumeración del conjunto de raíces para la recuperación de espacio inutilizado en una sistema de tiempo de ejecución controlado, según una realización de la presente invención La figura 3 es un diagrama de bloques funcional de alto nivel de un mecanismo de enumeración de pila usando una memoria caché de la traza de pila, según una realización de la presente invención. La figura 4 es un diagrama de flujo a modo de ejemplo de un procedimiento en el que se crea una memoria caché de pila y se usa para mejorar el rendimiento de enumeración del conjunto de raíces durante la recuperación de espacio inutilizado para un hilo, según una realización de la presente invención; y Las figuras 5 (a) – (d) son ilustraciones esquemáticas del estado de una memoria caché de la traza de pila durante diferentes sesiones de enumeración de pila para un hilo, según una realización de la presente invención

Descripción detallada Una realización de la presente invención es un procedimiento y un aparato para mejorar el rendimiento de enumeración del conjunto de raíces para recuperación de espacio inutilizado usando al menos una memoria caché de la traza de pila. La presente invención se puede usar para reducir la sobrecarga de enumeración de pila durante la recuperación de espacio inutilizado en aplicaciones de software con un gran número de hilos y una cadena de llamadas profunda por hilo, sin mucho coste. En algunas aplicaciones de software, una cadena de llamadas funcional es un hilo que puede ser repetitivo, es decir la relación entre llamante y llamado puede no cambiar mucho, de una sesión de recuperación de espacio inutilizado a la siguiente. De este modo una memoria caché de la traza de pila se puede usar para el hilo de almacenar información de la traza de pila, lo cual refleja la relación llamantellamado... [Seguir leyendo]

1. Un procedimiento de recuperación automática de objetos de espacio inutilizado, que comprende:

efectuar (220) la enumeración de un conjunto de raíces en una pila de un hilo; obtener (240) un conjunto de raíces combinando referencias obtenidas a partir de enumeración del conjunto de raíces para todos los hilos; trazar (250) objetos operativos que se pueden alcanzar a partir de referencias en el conjunto de raíces; y recuperar (260) espacio de almacenamiento ocupado por objetos distintos de los objetos operativos; y

caracterizado por:

la realización (220) de la enumeración del conjunto de raíces en una pila de un hilo por:

almacenamiento en una memoria caché de la traza de pila (140) información de traza de pila de tramas de pila; uso de la información de traza almacenada en la memoria caché de la traza de pila (140) sin desenrollado adicional de la pila si la información de traza que se inicia a partir de una trama se almacena en caché en la memoria caché de la traza de pila (140) ; y la modificación de la memoria de traza de pila para almacenar en caché la información de traza nueva o actualizada si la información de traza que se inicia a partir de una trama no se almacena en caché, o si la información de traza de pila ha cambiado desde la última enumeración de pila 2. El procedimiento de la reivindicación 1, en el que el conjunto de raíces comprende referencias actualmente operativas en las pilas, registros y otras zonas de almacenamiento para todos los hilos.

3. El procedimiento de la reivindicación 1 o la reivindicación 2, en el que la ejecución (220) de la enumeración del conjunto de raíces en una pila de un hilo usando una memoria caché (140) de traza de pila comprende:

Determinar si una trama de pila se almacena en caché en la memoria caché (140) de la traza de pila; Detectar (445) una parte de la información de traza de pila que no ha cambiado desde la última enumeración de pila en la memoria caché (140) de traza de pila y recuperar (450) la parte no modificada a partir de la memoria caché (140) de la traza de pila, si la trama de pila es almacenada en caché en la memoria caché (140) de la traza de pila; y Efectuar (430) una enumeración normal del conjunto de raíces en la pila, si la trama de pila no está almacenada en caché en la memoria caché (140) de la traza de pila.

4. El procedimiento de cualquiera de las reivindicaciones 1 a 3, en el que el trazado (250) de los objetos operativos comprende el marcado de los objetos operativos y de otros objetos de exploración que se pueden alcanzar a partir de los objetos marcados.

5. Un procedimiento según cualquiera de las reivindicaciones anteriores, en el que la ejecución (220) de la enumeración del conjunto de raíces en una pila de hilo comprende:

Iniciar una lista de enumeración de la pila; Crear (420) una memoria caché (140) de la traza de pila para el hilo; y Ejecutar (220) una enumeración del conjunto de raíces en la pila utilizando la memoria caché (140) de traza de pila para producir una lista de enumeración de pila actualizada.

6. El procedimiento de cualquier reivindicación anterior, que comprende, además, etiquetar una trama de pila para indicar si la trama de pila se ha almacenado en caché en la memoria caché (140) de la traza de pila o si se ha generado recientemente en la pila y no ha sido almacenada en caché en la memoria caché (140) de la traza de pila.

7. El procedimiento de la reivindicación 5, en el cual la lista de enumeración de pila comprende referencias actualmente operativas en la pila.

8. El procedimiento de la reivindicación 5, en el cual la creación (420) de la memoria caché (140) de la traza de pila comprende:

determinar (415) si la enumeración del conjunto de raíces en la pila se efectúa por primera vez; crear de manera dinámica la memoria caché (140) de la traza de pila y el almacenamiento en caché de información de tramas de pila en la memoria caché (140) de la traza de pila, si la enumeración del conjunto de raíces en la pila se efectúa por primera vez; y en caso contrario, reutilizar la memoria caché (140) de la traza de pila para la enumeración del conjunto de raíces en la pila 9. El procedimiento de cualquier reivindicación anterior, en el que el almacenamiento en caché de información de tramas de pila comprende añadir un identificador a cada trama utilizando los valores de un registro de indicador de instrucciones y de un registro de indicador de pila.

10. El procedimiento de la reivindicación 8, en el que la reutilización de la memoria caché (140) de la traza de pila comprende al menos una de lo siguiente:

usar la memoria caché (140) de la traza de pila sin cambios y modificar la memoria caché (140) de la traza de pila para recibir tramas de pila recientes y actualizadas.

11. El procedimiento de cualquier reivindicación anterior, en el que la ejecución (220) de la enumeración del conjunto de raíces en la pila utilizando la memoria caché (140) de la traza de pila comprende:

determinar si una trama de pila está almacenada en caché en la memoria caché (140) de la traza de pila basada en una etiqueta de la trama de pila; copiar una parte no modificada de la información de traza de pila de la memoria caché (140) de la traza de pila en la lista de enumeración de pila, si el valor de la etiqueta indica que la trama de pila está almacenada en caché en la memoria caché (140) de la traza de pila; y ejecutar en caso contrario una enumeración normal del conjunto de raíces en la pila.

12. El procedimiento de la reivindicación 11, en el que el copiado de la parte sin cambios de la información de traza de pila comprende la detección de una parte de la información de traza de pila que no ha cambiado desde la última enumeración de pila en la memoria caché (140) de la traza de pila y la recuperación de la parte sin cambios de la memoria caché (140) de la traza de pila.

13. El procedimiento de la reivindicación 11, en el que la ejecución de una enumeración normal de la pila comprende:

desenrollar la pila hasta alcanzar una trama que se almacena en caché en la memoria caché (140) de la traza de pila; almacenar en caché información de tramas no desenrolladas en la memoria caché (140) de la traza de pila; y añadir referencias enumeradas a partir de las tramas desenrolladas en la lista de enumeración de pila.

14. Un sistema (100) de tiempo de ejecución controlado, que comprende una máquina virtual (110) ; un compilador Justo En Tiempo (120) ; un mecanismo (130) de enumeración de un conjunto de raíces capaz de obtener (240) un conjunto de raíces; un recuperador (150) de espacio inutilizado capaz de trazar (250) objetos operativos que se pueden alcanzar a partir del conjunto de raíces y recuperar (260) un espacio de almacenamiento ocupado por objetos distintos de los objetos operativos; y

caracterizado por

el mecanismo (130) de enumeración del conjunto de raíces que comprende:

un mecanismo de enumeración de pìla; y al menos una memoria caché de la traza de pila; y caracterizado por:

efectuar (220) una enumeración del conjunto de raíces en una pila de hilo por:

el almacenamiento en una memoria caché (140) de la traza de pila de información de traza de pila de las tramas de pila; el uso de información de traza almacenadas en la memoria caché (140) de pila sin desenrollado adicional de la pila si la información de traza que se inicia a partir de una trama se almacena en caché en la memoria caché (140) de la traza de pila; y la modificación de la memoria caché de la traza de pila para almacenar en caché información de traza recientes o actualizadas si la información de traza que se inicia a partir de una trama no está almacenada en caché, o si la información de traza de pila se ha modificado desde la última enumeración de pila.

15. El sistema de la reivindicación 14, en el que la memoria caché (140) de la traza de pila comprende una zona de identificación para almacenar identificadores de trama de pila y una zona para almacenar referencias enumeradas para tramas de pila.

16. El sistema de la reivindicación 14 o la reivindicación 15, en el que el mecanismo (130) de enumeración del conjunto de raíces comprende:

un clasificador (310) de trama de pila capaz de clasificar una trama de pila basándose en una etiqueta de la trama de pila; un mecanismo (320) de almacenamiento en caché de información de traza capaz de almacenar en caché información de la trama de pila en una memoria caché (140) de la traza de pila, si el valor de la etiqueta indica que la trama de la pila no está almacenada en memoria;

un mecanismo (340) de detección de traza sin cambio capaz de detectar una parte de la información de traza de pila que no han cambiado desde la última enumeración de pila en la memoria caché (140) de la traza de pila, si el valor de la etiqueta indica que la trama de pila está almacenada en caché; y un mecanismo (350) de recuperación de traza sin cambios capaz de recuperar la parte sin cambios de la información de traza de pila de la memoria caché (140) de la traza de pila.

17. El sistema de cualquiera de las reivindicaciones 14 a 16, que comprende, además, un mecanismo (330) de desenrollado de pila capaz de desenrollar una pila hasta alcanzar una trama de pila que está almacenada en caché en la memoria caché (140) de la traza de pila.

18. El sistema de cualquiera de las reivindicaciones 14 a 17, en el que el mecanismo (320) de almacenamiento en caché de información de traza comprende:

un creador (325) de memoria caché capaz de crear la memoria caché (140) de la traza de pila cuando la enumeración del conjunto de raíces en la pila se efectúa por primera vez; y un componente de identificación de trama capaz de identificar una trama en la memoria caché (140) de la traza de pila.

19. Un programa informático que comprende un medio de código de programa informático adaptado para llevar a 20 cabo todas las etapas de cualquiera de las reivindicaciones 1 a 13 cuando dicho programa es ejecutado en un ordenador.