Capítulo 5: Implementación - Implementación de enlace dinámico - Recolección de basuras Implementación de enlace dinámico ********************************* Variables de instancia - Cada variable de instancia en objetos de la clase A ocupa un trozo de memoria que se ubica en la misma posición en todos los objetos de la clase A y todas las subclases de A, i.e. el mismo desplazamiento c/r al inicio del objeto. Métodos - Todos los objetos de clase A tienen un puntero de una tabla de métodos compartida. - Cada método definido en A tiene un slot en la tabla. Ahí se almacena una puntero hacia el código que ejecuta el método. - Métodos sobrecargados se consideran métodos distintos, i.e. métodos con igual nombre pero distinta firma ocupan slot distintos en la tabla. - Los objetos de la clase B que extiende de A tienen asociado una tabla de métodos distinta de la clase A. - Los métodos heredados o redefinidos en B ocupan el mismo slot. - Si el método es heredado, el puntero apunta hacia el mismo código que en A. Ese código sigue funcionando gracias a que las variables de instancia heredadas de A se ubican en la misma posicion tanto en los objetos en A como en los objetos en B. - Si el método es redefinido el puntero apunta hacia el nuevo código. - Para invocar un método el compilador determina su slot, obtiene la dirección del código con un par de indirecciones e invoca el método. Ventaja: invocación de métodos tan eficiente como en C. Desventaja: no sirve cuando hay herencia múltiple, no puede haber enlace dinámico c/r a los argumentos del método. Interfaces List l= ...; l.add(...); El compilador sabe que l es de tipo List, pero no sabe la clase específica del objeto. Como distintas clases pueden implementar Map además de otras interfaces, no es posible determinar el slot en tiempo de compilación. - En este caso se pueden usar técnicas de Hashing perfecto para encontrar la dirección del código a ejecutar. Aún así, el costo de invocación es bastante más caro que cuando se invoca un método conociendo su clase. - La implementación actual usa hashing para buscar el método (look up) y almacena un cache de la dirección encontrada. Si la próxima invocación corresponde a la misma dirección, la invocación se rápida, si no, se vuelve a hacer el look up. Este mecanismo funciona muy bien en el caso general pero mal cuando se procesan arreglos con tipos heterogéneos que comparten una misma interfaz. Recolección de basuras ********************** - heap: montón de memoria que mezcla objetos vivos con bloques de memoria disponible. Los bloques forman típicamente una lista enlazada. - petición de memoria: new T() Se busca un bloque con el tamaño adecuado, se parte si es necesario. Un trozo se otorga a la aplicación, el otro se mantiene en la lista enlazada. - Estrategias de búsqueda de bloques: + first-fit: se busca el primer bloque que tenga al menos el tamaño necesario. + best-fit: se busca el bloque que más se acerque al tamaño pedido. + worst-fit: se elige el bloque más grande. First-fit es el que funciona mejor, pero tiende a formar una lista con bloques demasiado pequeños al principio. La variante que se usa, emplea una lista circular. best-fit introduce demasiada fragmentación: muchos bloques de tamaño demasiado pequeño y por lo tanto inutilizables. Worst-fit no se usa. Estrategias de recolección de basuras - Conteo de referencias: se asocia a cada objeto en el heap un contador que indica cuantos punteros referencian el objeto. Por cada asignación p= q: + antes de la asignación: contador(p)-- si el contador se hace 0, el objeto es reciclable. + después de la asignación: contador(p)++ - Mark & Sweep (marcar y barrer) Se realiza cuando no hay más memoria disponible. Detecta los objetos que ya no son alcanzables por la aplicación para reutilizar su espacio. Sea R= conjunto de variables raíces= variables estáticas + variables locales de los métodos activos en los threads en ejecución. recolectar() { marcar() barrer() } marcarObj() { Por cada objeto o en el heap desmarcar(o) Por cada variable v en R marcarObj(v) } marcarObj(v) { Si !estaMarcado(v) { activarMarca(v) Por cada variable de instancia vi de tipo puntero en *v marcarObj(vi) } } barrer() { Por cada objeto o en el heap { Si o no ha sido marcado agregar o a lista de bloques disponibles, fusionar si es necesario. } } marcado: un arreglo de bits (1 bit por palabra en el heap) Desventajas: + lento + introduce pausas Variantes: + con compactación: cuando el heap se encuentra demasiado fragmentado, se desplazan los objetos vivos para dejar un solo gran bloque disponible. Esta variante es más lenta aún porque requiere corregir todos los punteros. + non stop y paralelo: el recolector corre en un thread independiente del thread de la aplicación (o los threads de la aplicación). De esta forma se evitan la pausas. El problema es que al asignar punteros existe una condición de borde que puede hacer que un objeto se considere inaccesible cuando sí es accesible. Esto se resuelve agregando código adicional en las asignaciones de punteros, lo que introduce un sobrecosto en tiempo de ejecución. + conservadores: se usan cuando la implementación del lenguaje no puede ubicar con precisión los punteros en la pila. Dada una palabra cualquiera en la pila, no se sabe si se trata de un puntero, un entero, un real, etc. Se actúa conservadoramente, tratándolo como un puntero si apunta hacia el comienzo de un objeto. Requiere un arreglo de bits adicional para marcar el inicio de los objetos. En este tipo de recolector no se puede desplazar objetos que son accesibles a través de punteros en la pila. - Stop & Copy El heap se divide en partes iguales y sólo se trabaja en una de las mitades. Cuando se acaba la memoria se hace un recorrido en profundidad del grafo de objetos accesibles a partir de las raíces, como en mark & sweep. A medida que se encuentran los objetos accesibles, estos se copian en la 2da. mitad del heap, y se corrigen todos sus punteros. Al final de este recorrido, la 2da. mitad contiene en su inicio todos los objetos accesibles y luego un solo gran bloque de memoria disponible. La aplicación continúa trabajando en la 2da. mitad del heap. En el siguiente ciclo de recolección se copia hacia la 1era. mitad. Ventajas: eficiente Desventajas: requiere el doble de memoria, es muy difícil hacerlo en paralelo y non stop. - Basado en generaciones El heap se descompone en n áreas de almacenamiento, llamadas generaciones, y que almacenan objetos de distinta edad, i.e. número de ciclos de recolección de basura que han sobrevivido. La 1era. generación contiene los objetos más jóvenes. La idea es que la mayoría de los ciclos de recolección se hace solo con las generaciones más jovenes. Los objetos que sobreviven ha estos ciclos pasan a la generación siguiente. Ventaja: es más eficiente porque los objetos jóvenes tienen menor probabilidad de sobrevivir a la recolección que los objetos más viejos. Típicamente sólo el 5% de los objetos de la 1era. generación sobrevive la 1era. recolección. Desventaja: se requiere modificación de la compilación de las asignaciones de punteros, de otro modo una condición de borde puede hacer que se recicle incorrectamente algunos objetos.