Multilevel Paging | Paging | Practice Problems

Multilevel Paging in OS-

 

Before you go through this article, make sure that you have gone through the previous article on Multilevel Paging.

 

We have discussed-

• Multilevel Paging is a paging scheme where there exists a hierarchy of Page Tables.
• Multilevel paging is needed when a page table can not be stored in a single frame due to its large size.

 

In this article, we will discuss practice problems based on multilevel paging.

 

Also Read- Paging Important Formulas

 

PRACTICE PROBLEMS BASED ON MULTILEVEL PAGING-

 

Problem-01:

 

Consider a system using multilevel paging scheme. The page size is 1 MB. The memory is byte addressable and virtual address is 64 bits long. The page table entry size is 4 bytes.

Find-

1. How many levels of page table will be required?
2. Give the divided physical address and virtual address.

 

Solution-

 

Given-

• Virtual Address = 64 bits
• Page size = 1 MB
• Page table entry size = 4 bytes

 

Number of Bits in Frame Number-

 

We have,

Page table entry size

= 4 bytes

= 32 bits

Thus, Number of bits in frame number = 32 bits

 

Number of Frames in Main Memory-

 

We have, Number of bits in frame number = 32 bits

Thus,

Number of frames in main memory

= 2³² frames

 

Size of Main Memory-

 

Size of main memory

= Total number of frames x Frame size

= 2³² x 1 MB

= 2⁵² B

Thus, Number of bits in physical address = 52 bits

 

Number of Bits in Page Offset-

 

We have,

Page size

= 1 MB

= 2²⁰ B

Thus, Number of bits in page offset = 20 bits

 

Alternatively,

Number of bits in page offset

= Number of bits in physical address – Number of bits in frame number

= 52 bits – 32 bits

= 20 bits

 

Process Size-

 

Number of bits in virtual address = 64 bits

Thus,

Process size

= 2⁶⁴ bytes

 

Number of Pages of Process-

 

Number of pages the process is divided

= Process size / Page size

= 2⁶⁴ B / 1 MB

= 2⁶⁴ B / 2²⁰ B

= 2⁴⁴ pages

 

Inner Page Table Size-

 

Inner page table keeps track of the frames storing the pages of process.

Inner page table size

= Number of entries in inner page table x Page table entry size

= Number of pages the process is divided x Page table entry size

= 2⁴⁴ x 4 bytes

= 2⁴⁶ bytes

 

Now, we can observe-

• The size of inner page table is greater than the frame size (1 MB).
• Thus, inner page table can not be stored in a single frame.
• So, inner page table has to be divided into pages.

 

Number of Pages of Inner Page Table-

 

Number of pages the inner page table is divided

= Inner page table size / Page size

= 2⁴⁶ B / 1 MB

= 2⁴⁶ B / 2²⁰ B

= 2²⁶ pages

 

Now, these 2²⁶ pages of inner page table are stored in different frames of the main memory.

 

Number of Page Table Entries in One Page of Inner Page Table-

 

Number of page table entries in one page of inner page table

= Page size / Page table entry size

= 1 MB / 4 B

= 2²⁰ B / 2² B

= 2¹⁸ entries

 

Number of Bits Required to Search an Entry in One Page of Inner Page Table-

 

One page of inner page table contains 2¹⁸ entries.

Thus,

Number of bits required to search a particular entry in one page of inner page table = 18 bits

 

Outer Page Table-1 Size-

 

Outer page table-1 is required to keep track of the frames storing the pages of inner page table.

Outer page table-1 size

= Number of entries in outer page table-1 x Page table entry size

= Number of pages the inner page table is divided x Page table entry size

= 2²⁶ x 4 bytes

= 2²⁸ bytes

= 256 MB

 

Now, we can observe-

• The size of outer page table-1 is greater than the frame size (1 MB).
• Thus, outer page table-1 can not be stored in a single frame.
• So, outer page table-1 has to be divided into pages.

 

Number of Pages of Outer Page Table-1

 

Number of pages the outer page table-1 is divided

= Outer page table-1 size / Page size

= 256 MB / 1 MB

= 256 pages

 

Now, these 256 pages of outer page table-1 are stored in different frames of the main memory.

 

Number of Page Table Entries in One Page of Outer Page Table-1

 

Number of page table entries in one page of outer page table-1

= Page size / Page table entry size

= 1 MB / 4 B

= 2²⁰ B / 2² B

= 2¹⁸ entries

 

Number of Bits Required to Search an Entry in One Page of Outer Page Table-1

 

One page of outer page table-1 contains 2¹⁸ entries.

Thus,

Number of bits required to search a particular entry in one page of outer page table-1 = 18 bits

 

Outer Page Table-2 Size-

 

Outer page table-2 is required to keep track of the frames storing the pages of outer page table-1.

Outer page table-2 size

= Number of entries in outer page table-2 x Page table entry size

= Number of pages the outer page table-1 is divided x Page table entry size

= 256 x 4 bytes

= 1 KB

 

Now, we can observe-

• The size of outer page table-2 is less than the frame size (16 KB).
• Thus, outer page table-2 can be stored in a single frame.
• In fact, outer page table-2 will not completely occupy one frame and some space will remain vacant.
• So, for given system, we will have three levels of page table.
• Page Table Base Register (PTBR) will store the base address of the outer page table-2.

 

Number of Bits Required to Search an Entry in Outer Page Table-2

 

Outer page table-2 contains 256 = 2⁸ entries.

Thus,

Number of bits required to search a particular entry in outer page table-2 = 8 bits

 

The paging system will look like as shown below-

 

 

Problem-02:

 

Consider a system using multilevel paging scheme. The page size is 1 GB. The memory is byte addressable and virtual address is 72 bits long. The page table entry size is 4 bytes.

Find-

1. How many levels of page table will be required?
2. Give the divided physical address and virtual address.

 

Solution-

 

Given-

• Virtual Address = 72 bits
• Page size = 1 GB
• Page table entry size = 4 bytes

 

Number of Bits in Frame Number-

 

We have,

Page table entry size

= 4 bytes

= 32 bits

Thus, Number of bits in frame number = 32 bits

 

Number of Frames in Main Memory-

 

We have, Number of bits in frame number = 32 bits

Thus,

Number of frames in main memory

= 2³² frames

 

Size of Main Memory-

 

Size of main memory

= Total number of frames x Frame size

= 2³² x 1 GB

= 2⁶² B

Thus, Number of bits in physical address = 62 bits

 

Number of Bits in Page Offset-

 

We have,

Page size

= 1 GB

= 2³⁰ B

Thus, Number of bits in page offset = 30 bits

 

Alternatively,

Number of bits in page offset

= Number of bits in physical address – Number of bits in frame number

= 62 bits – 32 bits

= 30 bits

 

Process Size-

 

Number of bits in virtual address = 72 bits

Thus,

Process size

= 2⁷² bytes

 

Number of Pages of Process-

 

Number of pages the process is divided

= Process size / Page size

= 2⁷² B / 1 GB

= 2⁷² B / 2³⁰ B

= 2⁴² pages

 

Inner Page Table Size-

 

Inner page table keeps track of the frames storing the pages of process.

Inner page table size

= Number of entries in inner page table x Page table entry size

= Number of pages the process is divided x Page table entry size

= 2⁴² x 4 bytes

= 2⁴⁴ bytes

 

Now, we can observe-

• The size of inner page table is greater than the frame size (1 GB).
• Thus, inner page table can not be stored in a single frame.
• So, inner page table has to be divided into pages.

 

Number of Pages of Inner Page Table-

 

Number of pages the inner page table is divided

= Inner page table size / Page size

= 2⁴⁴ B / 1 GB

= 2⁴⁴ B / 2³⁰ B

= 2¹⁴ pages

 

Now, these 2¹⁴ pages of inner page table are stored in different frames of the main memory.

 

Number of Page Table Entries in One Page of Inner Page Table-

 

Number of page table entries in one page of inner page table

= Page size / Page table entry size

= 1 GB / 4 B

= 2³⁰ B / 2² B

= 2²⁸ entries

 

Number of Bits Required to Search an Entry in One Page of Inner Page Table-

 

One page of inner page table contains 2²⁸ entries.

Thus,

Number of bits required to search a particular entry in one page of inner page table = 28 bits

 

Outer Page Table Size-

 

Outer page table is required to keep track of the frames storing the pages of inner page table.

Outer page table size

= Number of entries in outer page table x Page table entry size

= Number of pages the inner page table is divided x Page table entry size

= 2¹⁴ x 4 bytes

= 2¹⁶ bytes

= 64 KB

 

Now, we can observe-

• The size of outer page table is less than the frame size (1 GB).
• Thus, outer page table can be stored in a single frame.
• In fact, outer page table will not completely occupy one frame and some space will remain vacant.
• So, for given system, we will have two levels of page table.
• Page Table Base Register (PTBR) will store the base address of the outer page table.

 

Number of Bits Required to Search an Entry in Outer Page Table-

 

Outer page table contains 2¹⁴ entries.

Thus,

Number of bits required to search a particular entry in outer page table = 14 bits

 

The paging system will look like as shown below-

 

 

Problem-03:

 

Consider a system using multilevel paging scheme. The page size is 256 MB. The memory is byte addressable and virtual address is 72 bits long. The page table entry size is 4 bytes.

Find-

1. How many levels of page table will be required?
2. Give the divided physical address and virtual address.

 

Solution-

 

Given-

• Virtual Address = 72 bits
• Page size = 256 MB
• Page table entry size = 4 bytes

 

Number of Bits in Frame Number-

 

We have,

Page table entry size

= 4 bytes

= 32 bits

Thus, Number of bits in frame number = 32 bits

 

Number of Frames in Main Memory-

 

We have, Number of bits in frame number = 32 bits

Thus,

Number of frames in main memory

= 2³² frames

 

Size of Main Memory-

 

Size of main memory

= Total number of frames x Frame size

= 2³² x 256 MB

= 2⁶⁰ B

Thus, Number of bits in physical address = 60 bits

 

Number of Bits in Page Offset-

 

We have,

Page size

= 256 MB

= 2²⁸ B

Thus, Number of bits in page offset = 28 bits

 

Alternatively,

Number of bits in page offset

= Number of bits in physical address – Number of bits in frame number

= 60 bits – 32 bits

= 28 bits

 

Process Size-

 

Number of bits in virtual address = 72 bits

Thus,

Process size

= 2⁷² bytes

 

Number of Pages of Process-

 

Number of pages the process is divided

= Process size / Page size

= 2⁷² B / 256 MB

= 2⁷² B / 2²⁸ B

= 2⁴⁴ pages

 

Inner Page Table Size-

 

Inner page table keeps track of the frames storing the pages of process.

Inner page table size

= Number of entries in inner page table x Page table entry size

= Number of pages the process is divided x Page table entry size

= 2⁴⁴ x 4 bytes

= 2⁴⁶ bytes

 

Now, we can observe-

• The size of inner page table is greater than the frame size (256 MB).
• Thus, inner page table can not be stored in a single frame.
• So, inner page table has to be divided into pages.

 

Number of Pages of Inner Page Table-

 

Number of pages the inner page table is divided

= Inner page table size / Page size

= 2⁴⁶ B / 256 MB

= 2⁴⁶ B / 2²⁸ B

= 2¹⁸ pages

 

Now, these 2¹⁸ pages of inner page table are stored in different frames of the main memory.

 

Number of Page Table Entries in One Page of Inner Page Table-

 

Number of page table entries in one page of inner page table

= Page size / Page table entry size

= 256 MB / 4 B

= 2²⁸ B / 2² B

= 2²⁶ entries

 

Number of Bits Required to Search an Entry in One Page of Inner Page Table-

 

One page of inner page table contains 2²⁶ entries.

Thus,

Number of bits required to search a particular entry in one page of inner page table = 26 bits

 

Outer Page Table Size-

 

Outer page table is required to keep track of the frames storing the pages of inner page table.

Outer page table size

= Number of entries in outer page table x Page table entry size

= Number of pages the inner page table is divided x Page table entry size

= 2¹⁸ x 4 bytes

= 2²⁰ bytes

= 1 MB

 

Now, we can observe-

• The size of outer page table is less than the frame size (256 MB).
• Thus, outer page table can be stored in a single frame.
• In fact, outer page table will not completely occupy one frame and some space will remain vacant.
• So, for given system, we will have two levels of page table.
• Page Table Base Register (PTBR) will store the base address of the outer page table.

 

Number of Bits Required to Search an Entry in Outer Page Table-

 

Outer page table contains 2¹⁸ entries.

Thus,

Number of bits required to search a particular entry in outer page table = 18 bits

 

The paging system will look like as shown below-

 

 

Problem-04:

 

Consider a system using multilevel paging scheme. The page size is 16 MB. The memory is byte addressable and virtual address is 72 bits long. The page table entry size is 4 bytes.

Find-

1. How many levels of page table will be required?
2. Give the divided physical address and virtual address.

 

Solution-

 

Given-

• Virtual Address = 72 bits
• Page size = 16 MB
• Page table entry size = 4 bytes

 

Number of Bits in Frame Number-

 

We have,

Page table entry size

= 4 bytes

= 32 bits

Thus, Number of bits in frame number = 32 bits

 

Number of Frames in Main Memory-

 

We have, Number of bits in frame number = 32 bits

Thus,

Number of frames in main memory

= 2³² frames

 

Size of Main Memory-

 

Size of main memory

= Total number of frames x Frame size

= 2³² x 16 MB

= 2⁵⁶ B

Thus, Number of bits in physical address = 56 bits

 

Number of Bits in Page Offset-

 

We have,

Page size

= 16 MB

= 2²⁴ B

Thus, Number of bits in page offset = 24 bits

 

Alternatively,

Number of bits in page offset

= Number of bits in physical address – Number of bits in frame number

= 56 bits – 32 bits

= 24 bits

 

Process Size-

 

Number of bits in virtual address = 72 bits

Thus,

Process size

= 2⁷² bytes

 

Number of Pages of Process-

 

Number of pages the process is divided

= Process size / Page size

= 2⁷² B / 16 MB

= 2⁷² B / 2²⁴ B

= 2⁴⁸ pages

 

Inner Page Table Size-

 

Inner page table keeps track of the frames storing the pages of process.

Inner page table size

= Number of entries in inner page table x Page table entry size

= Number of pages the process is divided x Page table entry size

= 2⁴⁸ x 4 bytes

= 2⁵⁰ bytes

 

Now, we can observe-

• The size of inner page table is greater than the frame size (16 MB).
• Thus, inner page table can not be stored in a single frame.
• So, inner page table has to be divided into pages.

 

Number of Pages of Inner Page Table-

 

Number of pages the inner page table is divided

= Inner page table size / Page size

= 2⁵⁰ B / 16 MB

= 2⁵⁰ B / 2²⁴ B

= 2²⁶ pages

 

Now, these 2²⁶ pages of inner page table are stored in different frames of the main memory.

 

Number of Page Table Entries in One Page of Inner Page Table-

 

Number of page table entries in one page of inner page table

= Page size / Page table entry size

= 16 MB / 4 B

= 2²⁴ B / 2² B

= 2²² entries

 

Number of Bits Required to Search an Entry in One Page of Inner Page Table-

 

One page of inner page table contains 2²² entries.

Thus,

Number of bits required to search a particular entry in one page of inner page table = 22 bits

 

Outer Page Table-1 Size-

 

Outer page table-1 is required to keep track of the frames storing the pages of inner page table.

Outer page table-1 size

= Number of entries in outer page table-1 x Page table entry size

= Number of pages the inner page table is divided x Page table entry size

= 2²⁶ x 4 bytes

= 2²⁸ bytes

= 256 MB

 

Now, we can observe-

• The size of outer page table-1 is greater than the frame size (16 MB).
• Thus, outer page table-1 can not be stored in a single frame.
• So, outer page table-1 has to be divided into pages.

 

Number of Pages of Outer Page Table-1

 

Number of pages the outer page table-1 is divided

= Outer page table-1 size / Page size

= 256 MB / 16 MB

= 16 pages

 

Now, these 16 pages of outer page table-1 are stored in different frames of the main memory.

 

Number of Page Table Entries in One Page of Outer Page Table-1

 

Number of page table entries in one page of outer page table-1

= Page size / Page table entry size

= 16 MB / 4 B

= 2²⁴ B / 2² B

= 2²² entries

 

Number of Bits Required to Search an Entry in One Page of Outer Page Table-1

 

One page of outer page table-1 contains 2²² entries.

Thus,

Number of bits required to search a particular entry in one page of outer page table-1 = 22 bits

 

Outer Page Table-2 Size-

 

Outer page table-2 is required to keep track of the frames storing the pages of outer page table-1.

Outer page table-2 size

= Number of entries in outer page table-2 x Page table entry size

= Number of pages the outer page table-1 is divided x Page table entry size

= 16 x 4 bytes

= 64 bytes

 

Now, we can observe-

• The size of outer page table-2 is less than the frame size (16 MB).
• Thus, outer page table-2 can be stored in a single frame.
• In fact, outer page table-2 will not completely occupy one frame and some space will remain vacant.
• So, for given system, we will have three levels of page table.
• Page Table Base Register (PTBR) will store the base address of the outer page table-2.

 

Number of Bits Required to Search an Entry in Outer Page Table-2

 

Outer page table-2 contains 16 = 2⁴ entries.

Thus,

Number of bits required to search a particular entry in outer page table-2 = 4 bits

 

The paging system will look like as shown below-

 

 

Next Article- Practice Problems On Multilevel Paging | Set-02

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.