Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Administración de memoria: Memoriavirtual
Gunnar Wolf
Facultad de Ingeniería, UNAM
2013-04-08 — 2013-04-15
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Índice
1 Concepto
2 Paginación sobre demanda
3 Reemplazo de páginas
4 Asignación de marcos
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Disociar por completo memoria física y lógica
El primer gran paso hacia la memoria virtual lo cubrimosal hablar de paginación
Cada proceso tiene una vista lógica de su memoriaCada proceso se mapea a la memoria físicaPero es exclusivo, distinto del de los demás procesos
Ahora cada proceso tiene un espacio de direccionamientoexclusivo y muy grande
Pero omitimos cómo es que podemos ofrecer másmemoria que la físicamente disponible
Aquí entra en juego la memoria virtualLa memoria física es sólo una proyección parcial de lamemoria lógica, potencialmente mucho mayor
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Retomando el intercambio
Vimos el intercambio en primer término al intercambio(swap) al hablar de memoria particionada
Espacio de memoria completo de un procesoMejora cuando hablamos de segmentación
Intercambio parcial; segmentos no utilizados.El proceso puede continuar con porciones congeladas aalmacenamiento secundario
Con la memoria virtual, el intercambio se realiza porpágina
Mucho más rápido que por bloques tan grandes como unsegmentoCompletamente transparente al proceso
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Esquema general empleando memoria virtual
Figura: Esquema general de la memoria, incorporando espacio enalmacenamiento secundario, representando la memoria virtual
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Pequeño cambio de nomenclatura
El intercambio (swap) deja de ser un último recursoPasa a ser un elemento más en la jerarquía de memoria
El mecanismo para intercambiar páginas al disco ya no esun mecanismo aparte
Ya no hablamos del intercambiador (swapper)Sino que del paginador
Concepto Paginación sobre demanda Reemplazo de páginas Asignación 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 según haga faltaEs posible hacer ciertas indicaciones de preferencia, peroen general no es el caso
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Índice
1 Concepto
2 Paginación sobre demanda
3 Reemplazo de páginas
4 Asignación de marcos
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Deja dormir al código durmiente
En el transcurso de la vida de un proceso, porcionesimportantes de su memoria se mantienen durmientes —Código que sólo se emplea eventualmente
Respuesta a situaciones de excepciónExportación de un documento a determinado formatoVerificación de sanidad al cerrar el programaEstructuras inicializadas con espacio para permitir quecrezcan. . .
Las páginas en que están dichos datos no son necesariasdurante la ejecución normal
El paginador puede posponer su carga hasta cuando seannecesariasSi es que alguna vez lo son
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Entonces, ¿sobre demanda?
Todo el código que ejecute o referencie directamente elprocesador tiene que estar en memoria principal
Pero no tiene que estarlo antes de ser referenciadoPara ejecutar un proceso, sólo requerimos cargar laporción necesaria para comenzar la ejecución
Podemos emplear a un paginador flojoSólo ir cargando a memoria las páginas conforme van aser utilizadasLas páginas que no sean requeridas nunca serán cargadasa memoria
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
¿Paginador flojo?
Flojo: Concepto usado en diversas áreas del cómputo
Flojo (Lazy) Busca hacer el trabajo mínimo en un principio, ydiferir para más tarde tanto como sea posible
Ansioso (Eager) Busca realizar todo el trabajo que sea posibledesde un principio
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
¿Cómo hacemos flojo al paginador?
Estructura de MMU muy parecida a la del TLBLa tabla de páginas incluirá un bit de validez
Indica si la página está presente o no en memoriaSi no está presente, causa un fallo de página
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Respuesta a un fallo de página
Figura: Pasos que atraviesa la respuesta a un fallo de página
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Pasos para atender a un fallo de página
1 Verificar en PCB: ¿Esta página ya fue asignada alproceso? (¿es válida?)
2 Si no es válida, se termina el proceso3 Buscar un marco disponible
P.ej. en una tabla de asignación de marcos4 Solicita el al disco la lectura de la página hacia el marco
especificadoContinúa ejecutando otros procesos
5 Cuando finaliza la lectura, actualiza PCB y TLB paraindicar que la tabla está en memoria
6 Termina la suspensión del proceso.Continúa con la instrucción que desencadenó el fallo.El proceso continúa como si la página siempre hubieraestado en memoria
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Paginación puramente sobre demanda
Llevar este proceso al extremo: Sistema de paginaciónpuramente sobre demanda (Pure demand paging)
Al iniciar la ejecución de un proceso, lo hace sin ningunapágina en memoria
El registro de siguiente instrucción apunta a unadirección que no ha sido cargada
De inmediato se produce un fallo de páginaEl sistema operativo responde cargando esta primerpágina
Conforme avanza el flujo del programa, el proceso vaocupando el espacio real que empleará
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Efecto de la paginación sobre demanda
Al no cargarse todo el espacio de un proceso, puedeiniciar su ejecución más rápidoAl no requerir tener en la memoria física a los procesoscompletos, puede haber más procesos en memoria de losque cabrían antes
Aumentando el grado de multiprogramación
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Midiendo el impacto en la ejecución
El impacto en la ejecución de un proceso puede ser muygrandeUn acceso a disco es varios miles de veces más 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 página (0 ≤ p ≤ 1)Conociendo el tiempo de acceso a memoria (ta) y eltiempo que toma atender a un fallo de página (tf ):
te = (1− p)ta + ptf
Concepto Paginación sobre demanda Reemplazo de páginas Asignación 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 sólo uno de cada mil accesos a memoria ocasiona unfallo (p = 1
1000):
te = (1− 11000)× 200ns + 1
1000 × 8, 000, 000nste = 199,8ns + 8000ns = 8199,8ns
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Ahora sí: El impacto de la paginación sobredemanda
Esto es, el tiempo efectivo de acceso a memoria es 40veces más lento que si no empleáramos paginación sobredemandaPodríamos mantener la penalización por degradación pordebajo del 10% del tiempo originalPero para que te ≤ 220, tendríamos que reducir ap ≤ 1
399,990
No olviden: No (necesariamente) es tiempo muertoMultiprogramación: Mientras un proceso espera a que seresuelva su fallo de página, otros pueden continuarejecutando
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Ahora sí: El impacto de la paginación sobredemanda
Esto es, el tiempo efectivo de acceso a memoria es 40veces más lento que si no empleáramos paginación sobredemandaPodríamos mantener la penalización por degradación pordebajo del 10% del tiempo originalPero para que te ≤ 220, tendríamos que reducir ap ≤ 1
399,990
No olviden: No (necesariamente) es tiempo muertoMultiprogramación: Mientras un proceso espera a que seresuelva su fallo de página, otros pueden continuarejecutando
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Acomodo de las páginas en disco
El cálculo presentado asume que el acomodo de laspáginas en disco es óptimoSi hay que agregar el espacio que una página ocupa en unsistema de archivos, tf fácilmente aumenta
Navegar estructuras de directorioPosible fragmentación en espacio de archivos →lamemoria va quedando esparcida por todo el discoMayores movimientos de la cabeza lectoraProblema prevalente en los sistemas tipo Windows
Respuesta: Partición de intercambio, dedicada 100% a lapaginación
Mecanismo empleado por casi todos los sistemas Unix
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Índice
1 Concepto
2 Paginación sobre demanda
3 Reemplazo de páginas
4 Asignación de marcos
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Manteniendo el sobre-compromiso
Cuando sobre-comprometemos memoria, los procesos enejecución pueden terminar requiriendo que se carguenmás páginas de las que caben en la memoria físicaMantenemos el objetivo del sistema operativo: Otorgar alos usuarios la ilusión de una computadora dedicada a susprocesosNo sería aceptable terminar la ejecución de un proceso yaaceptado
Mucho menos si ya fueron aprobados sus requisitos y nosquedamos sin recurso
→Tenemos que llevar a cabo un reemplazo de páginas
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Importancia del reemplazo de páginas
Parte fundamental de la paginación sobre demandaLa pieza que posibilita una verdadera separación entrememoria lógica y físicaMecanismo que permite liberar alguno de los marcosactualmente ocupado
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Mecanismo para liberar un marco ocupado
Cuando todos los marcos están ocupados (o se cruza elumbral determinado), un algoritmo designa a una páginavíctima para su liberación
Veremos más adelante algunos algoritmos para estoEl paginador graba a disco los contenidos de esta páginay la marca como libre
Actualizando el PCB y TLB del proceso al cual pertenece
Puede continuar la carga de la página requerida¡Ojo! Esto significa que se duplica el tiempo detransferencia en caso de fallo de página (tf )
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Manteniendo a tf en su lugar
Con apoyo del MMU podemos reducir la probabilidad deesta duplicación en tfAgregamos un bit de modificación o bit de página sucia ala tabla de páginas
Apagado cuando la página se carga a memoriaSe enciende cuando se realiza un acceso de escritura aesta página
Al elegir una página víctima, si su bit de página sucia estáencendido, es necesario grabarla a disco
Pero si está apagado, basta actualizar las tablas delproceso afectadoAhorra la mitad del tiempo de transferencia
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
¿Cómo elegir una página víctima?
Para elegir una víctima para paginarla al disco empleamosun algoritmo de reemplazo de páginasBuscamos una característica: Para un patrón de accesosdado, obtener el menor número de fallos de página
Diferentes patrones de acceso generan diferentesresultados para cada algoritmoNos referiremos a estos patrones de acceso como cadenade referencia
Para los ejemplos presentados a continuación, nos basaremosen los presentados en Operating Systems Concepts Essentials
(Silberschatz, Galvin y Gagné, 2011)
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Eligiendo una cadena de referencia
La cadena de referencia debe representar un patrón típico(para la carga que deseemos analizar) de accesos amemoriaMuchas veces son tomados de un volcado/trazado deejecución en un sistema real
El conjunto resultante puede ser enormeSimplificación: No nos interesa el acceso independiente acada dirección de memoria, sino que a cada /páginaVarios accesos consecutivos a la misma página no tienenefecto en el análisis
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Y el reemplazo. . . ¿en dónde?
Requerimos de un segundo parámetroPara analizar un algoritmo con una cadena de referencia,tenemos que saber cuántos marcos tiene nuestracomputadora hipotética
Lo que buscamos es la cantidad de fallos de páginaDepende directamente de los marcos disponibles
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Casos límite 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, sólo se produciríancuatro fallos
Los necesarios para la carga inicialExtremo opuesto: Con un sólo marco, tendríamos 12fallos
Cada página tendría que cargarse siempre desde disco
Casos que se pueden estudiar: 2 o 3 marcos
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Datos base para los algoritmos
A continuación veremos varios algoritmos de reemplazode páginasPara el análisis, 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
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Primero en entrar, primero en salir (FIFO) (1)
Nuevamente, el algoritmo más simple y de obviaimplementaciónAl cargar una página, se toma nota de cuándo fue cargadaCuando llegue el momento de reemplazar una páginavieja, se elige la que se haya cargado hace más tiempo
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Primero en entrar, primero en salir (FIFO) (2)
Cadena de referencia ———–> 7 0 1 2 0 3 0 4 2 3 V V V VV V V V V M +—+ +—+ +—+ +—+ +—+ +—+ +—++—+ +—+ +—+ A | 7 | | 7 | | 7 | | 2 | | 2 | | 2 | | 2 | | 4 | |4 | | 4 | R +—+ +—+ +—+ +—+ +—+ +—+ +—++—+ +—+ +—+ C | | | 0 | | 0 | | 0 | | 0 | | 3 | | 3 | | 3 | | 2| | 2 | O +—+ +—+ +—+ +—+ +—+ +—+ +—++—+ +—+ +—+ S | | | | | 1 | | 1 | | 1 | | 1 | | 0 | | 0 | | 0 | |3 | +—+ +—+ +—+ +—+ +—+ +—+ +—+ +—++—+ +—+. . . Cadena de referencia ——-> 0 3 2 1 2 0 1 7 0 1 V V V VV V M +—+ +—+ +—+ +—+ +—+ +—+ +—+ +—++—+ +—+ A | 0 | | 0 | | 0 | | 0 | | 0 | | 0 | | 0 | | 7 | | 7 | | 7| R +—+ +—+ +—+ +—+ +—+ +—+ +—+ +—++—+ +—+ C | 2 | | 2 | | 2 | | 1 | | 1 | | 1 | | 1 | | 1 | | 0 | | 0| O +—+ +—+ +—+ +—+ +—+ +—+ +—+ +—++—+ +—+ S | 3 | | 3 | | 3 | | 3 | | 2 | | 2 | | 2 | | 2 | | 2 | | 1| +—+ +—+ +—+ +—+ +—+ +—+ +—+ +—+ +—++—+
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Primero en entrar, primero en salir (FIFO) (3)
Típicamente programado empleando una lista ligadacircular
Cada elemento que va recibiendo se agrega como elúltimo 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 desempeño es altoTodas las páginas tienen la misma probabilidad de serreemplazadas, independientemente de su frecuencia deuso
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Anomalía de Belady
En general, asumimos que a mayor cantidad de marcos dememoria disponibles, menos fallos de página se van apresentarLa Anomalía de Belady ocurre cuando un incremento enel número de marcos disponibles lleva a más fallos depágina
Depende del algoritmo y de la secuencia de la cadena dereferencia
FIFO es vulnerable a la anomalía de Belady
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Anomalía de Belady: Expectativas decomportamiento
Figura: Relación ideal entre el número de marcos y la cantidad defallos de página (Silberschatz, p.335)
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Anomalía de Belady: Comportamiento de FIFO
reset data=’fig/anomaliabelady.gnuplot.data’ set term pngfontscale 1.5 size 640,320 set xrange [0:8] set xlabel “Númerode marcos de memoria disponibles” set yrange [0:14] set ylabel“Fallos de página” unset key plot data using 1:2 withlinespoints linewidth 2
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Algoritmo óptimo (OPT) o mínimo (MIN) (1)
Interes casi puramente téóricoElegimos como página víctima a aquella que no vaya a serutilizada por un tiempo máximo
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Algoritmo óptimo (OPT) o mínimo (MIN) (2)
Cadena de referencia ———–> 7 0 1 2 0 3 0 4 2 3 V V V VV V M +—+ +—+ +—+ +—+ +—+ +—+ +—+ +—++—+ +—+ A | 7 | | 7 | | 7 | | 2 | | 2 | | 2 | | 2 | | 2 | | 2 | | 2| R +—+ +—+ +—+ +—+ +—+ +—+ +—+ +—++—+ +—+ C | | | 0 | | 0 | | 0 | | 0 | | 0 | | 0 | | 4 | | 4 | | 4 | O+—+ +—+ +—+ +—+ +—+ +—+ +—+ +—+ +—++—+ S | | | | | 1 | | 1 | | 1 | | 3 | | 3 | | 3 | | 3 | | 3 | +—++—+ +—+ +—+ +—+ +—+ +—+ +—+ +—+ +—+. . . Cadena de referencia ———–> 0 3 2 1 2 0 1 7 0 1 V V VM +—+ +—+ +—+ +—+ +—+ +—+ +—+ +—++—+ +—+ A | 2 | | 2 | | 2 | | 2 | | 2 | | 2 | | 2 | | 7 | | 7 | | 7| R +—+ +—+ +—+ +—+ +—+ +—+ +—+ +—++—+ +—+ C | 0 | | 0 | | 0 | | 0 | | 0 | | 0 | | 0 | | 0 | | 0 | | 0| O +—+ +—+ +—+ +—+ +—+ +—+ +—+ +—++—+ +—+ S | 3 | | 3 | | 3 | | 1 | | 1 | | 1 | | 1 | | 1 | | 1 | | 1| +—+ +—+ +—+ +—+ +—+ +—+ +—+ +—+ +—++—+
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Algoritmo óptimo (OPT) o mínimo (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 dinámica como lamemoriaRecuerden: Millones de accesos por segundo
Principal utilidad: Brinda una cota mínimaPodemos ver qué tan cercano resulta otro algoritmorespecto al caso óptimo
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Menos recientemente utilizado (LRU) (1)
Lo hemos mencionado ya en varios puntos de laadministración de memoriaBusca acercarse a OPT prediciendo cuándo será elpróximo uso de cada una de las páginas
Basado en su historia reciente
Elige la página que no ha sido empleada desde hace mástiempo
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Menos recientemente utilizado (LRU) (2)
Cadena de referencia ———–> 7 0 1 2 0 3 0 4 2 3 V V V VV V V V M +—+ +—+ +—+ +—+ +—+ +—+ +—++—+ +—+ +—+ A | 7 | | 7 | | 7 | | 2 | | 2 | | 2 | | 2 | | 4 | |4 | | 4 | R +—+ +—+ +—+ +—+ +—+ +—+ +—++—+ +—+ +—+ C | | | 0 | | 0 | | 0 | | 0 | | 0 | | 0 | | 0 | | 3| | 3 | O +—+ +—+ +—+ +—+ +—+ +—+ +—++—+ +—+ +—+ S | | | | | 1 | | 1 | | 1 | | 3 | | 3 | | 3 | | 2 | |2 | +—+ +—+ +—+ +—+ +—+ +—+ +—+ +—++—+ +—+. . . Cadena de referencia ———–> 0 3 2 1 2 0 1 7 0 1 V V VV M +—+ +—+ +—+ +—+ +—+ +—+ +—+ +—++—+ +—+ A | 0 | | 0 | | 0 | | 1 | | 1 | | 1 | | 1 | | 1 | | 1 | | 1| R +—+ +—+ +—+ +—+ +—+ +—+ +—+ +—++—+ +—+ C | 3 | | 3 | | 3 | | 3 | | 3 | | 0 | | 0 | | 0 | | 0 | | 0| O +—+ +—+ +—+ +—+ +—+ +—+ +—+ +—++—+ +—+ S | 2 | | 2 | | 2 | | 2 | | 2 | | 2 | | 2 | | 7 | | 7 | | 7| +—+ +—+ +—+ +—+ +—+ +—+ +—+ +—+ +—++—+
Concepto Paginación sobre demanda Reemplazo de páginas Asignación 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 están libres de laanomalía de Belady
Para n marcos, las páginas que están en memoria son unsubconjunto estricto de las que estarían con n + 1marcos.
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Implementación ejemplo de LRU (1)
Se agrega un contador a cada uno de los marcosEl contador se incrementa siempre que se hace referenciaa una página
Se elige como víctima a la página con el contrador másbajo
Esto es, a la que hace más tiempo no haya sidoactualizada
Desventaja: Con muchas páginas, se tiene que recorrer lalista completa para encontrar la más envejecida
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Implementación 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 página, se mueve a lacabeza (arriba) del stack — Peor caso: 6 operacionesPara elegir a una página víctima, se toma la de abajo delstack (tiempo constante)
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Más / menos frecuentemente utilizado (MFU /LFU)
Dos algoritmos contrapuestos, basados (como LRU) enmantener un contador
Miden la cantidad de referencias que se han hecho acada página
Lógica base:MFU Si una página fue empleada muchas veces,
probablemente va a ser empleada muchasveces más
LFU Si una página casi no ha sido empleada,probablemente recién fue cargada, y seráempleada en el futuro cercano
La complejidad de estos algoritmos es tan alta comoLRU, y su rendimiento es menos cercano a OPT
Casi no son empleados
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Aproximaciones a LRU
¿Principal debilidad de LRU? Su implementación requiereapoyo en hardware mucho más complejo que FIFOHay varios mecanismos que buscan aproximar elcomportamiento de LRU
Empleando información menos detallada
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Bit de referencia
Aproximación bastante comúnTodas las entradas de la tabla de páginas tienen un bit dereferencia, inicialmente apagado
Cada vez que se referencia a un marco, se enciende su bitde referenciaEl sistema reinicia periódicamente a todos los bits dereferencia, apagándolos
Al presentarse un fallo de página, se elige por FIFO deentre el subconjunto con el bit apagado
Esto es, entre las páginas que no fueron empleadas en elperiodo
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Bits adicionales (columna) de referencia
Mecanismo derivado del anterior, dando más granularidadSe maneja una columna de referencia, de varios bits deancho
Periódicamente, en vez de reiniciar a 0, el valor de todaslas entradas se recorre a la derecha, descartando el bitmás bajoEl acceso a un marco hace que se encienda su bit másalto
Ante un fallo de página, se elige entre los marcos convalor de referencia más bajo
Concepto Paginación sobre demanda Reemplazo de páginas Asignación 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 posición (dándole unasegunda oportunidad)Si elige a un marco que tiene apagado el bit dereferencia, lo designa como página víctima
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 apagado
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Segunda oportunidad mejorada (1)
Si agregamos al bit de referencia un bit de modificación,nos mayor expresividad, y puede ayudar a elegir a unapágina víctima más 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. Habría quegrabarlo a disco, y tal vez vuelva a requerirsepronto. Hay que evitar reemplazarlo.
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Segunda oportunidad mejorada (2)
Emplea una lógica como la de segunda oportunidad, peroconsiderando el costo de E/SPuede requerir dar hasta cuatro vueltas para elegir a lapágina víctima
Aunque cada vuelta es más corta
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Algoritmos con manejo de buffers
De uso cada vez más frecuenteNo esperan a que el sistema requiera reemplazar unmarco, buscan siempre tener espacio disponibleConforme la carga lo permite, el SO busca las páginassucias más proclives a ser paginadas
Va copiándolas a disco y marcándolas como limpias
Cuando tenga que traer una página de disco, siemprehabrá dónde ubicarla sin tener que hacer una transferencia
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Índice
1 Concepto
2 Paginación sobre demanda
3 Reemplazo de páginas
4 Asignación de marcos
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Viendo el lado opuesto del problema
Vimos ya cómo retirar marcos asignados¿Cómo conviene asignar los marcos a los procesos?Definamos algunos parámetros para nuestros ejemplos
Un sistema con 1024KB de memoria física256 páginas de 4KB cada unaEl sistema operativo ocupa 248KB (62 páginas); 194páginas para los procesos a ejecutar
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Vuelta a la paginación puramente sobre demanda
En un esquema de paginación puramente sobre demanda,cada fallo de página que se va generando lleva a que seasigne el marco correspondienteSe van asignando los marcos conforme son requeridos,hasta que hay 194 páginas ocupadas por procesos
Entonces, entran en escena los algoritmos de reemplazode páginas que ya vimosClaro está, cuando un proceso termina, sus marcosvuelven a la lista de marcos libres
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Puramente sobre demanda: Demasiado flojo
El esquema de paginación puramente sobre demandapuede resultar demasiado flojoSer un poco más ansioso aseguraría un mejor rendimientoConviene determinar un mínimo utilizable de marcos
Si asignamos por debajo del mínimo, sufre el rendimiento
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Mínimo de marcos: Arquitectura ydireccionamiento
Hasta ahora hemos simplificado asumiendo que cadainstrucción puede generar sólo un fallo de páginaIndependientemente de la arquitectura, cada instrucciónpuede desencadenar varias solicitudes
Una solicitud, la lectura de la siguiente dirección aejecutar (¡recuerden: von Neumann!)Otra, la dirección de memoria referidaPor ejemplo, si el flujo brinca a 0x00A2C8, y estainstrucción es load 0x043F00, para satisfacerlarequerimos dos páginas: 0x00A y 0x043→Requerimos un mínimo de dos páginas
Pero. . . ¿Y las referencias indirectas?
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Mínimo de marcos: Referencias indirectas
Casi todas las arquitecturas permiten hacer referenciasindirectas a memoriaUna instrucción de acceso a memoria (load, store)especifica una dirección de memoriaY esta dirección guarda la ubicación de memoriaPor ejemplo, 0x043F00 indica la carga de 0x010F80
→Satisfacer al load 0x043F00 requerirá entoncestres páginas: 0x00A, 0x043 y 0x010
. . . Y algunas arquitecturas (principalmente antiguas)permitían niveles ilimitados de indirección
Por ejemplo, por medio de un bit de indirecciónEn dado caso, es imposible asegurar un límite máximo→Es común que el MMU haga un conteo de referenciaspara evitar caer en un ciclo sin fin
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Instrucciones con operandos en memoria
Las arquitecturas RISC introdujeron requisitos deregularidad que incluyen el que la aritmética opereexclusivamente sobre los registros del procesadorLas arquitecturas más 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 instrucción
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
El nivel deseable de marcos
Con estos lineamientos determinamos ya un mínimoabsoluto
Muy bajo, poniéndolo en el contexto de los sistemasactuales
¿Cómo puede el sistema determinar un nivel deseable demarcos por proceso?
Depende siempre del estado actual del sistemaPodríamos intentar satisfacer los requisitos totales de unode los procesos
A menor cantidad de fallos de página, mayor rendimientoPero si reducimos el grado de multiprogramación,reducimos el uso efectivo del procesador
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Asignación igualitaria
Buscando un reparto justo de recursos, se divide el totalde memoria física disponible entre el número de procesosVolviendo a nuestra computadora ejemplo (256 marcos;62 marcos asignados al sistema, 194 a los procesos):
Si tenemos 4 procesos en ejecución, dos tendrán 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 sólo requiere 112KB (28 páginas). . .Ambos recibirán lo mismo — Y P2 desperdiciará 20páginas
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Asignación igualitaria
Buscando un reparto justo de recursos, se divide el totalde memoria física disponible entre el número de procesosVolviendo a nuestra computadora ejemplo (256 marcos;62 marcos asignados al sistema, 194 a los procesos):
Si tenemos 4 procesos en ejecución, dos tendrán 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 sólo requiere 112KB (28 páginas). . .Ambos recibirán lo mismo — Y P2 desperdiciará 20páginas
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Asignación proporcional
Brinda a cada proceso una porción del espacio dememoria física proporcional a su uso de memoria virtualSi además de los dos procesos descritos tenemos a P3 con560KB (140 páginas) y P4 con 320KB (80 páginas) dememoria virtual
Uso total de memoria virtual:VT = 512+ 28+ 140+ 80 = 760 páginas
Sobreuso de memoria física cercano al 4:1 respecto a las194 páginas disponibles
Cada proceso recibirá FP = VPVT
mFP : Espacio de memoria física que recibiráVP : Cantidad de memoria virtual que emplea,m: Total de marcos de memoria física disponibles
P1: 130 marcos; P2: 7 marcos; P3: 35 marcos; P4: 20marcos
Proporcional a su uso de memoria virtual.
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Modulando la asignación proporcional
Mínimos: El esquema debe cuidar nunca asignar pordebajo del mínimo de la arquitectura
Si P2 ocupara sólo 10 marcos de memoria física, en unaarquitectura x86 no deberían asignársele menos de 3marcos
Desbalance por procesos obesosSi P1 crece al doble de su tamaño virtual, hay que cuidartener umbrales máximos para no castigar de más a losdemás procesos del sistema
¿Manejo de prioridades?Si el sistema maneja prioridades, podrían incluirseponderadas, otorgando proporcionalmente más marcos alos procesos con mayor prioridad
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Sufrimiento ante la entrada de nuevos procesos
El esquema de asignación proporcional sufre cuando sonadmitidos nuevos procesos, cambia el tamaño en memoriavirtual de alguno de los existentes o (aunque menos)finalizan los que están en ejecuciónDeben recalcularse los totales, y probablemente reducir degolpe el espacio asignado a los procesos existentes
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Desperdicio de recursos
El patrón de uso de memoria física de un proceso nonecesariamente guarda correspondencia con su tamaño enmemoria virtualPueden emplear mucho menores requisitos endeterminadas secciones de su ejecuciónRecordar este punto →Conjunto activo
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Ámbitos del algoritmo de reemplazo de páginas
Respondiendo a los problemas que abre la sección anterior,podemos discutir el ámbito en el que operará nuestro
algoritmo de reemplazo de páginas
Reemplazo localReemplazo globalReemplazo global con prioridad
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Reemplazo local
Mantenemos tan estable como sea posible el cálculo demarcos de memoria por proceso
Cuando se presente un fallo de página, sólo se consideranaquellas pertenecientes al mismo proceso
El proceso tiene asignado un espacio de memoria físicaLo mantendrá mientras el sistema operativo no tomealguna decisión para modificarlo
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Reemplazo global
Los algoritmos de asignación determinan el espacioasignado /al momento de su inicialización
Pueden influir en los algoritmos de reemplazoP.ej. dando mayor peso a los marcos de un proceso queexcede su asignación para ser elegidas como víctima. . . 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 asignación física a cada proceso puede variar según elestado del sistema, momento a momento
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Reemplazo global con prioridad
Esquema mixtoPermite que un proceso sobrepase su límite
Pero sólo siempre que le robe espacio en memoria físicasólo 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 también operar bajo concesiones temporales,buscando equilibrar posteriormente
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Comparando los ámbitos de reemplazo
Reemplazo local Más rígido; 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
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
¿Y el tiempo real?
Cuando presentamos al tiempo real (Planificación deprocesos), mencionamos que el tiempo real duro esincompatible con sistemas basados en memoria virtualPrincipal razón: Las demoras inducidas por la paginaciónPodría indicarse que un proceso de tiempo real esté 100%en memoria física (nunca candidato para paginación)Reduce fuertemente el impacto que sufriría al pelear porrecursos
Pero no lo resuelve por completoNi la contención en el bus, ni la inversión deprioridades. . .→Sólo podemos prometer tiempo real suave
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Hiperpaginación: Definición
Uno o más procesos tienen demasiadas pocas páginasasignadas para llevar a cabo su trabajoGeneran fallos de pagina con tal frecuencia que resultaimposible realizar trabajo real
O resulta tan lento que la percepción es de no-avance
El sistema pasa más tiempo intentando satisfacer lapaginación que trabajando
Estamos en estado de hiperpaginaciónEn inglés, thrashing (literal: paliza)
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
¿Qué puede llevar a la hiperpaginación? (1)
El sistema tiene una carga normalEsquema de reemplazo global de marcosSe lanza un nuevo proceso
Su inicialización requiere poblar estructuras a lo largo desu memoria virtualO cambia de conjunto activoSerie de fallos de página →El sistema responde,reemplazando a varios marcos de otros procesos
Mientras esto continúa operando, algunos de los procesosvíctima requieren de las páginas que pasaron a disco
Recordemos que el disco es miles a millones de veces máslento que la memoria. . .
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
¿Qué puede llevar a la hiperpaginación? (2)
La utilización del procesador decrece. . . Porque los procesos están esperando a que sumemoria esté disponible
El sistema operativo aprovecha la situación para lanzarprocesos de mantenimiento
Que requieren que se les asigne memoria→Reducen aún más el espacio de memoria físicadisponible
Se forma una cola de solicitudes de paginación (algunasveces contradictorias)Baja todavía más la actividad del procesador (NOOP)
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
¿Cómo se ve la hiperpaginación?
reset clear set term png size 800,400 fontscale 1.5set multiplot unset key unset xtics unset ytics set yrange[0:2]set ylabel “Uso del procesador” set xlabel “ “ set origin 0.0,0.0set size 0.4,1 set lmargin 3 set rmargin 0 set border 1+2 setxrange[0:4] plot 2-(1/x)unset ylabel set xlabel “Grado de multiprogramación” set origin0.4,0.0 set size 0.25,1 set lmargin 0 set rmargin 0 set border 1set xrange[-0.2:0.2] plot 1.79-(x*x)set xlabel “ “ set origin 0.65,0.0 set size 0.1,1 set lmargin 0 setrmargin 0 set border 1 set xrange[-4:-0.6] set arrow from-4,1.85 to 3,1.85 size 1,15 filled set label 1 “Hiperpaginación”at -4, 2 plot (1/x)+2unset label 1 set xlabel “ “ set origin 0.75,0.0 set size 0.25,1set lmargin 0 set rmargin 2 set xrange[3:100] plot (1/x)
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
Respondiendo a la hiperpaginación
Los síntomas son muy clarosFáciles de detectar — ¡pregúntenle a cualquier usuario!
Reducir temporalmente el nivel de multiprogramaciónCaímos en hiperpaginación por tener requisitos enmemoria que no alcanzamos a satisfacer con la memoriafísica disponibleEl sistema puede seleccionar a uno (o más) procesos ysuspenderlos por completoIncluso poner su memoria física a disposición de otrosprocesosHasta que salgamos del estado de hiperpaginación
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
¿A cuál proceso castigar?
Al de menor prioridadAl que esté causando más fallosAl que esté ocupando más memoria. . .
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
El conjunto activo
El conjunto activo es una clara aproximación a lalocalidad de referenciaEl conjunto de páginas con que un proceso estátrabajando en un momento dado
¿Qué significa un momento dado?
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
El conjunto activo
widthwidth
Figura: Al aumentar demasiado el grado de multiprogramación, eluso del CPU cae abruptamente y caemos en la hiperpaginación(Silberschatz, p.349) Los picos y valles en la cantidad de fallos depágina de un proceso definen a su conjunto activo (Silberschatz,p.349)
Concepto Paginación sobre demanda Reemplazo de páginas Asignación de marcos
El conjunto activo y el espacio en memoria
Idealmente, en todo momento, debemos asignar a cadaproceso suficientes páginas para mantener en memoriafísica su conjunto activoSi no es posible hacerlo, el proceso es buen candidatopara ser suspendido. . . Pero no es fácil detectar con claridad cuál es elconjunto activo
Mucho menos predecir cuál será dentro de determinadotiempo¿Cuánto dura un proceso dentro de determinada rutina?Puede requerir rastrear y verificar decenas de miles deaccesos a memoria