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

Imágen de pdf 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ámicagráfica de visualizaciones

Publicado el 16 de Enero del 2021
79 visualizaciones desde el 16 de Enero del 2021
673,5 KB
33 paginas
Creado hace 14a (15/02/2007)
Notas de curso de Programación y

estructuras de datos. Memoria dinámica

Nikos Mylonakis, Fernando Orejas

nicos@lsi.upc.edu

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
  • Links de descarga
http://lwp-l.com/pdf18707

Comentarios de: Notas de curso de Programación y estructuras de datos. Memoria dinámica (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad