En informática, el mecanismo de memoria virtual se desarrolló en la década de 1960 . Se basa en el uso de la traducción sobre la marcha de las direcciones (virtuales) vistas por el software a direcciones RAM físicas . La memoria virtual permite:
El artículo de referencia James Kilburn, publicado en 1962, describe la primera computadora con un sistema de administración de memoria virtual paginada que usa un tambor como una extensión de los núcleos de memoria central de ferrita : el Atlas .
Hoy en día, todas las computadoras tienen un mecanismo de administración de memoria virtual, excepto algunas supercomputadoras o sistemas integrados en tiempo real.
El principio es el siguiente:
La tabla de páginas está indexada por el número de página. Cada fila se denomina "entrada en la tabla de páginas" ( entrada de la tabla de páginas , abreviado PTE) y contiene el número de cuadro. Dado que la tabla de páginas se puede ubicar en cualquier lugar de la memoria, un registro especial (PTBR para el registro base de la tabla de páginas ) mantiene su dirección.
En la práctica, el mecanismo de traducción forma parte de un circuito electrónico denominado MMU ( unidad de gestión de memoria ) que también contiene parte de la tabla de páginas, almacenada en una memoria asociativa formada por registros rápidos. Esto evita tener que consultar la tabla de páginas (en memoria) para cada acceso a la memoria.
A continuación se muestra un ejemplo real de una máquina cuyo procesador genera direcciones virtuales de 32 bits, pudiendo así acceder a 4 GiB de memoria. El tamaño de la página es de 4 KB . De esto se deduce que el campo de desplazamiento ocupa los 12 bits menos significativos y el campo de número de página los 20 bits más significativos.
Tenga en cuenta la presencia de un campo especial que pertenece a cada PTE. Para simplificar, hemos reducido el ancho de este campo a un bit: el bit de validez . Si es 0, significa que el número de fotograma no es válido. Por tanto, es necesario adquirir una técnica que permita actualizar esta PTE para que sea válida.
Pueden ocurrir tres casos:
En los dos últimos casos, el material genera una interrupción , denominada página predeterminada (o, a veces , error de página , traducción de un error de página en inglés ) que le da la mano al sistema operativo. Este se encarga de buscar un marco disponible en la memoria principal para poder asignarlo al proceso responsable de esta falla de página, y posiblemente recargar el contenido de este marco con el contenido guardado en la memoria masiva (actualmente el disco duro en un área llamado área de permuta o permuta ).
Puede que no haya más fotogramas libres en la memoria principal: entonces está ocupada al 100%. En este caso, un algoritmo de paginación se encarga de elegir una página "víctima". Esta página se reasignará inmediatamente al proceso de solicitud o se guardará primero en el disco duro y se actualizará la entrada en la tabla de páginas que hace referencia a ella. La página de la víctima puede muy bien pertenecer al proceso que carece de espacio.
A continuación se enumeran algunos ejemplos de algoritmos. La primera línea corresponde a la cadena de referencias , es decir el orden en el que el proceso accederá a las páginas. Se supone que la memoria principal está formada por tres fotogramas . El cuadro de la víctima aparecerá subrayado. Los fallos de página iniciales no se cuentan (son idénticos en número independientemente del algoritmo elegido).
7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
7 | 7 | 7 | 2 | 2 | 2 | 2 | 2 | 7 | ||||||||||||||||||||||||||||||||
0 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | |||||||||||||||||||||||||||||||||
1 | 1 | 3 | 3 | 3 | 1 | 1 |
7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
7 | 7 | 7 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 | 7 | 7 | 7 | |||||||||||||||||||||||||
0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 1 | 1 | 1 | 0 | 0 | ||||||||||||||||||||||||||
1 | 1 | 1 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 1 |
7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
7 | 7 | 7 | 2 | 2 | 4 | 4 | 4 | 0 | 1 | 1 | 1 | ||||||||||||||||||||||||||||
0 | 0 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 0 | 0 | |||||||||||||||||||||||||||||
1 | 1 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 7 |
Puede ser relativamente fácil encontrar casos patológicos que inutilicen un algoritmo. Por ejemplo, para el algoritmo LRU, este sería un programa que usa 5 páginas en un bucle en una máquina que tiene solo 4 cuadros. Primero usará los primeros 4 fotogramas secuencialmente (1, 2, 3, 4) luego ocurrirá una falla de página y será la página 1, la más antigua cargada, la que será la víctima. Las páginas utilizadas son ahora (5, 2, 3, 4). Dado que el programa se repite, necesita la página 1 (continúa de la página 5). Esta vez, la página de la víctima es la página 2, reemplazada por 1: (5, 1, 3, 4), luego (5, 1, 2, 4), (5, 1, 2, 3), etc. Se genera un error de página en cada iteración ...
Intuitivamente, aumentar el número de marcos de página (es decir, aumentar la memoria principal) debería reducir el número de errores de página.
La anomalía de Belady (1970) es un contraejemplo que muestra que esto no es absolutamente cierto con el algoritmo FIFO , de hecho el lector podrá verificar por sí mismo que la secuencia de referencias (3, 2, 1, 0, 3, 2 , 4, 3, 2, 1, 0, 4) conduce a
Nota : el alcance de esta curiosidad no debe exagerarse. Ciertamente muestra que el algoritmo FIFO en general no tiene una propiedad que uno hubiera esperado (agregar memoria reduce las fallas de página) pero no muestra que no la tenga en promedio . Y de todos modos, el algoritmo FIFO nunca se usa para el reemplazo de páginas.
Además, se puede demostrar que determinados algoritmos de sustitución de páginas ( LRU por ejemplo) no están sujetos a este tipo de anomalías.
Los métodos de selección de la página víctima mencionados anteriormente se pueden aplicar tanto a las páginas pertenecientes a un proceso (luego se habla de “asignación local”), como a todas las páginas y por lo tanto a toda la memoria (en este caso la técnica de asignación es se dice que es "global").
En un sistema de asignación global, el tiempo de ejecución de un proceso puede variar mucho de una instancia a otra porque el número de fallas de página no depende del proceso en sí. Por otro lado, este sistema permite que evolucione el número de ejecutivos asignados a un proceso.
El siguiente diagrama muestra tres procesos en ejecución, por ejemplo, un editor de texto llamado Ed. Las tres instancias están ubicadas en las mismas direcciones virtuales (1, 2, 3, 4, 5). Este programa utiliza dos áreas de memoria distintas: las páginas que contienen el código, es decir, las instrucciones que describen el programa, y el área de datos, el archivo que se está editando. Es suficiente mantener las mismas entradas en la tabla de páginas para que las tres instancias compartan el área de código. Por otro lado, las entradas correspondientes a las páginas de datos son distintas.
Se agregan algunas protecciones de bits a cada entrada en la tabla de páginas. Entonces podemos distinguir fácilmente entre las páginas asignadas al kernel, de solo lectura, etc. Vea el ejemplo a continuación.
Hay tres problemas principales:
El comportamiento de los programas no es caótico: el programa se inicia, llama a funciones (o partes del código) que a su vez llaman a otras, etc. Cada una de estas llamadas define una región. Es probable que el programa pueda pasar mucho tiempo ejecutándose en unas pocas regiones: este es el principio de localidad. El mismo principio se puede aplicar a las páginas que contienen datos.
En otras palabras, un programa accede con frecuencia a un pequeño conjunto de páginas y ese conjunto de páginas cambia lentamente con el tiempo.
Si somos capaces de mantener en la memoria estos espacios a los que se accede con frecuencia, reducimos las posibilidades de que un programa comience a deshacerse , es decir, reclamar páginas que se acaban de eliminar recientemente.
El conjunto de trabajo: espacio de trabajoPodemos definir un parámetro, Δ, que es el número de referencias a las páginas a las que accede el proceso durante un determinado período de tiempo. La siguiente figura muestra el valor del espacio de trabajo en dos momentos diferentes:
El valor de Δ debe elegirse con cuidado: demasiado pequeño no cubre el espacio de trabajo nominal del proceso; demasiado grande incluye páginas innecesarias. Si Δ es igual a infinito, cubre todo el programa, por supuesto.
Para un solo proceso, podemos representar gráficamente cómo se le asigna la memoria y visualizar los espacios de trabajo:
Las “bandejas” son áreas donde no hay fallas de página: el espacio asignado es lo suficientemente grande para contener todos los marcos que el proceso necesita durante un tiempo relativamente largo. Las fallas de página tienen lugar en la parte ascendente de la transición, mientras que la memoria se libera cuando la curva vuelve al siguiente espacio de trabajo: la zona de equilibrio.
Depende del sistema operativo implementar los algoritmos para que el valor de Δ sea óptimo para maximizar la tasa de multiprogramación y el uso de la unidad central . En otras palabras: evita tirar basura . Si la suma de los espacios de trabajo de cada proceso es mayor que el número de marcos disponibles, necesariamente habrá colapso.
Una de las ventajas de la memoria virtual es poder iniciar la ejecución de un programa tan pronto como se cargue su primera página de códigos en la memoria. La prepaginación no solo cargará la primera página, sino las siguientes, que tienen una probabilidad muy alta de ser accedidas.
Máquina | Espacio direccionable | Campos de número de página | Campos "Desplazamiento" |
---|---|---|---|
Atlas | 11 | 9 | |
PDP-10 | 9 | 9 | |
IBM-370 | 13 o 12 | 11 o 12 | |
Pentium Pro | 12 o 20 | 20 o 12 | |
Alpha 21064 | 13 | 30 |
Los campos M, U, N y NDP solo son válidos si el bit V es 1. Cuando V es 0, el campo NDP contiene la dirección en el disco duro donde se encuentra la página.
Valor | Proteccion |
---|---|
0000 | Sin acceso |
1000 | Leer para el kernel |
1100 | Leer / escribir para el kernel |
1010 | Lectura de usuario y kernel |
1110 | Lectura de usuario, lectura / escritura de kernel |
1111 | Lectura / escritura de usuario y kernel |
Bit 24, N ( N on-hidden), significa que la página no está almacenada en caché y el sistema debe leer o escribir directamente desde o hacia la memoria.
El M ( M odified) bit es modificado por el hardware, si el contenido de la página se modifica.
El bit U ( U tilisée) indica si la página ha sido leída o escrita por un proceso. Es útil, en asociación con los demás, para determinar el conjunto de trabajo de un proceso (ver arriba).
La segmentación proporciona una vista de la memoria más coherente con la del usuario. De hecho, éste no considera (¡o rara vez!) La memoria como una serie de páginas, sino más bien como espacios o regiones, destinados a un uso particular, por ejemplo: el código de un programa, los datos, la pila, un conjunto de subrutinas, módulos, una matriz, etc. La segmentación refleja esta organización.
Cada objeto lógico será designado por un segmento. En un segmento, el direccionamiento se realizará mediante un desplazamiento. El par (segmento, desplazamiento) se traducirá en una dirección de memoria mediante una tabla de segmentos que contiene dos campos, límite y base . La base es la dirección de inicio del segmento y limita la última dirección del mismo segmento:
Los sistemas paginados tienen un problema de fragmentación interna : se desperdicia espacio al final de una página. Los sistemas segmentados tienen un problema de fragmentación externa : los espacios entre los segmentos son demasiado pequeños para acomodar nuevos fragmentos, por lo que se desperdicia espacio.
Es posible recuperarlo compactando la memoria, es decir, moviendo los segmentos - reflejando estas modificaciones en las tablas de los segmentos - para que sean contiguos. Sin embargo, esta operación es cara.
Es posible compartir segmentos entre procesos, como se muestra en la figura siguiente, donde dos procesos Ed1 y Ed2 comparten el mismo segmento de código (programa) pero tienen segmentos de datos separados de diferentes tamaños.
Esta protección estará asegurada por bits adicionales agregados en la tabla de segmentos, de la misma manera que para un sistema paginado.
El ejemplo más conocido es el Intel 8086 y sus cuatro registros:
Los sucesores del 8086 también están segmentados:
Es posible mezclar los dos modos anteriores:
A veces es necesario eliminar todas las páginas o segmentos de un proceso de la memoria principal. En este caso, se dirá que el proceso se intercambia y todos los datos que le pertenecen se almacenarán en la memoria masiva. Esto puede suceder en procesos inactivos durante mucho tiempo cuando el sistema operativo necesita asignar memoria a los procesos activos. Las páginas o segmentos de código (programa) nunca se intercambiarán , sino que simplemente se reasignarán, ya que se pueden encontrar en el archivo correspondiente al programa ( el archivo ejecutable ). Por esta razón, el sistema operativo prohíbe el acceso de escritura a un archivo ejecutable que está en uso; simétricamente, no es posible iniciar la ejecución de un archivo mientras se mantiene abierto para el acceso de escritura de otro proceso.
La compresión de la memoria virtual puede mejorar el rendimiento de un sistema de memoria virtual. Esta técnica de administración de memoria virtual utiliza la compresión de datos para reducir el tamaño o la cantidad de solicitudes de paginación hacia y desde el almacenamiento auxiliar.
En un sistema de compresión de memoria virtual, las páginas se comprimen y almacenan en la memoria física, generalmente RAM , o se envían comprimidas a un almacenamiento auxiliar, como un disco duro o SSD . En cualquier caso, el rango de memoria virtual cuyo contenido se comprimió es inaccesible, por lo que los intentos de acceder a las páginas comprimidas desencadenan errores de página y revierten el proceso de compresión (recuperando el almacenamiento auxiliar y descomprimiendo). La huella de datos paginados se reduce mediante el proceso de compresión y la memoria RAM liberada se devuelve al grupo de memoria física disponible. En caso de que las páginas comprimidas se mantengan en la memoria RAM, las páginas comprimidas obviamente utilizan menos espacio que las páginas originales. En el caso de que las páginas comprimidas se mantengan en almacenamiento auxiliar, la memoria RAM se libera por completo y las operaciones de escritura y lectura en la memoria auxiliar son más rápidas que si las páginas no se hubieran comprimido.