1 Introducción (1) Idealmente, los programadores quieren memoria mucha, rápida, no volátil, barata Historia 1980’s: MDS (64k), monousuario, CP/M, overlays 1980’s: VAX (4Mb), multiusuario (docenas) 2000’s: Windows, 64Mb (normal 512 Mb) Jerarquía de memorias Caché: poca, rápida, cara RAM: Mb, velocidad y precio medios Disco: Gb, lenta y barata Es un problema de costes
2 Introducción (2) Trabajos del gestor de memoria Qué memoria está libre/ocupada Asignación/liberación de memoria a procesos Intercambio RAM-disco Clases de gestores de memoria Con intercambio Swapping y paginación Sin intercambio
3 Solo un programa en memoria (junto con el SO) Se carga y se queda ahí hasta que acaba (CP/M) MSDOS BIOS (Basic Input Ouput System) palmTop, empotrados minis Gestión básica de memoria (1)Monoprogramación sin intercambio ni paginación
4 Gestión básica de memoria (2)Multiprogramación con particiones fijas
5 Planificación: queda libre una partición, ¿qué trabajo cargar? El primero en la cola que quepa Fragmentación interna El más grande de la cola que quepa Se perjudica a los pequeños (y debe ser al revés) Disponer de una partición pequeña No retrasar un trabajo más de k veces OS/360, MFT (Multiprogramming with a Fixed number of Task) Gestión básica de memoria (3)Multiprogramación con particiones fijas
6 La utilización de CPU es función del nº. de procesos en memoria Grado de multiprogramación Gestión básica de memoria (4)Modelo de multiprogramación
7 Los procesos son independientes n: grado de multiprogramación p: fracción de tiempo que un proceso está esperando una I/O Utilización de la CPU = 1 – pn Los procesos no son independientes: 1 sola CPU-> los otros en preparados (esperando). Aproximación válida. Ejemplo: 32Mb memoria, el SO ocupa 16Mb cada proceso de usuario 4Mb => n = 4; si p=0.8, CPU = 60% Si compramos 16Mb => n = 8; si p=0.8, CPU = 83%; ganancia: 38% Si compramos otros 16Mb CPU=93%; ganancia: 12% Gestión básica de memoria (5)Modelo de multiprogramación (La sección 4.1.4 no entra para el examen)
8 Reubicación: ¿dónde reside un programa? estática, dinámica Las direcciones de un programa suelen ser relativas a su dirección de comienzo. PERO … al montar un programa no se sabe dónde se va a ejecutar. SOLUCIONES ? Modificación de direcciones durante la carga (estático) ? Registro de Reubicación (o registro base) (permite reubicación dinámica) Dir.Virtual Registro deReubicación DirecciónReal (Gp:) + 6000 5166 4418 4200 2854 512 0 A B C A B C 1345 0 747 0 2341 0 Espacio Virtual Espacio Real Ra = 2854Rb = 4418Rc = 512 Gestión básica de memoria (6)Reubicación y protección
9 Protección: acceso indiscriminado a cualquier área de memoria RegistroLímite RegistroBase DirecciónVirtual (Gp:) + (Gp:) < ERROR de direccionamiento ¡ ! RAM tamaño del programa dirección comienzo partición Gestión básica de memoria (7)Reubicación y protección
10 Intercambio (swapping) (1) Dos aproximaciones: Intercambio (entre RAM y disco) Memoria virtual (solo una parte del programa en RAM) Batch TiempoCompartido Se aceptan tantos trabajos como quepan en memoria Suele haber más procesos de usuario de los que caben en memoria¡ y hay que atenderlos a todos!
11 Intercambio (swapping) (2) PARTICIONES DE TAMAÑO VARIABLE(el nº, tamaño y dirección varía con el tiempo) (Gp:) ¡ Fragmentación Externa ! COMPACTACIÓN
12 P.ejem: 4 bytes: 40ns. 256Mb: 2,7 s. T4.4 (1ed) Ciertos sistemas con intercambio eliminan la fragmentación externa mediante compactación. Suponga que una computadora con 1Mb de memoria para usuario hace una compactación cada segundo. Si tarda 0,5 microseg en copiar un byte y el tamaño medio de los huecos es de 0,4 el tamaño medio de los segmentos ¿Cuál es la fracción del tiempo total de CPU que se utiliza para la compactación? Intercambio (swapping) (3)
13 Intercambio (swapping) (4) ¿Puede crecer dinámicamente la memoria de un proceso? A S. O. B Paracrecimiento En uso Paracrecimiento En uso S. O. Datos de B Código de B Pila de B Datos de A Código de A Pila de A Paracrecimiento Paracrecimiento (a) (b)
14 Intercambio (swapping) (5)Gestión de memoria con mapa de bits (Gp:) Se debe llevar la cuenta de la memoria utilizada y de los huecos libres (Gp:) Mapa de Bits Lista de Bloques Libres Sistema Buddy Mapa de Bits 0 8 16 24 32 A B C D E 1111100011111111110011111111100000111111 ¿Tamaño de la Unidad de Asignación? Pequeño ? Mapa GrandeGrande ? Mapa Pequeño? Fragmentación Interna Es caro buscar una zona libre de tamaño K.
15 Intercambio (swapping) (6)Gestión de memoria con listas enlazadas
16 Intercambio (swapping) (7) Gestión de memoria con listas enlazadas T4.4 Se trata de comparar la memoria necesaria para mantener la pista de los bloques de memoria libre utilizando un mapa de bits o una lista enlazada. La memoria es de 128 Mb y la unidad de asignación es de n bytes. Para El caso de la lista enlazada, suponer que la memoria consiste de una secuencia alternada de segmentos y huecos, cada uno de 64kb. También suponer que cada nodo en la lista necesita una dirección de memoria de 32 bits, una longitud de 16 bits y un campo (siguiente nodo) de 16 bits. ¿Cuántos bytes se necesitan para mantener el mapa de bits y cuántos para mantener la lista enlazada? ¿Qué método es el mejor?
17 Intercambio (swapping) (8) Gestión de memoria con listas enlazadas Lista de Bloques Libres (ordenados por dirección: liberación)
18 Intercambio (swapping) (9) Gestión de memoria con listas enlazadas Lista de Bloques Libres (ordenados por dirección: asignación) El primero que sirva siempre se comienza en la cabecera se generan muchos huecos pequeños al principio Siguiente que sirva lista circular; la cabecera se desplaza fragmentación externa: distribución uniforme El que mejor se adapte recorrer toda la lista: lento desperdicia más memoria El que peor se adapte no es buena idea
19 Intercambio (swapping) (10) Gestión de memoria con listas enlazadas Lista de Bloques Libres (ordenados por tamaño: asignación) Orden creciente de tamaños el primero que sirva = el que mejor se adapte siguiente que sirva no tiene sentido sobrecarga: mantener la lista ordenada en: asignación y liberación (¿compactar con vecinos?) Algoritmo Quick Fit lista separadas por tamaño (2k, 4k, …) asignación rápida; liberación: compactación Cada nodo de la lista puede ser el propio bloque
20 Intercambio (swapping) (11) T4.5 Considerar un sistema de intercambio en el que la memoria consiste de Los siguientes huecos (en tamaño) en el siguiente orden en memoria: 10kb, 4kb, 20kb, 18kb, 7kb, 9kb, 12kb y 15kb ¿Qué hueco se elegirá para Satisfacer la próxima petición de memoria: 12kb 10kb 9kb Para los algoritmos: El primero que sirva El que mejor se adapte El que peor se adapte El siguiente que sirva 20, 10, 18 12, 10, 9 20, 18, 15 20, 18, 9
21 Memoria Virtual (1) Se ocupa de tener la memoria de un proceso partida en trozos, e ir cargando en memoria principal el trozo que es necesario para poder continuar su ejecución. No es necesario tener todo el programa en memoria RAM Se podrían ejecutar programas mayores que la RAM Se podrían tener más procesos en memoria principal Menos E/S por intercambio: más velocidad Trozos Iguales Trozos de tamaño variable PAGINACIÓN SEGMENTACIÓN
22 Memoria Virtual (2). Paginación Posición y función de la MMU
23 La memoria virtual se divide en páginas La memoria física en marcos de página tamaño página = tamaño marco Conversión: MOV REG, 0 – Dirección 0 está en página 0 – Página 0 está en marco 2 – Dirección física es 8192 MOV REG, 8192 – Dirección 8192 está en página 2 – Página 2 está en marco 6 – Dirección física es 24576 ¿ MOV REG, 32780 ? Memoria Virtual (3). Paginación
24 Memoria Virtual (4). Paginación 32780 está en la página 8 (32768) La página tiene X La MMU genera un TRAP FALTA de PÁGINA: Elegir víctima Escribir a disco (si hace falta) Cargar la nueva página. Reiniciar MOV REG, 32780 P.ejem: Víctima la del marco 1. ¿escribir? Indicar que página 1: X Cargar página 8 en marco 1. Indicar que página 8 en marco 1 Reiniciar MOV REG, 32780 Dirección física: 4108
25 Memoria Virtual (5). Paginación
26 Memoria Virtual (6). Tabla de páginas Tabla de páginas: marco = TP (página) Tamaño de la tabla Velocidad de traducción C P U Pag . 0 Pag . 1 Pag . 2 Pag . 3 . . . . . . . . . . . . . . . . . . . . . Pag . n Espacio de Direcciones Virtuales Marco 0 Marco 1 Marco 2 . . . . . . . . . . . . Marco m dir . virtual dir . física Memoria Principal Tabla de Páginas
27 Tamaño de la tabla: Direcciones virtuales = 32 bits (232 = 4Gb) Si tamaño página = 4Kb (212) Número de páginas = 232/212 = 220 = 1Mg = nº de entradas TP Dirección virtual = 64 bits (264) Si tamaño de página = 4Kb (212) Número de páginas = 264/212 = 252=222*230=222 G = 4,5 Peta entradas = 4,5 * 1015 entradas Cada proceso tiene su propia tabla de páginas. El nº de entrada * tamaño (bytes) de cada entrada. Memoria Virtual (7). Tabla de páginas
28 Memoria Virtual (8). Tabla de páginas Tablas de página multinivel: – Evita mantener todas las tablas de página en memoria 4 Mb (210*212=22*220) Texto Datos Stack Gap
29 (Gp:) 3 2 1 0 (Gp:) 1023 (Gp:) 4Mb (4194304)) (Gp:) 12288 Memoria Virtual (9). Tabla de páginas dirección virtual: 0x00403004 (4206596, 0000 0000 0100 0000 0011 0000 0000 0100) PT1 = 0000 0000 01 (4M-8M) PT2 = 00 0000 0011 nº marco (Gp:) + dir. física Offset = 0000 0000 0100 Solo cargadas 4 TP
30 Estructura de una entrada: Número de marco en el que reside Presente/ausente: 1 está; 0 no está. Protección: 0 RW; 1 R o RWX Modificada (bit de ensuciado): 1 sucia; 0 limpia Referenciada: 0 cuando se carga; 1 cuando RW. Para sustitución Caching disabled: máquinas con E/S mapeada en memoria. No usar una copia vieja de la caché (de la página que contiene la memoria E/S) 32 bits aprox. Memoria Virtual (10). Tabla de páginas
31 Memoria Virtual (11). Tabla de páginas T4.13 Una computadora con direcciones de 32 bits utiliza una tabla de páginas de dos niveles. Las direcciones virtuales se dividen en un campo de 9 bits para la tabla de nivel superior y un campo de 11 bits para la tabla de nivel secundario; el resto es para el desplazamiento dentro de una página. ¿Cuál es el tamaño de la página? ¿Cuántas páginas existen en el espacio virtual de direccionamiento?
32 Memoria Virtual (12). TLB Tabla de páginas: Velocidad de traducción Una instrucción: 1, 2 o más referencias a memoria Cada referencia a memoria: consulta a la TP Soluciones: Todas las entradas en registros Muy caro (hw) Mucho tiempo en cambio contexto Toda la tabla en memoria (de todos los procesos) Registro RBTP (Registro Base de la Tabla de Páginas) Dir. Entrada = [RBTP] + (nº.pag * tamaño de la entrada) Cambio de contexto: recargar RBTP Mantener en memoria sólo la TP del proceso ejecutándose ¿Otras soluciones?
33 Localidad referencial TLB (Translation Lookaside Buffers) (memoria asociativa) dentro de la MMU Memoria Virtual (13). TLB (La sección “Software TLB Management” no entra para el examen)
34 Memoria Virtual (14) T4.17 En un ordenador los procesos tienen un espacio de direccionamiento de 1024 páginas y mantienen en memoria su tabla de páginas. La sobrecarga por lectura de una palabra desde la tabla de páginas es de 5 ns. Para reducir esta sobrecarga, el ordenador tiene una TLB con 32 entradas (página virtual, num. marco) que tarda 1 ns en realizar una consulta. ¿Cuál debe ser la tasa de aciertos en dicha memoria asociativa para reducir la sobrecarga a 2 ns.?
35 Memoria Virtual (15)Tabla invertida de páginas Tabla de páginas: Velocidad de traducción (Proceso, página virtual)
36 Memoria Virtual (16). T4.21 Un ordenador con páginas de 8kB, memoria principal de 256MB y un espacio de direccionamiento virtual de 64GB, utiliza una tabla invertida de páginas para implementar su memoria virtual. ¿Cómo de grande debería ser la tabla hash para asegurar que por término medio la cadena hash tiene una longitud menor que 1? Suponga que el tamaño de la tabla hash es potencia de 2.
37 Memoria Virtual (17) T4.12 Una máquina tiene un espacio de direcciones de 32 bits y una página de 8k. la tabla de páginas está en hardware, con una palabra de 32 bits por cada entrada. Al iniciar un proceso, la tabla de páginas se copia al hardware desde la memoria, con una palabra cada 100ns. Si cada proceso se ejecuta durante 100ms (incluyendo el tiempo de carga de la tabla de páginas), ¿cuál es la fracción del tiempo de CPU que se dedica a la carga de las tablas de páginas?
38 Algoritmos de sustitución de páginas (1) Se produce una falta de página y no hay memoria libre: Elegir victima Llevar victima a disco (si sucia) En TP: victima no presente Traer nueva página al marco donde estaba la víctima Actualizar TP: nueva está presente y marco y demás info ¿Cómo elegir la víctima? Algoritmos de sustitución de página Problemas similares: Memoria caché Caché de un servidor web
39 Objetivo de todos los algoritmos de sustitución: Elegir páginas que generen el menor número de faltas de página. En todos los algoritmos hay una constante: el nº de marcos existentes Algoritmo Óptimo de sustitución de páginas Quitar la página que tardará más tiempo en ser referenciada Imposible implementar Algoritmos de sustitución de páginas (2)
ESTA PRESENTACIÓN CONTIENE MAS DIAPOSITIVAS DISPONIBLES EN LA VERSIÓN DE DESCARGA