Paginación de memoria

En sistemas operativos de computadoras, los sistemas de paginación de memoria dividen los programas en pequeñas partes o páginas, lo que vendría siendo la memoria lógica. Del mismo modo, la memoria "física" es dividida en trozos del mismo tamaño que las páginas llamados marcos de página. Ambos tipos de bloques son del mismo tamaño. De esta forma, al ejecutar un proceso, sus páginas se cargan desde el almacén de respaldo a los marcos disponibles. Además, la cantidad de memoria desperdiciada por un proceso es el final de su última página, lo que minimiza la fragmentación interna y evita la externa.

La fragmentación externa y, por tanto, la necesidad de compactación puede evitarse por completo empleando la paginación. Ésta consiste en que cada proceso está dividido en varios bloques de tamaño fijo llamados páginas, dejando de requerir que la asignación sea de un área contigua de memoria. La memoria se presentará a cada proceso como si fuera de su uso exclusivo. La memoria física se divide en una serie de marcos (frames), todos ellos del mismo tamaño, y el espacio para cada proceso se divide en una serie de páginas (pages), del mismo tamaño que los marcos. La MMU se encarga del mapeo entre páginas y marcos mediante tablas de páginas.

Tanto el tamaño de las páginas como de los marcos de páginas es definido por el hardware y suele ser una potencia de 2. Sabiendo entonces que muchos sistemas soportan un gran espacio de direcciones lógicas esto haría que nuestra tabla de páginas (la estructura de datos que sirve para conocer donde está el marco en el que se haya cargado una cierta página) sea excesivamente grande. Como una alternativa a esta situación, se propone "paginar las tablas de páginas", es decir, se divide a la tabla de páginas en fragmentos más pequeños.

El procedimiento para determinar el número de página asociado a una localidad de memoria específica es realizado por medio de la operación módulo, mediante el residuo es posible asociar los datos con el marco y la tabla de páginas. En general calcular el valor del módulo para la derivación de claves resulta muy eficiente porque necesita poco costo (computacional, de memoria). La operación módulo también sirve para validar qué páginas son reales y cuáles no; cabe recordar que la memoria virtual se presenta como lo máximo que la arquitectura ofrece como una dirección de memoria; por tanto, no todas las páginas son verdaderas; para determinar cuáles páginas pueden ser direccionadas por la memoria física (limitada por número de pines), se realiza la operación módulo.

En un momento cualquiera, la memoria se encuentra ocupada con páginas de diferentes procesos, mientras que algunos marcos están disponibles para su uso. El sistema operativo mantiene una lista de estos últimos marcos, y una tabla por cada proceso, donde consta en qué marco se encuentra cada página del proceso. De esta forma, las páginas de un proceso pueden no estar continuamente ubicadas en memoria, y pueden intercalarse con las páginas de otros procesos.

En la tabla de páginas de un proceso, se encuentra la ubicación del marco que contiene a cada una de sus páginas. Las direcciones lógicas ahora se forman como un número de página y de un desplazamiento dentro de esa página (conocido comúnmente como offset). El número de página es usado como un índice dentro de la tabla de páginas, y una vez obtenida la dirección del marco de memoria, se utiliza el desplazamiento para componer la dirección real o dirección física. Este proceso se realiza en una parte del computador específicamente diseñada para esta tarea, es decir, es un proceso hardware y no software.

De esta forma, cuando un proceso es cargado en memoria, se cargan todas sus páginas en marcos libres y se completa su tabla de páginas.

Veamos un ejemplo:

La tabla de la derecha muestra una posible configuración de la memoria en un momento dado, con páginas de 4Kb. La forma en que se llegó a este estado puede haber sido la siguiente:

Se tienen cuatro procesos, llamados A, B, C y D, que ocupan respectivamente 3, 2, 2 y 3 páginas.

1. El programa A se carga en memoria (se le asignan los marcos 0, 1 y 2)
2. El programa B se carga en memoria (se le asignan los marcos 3 y 4)
3. El programa C se carga en memoria (se le asignan los marcos 5 y 6)
4. El programa B termina, liberando sus páginas
5. El programa D se carga en memoria (se le asignan los marcos 3 y 4 que usaba el proceso B y el marco 7 que permanecía libre)

De esta forma, las tablas simplificadas de cada proceso se ven de esta forma:

Ahora consideremos qué sucede cuando un programa quiere acceder a su memoria. Si el programa A contiene una referencia a la memoria con dirección 20FE, se realizará el siguiente procedimiento. 20FE es 0010000011111110 en notación binaria (en un sistema de 16 bit), y en el ejemplo se están usando páginas de 4Kb de tamaño. Cuando la petición de la dirección de memoria 20FE es realizada, la Unidad de Gestión de memoria se ve de esta forma:

0010000011111110 = 20FE
|__||__________|
 |       |
 |       v
 |      Posición de memoria dentro de la página (0FE)
 v
Número de página (0010 = 2)

* n = bits de la @ lógica -log2(número de palabras de una página).
* V: bit de validez.
* P: bit de persistencia.
* L: bit de derecho a lectura.
* E: bit de derecho a escritura.
* M: bit de modificación.

Al usar páginas de 4096 bytes, todas las ubicaciones dentro de una página pueden ser representadas por 12 bits, en el sistema binario (2¹²=4096), lo que deja 4 bits para representar el número de página. Si las páginas hubieran sido de la mitad del tamaño (2048) se podrían tener 5 bits para el número de página, lo que significa que a menor tamaño de página se pueden tener tablas con más páginas.

Cuando el pedido de acceso a memoria es realizado, la MMU busca en la tabla de páginas del proceso que realizó el pedido por la relación en memoria física. En nuestro ejemplo, la página número 2 del proceso A corresponde al marco número 2 en memoria física, con dirección real 1000:2000, por lo tanto, la MMU devolverá la dirección del marco en memoria física, con el desplazamiento dentro de esa página: 1000:20FE.