Tema 10.4: Gestión de Memoria Virtual
Antecedentes
 Memoria virtual – separación de la memoria lógica de la física

Sólo parte del programa necesita estar en memoria en un
momento dado para continuar su ejecución

El espacio de direcciones lógicas puede ser mayor que el
espacio de direcciones físicas

Permite compartir espacios de direcciones entre procesos

Permite una creación de procesos más eficiente
 La memoria virtual suele implementarse usando:

Paginación por demanda

Segmentación por demanda
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 2
Silberschatz, Galvin and Gagne ©2005
Memoria Virtual Mayor que la Memoria Física

Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 3
Silberschatz, Galvin and Gagne ©2005
Espacio de Direcciones Virtuales
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 4
Silberschatz, Galvin and Gagne ©2005
Paginación por Demanda
 Trae una página a memoria sólo cuando hace falta

La E/S se reduce

Se requiere menos memoria

La respuesta es más rápida

Puede haber más procesos en memoria
 Se necesita una página  la página es referenciada

referencia inválida  aborta

no está en memoria  se trae a memoria
 “Intercambiador” perezoso – nunca trae una página a memoria
salvo si es necesario

El intercambiador que trabaja con páginas es un paginador
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 5
Silberschatz, Galvin and Gagne ©2005
Bit de Validez

En cada entrada de la tabla de páginas hay un bit de validez
(v  en memoria, i  no en memoria o acceso ilegal)

Al comienzo el bit de validez es inicializado a i en todas las entradas

Ejemplo de tabla de páginas:
# Marco
Bit de validez
v
v
v
v
i
….
i
i
Tabla de páginas

Durante la traducción de direcciones, si el bit de validez de la entrada de
la tabla de páginas es i  fallo de página
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 6
Silberschatz, Galvin and Gagne ©2005
Tabla de Páginas cuando hay Páginas Ausentes
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 7
Silberschatz, Galvin and Gagne ©2005
Fallo de Página
 La primera referencia a una página producirá una
excepción capturada por el SO:
fallo de página
1. El SO mira en la tabla de páginas para decidir qué hacer:
 Referencia inválida  aborta
 No está en memoria  continúa
2. Obtiene un marco libre
3. Carga la página en el marco
4. Resetea las tablas
5. Establece el bit de validez a v
6. Reinicia la instrucción que causó el fallo de página
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 8
Silberschatz, Galvin and Gagne ©2005
Fallo de Página


Instrucciones problemáticas para el reinicio de instrucción

Instrucciones de cadenas

Auto incremento/decremento
Soluciones

Comprobar antes de ejecutar la instrucción que no va a
producirse un fallo de página

Almacenar los valores antiguos en registros temporales

Guardar el estado del microcódigo del procesador
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 9
Silberschatz, Galvin and Gagne ©2005
Pasos del Manejo de un Fallo de Páginas
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 10
Silberschatz, Galvin and Gagne ©2005
Rendimiento de la Paginación por Demanda
 Tasa de fallo de páginas 0  p  1

si p = 0, no hay fallo de páginas

si p = 1, cada referencia produce un fallo
 Tiempo de acceso efectivo (EAT)
EAT = (1 – p) x acceso a memoria
+ p (sobrecarga por fallo de página
+ escribir página
+ traer página
+ sobrecarga de reinicio
)
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 11
Silberschatz, Galvin and Gagne ©2005
Ejemplo de Paginación por Demanda
 Tiempo de acceso a memoria = 200 ns
 Promedio del tiempo de servicio de un fallo de páginas = 8 ms
 EAT = (1 – p) x 200 + p x 8.000.000
= 200 + p x 7.999.800
 Si uno de cada 1.000 accesos causa un fallo de páginas
EAT = 8,2 μs
El tiempo de ejecución se reduce en un factor de 41!!
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 12
Silberschatz, Galvin and Gagne ©2005
Qué Pasa Si No Hay Marco Libre?
 Reemplazo de páginas – encuentra una página en memoria
que no se esté usando y la retira

se usa un algoritmo de reemplazo

objetivo – minimizar el fallo de páginas
 La misma página podría ser traída a memoria varias veces
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 13
Silberschatz, Galvin and Gagne ©2005
Reemplazo de Páginas
 Previene la sobreasignación de memoria modificando la rutina de
fallo de páginas para incluir el reemplazo de páginas
 Se usa el bit de modificado (suciedad) para reducir la
sobrecarga por transferencias de páginas – sólo las páginas
modificadas se escriben a disco
 El reemplazo de páginas completa la separación entre la memoria
lógica y la memoria física – se puede proporcionar una gran
cantidad de memoria virtual sobre una menor memoria física
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 14
Silberschatz, Galvin and Gagne ©2005
Necesidad de Reemplazo de Páginas
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 15
Silberschatz, Galvin and Gagne ©2005
Reemplazo de Páginas Básico
1.
Encontrar la ubicación de la página deseada en disco
2.
Encontrar un marco libre:
- Si hay un marco libre, usarlo
- Si no hay un marco libre, usar un algoritmo de
reemplazo para escoger el marco víctima
3.
Traer la página deseada al (nuevo) marco libre;
actualizar las tablas de páginas y de marcos
4.
Continuar con la ejecución del proceso
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 16
Silberschatz, Galvin and Gagne ©2005
Reemplazo de Páginas
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 17
Silberschatz, Galvin and Gagne ©2005
Algoritmos de Reemplazo de Páginas
 El objetivo es una tasa de fallos de página lo más baja posible
 Los algoritmos se evalúan ejecutándolos sobre una cadena
de referencias a memoria y calculando el número de fallos de
página producidos con esa cadena
 En todos nuestros ejemplos, la cadena de referencias será
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 18
Silberschatz, Galvin and Gagne ©2005
Fallo de Páginas Frente a Número de Marcos
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 19
Silberschatz, Galvin and Gagne ©2005
Algoritmo First-In-First-Out (FIFO)

Cadena de referencias: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

3 marcos (3 páginas en memoria por proceso)


1
1
4
5
2
2
1
3
3
3
2
4
1
1
5
4
2
2
1
5
3
3
2
4
4
3
9 fallos de página
4 marcos
10 fallos de páginas
Anomalía de Belady: más marcos  más fallos de página
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 20
Silberschatz, Galvin and Gagne ©2005
Reemplazo de Páginas FIFO
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 21
Silberschatz, Galvin and Gagne ©2005
Anomalía de Belady
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 22
Silberschatz, Galvin and Gagne ©2005
Algoritmo Óptimo
 Reemplaza la página que será usada más tarde
 Ejemplo con 4 marcos
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
1
4
2
6 fallos de página
3
4
5
 En general, no conocemos los accesos futuros a memoria
 Este algoritmo se usa para estudiar el rendimiento de otros
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 23
Silberschatz, Galvin and Gagne ©2005
Reemplazo de Páginas Óptimo
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 24
Silberschatz, Galvin and Gagne ©2005
Algoritmo (LRU, Least Recently Used)
 Cadena de referencias: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
1
1
1
1
5
2
2
2
2
2
3
5
5
4
4
4
4
3
3
3
 Implementación con contador

Cada entrada de página tiene un contador; cada vez que la
página es referenciada se copia la hora en el contador

Cuando una página necesita ser cambiada, se miran los
contadores para determinar cuál se cambia
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 25
Silberschatz, Galvin and Gagne ©2005
Reemplazo de Páginas LRU
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 26
Silberschatz, Galvin and Gagne ©2005
Algoritmo LRU
 Implementación con pila – se mantiene una pila de números de
página:

Cuando una página es referenciada:


Se mueve a la cabeza de la pila
En el reemplazo se escoge la página de la cola de la pila
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 27
Silberschatz, Galvin and Gagne ©2005
Algoritmos de Aproximación al LRU
 Bit de referencia

Con cada página se asocia un bit, inicialmente puesto a 0

Cuando se referencia una página el bit se pone a 1

Se reemplaza la página con el bit a 0 (si hay alguna)

Esto no permite conocer el orden de uso
 Algoritmo de segunda oportunidad

Necesitamos un bit de referencia

También se denomina algoritmo de reloj

Si la página a reemplazar (de acuerdo al orden del reloj) tiene
el bit de referencia a 1:

Se pone el bit a 0

Se deja la página en memoria

Trata de reemplazar la siguiente página siguiendo el orden
del reloj
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 28
Silberschatz, Galvin and Gagne ©2005
Algoritmo de Segunda Oportunidad (de Reloj)
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 29
Silberschatz, Galvin and Gagne ©2005
Algoritmos de Conteo
 Se necesita un contador con el número de referencias que se
han hecho a cada página
 Algoritmo LFU: reemplaza la página con el valor más bajo
en el contador
 Algoritmo MFU: reemplaza la página con el valor más alto
en el contador

Se basa en el argumento de que la página con el número
más pequeño en el contador acaba de ser traída y aún
no se usa
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 30
Silberschatz, Galvin and Gagne ©2005
Asignación de Marcos
 Cada proceso necesita un número mínimo de páginas; ese número
depende de la máquina
 Ejemplo: IBM 370 – se pueden necesitar hasta 6 páginas para una
instrucción SS MOVE:

La instrucción ocupa 6 bytes, podría requerir 2 páginas

2 páginas para la cadena origen

2 páginas para el destino
 Esquemas principales de asignación

Asignación fija

Asignación por prioridad
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 31
Silberschatz, Galvin and Gagne ©2005
Asignación Fija
 Asignación equitativa – Por ejemplo, si hay 100 marcos y 5
procesos, se le da a cada proceso 20 marcos
 Asignación proporcional – Asigna marcos de acuerdo al tamaño
del proceso
s i  tamaño
S 
s
del proceso
pi
i
m  número
total de marcos
a i  asignación
para p i 
si
m  64
m
S
s1  10
s 2  127
a1 
a2 
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 32
10
 64  5
137
127
 64  59
137
Silberschatz, Galvin and Gagne ©2005
Asignación por Prioridad
 Usa un esquema de asignación proporcional basado en
las prioridades en lugar del tamaño
 Si el proceso Pi produce un fallo de páginas,

Escoge para reemplazar uno de sus marcos

Escoge para reemplazar un marco de un proceso con
menor prioridad
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 33
Silberschatz, Galvin and Gagne ©2005
Asignación Local y Global
 Reemplazo global – se escoge para reemplazar un marco
de cualquier proceso; un proceso puede tomar un marco
de otro
 Reemplazo local – se escoge para reemplazar un marco
del proceso que necesita la página
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 34
Silberschatz, Galvin and Gagne ©2005
Hiperpaginación
 Si un proceso no tiene suficientes páginas, la tasa de fallos de
página es muy alta. Esto lleva a:

Uso bajo de CPU

El SO piensa que necesita aumentar el grado de
multiprogramación

Otro proceso se añade al sistema
 Hiperpaginación  un proceso está ocupado trayendo y retirando
páginas de memoria
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 35
Silberschatz, Galvin and Gagne ©2005
Hiperpaginación
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 36
Silberschatz, Galvin and Gagne ©2005
Paginación por Demanda e Hiperpaginación


Por qué funciona la paginación por demanda?
Modelo de localidad

Los procesos migran de una localidad a otra

Las localidades pueden solaparse
Por qué ocurre la hiperpaginación?
 tamaño de la localidad > tamaño de la memoria
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 37
Silberschatz, Galvin and Gagne ©2005
Patrón de Referencias a Memoria
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 38
Silberschatz, Galvin and Gagne ©2005
Modelo de Conjunto de Trabajo
   ventana del conjunto de trabajo  un número fijo de
referencias a páginas
Ejemplo: 10.000 instrucciones
 WSSi (conjunto de trabajo del proceso Pi) =
número total de páginas referenciadas en la ventana más
reciente  (cambia con el tiempo)

Si  es demasiado pequeño no abarcará toda la localidad

Si  es demasiado grande abarcará varias localidades

Si  =   abarcará el programa entero
 D =  WSSi  total de marcos requeridos
 Si D > m  Hiperpaginación
 Política si D > m, se suspende un proceso
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 39
Silberschatz, Galvin and Gagne ©2005
Modelo de Conjunto de Trabajo
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 40
Silberschatz, Galvin and Gagne ©2005
Siguiendo la Pista al Conjunto de Trabajo
 Se aproxima con un temporizador y un bit de referencia
 Ejemplo:  = 10.000

El temporizador interrumpe cada 5000 unidades de tiempo

Se mantienen en memoria 2 bits por página

Cuando el temporizador interrumpe copia el bit de referencia
y lo pone a 0

Si uno de los bits en memoria es 1  la página está en el
conjunto de trabajo
 Mejora: 10 bits e interrumpir cada 1000 unidades de tiempo
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 41
Silberschatz, Galvin and Gagne ©2005
Frecuencia de Fallos de Página
 Es otra forma de evitar la hiperpaginación
 Se busca conseguir una tasa de fallos de página aceptable

Si la tasa actual es demasiado baja, el proceso pierde un marco
 Si la tasa actual es demasiado alta, el proceso gana un marco
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 42
Silberschatz, Galvin and Gagne ©2005
Prepaginación
 Prepaginación

Se usa para reducir el gran número de fallos de página que
ocurre al comienzo de un proceso

Consiste en traer a memoria todas o algunas de las páginas que
necesitará un proceso antes de que las referencie

La páginas prepaginadas pueden no ser utilizadas, hay gasto de
memoria y E/S

Asumimos que s páginas son prepaginadas y una fracción α de
esas páginas son usadas


Es el coste de los s * α fallos de página ahorrados > o < que
el coste de prepaginar s * (1- α) páginas innecesarias?
Si α es cercano a cero  la prepaginación no interesa
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 43
Silberschatz, Galvin and Gagne ©2005
Tamaño de las Páginas
 Para la selección del tamaño de página hay que tener en
cuenta:

La fragmentación interna

El tamaño de la tabla de páginas

La sobrecarga de E/S

La localidad
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 44
Silberschatz, Galvin and Gagne ©2005
Estructura del Programa
 Estructura del Programa

int data[128][128];

Cada fila se almacena en una página
 Programa 1
for (j = 0; j <128; j++)
for (i = 0; i < 128; i++)
data[i][j] = 0;
128 x 128 = 16,384 fallos de página

Programa 2
for (i = 0; i < 128; i++)
for (j = 0; j < 128; j++)
data[i][j] = 0;
128 fallos de página
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 45
Silberschatz, Galvin and Gagne ©2005
Interbloqueo de E/S
 Interbloqueo de E/S – A veces las páginas deben
bloquearse en memoria
 Las páginas que se están usando para copiar un fichero
de un dispositivo deben bloquearse para que no sean
escogidas por un algoritmo de reemplazo de páginas
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 46
Silberschatz, Galvin and Gagne ©2005
Windows XP
 Usa paginación por demanda con agrupamiento (clustering). El
clustering trae a memoria páginas adyacentes a la página que falló
 A los procesos se les asigna un conjunto de trabajo mínimo y
máximo
 El conjunto de trabajo mínimo es el mínimo número de páginas del
proceso que van a estar con seguridad en memoria
 A un proceso se le pueden asignar páginas hasta que llegue a su
conjunto de trabajo máximo
 Cuando la cantidad de memoria libre en el sistema cae por debajo
de un umbral, se hace un recorte automático del conjunto de
trabajo para restaurar la cantidad de memoria libre
 El recorte del conjunto de trabajo retira páginas de los procesos
que tienen un número de páginas mayor que el mínimo
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 47
Silberschatz, Galvin and Gagne ©2005
Solaris
 Mantiene una lista de marcos libres para asignar a los procesos
que fallan
 Lotsfree – umbral (cantidad de memoria libre) para comenzar la
paginación
 Desfree – umbral para incrementar la paginación
 Minfree – umbral para comenzar el intercambio
 La paginación la realiza el proceso pageout
 Pageout escanea las páginas usando una variante del algoritmo de
reloj (algoritmo de reloj modificado)
 Scanrate es la tasa a la que las páginas son escaneadas. Este
valor va entre slowscan y fastscan
 Pageout se llama más frecuentemente dependiendo de la cantidad
de memoria libre
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 48
Silberschatz, Galvin and Gagne ©2005
Escaneador de Páginas de Solaris 2
Fundamentos de los Computadores (ITT, Sist. Electr.), 2005-2006
Tema 10.4: 49
Silberschatz, Galvin and Gagne ©2005
Fin del Tema 10
Descargar

Transparencias(apartado 4)