OS Notes | Gate Vidyalay

Tag: OS Notes

Multilevel Paging | Paging | Practice Problems

Operating System

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-

How many levels of page table will be required?
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-

How many levels of page table will be required?
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-

How many levels of page table will be required?
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-

How many levels of page table will be required?
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.

Multilevel Paging in OS | Paging in OS

Operating System

Paging in OS-

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

We have discussed-

Paging is a non-contiguous memory allocation technique.
Page Table is a data structure that performs the mapping of page number to the frame number.

In this article, we will discuss about Multilevel Paging.

Multilevel Paging-

Multilevel paging is a paging scheme where there exists a hierarchy of page tables.

Need –

The need for multilevel paging arises when-

The size of page table is greater than the frame size.
As a result, the page table can not be stored in a single frame in main memory.

Working-

In multilevel paging,

The page table having size greater than the frame size is divided into several parts.
The size of each part is same as frame size except possibly the last part.
The pages of page table are then stored in different frames of the main memory.
To keep track of the frames storing the pages of the divided page table, another page table is maintained.
As a result, the hierarchy of page tables get generated.
Multilevel paging is done till the level is reached where the entire page table can be stored in a single frame.

Illustration of Multilevel Paging-

Consider a system using paging scheme where-

Logical Address Space = 4 GB
Physical Address Space = 16 TB
Page size = 4 KB

Now, let us find how many levels of page table will be required.

Number of Bits in Physical Address-

Size of main memory

= Physical Address Space

= 16 TB

= 2⁴⁴ B

Thus, Number of bits in physical address = 44 bits

Number of Frames in Main Memory-

Number of frames in main memory

= Size of main memory / Frame size

= 16 TB / 4 KB

= 2³² frames

Thus, Number of bits in frame number = 32 bits

Number of Bits in Page Offset-

We have,

Page size

= 4 KB

= 2¹² B

Thus, Number of bits in page offset = 12 bits

Alternatively,

Number of bits in page offset

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

= 44 bits – 32 bits

= 12 bits

So, Physical address is-

Number of Pages of Process-

Number of pages the process is divided

= Process size / Page size

= 4 GB / 4 KB

= 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 Number of bits in frame number

= 2²⁰ x 32 bits

= 2²⁰ x 4 bytes

= 4 MB

Now, we can observe-

The size of inner page table is greater than the frame size (4 KB).
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

= 4 MB / 4 KB

= 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

= Page size / Number of bits in frame number

= 4 KB / 32 bits

= 4 KB / 4 B

= 2¹⁰

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 Number of bits in frame number

= 2¹⁰ x 32 bits

= 2¹⁰ x 4 bytes

= 4 KB

Now, we can observe-

The size of outer page table is same as frame size (4 KB).
Thus, outer page table can be stored in a single frame.
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 = 10 bits

The paging system will look like as shown below-

PRACTICE PROBLEM BASED ON MULTILEVEL PAGING-

Problem-

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

Find-

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

Solution-

Given-

Virtual Address = 48 bits
Page size = 16 KB
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 KB

= 2⁴⁶ B

= 64 TB

Thus, Number of bits in physical address = 46 bits

Number of Bits in Page Offset-

We have,

Page size

= 16 KB

= 2¹⁴ B

Thus, Number of bits in page offset = 14 bits

Alternatively,

Number of bits in page offset

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

= 46 bits – 32 bits

= 14 bits

Process Size-

Number of bits in virtual address = 48 bits

Thus,

Process size

= 2⁴⁸ bytes

= 256 TB

Number of Pages of Process-

Number of pages the process is divided

= Process size / Page size

= 256 TB / 16 KB

= 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

= 64 GB

Now, we can observe-

The size of inner page table is greater than the frame size (4 KB).
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

= 64 GB / 16 KB

= 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 KB / 4 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 = 12 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

= 16 MB

Now, we can observe-

The size of outer page table-1 is greater than the frame size (4 KB).
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

= 16 MB / 16 KB

= 2¹⁰ pages

Now, these 2¹⁰ 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 KB / 4 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 = 12 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¹⁰ x 4 bytes

= 4 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 2¹⁰ entries.

Thus,

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

The paging system will look like as shown below-

Important Points-

At any level, the page table entry size of any page table will always be same because each entry points to the frame number.
When there is only one level of paging, there is only one page table whose size is less than or equal to page size.
All the page tables are completely filled except possibly the last page.

To gain better understanding about Multilevel Paging,

Watch this Video Lecture

Next Article- Practice Problems On Multilevel Paging

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Translation Lookaside Buffer | TLB | Paging

Operating System

Paging in OS-

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

We have discussed-

Paging in OS is a non-contiguous memory allocation technique.
Page Table is a data structure that maps page number to the frame number.

Disadvantage Of Paging-

One major disadvantage of paging is-

It increases the effective access time due to increased number of memory accesses.
One memory access is required to get the frame number from the page table.
Another memory access is required to get the word from the page.

Translation Lookaside Buffer-

Translation Lookaside Buffer (TLB) is a solution that tries to reduce the effective access time.
Being a hardware, the access time of TLB is very less as compared to the main memory.

Structure-

Translation Lookaside Buffer (TLB) consists of two columns-

Page Number
Frame Number

Translating Logical Address into Physical Address-

In a paging scheme using TLB,

The logical address generated by the CPU is translated into the physical address using following steps-

Step-01:

CPU generates a logical address consisting of two parts-

Page Number
Page Offset

Step-02:

TLB is checked to see if it contains an entry for the referenced page number.
The referenced page number is compared with the TLB entries all at once.

Now, two cases are possible-

Case-01: If there is a TLB hit-

If TLB contains an entry for the referenced page number, a TLB hit occurs.
In this case, TLB entry is used to get the corresponding frame number for the referenced page number.

Case-02: If there is a TLB miss-

If TLB does not contain an entry for the referenced page number, a TLB miss occurs.
In this case, page table is used to get the corresponding frame number for the referenced page number.
Then, TLB is updated with the page number and frame number for future references.

Step-03:

After the frame number is obtained, it is combined with the page offset to generate the physical address.
Then, physical address is used to read the required word from the main memory.

NOTE-

In the above discussion, we have assumed that no Page Fault occurs.

Diagram-

The following diagram illustrates the above steps of translating logical address into physical address-

Flowchart-

The following flowchart illustrates the above steps of translating logical address into physical address-

Important Points-

Point-01:

Unlike page table, there exists only one TLB in the system.
So, whenever context switching occurs, the entire content of TLB is flushed and deleted.
TLB is then again updated with the currently running process.

Point-02:

When a new process gets scheduled-

Initially, TLB is empty. So, TLB misses are frequent.
With every access from the page table, TLB is updated.
After some time, TLB hits increases and TLB misses reduces.

Point-03:

The time taken to update TLB after getting the frame number from the page table is negligible.
Also, TLB is updated in parallel while fetching the word from the main memory.

Advantages-

The advantages of using TLB are-

TLB reduces the effective access time.
Only one memory access is required when TLB hit occurs.

Disadvantages-

A major disadvantage of using TLB is-

After some time of running the process, when TLB hits increases and process starts to run smoothly, a context switching occurs.
The entire content of the TLB is flushed.
Then, TLB is again updated with the currently running process.

This happens again and again.

Other disadvantages are-

TLB can hold the data of only one process at a time.
When context switches occur frequently, the performance of TLB degrades due to low hit ratio.
As it is a special hardware, it involves additional cost.

Effective Access Time-

In a single level paging using TLB, the effective access time is given as-

This formula is valid only when there is single level paging and there are no page faults.

PRACTICE PROBLEMS BASED ON TRANSLATION LOOKASIDE BUFFER-

Problem-01:

A paging scheme uses a Translation Lookaside buffer (TLB). A TLB access takes 10 ns and a main memory access takes 50 ns. What is the effective access time (in ns) if the TLB hit ratio is 90% and there is no page fault?

Solution-

Given-

TLB access time = 10 ns
Main memory access time = 50 ns
TLB Hit ratio = 90% = 0.9

Calculating TLB Miss Ratio-

TLB Miss ratio

= 1 – TLB Hit ratio

= 1 – 0.9

= 0.1

Calculating Effective Access Time-

Substituting values in the above formula, we get-

Effective Access Time

= 0.9 x { 10 ns + 50 ns } + 0.1 x { 10 ns + 2 x 50 ns }

= 0.9 x 60 ns + 0.1 x 110 ns

= 54 ns + 11 ns

= 65 ns

Thus, Option (C) is correct.

Problem-02:

A paging scheme uses a Translation Lookaside buffer (TLB). The effective memory access takes 160 ns and a main memory access takes 100 ns. What is the TLB access time (in ns) if the TLB hit ratio is 60% and there is no page fault?

Solution-

Given-

Effective access time = 160 ns
Main memory access time = 100 ns
TLB Hit ratio = 60% = 0.6

Calculating TLB Miss Ratio-

TLB Miss ratio

= 1 – TLB Hit ratio

= 1 – 0.6

= 0.4

Calculating TLB Access Time-

Let TLB access time = T ns.

Substituting values in the above formula, we get-

160 ns = 0.6 x { T + 100 ns } + 0.4 x { T + 2 x 100 ns }

160 = 0.6 x T + 60 + 0.4 x T + 80

160 = T + 140

T = 160 – 140

T = 20

Thus, Option (C) is correct.

To gain better understanding about Translation Lookaside Buffer (TLB),

Watch this Video Lecture

Next Article- Multilevel Paging

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Paging in OS | Formulas | Practice Problems

Operating System

Paging in OS-

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

We have discussed-

Paging is a non-contiguous memory allocation technique.
Page Table is a data structure that performs the mapping of page number to the frame number.

Important Formulas-

The following list of formulas is very useful for solving the numerical problems based on paging.

For Main Memory-

Physical Address Space = Size of main memory
Size of main memory = Total number of frames x Page size
Frame size = Page size
If number of frames in main memory = 2^X, then number of bits in frame number = X bits
If Page size = 2^X Bytes, then number of bits in page offset = X bits
If size of main memory = 2^X Bytes, then number of bits in physical address = X bits

For Process-

Virtual Address Space = Size of process
Number of pages the process is divided = Process size / Page size
If process size = 2^X bytes, then number of bits in virtual address space = X bits

For Page Table-

Size of page table = Number of entries in page table x Page table entry size
Number of entries in pages table = Number of pages the process is divided
Page table entry size = Number of bits in frame number + Number of bits used for optional fields if any

NOTE-

In general, if the given address consists of ‘n’ bits, then using ‘n’ bits, 2ⁿ locations are possible.
Then, size of memory = 2ⁿ x Size of one location.
If the memory is byte-addressable, then size of one location = 1 byte.
Thus, size of memory = 2ⁿ bytes.
If the memory is word-addressable where 1 word = m bytes, then size of one location = m bytes.
Thus, size of memory = 2ⁿ x m bytes.

PRACTICE PROBLEMS BASED ON PAGING AND PAGE TABLE-

Problem-01:

Calculate the size of memory if its address consists of 22 bits and the memory is 2-byte addressable.

Solution-

We have-

Number of locations possible with 22 bits = 2²² locations
It is given that the size of one location = 2 bytes

Thus, Size of memory

= 2²² x 2 bytes

= 2²³ bytes

= 8 MB

Problem-02:

Calculate the number of bits required in the address for memory having size of 16 GB. Assume the memory is 4-byte addressable.

Solution-

Let ‘n’ number of bits are required. Then, Size of memory = 2ⁿ x 4 bytes.

Since, the given memory has size of 16 GB, so we have-

2ⁿ x 4 bytes = 16 GB

2ⁿ x 4 = 16 G

2ⁿ x 2² = 2³⁴

2ⁿ = 2³²

∴ n = 32 bits

Problem-03:

Consider a system with byte-addressable memory, 32 bit logical addresses, 4 kilobyte page size and page table entries of 4 bytes each. The size of the page table in the system in megabytes is _____.

Solution-

Given-

Number of bits in logical address = 32 bits
Page size = 4KB
Page table entry size = 4 bytes

Process Size-

Number of bits in logical address = 32 bits

Thus,

Process size

= 2³² B

= 4 GB

Number of Entries in Page Table-

Number of pages the process is divided

= Process size / Page size

= 4 GB / 4 KB

= 2²⁰ pages

Thus,

Number of entries in page table = 2²⁰ entries

Page Table Size-

Page table size

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

= 2²⁰ x 4 bytes

= 4 MB

Thus, Option (B) is correct.

Problem-04:

Consider a machine with 64 MB physical memory and a 32 bit virtual address space. If the page size is 4 KB, what is the approximate size of the page table?

16 MB
8 MB
2 MB
24 MB

Solution-

Given-

Size of main memory = 64 MB
Number of bits in virtual address space = 32 bits
Page size = 4 KB

We will consider that the memory is byte addressable.

Number of Bits in Physical Address-

Size of main memory

= 64 MB

= 2²⁶ B

Thus, Number of bits in physical address = 26 bits

Number of Frames in Main Memory-

Number of frames in main memory

= Size of main memory / Frame size

= 64 MB / 4 KB

= 2²⁶ B / 2¹² B

= 2¹⁴

Thus, Number of bits in frame number = 14 bits

Number of Bits in Page Offset-

We have,

Page size

= 4 KB

= 2¹² B

Thus, Number of bits in page offset = 12 bits

So, Physical address is-

Process Size-

Number of bits in virtual address space = 32 bits

Thus,

Process size

= 2³² B

= 4 GB

Number of Entries in Page Table-

Number of pages the process is divided

= Process size / Page size

= 4 GB / 4 KB

= 2²⁰ pages

Thus, Number of entries in page table = 2²⁰ entries

Page Table Size-

Page table size

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

= Number of entries in page table x Number of bits in frame number

= 2²⁰ x 14 bits

= 2²⁰ x 16 bits (Approximating 14 bits ≈ 16 bits)

= 2²⁰ x 2 bytes

= 2 MB

Thus, Option (C) is correct.

Problem-05:

In a virtual memory system, size of virtual address is 32-bit, size of physical address is 30-bit, page size is 4 Kbyte and size of each page table entry is 32-bit. The main memory is byte addressable. Which one of the following is the maximum number of bits that can be used for storing protection and other information in each page table entry?

Solution-

Given-

Number of bits in virtual address = 32 bits
Number of bits in physical address = 30 bits
Page size = 4 KB
Page table entry size = 32 bits

Size of Main Memory-

Number of bits in physical address = 30 bits

Thus,

Size of main memory

= 2³⁰ B

= 1 GB

Number of Frames in Main Memory-

Number of frames in main memory

= Size of main memory / Frame size

= 1 GB / 4 KB

= 2³⁰ B / 2¹² B

= 2¹⁸

Thus, Number of bits in frame number = 18 bits

Number of Bits used for Storing other Information-

Maximum number of bits that can be used for storing protection and other information

= Page table entry size – Number of bits in frame number

= 32 bits – 18 bits

= 14 bits

Thus, Option (D) is correct.

To gain better understanding about solving numerical problems on paging,

Watch this Video Lecture

Next Article- Optimal Page Size | Practice Problems

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Page Table | Paging in Operating System

Operating System

Paging in OS-

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

We have discussed-

Paging is a non-contiguous memory allocation technique.
The logical address generated by the CPU is translated into the physical address using the page table.

In this article, we will discuss about Page Table.

Page Table-

Page table is a data structure.
It maps the page number referenced by the CPU to the frame number where that page is stored.

Characteristics-

Page table is stored in the main memory.
Number of entries in a page table = Number of pages in which the process is divided.
Page Table Base Register (PTBR) contains the base address of page table.
Each process has its own independent page table.

Working-

Page Table Base Register (PTBR) provides the base address of the page table.
The base address of the page table is added with the page number referenced by the CPU.
It gives the entry of the page table containing the frame number where the referenced page is stored.

Page Table Entry-

A page table entry contains several information about the page.
The information contained in the page table entry varies from operating system to operating system.
The most important information in a page table entry is frame number.

In general, each entry of a page table contains the following information-

1. Frame Number-

Frame number specifies the frame where the page is stored in the main memory.
The number of bits in frame number depends on the number of frames in the main memory.

2. Present / Absent Bit-

This bit is also sometimes called as valid / invalid bit.
This bit specifies whether that page is present in the main memory or not.
If the page is not present in the main memory, then this bit is set to 0 otherwise set to 1.

NOTE

If the required page is not present in the main memory, then it is called as Page Fault.
A page fault requires page initialization.
The required page has to be initialized (fetched) from the secondary memory and brought into the main memory.

3. Protection Bit-

This bit is also sometimes called as “Read / Write bit“.
This bit is concerned with the page protection.
It specifies the permission to perform read and write operation on the page.
If only read operation is allowed to be performed and no writing is allowed, then this bit is set to 0.
If both read and write operation are allowed to be performed, then this bit is set to 1.

4. Reference Bit-

Reference bit specifies whether that page has been referenced in the last clock cycle or not.
If the page has been referenced recently, then this bit is set to 1 otherwise set to 0.

NOTE

Reference bit is useful for page replacement policy.
A page that has not been referenced recently is considered a good candidate for page replacement in LRU page replacement policy.

5. Caching Enabled / Disabled-

This bit enables or disables the caching of page.
Whenever freshness in the data is required, then caching is disabled using this bit.
If caching of the page is disabled, then this bit is set to 1 otherwise set to 0.

6. Dirty Bit-

This bit is also sometimes called as “Modified bit“.
This bit specifies whether that page has been modified or not.
If the page has been modified, then this bit is set to 1 otherwise set to 0.

NOTE

In case the page is modified,

Before replacing the modified page with some other page, it has to be written back in the secondary memory to avoid losing the data.
Dirty bit helps to avoid unnecessary writes.
This is because if the page is not modified, then it can be directly replaced by another page without any need of writing it back to the disk.

To gain better understanding about Page Table Entry,

Watch this Video Lecture

Next Article- Paging Important Formulas

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

← Older Posts

Newer Posts →