3.6k views

A virtual memory system uses First In First Out (FIFO) page replacement policy and allocates a fixed number of frames to a process. Consider the following statements:

P: Increasing the number of page frames allocated to a process sometimes increases the page fault rate.

Q: Some programs do not exhibit locality of reference.

Which one of the following is TRUE?

1. Both P and Q are true, and Q is the reason for P

2. Both P and Q are true, but Q is not the reason for P.

3. P is false but Q is true

4. Both P and Q are false.

P: Increasing the number of page frames allocated to a process sometimes increases the page fault rate.

This is true,
example : FIFO suffers from Bélády's anomaly which means that on Increasing the number of page frames allocated to a process it may sometimes increase the total number of page faults.

Q: Some programs do not exhibit locality of reference.

This is true : it is easy to write a program which jumps around a lot & which do not exhibit locality of reference.

Example : Assume that array is stored in Row Major order & We are accessing it in column major order.

So, answer is option (B). (As there is no relation between P & Q. As it is clear from example, they are independent.)

edited by
+1
but in your example- there is no locality of reference rt? In general how can we say there is no relation?
+2

P: Increasing the number of page frames allocated to a process sometimes increases the page fault rate.:- This part is very specific to FIFO, LRU & Optimal algorithm will never have this issue.

Q : If there is no locality of reference , no matter which algorithm we use, no matter how many frames we have say 2 or 3 or 5 (Assuming that no of frames are very less than no of references ), if we have big enough data set to access we will always get lot of  references , where each reference is reference to new page. So in that case, adding one more page / reducing 1 page wont make any difference.

ex :- 10000 page reference, 10 pages.

page reference like :- 1,2,3... 9999, 1,2,3,... -> In this case no matter what algorithm we use we wont get good performance.

Bottom line is Sole Reason for point P to be true is Belady's anomaly, not bad program design. (In fact here "sometimes" means using FIFO algorithm, otherwise we don't get Belady's anomaly & P is false for Optimal , LRU)

0
But what is the reason for Belady's anomaly? No locality does not imply Belady's anomaly. But full locality does imply no Belady's anomaly. Is this true?
+5
Belady's anomaly is kind of like providing"Bad" data, for hashing function. (Forgot the exact term for bad data ! ) Neither full locality nor No locality imply Belady anomaly. Though there are chances of observing belady's anomaly in case of locality ! In case of no locality, performance will be so bad, you wont notice it ! Though we can not say Belady's anomaly effect wont be present even in case of bad locality.. What is belady's anomaly- Page getting replaced currently is referenced next.. It can happen in both cases ! (Though it's effect will be more visible if we have good locality )
+3
I agree with the no relation statement, but reason is still not convincing :)
+4
Bcoz page fault occurs based on page reference pattern.(not based on locality of ref) - hope my reasoning is correct.
+1
Arjun sir since the page reference pattern is independent of spatial locality(memory where the pages are stored), but can we think of temporal locality? as it is after how much time the page is used again? But here temporral locality is not helping fifo because (012340123 in a 4 frame case)of bad page reference pattern(leading to belady's anamoly), so hence ,locality of reference is not the reason,is my thinking pattern correct?

Sir i am confused whether temporal locality is responsible?
0
Then what is the exact reason for belady's anomaly?
+1
The behaviour of Beladys anomaly because of stack algorithm,which says that at any point of time using any page replacement algorithm pages present is a frame of size n must be subset of pages present in a frame of size n+1 .

For ex: take reference string 0 1 2 3 0 1 4 0 1 2 3 4 and frame size 3 and 4.

you will observe that FIFO doesn't follow the stack algorithm that's why FIFO show Belady's anomaly.
0
@ junaid ahmad will u pls elaborate the point Q .
locality of reference means that same data value or related storage location are frequently accessed . actually ,This turns save time. i m not getting the point Q.
+1
point Q says that it is always true that a program shows locality of reference ...so the answer  is false because we can intentionally write a program which may not do so...
0
Does Bealady's Anomaly occur in LIFO replacement policy?
+1
Not sure about that,it will be iff it does not follow the stack algorithm.
0

(Belady anomaly) if and only if (not a stack algorithm). WHY ?

Can you explain it a bit may be using some example.This statement is not obvious to me.

Stack Algorithms

• A class of page replacement algorithms for which the set of pages in memory for n frames is always a subset of the set of pages that would be in memory with n+1 frames.

• (Belady anomaly) if and only if (not a stack algorithm). WHY ?

• What about OPT ? LRU ?

• Both OPT and LRU are stack algorithms.

+1

@VS

In stack algorithm, the set of pages in memory for n frames is always a subset of the set of pages that would be in memory with n+1 frames.

This means that whatever pages are present with n frames at any time, they are also present with n+1 frames.

Both optimal and LRU follow stack algorithm.

For LRU, the set of pages that would be in memory would be the n most recently referenced pages. If the number of frames is increased, these n pages will still be the most recently referenced and so will still be in memory.

But with FIFO, this is not the case. See for this reference 0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4 . FIFO doesn't follow the stack algorithm. Try it with 3 and 4 frames.

See the below image where-where * is present, the set of pages with 3 frames is not the subset of set of pages present with 4 frames.

The answer is B. Both P and Q are true But Q is not the reason for P because page fault is concerned with page present in frame not with page nearly the page accessed recently.
+1 vote

Statement P: Increasing the number of page frames allocated to a process sometimes increases the page fault rate.

Correct, as FIFO page replacement algorithm suffers from belady’s anomaly which states above statement.

Statement Q: Some programs do not exhibit locality of reference. Correct, Locality often occurs because code contains loops that tend to reference arrays or other data structures by indices. So we can write a program does not contain loop and do not exhibit locality of reference.

So, both statement P and Q are correct but Q is not the reason for P as Belady’s Anomaly occurs for some specific patterns of page references.

1
2