PDF de programación - Notas de curso de Programación y estructuras de datos. Memoria dinámica

Notas de curso de Programación y

estructuras de datos. Memoria dinámica

Nikos Mylonakis, Fernando Orejas

[email protected]

Dept. Llenguatges i Sistemes Informátics Universitat Politécnica de Catalunya

Barcelona

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.1/33

Contenido

• Introducción a los LP
• Memoria dinámica
• Control de datos
• Tipos de datos
• Especificación algebraica
• Implementación de tipos abstractos de datos

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.2/33

Introducción a los LP

• Qué es un lenguaje de programación. Clases de

lenguajes

• Criterios de diseño.
• Componentes de un LP.
• Implementación de un LP

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.3/33

• LP. Notación formal que permite escribir todos los

programas que pueden ser ejecutados por un
computador.

• Los lenguajes que describiremos son de alto nivel
• Diferencia entre algoritmo y programa

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.4/33

Clases de LP

• Imperativos y orientados a objetos (OO)

• Tiene instrucción de asignación
• No tienen transparencia referencial

• Declarativos

• Tienen transparencia referencial
• Implementación más ineficiente

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.5/33

Criterios de diseño

• Distinción cualitativa entre LP dependiendo del

próposito del LP

• Los criterios más importantes son:
• Eficiencia en la implementación
• Fiabilidad
• Usabilidad

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.6/33

Eficiencia

• En los años 50-60 era EL criterio de diseño
• Hoy en día también se valora la facilidad de

programar

• Ejemplo1: derivador simbólico en Prolog (25-30

líneas y en C++ (3.000))

• Sólo si la aplicación se ha de utilizar muchas

veces al día C++ es más interesante

• Ejemplo2: Java es menos eficiente que C++ pero

más portable y seguro

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.7/33

Fiabilidad

• Facilidad del LP para detectar un error lo antes

posible.

• La comprobación de tipos en tiempo de

compilación ayuda a detectar errores antes de la
ejecución.

• Ejemplo 1: i:=i+’a’ i:natural
• Hay comprobaciones que no se pueden realizar

en tiempo de compilación

• Ejemplo 2: Rango del índice de los vectores (t[i*2]

i:natural t:tabla [1..N] de entero

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.8/33

Usabilidad

• Hay LP que se diseñan para resolver una cierta

clase de problemas

• La evaluación de un LP ha de ser para su dominio

de aplicación

• Por tanto un LP puede ser mejor para una clase

de problemas y peor para otras

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.9/33

Componentes de un LP. Tipos de
datos

• Se ha de determinar sus tipos básicos,

constructores de tipos, relación de subtipos

• Se ha de determinar la comprobación de tipos que

se hace en tiempo de compilación

• Y la que se hace en tiempo de ejecución (ej:

índice de tablas)

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.10/33

Control de secuencia

• No hablaremos en la asignatura.
• Determina cómo se regula el flujo de los

programas

• En LP imperativos tenemos composiciones

condicionales e iterativas.

• Ejemplos de control más avanzados son la

reescritura de términos y el paralelismo

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.11/33

Control de datos (CD) y Unidades de
programas (UP)

• CD: Mecanismo que ofrecen los LP para acceder,

modificar o mover los datos de un programa

• Ejemplos: Paso de parámetros, ámbito de las

variables y parámetros

• UP: Forma de estructurar los programas
• Ejemplos: Clases en LPOO, módulos, funciones

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.12/33

Implementación de un LP

• Compilación: Proceso de traducción de un

programa en un LP a código máquina.

• Interpretación: Programa que va ejecutando un

programa a medida que lo va leyendo.

• Tradicionalmente se hablaba de compiladores (+

eficientes) e intérpretes (-eficientes)

• Hoy en día no existen LP 100% compilados ni

100% interpretados

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.13/33

• Hoy en día los intérpretes compilan y optimizan el

código de los bucles

• Y los compiladores utilizan máquinas virtuales

intermedias por ejemplo para E/S mediante el uso
de librerías. Por eso es necesario linkar los
programas

• Otro motivo que justifica la necesidad de linker es

la programación modular

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.14/33

Memoria dinámica

• Gestión de memoria en pila y en heap
• Punteros y operaciones básicas. Ejemplos
• Asignación y liberación de memoria dinámica
• Algoritmos de garbage collection

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.15/33

Gestión de memoria en pila

• Veamos como gestionar la memoria de las

variables requeridas en un programa con un
conjunto de acciones

• Ejemplo

accion P rincipal accion A1

accion A2

var x, y, z : . . .
fvar

var a, b : . . .
fvar

var c, d : . . .
fvar

...
A1;
...

...
A2;
...

...
A2;
...

faccion

faccion

faccion

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.16/33

Memoria requerida después de ejecutar la acción
principal, A1,A2 y una llamada recursiva

x

y

z

a b

c d c d

Descripción del proceso de obtención y liberación de
espacio y el concepto de bloque de activación.

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.17/33

• La estructura de datos requerida para gestionar la

memoria de este tipo de variables es una pila.

• Como ya vimos una pila es una estructura lineal
cuyas operaciones principales son las de apilar y
desapilar.

• Esta estructura de datos es facilmente

implementable mediante una tabla

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.18/33

• En el ejemplo la obtención de memoria se haría

con la operación apilar y la liberación de memoria
con desapilar.

• Esta gestión de memoria es limitada.
• Para tener estructuras de datos dinámicas

mediante el uso de punteros esta gestión de
memoria no es suficiente.

• La gestión de memoria para el caso de datos

general requiere de la estructura de datos de un
heap.

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.19/33

Heap

• Mediante un heap la memoria libre y ocupada en

general está entremezclada.

• Cuando se requiere una cierta cantidad de

memoria libre se busca en la zona libre un espacio
que cubra esa cantidad.

• También es posible liberar memoria que ya no es

requerida por el programa.

• Representación gráfica

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.20/33

• La gestión de memoria mediante heap es más

costosa

• Para asignar memoria se requiere realizar una

búsqueda por las zonas libres

• Aparece el problema de fragmentación. La

solución es compactar que agrava la ineficiencia

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.21/33

Punteros o referencias

• Para poder definir estructuras de datos dinámicas

los LP ofrecen los punteros o referencias

• Los punteros son constructores de tipos donde se
requiere un tipo adicional (generalmente básico o
una tupla)

• La sintaxis es ↑ T . Ej: x: ↑ entero
• Los valores de ↑ T son direcciones de memoria
donde se guardan elementos de tipo T más la
dirección distinguida N IL.

• En el ejemplo x denota la dirección de memoria de

una variable entera y x ↑ es una variable entera

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.22/33

Operaciones sobre punteros

• Nosotros asumiremos que el valor inicial de un

puntero es la dirección N IL.

• Para asignarle un espacio de memoria del tipo
determinado se tiene la operación reservar(x)

• Podemos realizar la asignación de punteros

(aliasing) pero normalmente no se tienen
operaciones aritméticas (en C++ sí que existen)

• Ejemplo

var y, x :↑ entero fvar
reservar(x);
y := x;

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.23/33

• Liberación de la zona de memoria mediante la

acción liberar(x).

• El efecto es que x vuelve a tomar el valor N IL y la

zona anteriormente asignada a x pasa a la zona
libre

• Problema de esta operación con aliasing
• En el ejemplo y pasa a ser referencia colgada

(dangling pointer). (En Java no es posible)

var y, x :↑ entero fvar
reservar(x); y := x; liberar(x)

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.24/33

Algoritmos de asignación y
liberación de memoria dinámica

• Presentamos diferentes algoritmos para las

acciones de reservar y liberar memoria

• La representación del heap es normalmente

mediante una lista encadenada de zonas libres
• Un posible algoritmo para reservar es buscar la

primera zona libre con la suficiente memoria
requerida

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.25/33

• Problema de fragmentación. Ejemplo: zonas libres
de 500, 200 y 300 y se realizan las acciones reser-
var(200);reservar(150);reservar(250);reservar(250)

• Alternativas: Empezar la búsqueda por la última

zona libre usada de forma circular (first fit)

• Buscar la zona de memoria que mejor se ajusta a

la zona requerida (best fit)

• Buscar la zona de memoria que peor se ajusta a

la zona requerida (worst fit)

• Estudios estadísticos demuestran que el first es

en general el mejor

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.26/33

Liberación de memoria

Para liberar una direccion d de longitud N de una zona
ocupada podemos:

• Liberar sin actualizar la lista de libres
• Actualizar la lista de libres recorriéndola.
• Resolver problemas de fragmentación en el caso

en que la zona liberada es contigua a una zona
libre

Nikos Mylonakis, UPC (Spain)

February 15, 2007 – p.27/33

Recolector de basura (Garbage
collector)

• Se entiende por basura la memoria que no está en

la zona libre y no es alcanzable por los punteros
de un programa.

• Un recolector de basura se encarga de recoger la

basura situándola en la zona libre

• Hay dos tipos:

• Los de parada/recogida se clasifican en los que

realizan copia y los que realizan marcado y
búsqueda (mark/scan).

• Los continuos pueden realizarse mediante
contador de referencias o sobre la marcha
(on-th