Virtual Memory and Page Replacement Questions and Answers

Q: The *-marked references cause page replacements.Which one or more of the following could be the page replacement policy/policies in use?

The policy could only be the Optimal page replacement policy.Check each replacement against the policies, counting for LFU and MFU every reference made to a page so far:Reference 4 (frames 1, 2, 3): page 2 is replaced. Optimal evicts the page used farthest in the future: 1 is next used at the 7th reference, 3 at the 12th, 2 at the 13th, so 2 goes. LRU would evict 1, the least recently used, so LRU is ruled out.Reference 6 (frames 1, 4, 5): page 1 is replaced. Optimal agrees (next uses: 4 at the 9th, 5 at the 10th, 1 at the 11th). LFU would evict 5, referenced once, against twice for 1 and 4, so LFU is ruled out.Reference 3, the 12th (frames 6, 1, 5): page 5 is replaced. Page 1 has by then been referenced three times, 5 twice and 6 once, so MFU would evict 1, ruling MFU out. Optimal is free to evict 5, since none of the three pages is used again.The remaining replacements (5 replaces 3, 1 replaces 4, 2 replaces 6) also agree with Optimal, so it is consistent with every step.

Q: In which one of the following page replacement algorithms it is possible for the page fault rate to increase even when the number of allocated frames increases?

The algorithm is FIFO (First In First Out).FIFO can suffer from Belady’s anomaly: for some reference strings, giving a process more frames produces more page faults. The standard example is the string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, which causes 9 faults with 3 frames but 10 with 4.LRU and OPT are stack algorithms: the set of pages in memory with \(k\) frames is always a subset of the set with \(k + 1\) frames, so adding frames can never increase the faults. MRU, which evicts the most recently used page, is not the algorithm the anomaly is known for; FIFO is the classic case.

Q: 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?

The page fault rate is \((X - M) / (D - M)\).If \(p\) is the page fault rate, a fraction \(p\) of accesses take \(D\) units and the rest take \(M\) units, so the measured average is\[ \begin{aligned} X &= (1 - p)M + pD \\ X - M &= p(D - M) \\ p &= \frac{X - M}{D - M} \end{aligned} \]Check: if no access faults, \(X = M\) and \(p = 0\); if every access faults, \(X = D\) and \(p = 1\). The option \((D - M)/(X - M)\) is the reciprocal and exceeds 1. \((D - X)/(D - M)\) is the hit rate \(1 - p\), and \((X - M)/(D - X)\) is the ratio of faults to hits.

Q: Thrashing means :

Thrashing means an increase in paging activity.When too many processes are in memory and each has fewer frames than its working set, they page fault constantly. The system spends most of its time swapping pages in and out rather than executing, so paging activity rises sharply while useful work collapses.Thrashing is the opposite of higher throughput and higher CPU utilisation: both fall. It is often triggered by raising the degree of multiprogramming too far, but the increase in multiprogramming is the cause, not what thrashing means.

Q: Suppose that the number of instructions executed between page fault is directly proportional to the number of page frames allocated to a program. If the available memory is doubled, the mean interval between page faults is also doubled. Further, consider that a normal instruction takes one microsecond, but if a page fault occurs, it takes 2001 microseconds. If a program takes 60 sec. to run, during which time it gets 15,000 page faults, how long would it take to run if twice as much memory were available ?

The program would take 45 sec.Each page fault costs 2001 microseconds instead of 1, so it adds 2000 microseconds over a normal instruction.\[ \begin{aligned} \text{fault time} &= 15000 \times 2000\ \mu s = 30\ s \\ \text{normal time} &= 60 - 30 = 30\ s \end{aligned} \]With twice the memory, the interval between faults doubles, so the number of faults halves to 7,500, while the normal execution time is unchanged:\[ \begin{aligned} \text{new time} &= 30 + 7500 \times 2000\ \mu s \\ &= 30 + 15 = 45\ s \end{aligned} \]30 seconds would be halving the whole run time, wrongly treating the normal instructions as reduced too, and 60 seconds ignores the saving.

Q: In a demand paging memory system, page table is held in registers. The time taken to service a page fault is 8 m.sec. if an empty frame is available or if the replaced page is not modified, and it takes 20 m.sec. if the replaced page is modified. What is the average access time to service a page fault assuming that the page to be replaced is modified 70% of the times ?

The average time is 16.4 m.sec.The page to be replaced is modified 70% of the time, costing 20 ms, and unmodified (or a free frame is available) 30% of the time, costing 8 ms.\[ \begin{aligned} t &= 0.3 \times 8 + 0.7 \times 20 \\ &= 2.4 + 14 = 16.4\ \text{ms} \end{aligned} \]11.6 ms comes from swapping the two percentages, 14 ms is the simple average of 8 and 20, and 28 ms adds them.

Direction for [ Question No: 1 To 1 ] :

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	after
-	1*	2*	3*	4*	5*	4	1	6*	4	5	1*	3*	2*
-	1	1	1	1	1	1	1	6	6	6	6	6	2
-	-	2	2	4	4	4	4	4	4	4	1	1	1
-	-	-	3	3	5	5	5	5	5	5	5	3	3

The *-marked references cause page replacements.

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

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

Exam Year(s)

GATE CS - 2025,

Answer: D

The policy could only be the Optimal page replacement policy.

Check each replacement against the policies, counting for LFU and MFU every reference made to a page so far:

Reference 4 (frames 1, 2, 3): page 2 is replaced. Optimal evicts the page used farthest in the future: 1 is next used at the 7th reference, 3 at the 12th, 2 at the 13th, so 2 goes. LRU would evict 1, the least recently used, so LRU is ruled out.
Reference 6 (frames 1, 4, 5): page 1 is replaced. Optimal agrees (next uses: 4 at the 9th, 5 at the 10th, 1 at the 11th). LFU would evict 5, referenced once, against twice for 1 and 4, so LFU is ruled out.
Reference 3, the 12th (frames 6, 1, 5): page 5 is replaced. Page 1 has by then been referenced three times, 5 twice and 6 once, so MFU would evict 1, ruling MFU out. Optimal is free to evict 5, since none of the three pages is used again.

The remaining replacements (5 replaces 3, 1 replaces 4, 2 replaces 6) also agree with Optimal, so it is consistent with every step.

Discuss in Forum

Which of the following is a storage allocation scheme in which secondary memory can be addressed as though it were part of the main memory?

A.Virtual memory
B.Secondary memory
C.CPU register memory
D.CPU buffer memory

Exam Year(s)

DSSSB TGT - 2023,

Answer: A

Virtual memory is the storage allocation scheme in which secondary memory (the disk) can be addressed as if it were part of main memory, so a program can be larger than the physical RAM. Secondary memory is the storage itself and not the scheme, and CPU registers and CPU buffers are small fast storage inside or beside the processor, not a way of addressing the disk as memory. A page of a program that is not in RAM is kept on the disk and brought in when needed, so the program behaves as if it had a much larger memory than is installed.

Discuss in Forum

In which one of the following page replacement algorithms it is possible for the page fault rate to increase even when the number of allocated frames increases?

A.LRU (Least Recently Used)
B.OPT (Optimal Page Replacement)
C.MRU (Most Recently Used)
D.FIFO (First In First Out)

Exam Year(s)

GATE CS - 2016,

Answer: D

The algorithm is FIFO (First In First Out).

FIFO can suffer from Belady’s anomaly: for some reference strings, giving a process more frames produces more page faults. The standard example is the string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, which causes 9 faults with 3 frames but 10 with 4.

LRU and OPT are stack algorithms: the set of pages in memory with \(k\) frames is always a subset of the set with \(k + 1\) frames, so adding frames can never increase the faults. MRU, which evicts the most recently used page, is not the algorithm the anomaly is known for; FIFO is the classic case.

Discuss in Forum

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)

Exam Year(s)

GATE CS - 2018,

Answer: B

The page fault rate is \((X - M) / (D - M)\).

If \(p\) is the page fault rate, a fraction \(p\) of accesses take \(D\) units and the rest take \(M\) units, so the measured average is

\[ \begin{aligned} X &= (1 - p)M + pD \\ X - M &= p(D - M) \\ p &= \frac{X - M}{D - M} \end{aligned} \]

Check: if no access faults, \(X = M\) and \(p = 0\); if every access faults, \(X = D\) and \(p = 1\). The option \((D - M)/(X - M)\) is the reciprocal and exceeds 1. \((D - X)/(D - M)\) is the hit rate \(1 - p\), and \((X - M)/(D - X)\) is the ratio of faults to hits.

Discuss in Forum

Thrashing means :

A.Increase in multiprogramming
B.Increase in paging activity
C.Increase in throughput
D.Increase in cpu utilization

Exam Year(s)

MH SET - 2018, SET Exam - 2018,

Answer: B

Thrashing means an increase in paging activity.

When too many processes are in memory and each has fewer frames than its working set, they page fault constantly. The system spends most of its time swapping pages in and out rather than executing, so paging activity rises sharply while useful work collapses.

Thrashing is the opposite of higher throughput and higher CPU utilisation: both fall. It is often triggered by raising the degree of multiprogramming too far, but the increase in multiprogramming is the cause, not what thrashing means.

Discuss in Forum

Suppose that the number of instructions executed between page fault is directly proportional to the number of page frames allocated to a program. If the available memory is doubled, the mean interval between page faults is also doubled. Further, consider that a normal instruction takes one microsecond, but if a page fault occurs, it takes 2001 microseconds. If a program takes 60 sec. to run, during which time it gets 15,000 page faults, how long would it take to run if twice as much memory were available ?

A.60 sec.
B.30 sec.
C.45 sec.
D.10 sec.

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

Answer: C

The program would take 45 sec.

Each page fault costs 2001 microseconds instead of 1, so it adds 2000 microseconds over a normal instruction.

\[ \begin{aligned} \text{fault time} &= 15000 \times 2000\ \mu s = 30\ s \\ \text{normal time} &= 60 - 30 = 30\ s \end{aligned} \]

With twice the memory, the interval between faults doubles, so the number of faults halves to 7,500, while the normal execution time is unchanged:

\[ \begin{aligned} \text{new time} &= 30 + 7500 \times 2000\ \mu s \\ &= 30 + 15 = 45\ s \end{aligned} \]

30 seconds would be halving the whole run time, wrongly treating the normal instructions as reduced too, and 60 seconds ignores the saving.

Discuss in Forum

In a demand paging memory system, page table is held in registers. The time taken to service a page fault is 8 m.sec. if an empty frame is available or if the replaced page is not modified, and it takes 20 m.sec. if the replaced page is modified. What is the average access time to service a page fault assuming that the page to be replaced is modified 70% of the times ?

A.11.6 m.sec.
B.16.4 m.sec.
C.28 m.sec.
D.14 m.sec.

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: B

The average time is 16.4 m.sec.

The page to be replaced is modified 70% of the time, costing 20 ms, and unmodified (or a free frame is available) 30% of the time, costing 8 ms.

\[ \begin{aligned} t &= 0.3 \times 8 + 0.7 \times 20 \\ &= 2.4 + 14 = 16.4\ \text{ms} \end{aligned} \]

11.6 ms comes from swapping the two percentages, 14 ms is the simple average of 8 and 20, and 28 ms adds them.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Virtual Memory and Page Replacement Questions and Answers || Virtual Memory and Page Replacement MCQ Questions and Answers || Virtual Memory and Page Replacement GK Questions and Answers || Virtual Memory and Page Replacement GK MCQ Questions || Virtual Memory and Page Replacement Multiple Choice Questions and Answers || Virtual Memory and Page Replacement GK || GK on Virtual Memory and Page Replacement || Operating Systems Questions and Answers || Operating Systems MCQ Questions and Answers || Operating Systems GK Questions and Answers || GK on Operating Systems

Virtual Memory and Page Replacement Questions and Answers

Direction for [ Question No: 1 To 1 ] :

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications