Numerical of Paging with Solution

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 = 2X, then number of bits in frame number = X
bits
• If Page size = 2X Bytes, then number of bits in page offset = X bits
• If size of main memory = 2X 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 = 2X 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

KEY NOTE-
In general, if the given address consists of ‘n’ bits, then using ‘n’ bits, 2n locations are
possible.

• Then, size of memory = 2n x Size of one location.

• If the memory is byte-addressable, then size of one location = 1 byte.
• Thus, size of memory = 2n bytes.
• If the memory is word-addressable where 1 word = m bytes, then size of one
location = m bytes.
• Thus, size of memory = 2n 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 = 222 locations
• It is given that the size of one location = 2 bytes

Thus, Size of memory

= 222 x 2 bytes

= 223 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 = 2n x 4 bytes.
Since, the given memory has size of 16 GB, so we have-
2n x 4 bytes = 16 GB
2n x 4 = 16 G
2n x 22 = 234
2n = 232
∴ 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
= 232 B
= 4 GB

Number of Entries in Page Table-

Number of pages the process is divided
= Process size / Page size
= 4 GB / 4 KB
= 220 pages

Thus,

Number of entries in page table = 220 entries

Page Table Size-

Page table size

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

= 220 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
= 226 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
= 226 B / 212 B
= 214
Thus, Number of bits in frame number = 14 bits

Number of Bits in Page Offset-

We have,
Page size

= 4 KB

= 212 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
= 232 B
= 4 GB

Number of Entries in Page Table-

Number of pages the process is divided

= Process size / Page size
= 4 GB / 4 KB
= 220 pages

Thus, Number of entries in page table = 220 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
= 220 x 14 bits
= 220 x 16 bits (Approximating 14 bits ≈ 16 bits)
= 220 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
= 230 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
= 230 B / 212 B
= 218
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

Numerical of Segmentation with Solution

Problem-
Consider the following segment table-
Segment
Base Length
No.

0 1219 700

1 2300 14

2 90 100

3 1327 580

4 1952 96

Which of the following logical address will produce trap addressing error?
1. (0, 430)
2. (1, 11)
3. (2, 100)
4. (3, 425)
5. (4, 95)

Calculate the physical address if no trap is produced.

Solution-

In a segmentation scheme, the generated logical address consists of two parts-

1. Segment Number
2. Segment Offset

We know-
• Segment Offset must always lie in the range [0, limit-1].
• If segment offset becomes greater than or equal to the limit of segment, then trap
addressing error is produced.

Option-A: 0, 430-

Here,
• Segment Number = 0
• Segment Offset = 430

We have,
• In the segment table, limit of segment-0 is 700.
• Thus, segment offset must always lie in the range = [0, 700-1] = [0, 699]

Now,
• Since generated segment offset lies in the above range, so request generated is
valid.
• Therefore, no trap will be produced.
• Physical Address = 1219 + 430 = 1649

Option-B: 1, 11-

Here,
• Segment Number = 1
• Segment Offset = 11

We have,
• In the segment table, limit of segment-1 is 14.
• Thus, segment offset must always lie in the range = [0, 14-1] = [0, 13]

Now,
• Since generated segment offset lies in the above range, so request generated is
valid.
• Therefore, no trap will be produced.
• Physical Address = 2300 + 11 = 2311
Option-C: 2, 100-

Here,
• Segment Number = 2
• Segment Offset = 100

We have,
• In the segment table, limit of segment-2 is 100.
• Thus, segment offset must always lie in the range = [0, 100-1] = [0, 99]

Now,
• Since generated segment offset does not lie in the above range, so request
generated is invalid.
• Therefore, trap will be produced.

Option-D: 3, 425-

Here,
• Segment Number = 3
• Segment Offset = 425

We have,
• In the segment table, limit of segment-3 is 580.
• Thus, segment offset must always lie in the range = [0, 580-1] = [0, 579]

Now,
• Since generated segment offset lies in the above range, so request generated is
valid.
• Therefore, no trap will be produced.
• Physical Address = 1327 + 425 = 1752

Option-E: 4, 95-
Here,

• Segment Number = 4
• Segment Offset = 95

We have,
• In the segment table, limit of segment-4 is 96.
• Thus, segment offset must always lie in the range = [0, 96-1] = [0, 95]

Now,
• Since generated segment offset lies in the above range, so request generated is
valid.
• Therefore, no trap will be produced.
• Physical Address = 1952 + 95 = 2047

Thus, Option-(C) is correct.