GATE IT 2007 | Question: 12

Question

The address sequence generated by tracing a particular program executing in a pure demand paging system with $100$ bytes per page is

$\text{0100, 0200, 0430, 0499, 0510, 0530, 0560, 0120, 0220, 0240, 0260, 0320, 0410.}$

 

Suppose that the memory can store only one page and if $x$ is the address which causes a page fault then the bytes from addresses $x$ to $\text{x + 99}$ are loaded on to the memory.

How many page faults will occur?

• A. $0$
• B. $4$
• C. $7$
• D. $8$

Comments

A simpler way to solve it is to divide each address in the address sequence by number of given records to get the reference string:

0100/100, 0200/100, 0430/100, 0499/100, ..........., 0370/100 will give us 1, 2, 4, 4, 5, 5, 5, 1, 2, 2, 2, 3, 3

Now we have only one frame which doesn't have any page. So when 1 is referenced, a page fault occurs and 1 is brought into the frame,  then 2 is referenced and another page fault occur since there is no 2 in frame (only one frame and it has 1). Now 2 is brought into this one frame (1 is removed). Then 4 is referenced and again page fault occurs, 4 is brought into the frame (2 is removed). Total 3 page faults by now. Then 4 is referenced again, since 4 is already in the frame no page fault. When 5 is referenced there is a page fault and 5 is brought into the frame. Next two reference bits are 5 and since 5 is already in frame no page faults occur. So far we have 4 page faults. Then 1 is referenced and we get a page fault (total five page faults). 1 is brought into the frame now. Then 2 is reference causing another page fault (total six page faults). Two is brought into the frame. Next again 2 is referenced twice which is already in the frame so no page fault. Then 3 is referenced which is not in the frame so page fault occurs (total seven page faults) and 3 is brought into the frame. The last reference bit is 3 which is already present in the frame so no page fault occurs. Hence we have a total of seven page faults.

---

@bleed red I think your method is wrong for this question. The last reference in question is $410$, which you have mistakenly taken to be $370$. Applying your method in actual sequence in question is giving $8$ page faults - which is not correct. Maybe this method can be used in such a scheme where, if the reference is to access $429$ and we take address $400-499$  to memory as we did in this question. https://gateoverflow.in/2619/gate1995_2-7

---

as it specifies when x is called we bring x+99 addresses, so we dont divide the pages ( 0 to 99 ) as page 0 , pages (100 to 199) as page 1, pages (200 to 299) as page 2 and so on !!!!!

which was done in https://gateoverflow.in/2619/gate-cse-1995-question-2-7 

is my logic correct ??

---

nice twist of 1995 question

Answer 1

$0100$ - page fault, addresses till $199$ in memory

$0200$ - page fault, addresses till $299$ in memory

$0430$ - page fault, addresses till $529$ in memory

$0499$ - no page fault

$0510$ - no page fault

$0530$ - page fault, addresses till $629$ in memory

$0560$ - no page fault

$0120$ - page fault, addresses till $219$ in memory

$0220$ - page fault, addresses till $319$ in memory 

$0240$ - no page fault

$0260$ - no page fault

$0320$ - page fault, addresses till $419$ in memory 

$0410$ - no page fault

So, $7$ is the answer- (C)

Comments

100/100 thanks sir............

---

@jatin khachane I came here just to ask this question only..”What is that line was not given? Could we be able to find out the answer even after that?” Have you got the answer?

---

@jatin khachane 1
 

If it is not explicitly stated, we follow the standard behavior of paging systems, which is to load the entire page that the address belongs to, based on the page size.

---

Answer:

In a paging system, for address x=0430x = 0430, the page containing 0400 to 0499 would be loaded into memory. The range is based on multiples of the page size, not the position of the specific address within the page.

This is standard behavior unless explicitly stated otherwise.

Answer 2

Option C is correct we will get 7 page faults. since for each fault, only 100 bytes will be loaded from the faulted byte onwards. 0100 causes fault then 0100 to 0199 will be loaded. Reffering to any byte in this range will not cause any fault. But next is 0200 which is not available so it is fault will load 0200 to 0299. like that we will have total 7 faults.

Answer 3

Consider [A-B] is range of numbers loaded on to the page or frame in Main memory. if 'A' referred B=A+99, this is given.

Loading sequences

for references 100, 200, 430, 530, 120, 220, 320 following are the contents in the page

[100-199] ==> [200-299] ==> [430-529] ==> [530-629] ==> [120-219] ==>[220-319] ==> [320-419]

 

count the transformations which is = 7

Answer 4

Since it is pure demand paging, 0 pages to start with MM. First fault will hit for record 0100.