Practico 10. Ejercicio 3

Practico 10. Ejercicio 3

de Agustina Moraes Nuñez -
Número de respuestas: 4

Hola, mirando la solución del ejercicio 3 del practico 10 me surgieron varias dudas.

En primer lugar, en la rutina en assembler 8086 no me queda claro por qué para acceder a la dirección de memoria donde se encuentra un nodo siempre se hace primero un shift a la izquierda de dos lugares. Supongo que esto se hace para quedarnos solo con el desplazamiento ya que se sabe que el segmento donde se encuentra el arreglo árbol es el ES y luego para acceder a dicha posición se accede a ES:[BX], pero igual no entiendo por qué la cantidad que se desplaza es 2 ni tampoco qué es concretamente lo que viene guardado en BX cuando se llama al procedimiento findNumber.

Por otro lado, en la parte C, para calcular el tamaño de stack necesario para un árbol en las condiciones del peor caso se considera el caso en que n (la cantidad de nodos del árbol) es 0, pero en la letra dice que el árbol tiene por lo menos un elemento. Entonces el paso base no tendría que ser f(1) en vez de f(0)? O hay algo que interpreté mal?

Otra duda de esta parte es que f(0) lo calcula como f(0) = 4 bytes (2 de la dirección de retorno y 2 de BX), pero tengo entendido que se van a hacer dos CALL al procedimiento findNumber, uno para verificar el subarbol izquierdo (que va a tener un cero) y otro para verificar el derecho (que también va a tener un 0). Entonces ahí no se necesitarían 4 bytes para la dirección de retorno? Porque al hacer CALL se pushea en el stack CS e IP, que cada uno ocupa 2 bytes y además se hacen 2 CALLs sumando un total de 4 bytes.

Por último, no entiendo por qué para el cálculo de la cantidad máxima de nodos que puede tener un árbol, en el punto 1. se considera que el tamaño de un nodo es 4 (yo pensaría que es 3 porque se guarda el dato, el nodo izquierdo y el derecho), y por qué se le resta 1 a esta cantidad. Vi la justificación de por qué se resta 1 (“el nodo correspondiente al offset 0 no se utiliza”) pero no me queda claro por qué habría un nodo que contiene el desplazamiento y si este nodo se encuentra antes de todos los nodos del árbol y por eso se considera que el tamaño de cualquier nodo es 4-1.

Puede ser que varias de estas dudas las tenga porque no entendí del todo cómo funciona el tema de los segmentos y los desplazamientos, y puede ser que esto sirva para aclarar. Les agradezco mucho si me pueden ayudar!


En respuesta a Agustina Moraes Nuñez

Re: Practico 10. Ejercicio 3

de Gustavo Brown -

Agustina,

  El parámetro que se recibe en BX es el índice del nodo actual en el árbol. Esto lo dice en la letra del problema (parte b). El árbol está dispuesto en memoria como un arreglo de nodos, donde cada nodo tiene además del dato asociado al nodo los índices de los hijos izquierdo y derecho.

Para calcular el desplazamiento del nodo en memoria (teniendo en cuenta que el árbol reside en el segmento ES a partir del desplazamiento 0) se debe multiplicar el índice del arreglo por el tamaño de cada nodo. En este caso cada nodo ocupa 4 bytes (2 para almacenar el dato, 1 para el hizo izquierdo y otro para el hijo derecho).  Entonces dado un índice el desplazamiento asociado se obtiene multiplicando el índice por 4. Para hacer esa cuenta la solución realiza un corrimiento a la izquierda de dos lugares.

Si cada nodo ocupase otra cantidad de bytes, tendrías que cambiar la cuenta. Por ejemplo si cada nodo ocuapase 6 bytes tendrías que multiplicar el índice por 6.

Para  calcular consumo de stack del peor caso tenés que visualizar cuál es el peor caso y ver en qué momento de la ejecución del algoritmo se consume la mayor cantidad de bytes en el stack. No importa que por letra se indique que el árbol no está vacío, el peor caso no es el de un árbol vacío. Los "casos base" son todos aquellos donde termina la recursión del algoritmo. Si te fijas en el código va a ver que el caso base se da cuando indiceArbol es igual a 0, o sea se chequea si (en la recursión) estoy parado en un índice inválido (el indice 0 en este ejercicio esta reservado para indicar un nodo inválido).

Entonces en este ejercicio el paso base se da cuando la función recibe 0 como índice (BX=0 en assembler), por lo tanto para un árbol de altura N se hacen N pasos recursivos y un paso base. Como tanto el paso recursivo como el base ocupa 4 bytes, ocurre que el consumo de stack para un árbol de altura N (que coincide con un árbol degenerado en lista de N nodos) es 4*(N+1).

Para f(0) el consumo de stack son 2 bytes para la dirección de retorno y 2 bytes del PUSH BX de la primer línea del procedimiento. Para el caso recursivo también son 2 bytes de la dirección de retorno y otros 2 del PUSH BX. Entre la primer y segunda llamada recursiva no se consume más stack (se hace POP y PUSH de BX) por lo que no hay contexto extra almacenado para la segunda llamda recursiva. Recordar que lo que hay que contar es el peor caso de consumo de stack, cuando se realiza la segunda llamada recursiva todo el stack consumido por la primera ya fue recuperado.

Lo del tamaño de cada nodo lo expliqué al comienzo de este mensaje, ocupa 4 bytes (2 para el dato y 1 para cada indice izquierdo y derecho).

Lo último que comentas que el tamaño de cualquier nodo es 4-1 no lo entiendo. El tamaño de cada nodo es 4 bytes. La cantidad máxima de nodos del árbol es la más restrictiva que soporta el problema. Por un lado está acotado por el tamaño de un segmento y por otro lado por la cantidad de índices distintos que se puedan referenciar. El análisis en la solución llega a que la segunda es más restrictiva siendo la cantidad de nodos en ese caso de 255.

Saludos,
  Gustavo




En respuesta a Gustavo Brown

Re: Practico 10. Ejercicio 3

de Agustina Moraes Nuñez -
Gustavo muchas gracias por la respuesta! Me queda claro ahora que en BX viene el índice del árbol y no una dirección de memoria y también por qué se multiplica el índice por 4.
Además vi que en la parte C no hace 64K / (4 -1) sino que hace (64K / 4) - 1 y esto último si tiene sentido porque se está calculando la cantidad de nodos que podría haber como máximo, que es el tamaño del segmento divido 4 pero teniendo en cuenta que el índice 0 no puede ser considerado un espacio de memoria donde iría un nodo porque como dijiste ese índice está reservado, y entonces se resta 1.
También entendí que el paso base es 0 porque se llama al procedimiento con este índice en BX, pero lo que me sigue generando duda es que se consuman 4 bytes para el paso recursivo, porque aunque se esté considerando el caso en que el árbol es una lista, tengo entendido que lo que se guarda en el stack al ejecutarse findNumber es:
- IP (dirección para retornar a la dirección luego de terminada la ejecución)
- BX (el índice con el que se llama al procedimiento en ese paso)
- IP (dirección para retornar luego de la llamada al procedimiento con el hijo izquierdo, que luego se saca del stack al ejecutar la instrucción RET)
- BX (el índice del hijo izquierdo, que luego se saca del stack si suponemos que este es el subárbol vacío, ya que saltaría a la etiqueta not_found y luego a la etiqueta end que hace POP BX)
- f(n-1) (lo que consume la llamada recursiva con el hijo derecho que es no vacío)
Entonces los dos BX ocuparían 2 bytes cada uno y también hay dos IP que tengo entendido que ocupan 2 bytes cada uno por ser registros de 8086.
Gracias de nuevo!
En respuesta a Agustina Moraes Nuñez

Re: Practico 10. Ejercicio 3

de Gustavo Brown -

Agustina,

  El paso baso es el paso donde termina la recursión. Todo paso arranca *antes* del comienzo de la rutina, al PUSHear los parámetros que se pasen por stack y hacer el CALL a la rutina. En este caso no hay parámetros pasados por stack así que arranca en el CALL a la rutina.

Luego en este ejercicio tenes 2 puntos de llamadas recursivas (sub arbol izquierdo y sub arbol derecho), y tenes que calcular cuanto stack se ha consumido hasta el comienzo de la primer llamada recursiva, y por otro lado compararlo con el consumo hasta el comienzo de la segunda llamada recursiva. En este caso el único contexto guardado es el registro BX que se PUSHea al comienzo de la rutina por lo que el peor caso se va a dar para un árbol que degenere en lista tanto sea por la izquierda como por la derecha. Hay que tener cuidado de no contar 2 veces el mismo contexto (al llamar y al considerarlo como paso recursivo). Por ejemplo en tu comentario hablas del paso recursivo que tiene guardados 2 IPs distintos y 2 BX distintos, por lo que parece que estas contando 2 veces el contexto (el del llamador y el del llamado), 

En este ejercicio el análisis sería así:
 Para el caso base tenemos 4 bytes de consumo, f(0) = 4:

 - 2 bytes de la dirección de retorno (al hacer el CALL a la rutina con indice 0)
 - 2 bytes del PUSH BX del comienzo de la rutina,

Cuando se trata del paso base se salta a "not_found" que recupera BX y RETorna liberando los 4 bytes.

Para paso recursivo también tenemos 4 bytes de consumo, que en este caso coinciden con los 4 del paso base. Es decir:

 -  2 bytes por el CALL a la rutina
 -  2 del contexto que se guarda al comienzo. 

Al ser el paso recursivo en vez de saltar a "not_found" ejecuta las llamadas recursivas (sub arbol izquiero y sub arbol derecho) pero no guarda ningún contexto adicional. 

O sea que para el caso recursivo se tiene f(n) = 4 + max(f_izquierdo(n-1) , f_derecho(n-1)). Si suponemos que el árbol degeneraba en lista por izquierda simplificamos la ecuación a f(n) =  4 + f(n-1) que es lo que muestra la solución. 

Saludos,
  Gustavo