Test by Bikram | Operating Systems | Test 2 | Question: 29

Question

In a paged memory, the page hit ratio is $0.35$. The time required to service the page fault is $100$ ns. Time required to access a page in primary memory is $10$ ns.

The average time required to access a page is ________ ns

Answer 1

Page access time=   
(1-page fault)*(Time required to access a page in primary memory) + (page fault) * Miss penalty

We assume page access is Simultaneous !

page fault rate is (1- hit ratio) = 1- 0.35 = 0.65 

Time required to access a page in primary memory is 10 ns as given .

Time to access page in primary memory  ( Tp) =  (1- 0.65)  * 10 = 0.35 * 10 = 3.5 ns.

Time required to access page in secondary memory is the Miss penalty time which is  100 ns as given .
Miss ratio =(1- 0.35)=0.65

Missed pages will be found  in secondary memory.

Time to access page in secondary memory ( Ts)   =  Miss ratio * time for secondary memory
=(1-0.35)*100
=65.0ns

Average time required to access a page is
= Ts+Tp

=65.0ns+3.5ns

=68.5ns

PS :

Read this comment to make everything clear : https://gateoverflow.in/96884/operating-systems-2-29#c125175

Comments

Bikram Sir , I read the above and below comments .

But still not getiing why u didnt add the time in second part . means lets take a example if there are 100 page access required . then 35 out of 100 will be find in primary level  . so time taken = 35*10 ns

and rest 65 will not be found in primary level (but how we will get to know that it is found in primary level , for that we need to access the primary level also so 10 ns should be added ) and then secondary storage access= 100 ns , so total time = 65*110 ns
 

so avg access time  (350+7150)/100 =75 ns

sir correct me , where  i am doing mistake.

---

No, you are thinking like what lokesh said ?

 for second case there is a miss means page is not found in primary memory and we have to look for secondary memory so why to search for again in primary memory ?

just think once again please.

---

Sir fine , It is not a problem . But you said "for second case there is a miss means page is not found in primary memory and we have to look for secondary memory "

But my doubt is HOW ???? 
how it will know that page is not available in primary memory ? For that is it not required to access the primary memory ??

If we alraedy know earlier that this is the page not available in primary memory then definitely we will not searchit again in primary memory . But how we will get that information without accessing the primary memory ??? 

And if it is simultaneous access then I am ok with solution .But nothing is given about simultaneous access/ hirerichal access in the question ??

---

and If it is hierarichal access .
sir if there are 100 page access . in ideal case if all found in primary level then time required =  100*10 =1000 ns

but 65 access out of 100 will result in to panalty . which is something extra then normal cost .

65*100=6500 ns

so tatal time for avg access = (1000+6500 ) / 100 = 75 ns

---

see @amit, 

i read all your comments even you see this page it also support my answer-http://stackoverflow.com/questions/7051959/average-page-access-time-os read second comment ,

Now for your How part .. page is missing means that page is not found in primary memory ,

if the requested data is in the local store (cache hit, cache access time)
 return the requested data
   else (cache miss, lower-level access time)
  get the requested and nearby data from the lower level

see this https://www.d.umn.edu/~gshute/arch/cache-performance.xhtml

---

Yes sir , I understood by the link u have shared at the last . There it is written that miss penalty is the difference  between lower level access time and cache access time..

so here in the formula you have used , it should be :

hit rate * primary memory access time + miss rate * secondary memory access time

= (1 -miss rate)* primary memory access time + miss rate * secondary memory access time

=primary memory access time + miss rate * (secondary memory access time  -  primary memory access time)

= primary memory access time + miss rate * miss penalty

Sir your answer is 100 % right :)
but  the formula u have used there at the place of miss penalty it should be secondary memory access time . though u have used secondary memory access time in the calcukation .

Thanks for sharing the link Sir :)

---

you have considered secondary memory access time as page fault service time which is wrong.

answer should be 75 ns

---

@sushmita

See here, page is missing means that page is not found in primary memory , so it would be found in Secondary memory itself , that's why we need to consider secondary memory access time as page fault service time .

please read my above discussions with Amit Paul .. and check those links .

My answer is correct here .

---

correct sir (y) ..

First of all, need to consider simult. memory access(by default, because GATE has given ans assuming simult. access in prev year) unless told hierarchical.

BTW very good healthy discussion. (y)

---

@amit and @sushmita

page access is simultaneous that we assume , as in previous gate questions we can see to assume simultaneous access to take in consideration ..

even in this link http://stackoverflow.com/questions/7051959/average-page-access-time-os 

you can find two different answers for this same question, one from simultaneous access another from hierarchical access .

if we use simultaneous access then answer is 68.5 ns

if we use hierarchical access then answer is 75 ns

but in previous year gate papers if you solve, you will find that Gate committee have use simultaneous access by default .

so we need to assume that page access is simultaneous here .

That's why 68.5 ns is correct answer.

---

@sushmita..

We had a lot of discussion on this concept... At many places, this concept has been discussed considering only hierarchical access whereas at another place assuming simult. access. So don't get confused. Arjun sir also had given many solutions assuming hierarchical access but once (in dec-Jan 16-17) Bikram sir pointed out it correctly and with many reference and many prev. year GATE questions, he made it clear that we need to assume stimult.. access whenever we find this type of question where we are given two or more level memory access. But be careful, if it is mentioned explicitly to take hierarchical then assume it accordingly ..  but in GATE we assume SIMULTANEOUS access by default.

you can see prev. year question for ref.

---

bikram sir , 

sir suppose we want a page called Page X which is not in the main memory. How does the entire search takes place ?

This what I thought how the procedure worked - 

1) Page Table (assuming there is one) will search for Page X and wont find any, this will lead to page fault.

2) This will begin the page fault service time  where the it will access the secondary memory for Page X and once found will load it into the primary memory and update the page table.

3) Now we will access the primary memory knowing it is loaded into the primary memory successfully.

Am I going wrong some where ?

---

 @amit and @harsh 

Yes, Harsh , you guess it correctly .

It is given that , time required to access page in secondary memory is 100 ns ..

here that 100 ns is for page fault time  includes Accessing the page in secondary memory + Loading the page in main memory + Accessing the page in Main memory.

so  Accessing the page in Main memory +   Accessing the page in secondary memory + Loading the page in main memory = 100 ns 

why so , because it is Simultaneous access we take into consideration.

Now , if it is hierarchical access, then  page fault time can  be  =  10 ns to load and access the main memory + 100 ns  to access the secondary memory .

---

@ Vijay, but arjun sir himself said to take hierarchical access by default at many places??

---

Thanx sir.

---

@harsh
same procedure i used to follow and I feel personally that our mind think in hierarchical way so i find it easy to understand .
But in Gate question until in the question is is mentioned for hierarchical access only then we will go for hierarchical approach otherwise we will consider the simultaneous access approach .

---

@sushmita

when explicitly they mention the hierarchical Access only then we will go with hierarchical approach otherwise we will consider the simultaneous access . As we can observe in previous gate papers, this is how gate committee takes access into consideration.

---

Thank you so much Bikram sir.

---

Update : 

After discussing with Bikram Sir , this what we could conclude - 

1) Simultaneous and Hierarchical access is related only when dealing between Cache memory and Main memory, where

   a) Write Back meant writing on the cache and only when a block has to be replaced in the cache we write      back the contents of that block to the main memory thus making it a Hierarchical access  and 

   b) Write Through meant writing onto the cache and main memory simultaneously whenever the contents          are modified making it simultaneous access. 

2) When dealing with Primary memory and Secondary Memory , there is no specific thing as simultaneous and hierarchical access.

The general procedure goes this way - 

Suppose we want a page called Page X which is not in the Main memory, the following things will happen  -

1) Page Table (assuming there is one) will search for Page X and wont find any, this will lead to Page Fault.

2) This will begin the Page Fault Service Time  where the it will access the Secondary memory for Page X and once found will load it into the Primary memory and update the page table.

3) Now we will access the Primary memory knowing it is loaded into the Primary memory successfully.

Now , in the above question it was earlier stated that -

 " The time required to access page in secondary memory is 100 ns. " , then the Page Fault Service Time  would be 100 + 10 = 110 ns. 

Now , after being rephrased to -

 " The time required to service the page fault is 100 ns. " , then Page Fault Service Time would be  100 ns ( as it includes everything)

---

Thanks much @Harsh , i am grateful to you as always :)

just one comment in your note to make it more clear :

in last line you said , as it includes everything .. where everything means Accessing the page in secondary memory + Loading the page in main memory + Accessing the page in Main memory = 100 ns .

Here that 100 ns is for service the page fault time given in the question .

Answer 2

0.35 ( 10 + 10 ) + 0.65( 10 + 100) = 78.5

Comments

i think you are talking about this one ;

Effective Access Time := (TLB_search_time + 2*memory_access_time) * (1- hit_ratio) +
       (TLB_search_time + memory_access_time) * hit_ratio

but this question we need average  time require to access a page .

---

oohh , i got it. I was thinking of effective address time but the question is for average. Thank you sir

---

sir , as u said ...

and for second case there is a miss means page is not found in primary memory and we have to look for secondary memory so why to search for again in primary memory ?

But how it will know that page is not available in primary storahe for that it need to search i primary memory .

In fact for each page access we need to look in primary storage . out of which 35 time we will get the the page in primary storage and 65 time we didnt get in primary memory so need to search in secodary.

Answer 3

$0.65(100ns)+0.35(10ns)=65ns+3.5ns=68.5ns$