GATE CS

Virtual memory

Demand paging and page replacement

Virtual memory lets a process run with only some of its pages in RAM: a page is brought in from disk on demand, and when memory is full a replacement algorithm picks a victim. For GATE you must trace FIFO, optimal and LRU on a reference string, compute effective access time from the page-fault rate, and reason about Belady's anomaly, frame allocation, program structure and thrashing.

6 previous-year questions · 6 solved · 5 practice questions

Demand paging and the page-fault sequence

In demand paging a page is loaded into a frame only when the process first touches it. In pure demand paging a process starts with no pages in memory, so its first instruction already faults. This works because of locality: over a short interval a process uses only a small part of its address space.

Each page-table entry carries a valid-invalid bit. Valid means the page is legal and currently in memory. Invalid means either that the page is outside the process's address space, or that it is legal but not in memory right now. Page replacement also uses a reference bit (set by hardware on any access) and a modify (dirty) bit (set on a write).

Servicing a page fault, in order

The CPU references a page whose entry is invalid, and the hardware traps to the operating system.
The OS checks an internal table (kept with the process control block). If the address is illegal, the process is terminated. If it is legal but not in memory, continue.
The OS finds a free frame. If none is free, a page-replacement algorithm picks a victim; if the victim is dirty it must first be written to disk.
The OS schedules a disk read of the needed page into that frame. The process waits and the CPU can run another process.
When the read completes, the OS updates the page table (frame number, valid bit set) and the frame table.
The interrupted instruction is restarted from the beginning, and this time it finds the page in memory.

EXAM TIP

A clean victim (dirty bit 0) is simply overwritten: one disk transfer per fault. A dirty victim costs two transfers (write it out, read the new page in). This is why the page-fault service time depends on the fraction of dirty victims.

Effective access time with page faults

Convention used here. Let $m$ be the memory-access time when the page is present (no TLB or page-table cost unless the question gives it). Let $S$ be the total time of an access that page-faults, including servicing the fault and restarting the access, unless the question says the restart access is extra. Let $p$ be the page-fault rate, the fraction of memory references that fault ( $0 \leq p \leq 1$ ). Times must be in the same unit; $1 ms = 1 0^{6} ns$ .

EFFECTIVE ACCESS TIME

EAT = (1 - p) m + p S

Weighted average of a hit-path access (time m) and a faulting access (total time S).

EFFECTIVE ACCESS TIME WHEN THE FAULT TIME IS EXTRA

EAT = (1 - p) m + p (m + S) = m + p S

Use this form when the question gives S as a delay added on top of the normal memory access, so a faulting access costs m + S.

AVERAGE FAULT SERVICE TIME WITH DIRTY VICTIMS

S = (1 - d) S_{clean} + d S_{dirty}

d is the fraction of faults whose victim is dirty; S_clean and S_dirty are the service times for a clean and a dirty victim.

LARGEST TOLERABLE FAULT RATE

p \leq \frac{ε m}{S - m}

Keeps EAT at most (1+ε)·m, i.e. a slowdown of at most 100ε percent, with S the total time of a faulting access. Follows from (1-p)m + pS ≤ (1+ε)m.

WORKED EXAMPLE

Memory access takes 200 ns. A fault takes 8 ms (total) when the victim is clean and 20 ms (total) when it is dirty; 40% of victims are dirty. The page-fault rate is $1 0^{- 5}$ . (a) Find the effective access time. (b) Find the largest fault rate for which the slowdown is at most 10%.

Solution

Average service time: $S = 0.6 \times 8 + 0.4 \times 20 = 12.8$ ms $= 1.28 \times 1 0^{7}$ ns.
(a) $EAT = (1 - 1 0^{- 5}) (200) + 1 0^{- 5} (1.28 \times 1 0^{7}) = 199.998 + 128 = 327.998$ ns.
(b) $ε = 0.1$ , so $p \leq \frac{0.1 \times 200}{1.28 \times 1 0 ^{7} - 200} = \frac{20}{12 799 800} \approx 1.5625 \times 1 0^{- 6}$ .

Answer: (a) about 328 ns; (b) p of about 1.56 x 10^-6, roughly one fault in 640,000 references.

EXAM TIP

Because $S$ is millions of times larger than $m$ , even a tiny $p$ dominates EAT. Always convert ms to ns before substituting, and check whether the question gives $S$ as the total time of the faulting access or as an extra delay on top of $m$ .

Page-replacement algorithms and counting faults

A reference string is the sequence of page numbers a process touches. Convention: all frames start empty, so the first reference to each distinct page is a fault, and every fault is counted (including those into empty frames). A reference to a page already in memory is a hit.

Algorithm	Victim chosen	Hit changes state?	Notes
FIFO	Page that has been in memory longest	No	Simple; can show Belady's anomaly
Optimal (OPT)	Page whose next use is farthest in the future (or never)	No (it uses future references, not history)	Lowest possible faults; needs the future, so only a yardstick
LRU	Page unused for the longest time	Yes: page becomes most recent	Looks backward as a guess for the future; no anomaly

Procedure for a trace

Write the reference string and keep the frame contents after each reference.
On a hit, change nothing for FIFO and OPT; for LRU move the page to the most-recent end.
On a fault with a free frame, load the page. With no free frame, apply the algorithm's rule to choose the victim.
For OPT, look at the rest of the string; a page never used again is evicted first. If several pages are never used again, evict the one loaded earliest (stated here as the tie rule; the choice between pages never used again does not change the fault count).
Count the faults at the end.

WORKED EXAMPLE

Reference string 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 with 3 frames, initially empty. Count the page faults under FIFO, LRU and OPT. (FIFO and LRU states are listed oldest or least-recent first.)

Solution

The table below gives the frame contents after each reference; F = fault, H = hit.
FIFO faults at references 1, 2, 4, 5, 6, 7, 9, 11, 12: 9 faults.
LRU faults at references 1, 2, 4, 5, 7, 9, 10: 7 faults.
OPT faults at references 1, 2, 4, 5, 7, 10: 6 faults. At reference 5 it evicts 1 (never used again); at reference 7 it evicts 2 (next used last); at reference 10, pages 3 and 4 are never used again, so the earlier-loaded page 3 goes.

Answer: FIFO 9, LRU 7, OPT 6 faults.

t	Ref	FIFO	LRU	OPT
1	2	[2] F	[2] F	{2} F
2	3	[2,3] F	[2,3] F	{2,3} F
3	2	[2,3] H	[3,2] H	{2,3} H
4	1	[2,3,1] F	[3,2,1] F	{1,2,3} F
5	5	[3,1,5] F	[2,1,5] F	{2,3,5} F
6	2	[1,5,2] F	[1,5,2] H	{2,3,5} H
7	4	[5,2,4] F	[5,2,4] F	{3,4,5} F
8	5	[5,2,4] H	[2,4,5] H	{3,4,5} H
9	3	[2,4,3] F	[4,5,3] F	{3,4,5} H
10	2	[2,4,3] H	[5,3,2] F	{2,4,5} F
11	5	[4,3,5] F	[3,2,5] H	{2,4,5} H
12	2	[3,5,2] F	[3,5,2] H	{2,4,5} H

EXAM TIP

The common slip is forgetting that a hit refreshes a page in LRU but does nothing in FIFO. Quick checks: OPT never has more faults than FIFO or LRU on the same string and frame count; with frames starting empty, any algorithm has at least as many faults as there are distinct pages and at most as many as the length of the string; and if the frames are at least the number of distinct pages, every algorithm faults exactly once per distinct page.

Belady's anomaly, stack algorithms and LRU approximations

Belady's anomaly is the case where giving a process more frames produces more page faults. It occurs with FIFO. Standard example: string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 under FIFO gives 9 faults with 3 frames but 10 faults with 4 frames.

A replacement algorithm is a stack algorithm if, for every reference string, every $n$ and after every reference, the set of pages in memory with $n$ frames is a subset of the set with $n + 1$ frames. Stack algorithms never show Belady's anomaly. LRU and OPT are stack algorithms; FIFO is not. Second chance (clock) is not a stack algorithm either and can show the anomaly: on the string above, with a page's reference bit set to 1 when it is loaded, second chance also gives 9 faults with 3 frames and 10 with 4.

True LRU needs hardware support on every reference, so real systems use approximations. Exact LRU can be kept with a per-page time-of-last-use counter, or with a stack of page numbers with the most recent on top. Cheaper approximations use the reference bit.

Second-chance (clock) algorithm

Keep frames in a circular list with a hand (equivalent to a FIFO queue with a reference bit).
On a hit, the page's reference bit is set to 1; the hand does not move.
On a fault, examine the page under the hand. If its reference bit is 1, clear it to 0 and advance the hand (the page gets a second chance).
If the reference bit is 0, that page is the victim: replace it, put the new page there (reference bit set as the system defines on load) and advance the hand.
If every bit is 1, the hand makes one full circle clearing all bits and then evicts the page it started at; at that fault the algorithm makes the same choice as FIFO.

Variant	Idea
Additional reference bits	Each page keeps a shift register of its last few reference bits, with the newest bit shifted into the high-order position; read as an unsigned number, the page with the smallest value is the victim (ties broken in FIFO order)
Enhanced second chance	Uses the pair (reference, modify); prefer victims in the order (0,0), (0,1), (1,0), (1,1), because a clean unreferenced page is cheapest and least likely needed

Counting-based algorithms keep a count of references per page. LFU (least frequently used) evicts the page with the smallest count; MFU (most frequently used) evicts the page with the largest count, on the argument that a page with a small count was probably just brought in. Neither approximates OPT well, and both are costly to implement.

EXAM TIP

For GATE traces, the reference bit of a freshly loaded page is taken as the question states; if not stated, read the question for what it intends and state your assumption, because the choice can change the count. Belady's anomaly is not guaranteed for FIFO on every string: it appears only on some strings.

Program structure and page faults

The order in which a program walks a large array decides how many page faults it causes. Conventions for this example: C stores arrays in row-major order, an int is 4 bytes, the page size is 512 bytes, the array starts on a page boundary, and the process has exactly one frame for the array (code and loop variables sit in other frames that are never replaced). Each row of int A[128][128] is $128 \times 4 = 512$ bytes, so each row is exactly one page.

int A[128][128];
int i, j;

/* Version 1: column by column */
for (j = 0; j < 128; j++)
    for (i = 0; i < 128; i++)
        A[i][j] = 0;

/* Version 2: row by row */
for (i = 0; i < 128; i++)
    for (j = 0; j < 128; j++)
        A[i][j] = 0;

WORKED EXAMPLE

For the two loops above, under the stated conventions, how many page faults does each version cause?

Solution

Version 1: consecutive accesses A[0][j], A[1][j], … lie in different rows, hence different pages. With one frame, every access faults: $128 \times 128 = 16384$ faults.
Version 2: all 128 accesses of one row lie in one page, so only the first access to each row faults: $128$ faults.

Answer: Column by column: 16,384 faults; row by row: 128 faults.

EXAM TIP

Giving version 1 more frames does not help under FIFO or LRU while the frames are fewer than 128: the inner loop cycles through 128 pages, so the page needed next is always the one evicted longest ago, and every access still faults.

Frame allocation, thrashing and the working set

With $m$ frames and $n$ processes, a policy must decide each process's share. Every process needs a minimum number of frames set by the instruction set (enough for the pages one instruction can touch). Equal allocation gives each process $⌊ m / n ⌋$ frames, with any leftover frames kept as a free pool. Proportional allocation divides frames in proportion to process size.

PROPORTIONAL ALLOCATION

a_{i} = \frac{s _{i}}{\sum _{j} s _{j}} \times m

s_i is the size (in pages) of process i and m the number of available frames. If a share is not whole, use the rounding the question states (for example, round down and keep the leftover frames free), keeping each share at or above the minimum.

Replacement may be global (the victim can be any frame, including another process's) or local (the victim comes from the faulting process's own frames). Global replacement uses memory flexibly, but a process's fault rate then depends on others' behaviour.

Thrashing is a state where a process (or the whole system) spends more time paging than executing. A typical chain: too many processes, so each has too few frames, so faults rise, the disk queue grows, CPU utilisation falls, and a naive scheduler admits even more processes, making it worse. Raising the degree of multiprogramming in response to low CPU utilisation is therefore wrong when the cause is paging.

The working set $W (t, Δ)$ is the set of distinct pages referenced in the most recent $Δ$ page references (the working-set window). Its size is $WSS$ . If $Δ$ is too small it misses part of the locality; if too large it spans several localities.

WORKED EXAMPLE

A process references pages 1, 2, 3, 2, 4, 4, 3, 5 (references 1 to 8). With $Δ = 4$ , find the working set and its size just after reference 8.

Solution

The last 4 references are 4, 4, 3, 5.
Distinct pages: ${3, 4, 5}$ .

Answer: W = {3, 4, 5}, WSS = 3.

TOTAL FRAME DEMAND

D = i \sum WSS_{i}

If D is greater than the number of available frames m, thrashing is likely; the OS should suspend a process (freeing its frames). If D is at most m, the OS may start another process.

Page-fault frequency (PFF) controls the fault rate directly. Choose an upper and a lower bound. If a process's fault rate goes above the upper bound, give it another frame; if below the lower bound, take a frame away. If no free frame exists when a process is above the upper bound, suspend a process.

Copy-on-write in brief

With copy-on-write (COW), fork() does not copy the parent's pages. Parent and child initially share the same frames, which are marked read-only (with a COW flag). When either process writes to a shared page, the write causes a protection fault; the OS then allocates a new frame, copies the page, maps the copy writable for the writer, and restarts the write. Pages never written stay shared.

Why it matters

fork() becomes cheap, because no page is copied up front.
If the child calls exec() at once, almost nothing is ever copied.
If the OS keeps a share count for each frame, the number of copies made equals the number of shared pages that are actually written: a page written by both is copied once, for the first writer, and the other process then holds the original alone, so its write needs no copy. Without such a count the OS may copy again on the second write, so follow what the question states.

EXAM TIP

In COW questions, count only pages that are written after the fork. Pages that are only read by parent and child are never copied.

PREVIOUS-YEAR QUESTIONS

6 questions from the CS papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE CSE 2025 Set 1 · GATE CSE 2025 Set 2 · GATE CSE 2023 · GATE CSE 2022 · GATE CSE 2020 · GATE CSE 2018

GATE 2025 CS1 Q.54

GATE 2025 · CS1Q.54 · 2 marks · NAT

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)

Answer and solution

GATE 2025 CS1 Q.54: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS1 Q.54: answer and solution

GATE 2025 CS2 Q.47

GATE 2025 · CS2Q.47 · 2 marks · MSQ

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):

initially - - - - 1^{*} 1 - - 2^{*} 12 - 3^{*} 123 4^{*} 143 5^{*} 145 4145 after 1145 6^{*} 645 46455645 1^{*} 615 3^{*} 613 2^{*} 213

The *-marked references cause page replacements.

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

GATE 2025 CS2 question 47: A table with an 'initially' column and 13 'after' columns, one per reference. — Figure from the GATE 2025 CS2 paper. It is part of the question.

(A)
Least Recently Used page replacement policy
(B)
Least Frequently Used page replacement policy
(C)
Most Frequently Used page replacement policy
(D)
Optimal page replacement policy

Answer and solution

GATE 2025 CS2 Q.47: answer and solution

GATE 2023 CS Q.57

GATE 2023 · CSQ.57 · 2 marks · NAT

Consider the following two-dimensional array D in the C programming language, which is stored in row-major order:

int D[128][128];

Demand paging is used for allocating memory and each physical page frame holds 512 elements of the array D. The Least Recently Used (LRU) page-replacement policy is used by the operating system. A total of 30 physical page frames are allocated to a process which executes the following code snippet:

for (int i = 0; i < 128; i++)
   for (int j = 0; j < 128; j++)
          D[j][i] *= 10;

The number of page faults generated during the execution of this code snippet is ______.

Answer and solution

GATE 2023 CS Q.57: answer and solution

See the question in the paper

Tap to open full size

GATE 2023 CS Q.57: answer and solution

GATE 2022 CS Q.64

GATE 2022 · CSQ.64 · 2 marks · NAT

Consider a demand paging system with four page frames (initially empty) and LRU page replacement policy. For the following page reference string

7, 2, 7, 3, 2, 5, 3, 4, 6, 7, 7, 1, 5, 6, 1

the page fault rate, defined as the ratio of number of page faults to the number of memory accesses (rounded off to one decimal place) is ______.

Answer and solution

GATE 2022 CS Q.64: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 CS Q.64: answer and solution

GATE 2020 CS Q.53

GATE 2020 · CSQ.53 · 2 marks · NAT

Consider a paging system that uses 1-level page table residing in main memory and a TLB for address translation. Each main memory access takes 100 ns and TLB lookup takes 20 ns. Each page transfer to/from the disk takes 5000 ns. Assume that the TLB hit ratio is 95%, page fault rate is 10%. Assume that for 20% of the total page faults, a dirty page has to be written back to disk before the required page is read in from disk. TLB update time is negligible. The average memory access time in ns (round off to 1 decimal places) is ______.

Answer and solution

GATE 2020 CS Q.53: answer and solution

See the question in the paper

Tap to open full size

GATE 2020 CS Q.53: answer and solution

GATE 2018 CS Q.10

GATE 2018 · CSQ.10 · 1 mark · MCQ

Consider a process executing on an operating system that uses demand paging. The average time for a memory access in the system is M units if the corresponding memory page is available in memory, and D units if the memory access causes a page fault. It has been experimentally measured that the average time taken for a memory access in the process is X units.

Which one of the following is the correct expression for the page fault rate experienced by the process?

(A)
(D - M) / (X - M)
(B)
(X - M) / (D - M)
(C)
(D - X) / (D - M)
(D)
(X - M) / (D - X)

Answer and solution

GATE 2018 CS Q.10: answer and solution

See the question in the paper

Tap to open full size

GATE 2018 CS Q.10: answer and solution

OTHER EXAMS

ISRO: 1 question

From ISRO's Scientist/Engineer written test: ISRO CS 2025. They are not counted in the GATE numbers on this page.

ISRO CS 2025 Q.70

ISRO 2025 · CSQ.70 · 1 mark · MCQ

Consider the following reference strings and assume 3 frames are available, then the number of page faults that occur using Optimal page replacement algorithm is
6, 0, 5, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 5, 2

(A)
15 Page Faults
(B)
9 Page Faults
(C)
12 Page Faults
(D)
8 Page Faults

Answer and solution

ISRO CS 2025 Q.70: answer and solution

See the question in the paper

Tap to open full size

ISRO CS 2025 Q.70: answer and solution

PRACTICE

5 questions to test yourself

PRACTICE 12 marks · MCQ

A process has 3 frames, initially empty, and references pages 1, 3, 5, 1, 2, 3, 4, 1, 5, 2 in this order. Ties in OPT go to the page loaded earliest. The numbers of page faults under FIFO, LRU and OPT respectively are:

(A)
8, 9, 6
(B)
8, 8, 6
(C)
9, 8, 6
(D)
8, 9, 7

Answer and solution

Answer: (A)

FIFO: faults at 1,3,5 then 1 hits; 2 evicts 1 giving [3,5,2]; 3 hits; 4 evicts 3 giving [5,2,4]; 1 evicts 5 giving [2,4,1]; 5 evicts 2 giving [4,1,5]; 2 evicts 4. Only two hits, so 8 faults.
LRU: after 1,3,5 and the hit on 1 the order is 3,5,1; then 2 (evict 3), 3 (evict 5), 4 (evict 1), 1 (evict 2), 5 (evict 3), 2 (evict 4) all fault. Only one hit, so 9 faults.
OPT: faults at 1,3,5; hit on 1; 2 evicts 5 (used last); 3 hits; 4 evicts 3 (never again); 1 hits; 5 faults, evicting 1 (never again, earliest loaded among 1 and 4); 2 hits. Faults: 1,3,5,2,4,5 = 6.
The triple is (8, 9, 6).

PRACTICE 22 marks · NAT

Memory access time is 100 ns. A page fault costs 6 ms in total when the victim page is clean and 14 ms in total when it is dirty; half of the victims are dirty. The page-fault rate is $2 \times 1 0^{- 5}$ per memory reference. Ignore TLB and page-table lookups. The effective access time in nanoseconds is ______ (1 ms = $1 0^{6}$ ns).

Answer and solution

Answer: $299.998$ (accepted range $\pm 0.05$ )

Average service time $S = 0.5 \times 6 + 0.5 \times 14 = 10$ ms $= 1 0^{7}$ ns.
$EAT = (1 - 2 \times 1 0^{- 5}) (100) + 2 \times 1 0^{- 5} (1 0^{7}) = 99.998 + 200 = 299.998$ ns.

PRACTICE 32 marks · MSQ

A system has 50 frames and three active processes whose working-set sizes are 20, 18 and 16 pages. Which statements are correct?

(A)
The total demand is 54 pages, which exceeds the 50 frames, so thrashing is likely if all three stay active.
(B)
Suspending the process with working set 18 leaves a total demand of 36 pages, within the 50 frames.
(C)
Admitting more processes is the right response when CPU utilisation is low because of heavy paging.
(D)
Suspending the process with working set 16 leaves a total demand of 34 pages.

Answer and solution

Answer: (A), (B)

$D = 20 + 18 + 16 = 54 > 50$ , so A is true.
Removing 18 leaves $54 - 18 = 36 \leq 50$ , so B is true.
C is false: low utilisation caused by paging means more processes worsen thrashing.
Removing 16 leaves $54 - 16 = 38$ , not 34, so D is false.

PRACTICE 41 mark · MSQ

Which of the following page-replacement algorithms are stack algorithms, so that they can never show Belady's anomaly?

(A)
Optimal (OPT)
(B)
Least recently used (LRU)
(C)
First in first out (FIFO)
(D)
Second chance (clock) with reference bits

Answer and solution

Answer: (A), (B)

A stack algorithm keeps the set of pages for n frames inside the set for n+1 frames after every reference.
OPT and LRU satisfy this property.
FIFO does not. Second chance does not either: with the reference bit set to 1 on load, the string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 gives 9 faults with 3 frames and 10 with 4.

PRACTICE 51 mark · NAT

A system has 80 free frames and three processes of sizes 10, 30 and 60 pages. Frames are divided in proportion to process size. The number of frames given to the 60-page process is ______.

Answer and solution

Answer: $48$

Total size $= 10 + 30 + 60 = 100$ pages.
$a = \frac{60}{100} \times 80 = 48$ frames.

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE CS

virtual memory

Preparing in Kolkata? IAE Academy's course for GATE CSE.