Transcription
Sistemas Operativos 2022Clase - 10U4 Memoria principalIng. Juan Manuel Calvo
Administración de la memoria Temas–Tareas de administración de memoria–Asignación de memoria a de la tabla de páginas–IntercambioObjetivos–Explique la diferencia entre una dirección lógica y una física y el papel de la unidad deadministración de memoria (MMU) en la traducción de direcciones.–Aplique estrategias de primer, mejor y peor ajuste para asignar memoria de forma contigua.–Explique la distinción entre fragmentación interna y externa.–Traduzca direcciones lógicas a direcciones físicas en un sistema de paginación que incluye unbúfer de búsqueda de traducción (TLB).–Describir la paginación jerárquica, la paginación hash y las tablas de páginas invertidas.
Administración de la memoria (Cont.) Para que un programa se ejecute este debe traerse desde el disco a la memoriay configurarse dentro de un proceso.El único almacenamiento que la CPU puede acceder directamente son losregistros y la memoria principal.La unidad de memoria solo ve un flujo de:–direcciones solicitudes de lectura, o–dirección datos y solicitudes de escritura El acceso al los registros se realiza en un ciclo de reloj de CPU (o menos) La memoria principal puede tomar muchos ciclos, provocando un bloqueo (stall) La caché se encuentra entre la memoria principal y los registros de la CPU Para garantizar el correcto funcionamiento es necesario un sistema deprotección de la memoria.
Protección Es necesario asegurarse de que unproceso pueda acceder solo aaquellas direcciones de su espacio.Una manera de proporcionar estaprotección mediante el uso de un parde registros base y límite que definenel espacio de direcciones lógicas delproceso.
Protección de direcciones de hardware La CPU debe verificar cada acceso a la memoria generado en el modo deusuario para asegurarse de que esté entre la base y el límite para ese usuarioLas instrucciones para cargar los registros base y límite son privilegiadas
Enlace de direcciones (Address Binding) Los programas del disco, listos para ser cargados en la memoria para ejecutarlos– Es inconveniente tener la dirección física del primer proceso de usuario siempre en 0000– Sin soporte, se cargarían en la dirección 0000¿Cómo cambiarlo?Direcciones representadas de diferentes maneras en diferentes etapas de la vida de unprograma–Las direcciones del código fuente suelen ser simbólicas–Las direcciones de código compilado se vinculan (bind) a direcciones reubicables–Ej: "14 bytes desde el comienzo de este módulo"El enlazador (linker) o cargador (loader) vinculará direcciones reubicables adirecciones absolutas Ej: 74014Cada vinculación (binding) se aplica (map) un espacio de direcciones a otro –
Enlace de las instrucciones y los datos a las posiciones de memoria El enlace de direcciones de instrucciones y datos a direcciones dememoria se puede hacer en tres etapas diferentes–Tiempo de compilación: si la ubicación de la memoria se conoce apriori, se puede generar un código absoluto; debe volver a compilarel código si cambia la ubicación inicial–Tiempo de carga: debe generar un código reubicable si la ubicaciónde la memoria no se conoce en el momento de la compilación–Tiempo de ejecución: enlace retrasado hasta el tiempo de ejecución. En este caso el proceso se puede mover durante su ejecución deun segmento de memoria a otroNecesita soporte de hardware para mapas de direcciones (porejemplo, registros base y límite)
Los varios pasos delprocesamiento de un programade usuario
Espacio de direcciones lógico vs. físico El concepto de un espacio de direcciones lógicas que está vinculado a un espaciode direcciones físicas separado es fundamental para la gestión adecuada de lamemoria.–Dirección lógica: generada por la CPU; también conocida como direcciónvirtual–Dirección física: dirección vista por la unidad de memoriaLas direcciones lógicas y físicas son las mismas en los esquemas de vinculaciónde direcciones en tiempo de compilación y en tiempo de carga; las direccioneslógicas (virtuales) y físicas difieren en el esquema de vinculación de direcciones entiempo de ejecuciónEl espacio de direcciones lógicas es el conjunto de todas las direcciones lógicasgeneradas por un programa.El espacio de direcciones físicas es el conjunto de todas las direcciones físicasgeneradas por un programa
Memory-Management Unit (MMU) Dispositivo de hardware que en tiempo de ejecución asignauna dirección virtual a una físicaSon posibles varios métodos
Memory-Management Unit (Cont.) Considere el esquema simple que es una generalización delesquema de registro base.El valor en el registro base se agrega a cada direccióngenerada por un proceso de usuario en el momento en que seenvía a la memoria.El programa de usuario trata con direcciones lógicas; nunca velas reales direcciones físicas–El enlace en tiempo de ejecución ocurre cuando se hacereferencia a la ubicación en la memoria–Dirección lógica vinculada a direcciones físicas
Memory-Management Unit (Cont.) Sigamos con el esquema simple. El registro base ahora se llama registro de reubicación El valor en el registro de reubicación se agrega a cada dirección generadapor un proceso de usuario en el momento en que se envía a la memoria.
Carga dinámica Para ejecutar un programa no es necesario que todo el código este cargado enmemoria.–En un dado momento puede estar solamente la parte que se está ejecutando–Las rutinas no se cargan hasta que son llamadas Mejor utilización del espacio de memoria; la rutinas no utilizadas nunca se cargan Todas las rutinas están guardadas en disco en formato de carga reubicable Útil cuando se necesitan grandes cantidades de código para manejar casos queocurren con poca frecuenciaNo se requiere soporte especial del sistema operativo–Implementado a través del diseño del programa.–El sistema operativo puede ayudar proporcionando bibliotecas paraimplementar la carga dinámica
Enlace dinámico Enlace estático: Las bibliotecas del sistema y el código de programa son combinadospor el cargador en la imagen del programa binarioEnlace dinámico: la vinculación se pospone hasta el momento de la ejecuciónEl stub es un pequeño fragmento de código que se utiliza para ubicar la rutina debiblioteca residente en memoria adecuadaEl stub se reemplaza a sí mismo con la dirección de la rutina y ejecuta la rutinaEl sistema operativo verifica si la rutina está en el espacio de direcciones de memoriadel proceso–Si no está en el espacio de direcciones, se la carga. La vinculación dinámica es particularmente útil para las bibliotecas Sistema también conocido como bibliotecas compartidas Es de utilidad para aplicar parches a las bibliotecas del sistema–Puede ser necesario un versionado
Asignación contigua La memoria principal debe soportar tanto con el sistema operativocomo con los procesos del usuario.–La memoria es un recurso limitado, debe asignarseeficientemente La asignación contigua es un método primitivo La memoria principal generalmente en dos particiones:–Sistema operativo residente, generalmente en memoria baja conlos vectores de interrupción–Los procesos de usuario luego se colocan en memoria alta–Cada proceso está contenido en una sola sección contigua dememoria
Asignación contigua ( Continuación) Registros de reubicación se usan para proteger los procesosde los usuarios entre sí y de cambiar el código y los datos delsistema operativo–El registro base contiene el valor de la dirección física máspequeña–El registro de límite contiene un rango de direccioneslógicas: cada dirección lógica debe ser menor que elregistro de límite–La MMU mapea direcciones lógicas dinámicamente–Puede permitir acciones como que el código del kernel seatransitorio y cambie el tamaño del kernel
Soporte de hardware para registros de límite yreubicación
Particiones variables Asignación de múltiples particiones–Grado de multiprogramación limitado por número de particiones–Tamaños de partición variables para mayor eficiencia (dimensionados según las necesidades de un procesodado)–Agujero: bloque de memoria disponible; agujeros de varios tamaños están dispersos a lo largo de la memoria–Cuando llega un proceso, se le asigna memoria desde un agujero lo suficientemente grande como paraacomodarlo.–La salida del proceso libera su partición, las particiones libres adyacentes combinadas–El sistema operativo mantiene información sobre: a) particiones asignadas b) particiones libres (agujeros)
El problema de asignación de almacenamiento dinámico ¿Cómo satisfacer una solicitud de tamaño n de una lista de agujeros libres?–Primer ajuste: asigne el primer agujero que sea lo suficientementegrande–Mejor ajuste: asigne el agujero más pequeño que sea losuficientemente grande; debe buscar en toda la lista, a menos que estéordenado por tamañoProduce el agujero sobrante más pequeño.Peor ajuste: asigne el agujero más grande; también debe buscar entoda la lista –Produce el agujero sobrante más grande.First-fit y best-fit son mejores que peor-fit en términos de velocidad yutilización del almacenamiento
Fragmentación Fragmentación externa: existe espacio de memoria total parasatisfacer una solicitud, pero no es contiguoFragmentación interna: la memoria asignada puede ser unpoco más grande que la memoria solicitada; esta diferencia detamaño es la memoria interna de una partición, pero no seutilizaAnálisis de primer ajuste revela que, dados los N bloquesasignados, se pierden 0,5 N bloques debido a la fragmentación–1/3 puede ser inutilizable - regla del 50 por ciento
Fragmentación (Cont.) la fragmentación externa se puede reducir por compactación–Reorganiza los contenidos de la memoria para juntar toda lamemoria libre en un bloque grande–La compactación es posible solamente si la reubicación esdinámica y se hace en el momento de la ejecución.–Problemas con la E/SNo mover las tareas en memoria mientras estaninvolucradas en E/S Hacer E/S solo en los búferes del sistema operativoConsidere que los archivos de intercambio pueden tener losmismos problemas de fragmentación
Paginación El espacio de direcciones físicas de un proceso puede ser no contiguo; al proceso sele asigna memoria física siempre que esta última esté disponible–Evita la fragmentación externa–Evita el problema de fragmentos de memoria de diferentes tamaños Divide la memoria lógica en bloques del mismo tamaño llamados páginas Divide la memoria física en bloques de tamaño fijo llamados marcos (frames) –El tamaño es potencia de 2, entre 512 bytes y 16 Mbytes–Se debe llevar un registro de todos los marcos libresPara ejecutar un programa de tamaño N páginas, necesita encontrar N marcos libresy cargar el programaConfigura una tabla de páginas para traducir direcciones lógicas a direccionesfísicasTodavía sufre de fragmentación interna
Esquema de traducción de direcciones La dirección generada por la CPU se divide en:Número de página (p): este se utiliza como índice en una tabla de páginasque contiene la dirección base de cada página en la memoria físicaDesplazamiento de página (d): combinado con la dirección base paradefinir la dirección de memoria física que se envía a la unidad de memoriapage number page offsetpdm -nnPara un espacio de direcciones lógicas de 2m y un tamaño de página de 2n
Hardware de paginación
Modelo de paginación de memoria lógica y física
Ejemplo de paginación Dirección lógica: n 2 y m 4. Usando untamaño de página de4 bytes y unamemoria física de 32bytes (8 páginas)
Paginación: cálculo de la fragmentación interna Tamaño de página 2048 bytes Tamaño del proceso 72.766 bytes 35 páginas 1.086 bytes Fragmentación interna de 2048 - 1086 962 bytes Fragmentación en el peor de los casos 1 marco – 1 byte Fragmentación promedio 1/2 tamaño de cuadro ¿Son deseables los marcos pequeños?– Pero cada entrada de la tabla de páginas requiere memoria paraseguirlaLos tamaños de página crecen con el tiempo
Marcos libresa) antes de la asignación.b) después de la asignación.
Implementación de la tabla de páginas La tabla de páginas se aloja en la memoria principal–El registro base de la tabla de páginas (Page-table base registerPTBR) apunta a la tabla de páginas–El registro de longitud de la tabla de páginas (Page-table lengthregister PTLR) indica el tamaño de la tabla de páginasEn este esquema, cada acceso a datos/instrucciones requiere dos accesosa la memoria.– Uno para la tabla de páginas y otro para los datos/instruccionesEl problema de acceso a dos memorias se resuelve mediante el uso de uncaché de hardware de búsqueda rápida especial llamado búfer debúsqueda de traducción (translation look-aside buffer TLB)–La TLB se implementa con una memoria asociativa
Translation Look-Aside Buffer Algunos TLB almacenan identificadores de espacio de direcciones(Address-space identifiers ASID) en cada entrada de TLB: identificande forma única cada proceso para proporcionar protección de espaciode direcciones para ese proceso.– De lo contrario hay que invalidar la TLB en cada cambio de contextoLos TLB suelen ser pequeños (de 64 a 1024 entradas)Si hay una falla en el acceso a la TLB, el valor se carga en la TLB paraun acceso más rápido la próxima vez–Se deben considerar las políticas de reemplazo.–Algunas entradas a la TLB se pueden fijar para un acceso rápidopermanente
Hardware TLB Memoria asociativa búsqueda paralelaP age # F rame #Traducción de direcciones (p, d)–Si p está en un registro asociativo, saca el marco #–De lo contrario, obtenga el marco # de la tabla de páginas en la memoria
Hardware de paginación con TLB
Tiempo efectivo de acceso Proporción de aciertos(Hit ratio): porcentaje de veces que se encuentra unnúmero de página en la TLBUna proporción de aciertos del 80 % significa que encontramos el número depágina deseado en el TLB el 80 % de las veces.Supongamos que para acceder a la memoria necesitamos 10 nseg.–Si encontramos la página deseada en TLB, entonces un acceso a la memoriamapeada tomará 10 ns–De lo contrario, necesitamos dos accesos a la memoria, por lo que son 20 ns.Tiempo de acceso efectivo (EAT)–Considere una proporción de aciertos del 99%,EAT 0,99 x 10 0,01 x 20 10,1 nslo que implica solo un 1% de ralentización en el tiempo de acceso.
Protección de memoria Protección de memoria implementada al asociar un bit de protección concada marco para indicar si se permite el acceso de solo lectura o delectura y escritura– También se pueden agregar más bits para indicar que el código de lapágina se pueda ejecutar, etc.Bit válido-no válido adjunto a cada entrada en la tabla de páginas:–"válido" indica que la página asociada está en el espacio dedirecciones lógicas del proceso y, por lo tanto, es una página legal–"no válido" indica que la página no está en el espacio de direccioneslógicas del proceso–O usando el registro de longitud de la tabla de páginas (PTLR)Cualquier violación da como resultado una trap al kernel.
Bit válido (v) o no válido (i) en una tabla de páginas
Páginas compartidas código compartido–Una copia del código (reentrante) solo lectura compartida entreprocesos–Similar a varios hilos que comparten el mismo espacio de proceso–También es útil para la comunicación entre procesos si se permitecompartir páginas de lectura y escritura.Código privado y datos–Cada proceso guarda una copia separada del código y los datos.–Las páginas para el código privado y los datos pueden apareceren cualquier parte del espacio de direcciones lógicas.
Ejemplo de páginas compartidas
Estructura de la tabla de páginas Usando métodos directos las estructuras de memoria para la paginación puedenvolverse enormes–Suponga un espacio de direcciones lógicas de 32 bits–Tamaño de página de 4 KB (212)–La tabla de páginas tendría 1 millón de entradas (2 32/212)–Si cada entrada es de 4 bytes cada proceso 4 MB de espacio dedirecciones físicas solo para la tabla de páginasNo se quiere asignar esto de forma contigua en la memoria principalUna solución simple es dividir la tabla de páginas en unidades más pequeñas – Paginación jerárquicaTablas de páginas con hashTablas de páginas invertidas
Tablas de páginas jerarquicas Dividir el espacio de direccioneslógicas en varias tablas de páginasUna técnica simple es una tabla depáginas de dos niveles.Luego paginamos la tabla de páginas
Ejemplo de paginación en dos niveles Una dirección lógica (en una máquina de 32 bits con un tamaño de página de 4K) se divide en:–un número de página que consta de 20 bits–un desplazamiento de página que consta de 12 bitsDado que la tabla de páginas está paginada, el número de página se divide en:–un número de página de 10 bits–un desplazamiento de página de 10 bitsPor lo tanto, una dirección lógica es la siguiente:Donde p1 es un índice en la tabla de páginas exterior y p2 es el desplazamiento dentro de lapágina de la tabla de página interiorConocido como tabla de páginas asignadas hacia adelante (forward-mapped page table)
Esquema de traducción de direcciones
Espacio de direcciones lógico de 64 bits Incluso el esquema de paginación de dos niveles no es suficiente Si el tamaño de la página es de 4 KB (212)–Entonces la tabla de páginas tiene 252 entradas.–Si el esquema es de dos niveles, las tablas de páginas internas podrían tener 210 entradas de 4bytes–La dirección se vería como–La tabla de páginas exterior tiene 242 entradas o 244 bytes–Una solución es agregar una segunda tabla de página externa–Pero en el siguiente ejemplo, la tabla de la segunda página exterior todavía tiene un tamaño de 234bytes. Y posiblemente 4 accesos a la memoria para llegar a una ubicación de memoria física
Esquema de paginación en tres niveles
Tablas de páginas con hash Habitual en espacios de direcciones 32 bits El número de página virtual se codifica en una tabla de páginas– Cada elemento contiene (1) el número de página virtual (2) el valor del marco de páginaasignado (3) un puntero al siguiente elementoLos números de páginas virtuales se comparan en esta cadena buscando unacoincidencia– Esta tabla de páginas contiene la cadena de elementos que se codifican en la mismaubicaciónSi se encuentra una coincidencia, se extrae el marco físico correspondienteUna variación para direcciones de 64 bits son tablas de páginas agrupadas (clusteredpage tables)–Similar a hash pero cada entrada se refiere a varias páginas (Ej: 16) en lugar de 1–Especialmente útil para espacios de direcciones dispersos (donde las referencias dememoria no son contiguas y están dispersas)
Tabla de páginas con hash
Tabla de páginas invertida En lugar de que cada proceso tenga una tabla de páginas y realice un seguimiento detodas las páginas lógicas posibles, realice un seguimiento de todas las páginas físicasUna entrada por cada página real de memoriaLa entrada consiste en la dirección virtual de la página almacenada en esa ubicaciónde memoria real, con información sobre el proceso que posee esa páginaReduce la memoria necesaria para almacenar cada tabla de páginas, pero aumenta eltiempo necesario para buscar en la tabla cuando se produce una referencia de páginaUsa la tabla hash para limitar la búsqueda a una, o como máximo, unas pocasentradas de la tabla de páginas– TLB puede acelerar el accesoPero, ¿cómo implementar la memoria compartida?–Una asignación de una dirección virtual a la dirección física compartida
Arquitectura de la tabla de páginas invertida
Intercambio ( Swapping) Un proceso puede intercambiarse temporalmente de la memoria a un almacén derespaldo y luego volverlo a la memoria para continuar su ejecución.– El espacio de memoria física total de los procesos puede exceder la memoria físicaAlmacenamiento de respaldo (Backing Store): disco rápido lo suficientemente grandecomo para acomodar copias de todas las imágenes de la memoria para todos losusuarios; debe proporcionar acceso directo a estas imágenes de memoriaRoll out, roll in: variante de intercambio utilizada para algoritmos de programaciónbasados en prioridades; el proceso de menor prioridad se intercambia para que elproceso de mayor prioridad pueda cargarse y ejecutarseLa mayor parte del tiempo de intercambio es tiempo de transferencia; el tiempo total detransferencia es directamente proporcional a la cantidad de memoria intercambiadaEl sistema mantiene una cola de procesos listos (Ready queue) para ejecutar los cualestienen imágenes de memoria en el disco
Intercambio (Cont.) ¿El proceso intercambiado debe restablecerse a las mismas direcciones físicas?–Depende del método de enlace de direccionesAdemás, considere las E/S pendientes hacia/desde el espacio de lamemoria del procesoEl intercambio completo de un proceso es demasiado lento – no se usa en los sistemas actualesVersiones modificadas se encuentran en muchos sistemas ( UNIX, Linux,Windows, etc)–Intercambio normalmente deshabilitado–Arranca si se asigna más del umbral de cantidad de memoria–Deshabilitado nuevamente una vez que la demanda de memoria se redujopor debajo del umbral
Vista esquemática del intercambio
Intercambio en sistemas móviles Normalmente no se admite–basado en memoria flashEspacio de memoria reducido Se deben limitar los ciclos de escritura de la flash Baja velocidad de transferencia entre la memoria flash y la CPUEn su lugar, si hay poca memoria se usan otros métodos para liberarla –iOS pide a las aplicaciones que renuncien voluntariamente a la memoria asignadaLos datos de solo lectura se eliminan de la RAM y se vuelven a cargar desdeflash si es necesario Si el proceso no puede liberar suficiente memoria el SO puede terminarlo.Android finaliza las aplicaciones si hay poca memoria libre, pero primero escribe elestado de la aplicación (application state) en flash para reiniciarla rápidamente. ––Ambos sistemas operativos admiten la paginación como se explica a continuación
Espacio de direcciones lógico vs. físico El concepto de un espacio de direcciones lógicas que está vinculado a un espacio de direcciones físicas separado es fundamental para la gestión adecuada de la memoria. - Dirección lógica: generada por la CPU; también conocida como dirección virtual - Dirección física: dirección vista por la unidad de memoria
