Paging in OS | Formulas | Practice Problems

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 _____.

1. 2
2. 4
3. 8
4. 16

 

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?

1. 16 MB
2. 8 MB
3. 2 MB
4. 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?

1. 2
2. 10
3. 12
4. 14

 

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.