Memoria Gesti N1

Paginación – Carga Dinámica
• Paginación Carga Dinámica
3

La página está
en memoria auxiliar

Programa
Referencia
1
6
Reiniciar
la instr.

2

Excepción

Memoria
secundaria

Memoria
principal
Tabla de
páginas

5
Actualizar la
tabla de páginas

4 Cargar la
página que
falla

Paginación – Mecanismo de acceso
• Mecanismo de acceso a instrucciones y datos
– Buscamos en el 1er nivel (Caché)
– Si estáse toma  Éxito
– Si no está se accede al siguiente nivel
• Buscamos en el 2º nivel si procede (Memoria
principal)
– Si está se toma y se pasa al 1er nivel
– Si no está se accede al nivel siguiente
– Se toma del 3er nivel (Memoria secundaria)

Paginación - Mecanismo
• Parámetros de eficiencia
– Si se encuentra  Acierto (HIT)
– Si no se encuentra  Fallo (MISS)
– Tasa de aciertos Acierto/(A+F)
– Tasa de fallos  Fallo/(A+F)
• Tiempo de Acierto incluye:
– Tiempo de acceso a nivel superior
– Tiempo de comprobación de si existe en ese
nivel

Paginación - Mecanismo
• Penalización de fallo incluye:
– Tiempo en sustituir un bloque del nivel superior

Reemplazo de páginas
• Se selecciona la página víctima mediante un
algoritmo de reemplazo.
• Si la página víctima había sido modificadadurante
su estancia en memoria, hay que escribirla en el
dispositivo de paginación (page-out). Si no, esta
operación no es necesaria.
• Se pone a cero el bit de validez correspondiente a
la página víctima en su tabla de páginas.

Reemplazo – Cadenas de referencia
•
•

•

Es finita y determinista (Solo se utiliza un proceso)
Se utiliza para evaluar la calidad de los algoritmos de
sustitución
La cadenade referencia se puede obtener:
aleatoriamente
grabando una traza de ejecución

Para determinar el número de fallos de página es necesario
conocer el número de marcos disponible
Si se referencia una página p, las referencias inmediatamente
sucesivas a esa página nunca causarán fallo de página
Si el número de marcos aumenta, en general, el número de
fallos de página disminuye

Algoritmos dereemplazo de páginas









Criterios utilizados para valorar los algoritmos de
sustitución:

Baja sobrecarga

Sin ajustes “No tuning”

Aproximación al LRU (menos usada recientemente)
Existen diferentes algoritmos, entre ellos:
Algoritmo óptimo
Algoritmo FIFO
Algoritmo LRU
Algoritmos de aproximación al LRU
El algoritmo de referencia es el algoritmo óptimo.

Algoritmo óptimo
• Sustituye lapágina que va a tardar más tiempo en
ser usada
– Bajar la tasa de fallos
– No es realizable y
– Solo se usa como referencia

Algoritmo óptimo
Ejemplo:
7

Cadena de referencia
0

1

2

0

3

0

4

2

3

0

Marcos de página

8 fallos de página

3

2

1

2

0

Algoritmo FIFO - PEPS
Sustituye la página que lleva más tiempo en
memoria.
Ejemplo: Cadena de referencia.
7 0 1 2 0 3 0 4 2 3

0

Marcos depágina

12 fallos de página

3

2

1

2

0

Ejecutar el algoritmo FIFO con 3 marcos
• Cadena de referencia:
5, 0, 2, 0, 1, 3, 0, 7, 2, 3, 0, 3, 1, 2, 1 y 0

Algoritmo FIFO - (First In-First Out)
•

•

Es un algoritmo sencillo de entender e implementar
Inconvenientes:
o
El rendimiento del algoritmo es pobre, debido a
que páginas frecuentemente usadas pueden
ser sustituidas.
o

Se puede producir laAnomalía de Belady:
aumento del número de fallos de página al
aumentar el número de marcos. (Ejecutar una
secuencia anterior con 3 marcos y una con 4
marcos)

Anomalía de Belady
•

•

•

•
•

Lo normal es esperar menos fallos cuando se
dispone de más marcos de memoria
En el algoritmo se sustitución FIFO puede
aumentar el número de fallos al aumentar el
número de marcos asignados a un proceso
Porejemplo para la siguiente secuencia:
123412512345
Con tres marcos se producen 9 fallos y con 4 se
producen 10 fallos!

Anomalía de Belady
Ejemplo:
1

2

Con 3 y 4 marcos de página
3

4

1

2

5

1

2

3

Con 3 marcos, 9 fallos de página

Con 3 marcos, 9 fallos de págna
Con 4 marcos, 10 fallos de página

4

5

Algoritmo LRU – Least Recently Use









Algoritmo de aproximación al...