L12: Practica 5
- Tiempo: 2h
-
Objetivos de la sesión:
- Aprender a reservar memoria
- Entender la base de las estructuras de datos
- Saber programar listas enlazadas
- Fecha: 2019/Dic/29
Haz click en la imagen para ver el vídeo en Youtube
Haz click en la imagen para ver el vídeo en Youtube
Haz click en la imagen para ver el vídeo en Youtube
Haz click en la imagen para ver el vídeo en Youtube
Haz click en la imagen para ver el vídeo en Youtube
- Introducción
- El montículo (Heap)
- Reserva dinámica de memoria
- Estructuras de datos
- Listas enlazadas
- Actividades NO guiadas
- Autores
- Licencia
- Enlaces
Los programas son implementaciones de algoritmos que ejecutan operaciones sobre estructuras de datos (Algorithms + Data Structures = Programs). Mediante la memoria dinámica podemos crear estas estructuras, y hacer que vayan creciendo dinámicamente, según el programa lo vaya necesitando. Aprenderemos cómo utilizar la memoria dinámica en el RISC-V y veremos ejemplos de cómo implementar la estructura de datos más sencilla: la lista enlazada
El montículo es la zona de la memoria destinada a la reserva dinámica. Es una zona que crece hacia arriba (hacia direcciones altas) y al igual que la pila, va variando su tamaño. El mapa de memoria que incluye todas las zonas que ya conocemos es este
El montículo, en el simulador RARs, se encuentra situado a partir de la dirección 0x1004000. Es una zona de memoria que controla el sistema operativo, y por tanto tenemos que usar una llamada al sistema para reservar la memoria dinámica que queramos usar
Para utilizar la memoria disponible en el montículo se la tenemos que pedir al sistema operativo. Esta operación se conoce como reserva de memoria. La realizamos invocando el servicio 9 del sistema operativo. Le pasamos como único parámetro el número de bytes que queremos reservar, y devuelve la dirección de la zona asignada
El puntero devuelto es múltiplo de 4, por lo que siempre se nos reservarán un número entero de palabras. Así, si le solicitamos que nos reserve 1 byte, en realidad nos reserva una palabra (4 bytes)
En nuestro primer ejemplo reservaremos una palabra (4 bytes) y almacenaremos el valor 0xCACABACA. El programa es el siguiente:
#-- Ejemplo de reserva de una palabra
.include "servicios.asm"
.text
#-- Reserva de 1 palabra (4 bytes)
li a0, 4
li a7, 9 #-- Servicio Sbrk
ecall
#-- En a0 tenemos el puntero a la zona de
#-- memoria asignada
#-- Guardamos una palabra de prueba
#-- en esa dirección
li t0, 0xCACABACA
sw t0, 0(a0)
#-- Terminar
li a7, EXIT
ecallLo ejecutamos y observamos los registros. La dirección asignada la vemos en a0. Es la 0x10040000, justamente la primer dirección del montículo. En la parte inferior, en la ventana de visualización de los datos seleccionamos el Heap y comprobamos que se ha almacenado en la primera posición el valor 0xCACABACA
El servicio de reserva de memoria se denomina SBRK. A partir de ahora definiremos la constante SBRK con el valor 9 y lo incluiremos en el fichero servicios.asm para usarlo en el resto de ejemplos y ejercicios
#-- Fichero servicios.asm
#-- Código de los servicios del sistema operativo
#-- Incluir estos archivos en tus programas
#-- para acceder a ellos fácilmente, y hacerlos más
#-- legibles
.eqv PRINT_INT 1
.eqv PRINT_STRING 4
.eqv READ_INT 5
.eqv READ_STRING 8
.eqv SBRK 9 #-- Reserva de memoria
.eqv EXIT 10
.eqv PRINT_CHAR 11
.eqv READ_CHAR 12Como segundo ejemplo, reservaremos dos bloques de 10 bytes, almacenaremos dos palabras en cada bloque y veremos cómo quedan en memoria
#-- Ejemplo de reserva de dos
#-- bloques de 10 bytes
#-- Se escriben 2 palabras en cada bloque
.include "servicios.asm"
#-- Tamaño del bloque a reservar
.eqv TAM 10
.text
#-- Reserva de 1 bloque de 10 bytes
li a0, TAM
li a7, SBRK
ecall
#-- Almacenamos dos palabras en
#-- en bloque
li t0, 0xCACABACA
li t1, 0xCAFEB0B0
sw t0, 0(a0)
sw t1, 4(a0)
#-- Reservamos otro bloque de 10 bytes
li a0, TAM
li a7, SBRK
ecall
#-- Almacenamos otras dos palabras
li t0, 0xB0CAF0CA
li t1, 0xDED0FE00
sw t0, 0(a0)
sw t1, 4(a0)
#-- Terminar
li a7, EXIT
ecall
Lo ejecutamos y miramos lo que se ha almacenado en el Heap
Observamos que los bloques de la reserva están alineados: es decir, que la primera palabra del segundo bloque empieza en una dirección múltiplo de 4
Así es como queda el HEAP al ejecutar el programa
Lo mismo que reservamos memoria para almacenar datos, también se puede liberar esta memoria para que el sistema operativo se la pueda asignar a otros procesos. Sin embargo, el sistema operativo del simulador RARs NO dispone de esta opción todavía. Así que en los ejemplos que hagamos NO liberaremos la memoria, aunque en las aplicaciones reales sí que hay que hacerlo
La memoria dinámica la usamos para construir estructuras de datos, cuyo tamaño es variable con la ejecución del programa. Ejemplo de estructuras de datos son las listas, colas, pilas, árboles, etc.
En este apartado vamos a ver todos los conceptos generales comunes a todas las estructuras de datos, y en el siguiente lo aplicaremos a una estructura concreta: la lista enlazada
Ya sabemos reservar bloques de memoria. Lo representamos de la siguiente manera:
El sistema operativo nos devuelve la dirección del bloque reservado en a0. Es un puntero a ese bloque. Lo representamos mediante una flecha que sale del registro a0 y llega a la base del bloque: es la dirección de la primera palabra del bloque. A partir de esa dirección, y dado que conocemos el tamaño del bloque, podemos acceder a cualquier de las palabras intermedias usando las instrucciones lw y sw aplicando un offset: 0(a0), 4(a0), 8(a0), etc...
Es muy importante NO perder nunca el puntero a ese bloque. Si lo perdemos, no tendremos ninguna manera de acceder a él, dado que el sistema operativo nos lo ha asignado y la dirección donde está no la hemos elegido nosotros: no la conocemos
Por ello, si ahora queremos crear otro bloque, tendremos que guardar primero el puntero del bloque, que tenemos ahora en a0, en otro registro o en otra posición de memoria. Por ejemplo, vamos a guardarlo en s0. Esto lo representamos gráficamente así:
Tenemos dos punteros, que apuntan al mismo bloque. Ahora ya podemos reservar un nuevo bloque cuya dirección se guardará en a0. Como la hemos copiado previamente, no la perdemos. Ahora tenemos dos bloques con su dos punteros para acceder a ellos
Estos bloques de memoria los podemos enlazar entre sí, de forma que un bloque contenga la dirección de otro bloque. En el ejemplo que estamos haciendo, si almacenamos a0 en la primera palabra del bloque 1, hacemos que el bloque 1 apunte al 2. Esto lo conseguimos con la instrucción: sw a0, 0(s0)
Ahora los bloques se dice que están enlazados. Son por tanto parte de la misma estructura. Y en vez de bloques, los llamamos nodos, para indicar que son elementos que pertenecen a la misma estructura de datos. Hemos definido una estructura de datos, que tiene dos nodos diferentes
También vemos que el nodo 2 está referenciado dos veces. Está apuntado por el nodo 1 y por el registro a0
Si ahora usamos el registro a0 para otra cosa, perdemos una referencia, y la estructura de datos que nos queda la representamos de esta forma
Todos los nodos están referenciados. Para acceder al nodo 1 hay que usar el registro s0. Y, para acceder al nodo 2, la primera palabra del nodo 1
Combinando estas dos acciones simples: creación de un bloque y enlazado, construimos estructuras de datos mucho más complejas. En el caso más general, los nodos puedes ser todos diferentes entre sí, y estar enlazados con muchos otros nodos (no sólo con uno)
Una de las estructuras básicas es la lista enlazada. Usaremos una lista simplemente enlazada para aprender cómo implementarla en el ensamblador del RISC-V
En una lista todos los nodos son iguales: tienen el mismo tamaño y la misma estructura. Cada nodo tiene dos campos: uno con datos y otro con un puntero al siguiente nodo
Este es un ejemplo de una representación de una lista simplemente enlazada, de 3 nodos
En todos los nodos hay un campo que contiene el enlace al siguiente nodo: es un puntero. Contiene la dirección de memoria en donde se encuentra almacenado el siguiente nodo. Un valor de 0 (NULL) indica que es el último (conocido como nodo cola de la lista). Gráficamente lo indicamos con el símbolo de conexión a tierra
Accedemos al primer elemento (conocido como nodo cabeza de la lista) mediante un puntero de acceso. A partir de acceder al primer nodo, ya podemos saltar a los siguientes nodos y leer información de ellos o modificarlos
Para practicar vamos a trabajar con una lista de número enteros. Los nodos tienen dos palabras (8 bytes). La situada en la dirección más baja es el puntero al siguiente nodo. Este campo lo llamaremos NEXT. La siguiente palabra, situada en el offset 4, contendrá el número entero. Este campo lo llamamos NUM
Esta es la estructura de los nodos
Este es el aspecto que tiene la lista cuando hemos introducido los valores 1, 2 y 3:
Para que sea más fácil su implementación, esta lista crece por la cabeza, de forma que el primer número que se introdujo es el que se encuentra al final de la lista (nodo cola), y el último introducido está el primero de la lista (nodo cabeza)
Empezamos creando la subrutina create() para crear un nodo e inicializarlo. La subrutina recibe los valores de los campos NEXT y NUM por los registros a0 y a1 respectivamente y reserva 8 bytes de memoria. Almacena los valores de los campos y devuelve por a0 el puntero al nuevo nodo
La información del nodo la definimos en constantes: su tamaño y el offset de cada uno de los campos:
#---- Informacion sobre el nodo
.eqv TAM 8 #-- Tamaño del nodo
.eqv NEXT 0 #-- Offset del campo NEXT
.eqv NUM 4 #-- Offset del campo NUMDe esta forma el acceso a los campos es más sencillo y menos propenso a errores. Así, Por ejemplo, para leer el número almacenado hay que utilizar esta instrucción:
lw t0, NUM(a0)La subrutina completa es la siguiente:
#-- de la lista
#-- ENTRADAS:
#-- a0: puntero al siguiente nodo
#-- a1: Numero a almacenar en ese nodo
#--
#-- SALIDAS:
#-- a0: Puntero al nodo creado
#-----------------------------------------------------
.include "servicios.asm"
.globl create
#---- Informacion sobre el nodo
.eqv TAM 8 #-- Tamaño del nodo
.eqv NEXT 0 #-- Offset del campo NEXT
.eqv NUM 4 #-- Offset del campo NUM
.text
create:
#-- Guardar los argumentos pasados en t0 y t1 respectivamente
mv t0, a0
mv t1, a1
#-- Crear un nodo nuevo
li a0, TAM
li a7, SBRK
ecall
#-- a0 apunta al nuevo nodo
#-- Inicializar los campos a los valores t0 y t1 (pasados como parametros)
sw t0, NEXT(a0)
sw t1, NUM(a0)
#-- Terminar
#-- En a0 se devuelve el puntero al nuevo nodo
retPara probar la subrutina create() y comprobar que funciona bien, usamos este programa principal, que crea un nodo con un 1 en el campo NUM y un 0 en NEXT
#-- Prueba de la creación de un nodo
.include "servicios.asm"
.text
#-- Crear un nodo con NUM=1, NEXT=0
mv a0, zero
li a1, 1
jal create
#-- Terminar
li a7, EXIT
ecallLo ejecutamos, seleccionamos la visualización del HEAP y comprobamos que primero hay almacenado un 0 y luego un 1
El nodo creado lo representamos así:
Como ejemplo, creamos una lista con 3 nodos, cuyos datos serán 1, 2 y 3. Basta con llamar tres veces consecutivas a la función de crear nodo, pasándole como argumento del campo NEXT el puntero al nodo anteriormente creado, y como argumento para el campo NUM los números 1, 2 y 3 respectivamente
#-- Ejemplo de creación de una lista enlazada
#-- de tres nodos, inicializada con los valores
#-- 1,2 y 3
.include "servicios.asm"
.text
#-- Crear un nodo nuevo, inicializa a 1
mv a0, zero
li a1, 1
jal create
#-- Crear otro nodo, inicializado a 2
li a1, 2
jal create
#-- Crear otro nodo, inicializado a 3
li a1, 3
jal create
li a7, EXIT
ecallLo ejecutamos. Vemos en el HEAP cómo efectivamente están los 3 nodos. El primer campo de cada nodo contiene la dirección del siguiente nodo, salvo el del nodo cola, que contiene 0
En este dibujo se muestra el Heap, y cómo la lista creada está mapeada en él
Para imprimir los valores almacenados en la lista, hay que visitar todos los nodos, empezando por el apuntado por puntero de acceso (cabeza). Esta operación se denomina recorrer la lista
Como ejemplo, vamos a imprimir la lista creado en los apartados anteriores, que contiene (por este orden) los números 3, 2 y 1. Lo haremos usando un algoritmo iterativo y uno recursivo
Para recorrer la lista utilizaremos un puntero índice que irá apuntando a los nodos de la lista de forma secuencia. Este puntero inicialmente será igual al puntero de acceso
Si este puntero es NULL, entonces hemos terminado de recorrer la lista. De lo contrario, se trata de un nodo. Leemos el número contenido en este nodo y lo imprimimos. A continuación leemos el puntero al siguiente nodo (campo NEXT) y se lo asignamos a nuestro puntero índice
La función para imprimir la lista es print(), y como argumento se le pasa el puntero de acceso
El código es el siguiente:
#--------------------------------------
#-- Subrutina: Imprimir el contenido de una lista enlazada
#--
#-- ENTRADA:
#-- a0: Puntero al primer elemento de la lista
#--
#-- SALIDA: Ninguna
#------------------------------------------------------------
.include "servicios.asm"
.globl print
#---- Informacion sobre el nodo
.eqv NEXT 0 #-- Offset del campo NEXT
.eqv NUM 4 #-- Offset del campo NUM
.text
print:
#-- Usamos t0 para recorer la lista
mv t0, a0
next:
#-- Comprobar si hemos llegado al final
#-- Si el puntero es NULL, terminamos
beq t0, zero, fin
#-----Hay nodo: Imprimir su valor
#-- Leer numero
lw a0, NUM(t0)
#-- Imprimirlo en la consola
li a7, PRINT_INT
ecall
#-- Imprimir un salto de linea
li a0, '\n'
li a7, PRINT_CHAR
ecall
#-- Actualizar t0 para apuntar al siguiente nodo
#-- t0 = t0->next
lw t0, NEXT(t0)
#-- Repetir
b next
fin:
#-- Terminar
retPara probarlo ampliamos el programa principal que ya teníamos, para llamar a la función print una vez creada la lista:
#-- Ejemplo de creación de una lista enlazada
#-- Luego se imprime
.include "servicios.asm"
.text
#-- Crear un nodo nuevo, inicializa a 1
mv a0, zero
li a1, 1
jal create
#-- Crear otro nodo, inicializado a 2
li a1, 2
jal create
#-- Crear otro nodo, inicializado a 3
li a1, 3
jal create
#-- Imprimir la lista
#-- Se pasa por a0 el puntero a la lista
jal print
#-- Terminar
li a7, EXIT
ecallAhora lo ejecutamos. Vemos que se imprime en la consola, en orden inverso al que se han introducido los números. Esto es así porque hemos añadido los nuevos nodos por la cabeza de la lista
Las listas, al igual que sucedía con las cadenas, son elementos recursivos. Dentro de ellas encontramos otras listas. Hay un patrón estructural que se repite en varios niveles. Por ello podemos utilizar también algoritmos recursivos
En el ejemplo que estamos haciendo, según el puntero de acceso a la lista usado, tendremos una lista de tres elementos, de dos, de uno o una lista vacía. Estas sublistas están contenidas en la lista original
El algoritmo que implementaremos para imprimir la lista de forma recursiva es el siguiente:
def print_list(l):
#-- Es una lista vacia?
if len(l) == 0:
#-- Si: terminar
return
#-- No es una lista vacia
else:
#-- Imprimir el valor
print(l[0])
#-- Imprimir la sublista
print_list(l[1:])
returnY esta es su implementación en ensamblador
#--------------------------------------
#-- Subrutina: Imprimir el contenido de una lista enlazada
#-- Se imprime usando un algoritmo recursivo
#--
#-- ENTRADA:
#-- a0: Puntero a la lista a imprimir
#--
#-- SALIDA: Ninguna
#------------------------------------------------------------
.include "servicios.asm"
.globl print
#---- Informacion sobre el nodo
.eqv NEXT 0 #-- Offset del campo NEXT
.eqv NUM 4 #-- Offset del campo NUM
.text
print:
#-- Si es una lista vacia, terminar
beq a0, zero, fin
#-- No es una lista vacia
#-- Crear la pila para guardar la direccion de retorno
addi sp, sp, -16
sw ra, 12(sp)
#-- Usamos t0 para acceder al nodo
mv t0, a0
#-- Imprimir el valor del nodo
lw a0, NUM(t0)
li a7, PRINT_INT
ecall
#-- Imprimir '\n'
li a0, '\n'
li a7, PRINT_CHAR
ecall
#-- Obtener el puntero al siguiente nodo
lw a0, NEXT(t0)
#-- Imprimir la sublista
jal print
lw ra, 12(sp)
addi sp, sp, 16
fin:
#-- Terminar
retEl programa principal es el mismo que el que hemos usado con el algoritmo iterativo
La única manera de dominar algo, y de comprender perfectamente todos los detalles es practicando. No hay más secretos que practicar, y practicar, y pensar, y equivocarse, y pensar en porqué no funciona y probar cómo arreglarlo. Las veces que haga falta. Cuantas más, mejor
Escribe un programa principal para pedir al usuario que introduzca números enteros positivos. Cada número introducido se añadirá a la lista de números Cuando se introduzca un número negativo se termina la fase de entrada de datos y se imprime la lista
Reutilizar las funciones creadas en la sesión: create() y print()
Utilizar el programa principal del ejercicio 1. Crear una nueva función print() que imprime al lista en sentido inverso, usando este algoritmo recursivo:
def print_inv(l):
#-- Es una lista vacia?
if len(l) == 0:
#-- Si: terminar
return
#-- No es una lista vacia
else:
#-- Imprimir la sublista en orden inverso
print_inv(l[1:])
#-- Imprimir el valor del primer nodo
print(l[0])
returnEn esta animación se muestra en funcionamiento. Los números impresos salen en el mismo orden en que fueron introducidos
Escribir la función len() que calcule la longitud de una lista, usando un algoritmo iterativo. Tiene como argumento de entrada el puntero a la lista, y devuelve el número nodos que tiene. Modificar el programa principal del ejercicio 1 para que pida al usuario la lista de número, que llame a la funcion len() y que imprima la longitud de la lista
Implementar la función len() para calcular la longitud de una lista usando este algoritmo recursivo:
def len_list(l):
if len(l) == 0:
return 0
else:
return 1 + len_list(l[1:])Utilizar el mismo programa principal que en el ejercicio 4
Implementar la función sum() que realiza la suma de todos los elementos de la lista, mediante un algoritmo iterativo. Se le pasa como argumento el puntero a la lista y devuelve su suma. Utilizar el programa principal del ejercicio 1 para introducir la lista
Implementar la función sum() para calcular la longitud de una lista usando este algoritmo recursivo:
def sum_list(l):
if len(l) == 0:
return 0
else:
return l[0] + sum_list(l[1:])Utilizar el mismo programa principal que en el ejercicio 5
Programa la subrutina add() para añadir un número al final de la lista. Tiene como entrada dos argumentos: la lista y el número a añadir al final de la lista. El programa principal deberá crear un nodo con el número 1 (usando la función create()) y a continuación insertar los números 2 y 3. Luego se llamará a print() para imprimir la lista. En la consola aparecerá:
1
2
3
Implementar la función append() usando este algoritmo recursivo, descrito en pseudocódigo python:
def append_list(l,n):
#-- Si es el ultimo elemento
if l.next == 0:
#-- Crear nodo y enlazarlo
#-- con la lista
l.next = Crete(0, n)
else:
#-- Añadir el elemento en la sublista
append_list(l[1:],n)Queremos trabajar con cadenas en vez de con números enteros. Para ello necesitamos crear una lista enlazada que contenga cadenas. Cada nodo tiene la siguiente estructura:
- Campo STR: Contiene una cadena de caracteres (máximo: 19 caracteres). El offset del campo STR es 4
- Campo NEXT: Puntero al siguiente nodo. El offset del campo NEXT es 0
Así, el tamaño de cada nodo será de 24 bytes: 4 bytes para el campo NEXT (1 palabra>) y 20 bytes para el campo STR (5 palabras)
Se pide:
-
Escribir el código de la subrutina create_str() para crear un nodo de esta lista. Tiene un parámetro de entrada que es el campo NEXT a asignar al nodo creado. En el campo STR se guarda la cadena introducida por el usuario, llamando al servicio READ_STRING. La función create_str() no imprime ninguna cadena en la consola, sólo se queda esperando a que el usuario introduzca la cadena. Se devuelve el puntero al nodo creado
-
Escribir el código de la función print() que imprime todas las cadenas contenidas en la lista. Como parámetro se le pasa el puntero a la lista, y no devuelve nada
-
Escribir un programa principal de prueba, que cree dos nodos enlazados de esta lista, llamando dos veces consecutivas a create_str(), y luego llamando a print() para imprimir la lista creada. La lista de dos nodos creada crece por la cabeza (igual que en la lista de números enteros usada en esta sesión)
En esta animación se muestra el programa en funcionamiento
Crear un programa principal, usando la lista del ejercicio 9, para pedir al usuario nombres de personas que se almacenarán en la lista. El usuario puede introducir todos los nombres que quiera. Finalizará cuando introduzca una cadena nula (pulsando ENTER sin introducir ningún nombre). El programa imprimirá la lista creada llamando a print()
Un ejemplo de ejecución se muestra en esta animación:
- Katia Leal Algara
- Juan González-Gómez (Obijuan)
