Gestión de Memoria Virtual
Introducción
Objetivo: Mantener la ilusión de que la memoria física es mayor de lo que es en realidad.
Características: Solo parte del programa tiene que estar a la vez en memoria. El espacio lógico de direcciones puede ser mucho mayor que el espacio físico. Permite a los procesos compartir espacios de direcciones. Permite una creación más eficiente de procesos. Pueden ejecutarse varios procesos a la vez aunque la suma de sus requisitos totales de memoria sea mayor que la memoria disponible. Permite aumentar el grado de multiprogramación. Menos E/S necesaria debido a cargar o hacer swap de procesos.
Espacio de direcciones lógico (o virtual)
La memoria virtual implica la separación de la memoria lógica de la memoria física. La memoria lógica de un proceso se inicia en 0 y se guarda en posiciones de memoria contiguas. La memoria principal se organiza en marcos. La MMU debe traducir memoria lógica a memoria física. Puede ser implementada vía: Paginación bajo demanda, Segmentación bajo demanda.
Espacio de direcciones lógico de un proceso
Diseño habitual del espacio de direcciones lógicas: La pila empieza en la dirección lógica máxima y crece hacia abajo. El heap crece hacia arriba. Características: Maximiza el uso del espacio de direcciones. El espacio de direcciones no utilizado entre los dos es parte del espacio de direcciones virtuales. No se necesita memoria física para ese espacio hasta que el heap o la pila crezcan. Los espacios de direcciones virtuales que incluyen huecos se denominan dispersos (sparse). Ventaja: se pueden llenar a medida que crecen los segmentos, o se pueden vincular de forma dinámica a ellos bibliotecas.
Memoria virtual. Uso compartido de páginas
La memoria virtual permite que dos o más procesos compartan ficheros y memoria mediante el uso compartido de páginas. Compartir bibliotecas del sistema. Compartir memoria entre procesos. Compartir páginas durante la creación de un proceso, para acelerar su creación.
Apartado 2: Paginación bajo demanda
Cargar una página en memoria solo cuando es necesario. Se necesita menos E/S. Se necesita menos memoria. Respuesta más rápida. Permite más usuarios. Mientras se ejecuta un proceso, algunas páginas estarán en memoria y otras estarán en almacenamiento secundario. Necesidad de soporte HW: bit válido/inválido: Válido: la página asociada es legal y está en memoria. Inválido: la página no es válida (es decir, no está en el espacio de direcciones lógicas del proceso), o es válida pero está en disco (almacenamiento secundario). Marcar una página como inválida no tiene ningún efecto si nunca se intenta acceder a dicha página.
Gestión de fallos de página
Si el marco al que se quiere acceder no se encuentra en memoria principal → Fallo de página. Atención del SO a la interrupción de fallo de página: 1. El SO comprueba que la dirección es válida. 2. Si la referencia es inválida, termina el proceso. Si no está en memoria, interrupción del sistema operativo. 3. Busca un marco libre. 4. Saca página del disco y la deja en marco libre. 5. Actualiza información. 6. Continúa ejecución de la instrucción en la que se produjo el fallo.
Aspectos de la paginación bajo demanda
Paginación bajo demanda pura: no tener nunca una página en memoria hasta que sea demandada. Un proceso empieza a ejecutarse sin páginas. La primera instrucción a ejecutar provocará un fallo de página. Se traerán solo las que se necesiten. Los programas tienden a tener una localidad de referencia que hace que la paginación bajo demanda tenga un rendimiento aceptable. HW necesario para ofrecer paginación bajo demanda: Tabla de páginas que debe tener la capacidad de marcar una entrada como válida/inválida. Memoria secundaria, denominada swap device, para contener aquellas páginas que no están en memoria principal (la sección del disco usada para paginación se llama swap space). Reinicio de la instrucción: necesitamos volver exactamente al mismo punto y estado. Se puede solucionar a nivel de microcódigo o usando registros temporales.
Rendimiento de la paginación bajo demanda
Tiempo de acceso efectivo EAT (effective access time): medida del rendimiento de un sistema: EAT = (1 − p) * ma + p * tfp donde p: probabilidad de fallo de página. ma: tiempo de acceso a memoria principal. tfp: tiempo necesario para servir un fallo de página.
Tiempo necesario para servir un fallo de página. Componentes principales: 1. Servir la interrupción del fallo de página. 2. Leer la página (↑↑↑ tiempo). 3. Reiniciar el proceso.
Ejemplo: Datos: Tiempo acceso a memoria: 200ns. Tiempo medio de servicio de fallo de página: 8ms. EAT = (1 − p) * 200ns + p * 8ms = 200 + p * 7999800ns. Si p = 1 1000 → EAT = 8,2μs → degradación por un factor de 40. Si queremos una degradación de como máximo un 10 %: 200 + p * 7999800.
Apartado 3: Copy-on-write
Copy-on-write (COW): Tradicionalmente, fork creaba una copia del proceso padre, duplicando las páginas. Para evitar gasto innecesario de memoria, 2 opciones.
Copy-on-write: Permite a padre e hijo compartir páginas inicialmente. Cuando alguno de los dos modifica una página compartida, esta se copia.
Uso de vfork: Variación de fork. El sistema suspende al padre y el proceso hijo usa el espacio del padre. Diseñado para que el proceso hijo llame inmediatamente a exec. Muy eficiente.
Lista de marcos libres: Habitualmente, los SOs mantienen una lista de páginas libres. Para mayor rapidez, se asigna una página de un pool de páginas libres. Estas páginas son borradas previamente (zero-fill-on-demand). Implicaciones de seguridad si esto no se hiciese.
Apartado 4: Reemplazo de páginas
Sobreasignación de memoria (Over-allocation): Si se aumenta el grado de multiprogramación, se puede producir una sobreasignación de memoria. Ejemplo: sistema de 40 marcos con 6 procesos de 10 páginas que usan 5 cada uno. Si se dejan 10 páginas como excedente, mejor utilización y rendimiento de la CPU. Si todos estos procesos necesitan a la vez las 10 páginas en algún momento → necesidad de 60 páginas cuando solo hay 40 disponibles. Además, la memoria del sistema no se usa solo para páginas de procesos de usuario, también como buffers de E/S.
Sobreasignación
¿Cómo sabemos que hay sobreasignación? Mientras se ejecuta un proceso se produce un fallo de página. El SO determina dónde reside la página deseada en disco (almacenamiento secundario), pero no hay marcos libres.
¿Qué puede hacer el SO? Puede terminar el proceso. No es la mejor opción. La paginación debe ser transparente al usuario. Puede hacer swap-out de todo el proceso para reducir el nivel de multiprogramación. Tampoco una buena opción en todas las situaciones. La mayoría de los SOs combinan swapping con reemplazo de páginas.
Reemplazo de páginas: Evitar la sobreasignación de memoria modificando la rutina de servicio de fallo de página para incluir el reemplazo de la página. Usar el bit de modificación (dirty bit) para reducir sobrecargas por transferencias de páginas (E/S). Solo las páginas modificadas se escriben en el disco. El reemplazo de páginas (y los algoritmos de reemplazo de páginas) completa la separación entre memoria lógica y memoria física. Memorias virtuales grandes pueden ser soportadas en memorias físicas pequeñas.
Reemplazo de páginas básico
Algoritmo: 1. Encontrar la ubicación de la página deseada en disco. 2. Encontrar un marco libre: 1. Si hay uno libre, usarlo. 2. Si no, usar un algoritmo de reemplazo de página para seleccionar un marco víctima. 3. Escribir el marco víctima en disco (si es necesario. Usar dirty bit). Modificar las tablas de páginas y marcos. 3. Leer la página deseada en el marco recién liberado; modificar las tablas de páginas y de marcos. 4. Continuar con la ejecución del proceso desde donde ocurrió el fallo de página.
Algoritmos de reemplazo de páginas y marcos
Asignación de marcos: Determina cuántos marcos asignar a cada proceso y qué marcos reemplazar.
Reemplazo de páginas: Objetivo: conseguir una mínima probabilidad de fallo, tanto en el primer acceso como en accesos subsiguientes.
Evaluación de los algoritmos: Se evalúan con una carga real. Se usa una cadena de referencias a números de páginas (físicas). Ejemplo que se usará: 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1. El resultado dependerá del número de marcos disponibles. Ejemplo que se usará: 3 marcos. Algoritmos: FIFO, Óptimo, LRU (y aproximaciones) y algoritmos de frecuencia.
FIFO: Se reemplaza siempre la más antigua. Implementación sencilla: puede usarse una cola. Se reemplaza siempre la página en la cabeza de la cola. Cuando una página se trae a memoria se inserta al final. Problemas: Anomalía de Belady: aumentar el número de marcos puede bajar el rendimiento.
%IMAGE1%
FIFO. Anomalía de Belady
Ejemplo para la cadena: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. El número de fallos para 4 marcos (10) es mayor que para 3 marcos (9).
%IMAGE2%
Algoritmo OPT (óptimo): Reemplaza la página que no se utilizará durante el mayor período de tiempo. Garantiza la tasa de fallos de página más baja posible para un número fijo de marcos. No sufre de la anomalía de Belady. No es fácil aplicarlo. No se puede conocer el futuro. Se usa para realizar estudios de comparación con otros algoritmos.
%IMAGE3%
Algoritmo LRU (Least Recently Used): Reemplaza la página que lleva sin usarse más tiempo. Usa el pasado cercano como predicción del futuro cercano. Se considera un buen algoritmo. No sufre de la anomalía de Belady. Difícil de implementar.
%IMAGE4%
Posibles implementaciones Algoritmo LRU
Implementación con contador: En cada entrada de la tabla de páginas hay una variable para un contador. Cada vez que hay una referencia a esa página, se copia el valor del reloj en el contador. Página a sustituir: aquella con contador más bajo. Inconvenientes: Se debe copiar el reloj en cada acceso. Se necesita buscar aquel con el contador más bajo.
Implementación con una pila: Pila implementada con una lista doblemente enlazada de pares página/marco. Cada acceso a una página → mueve la página a la cima de la pila. Página a sustituir: aquella situada en el fondo de la pila. Inconvenientes: Cada acceso requiere modificar, en el peor de los casos, 6 punteros.
Aproximaciones a LRU
Bit de referencia: Presente en muchos sistemas. 1 bit de referencia asociado a cada entrada en la tabla de páginas. Cada vez que se accede a la página, se pone a 1. Después de cierto tiempo, sabemos a qué páginas se ha accedido. Necesitaríamos saber también el orden.
Bits de referencia adicionales: Podemos usar 1 byte por cada página. Interrupción temporizada cada X tiempo. Shift a la derecha. Descarta el bit menos significativo. Contiene el historial de acceso de los últimos 8 ciclos. Se podría reemplazar aquellas páginas con un número menor. Los números no son únicos (más de una página puede tener el mismo valor). Reemplazar (swap-out) todas las páginas con el menor número, o FIFO para elegir entre ellas.
Aproximaciones a LRU. Algoritmo de segunda oportunidad: Algoritmo de reemplazo FIFO. Solo 1 bit de referencia. El HW actualiza a 1 el bit de referencia de la página cuando accedo. Página a sustituir: La más antigua en memoria, si su bit es 0. Si su bit es 1 (la he usado hace poco), le doy una segunda oportunidad. Pongo bit a 0. Modifico tiempo de llegada para que sea el actual. Busco la siguiente página más antigua (según FIFO), con las mismas reglas. Se puede implementar con una lista circular.
Mejora al algoritmo de segunda oportunidad: Uso de bit de referencia + bit de modificación (dirty bit). (0,0): ni usadas ni modificadas. Las mejores para ser reemplazadas. (0,1): no usada, sí modificada. Se deben guardar en memoria antes del reemplazo. (1,0): usada, pero no modificada. Probablemente se usará pronto. (1,1): usadas y modificadas. Se usará pronto y debemos escribirla a memoria. Da preferencia a las páginas modificadas.
Algoritmos de frecuencia: También llamados Counting-based. Mantienen un contador con el número de referencias a una página.
LFU (Least Frequently Used): Sustituye la página con menor contador. Problema: expulso a las páginas que acabo de traer y las que se han usado mucho durante el arranque no se expulsan nunca. No respeta la localidad temporal.
MFU (Most Frequently Used): Sustituye la página con mayor contador. Problema: expulso las páginas más frecuentes. Son costosos de implementar. No son usados habitualmente.
Algoritmos adicionales
Lista de marcos libres: Cuando hay un fallo de página… Se selecciona una víctima a ser desalojada. La página deseada se lee a un marco libre antes de que se desaloje a la víctima. Cuando se pueda, se desaloja a la víctima y se añade ese marco a la lista. Si hay un marco libre disponible, se usa este. Permite que el proceso se restaure lo más rápido posible.
Lista de páginas modificadas: Cuando el dispositivo de paginación esté inactivo. Una página modificada (dirty bit==1) se selecciona, se copia al sistema de almacenamiento y se actualiza su dirty bit a 0. Incrementa la posibilidad de que una página no necesite ser copiada a memoria cuando sea reemplazada.
Mantener la referencia a la antigua página: En la lista de marcos libres, no borrar el contenido y mantener la referencia a la página anterior. Cuando hay un fallo de página, se comprueba si está en la lista de marcos libres y si es así, se usa ese. Baja la penalización si se selecciona de forma incorrecta a una página víctima.
Interferencia con aplicaciones: Todos estos algoritmos hacen que el SO intente adivinar los futuros accesos a las páginas del sistema. Sin embargo, algunas aplicaciones poseen un mayor conocimiento que el SO. Por ejemplo, las bases de datos. Las aplicaciones con uso intensivo de memoria pueden causar un doble buffering. Sin embargo, algunas aplicaciones poseen un mayor conocimiento que el SO. El SO mantiene una copia de la página en la memoria como buffer de E/S. La aplicación mantiene la página en la memoria para su propio trabajo. Solución: el sistema operativo puede dar acceso directo al disco, saliendo del camino de las aplicaciones. Modo raw disk.
Apartado 5: Asignación de marcos
Asignación de marcos: Cada proceso necesita un mínimo de número de marcos para ejecutarse. Definido por la arquitectura. Ejemplo: Una instrucción codificada en 4 bytes accede a un byte en memoria, se necesitan 3 marcos (2 para la instrucción y otro para el dato). Si se permiten varios niveles de indirection, puede subir exponencialmente. Número máximo de marcos: Definido por la cantidad de memoria física disponible. Dos esquemas principales de asignación.
Reparto fijo: Equitativo: a todos los procesos se les asigna el mismo número de páginas. Proporcional: se asigna más a quien más necesita.
Reparto por prioridades: Es un reparto proporcional que usa prioridades en vez de tamaño. Cuando un proceso Pi tiene fallo de página: Se selecciona una de sus páginas como reemplazo. Se selecciona una página de un proceso con menor prioridad.
Asignación global o local: Asignación global: Selecciona un marco de reemplazo de todo el conjunto de marcos disponibles. Un proceso puede coger un marco de otro proceso. El tiempo de ejecución de un proceso puede variar mucho. Puede tener muchos fallos de memoria en una ejecución, pocos en la siguiente. El conjunto de páginas en memoria de un proceso ya no depende de él mismo. Muy buen rendimiento → es el que más se usa. Asignación local: Se circunscribe a su propio conjunto de páginas. Es más consistente con respecto al rendimiento de un proceso. Puede infrautilizar memoria.
Apartado 6: Hiperpaginación o Vapuleo (Thrashing)
Concepto: Si un proceso no tiene suficientes páginas → Alta frecuencia de fallo de página. Mucho tiempo perdido en acceso a disco → poco uso de CPU. El proceso se pasa más tiempo paginando que ejecutando.
Causas: El SO monitoriza la utilización de la CPU: Si la utilización es baja, se aumenta el grado de multiprogramación, añadiendo más procesos al sistema. Uso de un algoritmo de reemplazo de páginas global.
Limitando los efectos del vapuleo
Uso del conjunto de trabajo de un proceso: No admitir más procesos que aquellos que van a estar cómodamente con la memoria disponible. Se necesita calcular el conjunto de trabajo (working-set): Cantidad de memoria utilizada por un proceso en un intervalo dado (localidad). Comparando la suma de los working-sets de los procesos con la cantidad de memoria disponible veo si puedo admitir a más procesos. Utilizo bit de referencia y un temporizador cíclico.
Uso de la frecuencia de fallo: Ciclo de histéresis a partir de la frecuencia de fallos de página. Para decidir si se pueden añadir más procesos. Para calcular el número de marcos a asignar por proceso. Si el ratio de fallo de páginas es bajo → se le retira un marco. Si el ratio de fallo de páginas es alto → se le asigna un marco libre.
Gestión de Memoria Principal
Apartado 1: Introducción y conceptos básicos
Existen múltiples procesos que comparten el procesador. La CPU solo puede acceder de manera directa a memoria principal y registros. Los accesos a registro son rápidos (1 ciclo de CPU o menos). Accesos a memoria más lentos (pueden llevar varios ciclos). Se suele usar memoria caché entre registros y memoria principal. La memoria es un recurso limitado que debe ser compartido también. Es necesario gestionar el uso de la Memoria Principal. Es necesario proveer de protección entre usuarios.
Hardware básico para protección de la memoria: Un par de registros define el espacio de direcciones. Para cada acceso a memoria la CPU debe comprobar si está dentro de los límites para ese usuario.
Asignación de memoria código y datos: Al programar se suelen usar símbolos o referencias implícitas para posiciones de datos, saltos (ifs, whiles, etc.) int a; a = a + 1; Código compilado, normalmente, asocia estas posiciones de datos o código a direcciones reubicables (y relativas) ej. 14 bytes desde el inicio de este módulo. Para ejecutar es necesario que el procesador conozca estas direcciones de forma absoluta. Ej. 74014. Esta asociación entre dirección reubicable y dirección absoluta, normalmente la realiza el linker o el loader.
¿Cuándo traducir referencias a direcciones?
En tiempo de compilación: Sí se sabe a priori que parte de la memoria se va a usar. Se genera código con direcciones absolutas. Se debe recompilar si la localización cambia. Ej: programas .COM en MS-DOS.
En tiempo de carga: No se sabe a priori que parte de la memoria se va a usar. El código debe ser reubicable. Se debe recargar el código de usuario si la localización cambia.
En tiempo de ejecución: El código puede cambiar de sitio durante la ejecución. Necesita HW especial. Registro base + registro límite.
Espacio de direcciones lógico y físico
Espacio de direcciones lógico (o virtual): Las direcciones generadas por la CPU.
Espacio de direcciones físico: Las direcciones vistas desde la memoria.
Pueden ser diferentes. Depende del modelo de asignación de memoria a código y datos usado: En tiempo de compilación y en tiempo de carga: son iguales. En tiempo de ejecución: diferentes.
Unidad de Gestión de Memoria (Memory Management Unit, MMU): Dispositivo HW encargado de la traducción en tiempo de ejecución del espacio lógico al físico. Suele ser un chip separado o viene incorporada al microprocesador. Gestiona: La caché de traducción de direcciones (TLB) (lo veremos en paginación). Fallos de memoria (lo veremos en memoria virtual).
Ejemplo de MMU básica
Reubicación dinámica usando un registro de reubicación: El valor del registro de reubicación se añade a todas las direcciones generadas por el proceso en el momento que se envían a memoria. Ej: MS-DOS en la familia de procesadores Intel 80×86 usaba 4 registros de reubicación.
El programa nunca ve las direcciones físicas reales. Solo trata con direcciones lógicas. La localización final de una referencia no se sabe hasta que la referencia se ejecuta.
Carga dinámica de código (Dynamic loading)
Objetivo: No tener todo un programa en memoria si no es necesario.
Proceso: Unidad de carga: rutina (función/método). Solo se carga en memoria cuando se necesita. Todas las rutinas se guardan en memoria en un formato reubicable. El programa principal se carga en memoria. Cuando se llama a una rutina, se comprueba si está ya en memoria. Si no está, se carga en memoria y se actualizan las tablas de direcciones. Las rutinas que no se usan, no se cargan nunca. El sistema operativo ofrece un cargador dinámico. No hace falta ningún recurso especial. Responsabilidad del programador diseñar los programas de forma adecuada.
Enlazado dinámico (Dynamic linking)
Objetivos: Ahorrar espacio cuando se comparte código. Facilitar el cambio de versiones (no hace falta enlazar los programas). Orientado a bibliotecas del lenguaje o bibliotecas del sistema operativo. Sin esto, se deberían incluir en los ejecutables una copia de las bibliotecas del lenguaje que usen, desperdiciando disco duro y memoria principal.
Proceso: Se realiza en tiempo de ejecución. Previamente, se incluye un stub en el ejecutable por cada referencia a función de biblioteca. Stub: trozo de código que indica cómo localizar en memoria la rutina si ya está en memoria o cómo cargarla si no está en memoria. En la primera ejecución de un stub: Se cargará la rutina si no estaba en memoria. El stub se reemplaza por la dirección en la que está la rutina y la ejecuta. Observaciones: No sustituye al enlazado de código dentro de un programa o de datos. Exige gestión para versiones incompatibles de librerías.
Apartado 2: Intercambio (Swapping)
La memoria que ocupa un proceso (código y datos) pueden transferirse temporalmente a disco. En parte o en su totalidad. Estrictamente, swapping es intercambiar procesos. Parece que el sistema tiene tanta memoria como la física + el espacio que reservo en disco para swapping.
Consideraciones
Uso del almacenamiento de respaldo: El almacenamiento de respaldo (backing store) debe de ser rápido. Tener espacio suficiente para acomodar copias de todas las imágenes de memoria de todos los usuarios. Proveer de acceso directo a dichas imágenes de memoria. Las escrituras en disco son lentas. Tiempo en hacer swapping proporcional a la cantidad de memoria transferida a disco.
¿Un proceso debe volver a cargarse al mismo sitio en memoria? Depende del tipo de asignación de memoria a código y datos. Si se hace en tiempo de compilación o de carga, debe volver al mismo lugar. Si se hace en tiempo de ejecución, puede cargarse en otra posición de memoria.
Tiempo de cambio de contexto: Si el planificador selecciona un proceso P1 para pasar a la CPU y no está en memoria: Se debe hacer swap out de un proceso P2 que sí está en memoria. Hacer swap in de P1. El tiempo de cambio de contexto puede ser muy alto. Ejemplo: procesos de 100MB y disco duro con transferencia de 50MB/s. Tiempo de swap out: 2000ms. Tiempo de swap in: 2000 ms. Cambio de contexto: 4s (solo este componente). Reducir el tiempo de swapping si se intercambia solo la memoria usada (no la reservada para ese proceso). El proceso debe informar al SO en todo momento de sus requisitos de memoria.
Operaciones de entrada/salida pendientes: Un proceso P1 pide una operación de E/S indicando la posición de los datos en memoria. Si se permite realizar swapping a ese proceso, puede ser que la operación de E/S se realice sobre esa posición de memoria cuando ya no pertenece a P1. Soluciones: No permitir hacer swapping a un proceso con operaciones de E/S pendientes. Transferir siempre E/S a espacio de kernel, y de ahí al dispositivo de E/S → añade overhead. Versiones de swapping presentes en distintos SOs. UNIX: Deshabilitada normalmente. Se habilita cuando la memoria asignada pasa de un límite determinado. Se deshabilita otra vez cuando la carga del sistema se reduce.
Apartado 3: Distribución de la memoria (Asignación contigua)
Asignación contigua: Es necesario dejar espacio en la memoria para el SO y los distintos procesos de usuario. Uno de los métodos más antiguos: asignación contigua. Normalmente la memoria principal tiene dos particiones. Zona para el Sistema Operativo: Donde esté almacenado el vector de interrupciones. Normalmente en posiciones bajas de la memoria. Zona para programas de usuario: Cada proceso está contenido en una única sección de memoria (contigua). Tipos: Modelo de partición única: un único proceso ocupa toda la memoria excepto el espacio reservado para el sistema operativo. Modelo de particiones múltiples: se divide la memoria en múltiples particiones que pueden ser de tamaño fijo o variable. Necesita HW para la protección evitar que los usuarios interfieran unos con otros o con el SO.
Ejemplo de hardware para protección entre usuarios y SO: El espacio de direcciones definido por los registros: Registro límite: rango de direcciones límite. Registro de reubicación: inicio de la partición. Cuando la CPU selecciona un proceso para la ejecución, durante el cambio de contexto el dispatcher cambia los valores de estos registros. La MMU mapea las direcciones de forma dinámica. Puede permitir cambiar de tamaño al kernel añadiendo o quitando funcionalidades.
Modelo de particiones múltiples: El grado de multiprogramación está limitado por el número de particiones. Particiones de tamaño variable (ajustadas a las necesidades de cada proceso) → aumenta la eficiencia. Hueco: bloque de memoria disponible. Huecos de tamaño variable dispersos por la memoria. Cuando un proceso llega, se le asigna memoria de un hueco lo suficientemente grande como para cubrir sus necesidades. Cuando un proceso termina, libera su partición, que se une a las particiones libres adyacentes. El SO mantiene información acerca de: particiones asignadas y huecos.
Particiones múltiples: reserva de espacio: ¿Cómo encontrar un espacio de un tamaño dado en memoria? Estrategias para seleccionar un espacio disponible: El primero que quepa (first-fit): Busco ordenadamente entre los huecos, y reservo el primero que es suficientemente grande. El hueco que ajuste mejor (best-fit): Busco el menor hueco de todos los que se ajustan al tamaño requerido. El hueco que ajuste peor (worst-fit): Reservo el hueco mayor de todos los disponibles. First-fit es más rápido. Best-fit y first-fit hacen mejor uso de memoria. Best-fit y first-fit sufren de fragmentación externa.
Particiones múltiples: fragmentación interna
Definición: La memoria que se devuelve al realizar una petición puede ser mayor que la petición. Por ejemplo, memoria reservada en múltiplos de 4 (o en bloques de 256). La diferencia es la memoria perdida.
Particiones múltiples: fragmentación externa
Definición: Existe memoria libre suficiente para satisfacer una petición, pero los trozos de memoria disponibles NO son contiguos. La memoria está fragmentada en un número elevado de huecos pequeños.
Regla del 50 % (first-fit): Para servir a N procesos, se necesita espacio para 1, 5N procesos. En promedio un tercio de la memoria no se puede usar.
Soluciones: Compactación: Agrupar huecos. Solo es posible si se puede reubicar código en tiempo de ejecución. Permitir que el espacio de direcciones lógico no sea asignado contiguamente en la memoria. Paginación y segmentación.
Apartado 4: Paginación (Paging)
Paginación
Método básico: Dividir memoria física en bloques de tamaño fijo: marco. Tamaño del marco: una potencia de 2 (usualmente entre 512 bytes y 16MB). Dividir memoria lógica en bloques de tamaño igual al del marco: página. Tanto los marcos como las páginas están alineados. Para ejecutar un proceso de tamaño N páginas, necesito encontrar N marcos libres y cargar el programa. Un proceso puede solicitar un fragmento (en el espacio lógico de direcciones) contiguo de un cierto tamaño. El fragmento puede no ser contiguo en espacio físico de direcciones. Se necesita una tabla de páginas para traducir direcciones lógicas en direcciones físicas. Ventaja: eliminó fragmentación externa. Desventaja: aumento fragmentación interna (bloque del tamaño de la página).
Hardware básico
La dirección de memoria generada por la CPU está dividida en: Número de página (p): usado como índice en la tabla de páginas, la cual contiene el registro base para cada página en memoria física. Desplazamiento (d): combinado con el registro base, define la dirección física que se manda a memoria.
Ejemplo (mínimo): Tamaño memoria principal: 32 bytes (f + d = 5). Tamaño del espacio lógico: 16 bytes (p + d = 4). Tamaño página/marco: 4 bytes (d = 2). Número de páginas posibles en MP: 8 (f = 3).
Calculando la fragmentación interna Ejemplo: Tamaño página/marco: 2.048 bytes. Tamaño del espacio lógico (del proceso): 72.766 bytes. 35 páginas + 1.086 bytes. Fragmentación interna: 2.048 – 1.086 = 962 bytes. En el peor caso: 1 marco – 1 byte. En media: 1/2 tamaño del marco. Compromiso entre menor tamaño de página y memoria adicional necesaria para gestionarla. Algunos SOs admiten varios tamaños de página. Solaris: 2 tamaños de página.
Implementación de la tabla de páginas: Supongamos tabla de páginas en memoria principal. Implementaciones: Array de marcos: direccionando por número de página, obtengo marco. Problema: Ocupa mucho espacio. No todos los identificadores de página se utilizan. Tabla con pares identificador de página / marco. Registro base de la tabla de páginas (Page-table base register, PTBR): comienzo de la tabla de páginas. Registro longitud de la tabla de páginas (Page-table length register, PTLR): tamaño de la tabla de páginas. Bit válido/inválido. Problema: dos accesos a memoria por cada lectura. Se ralentiza la memoria por un factor de 2. Solución: meter tabla de páginas en memoria caché. Aprovechando el principio de localidad, solo es necesario guardar un subconjunto. Los pares (página, información asociada) que no quepan estarán en Memoria Principal.
Caché de direcciones (TLB): La MMU contiene una caché de direcciones: TLB (Translation Lookaside Buffer). La TLB suele ser totalmente asociativa (aunque puede tener otras políticas). Búsqueda paralela en pares clave-valor. Clave: identificador de página. Valor: número de marco. La búsqueda es rápida, pero el HW es caro. Características habituales: Tamaño de la TLB entre 32 y 1024 entradas (128 B a 8 KB). 1 entrada: 4 a 16 bytes. Tiempo de acierto: 1/2 a 1 ciclo de reloj. Penalización por fallo: 4 a 16 ciclos de reloj. Frecuencia de fallo: 0,01 % – 0,1 %.
Cambio de contexto: Cambio de contexto: Cada proceso puede tener su tabla de páginas propia. Cada proceso puede tener su espacio (lógico) de direcciones propio. Cambio de proceso implica: Cambiar PTBR y PTLR. Posiblemente fallos en la TLB.
Protección de la memoria con paginación
Protección: Aislamiento entre procesos: Una página física privada de un proceso solo está en su tabla de páginas. Un proceso no puede acceder al espacio de otro (o al del SO). Bits de permisos especiales (necesita soporte en la MMU): Lectura, escritura, ejecución. Bit válido-inválido.
Compartición de la memoria con paginación: Compartición: Dos procesos pueden tener en su tabla el mismo marco (con igual o distinto identificador de página). Comparto datos o código. Necesidad de sincronización y/o exclusión mutua. O código reentrante (i.e. no se automodifica).
Estructura de la tabla de páginas
Problemática: Actualmente HW ofrece soporte para espacios de direcciones lógicos muy grandes (de 232 a 264). La tabla de páginas en estos casos puede ser muy grande a su vez. No queremos guardarla en memoria principal (ocupando espacio…).
Ejemplo: Sistema de 32 bits. Tamaño de página 4KB (212). Tabla de páginas puede tener ≈ 1 millón de entradas (232/212). Si cada entrada en la página de tablas 4 bytes → necesario 4MB de espacio físico solo para la tabla de páginas.
Soluciones: Tabla de páginas multinivel (o jerárquicas). Tablas Hash (uso de Hash en las tablas de páginas). Tablas de páginas inversas.
Tabla de páginas multinivel: Tabla de páginas en dos niveles. Se divide el espacio lógico de direcciones en múltiples páginas. Se pagina la tabla de páginas. Problemas: Se requiere un mayor número de traducciones por cada acceso. No adecuado para arquitecturas de 64 bits.
Ejemplo para una arquitectura de 32 bits y tabla de páginas de dos niveles: Dirección lógica usando paginación dividida en: Número de página (p): 22 bits. Desplazamiento (d): 10 bits. Como la tabla de páginas también está paginada, p está dividida en: Número de página (p1): 12 bits. Desplazamiento (p2): 10 bits.
Tabla de páginas hasheada (Hashed Page Tables): Común en espacios de direcciones > 32 bits. Organización: El valor de hash es el número de página virtual. Cada entrada en la tabla de hash es una lista enlazada. Cada elemento de la lista enlazada: Número de página virtual. El marco al que corresponde. Un puntero al siguiente elemento de la lista.
Tabla de páginas inversas
Array con una entrada por marco. Dirección lógica: pid: identificador del proceso al que pertenece el marco. p: número de página. d: desplazamiento. Idea: indexar por marcos, en vez de por páginas. Ventaja: Menor número de entradas. Inconveniente: Hay que buscar (proceso lento). Uso de hash tables. Uso de TLB.
Apartado 5: Segmentación (Segmentation)
Segmentación: Esquema alternativo a la paginación. Los segmentos pueden tener cualquier tamaño. Criterio para definir un segmento: modelo de programación. Un segmento es una unidad lógica: Programa principal. Método, procedimiento, función. Objeto. Pila. Variables locales, globales. Arrays, etc.
Ejemplo
Tenemos 5 segmentos, numerados del 0 al 4. La tabla de segmentos contiene una entrada por segmento: Base: dónde empieza el segmento. Límite: tamaño del segmento. El segmento 2 empieza en la posición 4300, tiene una longitud de 400 bytes. Una dirección dada por se mapeará al byte 53 del segmento 2, es decir, la posición 4300 + 53 = 4353. Una dirección dada por, resultará en un trap del sistema operativo, pues ese segmento solo tiene 400 bytes.
Ventajas e inconvenientes
Ventajas: Más sencilla la gestión de la protección: Cada entrada en la tabla de segmentos tiene: Bit validación: si está a 0, el segmento es ilegal. Privilegios de lectura/escritura/ejecución. Los bits de protección se asocian a segmentos completos. La compartición de código se realiza a nivel de segmento.
Inconvenientes: Más complicada de gestionar la gestión dinámica de la memoria: Como los segmentos tienen tamaño variable, la sustitución de un segmento en memoria puede no ser inmediata (sí lo es en esquemas que usen paginación). Se requieren dos palabras para formar una dirección.
Apartado 6: Criterios comparación
Selección de estrategias de gestión de memoria: Selección de estrategia: Puede usarse paginación, segmentación o una mezcla de ambos. Elección condicionada por el hardware disponible. Para cada dirección de memoria generada por la CPU: Debe comprobarse su legalidad. Debe mapearse a una dirección física. Las comprobaciones necesarias no se pueden hacer de forma eficiente vía SW. → Es necesario disponer del HW necesario.
Criterios de comparación entre estrategias de gestión de memoria (I)
Hardware: Para esquemas de particiones múltiples o sencillos: un registro base o un par de registros base-límite. Para paginación-segmentación: necesarias tablas de mapeado para definir el mapa de direcciones.
Rendimiento: A mayor complejidad del algoritmo → más tiempo necesario para mapear una dirección lógica a una dirección física. La suma o comparación son operaciones rápidas. Paginación y segmentación: Rápidas si la tabla de mapeado está implementada en registros rápidos. Si la tabla está en memoria, se degrada el rendimiento. Rendimiento mejora si se usan búferes (TLB).
Un sistema multiproceso o multihilo suele ser más eficiente cuanto más nivel de multiprogramación exista. Dado un conjunto de procesos, se puede aumentar el nivel de multiprogramación, aumentando el número de procesos en memoria.
Fragmentación (externa e interna): Para aumentar el número de procesos en memoria se debe reducir la fragmentación de la misma. Sistemas con tamaño fijo de unidad (paginación, partición simple): fragmentación interna. Sistemas con tamaño variable (segmentación, particiones múltiples): fragmentación externa.
Posibilidad de reubicación en tiempo de ejecución: Para reducir la fragmentación externa. Compactar el programa en memoria sin que este lo note. Si solo se puede reubicar en tiempo de carga, no se puede compactar de esta manera.
Posibilidad de realizar swapping: En momentos determinados por el SO: Los procesos se transfieren temporalmente a una memoria de apoyo, para luego devolverlos a memoria principal. El SO es capaz de asignar más memoria de la que tiene → aumenta el número de procesos en memoria → aumenta el nivel de multiprogramación. Puede añadirse a cualquier algoritmo.
Posibilidad de compartir memoria: Si los usuarios pueden compartir código y datos, pueden acomodarse más procesos en memoria → aumenta el nivel de multiprogramación. Debe usarse paginación o segmentación, para ofrecer unidades a compartir (segmentos o páginas) entre usuarios.
Protección ofrecida: Si se implementa paginación o segmentación, diferentes secciones del programa pueden ser declaradas solo-lectura, solo-escritura o lectura-escritura. Restricción necesaria con código o datos compartidos. Útil para ofrecer en tiempo de ejecución comprobaciones sencillas de errores de programación comunes.