Sistemas

Sistemas Operativos
Operativos
Memoria
Memoria Virtual
Virtual

Profesores
Mag. Ing. Liliana CUENCA PLETSCH
Dr. Ing. Sergio GRAMAJO
Auxiliares
Ing. Jorge ROA Recopilación Bibliográfica y
elaboración del presente material de
Ing. Rodrigo VIGIL
estudio a cargo de Liliana CUENCA
PLETSCH y Alberto RISTOFF
 Bibliografía
Bibliografía consultada
consultada

•SILBERSCHATZ A. y. otros: “Sistemas Operativos –

Conceptos Fundamentales”. Séptima Edición, España,
Reverté S.A.

•STALLINGS William : “Sistemas Operativos”. Quinta

Edición, España, Pearson Prentice Hall. 2005
 Objetivos
Objetivos específicos
específicos

• Comprender las ventajas de un sistema de

memoria virtual

• Analizar la implementación de la memoria

virtual
 Memoria Virtual
Permite
Permite ejecutar
ejecutar procesos
procesos que
que no
no están
están cargados
cargados
completamente
completamente en
en MP
MP
¿Cómo?

El SO mantiene en MP las partes del proceso que se

requieren en un momento dado y en memoria secundaria el
resto

Implica

Profundizar la separación entre memoria lógica o virtual y

memoria física
 Memoria Virtual - Antecedente
Overlays
Overlays oo Solapamiento
Solapamiento
Memoria
Secundaria
Función
main() SO
(100
(100 Kb)
Kb)
(100 kb) invoca a A()

Función A
o invoca a B() invocaaa
invoca
(40 Kb) Main()
Main() B()
A()

156 Kb
Función B
(50 kb)
56B()
Kb
A()
Proceso

Memoria
principal
Paginación bajo demanda
Pág.0
Pág 0
Pág.1
Pág 1

PágPág.2
2

Presente

.
.
.

Ausente

MMU

Memoria Memoria
Pág. v Física Secundaria
Memoria
Virtual
 Implementación
Hay marcos libres?
No
Pág. 0
Marco v/i p/a
A Lóg
0
1
B
0 4 v p Swap Out
1 2
1 v a
2 C 3
2 6 v p
3 D 4 A
3 v a Fallo de
página 5
4 E 4 v a
6 C
5 F 5 9 v p
7
6 v a
6 G 8
7 v a Swap
7 H 9 F In
8 i a
Memoria 10
9 i a
Virtual 11 Sí
. . . .
12
Proceso j . . . .
13
. . . .
14 Memoria
v i a Secundaria
15

Memoria Física
Tabla de Páginas Proc.j
 Servicio de fallo de página – Sin bit M
v/i Sí Sí Generar dirección
p/a
= Física
=
v
p

Interrupciónrsfp
No
No

Marco No
Algoritmo Reemplazo de
Error: libre? página
Direccionamiento
ilegal
Sí Swap out página víctima

Swap in página requerida

Actualiza TP

Reiniciar instrucción
interrumpida
 Servicio de fallo de página – con bit M
Interrupción
v/i Sí rsfp p/a Sí Generar dirección
= = Física
v p

No
No Algoritmo Reemplazo de
página
Marco No
Error: libre?
Direccionamiento
ilegal Bit M
Sí
Sí =
0
Swap in página requerida
No

Actualiza TP Swap out página víctima

Reiniciar instrucción
interrumpida
 Rendimiento de la paginación bajo
demanda
• Tasa de fallos de página 0  p  1.0
– si p = 0 no hay fallos de página
– si p = 1, todas las referencias conducen a un fallo

• Tiempo efectivo de acceso a memoria (TEAM)

TEAM = (1 – p) x ma + p x tsfp

ma = tiempo de acceso a memoria cuando no se produce fallo de página

tsfp = tiempo de acceso a memoria cuando se produce fallo de página
 Rendimiento de la paginación bajo
demanda
• ma = 200 ns tsfp = 8.000.000 ns
p = 2%
• TEAM = (1 – p) x 200 ns + p x 8.000.000 ns=
= 0.98 x 200 + 0.02 x 8,000,000
= 196 + 160.000 = 160.196 ns
p = 4%
• TEAM = (1 – p) x 200 ns + p x 8.000.000 ns=
= 0.96 x 200 + 0.04 x 8,000,000
= 192 + 320.000 = 320.192 ns

Aspecto crítico: algoritmos de reemplazo de páginas

 Rendimiento de la paginación bajo
demanda
• Si se trabaja con registros asociativos, hay que pensar en los
siguiente:
– el % de veces que se encuentra, el tiempo es TAMA+TAM
– El % de veces que no se encuentra:
• Cuando el bit p/a está en presente el tiempo es TAMA +
2TAM
• Cuando el bit p/a está en ausente el tiempo es TSFP
– si no hay bit M, siempre implica swap out y swap in
– Si hay bit M, un% de veces respecto de p habrá solo swap
in y otro porcentaje de veces respecto de p habrá swap
out y swap in
 Rendimiento de la paginación bajo
demanda
Registros Compromiso con la
velocidad de acceso a
Caché instrucciones y datos de
Compromiso con
los procesos.
la capacidad. MP
Mejorar rendimiento
Mejorar nivel de
Discos
multiprogramación
CD-ROM
CD-RW
DVD-RW

Cinta
magnética

Jerarquías
Jerarquías de
de memoria
memoria
 EJERCITACIÓN
Se tiene un esquema de memoria virtual que trabaja con
paginación bajo demanda. Según las siguientes mediciones se
sabe que: El tiempo de acceso a memoria es de 1 ms. Dicho
sistema trabaja con un conjunto de 10 registros asociativos cuyo
tiempo de acceso es de 10 nanosegundos; el porcentaje de
aciertos cuando se busca una página en ellos, es de 90%, del
resto, el 10 % causa fallo de pagina, en cuyo caso el tiempo de
servicio de fallo de pagina es de 20 ms.

a)Calcular el tiempo efectivo de acceso a memoria

b) ¿Cuál será el tiempo de acceso efectivo si el porcentaje de

aciertos es del 60%, manteniéndose igual el resto de los
valores?
 EJERCITACIÓN

c) ¿Cuál será el tiempo de acceso efectivo si el porcentaje de

aciertos es del 60%, y el 40% de los que no se encuentran
en registros asociativos provocan fallo de página?

d) ¿Cuál será el tiempo de acceso efectivo si se agrega bit M y

el funcionamiento es el siguiente: el porcentaje de aciertos es
del 90%, del % de veces que no se encuentra el 10% de las
veces se produce fallo de página, de los cuales el 75% de las
veces la página no fue modificada, siendo el tiempo de
servicio de fallo de pagina de 4 ms si la página no fue
modificada y de 20 ms si fue modificada?
 Paginación bajo demanda

¿Encuentra?

¿No Encuentra?
¿Presente?

¿Ausente sin Bit M

o M=1?

TP en Memoria Física ¿Ausente con Bit M

M=0?
 Ejercitación

• Calcular el TEAM para un sistema que no dispone de Memoria

caché ni bit M.
Datos:
tam = 150 ns tsfp = 7.500.000 ns p = 0.0002

• Calcular el TEAM para un sistema que dispone de Memoria caché

pero no dispone de bit M.
Datos:
tam = 150 ns tama = 20 ns tsfp = 7.500.000 ns HR = 80%
del % de veces que no se encuentra el 7.5% de las veces se produce fallo de
página
 Ejercitación

• Calcular el TEAM para un sistema que dispone de Memoria caché y

bit M.
Datos:
tam = 150 ns tama = 20 ns tsfp (M=1) = 7.500.000 ns HR = 80%
tsfp (M=0) = 5.500.000 ns
del % de veces que no se encuentra el 7.5% de las veces se produce fallo de
página, de los cuales el 75% de las veces la página no fue modificada

En todos los casos esquematice primero la secuencia de

atención de fallo de página
 Políticas del SO para la memoria virtual

Política de recuperación Gestión del conjunto residente

Bajo demanda Tamaño del conjunto residente
Paginación adelantada Fijo
Variable
Política de ubicación Ámbito de reemplazo
Permite que un programa se ejecute Global
en cualquier ubicación de la memoria Local
Sólo relevante en segmentación pura Política de limpieza
Bajo demanda
Política de reemplazo Limpieza adelantada
Algoritmos básicos
Óptimo Control de carga
FIFO Grado de multiprogramación
Usada menos recientemente (LRU)
Del reloj
Buffers de página
Objetivo: minimizar la tasa de ocurrencia de fallos de página
Política de recuperación
Políticas del SO para la memoria virtual

Objetivo: minimizar la tasa de ocurrencia de fallos de página

 Política de ubicación
Cuando se produce un fallo de segmento hay que buscar en MP una ubicación
adecuada.
El problema no es trivial porque tanto los segmentos como los huecos en MP
son de tamaño variable. ¿Cómo se gestiona espacio libre en MP?
Política de ubicación
Política de ubicación
Políticas del SO para la memoria virtual

Objetivo: minimizar la tasa de ocurrencia de fallos de página

 Política de reemplazo

Bloqueo de marcos (núcleo del SO, buffer de E/S)

 Política de reemplazo
Algoritmo First-In-First-Out (FIFO)

Cadena de referencia: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

1 1 1 4 4 4 5 5 5
2 2 2 1 1 1 3 3
3 3 3 2 2 2 4

3 fallos de página comunes

6 fallos de página específicos del algoritmo
 Política de reemplazo
Algoritmo First-In-First-Out (FIFO)

Cadena de referencia: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

1 1 1 1 5 5 5 5 4 4
2 2 2 2 1 1 1 1 1
3 3 3 3 2 2 2 2
4 4 4 4 3 3 3

4 fallos de página comunes

6 fallos de página específicos del algoritmo
Política de reemplazo
Política de reemplazo
Anomalía de Belady
 Política de reemplazo
Algoritmo Optimo (OPT)

Cadena de referencia: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

1 1 1 1 1 4
2 2 2 2 2
3 3 3 3
4 5 5

4 fallos de página comunes

2 fallos de página atribuibles al algoritmo
 Política de reemplazo
Algoritmo LRU

Cadena de referencia: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

1 1 1 1 1 1 1 5
2 2 2 2 2 2 2
3 3 5 5 4 4
4 4 3 3 3

4 fallos de página comunes

4 fallos de página atribuibles al algoritmo
 Política de reemplazo
Algoritmo LRU

Implementación mediante una pila implementada como lista

doblemente ligada con punteros al inicio y al final

Cuando una página es referenciada se mueve al tope

Se reemplaza la página que queda en la parte inferior

Implementación mediante un contador

Cada entrada de página dispone de un contador en el cual se copia el

contenido del reloj cada vez que la página es referenciada. Cuando se
requiere eemplazar una página, se reemplaza la que tiene el menor valor
de contador.
 Política de reemplazo
Algoritmo LRU – Uso de la pila
Cadena de referencia: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Páginas en Memoria

1 1 1 1 1 1 4 4
2 2 2 2 2 2 5
3 4 5 3 3 3

Pila

1 1 1 4 1 2 5 1 2 3 4 5
2 2 1 4 1 2 5 1 2 3 4
3 2 2 4 1 2 5 1 2 3
 Política de reemplazo
Algoritmo de aproximación LRU: del Reloj o 2da Chance
 Política de reemplazo
Algoritmo de aproximación LRU: de Clases

Bit R Bit M

0 0

0 1

1 0

1 1
 Política de reemplazo
Buffering

Algoritmo Reemplazo de página

Asigna a Pool No Sí Asigna a Pool

Bit M
de Páginas de Páginas
=0
Modificadas libres
 Revisión

El algoritmo de reemplazo de páginas utilizado por algunas

versiones de Linux funciona de la siguiente manera:
•Cada entrada en la tabla de páginas dispone de un campo de
edad de 8 bits.
•Cada vez que se accede a una página, se incrementa la
variable edad.
•Linux recorre periódicamente la reserva de páginas globales y
disminuye la variable de edad de cada página cuando rota por
todas las páginas de memoria principal.
•Una página con edad 0 es una página vieja y se constituye en
la mejor víctima para el reemplazo. Cuanto mayor valor de
edad, menos elegible es para el reemplazo.

Este algoritmo se asemeja a: ……………………………

Políticas del SO para la memoria virtual

Objetivo: minimizar la tasa de ocurrencia de fallos de página

 Política de asignación
Tamaño.MP=70 pag / Tamaño.P1=15 pag – Tamaño.P2= 135 pág.
Política de asignación
Ámbito de reemplazo
Política de Asignación / Ámbito de reemplazo

Reemplazo Local Reemplazo Global

• El número de marcos No es posible
asignados a un proceso es
fijo.
Asignación • Las páginas que se van a
Fija reemplazar se eligen entre
los marcos asignados al
proceso.

• El número de marcos Las páginas que se van a

asignados a un proceso reemplazar se eligen
puede variar. entre todos los marcos de
Asignación • Las páginas que se van la memoria principal.
Variable reemplazar se eligen entre Esto hace que el tamaño
los marcos asignados al del conjunto residente de
proceso. los procesos varíe.
Políticas del SO para la memoria virtual

Objetivo: minimizar la tasa de ocurrencia de fallos de página

 Política de Limpieza

Demora la carga de una Podría estar

nueva página escribiéndose una página
que será modificada
nuevamente
Políticas del SO para la memoria virtual

Objetivo: minimizar la tasa de ocurrencia de fallos de página

Hiperpaginación
Soluciones a la Hiperpaginación
Soluciones a la Hiperpaginación
Modelo del Conjunto de trabajo
(Conjunto Activo – Working Set)
Modelo del Conjunto de trabajo
(Conjunto Activo – Working Set)
Sobrecarga