Paging in OS | Practice Problems | Set-02

Paging in OS-

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

We have discussed-

• Paging is a non-contiguous memory allocation technique.
• Page Table is a table that maps a page number to the frame number containing that page.
• Multilevel Paging is a paging scheme where there exists a hierarchy of page tables.

Also Read- Important Formulas of Paging

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

PRACTICE PROBLEMS BASED ON MULTILEVEL PAGING IN OS-

Problem-01:

Consider a single level paging scheme. The page size is 4 KB and page table entry size is 4 bytes. The size of page table is 4 KB. Give the division of virtual address space.

Solution-

Given-

• Page size = 4 KB
• Page table entry size = 4 bytes
• Page table size = 4 KB

Let the number of bits in virtual address = n bits

Number of Bits in Page Offset-

We have,

Page size

= 4 KB

= 2¹² B

Thus, Number of bits in page offset = 12 bits

Process Size-

Number of bits in virtual address = n bits

Thus,

Process size = 2ⁿ bytes

Number of Pages of Process-

Number of pages the process is divided

= Process size / Page size

= 2ⁿ B / 4 KB

= 2ⁿ B / 2¹² B

= 2^n-12 pages

Page Table Size-

Page table keeps track of the frames storing the pages of process.

Page table size

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

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

= 2^n-12 x 4 bytes

= 2^n-12+2 bytes

= 2^n-10 bytes

But we are given page table size = 4 KB

Thus,

2^n-10 bytes = 4 KB

2^n-10 = 2¹²

n – 10 = 12

∴ n = 22

Thus, number of bits in virtual address = 22 bits

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

Method-01:

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

= Number of bits in virtual address – Number of bits in page offset

= 22 bits – 12 bits

= 10 bits

Method-02:

Number of entries in page table

= Number of pages the process is divided

= 2^n-12

= 2^22-12

= 2¹⁰

Thus, Number of bits required to search a particular entry in page table = 10 bits

Problem-02:

Consider a two level paging scheme. The page size is 4 KB and page table entry size is 4 bytes. The size of outer page table is 4 KB. Give the division of virtual address space.

Solution-

Given-

• Page size = 4 KB
• Page table entry size = 4 bytes
• Page table size = 4 KB

Let the number of bits in virtual address = n bits

Number of Bits in Page Offset-

We have,

Page size

= 4 KB

= 2¹² B

Thus, Number of bits in page offset = 12 bits

Process Size-

Number of bits in virtual address = n bits

Thus,

Process size = 2ⁿ bytes

Number of Pages of Process-

Number of pages the process is divided

= Process size / Page size

= 2ⁿ B / 4 KB

= 2ⁿ B / 2¹² B

= 2^n-12 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^n-12 x 4 bytes

= 2^n-12+2 bytes

= 2^n-10 bytes

Number of Pages of Inner Page Table-

Number of pages the inner page table is divided

= Inner page table size / Page size

= 2^n-10 B / 4 KB

= 2^n-10 B / 2¹² B

= 2^n-10-12

= 2^n-22 pages

Now, these 2^n-22 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

= 4 KB / 4 bytes

= 1 K

= 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 = 10 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^n-22 x 4 bytes

= 2^n-22+2 bytes

= 2^n-20 bytes

But we are given outer page table size = 4 KB

Thus,

2^n-20 bytes = 4 KB

2^n-20 = 2¹²

n – 20 = 12

∴ n = 32

Thus, number of bits in virtual address = 32 bits

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

Method-01:

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

= Number of bits in virtual address – (Number of bits required to search an entry in inner page table + Number of bits in page offset)

= 32 bits – (10 bits + 12 bits)

= 32 bits – 22 bits

= 10 bits

Method-02:

Number of entries in outer page table

= Number of pages the inner page table is divided

= 2^n-22

= 2^32-22

= 2¹⁰

Thus, Number of bits required to search a particular entry in outer page table = 10 bits

Problem-03:

Consider a three level paging scheme. The page size is 4 KB and page table entry size is 4 bytes. The size of outermost page table is 4 KB. Give the division of virtual address space.

Solution-

Given-

• Page size = 4 KB
• Page table entry size = 4 bytes
• Page table size = 4 KB

Let the number of bits in virtual address = n bits

Number of Bits in Page Offset-

We have,

Page size

= 4 KB

= 2¹² B

Thus, Number of bits in page offset = 12 bits

Process Size-

Number of bits in virtual address = n bits

Thus,

Process size = 2ⁿ bytes

Number of Pages of Process-

Number of pages the process is divided

= Process size / Page size

= 2ⁿ B / 4 KB

= 2ⁿ B / 2¹² B

= 2^n-12 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^n-12 x 4 bytes

= 2^n-12+2 bytes

= 2^n-10 bytes

Number of Pages of Inner Page Table-

Number of pages the inner page table is divided

= Inner page table size / Page size

= 2^n-10 B / 4 KB

= 2^n-10 B / 2¹² B

= 2^n-10-12

= 2^n-22 pages

Now, these 2^n-22 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

= 4 KB / 4 bytes

= 1 K

= 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 = 10 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^n-22 x 4 bytes

= 2^n-22+2 bytes

= 2^n-20 bytes

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

= 2^n-20 B / 4 KB

= 2^n-20 B / 2¹² B

= 2^n-20-12

= 2^n-32 pages

Now, these 2^n-32 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

= 4 KB / 4 bytes

= 1 K

= 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 = 10 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

= 2^n-32 x 4 bytes

= 2^n-32+2 bytes

= 2^n-30 bytes

But we are given outermost page table size = 4 KB

Thus,

2^n-30 bytes = 4 KB

2^n-30 = 2¹²

n – 30 = 12

∴ n = 42

Thus, number of bits in virtual address = 42 bits

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

Method-01:

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

= Number of bits in virtual address – (Number of bits required to search an entry in outer page table-1 + Number of bits required to search an entry in inner page table + Number of bits in page offset)

= 42 bits – (10 bits + 10 bits + 12 bits)

= 42 bits – 32 bits

= 10 bits

Method-02:

Number of entries in outer page table-2

= Number of pages the outer page table-1 is divided

= 2^n-32

= 2^42-32

= 2¹⁰

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

Problem-04:

Complete the following table-

Solution-

• We have to solve these problems in exactly the same manner as we have solved above.
• So, try yourself.

The answers to these problems are-

1. 6 bits, 12 bits
2. 6 bits, 10 bits, 12 bits
3. 6 bits, 10 bits, 10 bits, 12 bits

Next Article- Practice Problems On Multilevel Paging Using TLB | Set-03

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary

Article Name

Paging in OS | Practice Problems | Set-02

Description

Practice Problems based on Paging and Multilevel Paging in OS. Multilevel Paging is a paging scheme where there exists a hierarchy of page tables. Page table performs the mapping of page number to frame number.

Author

Akshay Singhal

Publisher Name

Gate Vidyalay

Publisher Logo