Memory Management

GATE CS previous year questions · 7 questions

GATE CS 2025 Set 1 | Question 14

MCQ · 1 mark · −0.33

Consider a demand paging memory management system with 32-bit logical address, 20-bit physical address, and page size of 2048 bytes. Assuming that the memory is byte addressable, what is the maximum number of entries in the page table?

Options for GATE CS 2025 Set 1 | Question 14

Explanation

Answer: (A)

A page table has one entry for each page of the logical address space. The page size is \(2048 = 2^{11}\) bytes, so the number of pages is \(\frac{2^{32}}{2^{11}} = 2^{21}\). The 20-bit physical address affects only the size of each entry (a frame number of \(20 - 11 = 9\) bits), not the number of entries.

Answer: A

GATE CS 2025 Set 1 | Question 54

NAT · 2 marks

In optimal page replacement algorithm, information about all future page references is available to the operating system (OS). A modification of the optimal page replacement algorithm is as follows:

The OS correctly predicts only up to next 4 page references (including the current page) at the time of allocating a frame to a page.

A process accesses the pages in the following order of page numbers:

1, 3, 2, 4, 2, 3, 1, 2, 4, 3, 1, 4.

If the system has three memory frames that are initially empty, the number of page faults that will occur during execution of the process is ________ . (Answer in integer)

Explanation

Answer: 6

On a fault with all frames full, look at the current reference and the next three. Replace a resident page that is not in this window; if all of them are in it, replace the one needed last.

  • 1, 3, 2: three faults fill the frames: {1, 3, 2}.
  • 4: fault. Window 4, 2, 3, 1, so page 1 is needed last; replace it: {4, 3, 2}. The next 2 and 3 are hits.
  • 1: fault. Window 1, 2, 4, 3, so page 3 is needed last; replace it: {4, 1, 2}. The next 2 and 4 are hits.
  • 3: fault. Window 3, 1, 4 does not contain page 2; replace it: {4, 1, 3}. The last 1 and 4 are hits.

Total page faults \(= 3 + 1 + 1 + 1 = 6\).

Answer: 6

GATE CS 2025 Set 2 | Question 47

MSQ · 2 marks

Consider a demand paging system with three frames, and the following page reference string: 1 2 3 4 5 4 1 6 4 5 1 3 2. The contents of the frames are as follows initially and after each reference (from left to right):

initiallyafter
-1*2*3*4*5*416*451*3*2*
-1111111666662
--224444444111
---33555555533

The *-marked references cause page replacements.

Which one or more of the following could be the page replacement policy/policies in use?

Options for GATE CS 2025 Set 2 | Question 47

Explanation

Answer: (D)

The table replaces page 2 at the 4th reference, 3 at the 5th, 1 at the 8th, and then 4, 5 and 6 at the last three.

  • Optimal fits. At the 4th reference the frames hold 1, 2, 3, next used at references 7, 13 and 12, so 2, needed farthest ahead, goes. Likewise 3 goes at the 5th reference and 1 at the 8th. At the last three faults no page in memory is used again, so any victim is optimal.
  • LRU fails: at the 4th reference it would evict 1, the least recently used page.
  • LFU fails: at the 8th reference page 5 has one use and pages 1 and 4 have two, so it would evict 5.
  • MFU fails: at the 4th reference pages 1, 2 and 3 have one use each, and a first-in or least-recently-used tie-break evicts 1, not 2.

Answer: D

GATE CS 2025 Set 2 | Question 58

NAT · 2 marks

A computer system supports a logical address space of \(2^{32}\) bytes. It uses two-level hierarchical paging with a page size of 4096 bytes. A logical address is divided into a \(b\)-bit index to the outer page table, an offset within the page of the inner page table, and an offset within the desired page. Each entry of the inner page table uses eight bytes. All the pages in the system have the same size.

The value of \(b\) is ___________ . (Answer in integer)

Explanation

Answer: 11

Split the 32-bit logical address from the right:

  • Offset within the desired page: \(4096 = 2^{12}\) bytes, so 12 bits.
  • Offset within a page of the inner page table: one page holds \(4096 / 8 = 512 = 2^{9}\) eight-byte entries, so 9 bits.
  • Outer page table index: whatever is left, \(b = 32 - 12 - 9 = 11\).

So the outer page table has \(2^{11} = 2048\) entries, each pointing to one page of the inner page table.

Answer: 11

GATE CS 2024 Set 1 | Question 62

NAT · 2 marks

Consider a memory management system that uses a page size of 2 KB. Assume that both the physical and virtual addresses start from 0. Assume that the pages 0, 1, 2, and 3 are stored in the page frames 1, 3, 2, and 0, respectively. The physical address (in decimal format) corresponding to the virtual address 2500 (in decimal format) is _________

Explanation

Answer: 6596

A page holds \(2\ \text{KB} = 2048\) bytes, so split the virtual address into a page number and an offset:

  • page number \(= \lfloor 2500 / 2048 \rfloor = 1\);
  • offset \(= 2500 - 2048 = 452\).

Page 1 is stored in frame 3 (the second pair in the list), and the offset carries over unchanged:

\[3 \times 2048 + 452 = 6144 + 452 = 6596\]

Answer: 6596

GATE CS 2024 Set 2 | Question 24

MSQ · 1 mark

Which of the following tasks is/are the responsibility/responsibilities of the memory management unit (MMU) in a system with paging-based memory management?

Options for GATE CS 2024 Set 2 | Question 24

Explanation

Answer: (B), (C), (D)

The MMU is the hardware between the CPU and memory that handles every memory reference. Its jobs are the ones done on each access:

  • B: it translates each virtual address to a physical address through the page table, with the TLB caching recent translations.
  • C: if the page table entry is invalid or not present, it cannot translate the address and raises a trap (a page fault) for the OS to handle.
  • D: it checks the protection bits on every access and traps when a process writes to a read-only page.

A is not an MMU task. Creating a process and allocating and filling its page table is done in software by the operating system kernel; the MMU only uses the table the OS has set up, for example through the page-table base register.

Answer: B, C, D

GATE CS 2024 Set 2 | Question 64

NAT · 2 marks

Consider a 32-bit system with 4 KB page size and page table entries of size 4 bytes each. Assume 1 KB = \(2^{10}\) bytes. The OS uses a 2-level page table for memory management, with the page table containing an outer page directory and an inner page table. The OS allocates a page for the outer page directory upon process creation. The OS uses demand paging when allocating memory for the inner page table, i.e., a page of the inner page table is allocated only if it contains at least one valid page table entry.

An active process in this system accesses 2000 unique pages during its execution, and none of the pages are swapped out to disk. After it completes the page accesses, let \(X\) denote the minimum and \(Y\) denote the maximum number of pages across the two levels of the page table of the process.

The value of \(X+Y\) is ________

Explanation

Answer: 1028

A 4 KB page holds \(2^{12} / 4 = 1024\) entries. So one inner page-table page maps 1024 pages, and the outer directory (one page, 1024 entries) can point to at most 1024 inner pages. The directory page always exists.

  • Minimum: the 2000 pages fall into as few 1024-page regions as possible, \(\lceil 2000 / 1024 \rceil = 2\) inner pages, so \(X = 1 + 2 = 3\).
  • Maximum: the pages are spread out so that each inner page has few valid entries. With 2000 pages and only 1024 possible inner pages, all 1024 can be in use, so \(Y = 1 + 1024 = 1025\).

Hence \(X + Y = 3 + 1025 = 1028\).

Answer: 1028