APLICACIONES
Dos de
las aplicaciones mas conocidas de listas son:
- Representación de polinomios
- Resolución de colisiones (Hash)
En
general puede decirse que las listas son muy útiles para aquellas aplicaciones
en las cuales se necesite dinamismo en el crecimiento y reducción de las
estructuras de datos
6.1.
Aplicacion´ de Listas: Recoleccion´ de Basura y Compactaci´on
En un
ambiente de computadores multi-procesos, muchos programas residen en memoria al
mismo
tiempo.
Diferentes programas tiene diferentes requerimientos de memoria. As´ı un
programa puede
requerrir
60K o 300K de memoria. En cualquier momento que el sistema necesite memoria,
necesita
localizar
memoria continua del tamano˜ deseado. Cuando la ejecuci´on de un programa es
terminada,
la memoria
que ha sido ocupada debe ser liberada y disponible para otro programa. Mas´
aun, ´
bloques de
memoria pueden ser liberados en una secuencia diferente a la que fueron
solicitados.
Suponga por
ejemplo el siguiente caso:
Se tiene
una memoria de 100000 palabras y 5 programasa P1, P2, P3, P4, y P5 que
requieren
bloques de
memoria de tamanos ˜ 10000, 15000, 6000, 8000 y 20000. La vista de la memoria
al
localizar
el programa P5 ser´ıa:
10000 310000 59000 100000
P1 P2 P3
P4 P5 Free Space
Figura 12:
Memoria con 5 procesos en ejecucion´
Asuma ahora
que el programa P4 y P2 completaron su ejecuci´on y que por lo tanto la memoria
es
liberada:
10000 310000 59000 100000
P1 Free P3
Free P5 Free Space
Figura 13:
Memoria con 2 procesos terminados
Ahora se
tienen 3 bloques de memoria contigua libres y tres ocupados. Con el propos ´
ito de seguir
permitiendo
la localizacion´ de memoria, es necesario mantener registro de los bloques que
no est´an
en uso.
Para eso se usa un lista de bloques de memoria que no est´an en uso.
El proceso
de recolecci´on de basura es llevado a cabo en dos pasos: (1) marcacion´ de los
bloques
que est´an
en uso y (2) compactaci´on de los bloques libres a memoria disponible. Este
segundo paso
es trivial
si los bloques son de igual tamano˜ llegando a ser de O(n), siendo n el numero
´ de nodos.
Cuando
existe un taman˜o variable por nodo, es deseable compactar la memoria de manera
que
todos los
nodos libres queden en memoria contigua, lo que se llama compactaci´on de
memoria. La
compactaci´on
de memoria reduce el tiempo de recuperacion.
que?
ReplyDelete