PUERTA | PUERTA CS 2010 | Pregunta 37

El siguiente programa utiliza seis variables temporales a, b, c, d, e, f.

 
    a = 1
    b = 10
    c = 20
    d = a+b
    e = c+d
    f = c+e
    b = c+e
    e = b+f
    d = 5+e
    return d+f

Suponiendo que todas las operaciones toman sus operandos de los registros, ¿cuál es el número mínimo de registros necesarios para ejecutar este programa sin derramar?
(A) 2
(B) 3
(C) 4
(D) 6

Respuesta: (B)
Explicación: Todas las expresiones dadas usan como máximo 3 variables, por lo que nunca necesitamos más de 3 registros.

Ver   http://en.wikipedia.org/wiki/Register_allocation

Requiere mínimo 3 registros.

Principio de Asignación de Registros : Si una variable necesita ser asignada a un registro, el sistema busca cualquier registro libre disponible, si encuentra uno, lo asigna. Si no hay un registro libre, busca un registro que contenga una variable inactiva (una variable cuyo valor no se utilizará en el futuro), y si encuentra uno, lo asigna. De lo contrario, va por derrame (verifica un registro cuyo valor se necesita después de un tiempo prolongado, guarda su valor en la memoria y luego usa ese registro para la asignación actual, más tarde, cuando se necesita el valor anterior del registro, el sistema obtiene de la memoria donde se guardó y asignarlo en cualquier registro que esté disponible).

Pero aquí no deberíamos aplicar el derrame como se indica en la pregunta.

(digamos que el registro R1 está asignado para la variable ‘a’)

(R2 para ‘b’, porque el valor de ‘a’ se utilizará en el futuro, por lo tanto, no se puede reemplazar la variable de ‘a’ por la de ‘b’ en R1)

(R3 para ‘c’, porque los valores de ‘a’ y ‘b’ se usarán en el futuro, por lo tanto, no se puede reemplazar la variable ‘a’ o ‘b’ por ‘c’ en R1 o R2 respectivamente)

(ahora, ‘d’ se puede asignar a R1 porque R1 contiene una variable muerta que es ‘a’ y se llama así porque no se usará en el futuro, es decir, ninguna expresión posterior usa el valor de la variable ‘a’)

(‘e’ se puede asignar a R1, porque actualmente R1 contiene el valor de varibale ‘d’ que no se utilizará en la expresión posterior).

Nota : un valor ya calculado de una variable se usa solo para la operación de LECTURA (no para ESCRITURA), por lo tanto, solo debemos ver en el lado derecho de las expresiones posteriores si la variable se usará o no.

(‘f’ se puede asignar a R2, porque el valor de ‘b’ en el registro R2 no se usará en expresiones posteriores, por lo tanto, R2 se puede usar para asignar ‘f’ reemplazando ‘b’)

(‘b’ se puede asignar a R3, porque el valor de ‘c’ en R3 no se usa más adelante)

(aquí ‘e’ ya está en R1, por lo que no hay asignación aquí, asignación directa)

(‘d’ se puede asignar a R1 o R3, porque los valores en ambos no se usan más, asignemos en R1)

(sin asignación aquí, simplemente se agregan y devuelven los contenidos de los registros R1 y R2)

por lo tanto, solo necesitamos 3 registros, R1 R2 y R3.

 
Cuestionario de esta pregunta