Tabla de páginas invertidas en el sistema operativo – Part 1

Requisitos previos: paginación , entradas de la tabla de páginas , segmentación

La mayoría de los sistemas operativos implementan una tabla de páginas separada para cada proceso, es decir, para un número ‘n’ de procesos que se ejecutan en un sistema operativo multiproceso/tiempo compartido, hay un número ‘n’ de tablas de páginas almacenadas en la memoria. A veces, cuando un proceso tiene un tamaño muy grande y ocupa memoria virtual, con el tamaño del proceso, el tamaño de la tabla de páginas también aumenta sustancialmente.

Example: A process of size 2 GB with:
Page size = 512 Bytes
Size of page table entry = 4 Bytes, then
Number of pages in the process = 2 GB / 512 B = 222
PageTable Size = 222 * 22 = 224 bytes

A través de este ejemplo, se puede concluir que para múltiples procesos que se ejecutan simultáneamente en un sistema operativo, una parte considerable de la memoria está ocupada solo por tablas de páginas. Los sistemas operativos también incorporan esquemas de paginación multinivel que aumentan aún más el espacio necesario para almacenar las tablas de páginas y se invierte una gran cantidad de memoria para almacenarlas. La cantidad de memoria ocupada por las tablas de páginas puede convertirse en una sobrecarga enorme y siempre es inaceptable ya que la memoria principal siempre es un recurso escaso. Se realizan varios esfuerzos para utilizar la memoria de manera eficiente y para mantener un buen equilibrio en el nivel de multiprogramación y uso eficiente de la CPU. 

Tabla de páginas invertidas: un enfoque alternativo es usar la estructura de la tabla de páginas invertidas que consiste en una entrada de tabla de una página para cada marco de la memoria principal. Por lo tanto, la cantidad de entradas de la tabla de páginas en la tabla de páginas invertida se reduce a la cantidad de cuadros en la memoria física y se usa una sola tabla de páginas para representar la información de paginación de todos los procesos. A través de la tabla de páginas invertida, se elimina la sobrecarga de almacenar una tabla de páginas individual para cada proceso y solo se requiere una porción fija de memoria para almacenar la información de paginación de todos los procesos juntos. Esta técnica se denomina paginación invertida ya que la indexación se realiza con respecto al número de cuadro en lugar del número de página lógica. Cada entrada en la tabla de páginas contiene los siguientes campos.

• Número de página: especifica el rango de números de página de la dirección lógica.
• ID de proceso: una tabla de página invertida contiene la información del espacio de direcciones de todos los procesos en ejecución. Dado que dos procesos diferentes pueden tener un conjunto similar de direcciones virtuales, se hace necesario en la tabla de páginas invertidas almacenar una identificación de proceso de cada proceso para identificar su espacio de direcciones de manera única. Esto se hace usando la combinación de PId y número de página. Por lo tanto, este ID de proceso actúa como un identificador de espacio de direcciones y garantiza que una página virtual para un proceso en particular se asigne correctamente al marco físico correspondiente.
• Bits de control: estos bits se utilizan para almacenar información adicional relacionada con la paginación. Estos incluyen el bit válido, el bit sucio, los bits de referencia, la protección y los bits de información de bloqueo.
• Puntero enstringdo: en ocasiones, es posible que dos o más procesos compartan una parte de la memoria principal. En este caso, dos o más páginas lógicas se asignan a la misma entrada de tabla de páginas y luego se utiliza un puntero de enstringmiento para asignar los detalles de estas páginas lógicas a la tabla de páginas raíz.

Funcionamiento: a continuación se muestra el funcionamiento de una tabla de páginas invertidas. La dirección virtual generada por la CPU contiene los campos y cada entrada de la tabla de páginas contiene otra información relevante requerida en el mecanismo relacionado con la paginación. Cuando se produce una referencia a la memoria, esta dirección virtual se compara con la unidad de mapeo de memoria (MMU), se busca en la tabla de páginas invertidas y se obtiene el número de cuadro correspondiente. Si se encuentra la coincidencia en la i ^-ésima entrada, la dirección física del proceso se envía como la dirección real; de lo contrario, si no se encuentra ninguna coincidencia, se genera una falla de segmentación. Nota: Número de entradas en la tabla de páginas invertidas = Número de cuadros en el espacio de direcciones físicas (PAS).

Ejemplos: la tabla de página invertida y sus variaciones se implementan en varios sistemas como PowerPC, UltraSPARC y la arquitectura IA-64. Una implementación del sistema operativo Mach en la RT-PC también utiliza esta técnica. 

Ventajas y desventajas:

• Espacio de memoria reducido: las tablas de páginas invertidas suelen reducir la cantidad de memoria necesaria para almacenar las tablas de páginas a un límite de tamaño de memoria física. El número máximo de entradas podría ser el número de marcos de página en la memoria física.
• Mayor tiempo de búsqueda: las tablas de páginas invertidas se ordenan por número de cuadro, pero la búsqueda en la memoria se lleva a cabo con respecto a la dirección virtual, por lo que suele llevar más tiempo encontrar la entrada adecuada, pero a menudo estas tablas de páginas se implementan utilizando estructuras de datos hash para una búsqueda más rápida.
• Implementación de memoria compartida difícil: como la tabla de páginas invertidas almacena una sola entrada para cada cuadro, se vuelve difícil implementar la memoria compartida en las tablas de páginas. Las técnicas de enstringmiento se utilizan para asignar más de una dirección virtual a la entrada especificada en el orden del número de trama.