Memoria virtual. Sistemas Operativos Tema 9. Memoria virtual. Memoria virtual. Memoria virtual. Memoria virtual. Memoria virtual

Memoria virtual „ Sistemas Operativos Tema 9. Memoria virtual „ „ „ „ La memoria virtual es una técnica que permite la ejecución de procesos parcia

18 downloads 327 Views 1MB Size

Recommend Stories


Capítulo 4 Memoria virtual
Capítulo 4 Memoria virtual Cómo la memoria virtual se mapea a la memoria física. La memoria virtual es una técnica de gestión de la memoria que permi

CAMPUS VIRTUAL ENTORNO VIRTUAL ANGELINO
CAMPUS VIRTUAL ENTORNO VIRTUAL ANGELINO CALIFICACIONES: LIBRO DE CALIFICACIONES CON ACTIVIDADES (FORO, TAREAS Y CUESTIONARIOS) YA CREADAS EN EL CURSO

ta virtual Cultura ITSO Revista virtual
Revista virtual Septiembre - Octubre 2011 Cultura ITSON Cultura ITSON Cultura ITSON Cultura ITSON Cultura ITSON Cultura ITSON Cultura ITSON Cultura

El virtual antes de la era virtual
http://dx.doi.org/10.4995/ANIAV.2015.1078   Valdaliso  Casanova,  Teresa.   Investigadora/doctoranda,  Universidad  Politécnica  de  Valencia,  Depar

Story Transcript

Memoria virtual „

Sistemas Operativos Tema 9. Memoria virtual

„ „ „ „

La memoria virtual es una técnica que permite la ejecución de procesos parcialmente cargados en memoria principal Los programas pueden ser más grandes que la memoria física Se utiliza el disco como almacén secundario de procesos Libera al programador de la preocupación de que sus programas quepan en memoria La idea es mantener en memoria principal sólo los fragmentos de cada proceso que se estén utilizando

© 1998-2008 José Miguel Santos – Alexis Quesada – Francisco Santana – Belén Esteban 1

Memoria virtual „

‰

‰

„

„

Memoria virtual

Programas reales Æ en muchos casos no se necesita todo el programa ‰

2

„

Código que maneja condiciones de error poco comunes (casi nunca se ejecuta) En muchos casos se reserva más memoria de la necesaria (vectores, tablas, etc...) Opciones y funciones del programa que se usan con muy poca frecuencia (copias de seguridad -, listados específicos, etc...)

Si empleamos m.v., con poca memoria física se pueden atender grandes demandas de memoria: ‰

‰

El sistema operativo selecciona automáticamente qué fragmentos del proceso residen en memoria principal Ojo, todo esto es bastante complejo de resolver

‰

el programador no tiene que preocuparse tanto de la escasez de memoria eliminamos la necesidad de técnicas como los recubrimientos (overlays) cuya responsabilidad recae en el programador “caben más procesos simultáneamente en la memoria física” -> aumenta la productividad de la CPU

3

Memoria virtual

Memoria virtual „

„

4

Riesgo: si escogemos mal los fragmentos en memoria principal, tendremos que recurrir al disco con frecuencia La m.v. funciona porque los programas cumplen una fuerte localidad: los siguientes accesos a memoria suelen estar cerca de los anteriores

„

„

Por tanto, con m.v. los procesos se cargan parcialmente en memoria real, siendo el SO el que lleva a cabo toda la gestión del espacio de forma transparente al programador El SO decide: ‰ ‰ ‰

5

Qué partes cargar Cuándo cargarlas Dónde ubicarlas

6

Memoria virtual: esquema general

Paginación por demanda

(demand paging) „ „

Técnica más habitual para implementar memoria virtual Combinar paginación con intercambio (swap) ‰

‰

En lugar de intercambiar un proceso entero, ahora sólo intercambiamos algunas páginas Ideal: „ „ „

Cuando un proceso se va a traer a memoria, el paginador “adivine” cuales son las paginas que va a usar De esta forma, en lugar de traer a memoria todo el proceso, el paginador sólo trae las páginas necesarias De esta forma se evita leer y colocar en la memoria páginas que no se usan, reduciendo de esta forma el tiempo de intercambio y la cantidad de memoria física requerida

7

Paginación por demanda „

8

Paginación por demanda

Si no tenemos todas las páginas en memoria, cuando se referencia a una página concreta, ¿Cómo saber si está en memoria? ‰

‰

Necesario distinguir entre páginas válidas (en memoria principal) y no válidas (sólo en disco) Las páginas válidas/no válidas se marcan en la tabla de páginas por medio de un bit de validez

9

Paginación por demanda: la idea

10

Fallo de página „

SI ADIVINAMOS CORRECTAMENTE Y TRAEMOS A LA MEMORIA SOLO LAS PAGINAS QUE SE NECESITAN, EL PROCESO SE EJECUTARA EXACTAMENTE IGUAL QUE SI HUBIERAMOS TRAIDO TODAS LAS PAGINAS

11

„

Si se intenta acceder a una página no válida (bit de invalidez activado), el hardware genera una excepción llamada fallo de página (page fault) El fallo de página provoca que el s.o. recupere del disco (swap area) la página requerida. Se actualiza la tabla de páginas y se reintenta la instrucción que ocasionó el fallo

12

Explicación del diagrama anterior

Gestión de un fallo de página

„

„ „

„

„

„

1.- Acceso a la tabla de páginas donde se observa que el bit de validez indica que no está en memoria => Page _Fault 2.- Guardar los registros del usuario y el estado del proceso 3.- Determinar que la interrupción fue un fallo de página (vector de interrupciones) 4.- Verificar que la referencia a la página fue válida (el SO consulta una tabla interna, que usualmente se guarda con el BCP del proceso). Si la referencia no es válida, se termina el proceso. Si era válida pero todavía no se ha traído esa página, se determina la posición de la página en el disco (información que también estará en el BCP) y procedemos a traerla. 5.- Encontramos un marco libre y planificamos una operación de disco para leer la página deseada y colocarla en el marco recién asignado 6.- Durante la espera, asignar la CPU a algún otro usuario (opcional)

13

Explicación del diagrama anterior (2) „ „

„ „

„ „

14

Paginación por demanda

7.- Interrupción del disco (E/S terminada) 8.- Guardar los registros y el estado de proceso del otro usuario (si se ejecutó el paso 6) 9.- Determinar que la interrupción provino del disco 10.- Corregir la tabla interna que se guarda junto con el proceso y la tabla de páginas, de modo que indiquen que la página ya está en memoria 11.- Esperar que la CPU se asigne otra vez a este proceso 12.- Restaurar los registros de usuario, el estado del proceso y la nueva tabla de páginas, y reanudar la instrucción interrumpida

„

Caso extremo: ‰

Paginación por demanda pura „

„

‰

‰

„

Nunca se trae una página a memoria si no se necesita

Ejecución de una instrucción Puede generar más de un fallo de página (una página para la instrucción y muchas para los datos) Problema: rendimiento disminuye considerablemente al aumentar el nº de fallos de página

Sin embargo, la localidad en los programas hace que el rendimiento de la paginación por demanda sea razonable

15

Paginación por demanda: ventajas „

„

Los programadores disponen de un espacio de memoria mayor que las disponibilidades de memoria real del sistema Mejora el rendimiento general del sistema ‰

„

16

Reanudación de instrucciones „

Mejora el uso de la memoria, mejorando el grado de multiprogramación y por tanto mejorando la capacidad de planificación del SO

Pero es importante mantener baja la frecuencia de fallos de página, ya que de lo contrario el tiempo de acceso aumentará y frenará drásticamente la ejecución de los procesos 17

Además del apoyo hardware específico necesario, ¿Existe algún otro tipo de restricción para que esta técnica se pueda implementar? ‰

Necesidad de poder reiniciar una instrucción después de un fallo de página „

Ejemplos: ‰ ‰

DECREMENTAR reg[1] y BIFURCAR a la dirección Y si el resultado es cero Instrucción MVC del IBM 360

18

Reanudación de instrucciones „

„ „

Algoritmos de gestión de memoria virtual

Una implicación arquitectónica importante para poder implementar paginación por demanda, y en general, memoria virtual es que se puede producir la interrupción de ciertas instrucciones durante su ejecución Problemas: reiniciar la instrucción no siempre soluciona el problema Soluciones: ‰

‰

‰

„

Para la implementación de la paginación por demanda, el SO debe implementar: ‰

Algoritmo de asignación de marcos „

Deshacer los efectos parciales de la instrucción interrumpida y reiniciar la instrucción cuando haya sido procesada la excepción Reanudar la instrucción desde el punto exacto de interrupción cuando el elemento ausente sea incorporado a memoria Preexaminar las referencias a memoria buscando fallos de página antes de comenzar la ejecución de la instrucción

‰

Si tenemos varios procesos en memoria es necesario decidir cuantos marcos se asignan a cada uno

Algoritmo de reemplazo de páginas „

Proceso básico ‰ ‰ ‰

„

1.- Atender la interrupción de fallo de página 2.- Traer la página a memoria y colocarla en un marco libre 3.- Reiniciar el proceso

¿Y si no hay marcos libres? Æ Reemplazo de páginas

19

Algoritmo de reemplazo „

Bit de modificación

Modificación en el proceso básico: ‰

‰

‰

‰

20

„

Si no hay marco libre, usar un algoritmo de reemplazo de página para escoger un marco víctima Escribir la página víctima en el disco y actualizar tablas Leer la página del disco y colocarla en el marco recién liberado y actualizar tablas Finalmente reiniciar el proceso de usuario

Problema: ‰

‰

Si no hay marcos libres se requieren dos transferencias de páginas Este gasto extra puede reducirse empleando un bit de modificación o bit sucio „

El hardware pone a 1 el bit de modificación de una página siempre que se escribe una palabra o byte de la página

21

Ejemplo de cadena de referencias

Algoritmos de reemplazo: cómo evaluarlos „ „

Objetivo: Frecuencia de fallos de página sea lo más baja posible Evaluamos un algoritmo ejecutándolo con una serie específica de referencias y calculando el número de fallos de página ‰

„

22

0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103, 0104, 0101, 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105 (decimal) Si el tamaño de página es de 100 bytes, se reduce a la siguiente cadena de referencias

La serie de referencias las podemos generar forma aleatoria o rastreando la ejecución de un sistema dado y registrando la dirección de cada referencia a la memoria

Para una serie de referencias determinadas y un algoritmo concreto, determinar el número de fallos de página requiere conocer el número de marcos de los que se dispone en el sistema

1,4,1,6,1,6,1,6,1,6,1

23

24

Algunos algoritmos de reemplazo

Algoritmo FIFO „

Básicos

„

‰ ‰ ‰

1. FIFO ‰

FIFO OPTIMO LRU – least recently used

‰ ‰

Aproximaciones LRU

„

‰ ‰ ‰

LRU con bits de referencia adicionales LRU de segunda oportunidad o del reloj LRU de segunda oportunidad mejorado

‰

‰

De conteo

„

‰ ‰

LFU – less frequently used MFU – most frequently used

Se sustituye la página residente que lleve más tiempo en memoria Fácil de implementar (cola FIFO de páginas) Problema: al no tener en cuenta la historia del uso de una página dada, FIFO puede prescindir de páginas a las que se accede con frecuencia Padece la anomalía de Belady (fenómeno paradójico consistente en que aumenta el número de fallos de páginas cuando se asignan más páginas reales al proceso) Propiedad de pila: para cualquier punto en la cadena de referencia, el conjunto de páginas en N marcos de página es un subconjunto del que se formaría en N+1 marcos de página

25

Ejemplo: FIFO

26

Efecto Belady

27

Ejemplo: óptimo o mínimo

Algoritmo de reemplazo óptimo „

28

2. Óptimo ‰

‰

‰ ‰

Escoger como víctima la página que más tarde en volver a ser accedida Es el algoritmo que presenta la frecuencia de fallos de página más baja de todos No implementable (requiere presciencia) Útil como referencia de comparación

29

30

Ejemplo: LRU

Algoritmo LRU „

3. LRU: menos recientemente usada ‰ Aproximación implementable del óptimo ‰ Se asocia a cada página el instante en que se usó por última vez, y en caso de reemplazo se escoge la página que tiene más tiempo sin usarse ‰ Implementacion: „ „

‰ ‰

Contadores (marca de tiempo) Pila

Requiere hardware adicional y es costoso Los sistemas reales implementan aproximaciones a la LRU

31

Aproximaciones a la LRU „

32

Varios bits de referencia

4. Aproximación a LRU ‰ Tanto el reemplazo óptimo como el LRU no padecen la anomalía de Belady ‰ Las técnicas basadas en LRU utilizan un bit de referencia puesto por el hardware ‰ El hardware enciende el bit de referencia de una página cada vez que se hace referencia a ella (lectura o escritura) ‰ Examinando este bit no conoceremos el orden de uso, pero sí sabemos cuáles páginas se usaron y cuales no

„

4.1. Algoritmo con bits de referencia adicionales ‰

‰

Es posible obtener información de ordenamiento adicional si registramos los bits de referencia a intervalos adicionales Por ej.: byte histórico „ „ „

‰

‰

11000100 01110111 Se usó más recientemente LRU: página con el número más bajo

No está garantizada la unicidad de dichos números (en caso de igualdad, se podría aplicar FIFO) Si el número de bits históricos es cero, es decir, dejamos sólo el bit de referencia => Algoritmo de segunda oportunidad

33

Algoritmo 2ª oportunidad o del reloj „

34

Algoritmo 2ª oportunidad o del reloj

4.2. Algoritmo de segunda oportunidad o algoritmo del reloj ‰ FIFO teniendo en cuenta el bit de referencia ‰ Si el valor es cero, reemplazamos la página, pero si es 1, le damos una segunda oportunidad, ponemos su bit de referencia a cero y seleccionamos la siguiente página FIFO ‰ Una forma de implementar el algoritmo de segunda oportunidad es con una cola circular ‰ = FIFO si todos los bits están encendidos 35

36

Algoritmos de conteo: LFU, MFU

2ª oportunidad, mejorado „

5. Algoritmos de conteo

„

4.3. Algoritmo de segunda oportunidad mejorado ‰ = pero considerando tanto el bit de referencia como el bit de modificación ‰ Cuatro situaciones: (0,0), (0,1), (1,0), (1,1) ‰ Se reemplaza la primera página que encontremos de la clase más baja ‰ Es posible que se tenga que explorar la cola varias veces entes de encontrar la página a reemplazar ‰ Ej: Macintosh

‰ ‰

Contador del número de referencias 5.1. Algoritmo LFU: menos frecuentemente usadas (cuenta más baja) son las reemplazadas „ „ „

‰

Problema: páginas que se usaron mucho durante la fase inicial del proceso y luego no se vuelven a usar Solución: Desplazar las cuentas un bit a la derecha a intervalos regulares Problema serio: páginas traídas recientemente, alta probabilidad de salir (cuenta baja)

5.2. Algoritmo MFU: más frecuentemente usada (cuenta más alta) es la reemplazada, para evitar el problema anterior „

Problema: se pueden mantener páginas viejas a las que no se accede

37

Campos en la tablas de páginas

Algoritmos de reemplazo: resumen Problemas FIFO Optimo

El peor resultado (mayor tasa de fallos de página)

Anomalía de Belady

El mejor resultado (menor tasa de fallos de página)

No implementable

38

Hardware y/o ED necesarios

Marco

Memoria Paginada

Memoria Virtual

obligatorio

obligatorio

Lista encadenada de páginas Permisos

opcional

opcional

Validez

obligatorio

LRU

Demasiada información + hardware

Contador (timestamp) en TP o pila

Sucio

opcional

Aprox. LRU con bits referencia

El SO debe interrumpir y desplazar los bits referencia

Bits de referencia en TP

Bloqueo

opcional

Aprox. LRU de 2ª oportunidad Aprox. LRU de 2ª oportunidad mejorado

Bit de referencia en TP + lista circular Selecciona la página que menos tiempo se tarda en reemplazar y que se ha utilizado menos recientemente

Se necesitan varias batidas en la lista circular

Bit de referencia en TP + lista circular

LFU

La últimas páginas introducidas recientemente están continuamente reemplazándose

Contador en TP

MFU

Las páginas mas “populares” se reemplazan

Contador en TP

FIFO

LRU

Bits de referencia Contador (timestamp)

LRU con bits referencia

LRU 2ª oportun.

LRU 2ª oportun. mejorado

obligatorio (varios bits)

obligatorio (1! bit)

obligatorio (1! bit)

LFU

MFU

obligatorio

obligatorio

opcional

Contador accesos

39

Paginación por demanda: mejoras en el reemplazo „

„

„

40

Asignación de marcos a los procesos

Reserva de marcos libres: % de marcos libres para no esperar a que las víctimas se escriban en disco Recordar qué páginas están en los marcos libres Descargar en disco las páginas modificadas en segundo plano

„

Reserva de marcos ‰

‰

‰

Es conveniente definir un sistema de reparto de los marcos a los procesos en ejecución Todo proceso debería tener una reserva mínima de marcos (depende del repertorio de instrucciones) ¿Cómo asignar los marcos a los procesos? „ „ „

41

Reparto alícuoto Reparto proporcional (por tamaño, por prioridad) Reemplazo ¿global o local?

42

Tipos de reemplazo „

„ „

Un mismo proceso podría tener un rendimiento muy diferente a causa de circunstancias puramente externas

„

Reemplazo local ‰

„

Primeros sistemas de paginación „

El conjunto de páginas candidatas a sustituir está/no está restringido al proceso que provoca la carencia de página

Reemplazo global ‰

„

„

Reemplazo local/global ‰

„

Hiperpaginación y área activa

Podría obstaculizar la ejecución de un proceso al no permitirle aprovechar otras páginas de memoria de poco uso

„

El reemplazo global generalmente aumenta el rendimiento del sistema y es el método más utilizado

„

SO supervisa la utilización de la CPU Si el aprovechamiento es demasiado bajo Æ aumenta el grado de multiprogramación Supongamos una política de reemplazo global Al entrar un nuevo proceso Æ solicitudes de marcos (se quitaran marcos a otros procesos, procesos que a su vez necesitaran mas marcos y los quitaran a otros procesos) Resultado: Aumenta la cola de procesos en el dispositivo de paginación (el encargado de servir los fallos de página) y se va vaciando la cola de preparados Consecuencia: disminuye el aprovechamiento de la CPU y entonces el planificador de CPU aumenta el grado de multiprogramación, agravando aún más el problema

43

Hiperpaginación y área activa „

„

Modelo de localidades

Si el grado de multiprogramación es excesivo, el sistema puede estar más tiempo paginando que haciendo trabajo productivo (hiperpaginación) ¿cómo evitarla? ‰

„

„

Políticas de reemplazo local „

‰

44

„

la hiperpaginación de un proceso puede afectar al resto

Concediendo memoria según las necesidades reales (localidades, área activa...)

Se observa que todo proceso trabaja en cada momento con unas zonas de código y datos bien delimitadas: localidad Cuando se salta a otra subrutina, etc., se cambia de localidad Si un proceso tiene asignada su localidad en memoria principal, no ocasiona fallos de página

45

Área activa (working set) „ „

Área activa

Concepto que trata de aproximarse a la localidad actual de un proceso Es el conjunto de páginas con el que ha trabajado un proceso en un pasado reciente  (ventana del área activa) : ‰

„

46

WS(t, ) = páginas accedidas entre t y t- 

Si  tiene el tamaño adecuado, es una fiel aproximación de la localidad actual

47

48

Área activa: cómo aplicarla en la gestión de memoria virtual „ „ „

„

¿Cómo detectar las áreas activas? „

El SO vigila el área activa de cada proceso y le asigna un número de marcos igual a su tamaño Si hay suficientes marcos adicionales, se puede iniciar otro proceso Si la suma de los tamaños de las áreas activas aumenta hasta exceder el número total de marcos disponibles, el SO seleccionará un proceso para suspenderlo

„

La estrategia del área activa evita la hiperpaginación al tiempo que mantiene el grado de multiprogramación lo más alto posible

Lo difícil del modelo del área activa es cómo sabe el SO cuál es el área activa de un proceso en cada momento Implementación ‰ El área activa se puede estimar utilizando el bit de referencia, de forma similar a la LRU „ A intervalos regulares, los bits de referencia de las páginas residentes pueden ser registrados (nº de bits históricos) y borrados „ De esta forma tenemos una especie de historial de uso ‰

Si se descubre que un proceso no tiene páginas suficientes para su área activa, se le suspende por completo: así se evita la hiperpaginación

49

Frecuencia de fallos de página (PFF) „ „ „ „

50

Prepaginación

Podemos establecer límites superiores e inferiores para la frecuencia de fallos de página deseada Si la PFF de un proceso es muy baja, le quitamos páginas; si es muy alta, le damos más páginas Si la PFF global aumenta y no hay marcos libres, seleccionamos un proceso y lo suspendemos Los marcos de página se repartirán entre los procesos que tengan fallos de página muy frecuentes

„

Prepaginación: cuando se reanuda un proceso que estaba en swap, traer a memoria principal todas las páginas del área activa ‰

Para cada proceso se guarda también la información relativa al área activa

‰

La prepaginación puede ser ventajosa en algunos casos (cuando el costo de la prepaginación sea menor que el de atender los fallos de página correspondientes)

51

Tamaño de página óptimo „

„

52

Influencia de la estructura del código

La eficiencia de las operaciones de E/S (disco) y el espacio consumido en tablas recomiendan tamaños de página grandes La localidad y la fragmentación recomiendan tamaños de página pequeños

53

„

Estructura de los programas La forma en que se accede a los datos Las estructuras de datos que se emplean ‰ Cómo se estructura el código (el compilador y el cargador también pueden tener efecto sobre la paginación) ‰ El lenguaje de programación (la localidad es mejor en lenguajes con uso restringido de punteros) Influyen en el rendimiento de la memoria virtual ‰ ‰

54

Otras técnicas: segmentación por demanda

Otras consideraciones Interbloqueo de E/S cuando se emplea DMA

„

‰ ‰

„

E/S pendiente en una página reemplazada Soluciones: „ „

Segmentación por demanda ‰ ‰

La unidad de gestión es el segmento Ej: OS/2 en el Intel 80286

Búferes en memoria del SO Permitir fijar páginas en memoria (bit de bloqueo)

Tiempo real: la m.v. es nociva en un sistema de t.r.

„

55

Memoria virtual: sumario „

Estrategias Paginación bajo demanda Algoritmos de reemplazo de páginas

Algoritmos de asignación de marcos

„

•FIFO •OPT •LRU

•LRU bits adicionales •LRU 2ª oport. •LRU 2ª oport. mejorado

•LFU •MFU

•Reserva de marcos •Reemplazo local / global

Mejoras Reserva de marcos libres Evitar Hiperpaginación

„

• Reemplazo local • Localidades/área activa • Frecuencia de fallos de página

Otras consideraciones Prepaginación Tamaño de página Estructura de los programas Interbloqueo de E/S con DMA

57

56

Get in touch

Social

© Copyright 2013 - 2024 MYDOKUMENT.COM - All rights reserved.