Sistemas Operativos9 Memoria Virtual

Prof. Javier Cañas R.

Nota

• El texto guía es: Operating System Concepts, Eight Edition, Avi Silberschatz, Peter Baer Galvin, Greg Gagne

• Estas PPT están basadas en las PPT originales que el autor del texto guía mantiene en: http://www.os-book.com/

Copyright Note

The slides below are copyright Silberschatz, Galvin and Gagne, 2008. The slides are authorized for personal use, and for use in conjunction with a course for which Operating System Concepts is the prescribed text. Instructors are free to modify the slides to their taste, as long as the modified slides acknowledge the source and the fact that they have been modified. Paper copies of the slides may be sold strictly at the price of reproduction, to students of courses where the book is the prescribed text. Any use that differs from the above, and any for profit sale of the slides (in any form) requires the consent of the copyright owners; contact Avi Silberschatz (avi@cs.yale.edu) to obtain the copyright owners consent.

Temario

1. Antecedentes

2. Paginación por demanda

3. Copia en Escritura

4. Reemplazo de Páginas

5. Asignación dr Frames

6. Thrashing

Objetivos

• Describir los beneficios de los sistemas de memoria virtual

• Explicar los conceptos de paginación por demanda, algoritmos de reemplazo de página y asignación de marcos de páginas.

• Discutir el principio del modelo Working-Set.

1 Antecedentes

• Memoria virtual: consiste en la separación de la memoria lógica (usuario) de la memoria real:

• Sólo una parte del programa necesita estar en memria para ejecución.

• El espacio lógico puede ser mucho mayor que el espacio físico.

• Permite compartir espacios de direcciones entre varios procesos.

• La creación de procesos es más eficiente.

... Antecedentes

• La memoria virtual se puede implementar vía:

• Paginación por demanda

• Segmentación por demanda

La memoria virtual es más grande que la física

El espacio de direcciones virtuales

Biblioteca compartida usando memoria Virtual

System libraries Share memory Process creation

with fork()

2 Paginación por Demanda

• Consiste en llevar páginas a memoria sólo cuando éstas se necesitan. Con esto se logra:

• Menor necesidad de I/O

• Menor necesidad de memoria

• Respuesta más rápida

• mayor número de usuarios

... Paginación por demanda

• Si una página se necesita, se referencia:

• Si la referencia es inválida: se aborta

• Si la página no está en memoria, se trae

• Swapper perezoso: nunca intercambia una página a memoria a menos que se necesite.

• Un Swapper que se relacione con páginas se llama pager.

Transferencia de una memoria paginada a espacio contiguo de

disco

Bit válido-inválido Cada entrada de la T. de Página tiene asociado un bit Válido-Inválido

(v ⇒ en-memoria, i ⇒ no-en-memoria)

Inicialmente el bit valid–invalid bit se inicializa en i en todas las entradas Ejemplo de Tabla de Página:

Durante el cálculo de dirección, si el bit válido-inválido es I ⇒ falla de página

vvvvi

ii

….

Frame # valid-invalid bit

page table

Tabla de Página cuando algunas páginas no están en memoria

... Falla ¿Qué pasa si un proceso intenta un acceso a una página que no está en

memoria? Un acceso a una página inválida genera falla de página Si el bit está marcado inválido se genera trap al SO1. El SO busca en otra tabla (en PCB) para decidir si la referencia es válida:

Referencia inválida ⇒ aborta

No está en memoria2. Tomar un frame libre3. Intercambiar la página al frame (Swap)4. Reset de tablas5. Poner bit válido como= v6. Reinicializar la instrucción que generó la falla

... Falla de Página

• Un requisito fundamental de la paginación por demanda es la habilidad de re iniciar una instrucción después de una falla de página:

• Si la falla ocurre durante el fetch, se re inicia haciendo un fetch nuevamente.

• Si la falla ocurre en un fetch de operando, se debe hacer nuevamente el fetch (IF) y la decodificación (ID) y después el fetch de operando.

... Falla

• Ejemplo de peores casos:

• movimiento de bloques

• Instrucciones con tres direcciones:

add, A, B, C (A ←B+C)

Secuencia en manejo de falla de página

Desempeño de la paginación por demanda

• Tasa de fallas de página: 0≤ p ≤1.0

• Si p=0 no hay fallas de página

• Si p=1, cada referencia genera falla

• Tiempo de Acceso Efectivo (TAE)

TAE=(1-p) × acceso_memoria + p × ( overhead_falla + swap_out_página + swap_in_página + overhead_restart)

Ejemplo Tiempo acceso memoria = 200 nseg

promedio servicio falla = 8 mseg.

TAE = (1 – p) x 200 + p (8 mseg) = (1 – p x 200 + p x 8,000,000 = 200 + p x 7,999,800

Si un acceso de 1,000 genera una falla de página, entonces

TAE = 8.2 μseg. La velocidad se frena por un factor de 40!!

3 Copia en Escritura

• Un beneficio adicional de la memoria virtual es un menor tiempo para la creación de procesos. Esto se logra con la técnica de Copia en Escritura (COW Copy-on-Write).

• La llamada al sistema fork() genera un proceso hijo que es una copia de su padre.

• COW permite que inicialmente padre e hijo compartan las mismas páginas de memoria.

... COW

• Estas páginas están marcadas como Copia-en-escritura. Si cualquiera de los procesos escribe en una página compartida, se genera una copia de la página compartida.

• COW permite mayor eficiencia en la creación de procesos. Solo se copian páginas modificadas.

• Páginas libres se asignan desde un pool de “páginas en cero”. Las páginas demandadas se ponen en “cero” antes de la asignación.

Antes que el Proceso 1 modifique página C

Después que el Proceso 1 modificó página C

4 Reemplazo de Páginas

• Si un proceso de 10 páginas actualmente sólo usa la mitad de ellas, entonces, la paginación por demanda ahorra el I/O necesario de cargar 5 páginas que no se utilizarán.

• Esto implica que podemos aumentar el grado de multiprogramación, corriendo el doble de procesos.

Sobre-asignación

• Si aumentamos el grado de multiprogramación, estamos sobre asignando memoria.

• Al sobre-asignar, si ocurre una falla de página, la página requerida está en disco, pero no hay frames libres (ver figura).

• Es necesario prevenir sobre-asignación modificando la falla de página para incluir reemplazo.

• Usar el bit de modificación (dirty bit) para reducir el overhead en transferencia de páginas a disco.

Caso: No hay frames libres!

• La completa separación de los espacios lógicos y físicos se completa con reemplazo de página. Una gran memoria virtual se puede lograr en una memoria física pequeña.

• Reemplazo de página: encontrar una página que no esté en uso y volverla al disco.

Reemplazo de páginas

• Se requiere:

• Un algoritmo

• Desempeño: el mejor algoritmo resulta en el mínimos de fallas de página.

• Algunas páginas se traerán a memoria varias veces.

Reemplazo de Páginas

Procedimiento de Reemplazo

1. Encontrar la ubicación de la página solicitada en disco

2. Encontrar un frame libre:

• Si hay un frame libre, utilizarlo

• Si no hay usar algoritmo de reemplazo de página para seleccionar un frame víctima

3. Traer la página al nuevo frame libre. Actualizar tabla de página.

4. Recomenzar

Reemplazo de Página

Algoritmos de reemplazo de Página

• Se desea la menor tasa de fallas de página

• Los algoritmos se evalúan corriendo un string de referencias a memoria (string de referencia) y calculando el número de fallas de página.

• Para todos los ejemplos se considerará el siguiente string de referencia: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

• Notación: M(m,r)={páginas}, donde m= número de frame y r es el índice del string de referencia (comienza en 1).

Número de fallas de página vs número de frames

• En la medida que aumenta el número de frames, el número de fallas de página baja a un nivel mínimo.

Algoritmo FIFO: First-in-First-out

String de referencia: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 3 frames (3 páginas en memoria por proceso)

4 frames

Anomalía de Belady: más frames ⇒ más fallas de página

1

2

3

1

2

3

4

1

2

5

3

4

9 fallas de página

1

2

3

1

2

3

5

1

2

4

5 10 page faults

44 3

Ejemplo reemplazo FIFO

M(3,5)={0,1,2}

Anomalía de Belady en FIFO

Algoritmo Óptimo

1

2

3

4

6 page faults

4 5

La página que se reemplaza es la que no se usará en el período más grande de tiempo

Ejemplo con 4 frames

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

¿Cómo se puede saber? Se utiliza como referencia para comparar algoritmos

Ejemplo

Algoritmo LRU

• LRU: Least Recently Used, Menos Recientemente Usada.

• Ejemplo: String de referencia: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

5

2

4

3

1

2

3

4

1

2

5

4

1

2

5

3

1

2

4

3

Ejemplo

Implementación con contador

• Cada entrada de la página tiene un contador; toda vez que la página es referenciada en esta entrada, se copia el reloj en el contador.

• Cuando se necesita cambiar una página, se observan los contadores.

• Se requiere una búsqueda en la tabla y una escritura en memoria.

Implementación con Stack

• Se mantiene un Stack con los números de página en una lista doblemente enlazada:

• Si la página es referenciada:

‣ Mover al tope de stack

‣ Se requiere cambiar 6 punteros

• No se requiere buscar para reemplazar

• Sacar una página y ponerla en el tope significa en el peor caso cambiar 6 punteros!

Ejemplo de uso de Stack

Repaso ¿Qué significa sobre asignación de memoria (over-

allocating)?Dado: 1, 2, 5, 3, 4, 2, 5, 3, 2, 1, 2, 5, calcular M(4,8)

usando algoritmo OPT ¿En qué consiste la anomalía de Belady?Que propiedad tiene un algoritomo de Stack de reemplazo de

página? ¿Cómo se puede implementar LRU? ¿Qué es el “dirty” bit?

Aproximaciones a LRU

• Bit de referencia:

• A cada página se asocia un bit. inicialmente en cero.

• Cuando una página es referenciada, el bit se pone en 1.

• Reemplazar la página que tiene bit de referencia en cero (si existe).

• No se conoce el orden

...Aproximaciones a LRU

• Segunda oportunidad:

• Se necesita un bit de referencia: si la página es seleccionada para reemplazo, se inspecciona el bit de referencia. Si el bit es cero, se reemplaza esta página. Si el bit es 1, se le da na nueva oportunidad a esta página y se selecciona la siguiente.

• Reemplazo orden de reloj: El puntero avanza como un reloj.

• Si la página a reemplazar (en orden de reloj) tiene el bit de referencia en 1:

• Se fija en cero el bit• La página queda en memoria• Reemplazar la siguiente (orden reloj), sujeta a las mismas reglas.

Reemplazo “segunda oportunidad” (Reloj)

Algoritmos de Conteo

• Mantener un contador del número de referencias realizadas a cada página.

• Algoritmo LFU (Least Frequently Used): reemplazar la página con el menor contador.

• Algoritmo MFU (Most Frequently Used): se basa en el argumento que la página con el contador menor probablemente será necesitada y usada a la brevedad.

• Tanto LFU como MFU sus implementaciones son caras y no se aproximan al algoritmo óptimo.

5 Asignación de Frames

• Cada proceso necesita un mínimo número de páginas.

• Ejemplo: IBM 370 necesita 6 páginas para soportar la instrucción SS MOVE:

• SS MOVE ocupa 6B, que puede ocupar 2 páginas

• 2 páginas para manejar “desde”

• 2 páginas para manejar “hacia”

• Existen dos esquemas de asignación: fija y por prioridad.

Asignación Fija

• Asignación igualitaria: Por ejemplo, si hay 100 frames y 5 procesos, a cada uno le corresponden 20 frames.

• Asignación proporcional: Se asignan frames acorde al tamaño de los procesos

- Sea si= tamaño del proceso pi

- S=∑si

- m= número total de frames

- ai= asignación a pi=(si/S)×m

!

m = 64

s1

= 10

s2

= 127

a1

=10

137" 64 # 5

a2

=127

137" 64 # 59

Asignación por Prioridad

• Se utiliza la asignación proporcional, pero en vez del tamaño del proceso se utiliza su prioridad

Asignación Global vs Local

• Si el proceso P1 genera una falla de página:

‣ Seleccionar para reemplazo uno de sus frames

‣ Seleccionar un frame de un proceso con la prioridad más baja

• Reemplazo Global: se escoge un frame del conjunto de todos los frames. Un proceso puede tomar un frame de otro proceso.

• Reemplazo Local: cada proceso selecciona frames sólo de sus frames asignados.

6 Thrashing

• Si un proceso no tiene las páginas suficientes, el número de fallas de página puede llegar a ser muy alto. La consecuencia es:

• Baja utilización de CPU

• El SO llega a pensar que debe aumentar el grado de multiprogramación y agrega otro proceso al sistema...

• Thrashing: el proceso está muy ocupado haciendo intercambio de páginas entre memoria y disco.

... Thrashing

Paginación por demanda y Thrashing

• ¿Por qué funciona la paginación por demanda?

Rp: porque existe un modelo de localidad

• Los procesos cambian de una localidad a otra.

• Las localidades pueden traslaparse

• ¿Por que ocurre thrashing?

Rp: porque: ∑ (tamaños de localidades) > tamaño memoria

Ejemplo de localidades en un patrón de referencias a memoria

El Modelo Working-Set Δ ≡ ventana working-set ≡ número fijo de páginas referenciadas

Ejemplo: 10,000 instrucciones

WSSi (working set del Proceso Pi) =número total de páginas referenciadas en el Δ más reciente (varia en el tiempo) Si Δ muy pequeño no abarcará la localidad completa Si Δ muy grade, abarcara varias localidades Si Δ = ∞ ⇒ abarcará el programa completo

Sea: D = Σ WSSi ≡ el total de frames demandados

‣ Si D > m ⇒ Thrashing

‣ Política: SiD > m, suspender uno de los procesos

... Modelo W-S

Conocer en todo momento el Working-Set• Se puede aproximar con un timer más un bit

de referencia.

• Ejemplo: Δ=10.000 referencias

• El timer interrumpe cada 5000 unidades de tiempo.

• Se mantienen 2 bits por cada página en memoria (bits de historia)

• Toda vez que el timer interrumpe, se copian lo bits a memoria y se fijan todos los bits de referencia en cero.

• Si uno de los bits en memoria está en uno, la página está en el Working Set

... Conocer en todo

• Este método no es completamente exacto. ¿Por qué?

• Se puede mejorar usando 10 bits de historia e interrumpiendo cada 1000 unidades de tiempo.

Ajustes de Fallas de Página

• Es necesario establecer una tasa aceptable de fallas de página:

• Si la tasa actual es baja, los procesos pueden perder frames.

• Si es muy alta, deben ganar frames

WS y fallas de página

Unix y Mac OS X

• vm_stat (Mac OS X). En Unix vmstat

Sistemas Operativos9 Memoria Virtual

Prof. Javier Cañas R.