Date post: | 10-Nov-2015 |
Category: |
Documents |
Upload: | joseescobargines |
View: | 238 times |
Download: | 3 times |
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Administracin de memoria: Memoriavirtual
Gunnar Wolf
Facultad de Ingeniera, UNAMInstituto de Investigaciones Econmicas, UNAM
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
ndice
1 Concepto
2 Paginacin sobre demanda
3 Reemplazo de pginas
4 Asignacin de marcos
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Disociar por completo memoria fsica y lgica
El primer gran paso hacia la memoria virtual lo cubrimosal hablar de paginacin
Cada proceso tiene una vista lgica de su memoriaCada proceso se mapea a la memoria fsicaPero es exclusivo, distinto del de los dems procesos
Ahora cada proceso tiene un espacio de direccionamientoexclusivo y muy grande
Pero omitimos cmo es que podemos ofrecer msmemoria que la fsicamente disponible
Aqu entra en juego la memoria virtualLa memoria fsica es slo una proyeccin parcial de lamemoria lgica, potencialmente mucho mayor
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Retomando el intercambio
Vimos el intercambio en primer trmino al intercambio(swap) al hablar de memoria particionada
Espacio de memoria completo de un procesoMejora cuando hablamos de segmentacin
Intercambio parcial; segmentos no utilizados.El proceso puede continuar con porciones congeladas aalmacenamiento secundario
Con la memoria virtual, el intercambio se realiza porpgina
Mucho ms rpido que por bloques tan grandes como unsegmentoCompletamente transparente al proceso
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Esquema general empleando memoria virtual
Figura: Esquema general de la memoria, incorporando espacio enalmacenamiento secundario, representando la memoria virtual
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Pequeo cambio de nomenclatura
El intercambio (swap) deja de ser un ltimo recursoPasa a ser un elemento ms en la jerarqua de memoria
El mecanismo para intercambiar pginas al disco ya no esun mecanismo aparte
Ya no hablamos del intercambiador (swapper)Sino que del paginador
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Transparencia al proceso
Es importante recalcar que cuando hablamos de memoriavirtual, sta se mantiene transparente al procesoEl proceso puede dedicarse a cumplir su tarea, el sistemaoperativo paginar la memoria segn haga faltaEs posible hacer ciertas indicaciones de preferencia, peroen general no es el caso
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
ndice
1 Concepto
2 Paginacin sobre demanda
3 Reemplazo de pginas
4 Asignacin de marcos
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Deja dormir al cdigo durmiente
En el transcurso de la vida de un proceso, porcionesimportantes de su memoria se mantienen durmientes Cdigo que slo se emplea eventualmente
Respuesta a situaciones de excepcinExportacin de un documento a determinado formatoVerificacin de sanidad al cerrar el programaEstructuras inicializadas con espacio para permitir quecrezcan. . .
Las pginas en que estn dichos datos no son necesariasdurante la ejecucin normal
El paginador puede posponer su carga hasta cuando seannecesariasSi es que alguna vez son requeridas
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Entonces, sobre demanda?
Todo el cdigo que ejecute o referencie directamente elprocesador tiene que estar en memoria principal
Pero no tiene que estarlo antes de ser referenciadoPara ejecutar un proceso, slo requerimos cargar laporcin necesaria para comenzar la ejecucin
Podemos emplear a un paginador flojoSlo ir cargando a memoria las pginas conforme van aser utilizadasLas pginas que no sean requeridas nunca sern cargadasa memoria
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Paginador flojo?
Flojo: Concepto usado en diversas reas del cmputo
Flojo (Lazy) Busca hacer el trabajo mnimo en un principio, ydiferir para ms tarde tanto como sea posible
Ansioso (Eager) Busca realizar todo el trabajo que sea posibledesde un principio
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Cmo hacemos flojo al paginador?
Estructura de MMU muy parecida a la del TLBLa tabla de pginas incluir un bit de validez
Indica si la pgina est presente o no en memoriaSi no est presente, causa un fallo de pgina
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Respuesta a un fallo de pgina
Figura: Pasos que atraviesa la respuesta a un fallo de pginaGunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Pasos para atender a un fallo de pgina1 Verificar en PCB: Esta pgina ya fue asignada al
proceso? (es vlida?)2 Si no es vlida, se termina el proceso3 Buscar un marco disponible
P.ej. en una tabla de asignacin de marcos4 Solicita el al disco la lectura de la pgina hacia el marco
especificadoContina ejecutando otros procesos
5 Cuando finaliza la lectura, actualiza PCB y TLB paraindicar que la tabla est en memoria
6 Termina la suspensin del proceso.Contina con la instruccin que desencaden el fallo.El proceso contina como si la pgina siempre hubieraestado en memoria
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Paginacin puramente sobre demanda
Llevar este proceso al extremo: Sistema de paginacinpuramente sobre demanda (Pure demand paging)
Al iniciar la ejecucin de un proceso, lo hace sin ningunapgina en memoria
El registro de siguiente instruccin apunta a unadireccin que no ha sido cargada
De inmediato se produce un fallo de pginaEl sistema operativo responde cargando esta primerpgina
Conforme avanza el flujo del programa, el proceso vaocupando el espacio real que emplear
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Efecto de la paginacin sobre demanda
Al no cargarse todo el espacio de un proceso, puedeiniciar su ejecucin ms rpidoAl no requerir tener en la memoria fsica a los procesoscompletos, puede haber ms procesos en memoria de losque cabran antes
Aumentando el grado de multiprogramacin
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Midiendo el impacto en la ejecucin
El impacto en la ejecucin de un proceso puede ser muygrandeUn acceso a disco es varios miles de veces ms lento queun acceso a memoriaPodemos calcular el tiempo de acceso efectivo (te) apartir de la probabilidad de que en un proceso se presenteun fallo de pgina (0 p 1)Conociendo el tiempo de acceso a memoria (ta) y eltiempo que toma atender a un fallo de pgina (tf ):
te = (1 p)ta + ptf
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Resolviendo con valores actuales
ta ronda entre los 10 y 200nstf est cerca de los 8ms
Latencia del disco duro: 3msTiempo de posicionamiento de cabeza: 5msTiempo de transferencia: 0.05ms
Si slo uno de cada mil accesos a memoria ocasiona unfallo (p = 11000):
te = (1 11000) 200ns + 11000 8, 000, 000nste = 199,8ns + 8000ns = 8199,8ns
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Ahora s: El impacto de la paginacin sobredemanda
Esto es, el tiempo efectivo de acceso a memoria es 40veces ms lento que si no empleramos paginacin sobredemandaPodramos mantener la penalizacin por degradacin pordebajo del 10% del tiempo originalPero para que te 220, tendramos que reducir ap 1399,990No olviden: No (necesariamente) es tiempo muerto
Multiprogramacin: Mientras un proceso espera a que seresuelva su fallo de pgina, otros pueden continuarejecutando
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Ahora s: El impacto de la paginacin sobredemanda
Esto es, el tiempo efectivo de acceso a memoria es 40veces ms lento que si no empleramos paginacin sobredemandaPodramos mantener la penalizacin por degradacin pordebajo del 10% del tiempo originalPero para que te 220, tendramos que reducir ap 1399,990No olviden: No (necesariamente) es tiempo muerto
Multiprogramacin: Mientras un proceso espera a que seresuelva su fallo de pgina, otros pueden continuarejecutando
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Acomodo de las pginas en disco
El clculo presentado asume que el acomodo de laspginas en disco es ptimoSi hay que agregar el espacio que una pgina ocupa en unsistema de archivos, tf fcilmente aumenta
Navegar estructuras de directorioPosible fragmentacin en espacio de archivos lamemoria va quedando esparcida por todo el discoMayores movimientos de la cabeza lectoraProblema prevalente en los sistemas tipo Windows
Respuesta: Particin de intercambio, dedicada 100% a lapaginacin
Mecanismo empleado por casi todos los sistemas Unix
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
ndice
1 Concepto
2 Paginacin sobre demanda
3 Reemplazo de pginas
4 Asignacin de marcos
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Manteniendo el sobre-compromiso
Cuando sobre-comprometemos memoria, los procesos enejecucin pueden terminar requiriendo que se carguenms pginas de las que caben en la memoria fsicaMantenemos el objetivo del sistema operativo: Otorgar alos usuarios la ilusin de una computadora dedicada a susprocesosNo sera aceptable terminar la ejecucin de un proceso yaaceptado
Mucho menos si ya fueron aprobados sus requisitos y nosquedamos sin recurso
Tenemos que llevar a cabo un reemplazo de pginas
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Importancia del reemplazo de pginas
Parte fundamental de la paginacin sobre demandaLa pieza que posibilita una verdadera separacin entrememoria lgica y fsicaMecanismo que permite liberar alguno de los marcosactualmente ocupado
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Mecanismo para liberar un marco ocupado
Cuando todos los marcos estn ocupados (o se cruza elumbral determinado), un algoritmo designa a una pginavctima para su liberacin
Veremos ms adelante algunos algoritmos para estoEl paginador graba a disco los contenidos de esta pginay la marca como libre
Actualizando el PCB y TLB del proceso al cual pertenece
Puede continuar la carga de la pgina requeridaOjo! Esto significa que se duplica el tiempo detransferencia en caso de fallo de pgina (tf )
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Manteniendo a tf en su lugar
Con apoyo del MMU podemos reducir la probabilidad deesta duplicacin en tfAgregamos un bit de modificacin o bit de pgina sucia ala tabla de pginas
Apagado cuando la pgina se carga a memoriaSe enciende cuando se realiza un acceso de escritura aesta pgina
Al elegir una pgina vctima, si su bit de pgina sucia estencendido, es necesario grabarla a disco
Pero si est apagado, basta actualizar las tablas delproceso afectadoAhorra la mitad del tiempo de transferencia
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Cmo elegir una pgina vctima?
Para elegir una vctima para paginarla al disco empleamosun algoritmo de reemplazo de pginasBuscamos una caracterstica: Para un patrn de accesosdado, obtener el menor nmero de fallos de pgina
Diferentes patrones de acceso generan diferentesresultados para cada algoritmoNos referiremos a estos patrones de acceso como cadenade referencia
Para los ejemplos presentados a continuacin, nos basaremosen los presentados en Operating Systems Concepts Essentials
(Silberschatz, Galvin y Gagn, 2011)
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Eligiendo una cadena de referencia
La cadena de referencia debe representar un patrn tpico(para la carga que deseemos analizar) de accesos amemoriaMuchas veces son tomados de un volcado/trazado deejecucin en un sistema real
El conjunto resultante puede ser enormeSimplificacin: No nos interesa el acceso independiente acada direccin de memoria, sino que a cada pginaVarios accesos consecutivos a la misma pgina no tienenefecto en el anlisis
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Y el reemplazo. . . en dnde?
Requerimos de un segundo parmetroPara analizar un algoritmo con una cadena de referencia,tenemos que saber cuntos marcos tiene nuestracomputadora hipottica
Lo que buscamos es la cantidad de fallos de pginaDepende directamente de los marcos disponiblesY del tamao (en pginas de memoria) de nuestroproceso
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Casos lmite respecto a los marcos disponibles
Por ejemplo, a partir de la cadena de referencia:1, 4, 3, 4, 1, 2, 4, 2, 1, 3, 1, 4
En una computadora con 4 marcos, slo se producirancuatro fallos
Los necesarios para la carga inicialExtremo opuesto: Con un slo marco, tendramos 12fallos
Cada pgina tendra que cargarse siempre desde disco
Casos que se pueden estudiar: 2 o 3 marcos
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Datos base para los algoritmos
A continuacin veremos varios algoritmos de reemplazode pginasPara el anlisis, asumiremos una memoria con 3 marcosY la siguiente cadena de referencia:
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Primero en entrar, primero en salir (FIFO) (1)
Nuevamente, el algoritmo ms simple y de obviaimplementacinAl cargar una pgina, se toma nota de cundo fue cargadaCuando llegue el momento de reemplazar una pginavieja, se elige la que se haya cargado hace ms tiempo
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Primero en entrar, primero en salir (FIFO) (2)
Figura: Algoritmo FIFO de reemplazo de pginas: 15 fallos
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Primero en entrar, primero en salir (FIFO) (3)
Tpicamente programado empleando una lista ligadacircular
Cada elemento que va recibiendo se agrega como elltimo elementoTras agregarlo, se empuja al apuntador para convertirloen la cabeza
Desventaja: No toma en cuenta la historia de las ltimassolicitudes
La cantidad de patrones de uso que le pueden causar unbajo desempeo es altoTodas las pginas tienen la misma probabilidad de serreemplazadas, independientemente de su frecuencia deuso
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Anomala de Belady
En general, asumimos que a mayor cantidad de marcos dememoria disponibles, menos fallos de pgina se van apresentarLa Anomala de Belady ocurre cuando un incremento enel nmero de marcos disponibles lleva a ms fallos depgina
Depende del algoritmo y de la secuencia de la cadena dereferencia
FIFO es vulnerable a la anomala de Belady
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Anomala de Belady: Expectativas decomportamiento
Figura: Relacin ideal entre el nmero de marcos y la cantidad defallos de pgina
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Anomala de Belady: Comportamiento de FIFO
Figura: El algoritmo FIFO presenta la anomala de Belady con lacadena de referencia 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Algoritmo ptimo (OPT) o mnimo (MIN) (1)
Interes casi puramente tricoElegimos como pgina vctima a aquella que no vaya a serutilizada por un tiempo mximo
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Algoritmo ptimo (OPT) o mnimo (MIN) (2)
Figura: Algoritmo ptimo de reemplazo de pginas (OPT): 9 fallos
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Algoritmo ptimo (OPT) o mnimo (MIN) (3)
ptimo demostrado, pero no aplicableRequiere conocimiento a priori de las necesidades delsistema
Si es de por s impracticable en los despachadores, lo esmucho mas al hablar de un rea tan dinmica como lamemoriaRecuerden: Millones de accesos por segundo
Principal utilidad: Brinda una cota mnimaPodemos ver qu tan cercano resulta otro algoritmorespecto al caso ptimo
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Menos recientemente utilizado (LRU) (1)
Lo hemos mencionado ya en varios puntos de laadministracin de memoriaBusca acercarse a OPT prediciendo cundo ser elprximo uso de cada una de las pginas
Basado en su historia reciente
Elige la pgina que no ha sido empleada desde hace mstiempo
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Menos recientemente utilizado (LRU) (2)
Figura: Algoritmo reemplazo de pginas menos recientementeutilizadas (LRU): 12 fallos
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Menos recientemente utilizado (LRU) (3)
Para nuestra cadena de referencia, resulta en el puntomedio entre OPT y FIFOPara una cadena S y su cadena espejo RS ,OPT (S) = LRU(RS) (y viceversa)Est demostrado que LRU y OPT estn libres de laanomala de Belady
Para n marcos, las pginas que estn en memoria son unsubconjunto estricto de las que estaran con n + 1marcos.
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Implementacin ejemplo de LRU (1)
Se agrega un contador a cada uno de los marcosEl contador se incrementa siempre que se hace referenciaa una pgina
Se elige como vctima a la pgina con el contrador msbajo
Esto es, a la que hace ms tiempo no haya sidoactualizada
Desventaja: Con muchas pginas, se tiene que recorrer lalista completa para encontrar la ms envejecida
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Implementacin ejemplo de LRU (2)
La lista de marcos es una lista doblemente ligadaEsta lista es tratada como una lista y como un stack
Cuando se hace referencia a una pgina, se mueve a lacabeza (arriba) del stack Peor caso: 6 operacionesPara elegir a una pgina vctima, se toma la de abajo delstack (tiempo constante)
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Ms / menos frecuentemente utilizado (MFU /LFU) (1)
Dos algoritmos contrapuestos, basados (como LRU) enmantener un contador
Miden la cantidad de referencias que se han hecho acada pgina
Lgica base:MFU Si una pgina fue empleada muchas veces,
probablemente va a ser empleada muchasveces ms
LFU Si una pgina casi no ha sido empleada,probablemente recin fue cargada, y serempleada en el futuro cercano
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Ms / menos frecuentemente utilizado (MFU /LFU) (2)
La complejidad de estos algoritmos es tan alta comoLRU, y su rendimiento es menos cercano a OPT
Casi no son empleados
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Aproximaciones a LRU
Principal debilidad de LRU? Su implementacin requiereapoyo en hardware mucho ms complejo que FIFOHay varios mecanismos que buscan aproximar elcomportamiento de LRU
Empleando informacin menos detallada
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Bit de referencia
Aproximacin bastante comnTodas las entradas de la tabla de pginas tienen un bit dereferencia, inicialmente apagado
Cada vez que se referencia a un marco, se enciende su bitde referenciaEl sistema reinicia peridicamente a todos los bits dereferencia, apagndolos
Al presentarse un fallo de pgina, se elige por FIFO deentre el subconjunto con el bit apagado
Esto es, entre las pginas que no fueron empleadas en elperiodo
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Bits adicionales (columna) de referencia
Mecanismo derivado del anterior, dando ms granularidadSe maneja una columna de referencia, de varios bits deancho
Peridicamente, en vez de reiniciar a 0, el valor de todaslas entradas se recorre a la derecha, descartando el bitms bajoEl acceso a un marco hace que se encienda su bit msalto
Ante un fallo de pgina, se elige entre los marcos convalor de referencia ms bajo
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Segunda oportunidad (o reloj)
Maneja un bit de referencia y un recorrido tipo FIFOEl algoritmo avanza linealmente sobre la lista ligadacircularHay eventos que encienden el bit, y eventos que loapagan:
Una referencia a un marco enciende su bit de referenciaSi elige a un marco que tiene encendido el bit dereferencia, lo apaga y avanza una posicin (dndole unasegunda oportunidad)Si elige a un marco que tiene apagado el bit dereferencia, lo designa como pgina vctima
Se le llama de reloj porque puede verse como unamanecilla que avanza sobre la lista de marcos
Hasta encontrar uno con el bit de referencia apagadoGunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Segunda oportunidad mejorada (1)
Si agregamos al bit de referencia un bit de modificacin,nos mayor expresividad, y puede ayudar a elegir a unapgina vctima ms barata. En rden de preferencia:
(0,0) El marco no ha sido utilizado ni modificado.Buen candidato.
(0,1) Sin uso reciente, pero est sucio. Hay queescribirlo a disco.
(1,0) Est limpio, pero tiene uso reciente, y esprobable que se vuelva a usar pronto
(1,1) Empleado recientemente y sucio. Habra quegrabarlo a disco, y tal vez vuelva a requerirsepronto. Hay que evitar reemplazarlo.
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Segunda oportunidad mejorada (2)
Emplea una lgica como la de segunda oportunidad, peroconsiderando el costo de E/SPuede requerir dar hasta cuatro vueltas para elegir a lapgina vctima
Aunque cada vuelta es ms corta
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Algoritmos con manejo de buffers
De uso cada vez ms frecuenteNo esperan a que el sistema requiera reemplazar unmarco, buscan siempre tener espacio disponible
Algoritmos ansiosos, no flojosOperan basados en umbrales aceptables/deseables
Conforme la carga lo permite, el SO busca las pginassucias ms proclives a ser paginadas
Va copindolas a disco y marcndolas como limpias
Cuando tenga que traer una pgina de disco, siemprehabr dnde ubicarla sin tener que hacer una transferencia
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Ejemplo: Tres sistemas Linux (1)
Figura: Manejo de memoria (24 horas) en un sistema embebido(16MB RAM)
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Ejemplo: Tres sistemas Linux (2)
Figura: Manejo de memoria (24 horas) en un servidor medio (8GBRAM)
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Ejemplo: Tres sistemas Linux (3)
Figura: Manejo de memoria (24 horas) en un servidor grande(32GB RAM)
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
ndice
1 Concepto
2 Paginacin sobre demanda
3 Reemplazo de pginas
4 Asignacin de marcos
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Viendo el lado opuesto del problema
Vimos ya cmo retirar marcos asignadosCmo conviene asignar los marcos a los procesos?Definamos algunos parmetros para nuestros ejemplos
Un sistema con 1024KB de memoria fsica256 pginas de 4KB cada unaEl sistema operativo ocupa 248KB (62 pginas); 194pginas para los procesos a ejecutar
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Vuelta a la paginacin puramente sobre demanda
En un esquema de paginacin puramente sobre demanda,cada fallo de pgina que se va generando lleva a que seasigne el marco correspondienteSe van asignando los marcos conforme son requeridos,hasta que hay 194 pginas ocupadas por procesos
Entonces, entran en escena los algoritmos de reemplazode pginas que ya vimosClaro est, cuando un proceso termina, sus marcosvuelven a la lista de marcos libres
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Puramente sobre demanda: Demasiado flojo
El esquema de paginacin puramente sobre demandapuede resultar demasiado flojoSer un poco ms ansioso asegurara un mejor rendimientoConviene determinar un mnimo utilizable de marcos
Si asignamos por debajo del mnimo, sufre el rendimiento
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Mnimo de marcos: Arquitectura ydireccionamiento
Hasta ahora hemos simplificado asumiendo que cadainstruccin puede generar slo un fallo de pginaIndependientemente de la arquitectura, cada instruccinpuede desencadenar varias solicitudes
Una solicitud, la lectura de la siguiente direccin aejecutar (recuerden: von Neumann!)Otra, la direccin de memoria referidaPor ejemplo, si el flujo brinca a 0x00A2C8, y estainstruccin es load 0x043F00, para satisfacerlarequerimos dos pginas: 0x00A y 0x043 Requerimos un mnimo de dos pginas
Pero. . . Y las referencias indirectas?Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Mnimo de marcos: Referencias indirectas
Casi todas las arquitecturas permiten hacer referenciasindirectas a memoriaUna instruccin de acceso a memoria (load, store)especifica una direccin de memoriaY esta direccin guarda la ubicacin de memoriaPor ejemplo, 0x043F00 indica la carga de 0x010F80
Satisfacer al load 0x043F00 requerir entoncestres pginas: 0x00A, 0x043 y 0x010
. . . Y algunas arquitecturas (principalmente antiguas)permitan niveles ilimitados de indireccin
Por ejemplo, por medio de un bit de indireccinEn dado caso, es imposible asegurar un lmite mximo Es comn que el MMU haga un conteo de referenciaspara evitar caer en un ciclo sin fin
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Instrucciones con operandos en memoria
Las arquitecturas RISC introdujeron requisitos deregularidad que incluyen el que la aritmtica opereexclusivamente sobre los registros del procesadorLas arquitecturas ms antiguas permiten que losoperandos y resultado sean direcciones de memoria
Antiguas? De antes de que la diferencia de velocidadentre CPU y memoria fueran tantaRecordemos que la principal arquitectura actual tieneherencia desde 1970. . .Si en un x86, en 0x00AC28 tenemos ADD [edx],[ecx], en EDX el valor 0x010F80 y en ECX el valor0x043F00,
En el acumulador EAX obtendremos la suma delcontenido de los dos operadores Tres referencias a memoria en una sola instruccin
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
El nivel deseable de marcos
Con estos lineamientos determinamos ya un mnimoabsoluto
Muy bajo, ponindolo en el contexto de los sistemasactuales
Cmo puede el sistema determinar un nivel deseable demarcos por proceso?
Depende siempre del estado actual del sistemaPodramos intentar satisfacer los requisitos totales de unode los procesos
A menor cantidad de fallos de pgina, mayor rendimientoPero si reducimos el grado de multiprogramacin,reducimos el uso efectivo del procesador
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Asignacin igualitaria
Buscando un reparto justo de recursos, se divide el totalde memoria fsica disponible entre el nmero de procesosVolviendo a nuestra computadora ejemplo (256 marcos;62 marcos asignados al sistema, 194 a los procesos):
Si tenemos 4 procesos en ejecucin, dos tendrn derechoa 49 marcos y dos a 48Los marcos no pueden dividirse; es imposible asignar 48.5a cada uno
El esquema es justo, pero deficienteSi tenemos un gestor de bases de datos P1 con 2048KB(512 marcos) de memoria virtual, y un proceso deusuario P2 que slo requiere 112KB (28 pginas). . .Ambos recibirn lo mismo Y P2 desperdiciar 20pginas
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Asignacin igualitaria
Buscando un reparto justo de recursos, se divide el totalde memoria fsica disponible entre el nmero de procesosVolviendo a nuestra computadora ejemplo (256 marcos;62 marcos asignados al sistema, 194 a los procesos):
Si tenemos 4 procesos en ejecucin, dos tendrn derechoa 49 marcos y dos a 48Los marcos no pueden dividirse; es imposible asignar 48.5a cada uno
El esquema es justo, pero deficienteSi tenemos un gestor de bases de datos P1 con 2048KB(512 marcos) de memoria virtual, y un proceso deusuario P2 que slo requiere 112KB (28 pginas). . .Ambos recibirn lo mismo Y P2 desperdiciar 20pginas
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Asignacin proporcional
Brinda a cada proceso una porcin del espacio dememoria fsica proporcional a su uso de memoria virtualSi adems de los dos procesos descritos tenemos a P3 con560KB (140 pginas) y P4 con 320KB (80 pginas) dememoria virtual
Uso total de memoria virtual:VT = 512+ 28+ 140+ 80 = 760 pginas
Sobreuso de memoria fsica cercano al 4:1 respecto a las194 pginas disponibles
Cada proceso recibir FP = VPVTmFP : Espacio de memoria fsica que recibirVP : Cantidad de memoria virtual que emplea,m: Total de marcos de memoria fsica disponibles
P1: 130 marcos; P2: 7 marcos; P3: 35 marcos; P4: 20marcos
Proporcional a su uso de memoria virtual.Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Modulando la asignacin proporcional
Mnimos: El esquema debe cuidar nunca asignar pordebajo del mnimo de la arquitectura
Si P2 ocupara slo 10 marcos de memoria fsica, en unaarquitectura x86 no deberan asignrsele menos de 3marcos
Desbalance por procesos obesosSi P1 crece al doble de su tamao virtual, hay que cuidartener umbrales mximos para no castigar de ms a losdems procesos del sistema
Manejo de prioridades?Si el sistema maneja prioridades, podran incluirseponderadas, otorgando proporcionalmente ms marcos alos procesos con mayor prioridad
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Sufrimiento ante la entrada de nuevos procesos
El esquema de asignacin proporcional sufre cuando sonadmitidos nuevos procesos, cambia el tamao en memoriavirtual de alguno de los existentes o (aunque menos)finalizan los que estn en ejecucinDeben recalcularse los totales, y probablemente reducir degolpe el espacio asignado a los procesos existentes
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Desperdicio de recursos
El patrn de uso de memoria fsica de un proceso nonecesariamente guarda correspondencia con su tamao enmemoria virtualPueden emplear mucho menores requisitos endeterminadas secciones de su ejecucinRecordar este punto Conjunto activo
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
mbitos del algoritmo de reemplazo de pginas
Respondiendo a los problemas que abre la seccin anterior,podemos discutir el mbito en el que operar nuestro
algoritmo de reemplazo de pginas
Reemplazo localReemplazo globalReemplazo global con prioridad
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Reemplazo local
Mantenemos tan estable como sea posible el clculo demarcos de memoria por proceso
Cuando se presente un fallo de pgina, slo se consideranaquellas pertenecientes al mismo proceso
El proceso tiene asignado un espacio de memoria fsicaLo mantendr mientras el sistema operativo no tomealguna decisin para modificarlo
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Reemplazo global
Los algoritmos de asignacin determinan el espacioasignado /al momento de su inicializacin
Pueden influir en los algoritmos de reemplazoP.ej. dando mayor peso a los marcos de un proceso queexcede su asignacin para ser elegidas como vctima. . . O pueden operar bajo un esquema laissez-faire,buscando que el sistema se auto-regule basado en lasnecesidades reales momento a momento
Operan sobre el espacio completo de memoriaLa asignacin fsica a cada proceso puede variar segn elestado del sistema, momento a momento
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Reemplazo global con prioridad
Esquema mixtoPermite que un proceso sobrepase su lmite
Pero slo siempre que le robe espacio en memoria fsicaslo a procesos de prioridad inferior a l
Consistente con el comportamiento de los algoritmosplanificadores
Siempre da preferencia a un proceso de mayor prioridadpor sobre los de menor prioridad
Puede tambin operar bajo concesiones temporales,buscando equilibrar posteriormente
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Comparando los mbitos de reemplazo
Reemplazo local Ms rgido; no permite aprovechar lasmenores demandas de unos procesos parafavorecer a los que tienen mayores demandas enun momento dado
Reemplazo global (ambos) Puede llevar a rendimientoinconsistente fuera del control de cada uno de losprocesos
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Y el tiempo real?
Cuando presentamos al tiempo real (Planificacin deprocesos), mencionamos que el tiempo real duro esincompatible con sistemas basados en memoria virtualPrincipal razn: Las demoras inducidas por la paginacinPodra indicarse que un proceso de tiempo real est 100%en memoria fsica (nunca candidato para paginacin)Reduce fuertemente el impacto que sufrira al pelear porrecursos
Pero no lo resuelve por completoNi la contencin en el bus, ni la inversin deprioridades. . . Slo podemos prometer tiempo real suave
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Hiperpaginacin: Definicin
Uno o ms procesos tienen demasiadas pocas pginasasignadas para llevar a cabo su trabajoGeneran fallos de pagina con tal frecuencia que resultaimposible realizar trabajo real
O resulta tan lento que la percepcin es de no-avance
El sistema pasa ms tiempo intentando satisfacer lapaginacin que trabajando
Estamos en estado de hiperpaginacinEn ingls, thrashing (literal: paliza)
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Qu puede llevar a la hiperpaginacin? (1)
El sistema tiene una carga normalEsquema de reemplazo global de marcosSe lanza un nuevo proceso
Su inicializacin requiere poblar estructuras a lo largo desu memoria virtualO cambia de conjunto activoSerie de fallos de pgina El sistema responde,reemplazando a varios marcos de otros procesos
Mientras esto contina operando, algunos de los procesosvctima requieren de las pginas que pasaron a disco
Recordemos que el disco es miles a millones de veces mslento que la memoria. . .
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Qu puede llevar a la hiperpaginacin? (2)
La utilizacin del procesador decrece. . . Porque los procesos estn esperando a que sumemoria est disponible
El sistema operativo aprovecha la situacin para lanzarprocesos de mantenimiento
Que requieren que se les asigne memoria Reducen an ms el espacio de memoria fsicadisponible
Se forma una cola de solicitudes de paginacin (algunasveces contradictorias)Baja todava ms la actividad del procesador (NOOP)
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Cmo se ve la hiperpaginacin?
Figura: Al aumentar demasiado el grado de multiprogramacin, eluso del CPU cae abruptamente y caemos en la hiperpaginacin(Silberschatz, p.349)
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
Respondiendo a la hiperpaginacin
Los sntomas son muy clarosFciles de detectar pregntenle a cualquier usuario!
Reducir temporalmente el nivel de multiprogramacinCamos en hiperpaginacin por tener requisitos enmemoria que no alcanzamos a satisfacer con la memoriafsica disponibleEl sistema puede seleccionar a uno (o ms) procesos ysuspenderlos por completoIncluso poner su memoria fsica a disposicin de otrosprocesosHasta que salgamos del estado de hiperpaginacin
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
A cul proceso castigar?
Al de menor prioridadAl que est causando ms fallosAl que est ocupando ms memoria. . .
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
El conjunto activo
El conjunto activo es una clara aproximacin a lalocalidad de referenciaEl conjunto de pginas con que un proceso esttrabajando en un momento dado
Qu significa un momento dado?
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
El conjunto activo
Figura: Los picos y valles en la cantidad de fallos de pgina de unproceso definen a su conjunto activo (Silberschatz, p.349)
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demanda
Reemplazo de pginasAsignacin de marcos
El conjunto activo y el espacio en memoria
Idealmente, en todo momento, debemos asignar a cadaproceso suficientes pginas para mantener en memoriafsica su conjunto activoSi no es posible hacerlo, el proceso es buen candidatopara ser suspendido. . . Pero no es fcil detectar con claridad cul es elconjunto activo
Mucho menos predecir cul ser dentro de determinadotiempoCunto dura un proceso dentro de determinada rutina?Puede requerir rastrear y verificar decenas de miles deaccesos a memoria
Gunnar Wolf Administracin de memoria: Memoria virtual
ConceptoPaginacin sobre demandaReemplazo de pginasAsignacin de marcos