Table of contents
1.
Introduction
2.
MultiLevel Paging
2.1.
Working
2.2.
Illustration of Multilevel Paging
2.3.
Disadvantage
3.
Frequently Asked Questions
3.1.
How do multi-level page tables save space?
3.2.
What is the primary advantage of using a two level page table?
3.3.
What is the main advantage of a multilevel page table over a single level one?
4.
Conclusion
Last Updated: Mar 27, 2024

Multilevel Paging in Operating System

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

  • Paging is a memory management strategy that avoids the necessity for contiguous physical memory allocation. This approach allows a process's physical address space to be non-contiguous.
  • Page tables are data structures that map the page number to the frame number.
  • The process of Paging is when we divide the entire procedure into equal-sized pages. In addition, each page has a set quantity of words (if it is word addressable).
  • When the size of the page table is greater than the frame size, then the page table cannot be stored in a single frame in the main memory in such a case. In such cases, we need the Multilevel paging technique.

(Also, see Need for Paging)

MultiLevel Paging

Multilevel paging is a hierarchical technique consisting of two or more layers of page tables. Level 1 page table entries are pointers to a level 2 page table, while level 2 page table entries are pointers to a level 3 page table, and so on. The actual frame information is stored in the entries of the final level page table. Level 1 has a single-page table whose address is contained in PTBR (Page Table Base Register).

 

Virtual Address

 Virtual Address       

Working

  • The page table that is larger than the frame size is divided into several parts.
  • Except for the last component, the size of each part is the same as the size of the frame.
  • The page table pages are then stored in various frames of main memory.
  • Another page table is maintained to keep track of the frames that store the pages of the divided page table.
  • As a consequence, the page table hierarchy is created.
  • Multilevel paging is carried out until the level is reached, where the complete page table can be stored in a single frame.


In multilevel paging, regardless of the levels of paging, all page tables are kept in the main memory. 

As a result, obtaining the physical address of a page frame necessitates more than one memory access. 

Each level requires one access.

Except for the last level page table item, each page table entry provides the base address of the subsequent level page table.

3 Level Paging System

 

The following is a reference to the actual page frame:

PTE reference in level 1 page table = PTBR value + Level 1 offset in virtual address

PTE reference in level 2 page table = base address (present in Level 1 PTE) + level 2 offset (present in VA).

PTE reference in level 3 page table = base address (present in Level 2 PTE) + level 3 offset (present in VA).

PTE is the actual page frame address (present in level 3).

 

The page table will usually be the same size as the page itself.
Click here to know about Process Control Block in OS 

Illustration of Multilevel Paging

Let us consider a system that employs a paging technique in which :

  • Physical Address Space = 16 TB 
  • Physical Address Space = 16 TB 
  • 4 KB page size


Let us now determine how many levels of page tables will be needed.

The number of bits in a physical address:

 Main memory size = Physical Address Space = 16 TB = 244 B

 As a result, the physical address contains 44 bits.

The number of frames in the main memory:

Frames in main memory = main memory size / frame size = 16 TB / 4 KB =  232 frames

As a result, the number of bits in a frame number equals 32 bits.

The number of bits in the page offset:

We have a page size of = 4 KB = 212 B.

As a result, the number of bits in page offset equals 12 bits.

Alternatively,

The number of bits in the page offset

= The number of bits in the physical address − the number of bits in the frame number

= 44 bits - 32 bits =12 bits

Thus, the physical address is :

Physical Address

Number of Pages of Process:

The Number of pages in which the process is divided

= Process size / Page size =  4 GB / 4 KB 

= 220 pages 

Inner Page Table Dimensions:

The inner page table maintains track of the frames that hold the process pages.

Inner Page table size  = The number of entries in the inner page table X the size of the page table entry

= Number of pages in which the process is divided x Number of bits in frame number

= 220 x 32 bits = 220 x 4 bytes = 4 MB

We can now observe:

The inner page table is larger than the frame size (4 KB).

 As a result, the inner page table cannot be stored in a single frame.

As a result, the inner page table must be divided into pages.

The number of pages of the inner page table

The number of pages in which the inner page table is divided 

= Inner page table size / Page size

= 4 MB / 4 KB = 210 pages

These 210 pages of the inner page table are now stored in various frames of th main memory.

Number of Page Table Entries on One Inner Page Table Page:

The number of page table entries on a single page of an inner page table

= Size of a page / Size of a page table entry

= Page size / the number of bits in the frame number

= 4 KB / 32 bits = 4 KB / 4 B = 210

Number of bits required to search an entry in one Page of an Inner Page Table

There are 210 entries on one page of the inner page table.

Thus, The number of bits needed to search for a specific entry in one page of an inner page table = 10 bits.

Outer Page Table Size

The outer page table is needed to maintain track of the frames that store the pages of the inner page table.

Size of outer page table

 = number of entries in outer page table X  Page table entry size

 = number of pages in which the inner page table is divided X number of bits in frame number

= 210 x 32 bits = 210 x 4 bytes = 4 KB

Now we can see that 

  • The size of the outer page table is the same as the size of the frame (4 KB).
  • As a result, the outer page table may be stored in a single frame.
  • As a result, we will have two levels of page tables for the specified system.
  • The base address of the outer page table will be stored in the Page Table Base Register (PTBR).


The number of bits required to search for an entry in an outer page table

The outer page table has 210 entries.

Thus, the number of bits necessary to search for a certain entry in the outer page table is equal to 10 bits. 

As demonstrated below, the paging system will look like this:

 

Paging System

Disadvantage

Programs can be slowed by a factor of two or more when there are extra memory references to access address translation tables. We may speed up the address translation by saving page table entries in a translation lookaside buffer (TLB).

You can also read about the interleave memory.

Must Read Evolution of Operating System

Frequently Asked Questions

How do multi-level page tables save space?

The page table has four entries, each of which is four bytes long. Multi-level Page Table: Let's utilise the first 10-most significant bits to index into the first level page table in the case of a two-level page table. The next 10-bits will be indexed into the second-level page table, which contains the page number to frame number mappings.

What is the primary advantage of using a two level page table?

A multi-level table for logical address translation without virtual memory has the benefit of being able to have a dynamic page table size (even if it is not paged out). Paging is based only on the prospect of a benefit (however, systems with dedicated system address spaces can page page-tables without having nesting).

What is the main advantage of a multilevel page table over a single level one?

A multilevel (hierarchical) page table has the following advantages over a single-level one: (a) Page number lookups are quicker. (b) If there are huge areas of unoccupied memory, the page table can take up significantly less space. (c) Each section (code, data, and stack) may be controlled independently.

Conclusion

  • Cheers if you reached here! In this blog, we learned about the MultiLevel Paging in Operating System.
  • We have covered the need for MultiLevel Paging and its definition.
  • We have also seen its working.
  • Further, we saw an illustration of MultiLevel Paging.
  • We have also witnessed the Disadvantages of MultiLevel Paging in OS.


On the other hand, learning never ceases, and there is always more to learn. So, keep learning and keep growing, ninjas!

With this fantastic course from CodingNinjas, you can make learning enjoyable and stress-free.

Recommend Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Good luck with your preparation!

Live masterclass