Multilevel Paging in OS

Multilevel paging is a memory management method used in operating systems (OS) to manage memory more efficiently. The page table is partitioned into numerous levels with this approach, with each level having a subset of the page table entries.

The top-level data structure in multilevel paging is the page directory. It has a set number of entries, each pointing to a page table. Each page directory entry represents a page of virtual memory, which is usually 4 KB (Kilo Byte) in size. A control register in the CPU specifies the position of the page directory in physical memory.

The above diagram shows the multi-level page tables. The page table is the second-level data structure used in multilevel paging. It contains a fixed number of entries, each of which maps a virtual page to a physical page. Each entry in the page table represents a page of virtual memory, which is also typically 4 KB (Kilo Bytes) in size. The page table is in physical memory, and its location is specified by an entry in the page directory.

 When a process seeks access to a memory location, the central processing unit constructs a virtual address that includes a page number and an offset inside the page. The page number is used to index the page directory to find the entry matching the requested page. The page directory item gives the physical location of the page table for that page.

Once the page table is located, the CPU uses the offset within the virtual address to index into the page table to find the entry corresponding to the requested memory location. The page table entry contains the physical address of the memory location.

If the page table entry is invalid, the CPU generates a page fault, which is handled by the operating system. The operating system reads the data from the disk into a free page frame in physical memory, updates the page table entry, and restarts the instruction that caused the page fault.

Multilevel paging reduces the page table and the amount of memory needed to hold it. A 32-bit address space, for example, requires a page table with 2 power 20 (1048576) entries, which necessitates 4 MB of RAM. The page directory contains just 2 power 10 (1024) items with two-level paging, and each page table has 2 power 10 (1024) entries, using only 8 KB (Kilo Bytes) of memory.

Multilevel paging also allows for more efficient use of memory. Only the pages that are currently being used by a process need to be mapped to physical memory, while the rest of the pages can remain on the disk until they are needed. This allows more processes to run simultaneously without running out of physical memory.

However, multilevel paging also increases the overhead of memory access. The operating system needs to perform multiple memory lookups to translate a virtual address to a physical address, which can slow down the system. To minimize this overhead, modern CPUs use hardware-based translation look-aside buffers (TLBs) to cache recently used translations.

 Here's an example of multilevel paging in action in an operating system:

 Assume we have a process that requires 16 GB of memory. The operating system splits the virtual address space of the process into 4 KB (Kilo Bytes) pages. A piece page is broken further into smaller pages of 1 KB (Kilo Byte) apiece, resulting in a two-level paging system.

The page directory, which comprises a list of page tables, is the initial level of the paging structure. Each page directory entry corresponds to a page table, which holds the physical addresses of the page's smaller pages.

The page table, which holds a list of page entries, is the second level of the paging structure. Each page table item corresponds to a 1 KB (Kilo Byte) page and specifies the page's physical address.

When a process wants to access a memory address, the operating system finds the corresponding page directory entry and utilizes it to find the page table. The page table entry is then used to find the physical address of the required page.

Because it only needs to allocate memory for the pages that the process actually uses, multilevel paging allows the operating system to allocate and manage memory more efficiently. It also reduces the amount of memory needed to hold the page tables since the operating system may utilize smaller page tables for each page directory entry.

Conclusion:

In conclusion, multilevel paging is a memory management method used by operating systems to handle huge amounts of memory. It involves partitioning a process's virtual address space into several pages, and each page is further divided into smaller pages, resulting in a hierarchical structure.

There are a few disadvantages to adopting tiered paging. The additional degree of indirection required to reach a memory address, for example, might result in greater overhead and longer access times. Overall, multilevel paging is a useful technique for managing large amounts of memory in operating systems, but it should be carefully considered in the context of the specific system requirements and trade-offs between performance, complexity, and memory usage.