In Operating System, we have concept of multilevel paging. I understand it, but what I don’t quite get is until when we keep doing paging? I saw some articles which say keep applying paging on page table until we can fit it in one frame (of RAM). Is this true?
I asked some people and they say it’s wrong concept.
Can anyone please clarify this doubt? It would increase credibility if you could also provide some standard resource (like a book of any author recognized by many universities) which mentions about this. An answer with all cases and explanation would be appreciated.
The number of levels in a multilevel paging system is determined by the size of the virtual address space, the page size, and the architecture of the system. In theory, there can be as many levels as needed to break down the virtual address space, but in practice, the number is limited by performance and architectural constraints.
We can come up with a formula for this
Number of paging levels = Bits in Virtual Address / Bits for Page Table Indexing
-For 32-bit Architecture:
You have a 32-bit virtual address space and a page size of 4 KB (which is 2^12 bytes). That leaves 20 bits for page table indexing.
If each page table entry is 4 bytes, the page table can hold 2^10 (1024) entries.
You can divide the 20-bit address space into two 10-bit fields, so a 2-level paging scheme works.
For a 64-bit system with a 4 KB page size, you have 52 bits for page table indexing (64 bits total minus 12 bits for the page offset).
If the page table has 512 entries per table (9 bits per level, assuming 8 bytes per page table entry), this would typically result in a 4-level paging scheme, as 52 bits can be split into four 9-bit fields (each for one level).
x86-64 typically uses 4-level paging (in Linux and Windows) with 512 entries per page table as follows
Level 1 (PML4 table): 9 bits
Level 2 (Page Directory Pointer Table): 9 bits
Level 3 (Page Directory): 9 bits
Level 4 (Page Table): 9 bits
Remaining bits: 12 bits for the page offset.
ARM architecture might use 3 or 4 levels, depending on the configuration (e.g., using a 39-bit or 48-bit virtual address space).
In theory, you could continue adding levels as needed, but each additional level increases the memory access time for address translation, which is why more than 4 or 5 levels are uncommon in practice. Excessive levels would lead to inefficient performance due to multiple memory lookups.
Besides performance overhead, managing multiple levels of paging adds complexity to the OS’s memory management subsystem
In modern systems, typically 3 to 5 levels of paging are used depending on the architecture and the size of the virtual address space.