Memoria Virtual
Msc. Rina Arauz
Gestión de memoria 2
Introducción Problema: ejecutar programas de tamaño mayor que la
memoria disponible. Soluciones
Memoria virtual: Control realizado por el S.O.
La memoria virtual es una técnica de gestión de la memoria que permite que el sistema operativo disponga de mayor cantidad de memoria de la que existe físicamente.
La memoria virtual (MV) se basa en el principio de localidad de las referencias.
Memoria Virtual
Consiste en utilizar el disco duro como memoria principal y almacenar en RAM solamente las instrucciones y los datos que están siendo utilizados por el procesador, la idea es mantener en memoria principal sólo la información que se necesite en cada momento, el espacio en el disco duro (HDD) se usa como si fuera RAM.
Gestión de memoria 3
En windows se puede encontrar la memoria virtual en forma de un archivo llamado pagefile.sys en el disco primario (“C:” ) (propiedades de Mi PC, Opciones avanzadas). El limite máximo del archivo paginado (o Memoria Virtual) es de 4096Mb por unidad o partición.
Otros SO como Linux dejan una partición del disco dedicada exclusivamente para la memoria virtual, generalmente llamado swap.
El valor recomendado de Memoria Virtual, se obtiene multiplicando la memoria RAM por 2 (máximo 2,5).
Gestión de memoria 4
Gestión de memoria 5
Ventajas
Permite aumentar el tamaño de los programas permitiendo que sean mayores que la memoria física.
Permite aumentar el grado de multiprogramación, ya que permite ubicar más procesos en memoria.
Gestión de memoria 6
Implementación
La memoria virtual puede basarse tanto en mecanismos de paginación como de segmentación.
Lo habitual es que se base en un esquema paginado por las siguientes razones: Al trabajar con bloques de tamaño fijo, las
transferencias desde y hacia el disco son más simples
Las políticas de ubicación son más simples: todos los bloques son iguales
Gestión de memoria 7
Soporte hardware (Memoria virtual basada en paginación)
Requerimientos hardware: Tabla de páginas Bits en los descriptores de página:
Bit de validez
Bit de referencia
Bit de modificación
Interruptibilidad de las instrucciones Dispositivo de almacenamiento secundario
Tabla de Páginas
Cada proceso tiene su tabla de páginas. (TdP) Cada entrada en la tabla contiene el número de marco en memoria principal
donde dicha página fue cargada, bit de validez, de referencia y modificación.
Bit de validez o de Presencia: indica si la página está cargada en la memoria principal. “1” si la página está almacenada en memoria principal, “0” si la pagina NO está en Memoria principal (fallo de pág). Cuando se intenta acceder a una página que no se encuentra cargada en memoria se produce un fallo de página.
Bit de referencia: Se activa cuando una página se accesa es decir cuando se accede a una dirección lógica que pertenece a esa página.
Bit de Modificación: Se activa cuando hay inconsistencia entre memoria principal y el disco duro. Cuando se ha escrito en una dirección lógica que pertenece a esa página.
Gestión de memoria 8
Gestión de memoria 9
BV BR BM Pág. Marco
1 0 0 A M25
1 1 0 B M85
0 0 0 C -
1 1 1 D M02
0 0 0 E -
Tabla de Páginas
Gestión de memoria 10
Memoria virtual basada en paginación
OUTININ
OUTOUTIN
zx
y
(P0)(P4)
(P3) (P0)(P1)
(P2)
(P5)(P4)(P3)
Tabla del mapa de páginas Tabla del mapa
de archivos
Memoriaprincipal
Memoriasecundaria
Gestión de memoria 11
Carga dinámica
Programa
S. O.
Memoria principal
Marco libre
0
Tabla de páginas
2Excepción
3La página estáen memoria auxiliar
4 Cargar lapágina quefalla
Memoria secundaria
LOAD M6
1Referencia
Reiniciar la instr.
5Actualizar latabla de páginas
Gestión de memoria 12
Paginadores
Son la parte del SO responsable de mover páginas entre la MP y el disco y viceversa.
Pueden ser de tres tipos: De archivos (mmap, exec) De objetos anónimos (swap) De dispositivos (frame buffer)
Gestión de memoria 13
Tasa de fallos de página
Es la probabilidad de que se produzca un fallo de página p = número de fallos / número total de
referencias: 0 p 1
Número de marcos
Tasa de fallos de páginaLa tasa de fallos depágina disminuye cuando aumenta el número de marcos
Gestión de memoria 14
Tiempo de servicio del fallo de página
Los tiempos que más afectan son: Los cambios de contexto Salvar una página modificada a disco (page out) Cargar la página referencia de disco a memoria
(page in) El planificador asigna la CPU a otros procesos
mientras se realizan las lecturas (page in) y escrituras asociadas al fallo de página
Gestión de memoria 15
Rendimiento de la paginación
Tiempo de acceso efectivo (TAE): TAE = (1 - p) * TAM + p * (1 + pm) * TTP
donde:
TAM: tiempo de acceso a memoria
TTP: tiempo de transferencia página/disco
p: tasa de fallos de página
pm: probabilidad de que la página a reemplazar haya sido modificada
Gestión de memoria 16
Hiperpaginación (Thrashing)
Hiperpaginación: Un proceso genera fallos de página frecuentemente y el sistema pasa la mayor parte del tiempo paginando
Grado de multiprogramación
Thrashing
Utilización de la CPU
Gestión de memoria 17
Hiperpaginación (Thrashing)
Posible causa de la hiperpaginación: Un proceso necesita más marcos, su tasa de fallos de página aumenta y se produce la siguiente reacción en cadena: Disminuye el uso de la CPU El S.O. decide aumentar el grado de
multiprogramación La tasa de fallos de página se incrementa más
Soluciones: Reducir la multiprogramación o emplear un
algoritmo de reemplazo local o por prioridades Prevenir la hiperpaginación
Tamaño de Página (Consideraciones)
Página pequeña se requieren más páginas por proceso tablas más grandes menor fragmentación interna.
Páginas grandes se requieren menos páginas por proceso tablas pequeñas mayor fragmentación interna.
Memoria secundaria está diseñada para transferir eficientemente grandes bloques de datos, luego por todo lo anterior podríamos concluir que es mejor tener páginas más grandes.
Gestión de memoria 18
Gestión de memoria 19
Algoritmos
Política de asignación: ¿Qué cantidad de memoria real se asigna a un proceso activo?
Política de ubicación: ¿Dónde puede ubicarse un bloque en memoria principal?
Política de búsqueda: ¿Cuándo y qué bloques traer del almacenamiento secundario a MP? Paginación anticipada Paginación por demanda
Política de reemplazo: ¿Qué bloque debería sustituirse al traer a memoria principal un nuevo bloque si no hay memoria libre?
Gestión de memoria 20
Políticas de asignación
El mínimo número de marcos que debe asignarse a un proceso está definido por la arquitectura.
Tipos de algoritmos de asignación: Asignación equitativa Asignación proporcional Asignación prioritaria
Gestión de memoria 21
Políticas de ubicación
Políticas de ubicación: En paginación: “Indiferente”
En segmentación
First fit: el primero que sirva
Next fit: el siguiente que sirva
Best fit: el que mejor se adapte
Worst fit: el que peor se adapte
Sistema Buddy
Gestión de memoria 22
P2
P1
P1
Sistema Buddy
256
1024 Kb
256
128
P1
128
128
128 64
P2
64
P2
P2
64
64
P4
P4
P3
P3
P3
P3
P3
128
128
128
128
128
512
512
512
512
512
512
512
1024 Kb
256
Inicial
P1 pide 70
P2 pide 35
P3 pide 80
Devuelve P1
P4 pide 60
Devuelve P2
Devuelve P4
Devuelve P3
1
3
3
3
4
3
4
3
1
Bloques libres
Gestión de memoria 23
Paginación por demanda
El camino que toma un programa cuando se está ejecutando no es predecible Se cargan las páginas a medida que se
necesitan Ventajas:
Las páginas traídas son las que realmente se necesitan
La sobrecarga que implica la decisión de qué páginas traer al almacenamiento principal es mínima
Gestión de memoria 24
Paginación anticipada (prepaginación)
Trata de evitar los retardos por fallos de página Se cargan un cierto número de páginas en base
a una predicción Ventajas:
Si la predicción es buena, el tiempo de ejecución de los procesos se reduce considerablemente
Con la reducción de costes del hardware, las consecuencias de una mala predicción son menos graves
Gestión de memoria 25
Reemplazo de páginas
Es necesario cuando se produce un fallo de página y está toda la memoria llena
Tasa de fallos uno por cada 106 – 2 x 107 accesos Si hay un fallo de página (miss) hay que:
Encontrar la página demandada en memoria auxiliar
Encontrar un marco libre o liberarlo usando un algoritmo de reemplazo de páginas
Cargar la página en memoria principal (page in) Transferir el control al proceso de usuario
Gestión de memoria 26
Algoritmos de reemplazo de páginas
Se pretende utilizar el algoritmo que seleccione páginas que causen la frecuencia de fallos más baja
Criterios para valorar la calidad de los algoritmos de sustitución: Baja sobrecarga Sin ajustes (“No tuning”) Aproximación al LRU (menos usada
recientemente)
Gestión de memoria 27
Cadenas de referencia
Para evaluar la calidad de los algoritmos de sustitución se consideran: Cadenas de referencia: listas de referencias a
páginas Número de marcos de página de que se dispone
Obtención de las cadenas de referencia: Artificialmente, de forma pseudoaleatoria Grabando una traza de ejecución
Gestión de memoria 28
Cadenas de referencia
Ejemplo: 0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103, 0104 0101, 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105 Con páginas de 100h palabras Cadena de referencias:
sólo nos interesa el número de página si se referencia una página p, las referencias inmediatamente
sucesivas a esa página nunca causarán fallo de página
1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1 Con tres marcos habrá 3 fallos y con 1 marco 11
fallos si el número de marcos aumenta, en general, el
número de fallos de página disminuye
Gestión de memoria 29
Algoritmos de reemplazo de páginas
Existen diferentes algoritmos, entre ellos: Algoritmo óptimo Algoritmo FIFO Algoritmo LRU Algoritmos de aproximación al LRU
Gestión de memoria 30
Algoritmo óptimo
Se reemplaza la página que va a tardar más tiempo en ser usada
La tasa de fallos es la más baja posible Algoritmo imposible de realizar
Criterio comparativo
Gestión de memoria 31
Algoritmo óptimo
Ejemplo: Cadena de referencia
Marcos de páginaMarcos de página
330011
11
77
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0
00
77
11
00
77
77
11
00
7722
00
22
1133 33
00
22
00
22
33
0044
22
33
44
22
33
44
22
44
33 33
00
22
33
00
22
3311
00
22
11
00
22
11
00
22
8 fallos de página
4400
22
Gestión de memoria 32
Algoritmo FIFO
Sustituye la página que lleva más tiempo en memoria
Ejemplo: Cadena de referencia
Marcos de páginaMarcos de página
222200
11
77
00
77
11
00
77
77
11
00
7722
00
22
11
00
00
33
22
44
33 33
22
00
33
22
00
33
22
22
11
00
33
22
11
44
33
00
00
0033
22
44
11
00
33
3322
11
00
22
4400
3322
44
1100
33
22
12 fallos de página
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0
Gestión de memoria 33
Algoritmo FIFO
Algoritmo sencillo de entender e implementar Inconvenientes:
Rendimiento del algoritmo pobre. Páginas frecuentemente usadas pueden ser sustituidas
Se puede producir la Anomalía de Belady: aumento del número de fallos de página al aumentar el número de marcos
Gestión de memoria 34
Anomalía de Belady
Ejemplo: Con 3 y 4 marcos de página
1 2 3 4 1 2 5 1 2 3 4 5 1 2 3 4 1 2 5 1 2 3 4 5
Con 3 marcos, 9 fallos de página
5511 4422 33 11
1111 4422 33 22
11112211
332211
332211
2233 22
1122 22
551155
2211
2233
44
44
331144
221144
1155 55
443355
3355
33
112211
332211
11
33221144
33 221155
22
22 443355
22
44
44
22
11
2211
44
22
33221144
1144
221155
1155
3355
3355
Con 3 marcos, 9 fallos de págnaCon 3 marcos, 9 fallos de págnaCon 4 marcos, 10 fallos de página
331111
2211
332211
44332211
44332211
44332211
44332255
22
44331155
3344221155
4433221155
33
55
221144
33225544
1 2 3 4 1 2 5 1 2 3 4 5
Gestión de memoria 35
Algoritmo LRU (Least Recently Used)
Algoritmo de aproximación al reemplazo óptimo Basado en utilizar el pasado reciente como una
predicción del futuro más próximo Sustituye la página menos usada en el pasado
inmediato Carece de la anomalía de Belady La implementación requiere de hardware adicional:
Campo en las entradas de la tabla de páginas Pila de las páginas en memoria
Gestión de memoria 36
Algoritmo LRU (Least Recently Used)
¿Podría comportarse erróneamente el algoritmo con un bucle que ocupa varias páginas?
Ejemplo:
Cadena de referencia
Marcos de páginaMarcos de página
002211
11
770077
110077
77
11007722
0022
11 33 330022
44
22 223300
223300
2233
11 fallos de página
330022 44
33
3322
00
2200 33
4400 00
223311
0022
0044
3344 11
33
22330011
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0
Gestión de memoria 37
Algoritmos de aproximación al LRU
Existen diferentes algoritmos, entre ellos: Algoritmo del reloj global Algoritmo FIFO con segunda oportunidad Algoritmo NFU