GATE CS Mastery
Cheat sheets

GATE CS 2015 Set 2 · Operating Systems

Question 57

NATPrinted as CS Q.472 marksNo negative markingMedium (estimate)

Question

A computer system implements 8 kilobyte pages and a 32-bit physical address space. Each page table entry contains a valid bit, a dirty bit, three permission bits, and the translation. If the maximum size of the page table of a process is 24 megabytes, the length of the virtual address supported by the system is _____ bits.

Official answer and solution
Official answer
36
From
Official GATE 2015 answer key

Solution

Determine the Page Table Entry (PTE) size, compute the maximum number of pages, and sum with the page offset.

  1. Page offset length:
    Page size = 8 KB=213 bytes  ⟹  8\text{ KB} = 2^{13}\text{ bytes} \implies Page offset p=13 bitsp = 13\text{ bits}.
  1. Frame number length:
    Physical address space = 32 bits.
    Number of frames = 232213=219  ⟹  \dfrac{2^{32}}{2^{13}} = 2^{19} \implies Frame number = 19 bits.
  1. Page Table Entry (PTE) size:
    Each PTE consists of:
  • Translation (frame number): 19 bits
  • Valid bit: 1 bit
  • Dirty bit: 1 bit
  • Permission bits: 3 bits
Total PTE size=19+1+1+3=24 bits=3 bytes.\text{Total PTE size} = 19 + 1 + 1 + 3 = 24\text{ bits} = 3\text{ bytes}.
  1. Number of page table entries:
Number of entries=Maximum page table sizePTE size=24 MB3 bytes=24×2203=8×220=223 entries.\text{Number of entries} = \frac{\text{Maximum page table size}}{\text{PTE size}} = \frac{24\text{ MB}}{3\text{ bytes}} = \frac{24 \times 2^{20}}{3} = 8 \times 2^{20} = 2^{23}\text{ entries}.
  1. Virtual address length:
Virtual address length=Virtual page number (VPN) bits+Page offset bits=23+13=36 bits.\text{Virtual address length} = \text{Virtual page number (VPN) bits} + \text{Page offset bits} = 23 + 13 = 36\text{ bits}.
Final answer

36

Common trap

Assuming PTE size must be rounded up to 4 bytes (222^2 bytes) instead of using the exact 24 bits (3 bytes) supported by the calculation.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2015 Computer Science and Information Technology (CS) Session 2
Question
57 of 65, printed as CS Q.47
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.