Sistemas Operativos

Memoria Virtual
 Memoria Virtual
1. Aspectos Generales
2. Paginación por demanda
3. Algoritmos de reemplazo de páginas
4. Modelo del conjunto activo
 1. Aspectos Generales
• Todos los esquemas vistos hasta ahora exigen
que el programa esté entero en memoria
• El principio de cercanía indica que
probablemente cuando se ejecute un programa
nunca se va a ejecutar todo su código
• Si tenemos esquemas con:
– Reubicación dinámica
– División del espacio lógico del proceso
• No es necesario tener todos los fragmentos del
programa en memoria principal para ejecutarse
 1. Aspectos Generales
• A la parte del programa residente en memoria
principal se llama conjunto residente
• Cuando el proceso encuentra una dirección
lógica que no está en la MP, se genera una
excepción que provoca la carga del fragmento
deseado
• Ventajas
– El espacio lógico del programa puede ser
mayor que la memoria física disponible
– Aumenta el grado de multiprogramación
– Aumentará la velocidad de ejecución
 1. Aspectos Generales
• Inconvenientes
– La máxima velocidad de ejecución de un
programa en un sistema con memoria virtual
no puede ser mayor a la obtenida en un
sistema sin memoria virtual
– Requiere de hw y sw especial
• El SO se encargará de: la politica de lectura, de
ubicación, de reemplazo, gestión del conjunto
residente, política de vaciado y control de carga
 2. Paginación por demanda
• Características
• Fallo de Páginas
• Hardware necesario
• reemplazo de páginas
• Rendimiento
 2. Paginación por demanda
Características
 Sólo traeremos una página a memoria cuando se
necesite. Las ventajas son:
– Menos E/S
– Menos Memoria
– Respuesta más rápida
 Problema: el rendimiento
 ¿Cuándo se necesita? Cuando se referencia
– Referencia es inválida se aborta
– Si es válida se trae página a memoria
2. Paginación por demanda
Ejemplo:
 2. Paginación por demanda
Características
• Sobrecargamos la semántica del bit del validez o
presencia de cada PTE para implementar la
paginación por demanda. Si el bit vale:
– 1 entonces la página está en memoria
– 0 entonces no esta en memoria principal pero
sabemos si la página es válida. En el PCB del
proceso se guardará la información sobre las páginas
que son válidas para el proceso
 2. Paginación por demanda
Características
• Al inicio, el bit está a cero en todas las PTE.
Durante la traducción de direcciones, si se
referencia una página con el bit de validez a cero se
produce un fallo de página
• Qué pasos se realizan ante un fallo de página?
2. Paginación por demanda
 2. Paginación por demanda
Fallo de Página
1. Se detecta si el error es realmente un fallo de
página o una dirección inválida
2. Si es una dirección inválida finalizo
3. Si es por fallo de página, la buscamos en MP
4. Le asignamos un marco
5. Cargamos el contenido de la página en el marco
6. Ponemos el bit de presencia de la tabla a 1 para
indicar que la página está en memoria
7. Reiniciamos la ejecución de la instrucción
 2. Paginación por demanda
Hardware necesario
 Para la traducción necesitamos añadir a la TP un bit
de presencia BP para detectar las páginas cargadas
en memoria
 2. Paginación por demanda
Hardware necesario
 Un dispositivo auxiliar de alta velocidad. Además las
operaciones de E/S se hacen mediante
controladores DMA
 Hw para distinguir entre fallo de página y la
interrupción por direccionamiento incorrecto
 Hw para poder reinicializar la instrucción
interrumpida
 2. Paginación por demanda
Reemplazo de páginas
• ¿Qué pasa cuando se da un fallo de página y no
hay espacio suficiente en memoria para cargar la
memoria?
• La solución la encontramos en el reemplazo de
páginas:
– Encontramos un marco que no se esté usando en
ese momento y se libera
– Al liberarla copiamos su contenido en memoria
secundaria
 2. Paginación por demanda
Reemplazo de páginas
 2. Paginación por demanda
Rendimiento
• La probabilidad de fallo de página 0<=p<=1.
– Si p=0, no hay fallos de página
– Si p=1, cada referencia es un fallo

• TEA = (1-p)*acceso a memoria + p*(tiempo de

fallo de página).
• Tfp = sobrecarga fallo pagina + [swap out] +
[swap in] +sobrecarga de restauración
 2. Paginación por demanda
Rendimiento – Ejemplo
• Tiempo de acceso a memoria = 100 nanosegs
• Tiempo de fallo de página = 15 mseg =
15.000.000 nanosegs.

TAE= (1-p)* 100 + p(15.000.000)‫‏‬

TAE= 100 + 14.999.900*p‫‏‬
 2. Paginación por demanda
Bit de modificación
• El uso de un bit adicional en las PTE, el bit de
modificación reduce la sobrecarga de transferencia
de algunas páginas
• Sólo se escriben al disco las páginas que han sido
modificadas; las no modificadas pueden descartarse
ya que tenemos una copia de ellas en el archivo
ejecutable en disco
 2. Paginación por demanda
Reemplazo de páginas
 El concepto de reemplazo de página está
relacionado con:
 El número de marcos de página a asignar a un
proceso
 Si el conjunto de páginas a considerar para el
reemplazo debe limitarse a las del proceso que
provocó el fallo de página o a todos los
procesos
 Del conjunto de páginas seleccionadas ¿cuál
se elige para reemplazarla?
 3. Algoritmos de reemplazo de
páginas
• Algoritmo FIFO
– Anomalía de Belady
• Algoritmo óptimo
• Algoritmo LRU (menos recientemente usado)‫‏‬
• Algoritmo del reloj
• Política de asignación de marcos
 3. Algoritmos de reemplazo de
páginas
• Se desea el menor número de fallos de página
• Se evalúa el algoritmo mediante un string particular de
referencias a memoria (string de referencias) y se
calcula el número de fallos de página.
• Algoritmos aplicables a políticas de reemplazo locales y
globales
• En todos los ej: siguientes, el string de referencia será:
0,1,2,3, 0,1,4,0,1,2,3,4
• 3 marcos (3 págs pueden estar en memoria al mismo
tiempo.
 3. Algoritmos de reemplazo de
páginas
Algoritmo FIFO

0 1 2 3 0 1 4 0 1 2 3 4

F
 3. Algoritmos de reemplazo de
páginas
Algoritmo FIFO

0 1 2 3 0 1 4 0 1 2 3 4

0 0
1

F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo FIFO

0 1 2 3 0 1 4 0 1 2 3 4

0 0 0
1 1
2

F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo FIFO

0 1 2 3 0 1 4 0 1 2 3 4

0 0 0 3
1 1 1
2 2

F F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo FIFO

0 1 2 3 0 1 4 0 1 2 3 4

0 0 0 3 3
1 1 1 0
2 2 2

F F F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo FIFO

0 1 2 3 0 1 4 0 1 2 3 4

0 0 0 3 3 3
1 1 1 0 0
2 2 2 1

F F F F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo FIFO
– 10 Fallos

0 1 2 3 0 1 4 0 1 2 3 4

0 0 0 3 3 3 4 4 4 4 4 4
1 1 1 0 0 0 0 0 2 2 2
2 2 2 1 1 1 1 1 3 3

F F F F F F F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo FIFO
– La tendencia es entre más marcos
menos fallo de página. Pero,
– La anomalía de Belady no cumple con
esta tendencia, es decir más marcos
entonces más fallos de página.
– Ejm: 4 marcos
 3. Algoritmos de reemplazo de
páginas
Algoritmo FIFO
– 10 fallos
0 1 2 3 0 1 4 0 1 2 3 4

0 0 0 0 0 0 4 4 4 4 3 3
1 1 1 1 1 1 0 0 0 0 4
2 2 2 2 2 2 1 1 1 1
3 3 3 3 3 3 2 2 2

F F F F F F F F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo Óptimo

0 1 2 3 0 1 4 0 1 2 3 4

F
 3. Algoritmos de reemplazo de
páginas
Algoritmo Óptimo

0 1 2 3 0 1 4 0 1 2 3 4

0 0
1

F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo Óptimo

0 1 2 3 0 1 4 0 1 2 3 4

0 0 0
1 1
2

F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo Óptimo

0 1 2 3 0 1 4 0 1 2 3 4

0 0 0 0
1 1 1
2 3

F F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo Óptimo

0 1 2 3 0 1 4 0 1 2 3 4

0 0 0 0 0
1 1 1 1
2 3 3

F F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo Óptimo

0 1 2 3 0 1 4 0 1 2 3 4

0 0 0 0 0 0
1 1 1 1 1
2 3 3 3

F F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo Óptimo
– 7 fallos

0 1 2 3 0 1 4 0 1 2 3 4

0 0 0 0 0 0 0 0 0 2 2 2
1 1 1 1 1 1 1 1 1 3 3
2 3 3 3 4 4 4 4 4 4

F F F F F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo LRU

0 1 2 3 0 1 4 0 1 2 3 4

F
 3. Algoritmos de reemplazo de
páginas
Algoritmo LRU

0 1 2 3 0 1 4 0 1 2 3 4

0 0
1

F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo LRU

0 1 2 3 0 1 4 0 1 2 3 4

0 0 0
1 1
2

F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo LRU

0 1 2 3 0 1 4 0 1 2 3 4

0 0 0 3
1 1 1
2 2

F F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo LRU

0 1 2 3 0 1 4 0 1 2 3 4

0 0 0 3 3
1 1 1 0
2 2 2

F F F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo LRU

0 1 2 3 0 1 4 0 1 2 3 4

0 0 0 3 3 3
1 1 1 0 0
2 2 2 1

F F F F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo LRU
– 10 fallos

0 1 2 3 0 1 4 0 1 2 3 4

0 0 0 3 3 3 4 4 4 2 2 2
1 1 1 0 0 0 0 0 0 3 3
2 2 2 1 1 1 1 1 1 4

F F F F F F F F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo del Reloj

0 1 2 3 0 1 4 0 1 2 3 4

→ 0

F
 3. Algoritmos de reemplazo de
páginas
Algoritmo del Reloj

0 1 2 3 0 1 4 0 1 2 3 4

→ 0 0

→ 1

F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo del Reloj

0 1 2 3 0 1 4 0 1 2 3 4

→ 0 0 0 → →

→ 1 1

→ 2

F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo del Reloj

0 1 2 3 0 1 4 0 1 2 3 4

→ 0 0 0 → 3 →

→ 1 1 1 →

→ 2 2

F F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo del Reloj

0 1 2 3 0 1 4 0 1 2 3 4

→ 0 0 0 → 3 3

→ 1 1 1 → 0

→ 2 2 2 →

F F F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo del Reloj

0 1 2 3 0 1 4 0 1 2 3 4

→ 0 0 0 → 3 3 3 →

→ 1 1 1 → 0 0

→ 2 2 2 → 1

F F F F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo del Reloj

0 1 2 3 0 1 4 0 1 2 3 4

→ 0 0 0 → 3 3 3 → 4 →

→ 1 1 1 → 0 0 0 →

→ 2 2 2 → 1 1

F F F F F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo del Reloj

0 1 2 3 0 1 4 0 1 2 3 4

→ 0 0 0 → 3 3 3 → 4 4

→ 1 1 1 → 0 0 0 → 0* →

→ 2 2 2 → 1 1 1

F F F F F F F
 3. Algoritmos de reemplazo de
páginas
Algoritmo del Reloj
– 10 fallos

0 1 2 3 0 1 4 0 1 2 3 4

→ 0 0 0 → 3 3 3 → 4 4 4 2 2 2 →

→ 1 1 1 → 0 0 0 → 0* → 0* → 0 → 3 3

→ 2 2 2 → 1 1 1 1* 1 1 → 4

F F F F F F F F F F
 3. Algoritmos de reemplazo de
páginas
Política de reemplazo de páginas
• Local
– Cuando se da un fallo de página de un proceso
sólo pueden usarse marcos asociados al proceso
para su reemplazo
• Global
– Cuando se da un fallo de página de un proceso
se puede seleccionar un marco asociado a otro
proceso para su reemplazo
 3. Algoritmos de reemplazo de
páginas
Política de asignación de marcos
• Multiprogramación
• Es necesario, determinar cuántos marcos de
página se asignan a cada proceso.
• Cada proceso necesita un número mínimo de
páginas
• Existen dos tipos de estrategias
 3. Algoritmos de reemplazo de
páginas
Política de asignación de marcos
• Asignación fija
– Asignación proporcional
• Según la dimensión del proceso
• si= tamaño del proceso pi
• S = ∑ si
• ai= asignación para pi= si / S * m
– Ejemplo: Marcos = 62, dos procesos, uno 10
páginas y otro de 127 páginas.
 3. Algoritmos de reemplazo de
páginas
Política de asignación de marcos
• Asignación fija
– Asignación por prioridad
• Se asignan marcos dependiendo de la prioridad y
no del tamaño del proceso.
• Si el proceso genera un fallo de página
– Selecciona un marco de un proceso con menor prioridad
– Lleva asociada una estrategia de reemplazo
local.
 3. Algoritmos de reemplazo de
páginas
Política de asignación de marcos
• Asignación variable
– Varia según las necesidades que tenga el
proceso en diferentes instantes de tiempo
– Puede usar tanto estrategias de reemplazo
locales o globales.
 4. Modelo del Conjunto Activo
• Hiperpaginación
• Modelo del conjunto activo
 4. Modelo del Conjunto Activo
Hiperpaginación
• Si un proceso no tiene “suficientes” páginas, el
% de fallos de página puede ser muy alta. Esto
conduce a.
– Baja utilización de la CPU
– El sistema operativo cree que necesita aumentar el
grado de multiprogramación
– Se añade otro proceso al sistemas
• Hiperpaginación = un proceso esta ocupado
intercambiando páginas
 4. Modelo del Conjunto Activo
Hiperpaginación
• Porqué funciona la
paginación?
– El proceso emigra de una
“localidad” a otra
– Las localidades pueden
solaparse
• Por que ocurre la
hiperpaginación?
∑ tamaño de la localidad >
tamaño total de memoria
 4. Modelo del Conjunto Activo
• El conjunto activo (Working Set)‫‏‬
• Se basa en la suposición de localidad
• Δ ≡ ventana del conjunto de trabajo ≡ un número
fijo de referencias a página
• WSSi (Conjunto de trabajo del proceso Pi) =
número total de páginas referenciadas en el
más reciente intervalo Δ (varia en el tiempo)
– Si Δ es demasiado pequeño no abarca la localidad completa.
– Si Δ es demasiado grande abarcará varias localidades.
– Si Δ = infinito entonces abarcará el programa entero.
 4. Modelo del Conjunto Activo
• D = ∑ WSSi ≡ Total marcos demandados
• If D > m => Hiperpaginación
• La política adecuada, si D > m suspender un
proceso.
• (m = número de marcos disponibles)
• Dinámicamente ajusta los marcos asignados
 4. Modelo del Conjunto Activo
• Ejemplos:
• Sea la cadena de referencias

W
…1 2 3 4 5 6 6 6 5 2 4 4 7 7 5 ..
=
t t
Δ 1 Δ 2
 4. Modelo del Conjunto Activo
• Si el tamaño de la ventana Δ = 3:
– En t1, WS (t1, 3) = {4,5,6}
– En t2, WS (t2,3) = {4,7}
• Si Δ = 5, los conjuntos activos serían:
– En t1, WS (t1, 5) = {2,3,4,5,6}
– En t2, WS (t2, 5) = {2,4,7}
 4. Modelo del Conjunto Activo
• La importancia del modelo del conjunto activo se
debe a que liga la gestión de memoria y la
planificación través del Principio del Conjunto
Activo:

“Un proceso sólo puede ejecutarse si su conjunto

activo está en memoria principal. Una página no
puede retirarse de memoria principal si está
dentro del conjunto activo del proceso en
ejecución”.
 Ejercicios en clase
1.Considerar la siguiente serie de referencias a páginas:
2, 1, 2, 1, 2, 3, 4, 2, 3, 6, 2, 1, 1, 5, 6

Halle el número de fallos de página utilizando los

algoritmos RELOJ y OPTIMO si:
a) Dispone de 3 páginas en memoria
b) Dispone de 4 páginas en memoria.
 Ejercicios en clase
1.Dadas las particiones variables de memoria (10K, 4K,
20K, 18K, 7K, 9K, 12K y 15K) en ese orden y los procesos
de 10K, 12K, 9K, 13K ( en ese orden).

a)Cómo podría cada uno de los algoritmos Mejor, Peor y

Primer Ajuste colocar los procesos en memoria?
b)Cuál algoritmo aprovecha mejor la memoria?
c)Se podría aplicar compactación en algunos de los casos,
explique su respuesta.