Memoria Asociativa, Paginación y Estrategias de Reposición en Sistemas de Memoria Virtual

Memoria Asociativa y su Funcionamiento

La memoria asociativa guarda pares (clave, valor). Cuando se le presenta la clave, busca simultáneamente en todos sus registros y retorna, en pocos nanosegundos, el valor correspondiente. La memoria asociativa es costosa, razón por la cual los TLBs (Translation Lookaside Buffers) rara vez contienen más de 64 registros.

Paginación y TLB

Por pequeño que sea el TLB, la probabilidad de que la página esté en él (tasa de aciertos) es alta, porque los programas suelen hacer muchas referencias a unas pocas páginas. Un Intel 80486 tiene 32 entradas en el TLB; Intel asegura una tasa de aciertos del 98%. En cada cambio de contexto, hay que limpiar el TLB, lo que puede ser barato, pero hay que considerar un costo indirecto: si los cambios de contexto son muy frecuentes, la tasa de aciertos se puede reducir.

Paginación por Demanda

Constituye el sistema de memoria virtual más corriente. La referenciación de una página no residente en memoria se conoce como fallo de página. Un fallo de página es causal de una colocación en algún marco disponible. La no existencia de marcos disponibles es causal de una reposición.

Cálculo del Tiempo Efectivo de Direccionamiento

Para un proceso en ejecución, si t_e es el tiempo efectivo de direccionamiento en un sistema de paginación por demanda, entonces:

t_e = (1 - p) * t_m + p * t_f

Donde p es la probabilidad de ocurrencia de un fallo de página, t_m el tiempo de acceso a memoria y t_f el tiempo de servicio destinado a la atención de un fallo.

Componentes del Tiempo de Servicio de un Fallo (t_f)

t_f = t_i + t_d + t_c + t_r

• t_i: Tiempo necesario para atender una interrupción por fallo.
• t_d: Tiempo de descarga de una página.
• t_c: Tiempo de carga de una página.
• t_r: Tiempo de reinicio del proceso.

Sin embargo:

• Inexistencia de reposición ⇒ t_d = 0
• Inexistencia de fallo ⇒ t_f = 0

Estrategias de Reposición

El algoritmo óptimo será aquel que:

• Seleccione para ser reemplazada la página que vaya a tardar más en ser utilizada.
• Tenga menos fallas en relación con la cantidad de marcos disponibles.
• Ocupe menos recursos en su utilización (cueste menos).

Algoritmo FIFO (First-In, First-Out)

• Más sencillo.
• Cuando se necesita sustituir una página, se elige aquella que lleve más tiempo en memoria.
• El rendimiento de esta estrategia se ve afectado por las páginas de uso frecuente.

Algoritmo OPT (Óptimo)

• Se escoge aquella página que no se utilizará durante el máximo período de tiempo.
• El rendimiento de esta estrategia es el óptimo, pues presenta la mínima tasa de fallos de página.
• Difícil de implementar.

Algoritmo LRU (Least Recently Used)

• Se escoge aquella página que no se ha utilizado durante el máximo período de tiempo.
• El sistema debe contabilizar de alguna manera el uso de las páginas en memoria.

Hiperpaginación (Thrashing)

A una alta actividad de paginación se le llama hiperpaginación (thrashing). Un sistema está en hiperpaginación si emplea más tiempo paginando que ejecutando.

Localidad

• Conjunto de páginas que se utilizan conjuntamente.
• Un proceso está compuesto por varias localidades distintas.
• Están definidas por la estructura del programa y sus estructuras de datos.
• Si se asignan menos marcos que el tamaño de la localidad, el proceso entrará en hiperpaginación, ya que no puede mantener en memoria todas las páginas que está usando en ese momento.