**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
^{n}locations are possible. - Then, size of memory = 2
^{n}x Size of one location. - If the memory is byte-addressable, then size of one location = 1 byte.
- Thus, size of memory = 2
^{n}bytes. - If the memory is word-addressable where 1 word = m bytes, then size of one location = m bytes.
- Thus, size of memory = 2
^{n}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
^{22}locations - It is given that the size of one location = 2 bytes

Thus, Size of memory

= 2^{22} x 2 bytes

= 2^{23} 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^{n} x 4 bytes.

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

2^{n} x 4 bytes = 16 GB

2^{n} x 4 = 16 G

2^{n} x 2^{2} = 2^{34}

2^{n} = 2^{32}

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

- 2
- 4
- 8
- 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^{32} 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^{20} pages

Thus,

Number of entries in page table = 2^{20} entries

**Page Table Size-**

Page table size

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

= 2^{20} 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^{26} 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^{26} B / 2^{12} B

= 2^{14}

Thus, Number of bits in frame number = 14 bits

**Number of Bits in Page Offset-**

We have,

Page size

= 4 KB

= 2^{12} 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^{32} 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^{20} pages

Thus, Number of entries in page table = 2^{20} 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^{20} x 14 bits

= 2^{20} x 16 bits (Approximating 14 bits ≈ 16 bits)

= 2^{20} 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?

- 2
- 10
- 12
- 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^{30} 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^{30} B / 2^{12} B

= 2^{18}

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,

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