Paginación multinivel en el sistema operativo

Requisito previo: paginación 

La paginación multinivel es un esquema de paginación que consta de dos o más niveles de tablas de páginas de forma jerárquica. También se conoce como paginación jerárquica. Las entradas de la tabla de páginas de nivel 1 son punteros a una tabla de páginas de nivel 2 y las entradas de las tablas de páginas de nivel 2 son punteros a una tabla de páginas de nivel 3 y así sucesivamente. Las entradas de la tabla de páginas del último nivel almacenan la información real del marco. El nivel 1 contiene una tabla de una sola página y la dirección de esa tabla se almacena en PTBR (registro base de la tabla de páginas).

¿Por qué se requiere?

Si el tamaño del marco de la memoria principal es más pequeño que el tamaño de la página y el proceso no puede ajustarse de esa manera, dividimos las páginas en más páginas, y este concepto se conoce como paginación multinivel.

Dirección virtual: 

In multilevel paging whatever may be levels of paging, all the page tables will be stored in the main memory. So it requires more than one memory access to get the physical address of the page frame. One access for each level is needed. Each page table entry except the last level page table entry contains the base address of the next level page table. 

Referencia al marco de página real: 

• Referencia a PTE en la tabla de páginas de nivel 1 = valor de PTBR + compensación de nivel 1 presente en la dirección virtual.
• Referencia a PTE en la tabla de páginas de nivel 2 = Dirección base (presente en PTE de nivel 1) + compensación de nivel 2 (presente en VA). 
• Referencia a PTE en la tabla de páginas de nivel 3 = Dirección base (presente en PTE de nivel 2) + compensación de nivel 3 (presente en VA). 
• Dirección de marco de página real = PTE (presente en el nivel 3). 
   

Generalmente, el tamaño de la tabla de páginas será igual al tamaño de la página. 

Suposiciones: 
Byte de memoria direccionable y n es el número de bits utilizados para representar la dirección virtual. 

Fórmula importante: 
 

Number of entries in page table: 
= (virtual address space size) / (page size) 
= Number of pages

Virtual address space size: 
= 2n B 

Size of page table: 
<>= (number of entries in page table)*(size of PTE) 

Si el tamaño de la tabla de páginas es > el tamaño deseado, cree 1 nivel más. 

Desventaja: las 
referencias de memoria adicionales para acceder a las tablas de traducción de direcciones pueden ralentizar los programas por un factor de dos o más. Utilice el búfer de búsqueda de traducción (TLB) para acelerar la traducción de direcciones almacenando las entradas de la tabla de páginas. 

Ejemplo: 
P. Considere un sistema de memoria virtual con una memoria física de 8 GB, un tamaño de página de 8 KB y una dirección virtual de 46 bits. Suponga que cada tabla de páginas cabe exactamente en una sola página . Si el tamaño de entrada de la tabla de páginas es 4B, ¿cuántos niveles de tablas de páginas se necesitarán? 

Explicación: 

Page size = 8KB = 213 B
Virtual address space size = 246 B
PTE = 4B = 22 B

Number of pages or number of entries in page table, 
= (virtual address space size) / (page size) 
= 246B/213 B 
= 233 

Tamaño de la tabla de páginas, 

= (number of entries in page table)*(size of PTE) 
= 233*22 B 
= 235 B 

Para crear un nivel más,  

Size of page table > page size

Number of page tables in last level, 
= 235 B / 213 B 
= 222 

La dirección base de estas tablas se almacena en la tabla de páginas [penúltimo nivel]. 

Size of page table [second last level] 
= 222*22B 
= 224B 

Para crear un nivel más, 
Tamaño de la tabla de páginas [penúltimo nivel] > tamaño de página  

Number of page tables in second last level 
= 224B/213 B 
= 211 

La dirección base de estas tablas se almacena en la tabla de página [tercer último nivel]  

Size of page table [third last level] 
= 211*22 B 
= 213 B 
= page size 

∴ Se requieren 3 niveles.