4. Particiones de Memoria Nº procesos = 2 * Nº huecos. Asimetria por fundir huecos adyacentes. F: % mem en huecos S : tamaño medio de los procesos. kS : tamaño medio de los huecos. M: mem total. Nº huecos => n/2 Mem en h => (n/2)ks=m-ns Fracción: f = (MEM Proc/ m) = (nks/2m) F = k/(k+2). (k cercano a ½ => 20% de uso). 4.8 Análisis de la gestión.
5. Algoritmos de Asignaciones First fit. Se busca cualquier hueco en el que quepa el proceso. Por cada asignación se crea una entrada de proceso y otra de hueco. Rápido. Next fit. Si el flujo de llegada de procesos es uniforme todos con las mismas necesidades de MEM. Comienza donde se realizó la última asignación. Best fit. Busca en toda la lista el hueco que mejor se adapta a las necesidades (más pequeño de los posibles). Lento (busca siempre toda la lista). Desaprovecha MEM por dejar huecos muy pequeños. Worst fit. Busca el espacio vacío más grande. El hueco sobrante es grande: utilizable.
5.1 Algoritmos de Asignaciones.
(Gp:) Último bloque asignado (14K) (Gp:) Primer ajuste (Gp:) Mejor ajuste (Gp:) Bloque asignado (Gp:) Bloque libre (Gp:) Siguiente ajuste (Gp:) (a) Antes (Gp:) (b) Después (Gp:) 8M (Gp:) 8M (Gp:) 12M (Gp:) 12M (Gp:) 22M (Gp:) 18M (Gp:) 8M (Gp:) 8M (Gp:) 6M (Gp:) 6M (Gp:) 6M (Gp:) 2M (Gp:) 14M (Gp:) 36M (Gp:) 14M (Gp:) 20M
Figura 7.5. Ejemplo de una configuración de memoria antes y después de asignar un bloque de 16 Mbytes.
5. Algoritmos de Asignaciones Listas separadas: Los algoritmos pueden ser acelerados mediante listas separadas de huecos y procesos. Los alg. Sólo buscan en la lista de huecos. Actualizaciones de las listas son complejas. Ordenación según el tamaño. Mejora en el Best fit. Quick fit: Listas separadas para los tamaños más usados. Las búsquedas son rápidas. Actualizaciones lentas. 5.2 Algoritmos de Asignaciones: Aceleración.
Memoria Virtual Sub Tema 6
6. Memoria Virtual: Definición y conceptos Conceptos de MV [Fotheringhan 1961] Principio de Cercanía. Working-Set Fallo de página
6. Memoria Virtual: Definición y conceptos Fotheringham, 1961: “El programa (pila, datos, programa) puede ser mayor que la MEM. El S.O. mantiene las partes en uso del programa en MEM y el resto en el HD. Se tiene una memoria virtual.”
Posible gracias al Principio de Cercanía: Las referencias a los datos y al programa dentro de un proceso tienden a agruparse.
Se pueden mantener más procesos en la memoria principal: Se cargan sólo algunos fragmentos de un proceso particular. Con tantos procesos en la memoria principal es muy probable que uno de los procesos esté en estado Listo en un instante determinado. Es posible que un proceso sea más grande que toda la memoria principal.
El sistema operativo comienza trayendo sólo unos pocos fragmentos del programa. Working set: El conjunto residente es la parte de un proceso que está realmente en la memoria principal.
6. Memoria Virtual: Definición y conceptos Si el procesador encuentra una dirección lógica que no está en la memoria principal: Genera una interrupción que indica un fallo de acceso a la memoria. El sistema operativo pone al proceso interrumpido en estado Bloqueado. La solución tradicional para programas mayores que la MEM física. Overlays: Distribución del programa en módulos cargados ségún necesidades. Control: El programador.
Fotheringham, 1961: “El programa (pila, datos, programa) puede ser mayor que la MEM. El S.O. mantiene las partes en uso del programa en MEM y el resto en el HD. Se tiene una memoria virtual.”
El programa se ejecuta hasta llegar a zona de programa no presente en MEM. Fallo de página para cargar la página. La CPU ha de poder retomar la ejecución: Transacciones. Anticipo de fallos.
7. Memoria Virtual: Soporte Tiene que existir un soporte de hardware para la paginación y la segmentación. El sistema operativo debe incluir un software para gestionar el movimiento de páginas o segmentos entre memoria secundaria y memoria principal.
Memoria virtual: Espacio de direcciones >> MEM. El espacio virtual dividido en páginas (512 B< página < 8 KB). Cada página se corresponde con un marco de página. Tamaño marco = tamaño página. Transferencias MEM ? disco son del tamaño de la página.
Soportes de la memoria virtual.
8. Tablas de páginas
Tablas de páginas. (Gp:) Tabla de páginas del proceso A (Gp:) Tabla de páginas del proceso B (Gp:) Tabla de páginas del proceso C (Gp:) Tabla de páginas del proceso D (Gp:) Lista de marcos libres (Gp:) Estructuras de datos para el ejemplo anterior en el instante de tiempo (f).
8. Tablas de páginas
8. Tablas de páginas: Traducción Espacio del proceso Espacio de memoria física Sistema con VM de 64k MEM de 32k. 0 010 1 001 1 110 1 000 1 100 1 011 1 000 0 000 0 000 0 101 1 000 0 111 1 000 0 000 0 000 0 000 0 La página no presente => bit de ausencia. Su acceso genera un fallo de página. Detiene ejecución. Salva el contenido de un marco en el HD. Se carga la página llamada. Retorna la ejecución del programa en la dirección que generó el fallo. (Gp:) 0, 4k 4, 8k 8, 12k 12, 16k 16, 20k 20, 24k 24, 28k 28, 32k (Gp:) 0, 4k 4, 8k 8, 12k 12, 16k 16, 20k 20, 24k 24, 28k 28, 32k 32, 36k 36, 40k 40, 44k 44, 48k 48, 52k 52, 56k 56, 60k 60, 64k
N.º pág. N.º marco Traducción de direcciones en un sistema de paginación.
Despla- zamiento (Gp:) N.º marco (Gp:) Despla- zamiento
Despla- zamiento Dirección virtual Registro Tabla de páginas N.º página Marco de página Puntero a tabla de páginas Programa Mecanismo de paginación Memoria principal
El sistema mapea la M.V. en la MEM mediante la MMU (chip o colección de ellos). Del ejemplo: 64k => 16 bits D 0 => Marco 2 => 8192 D 20500 (página 5) => marco 4 => 12288+20 = 12308 0101000000010100 => 100000000010100 8. Memoria Virtual: Traducción Tabla de páginas.
9. Tablas de páginas: Implementación Dependiendo del tamaño de la tabla de páginas la gestión se realiza: TP en registros. TP en memoria. TP multinivel. MEM asociativa. Tablas de páginas.
9. Tablas de páginas: Implementación 9.1 TP en registros. Cada proceso tiene asociado un número de registros. Cada registro tiene asociado un marco de página. La carga de un proceso => carga en los registros. Durante la ejecución del proceso no se realizan accesos a MEM para traducir direcciones. Tablas de páginas.
9. Tablas de páginas: Implementación 9.2 TP en memoria. Un registro apunta al comienzo de la TP. Cambio de contexto => cambio de dirección del registro. Varias referencias a MEM para traducir los accesos a MEM. Tablas de páginas.
9. Tablas de páginas: Implementación 9.3 TP multinivel TP muy grandes (32 bits => 4GB). TP por partes. PT2 1024 (Gp:) TP1 10bits (Gp:) TP2 10bits (Gp:) Offset 12 bits
(Gp:) PT1 1024 (Gp:) 4MB (Gp:) Dirección
4206896 = 4MB + 12292 00000000010000000011000000000100 PT1 = 1 => entre 4M y 8 M PT2 = 3 => entre 12288 y 16383 (encima de 4M) Offset = 4
Esquema de dos niveles para direcciones de 32 bits 4 Kbytes para la raíz de la tabla de páginas 4 Mbytes para la tabla de páginas de usuario 4 Gbytes para el espacio de direc- ciones de usuario Figura 8.4. Tabla de páginas jerárquica de dos niveles [JACO98a].
9. Tablas de páginas: Implementación 9.4 MEM asociativa. Por la lentitud en las traducciones. TP grandes => en MEM, no en registros. Localidad en las referencias a memoria. Solución: Componente del MMU con 8-32 entradas. Cada entrada: nº página virtual. Bit de modificado. Protección (rwx). Marco de página (real). Validez. El cambio de contexto borra la MEM asoc. Comienza limpia para cada proceso. Solución: un juego de MEM asoc. Por proceso.
9. Tablas de páginas: Implementación Gestión mediante bits. Bits en la TP por cada página. Entrada en la tabla de páginas: Nº marco Presencia/ausencia 1/0 Protección 1 -> R // 0 -> WR Modificado Necesario actualizar la pag al HD. Referenciado Página en uso. Cache Página en cache (pag. Sobre registros).
9.5 Tabla de páginas: Protección.
9. Tablas de páginas: Implementación Dirección virtual Entrada de la tabla de páginas (a) Sólo paginación Número de página Desplazamiento (Gp:) P (Gp:) M (Gp:) Otros bits de control (Gp:) Número de marco
Formatos típicos de gestión de memoria. 9.6 Entradas de la tabla de páginas
9. Tablas de páginas: Implementación Cada referencia a la memoria virtual puede generar dos accesos a la memoria: Uno para obtener la entrada de la tabla de páginas correspondiente. Otro para obtener el dato deseado. Para solucionar este problema, los esquemas de memoria virtual hacen uso de un cache especial para las entradas de la tabla de páginas: Se trata de la buffer de traducción adelantada (TLB, Translation Lookaside Buffer). Contiene aquellas entradas de la tabla de páginas usadas hace menos tiempo. Funciona del mismo modo que una memoria cache.
Dada una dirección virtual, El procesador examinará primero la TLB. Si la entrada de la tabla de páginas buscada está presente (un “acierto en la TLB”), se obtiene el número de marco y se forma la dirección real. Si la entrada de la tabla de páginas no se encuentra (un “fallo en la TLB”), el procesador emplea el número de página como índice para buscar en la tabla de páginas del proceso y examinar la entrada correspondiente de la tabla de páginas.
9.7 Buffer de traducción adelantada.
Volver a la instrucción que falló Rutina de gestión de fallo de página Sí No Sí Sí No No Comienzo La CPU comprueba la TLB Acceder a la tabla de páginas Actualizar TLB La CPU genera la dirección física El SO ordena a la CPU leer la página del disco La CPU activa el hardware de E/S La página se transfiere del disco a memoria principal Actualizar las tablas de páginas Actualizar las tablas de páginas ¿Memoria llena? Figura 8.8. Funcionamiento de la paginación con buffer de traducción adelantada (TLB) [FUTH87]. ¿Está la entrada de la tabla de página en la TLB? ¿Está la página en memoria principal?
Dirección virtual Memoria principal Memoria secundaria Buffer de traducción adelantada Dirección real Despla- zamiento Despla- zamiento Acierto de TLB Fallo de TLB Tabla de páginas Despla- zamiento Cargar página
Fallo de página
Nº. Pág. N.º marco Figura 8.7. Uso de un Buffer de Traducción Adelantada. (Gp:) N.º pág. (Gp:) Despla- zamiento
10. Algoritmos de reemplazo Rigen el criterio de sustitución de los marcos tras el fallo. Máximas: Baja sobrecarga del sistema: Velocidad en la determinación de la víctima. No ajustes: Algoritmos independientes de la máquina (problemas por el bajo nivel). Elección óptima: Elección de la víctima cercana a la óptima. Evaluación respecto de cadena de referencia (aleatoria o real) y un número de marcos.
Algoritmos de reemplazo.
10. Algoritmos de reemplazo FIFO: Primera página en entrar es la primera en salir. Trata los marcos asignados a un proceso como un buffer circular. Las páginas se suprimen de la memoria según la técnica de turno rotatorio (round-robin). Es una de las políticas de reemplazo más sencillas de implementar. Se reemplaza la página que ha estado más tiempo en la memoria. Problema: Estas páginas pueden necesitarse de nuevo y en un plazo de tiempo corto. Óptimo: Víctima será la página que más tardará en ser usada. Tiene la menor tasa de fallos. No es implementable: Conocer los accesos futuros. Se usa como patrón de evaluación. Menos recientemente usada (LRU). Se predice el futuro en función del pasado. Victima: pag. menos usada en el pasado. Cada pág. asociada con el instante del acceso. Necesarias estructura de información para gestionar la historia: Contador de tiempo / pag. Cola de accesos/página. Pila: con los accesos. Al principio siempre el último acceso.
10. Algoritmos de reemplazo Aproximaciones a LRU: Bit de referencia: Bit en ON por cada acceso. Bits de ref. adicionales: Histórico de los accesos con cadenas de bits. Se ponderan los accesos. Segunda oportunidad: FIFO + bit de referencia. Puntero que barre los marcos. Bit = 0 => reemplazo. Bit = 1 => bit = 0: avance de posición. Least frequetly used (LFU) Bits de ref. adicionales. Contador de accesos. Problema: Fijar el origen de tiempos no es bueno por la localidad. Reloj: Requiere asociar un bit adicional a cada marco, denominado bit de uso. Cuando se carga una página por primera vez en un marco de memoria, el bit de uso de dicho marco se pone a cero. Cuando se hace referencia a la página posteriormente, el bit de uso se pone a 1. Cuando llega el momento de reemplazar una página, el primer marco encontrado con el bit de uso a 0 es reemplazado. Durante la búsqueda para realizar reemplazos cada bit de uso a 1 se cambia a 0.
Primer marco en el buffer circular de marcos que son candidatos para el reemplazo
Página 9 uso = 1 Página 19 uso = 1 Página 191 uso = 1 Página 1 uso = 1 Página 45 uso = 1 Página 13 uso = 0 Página 67 uso = 1 Página 33 uso = 1 Figura 8.16. Ejemplo de funcionamiento de la política del reloj.
(a) Estado del buffer justo antes del reemplazo de página
Puntero al siguiente marco
Página 556 uso = 0 Página 222 uso = 0
Figura 8.16. Ejemplo de funcionamiento de la política del reloj.
(b) Estado del buffer justo después del siguiente reemplazo de página Página 9 uso = 1 Página 19 uso = 1 Página 1 uso = 0 Página 45 uso = 0 Página 191 uso = 0 Página 727 uso = 1 Página 13 uso = 0 Página 67 uso = 1 Página 33 uso = 1 Página 222 uso = 0
10. Algoritmos de reemplazo Almacenamiento intermedio de páginas: La pista de la página reemplazada se asigna a una de las dos listas siguientes: La lista de páginas libres, si la página no ha sido modificada. La lista de páginas modificadas, si lo ha sido.
10.1 CACHE de páginas.
11. Tamaño de página. Cuanto menor sea el tamaño de página, Menor será la cantidad de fragmentación interna. Mayor será el número de páginas que se necesitan por proceso. Tabla de páginas grandes o mayor número de registros en la MMU. Un número mayor de páginas por proceso significa que las tablas de páginas serán mayores. Una gran parte de las tablas de páginas de los procesos activos deben estar en la memoria virtual. La memoria secundaria está diseñada para transferir eficazmente los bloques de datos de mayor tamaño, de manera que es propicia para tamaños de página mayores. Si el tamaño de página es muy pequeño, estarán disponibles en la memoria principal un gran número de páginas para cada proceso. Después de un tiempo, todas las páginas de la memoria contendrán parte de las referencias más recientes del proceso. La tasa de fallos de página será menor. Cuando se incrementa el tamaño de la página, cada página individual contendrán posiciones cada vez más distantes de cualquier referencia reciente. La tasa de fallos será mayor.
11. Tamaño de página: Hiperpaginación El número de páginas de cada programa (working set) es inferior al necesario apra el prinipio de proximidad. El sistema operativo expulsa un fragmento de un proceso justo antes de ser usado. El procesador consume más tiempo intercambiando fragmentos que ejecutando instrucciones de usuario. Hiperpaginación.
11. Tamaño de página Múltiples tamaños de página proporcionan la flexibilidad necesaria para usar una TLB eficazmente. Las páginas grandes se pueden utilizar para traducir instrucciones de programa. Las páginas de pequeño tamaño se pueden emplear para las pilas de los hilos. La mayoría de los sistemas operativos favorecen el uso de un solo tipo de página. Tamaño de página.
(Gp:) Ejemplos de tamaños de páginas. (Gp:) Computadora (Gp:) Tamaño de página (Gp:) Atlas 512 palabras de 48 bits Honeywell-Multics 1.024 palabras de 36 bits IBM 370/XA y 370/ESA 4 Kbytes Familia VAX 512 bytes IBM AS/400 512 bytes DEC Alpha 8 Kbytes MIPS de 4 Kbytes a 16 Mbytes UltraSPARC de 8 Kbytes a 4 Mbytes Pentium de 4 Kbytes a 4 Mbytes Power Pc 4 Kbytes
Ejemplos de tamaños de páginas
 Página anterior | Volver al principio del trabajo | Página siguiente  |