Memoria Virtual
Fallos de Página
Algoritmos de Reemplazamiento
Cecilia Hernández
2007-1
Volviendo a Paginación
dirección virtual
npv
offset
Marco Pag 0
Marco Pag 1
Marco Pág 2
Marco Pag 3
nmp
nmp
offset
dirección física
npv: Num. página virtual
nmp: Num. marco página
Marco Pag 4
.
.
.
Marco Pag N
Cada Proceso tiene su propia tabla de página
Entradas de Tablas de Páginas (PTE)

Estructura de cada entrada en la tabla de páginas
 Usualmente mas que solo el número de marco de
página
1 1 1
2
V R M Prot
20
Marco de pagina
V : Bit válido. indica si página es válida
R : Bit de Referencia se setea cuando página ha
sido leída o escrito
M : Dirty bit, es seteado cuando la página ha sido
escrita
Prot : Bits de protección de Lectura, Escritura,
Ejecución
Memoria virtual usando paginación

Dijimos que un proceso no necesita estar
completamente en memoria física



Bueno donde está? El espacio de direccionamiento
completo se encuentra en disco (almacenamiento
secundario) en bloques paginados
El SO utiliza la memoria como cache de lo que esta en
disco (en base a páginas)
Una página del proceso en disco se carga en un marco
de página (para ello debe encontrarse un marco libre)
• SO normalmente tiene lista de marcos libres
• Normalmente páginas de procesos son cargadas a
memoria por demanda (Paginación por demanda)

Si no marcos libres y un proceso requiere uno, una
página ocupando un marco es sacada de memoria
• Se escriben a disco si han sido modificadas (dirty bit)

Esta acción es transparente a proceso de usuario
• Manejado por SO y Hardware
Fallos de página

Qué ocurre si un proceso referencia una dirección
virtual que se mapea a un marco que ha sido
quitado a la página




Cuando esto ocurrió bit válido de entrada en tabla de
página de proceso se puso en 0
Cuando proceso referencia entrada con bit inválido se
produce Fallo de página
Fallo de Página produce una interrupción y SO ejecuta
manejador de Fallo de página
Manejador
• Usa estructura de datos (parecida a tabla de página) que
contiene bloque de disco que contiene página
• Lee página a marco disponible, actualiza PTE
• SO reejecuta proceso que generó Fallo de página
Ilustración Fallo de Página
3
Rutina atención
Fallo Página
Estructura datos
SO
tabla de página
1
piezas disco
2
i
CPU
6
DISCO
Marco pagina
5
4
Memoria Física
Pasos en Fallo de Página






(1) Referencia a Memoria: Información de Memoria en PCB de proceso
captura proceso ejecuta una referencia a memoria inválida
(2) Si es inválida porque es ilegal, proceso es terminado. Si no, interrupción
fallo de página, se ejecuta rutina de atención
(3) SO encuentra marco de página libre donde cargar página de disco (SO
mantiene páginas de disco asociadas a páginas de proceso en una
estructura de datos manejada en SO)
(4) Lectura de página de disco a marco de página. Proceso se bloquea
durante esta transferencia
(5) Cuando lectura de disco se completa, se escribe en PTE bit válido y en
PCB de proceso que página esta disponible en memoria. Proceso pasa a
listo
(6) Se ejecuta de nuevo instrucción interrumpida por fallo de página
Paginación por Demanda

Técnica que permite otorgar páginas de memoria
a procesos a medida que lo necesiten

Similar a swapping in, pero sólo para el código y
datos requerido por el proceso
• Lo que proceso requiere en su ejecución varía en el
tiempo

Procesos residen en almacenamiento secundario
• Cuando proceso entra en ejecución páginas se van
cargando en memoria (desde disco) a medida que
se necesiten

SO actuales traen grupos de páginas (clusters)
• SO mantiene información de grupos que puede traer,
compilador también ayuda
Reemplazo de páginas

Cuando una página se lee de disco


Si hay marcos de páginas libres, obtener una
Si no SO debe obtener una de las ocupadas
• Reemplazo de páginas
• Algoritmos de reemplazamiento
• Obtener un marco que no se usará en el futuro
cercano
• Obtener un marco que no ha sido modificada
• SO trata de tener un número de marcos libres para no
tener que pagar costo de reemplazo en ese momento
Como se carga un programa?




Crea PCB de proceso
Crea tabla de página
Pone espacio de direccionamiento en disco en
piezas de tamaño de una página y construye tabla
que contiene mapeo de páginas y ubicación en
disco
Construye tabla de página (apuntada de PCB)


Todas las PTEs con bit inválido
Cuando proceso comienza su ejecución

Instrucciones fallan en páginas de código y datos a
medida que proceso va referenciando páginas de
código y datos
Parece complicado… Cómo que esto
funciona?

Cuál es la clave?

Localidad
• Temporal: referencias recientes tienden a ocurrir de nuevo
en el futuro cercano
• Espacial: referencias cercanas tienden a ocurrir de nuevo
en el futuro cercano

Buena localidad tiene como consecuencia paginación
menos frecuente
• Paginación en este caso vista como frecuencia de fallos
de página
• Idea es una vez que página ha sido cargada en memoria,
se referencia de nuevo pronto
• Pero esto depende de algunos factores
• Grado de localidad de aplicación
• Algoritmo de reemplazo de páginas
• Cantidad de memoria física disponible en relación a lo que
necesita proceso para ejecutar sin generar fallos de página
Paginación por Demanda y Conjunto de
trabajo

Cuando proceso comienza ejecución



Su tabla de páginas posee todas las entradas inválidas
Ninguna de sus páginas han sido mapeadas a memoria
(páginas no tienen asociadas marcos de página)
Cuando proceso empieza a ejecutarse
• Ejecución de instrucciones generan fallos de páginas
por código y datos
• Proceso deja de generar fallos de páginas cuando
tiene todas las páginas que necesita para ejecutarse
• Conjunto de trabajo cargado en memoria
Cuando la Memoria es Escasa?

Cuando queda poca memoria física libre, y nuevo
proceso se ejecuta

Nuevo proceso genera fallos de páginas para cargar
working set
• Si SO tiene marcos de páginas libres los otorga a proceso

Si no hay memoria, SO debe liberar páginas (marcos
asociados a páginas) de otros procesos o sí mismo
(pasarlos a disco) para otorgarse las a nuevo proceso
• Sólo se necesitan escribir si páginas han sido modificadas
• SO realiza movimiento de páginas memoria/disco
• Transparente a aplicación
• Que páginas elegir para reemplazar?
• Algoritmos de reemplazo de páginas
• Generalmente SO mantiene una lista de marcos libres y
cuando esta baja de un umbral ejecuta algoritmo de reemplazo
Fallo de Páginas 2

Qué ocurre con un proceso que referencia a dirección
virtual en una página, cuyo marco de página ha sido
reemplazado?



Cuando página fue reemplazada, el SO puso la página
como inválida (usando bit válido) en la entrada en la tabla de
páginas
Cuando proceso accesa la página, el bit inválido de la
entrada en tabla de página produce una excepción (fallo de
página)
SO ejecuta el manejador de fallo de página
• Si SO no posee marcos de páginas libres debe quitar una
página a un proceso para dar a proceso que la requiere
• Generalmente SO mantiene una lista de marcos libres y
cuando esta baja de un umbral ejecuta algoritmo de reemplazo
Reemplazamiento de Páginas

Objetivos de los algoritmos de reemplazamiento de
páginas


Disminuir la razón de fallos de páginas
seleccionando la mejor página “víctima” para
reemplazo
Ideal: La mejor página “víctima” es una que no
volverá a ser referenciada nunca
• Proceso que la posee no generará fallo de
página referenciándola
Algoritmos de Reemplazo Optimo
Algoritmo de Belady

Misma idea de SJF (algoritmo de planificación de procesos)



Por que es útil este algoritmo?


No, depende de carga de trabajo
Existe el peor algoritmo


Sirve como referencia para comparar otros algoritmos
Existe el mejor algoritmo


Seleccionar página que no será referenciada por el tiempo más
largo en el futuro
Problema: No se puede predecir el futuro
No, pero algoritmo aleatorio es uno de los malos
Por intuición si un sistema tiene más marcos de páginas
disponibles, cualquiera sea el algoritmo de reemplazo de páginas
ocurrirán menos fallos de páginas

Esto no se cumple siempre, a veces puede aumentar Esto se
conoce como la anomalía de Belady
Algoritmo de Reemplazo 2 : FIFO

Fácil de implementar

Lista de páginas del sistema
• Cuando SO asigna marco a página ponerla al final de la lista
• Cuando SO tiene que reemplazar página, saca la primera de la
lista

Por que podría ser bueno?


Quizás la página que entró a memoria primero ahora no
se necesita
Por que podría ser malo?



Quizás página esta en uso
No hay información en absoluto
Podría exponer anomalía de Belady
Algoritmo de Reemplazo 3 : Least Recently
Used (LRU)

LRU usa información acerca de referencias para
decidir que página es mejor como víctima


Idea: Referencias pasadas dan una idea del
comportamiento futuro
En reemplazo. elegir página que no ha sido usada por el
mayor tiempo
• LRU mira pasado y Belady mira futuro

Implementación
• Idealmente: Poner una marca de tiempo (timestamp) en cada
referencia a memoria y poner esta información en entrada de
página, ordenar búsqueda de acuerdo a marca de tiempo
• Muy cara
• En la práctica: Una aproximación
Aproximación para LRU

Muchas aproximaciones, todas usan bit R

Mantener un contador por cada página
• Periódicamente para cada página
• (1) If R == 0 then incrementar contador (no se ha usado)
• (2) If R == 1 then contador = 0 (se ha usado)
• Contador mantiene número de intervalos desde la última
referencia
• Página con mayor contador es la menos recientemente
usada
• Implementación es cara. Copia de registro, SO
mantención, cambio contexto, búsqueda página en tabla
para reemplazo
Algoritmo de Reemplazo 4 : LRU Reloj

LRU con Reloj. Página no usada recientemente o Segunda
Oportunidad


Reemplazar una página que es de las más viejas
Organizar los marcos de páginas en una cola circular FIFO y
recorrer cola buscando víctima de la siguiente manera
• Si bit R = 0 página es elegida para reemplazo
• Si bit R = 1 página ha sido usada, darle segunda oportunidad y poner bit
en 0 y seguir con la siguiente página



Puntero que recorre cola se mueve rápido cuando hay necesidad de
páginas
Si hay mucha memoria libre… baja sobrecarga
Si la memoria física es grande mas difícil de lograrlo bien
• Solución: agregar más punteros para elegir víctima
Asignando Marcos de Páginas


En un sistema multiprogramado se necesita
entregar memoria a procesos que compiten por su
asignación
 De donde elegir víctimas de mismo proceso o
diferente?
Algoritmos de espacio fijo (Local)
 Cada proceso tiene un límite de páginas que
puede usar
 Cuando proceso alcanza límite, páginas víctimas
son extraídas del mismo proceso
 Procesos grandes que requieren muchas de sus
páginas en memoria pueden sufrir
Asignando Marcos de Páginas cont

Algoritmos de espacio variable (Global)


Conjunto de páginas necesitadas por proceso varía en el
tiempo (tamaños de working sets cambian)
Reemplazo global, página víctima puede provenir de
cualquier proceso
• Algunos procesos pueden entorpecer ejecución del resto
• Linux usa este algoritmo
Conjunto de trabajo (Working set)




El working set de un proceso se utiliza para modelar la
localidad dinámica de su uso de memoria
Idea: Examinar conjunto de referencias a memoria más
recientes y mantener en memoria WS de procesos en el
tiempo con el objetivo de disminuir fallos de página
Working set de un proceso varía en el tiempo de acuerdo a
su localidad
Definición:

WS(t,w) = { páginas P tal que P fue referenciada en periodo de
tiempo (t, t-w) }

t es tiempo y w es la ventana del working set. Página p
está en WS sólo si fue refereciada en las últimas w
referencias
Conjunto de trabajo

Ejemplo: Ventana de 10 referencias

Tamaño de conjunto de trabajo = 4
215777775162937


WS(t1,10) = {1, 2, 5, 7}
Qué ocurre con el tamaño de conjunto de trabajo
cuando disminuye su localidad o expone mala
localidad?
Por intuición, el conjunto de trabajo debe estar en
memoria si no entonces habrían muchos fallos de
página (thrashing)

Cuando alguien pregunta: Cuánta memoria necesita firefox?
la pregunta es mas bien, cuál es el tamaño promedio ( o
peor caso) del conjunto de trabajo de firefox?
Algoritmo de Reemplazo 5: usando Conjunto
de trabajo (Working Set)

El working set de un proceso cambia con la localidad
de proceso





Durante periodos de poca localidad, frecuencia de fallos de
páginas aumenta
Durante este periodo tamaño de working set es grande
Intuición dice que el working set de un proceso debe estar en
memoria para disminuir notablemente el número de fallos de
página
Usa LRU clock para asegurarse de tener páginas correctas en
WS
Algoritmo
• Iniciar nuevo proceso sólo si su working set cabe en memoria
• Si suma de working sets de procesos excede memoria física,
entonces se puede suspender un proceso y ejecutarlo más
tarde
• Cuál debería ser la ventana para conjunto de trabajo de proceso?
Algoritmo de Reemplazo 6: Frecuencia de
Fallo de Página

Algoritmo de espacio variable
 Monitorear la frecuencia de fallo de página de
proceso
 Si la frecuencia pasa un umbral superior darle
más memoria

Si la frecuencia baja de un umbral inferior
quitarle memoria al proceso
• Proceso debería fallar más, pero permitir que otro
proceso falle menos

No funciona siempre
Frecuencia fallos de página
Razón de fallos de página
Aumentar número
de marcos
Umbral superior
Disminuir número
de marcos
Umbral inferior
Número de marcos asignados por proceso
Número de referencias a memoria entre fallos de página
Fallos de página
Qué pasa?
Qué pasa?
Donde es mejor
operación?
Número de marcos asignados por proceso
Rendimiento con Paginación con Demanda

Si no hay fallos de página





Tiempo efectivo de acceso a memoria depende de :
• tasa de aciertos (hits) de caches (datos y/o TLB)
• costos en tiempo de acceso a caches y memoria
En general se define como
Tiempo efectivo de acceso a memoria =TEAM
TEAM = %aciertos*(costo acierto) + %fallas*(costo falla)
Si hay fallos de página

Tiempo de acceso efectivo = (1 – p)*TEAM + p*(costo fallo
de página)
• donde p es la probabilidad de fallos de páginas
Hiperpaginación

Cuando un proceso tiene una alta razón de fallo
de páginas




SO pasa mucho tiempo atendiendo fallos de página
(pasando páginas de disco a memoria y viceversa)
La CPU esta principalmente utilizada haciendo trabajo
de administración que trabajo útil
Podría ser simplemente que sistema no cuenta con la
memoria necesaria para atender a todos los procesos
Puntos importantes

Si sistema tiene mucha memoria
• Algoritmo de reemplazo no tiene tanta incidencia
• Si no entonces algoritmo de reemplazo si la tiene
%Utilización de CPU o Productividad (reqs/segs)
Hiperpaginación
Qué ocurre aquí?
Numero de procesos activos
Nivel de multiprogramación
Resumen

Paginación por demanda


Algoritmos de reemplazo de páginas







Inicialmente proceso no tiene páginas cargadas, SO las carga a
medida que proceso lo necesita (a través de fallos de página)
Belady : Óptimo, pero no se puede realizar
FIFO: reemplazar página que fue cargada hace más tiempo
LRU: reemplazar página que fue referenciada hace más tiempo
LRU reloj: reemplazo LRU con segunda oportunidad
Working Set: mantener en memoria páginas que incluyen menor
razón de fallo de página
Frecuencia de Fallo de páginas: variar número de marcos en
base a umbrales de fallos de páginas
Reemplazamiento local o global
Descargar

Algoritmos de Reemplazamiento