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. Son usadas para realizar las traducciones de direcciones de memoria virtual (o lógica) a memoria real (o física) y en general el sistema operativo mantiene una por cada proceso corriendo en el sistema.
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.
Funcionamiento
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 en base a 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 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.
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.
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.