Tabla de paginación

Las tablas de paginación o tablas de páginas son una parte integral del Sistema de Memoria Virtual en sistemas operativos, cuando se utiliza paginación. Las tablas son mantenidas por el sistema operativo y utilizadas por la Unidad de Gestión de Memoria (MMU) para realizar las traducciones de direcciones de memoria virtual (o lógica) a memoria física y en general el sistema operativo mantiene una por cada proceso corriendo en el sistema.

Las traducciones de memoria paginada toman las direcciones lógicas y por medio de la tabla de páginas se obtiene las direcciones físicas reales.

En cada entrada de la tabla de paginación (en inglés PTE, Page Table Entry) existe un bit de presencia, que está activado cuando la página se encuentra en memoria principal. Otro bit que puede encontrarse es el de modificado, que advierte que la página ha sido modificada desde que fue traída del disco, y por lo tanto deberá guardarse si es elegida para abandonar la memoria principal; y el bit de accedido, usado en el algoritmo de reemplazo de páginas llamado Menos Usado Recientemente (LRU, least recently used). También podría haber otros bits indicando los permisos que tiene el proceso sobre la página (leer, escribir, ejecutar).

Dado que las tablas de paginación pueden ocupar un espacio considerable de la memoria principal, estas también podrían estar sujetas a paginación, lo que da lugar a una organización paginada de múltiples niveles (o tabla de páginas multinivel). En los sistemas con un tamaño de direcciones muy grande ( 64 bits ), podría usarse una tabla de páginas invertida, la cual utiliza menos espacio, aunque puede aumentar el tiempo de búsqueda de la página.

Definiciones

Marcos o páginas físicas: Porciones de memoria física.
Número de página física: Número del marco.
Proceso: Es un flujo de ejecución, es un programa en ejecución y tiene asignado una página física, como contiene un espacio de páginas lógicas. De hecho, cada proceso tiene su tabla de páginas.
Mapeado: Asignación de una página lógica. Ocurre igual que en los videojuegos cuando asignamos una tecla a una acción.
Páginas lógicas: Están mapeadas a un marco (porción de memoria física).
Tabla de páginas: Formada por el mapeo entre páginas físicas y lógicas.

Proceso de traducción

La unidad de administración de memoria (MMU) dentro de la CPU almacena un caché de asignaciones utilizadas recientemente de la tabla de páginas del sistema operativo. Esto se denomina búfer de búsqueda de traducción (TLB), que es un caché asociativo. Cuando es necesario traducir una dirección virtual a una dirección física, primero se busca la TLB. Si se encuentra una coincidencia, lo que se conoce como coincidencia de TLB, se devuelve la dirección física y puede continuar el acceso a la memoria. Sin embargo, si no hay ninguna coincidencia, lo que se denomina falla de TLB, la MMU o el controlador de fallas de TLB del sistema operativo normalmente buscará la asignación de direcciones en la tabla de páginas para ver si existe una asignación, lo que se denomina recorrido de página. Si existe, se vuelve a escribir en la TLB, lo que debe hacerse porque el hardware accede a la memoria a través de la TLB en un sistema de memoria virtual, y se reinicia la instrucción que falla, lo que también puede ocurrir en paralelo. La traducción posterior dará como resultado un acierto de TLB y el acceso a la memoria continuará.

Funcionamiento

Conexión entre páginas virtuales y las páginas físicas, la memoria física puede contener páginas de distintos procesos. Las páginas se pueden almacenar en el disco si se usan con poca frecuencia o si la memoria física está llena.

Se debe hacer referencia a dos funciones esenciales:

Transforma una dirección virtual a física
Transfiere páginas de la memoria secundaria a la memoria principal y viceversa.

El traductor de memoria paginada toma la dirección lógica y, por medio de la tabla de páginas, obtiene la dirección física real. Los bits más significativos de una dirección lógica representan el número de página lógica, los menos significativos el desplazamiento dentro de la página. Concretamente, en un procesador de 32 bits, con un tamaño de página de 4Kb = 2^12, se emplean 12bits para el desplazamiento dentro de la página. Es decir, para referenciar los datos que una página contiene. Los restantes 20 bits más significativos indican el número de página.

Las páginas cuentan con mecanismos de protección, expresados en bits de lectura, escritura y ejecución, esto permite definir páginas de sólo lectura, por ejemplo, para almacenar datos con un valor predefinido (constantes). Páginas de sólo lectura y ejecución, para almacenar código, así como páginas de lectura y escritura para la pila del proceso. Si se accede a una página lógica que no existe en la tabla de páginas de un determinado proceso, el sistema lanza una excepción que finaliza de la ejecución del proceso.

Elementos de administración

Para mantener la contabilidad de marcos libres se pueden emplear estructuras de datos tales como:

Mapa de bits de marcos libres: Que contiene 1 si está asignada a un proceso, o 0 si está libre.
Lista de marcos libres: Hay una lista global de marcos libres y una lista por proceso de marcos ocupados.

Además, se puede emplear el mecanismo de los compañeros para mantener listas de varias páginas consecutivas (bloques) de tamaño con base en potencia de 2. Por ejemplo, imaginemos un sistema con páginas de 4 Bytes, bloques de 4 Kbyte (orden 0), bloques de 8 Kbyte (orden 1, dos páginas), bloques de 16 Kbyte (orden 2, cuatro páginas), bloques de 32 Kbyte (orden 3, 8 páginas) y así aumentar gradualmente.

Una reserva de página de orden 0 nunca falla a no ser que no haya memoria disponible en el sistema. La de orden 1 puede fallar si no hay dos páginas consecutivas.

El hecho de asignar páginas de manera consecutiva permite explotar mejor la propiedad de localidad espacial en el acceso a memoria.

Tabla de Páginas Multinivel

La tabla de páginas multinivel es una estructura de tabla de páginas que a su vez contiene asignaciones para páginas virtuales. Se realiza manteniendo varias tablas de páginas que cubren un determinado bloque de la memoria virtual. Por ejemplo, podemos crear páginas más pequeñas de 4KB de 1024 entradas que cubran 4 MB de memoria virtual.

Esto es provechoso, ya que, las partes superiores e inferiores de la memoria virtual se usan para ejecutar un proceso; la parte superior se usa a menudo para segmentos de texto y datos, mientras que la parte inferior para la pila, con memoria libre en el medio. La tabla de páginas multinivel puede mantener algunas de las tablas de páginas más pequeñas para cubrir solo las partes superior e inferior de la memoria y crear otras nuevas solo cuando sea estrictamente necesario. Cada una de estas tablas de páginas más pequeñas están unidas entre sí por una tabla de páginas mayor, lo que crea efectivamente una estructura de datos tipo árbol. Este modelo se puede repetir y crecer para obtener más niveles. Por ejemplo, una dirección virtual en este esquema podría dividirse en tres partes: el índice en la tabla de la página raíz, el índice en la tabla de la subpágina y el desplazamiento en esa página.

Tabla de páginas de todo el sistema: Es una variante de las tablas de página multinivel, en la que el dispositivo traductor sólo tiene una sola entrada por cada proceso, indexadas por PID, y una dirección de tabla que contiene las páginas del proceso entrante. Así, ante una conmutación de procesos basta con cambiar de PID.

Tabla de Páginas Invertida

Es una técnica de paginación donde existe una entrada por cada página real de la memoria, además, incorpora información del proceso dueño dicha página. Por lo tanto, en el sistema solo habrá una tabla de páginas invertida y esta solo tendrá una entrada por cada marco en la memoria física.

La principal ventaja de este método es que reduce la memoria física ocupada por la tabla de páginas. Por otra parte, genera una desventaja, la cual aumenta el tiempo de búsqueda de páginas, ya que, se debe verificar la tabla de páginas cada vez que hay una referencia a una página, debido a que esta se encuentra ordenada según mande la memoria física y las búsquedas se realizan según la memoria virtual. Para solucionar esta desventaja se utiliza una tabla de hash, para limitar la búsqueda a una o en el peor de los casos, unas pocas entradas de la tabla de páginas, pero cada acceso a una página requerirá dos accesos a memoria: el primero, para acceder a la tabla de hash, y el segundo, para la tabla de páginas (recordar que primero se explora un buffer TLB -Translation Lookaside Buffer- antes de consultar la tabla hash). Los sistemas que utilizan tablas de páginas invertidas tienen problemas para implementar el concepto de memoria compartida, ya que, cada entrada de la tabla de páginas invertida corresponde a solo un marco en memoria.

Tablas de páginas virtualizadas

Para crear una estructura de tabla de páginas que contenga asignaciones para cada página virtual en el espacio de direcciones virtuales se podría generar un desperdicio de espacio, podemos solucionar este problema de espacio excesivo colocando la tabla de páginas en la memoria virtual y dejando que el sistema de memoria virtual administre la memoria que requiere la tabla de páginas. Sin embargo, parte de esta estructura de tabla de páginas lineal siempre debe permanecer residente en la memoria física para evitar errores de páginas circulares y buscar una página que ya no se encuentre en la memoria.

Véase también

Referencias

Universidad de Sevilla, Ingeniería de Computadores.
Universidad del País Vasco EHU/UPV. Sistemas Operativos, ingeniería de Computadores.
Milan Milenkovic (1994). Sistemas Operativos - Conceptos y Diseño (2ª edición). Mcgraw-hill. ISBN 8448146417.
Abraham Silberschatz, Greg Gagne, Peter Baer Galvin (2006). Fundamentos de sistemas operativos (7ª edición). Mcgraw-hill. pp. 690. ISBN 8448146417.

Datos: Q1195972

Las tablas son mantenidas por el sistema operativo y utilizadas por la Unidad de Gestión de Memoria (MMU) para realizar las traducciones. Para evitar un acceso a las tablas de paginación, hay un dispositivo llamado Buffer de Traducción Adelantada (TLB, Translation Lookaside Buffer), acelerando el proceso de traducción.