Tesis

Recolección de basura en D
Leandro Matías Lucarella
Dirección Lic. Rosa Wachenchauzer
Padrón 77.891

Tesis de Grado en Ingeniería en Informática
Departamento de Computación
Facultad de Ingeniería
Universidad de Buenos Aires

Octubre 2010

Índice general

1. Introducción 1.1. Objetivo . . 1.2. Alcance . . . 1.3. Limitaciones 1.4. Organización

. . . .

. . . .

. . . .

. .. .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .1 2 2 2 2 5 5 6 7 7 11 13 15 18 21 23 23 24 25 28 28 29 29 34 35 37 39 39 40 41 41

2. El lenguaje de programación D 2.1. Historia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Descripción general . . . . . . . . . . . . . . . . . . . . . 2.3. Características del lenguaje . . . . . . . . . . . . . . . . . 2.3.1. Programación genérica y meta-programación . . . 2.3.2.Programación de bajo nivel (system programming) 2.3.3. Programación de alto nivel . . . . . . . . . . . . . 2.3.4. Programación orientada a objetos . . . . . . . . . 2.3.5. Programación confiable . . . . . . . . . . . . . . . 2.4. Compiladores . . . . . . . . . . . . . . . . . . . . . . . . . 3. Recolección de basura 3.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1. Conceptos básicos. . . . . . . . . . . . . . . . . 3.1.2. Recorrido del grafo de conectividad . . . . . . . . 3.1.3. Abstracción tricolor . . . . . . . . . . . . . . . . . 3.1.4. Servicios . . . . . . . . . . . . . . . . . . . . . . 3.2. Algoritmos clásicos . . . . . . . . . . . . . . . . . . . . . 3.2.1. Conteo de referencias . . . . . . . . . . . . . . . . 3.2.2. Marcado y barrido . . . . . . . . . . . . . . . .. 3.2.3. Copia de semi-espacio . . . . . . . . . . . . . . . 3.3. Estado del arte . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1. Recolección directa / indirecta . . . . . . . . . . . 3.3.2. Recolección incremental . . . . . . . . . . . . . . 3.3.3. Recolección concurrente / paralela / stop-the-world 3.3.4. Lista de libres / pointer bump allocation . . . . . . 3.3.5. Movimiento de celdas .. . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . .. . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . .. . . .

. . . . . . . . . . . . . . .

I

3.3.6. 3.3.7.

Recolectores conservativos versus precisos . . . . . . . . . . . . . . . . . . . 42 Recolección por particiones / generacional . . . . . . . . . . . . . . . . . . . . 43 45 45 45 46 46 46 47 47 50 59 65 67 72 72 74 77 77 78 83 85 85 86 88 92 94 97 104 105 111 126 134 134

4. Recolección de basura en D 4.1. Características ynecesidades particulares de D . . . . . . . 4.1.1. Programación de bajo nivel (system programming) 4.1.2. Programación de alto nivel . . . . . . . . . . . . . 4.1.3. Información de tipos . . . . . . . . . . . . . . . . 4.1.4. Orientación a objetos y finalización . . . . . . . . 4.2. Recolector de basura actual de D . . . . . . . . . . . . . . 4.2.1. Organización del heap . . . . . . . . . . . . . . ....