memoriavirtual - academia cartagena99 · 2015. 6. 17. · listasenlazadas(windows)...

Introducción a la memoria virtual (MV)Conceptos relacionados con la MV

Algoritmos de gestión de la MVCasos de estudio

Memoria virtual

E. Campo M. Knoblauch Ó. López J. Clemente

Departamento de AutomáticaUniversidad de Alcalá

Sistemas Operativos Avanzados Memoria virtual 1 / 41



Índice1 Introducción a la memoria virtual (MV)

¿Qué es la MV?Ventajas de la MV

2 Conceptos relacionados con la MVRequisitos hardware de la MVCarga dinámicaPaginadoresHiperpaginación

3 Algoritmos de gestión de la MVAlgoritmos de gestión de memoriaPolíticas de asignaciónPolíticas de ubicaciónPolíticas de búsqueda o de lecturaPolíticas de reemplazo

4 Casos de estudioMach 3.0WindowsLinux





¿Qué es la MV?

Es un esquema de gestión de memoria en el que los procesos:Se ejecutan sin estar completamente cargados en memoriaprincipal (MP)Pueden tener mayor tamaño que la MP disponible

Permite un desacoplamiento entre el espacio de direccionesfísicas y el espacio de direcciones virtualUtiliza el almacenamiento secundario como extensión de laMPBasada en el principio de localidad de las referencias ⇒ Sólose mantiene en MP la información necesaria en cada momentoEl control lo realiza el sistema operativo (SO) con la ayudaimprescindible del hardware


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado




Ventajas de la MV

1 Transparencia en las transferencias, dispositivo dealmacenamiento ⇔ MP

2 El tamaño de los procesos depende del espacio dedireccionamiento virtual y del disco duro

3 Se mejora el rendimiento del sistema ⇒ se incrementa elgrado de multiprogramación

4 Reduce la E/S ⇒ sólo se cargan en MP las partes necesariasde un programa


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado



Requisitos hardware de la MVCarga dinámicaPaginadoresHiperpaginación

Requisitos hardware de la MV

Se utilizan mecanismos de paginación y segmentaciónVentaja de la paginación:

Transferencias más simples con bloques de tamaño fijoDisco ⇔ MP

Hardware de paginación:Unidad de gestión de la tabla del mapa de páginasBits en los descriptores de páginas de: presencia, modificación(dirty bit) y referenciaAlmacenamiento auxiliar para las páginas del procesoSoporte para interrumpir instrucciones


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado




Requisitos hardware de la MV





Carga dinámica

Transferencia de páginas de dispositivo de almacenamiento aMPSi la página referenciada no está disponible en MP ⇒ Fallo depágina (FP)

La tasa de fallos de página disminuye al aumentar el númerode marcos

Los tiempos que más afectan a la carga dinámica son:Cambios de contextoGuardar una página modificada en disco (page out)Cargar una página referenciada en MP (page in)

Mientras se realiza, el proceso está bloqueado


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado




Carga dinámica





Paginadores

Parte del SO que mueve páginas entre disco y MPRutinas para hacer la transferencia cuando se produce un FPSe crean y destruyen con el objeto proyectado en MVTipos de paginadores

De archivosP.ej.: mmap, exec

De objetos anónimos o swap pagerAquellos que no tienen una imagen en el sistema de archivos

Gestión del área de swap(área de memoria persistente para los objetos anónimos)

De dispositivosP.ej.: gestión del frame bufferSe proyecta la zona de memoria utilizada por el dispositivo (noen el disco)


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado




Hiperpaginación, vapuleo o thrashing

Caída de rendimiento al aumentar el grado demultiprogramaciónCuando los procesos intercambian páginas disco ⇔ MP

Soluciones:Reducir grado de multiprogramaciónUtilizar un algoritmo de reemplazo localSuministrar a cada proceso el número de marcos que necesite

Modelo del conjunto de trabajoFrecuencia de fallos de página


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado




Soluciones a la hiperpaginación

Modelo del conjunto de trabajoConjunto de páginas referenciadas por el proceso durante unintervalo de tiempoBasado en principio de localidad de referenciasMantiene alto el grado de multiprogramación


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado




Soluciones a la hiperpaginación

Frecuencia de fallos de páginaSe establece un umbral superior y otro inferior, para quitar oasignar marcos de página a un proceso


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado



Algoritmos de gestión de memoriaPolíticas de asignaciónPolíticas de ubicaciónPolíticas de búsqueda o de lecturaPolíticas de reemplazo

Algoritmos de gestión de memoria (i)

Objetivo ⇒ Minimizar el porcentaje de FPs, con mínimasobrecarga y máximo aprovechamiento de la MPPolíticas de asignación¿Qué cantidad de MP se asigna a un determinado proceso?

Asignación fija y asignación variableAlcance del reemplazo: global y localGestión del espacio libre

Políticas de ubicación¿Dónde se ubica un bloque en MP?Políticas de búsqueda o lectura¿Cuándo y qué páginas se cargan en MP?

Paginación por demandaPaginación anticipada o prepaginación


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado




Algoritmos de gestión de memoria (ii)

Políticas de reemplazo¿Qué páginas deben sustituirse en MP?

Algoritmo óptimoAlgoritmo primera página en llegar/primera en salir FirstIn-First Out (FIFO)Algoritmo página menos usada recientemente - Least RecentlyUsed (LRU)Algoritmos de aproximación al LRU: reloj global, FIFO segundaoportunidad, página no usada frecuentemente - Not FrequentlyUsed(NFU)





Políticas de asignación (i)

Determinan qué cantidad de MP se asigna a un proceso segúnsus necesidadesAsignación fijaEl número de marcos se decide en la carga inicial y estádeterminado por el tipo de procesoAsignación variableEl número de marcos cambia a lo largo de la vida de unproceso

Modelo del conjunto de trabajoFrecuencia de FPs


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado




Políticas de asignación (ii)

Alcance del reemplazoGlobal: Considera todos los marcos de MP como candidatos,independientemente del proceso al que pertenezcan

Ventaja: Mejor aprovechamiento de la MPInconveniente: HiperpaginaciónEjemplo: Unix

Local: Considera los marcos del proceso que originó el FPVentaja: El número de FPs es más deterministaInconveniente: Mayor sobrecarga ⇒ Cálculo de los marcos aasignar en cada instanteEjemplos: VMS y Windows


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado




Políticas de asignación (iii)

Gestión del espacio libreEl SO mantiene el estado de los marcos libres o asignados

Mapa de bitsListas enlazadas (Windows)Sistema de colegas o buddy (Linux, Unix)


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado




Políticas de ubicación

Determinan dónde se ubica un bloque en MPSegmentación pura

Primer ajusteSiguiente ajusteMejor ajustePeor ajuste

PaginaciónCarece de importancia


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado




Políticas de búsqueda o de lectura

Determinan cuándo y qué páginas se cargan en MPPaginación por demandaSólo se carga en MP cuando se ha referenciado

VentajasEn MP sólo hay lo que se necesitaLa sobrecarga es mínima

Paginación anticipada o prepaginaciónSe cargan en MP según una predicción

VentajasSi la predicción es buena, el tiempo de ejecución de losprocesos se reduceÚtil cuando se accede secuencialmente a dispositivos dealmacenamiento


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado




Políticas de reemplazo

Deciden qué páginas deben sustituirse en MPCriterios

1 Baja sobrecarga2 Sin ajustes en máquinas con distintas configuraciones (no

tuning)3 Aproximación al LRU

Cadena de referenciasLista de referencias a páginas para evaluar la calidad de estosalgoritmosSe eliminan los accesos contiguos a la misma páginaObtención

Artificialmente, de forma pseudoaleatoriaA partir de una traza de ejecución


ÁngelNota adhesivaLRU: Least Recently Use (Menos Usado Recientemente)

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado




Políticas de reemplazoAlgoritmo óptimo

Se reemplaza la página que va a tardar más tiempo en usarseVentaja: Ofrece la tasa de fallos más baja posibleEstablece un criterio de evaluación del resto de algoritmosInconveniente: No implementable


ÁngelNota adhesiva8 páginas: de la 0 a la 7, con 3 marcos

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado




Políticas de reemplazoAlgoritmo FIFO

Se reemplaza la página que lleva más tiempo cargada en MPVentaja: Sencillo de implementarInconvenientes

Bajo rendimientoAnomalía de Belady ⇒ Incremento FPs al aumentar no marcosEjemplo: Calcular FPs en 1 2 3 4 1 2 5 1 2 3 4 5 con 3 y 4 marcos


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado




Políticas de reemplazoAlgoritmo LRU

Aproximación al algoritmo óptimo. Utiliza el pasado recientepara predecir el futuroSustituye la página menos usada en el pasadoInconvenientes

Dificultad de implementaciónAlta sobrecargaSolución: Utilizar algoritmos de aproximación al LRU


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado





Algoritmos de aproximación al LRU - Reloj globalSe crea una lista circular y se emplea un bit R asociado a cadapágina

1 Mientras la lista no esté llena, cargar páginas con bit dereferencia (R) igual a 0

2 Si se referencia una página, se pone bit R = 13 Cada cierto periodo, con un puntero giratorio poner bits R = 04 Si la lista está llena:

Si bit R = 0, reemplazar página y avanzar punteroSi bit R = 1, poner bit R = 0 y avanzar el puntero

Ejemplo: 4.3 BSD


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado





Algoritmos de aproximación al LRU - FIFO con 2a oportunidadSe emplea un bit R asociado a cada página

1 Elegir una página con criterio FIFO- Si R = 1, poner R = 0- Si R = 0, sustituir la página

2 Avanzar puntero e ir a 1Generalmente se implementa con una cola FIFO circularVentaja: Baja sobrecargaInconveniente: Puede degenerar en un FIFO si todas lapáginas tienen R = 1


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado





Algoritmos de aproximación al LRU - FIFO con 2a oportunidad


ÁngelResaltado





Algoritmos de aproximación al LRU - NFUSe controla la interrupción de un reloj y se emplea uncontador y un bit R asociado a cada página

Por cada interrupción del reloj- Si R = 1, incrementar el contador- Poner todos los bits R a 0Por cada FP, se reemplaza la página con el menor valor en elcontador

Inconveniente: Si una página se usó mucho, no se reemplazaráaunque ya no se acceda a ellaSolución: Emplear mecanismos que envejezcan los contadores.En vez de incrementarlos

Desplazar el contador 1 bit a la derechaAñadir bit de ref. en el extremo izquierdo del contador


ÁngelNota adhesivaNFU (Not Frecuent Used): No Usado Frecuentemente

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado





Algoritmos de aproximación al LRU - NFU


ÁngelResaltado



Mach 3.0WindowsLinux

Mach 3.0

Aproximación al LRU con FIFO segunda oportunidadUtiliza tres colas de páginas

Cola de páginas libres, puestas a 0. Se reemplazan cada vezque hay un FPCola de páginas activas. Mantienen el conjunto de trabajoCola de páginas inactivas. Buffer de páginas no referenciadas

El demonio pageout libera páginas, moviéndolas de la cola deactivas a la de inactivas cuando el número de páginas librescae por debajo de un umbral


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado




W2K

Mecanismo de clusteringSi hay FP, realiza paginación bajo demanda trayendo variaspáginas contiguasDepende de la cantidad de MP y tipo de objeto que produjo elFPEn sistemas de sobremesa el valor del clustering es 8 marcospara código, 4 para datos y 8 para el resto

Gestión del conjunto de trabajo (WS) ⇒ Número de páginascargadas en MP del proceso en ejecución

Asignación variable de número de marcos y alcance localAl iniciar un proceso se asigna un tamaño mínimo del WSEl tamaño de los WS varía dinámicamente entre 50 y 345páginas

Reajusta el WS de los procesos y decide qué cantidad depáginas se pueden liberarIncrementa el tamaño del WS si el proceso genera FPs


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado




W2K

Estado de los marcosErróneo - Con daños físicosLibre - Sin asignar, pero no puede asignarse hasta poner a 0sVacío - Iniciado a 0sActivo - Presente en un WS o bloqueado en memoriaTransición - Está actualizándose con información del discoReposo - Ha dejado de pertenecer a un WS, pero contieneinformación y está apuntado desde la TMPModificado - La información que contiene no se ha salvado endiscoModificado sin escritura - Es necesario esperar para actualizarsu información en disco





W2K





LinuxDireccionamiento de la memoria virtual

Tabla de páginas con tres niveles y cuatro campos: directoriode páginas, directorio intermedio, tabla de páginas ydesplazamientoCada tabla de páginas ocupa 1 páginaDiseñada para Alpha 64 bits. Se adapta a x86 (32 bits)definiendo tamaño del directorio intermedio = 1


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado




Linux

Estructuras de datos





Linux

Fallo de páginas





Linux

Asignación de páginas utilizando el sistema de colegas





Linux

Algoritmo de reemplazoAlcance del reemplazo globalLa gestión del área de intercambio se realiza con el demoniokswapd

Cada segundo comprueba el número de marcos libres y buscalos que pueden ser reemplazadosEs un algoritmo de aproximación al LRU con envejecimientoBasado en la edad de las páginas


ÁngelResaltado

ÁngelResaltado




Linux

Algoritmo de reemplazoTécnica de envejecimiento de páginas

Todas las páginas se inician con edad 3Si se accede a una página, R = 1, se incrementa en 3 la edadde la página, hasta un máximo de 20Si se ejecuta kswapd, se decrementa en 1 la edad de lapáginas que no se usan (bit R = 0)

Si una página modificada se lleva a discoSe marca como inválida la entrada en la TMPSe incluye la información para su recuperación posteriorSe libera el marco, añadiéndolo a lista de marcos libres

Las páginas no modificadas se marcan como libres y susmarcos se añaden a la lista de marcos libresSi se recuperan suficientes marcos para el proceso, el demoniodormirá de nuevoSi no, se continúa con el siguiente proceso


ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado

ÁngelResaltado




Linux

Algoritmo de reemplazo


Referencias bibliográficas

[Sánchez, 2005] S. Sánchez Prieto.Sistemas Operativos.Servicio de Publicaciones de la UA, 2005.[Stallings, 1999] W. Stallings.Organización y arquitectura de Computadores.Ed. Prentice Hall, 1999.[Silberschatz, 2006] A. Silberschatz, P. B. Galván y G. GagneFundamentos de Sistemas Operativos.McGraw Hill. 2006[Tanenbaum, 2009] A. Tanenbaum.Sistemas Operativos Modernos.Ed. Pearson Education, 2009.


Introducción a la memoria virtual (MV)¿Qué es la MV?Ventajas de la MV

Conceptos relacionados con la MVRequisitos hardware de la MVCarga dinámicaPaginadoresHiperpaginación

Algoritmos de gestión de la MVAlgoritmos de gestión de memoriaPolíticas de asignaciónPolíticas de ubicaciónPolíticas de búsqueda o de lecturaPolíticas de reemplazo

Casos de estudioMach 3.0WindowsLinux

Apéndice

memoriavirtual - academia cartagena99 · 2015. 6. 17. · listasenlazadas(windows)...

Documents