9 votes 9 votes Suppose: TLB lookup time = 20 ns TLB hit ratio = 80% memory access time = 75 ns swap page time = 500,000 ns 75% of pages are dirty OS uses a 3 level page table What is the effective access time (EAT) if we assume the page fault rate is 15% ? Operating System operating-system demand-paging memory-management multilevel-paging + – biranchi asked Jan 25, 2017 • retagged May 22, 2020 by soujanyareddy13 biranchi 4.7k views answer comment Share Follow See 1 comment See all 1 1 comment reply Bikram commented Aug 26, 2017 reply Follow Share Indeed 75140 is correct answer .. see this why it is correct http://www.cs.jhu.edu/~yairamir/cs418/os5/tsld028.htm 0 votes 0 votes Please log in or register to add a comment.
Best answer 13 votes 13 votes EAT=No Page Fault(TLB hit+TLB miss)+ Page Fault (TLB hit+TLB miss+ Page swap time) =0.85(0.8(20+75)+0.2(20+3$\times$75+75))+0.15(0.8(20+75)+0.2(20+3$\times$75+75)+500000) =119+75021=75140 ns srestha answered Jan 25, 2017 • edited Apr 27, 2019 by srestha srestha comment Share Follow See all 41 Comments See all 41 41 Comments reply Akriti sood commented Jan 25, 2017 i edited by Akriti sood Jan 25, 2017 reply Follow Share @srestha,what is dirty bit doing here??and page swap time is btw disk and MM?? and when there is a page fault and no dirty page,then why r u multiplying 3 with M time??in that case we have to bring data from disk..right?so page swap time should be there while in dirty page case,you are not considering the address translation time at all. there aere 3 levels,so 3 time accessing M.M for page tbles and 4th time for the data. AND CAN I USE THIS FORMULS- tlb hit time + tlb miss rate*(3* MM access) ///time for address translation as there are 3 tables + MM. time + page fault rate*(page fault routine) //for getting the data 0 votes 0 votes Akriti sood commented Jan 25, 2017 reply Follow Share you should add one extra MM time for reading the data. 0 votes 0 votes Sushant Gokhale commented Jan 25, 2017 reply Follow Share Getting approximate 431 microsec 0 votes 0 votes Akriti sood commented Jan 25, 2017 reply Follow Share @sushant..equation?? 0 votes 0 votes Sushant Gokhale commented Jan 25, 2017 reply Follow Share https://gateoverflow.in/35154/write-back-and-write-through 0 votes 0 votes Akriti sood commented Jan 25, 2017 reply Follow Share @sushant,in that question,page fault is not there. what happens when there is a page fault and no dirty bit?? my equation is - tlb hit time + tlb miss rate*(3* MM access) ///time for address translation as there are 3 tables + no page fault * MM time + page fault *( dirty bit rate * () + no dirty bit *() ) //for getting the data not getting what to write in those brckets.please suggest 0 votes 0 votes Sushant Gokhale commented Jan 25, 2017 reply Follow Share @Akriti. I will start with M.M Avg M.M access time(considering only M.M and secondary mem) = 0.85(75) + 0.15(75 + 5*105 + 0.75*5*105) = 431250 ns (approx) Assuming page tables always reside in M.M ( atleast outermost level should reside. We should also calculate paging for inner 2 page tables but here for simplification I m not taking) Avg Access time = TLB HR*( 20 + 431250) + TLB MR *( 20 + 3*page table access + 431250) = 0.8 * (20 + 431250) + 0.2*(20 + 3*75 + 431250) = 431.25 microsec 0 votes 0 votes cse23 commented Jan 25, 2017 reply Follow Share @srestha during page fault service time if page is not dirty then why time is 3*MM access time? if this is not dirty page then simply we have to replace it with the required page..and we bring the page from secondary memory which is nothing but page fault service time and it is not given in the question.. if it is diry then along with page replacement we have to write it back to swap space 0 votes 0 votes Akriti sood commented Jan 25, 2017 reply Follow Share @sushant,i think there is some caculation mistake in your MM time calculation i am not getting 431250 ns..and in case of page fault,if no dirty bit is there then we take 50000 time to bring the page from disk,and in case of dirty bit,we take one 50000 time for bringing it to MM and second for writing the block back..right?? whats the problem in my equation??i am just adding ddress translation time with data access time. 0 votes 0 votes The_Toad_Sage commented Jan 25, 2017 i edited by The_Toad_Sage Jan 25, 2017 reply Follow Share I'm getting an equation like this: 20+ (0.2*3*75) + 75 + 0.15*500000 (0.75*(500000)) ns 0 votes 0 votes Rahul Jain25 commented Jan 25, 2017 reply Follow Share @sushant Didnt get your average memory access formula. Why are you addint swap time again by multiplying by 0.75?? 0 votes 0 votes Sushant Gokhale commented Jan 25, 2017 reply Follow Share @Akriti. I have approximated at many places. When there too high numbers involved, I have ignored rest of the numbers. Regarding dirty pages, I have added addtional time to 1 normal disk access(in case of page fault) i.e. 1 disk access + 0.75 * 1 disk access 0 votes 0 votes Rahul Jain25 commented Jan 25, 2017 reply Follow Share So sushant you have taken disk access time same as swap time. Is swap memory part of disk??? And they should have given the disk access time right??? Or we have to take same swap time and disk time?? 0 votes 0 votes Akriti sood commented Jan 25, 2017 reply Follow Share I GOT THAT SUSHANT,but i can also solve with my equation..yes or no?? 0 votes 0 votes Sushant Gokhale commented Jan 25, 2017 reply Follow Share @Rahul. When there are dirty pages, first you need to write the page back to disk and then normal operation. Hence, that additonal 0.75 * 1 disk access time component 0 votes 0 votes Akriti sood commented Jan 25, 2017 reply Follow Share @rahul,yes ,,they should have given the disk access time 0 votes 0 votes Rahul Jain25 commented Jan 25, 2017 reply Follow Share @akriti @sushant is the swap space part of disk or seperate??? If swap space is part of disk then sushants formula is correct. 0 votes 0 votes Sushant Gokhale commented Jan 25, 2017 reply Follow Share @Rahul. Swap time is just to bring the page into mem. Its not same as page fault service time. @Akriti. I go step by step, hierarchically, from lower level of mem to higher level. I really dont use those difficult formulaes nor understand them :P 0 votes 0 votes Sushant Gokhale commented Jan 25, 2017 reply Follow Share Consider swap as disk part. Not sure of swap space on MM. Consider swap time as disk access time 0 votes 0 votes Rahul Jain25 commented Jan 25, 2017 reply Follow Share Definately not in main memory. Alright I think I got it, first write if page dirty and then swap. Thanks @sushant. 1 votes 1 votes Akriti sood commented Jan 25, 2017 reply Follow Share @sushant,its not a formula. i was just considering address translation time + data access time 0 votes 0 votes srestha commented Jan 25, 2017 reply Follow Share I have a question. Is it given write back? then why need dirty page to consideration? 0 votes 0 votes Rahul Jain25 commented Jan 25, 2017 reply Follow Share @sreshta you are going towards cache concept. And here we have work with main memory and secondary memory. And when we swap the page if dirty bit then we have to erite that page in disk or secondary memory. 0 votes 0 votes ankyAS commented Feb 2, 2017 reply Follow Share why are u multiplying 3*75 .is it for dirty read? 0 votes 0 votes Kaluti commented Feb 25, 2017 i edited by Kaluti Aug 27, 2017 reply Follow Share First I will calculate average memory access time 0.80*(20+75)+.20*(20+4*75) that will come out to be 140ns now after that average instructions execution time .15*(.75*(75+5*10^(5))+.25*(75+1*5*10^(5))+(100-.15)*140 that will come out to be 131191 ns approx here page fault service time not given so I have indirectly calculated to be page swap time plus writing it to disk if it is dirty read lus updating page table if it is nt dirty read then only swaping and udating page table and it is right swap space is part of disk plz correct if it is wrong 0 votes 0 votes ninja_hattori commented Mar 12, 2018 reply Follow Share where is 75% used in this equation ? 0 votes 0 votes Abbas2131 commented Sep 6, 2018 reply Follow Share @srestha maam, why have you taken only 3 memory accesses when 3 level page table table is given. shouldn't it be 4? 0 votes 0 votes Ritwik Mishra 1 commented Apr 27, 2019 i edited by Ritwik Mishra 1 Apr 27, 2019 reply Follow Share It should be 500,000 in the answer 50,000 is written 0 votes 0 votes srestha commented Apr 27, 2019 i edited by srestha Apr 27, 2019 reply Follow Share ok now? 0 votes 0 votes ayushsomani commented Jul 26, 2019 reply Follow Share @ninja_hattori Since, Swapping page time is same for both the cases i.e. If Page is not dirty and if Page is dirty, therefore, we get Page Service time equal to Swapping page time. https://gateoverflow.in/?qa=blob&qa_blobid=2405338696923312454 0 votes 0 votes Kaurbaljit commented Nov 21, 2019 reply Follow Share https://gateoverflow.in/238144/test-series Almost same question, but two different approaches. @srestha can you please make it clear? 0 votes 0 votes srestha commented Nov 22, 2019 reply Follow Share @Kaurbaljit What is your ans? I mean is there any mistake in solution? 0 votes 0 votes Kaurbaljit commented Nov 22, 2019 reply Follow Share I meant, in one question you have considered 2 disk-operations when the page is dirty and while in another similar question you haven't. @srestha 0 votes 0 votes srestha commented Nov 22, 2019 reply Follow Share @Kaurbaljit If we done both like same question, then Sushant Gokhle solution is matching in comment section. right? Though I am not sure, if this solution has any mistake. 0 votes 0 votes Kaurbaljit commented Nov 22, 2019 reply Follow Share Actually in one solution you have considered the page-fault in case of TLB-hit and in another one you simply discarded. I am not getting that specifically. According to me following should be more generalized- TLb-hit*(page-fault + no page-fault) + TLB-miss*(page-fault + no page-fault) likewise you did here in above question, but instead 2 disk-accesses should have been considered in dirty-page's case, rest is all good. @srestha @Satbir can you please clear this doubt? 0 votes 0 votes rituraj2847 commented Nov 25, 2019 reply Follow Share @srestha How would we solve if write back policy is used? 0 votes 0 votes srestha commented Nov 25, 2019 reply Follow Share write back policy should be mentioned then. Here it is not mentioned, so no need of write back 0 votes 0 votes rituraj2847 commented Nov 25, 2019 reply Follow Share I mean in case of write back policy, what would be the solution? 0 votes 0 votes srestha commented Nov 25, 2019 reply Follow Share How much r u getting then? 0 votes 0 votes suvradip das commented Mar 13, 2020 reply Follow Share @baljeetkaur you are absolutely on point. Since the page is dirty we need two spaps and one swap for a non dirty page. @sreshtha youre answer may have matched but you did like this for otyher test series question. 0 votes 0 votes sachin486 commented Sep 5, 2020 reply Follow Share I don’t understand why in page fault (0.15) TLB hit time is considered….because in case of page fault obviously 100% there will be TLB miss 0 votes 0 votes Please log in or register to add a comment.
4 votes 4 votes we can also solve like this - Prateek Raghuvanshi answered Aug 26, 2018 • edited Aug 26, 2018 by Prateek Raghuvanshi Prateek Raghuvanshi comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments Prateek Raghuvanshi commented Nov 5, 2018 reply Follow Share Why are you relating this to page fault ??we need page tables for address translation,we are not considering page fault . 0 votes 0 votes 3lurryface commented Dec 31, 2019 reply Follow Share @Gurdeep Saini that is my doubt for almost one year from now that why there is no page fault while accessing multi-level page tables. It is only possible if all the pages of inner page tables are present in memory all the time but then what is the use of multilevel paging when we need to store whole inner page tables in memory it makes no sense at all. 0 votes 0 votes suvradip das commented Mar 13, 2020 reply Follow Share @prateek since the page is dirty the definitely we need two swaps, one swap for writing the page onto the secondary memory and another onr for getting the new page into the main memory. Hence the effective Page fault service time = (dirty page *(time to service a dirty page main memory access time) + no dirty page( time to service a non dirty page + main memory access time) =(0.75( 2*500,000 + 75) + 0.25(500,000 + 75)) ns 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes https://gateoverflow.in/?qa=blob&qa_blobid=2405338696923312454 ayushsomani answered Jul 26, 2019 ayushsomani comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes EAT=No Page Fault(TLB hit+TLB miss)+ Page Fault (TLB hit+TLB miss+ Page swap time + dirty pages x page swap time) =0.85[ 0.8(20+75)+0.2(20+3×75+75) ]+0.15[ 0.8(20+75)+0.2(20+3×75+75)+500000 +.75x500000 ] =93890 ns reference question – https://gateoverflow.in/77917/testbook-os-test sachin486 answered Sep 12, 2020 • edited Sep 13, 2020 by sachin486 sachin486 comment Share Follow See all 0 reply Please log in or register to add a comment.