6.5k views
In a two-level virtual memory, the memory access time for main memory, $t_{M}=10^{-8}$ sec, and the memory access time for the secondary memory, $t_D=10^{-3}$ sec. What must be the hit ratio, $H$ such that the access efficiency is within $80$ percent of its maximum value?

edited | 6.5k views
0

why we are taking 3*10^8 as max efficiency?

srestha help pls

0
Correct me if I am wrong but since the question says within 80% shouldn't be value of hit ratio <= 80%?
0
yes hit ratio should be less than 80%
+2
Can someone please tell me, how can I distinguish which of the below formula to use:

EMAT= H(AT1) + M(AT2)

EMAT= AT1 + M(AT2)

EMAT=> Effective Memory Access Time
AT1=> Access Time for Level 1 memory
AT2=> Access Time for Level 2 memory
H=> Hit ratio of level 1 memory
M=> Miss rate of level 1 memory
(Last level memory will always be a hit)

I have came across it multiple times in Operating Systems and Computer Organization & Architecture in topics like TLB, multilevel cache, multiple memory hierarchies. I can't decide which formula to use.

+3

EMAT=hM+(1-h)(M+SM)
hM+M+SM-hM-hSM
M+SM(1-h)
EMAT=M+m(SM)

h-> hit rate for MM

M->Main Memory access time

SM->Secondary memory access time

m->miss rate for MM

This how the second equation got derived from first.

+1
Is this formula applied in parallel access also?

In $2$ level virtual memory, for every memory access, we need $2$ page table access (TLB is missing in the question) and $1$ memory access for data. In the question TLB is not mentioned (old architecture). So, best case memory access time

$= 3 \times 10^{-8}\; s$.

We are given

$3 \times 10^{-8} = 0.8 \left[ \underset{\text{2 for Page Tables and 1 Mem}}{3 \times 10^{-8}} + (1-h) \times 10^{-3}\right]$

(For above, the main memory access time and page table access times are included for all memory accesses -- hence $h$ is not multiplied with $3 \times 10^{-8})$

$\implies 0.6 \times 10^{-8} = 0.8 \times 10^{-3} - 0.8h \times 10^{-3} \\ \implies h = \frac{8 \times 10^{-4} - 6 \times 10^{-9}}{8 \times 10^{-4}} = 1 - 0.75 \times 10^{-5} \approx 99.99\%$
by Veteran
edited by
+2
Does 2 level virtual memory means two level page table??
+5
What's the meaning of the line " access efficiency is within 80% of its maximum value"?

Does it say THAT the total Access time should be within 80% of the time to work for maximum efficiency (minimum time to Access memory I.e. Time to access first two able and then data)?

@arjunsir

How did u solve after the line of ur solution "we are given" ??
+1
maximum access is access efficiency.

That is why , only best case is taken as answer
0
Maximum access means.. Maximum access in less time..Right?

I couldn't understand the equations given in Arjun sir's solution after "we are given" . Can you explain [email protected]
0

Actually in 3 level of access it could only access 80%

Among it if total hit it will take 3*10-8

otherwise in miss it will take only data access time

0

Yahh I got that reason..

Where is "h" hit time in following eqn. How we got this eqn? U are saying only 80% of it can be used then why is that whole equal to 3x 10-8 (Lhs)

"3×10-8=0.8[3×10−8+(1−h)×10−3]

⟹0.6×10−8=0.8×10−3−0.8h×10−3⟹h=8×10−4−6×10−98×10−4=1−0.75×10 "

0
Here we have assumed no page faults for page tables. ?
+1
Yes ..
0
@ ARJUN sir

What does it mean  by two level virtual  memory? Please explain  .
0
Why hit ratio is not used in the equation and only miss is used?Arjun sir can you please explain solution a bit.
+2
@Arjun Sir

plz chk the solution

$3 \times 10^{-8} = 0.8 \left[ {\color{Blue} 3} \times 10^{-8} + (1-h) \times 10^{-3}\right]$

should it not be

$3 \times 10^{-8} = 0.8 \left[ {\color{Blue} h} \times 10^{-8} + (1-h) \times 10^{-3}\right]$

doubt in that line

otherwise plz tell me why that should be 3?
0
I agree with srestha doubt

Also it says 80% of maximum value is 3*10^-8 so why are we not multiplying RHS with .8 instead of LHS
+9
@rahul 80% of its maximum value. Ok. Whatever is in LHS i.e the minimum time (best case)
if you will multiply 0.8 in LHS then it will become even lesser. So it will increase efficiency more than 100% so you will get h more than 1.
So think again.  It will be multiplied in RHS. (OR it will be divided in LHS to make time more i.e to reduce efficiency)
0
@srestha  No, Arjun Sir is correct. i.e 3 not h.
I guess you are confused because you are following another way of applying it, you are mixing these 2 way of solving the same in one.
You can see my answer I have done it in the way you are talking about.
0
@srestha @Ahwan
Please Explain a bit about "2 level virtual memory"- does it mean that the first level is the Main memory and the second level is Disk? If so why to MM is Virtual, MM use to Physical memory?

and which "2-page tables" are talked about I think it is "not 2 level page table"(which is different), are those table for separately for MM and Disk but we in general use single page table per process, so what else could be these tables?

I didn't get which "3 Main Memory reference"(except the last 1 for fetching data from MM) sir is talking about?
+4

"access efficiency is within 80 percent of its maximum value"

can be read as "access efficiency is within 80 percent of the maximum efficiency"

What is maximum efficiency ? Maximum efficiency arises when hit ratio is 100%. That means, all access of pages are in main memory. There by, $3 X 10^{-8}$ is the maximum efficiency.

I hope I am right.

--

Now, Let emat be effective memory access time, p be the miss rate, $t_{m}$ be the memory access time and PFS be the page fault service time,

emat = p( $t_{m}$ + PFS ) + (1-p)$t_{m}$

emat = p(PFS) + $t_{m}$

$3*10^{-8} = 0.8[p*10^{-3} + 3*10^{-8}]$

Now get p and h = 1-p

0

Arjun Sir, Why did you consider 2 level page table as 2 level virtual memory which in fact makes 3 level memory access [ PT1 -> PT2 -> MAIN MEMORY ]

Cant we take it as simple two level memory,  h*10-8 + (1-h)* 10-3  as effective memory access.

0

@Arjun Sir is this 2 level page table used in this problem or any other

Red line is access when miss

0

@Srestha,Here according to you h*10-8 coz the data could be found in MM or in case of a miss,it could be in SM. Am I right?Also, since there is no cache memory involved,the overhead is fairly small. Isn't it?

0
@Sir Arjun,How have we assumed that paging is being used and not swapping?If not explicitly mentioned,then we'll assume paging?
+1

As mentioned on wikipedia, The efficiency of an entity (a device, component, or system) in electronics and electrical engineering is defined as useful power output divided by the total electrical power consumed (a fractional expression),

https://en.wikipedia.org/wiki/Electrical_efficiency

Let $h$ be the hit rate then

$\Rightarrow 80 = \dfrac{3 \times 10^{-8}h }{\underbrace{3\times 10^{-8}h} + (1-h)\times 10^{-3}} \times 100$

$\Rightarrow 3 \times 10^{-8}h = 0.8[\underbrace{3\times 10^{-8}h} + (1-h)\times 10^{-3}]$

$\Rightarrow 30h \times 10^{-9} = 24h \times 10^{-9} + 0.8\times 10^{-3} -0.8h \times 10^{-3}$

$\Rightarrow 6h \times 10^{-9} + 0.8h\times 10^{-3} = 0.8 \times 10^{-3}$

$\Rightarrow h = \dfrac{0.8 \times 10^{-3}}{0.800006 \times 10^{-3}}$

$\Rightarrow h = 0.999925$

Hence hit ratio should be $99.99 \%$

In the selected ans in the equation

$3 \times 10^{-8} = 0.8[\underbrace{3\times 10^{-8}} + (1-h)\times 10^{-3}]$

why $h$ is not multiplied here as $h$ refers to hit rate. When there is miss then it will be $(1-h)$ miss rate with which secondary memory will be accessed but why hit rate is not considered when 2 level page table and corresponding frame is being accessed?

Best time would be 3* (10^-8)  if efficiency is 1.
but efficiency is 0.8.
3*(10^-8) / time taken  = 0.8
So time taken = (3*10^-8) / 0.8

Now
time taken = 2 page table access + h(1 memory access) + (1-h)(1 memory access+ 1 disk access)
3*(10^-8) / 0.8 =  2*10^-8  + h ( 10^-8 ) + (1 - h) (  10^-8 + 10^ -3)
Solving this will give value of h ≈ 99.99%

by Boss
edited by
0
+1

@Arjun Sir  @Bikram sir Please say, here in 2nd part it should be  (1 memory access+ 1 disk access)  or (1 disk access only)   It will not change the answer here though.  The changed value is after 4 decimal places.
We know PFS includes memory access time too. But here what to do? But here nothing like pfs is mentioned. We are bringing from disk. So we are bringing the frame to memory then accessing or directly accessing it?

0
Is access efficiency same as access time here?
0
@Ahwan

when do we do page table access? to check valid or invalid bit, right?

why u do hit and page table access separately?

If there is a hit in PTE then do we need 2 level page table access and then disk access separately?
+1
@Srestha
To access a frame, we need to find it's address from page table.
In 2 level paging, we have to go through 2 page tables to find the address of the frame where the actual frame we are looking for exists.

Now I did not get your question exactly.
+1

@Ahwan Nice answer but may you please tell how to solve this equation mathematically?

3*(10^-8) / 0.8 =  2*10^-8  + h ( 10^-8 ) + (1 - h) (  10^-8 + 10^ -3)

I'm stuck here as -

## 3*10^-8/0.8 = H(3*10^-8) + 10^-11 - 10^-11*H

0

@iarnav

why have u taken

3*10^-8/0.8 = H(2*10^-8 + 10^-8) + (1-H) (10^-8 + 10^-3)

0
Srestha , I'm way out of loop now. Will tell, when I see OS again!

For maximum efficiency hit ratio should be 1.

when H=1, then we need 3 memory access, two m/m access to access the two-level page tables, and one more m/m access to access the physical memory.

So, maximum efficiency when H=1, E.M.A.T = $3*10^-8$ or 30ns

Efficiency should be 80% from 100%.
When efficiency is 100% then E.M.A.T is 30ns
When efficiency is 80% then E.M.A.T will be 30ns/.80 = 37.5 ns (80% of 37.5ns is 30ns)

Now calculate the value of H:

37.5ns = H(30ns) + (1-H)($10^{-3}$)

(or)

37.5ns = H(30ns) + (1-H)($10^6$ns)

now all time units are same.

37.5 = H(30) + (1-H)($10^6$)

37.5 = 30H + $10^6$ -H$10^6$

H = $\frac{999962.5}{9999970}$ = 99.99%

by Boss
+1

@Arjun Sir

he is asking, when there is a miss in main memory, will not two level of primary memory access and again two level for secondary memory access and then data access?

i.e. total five level of memory access?

0

Please check my understanding and tell where am i going wrong.(refering the above diagram)

two level virtual memory, means already two level page table in MM, that requires 2 level memory access

We go to p1->p2 -> data so total 3m access in case of hit.(in case if page is present in main memory)i.e HIT

already we did two level page table in MM, that requires 2 level memory access and page was not found in them = 2m

so we access the page from secondary memory. = d

then update info in both the page tables = 2m

so total 5m+d in case of miss

0

@Satbir

then update info in both the page tables = 2m

This is the point I think, u r wrong about.

though page table is in memory, but it is not in physical or main memory. So, In physical memory , there is nothing but data.

Data pages(in diagram) are nothing but physical memory. So, after two level of page table access, if it is found data in main memory, other wise just go to secondary memory (which is same another level of memory, like the given picture)

0

though page table is in memory, but it is not in physical or main memory .

How can we say this ?

if it is not in main memory then where is it ?

There are basically only two types of memory -> main memory like RAM and secondary memory like disk.

Though other types like cache, register are also there but they are not related to this question.

if is true then also we need to do 3m+d right instead of doing 5m+d.

+1

from VA, OS will check in Outer level PT, if found then go to next inner level PT, then the final M.M( It's called hit).

H(3m)

If not found in outer level PT, then go to secondary memory(d), load that page into memory & restart again from outer PT. ( d + 3m)

It's not like that, after accessing two levels PT & then it founds that the desired page is not in memory. No, Os deosn't cheat like that.

If Outer level PT checking is passed then it's guranteed to be in M.M (that's how the paging level is built).If outer level PT checking is not passed then Os have to load it from seconadry memory to Main Memory.

0

@MRINMOY_HALDER

Here main problem is page table upgradation require every time or not??

@Satbir

Can u tell me one thing, if page table access is same as main memory access, then why some question gives page fault service time differently?

0
understood now. thankyou mrinmoy
0
because in case of page fault we access both main memory and secondary memory in order to swap the desired page to main memory from secondary memory and then updating the page table.

Also if main memory is full then we have to put back pages from main to secondary memory if it is a dirty page.

So the page fault is kind of a procedure in itself which is executed in various steps and involves accessing both main and secondary memory.
0

I think if u think about practically, then after page fault & loading a page from secondary to Main, there may be many times M.M can be accessed.

but In theoritically one thing we must say that it's compulsary to access M.M (n+1) times in n level paging after page falult service. This is always happen.( yes you can consider also about updating PT 1, then pT2......) but also you can ignore them by arguing that d >>>> any no. of m

for GATE, I think upto (n+1).m is enough to understand.

0

@Satbir

then we can do it with  main memory access time and secondary memory access time. But why do we need page fault service time differently?

@Arjun Sir

Can u tell me, is it always require, page table access time is same as main memory access time?

@MRINMOY_HALDER

If second level page table or last level page table can decide, that a page is in main memory or not, then why do we need to add main memory access time every time before secondary memory access time?

0

why do we need to add main memory access time every time before secondary memory access time?

can't get this

0

we do like this

EAT=hit* primary memory access time+(1-hit)(Main memory access time+secondary memory access time)

But According to u formula should be

EAT=hit* primary memory access time+(1-hit)(secondary memory access time)

which one should be correct?

OR,

can it say, Main Memory access is nothing but second leel page table access?

How do u define that MM access??

0
Do you agree that secondary memory access >> Main Memory access ???
0
may be.

but my question not answered still.

Can we tell something certainly about it?
0

EAT=hit* primary memory access time+(1-hit)(Main memory access time+secondary memory access time)

this is correct formula.

We are ignoring Main memory access time because $10^{-3} >>10^{-8}$

then we can do it with  main memory access time and secondary memory access time. But why do we need page fault service time differently?

because there are many steps involved in page fault service.

if page fault service time is not given then we calculate it using main memory and secondary memory access time.

0

EAT=hit* primary memory access time+(1-hit)(Main memory access time+secondary memory access time)

this is correct formula.

We are ignoring Main memory access time because 10−3>>10−8

@Satbir

because there are many steps involved in page fault service.

if page fault service time is not given then we calculate it using main memory and secondary memory access time.

if this is main scenario, then maximum question ignore it. But maximum GATE question includes it.

0

@Satbir

I got this

Typically, page tables are said to be stored in the kernel-owned physical memory. However page tables can get awfully big since each process have their own page tables (unless the OS uses inverted paging scheme). For even a 32 bit address space with a typical 4KB page size, we shall require a 20 Bit virtual page number and a 12 bit offset. A 20 bit VPN(Virtual Page Number) implies that there would be 2^20 translations. Even if each translation i.e the Page Table entry requires 4 Bytes of memory, it amounts to 4x(2^20)= 4MB of memory, all just of address translations, which is awful.

Hence modern OSes place such large page tables in virtual kernel memory which is the Hard Disk, and swaps them to the physical memory whenever required. Thus page table is virtualized the same way each page is virtualized.

Is that mean page  table in main memory or page table swapped in main memory?

0

This is done in modern days, but in what we study for GATE ...if size of page table is too big then we use demand paging and multilevel paging.

Is that mean page  table in main memory or page table swapped in main memory?

Page table is swapped to main memory

0

@Satbir

yes, and page table only used for mapping from virtual addresses to physical addresses. So, if it is inside physical memory, then will it be possible for page table?

0
Yes.

We take some space from physical memory to store page table and the remaining space will be mapped to virtual memory.

As mentioned on wikipedia, The efficiency of an entity (a device, component, or system) in electronics and electrical engineering is defined as useful power output divided by the total electrical power consumed (a fractional expression),

https://en.wikipedia.org/wiki/Electrical_efficiency

Let $h$ be the hit rate then

$\Rightarrow 80 = \dfrac{3 \times 10^{-8}h }{\underbrace{3\times 10^{-8}h} + (1-h)\times 10^{-3}} \times 100$

$\Rightarrow 3 \times 10^{-8}h = 0.8[\underbrace{3\times 10^{-8}h} + (1-h)\times 10^{-3}]$

$\Rightarrow 30h \times 10^{-9} = 24h \times 10^{-9} + 0.8\times 10^{-3} -0.8h \times 10^{-3}$

$\Rightarrow 6h \times 10^{-9} + 0.8h\times 10^{-3} = 0.8 \times 10^{-3}$

$\Rightarrow h = \dfrac{0.8 \times 10^{-3}}{0.800006 \times 10^{-3}}$

$\Rightarrow h = 0.999925$

Hence hit ratio should be $99.99 \%$

In the selected ans in the equation

$3 \times 10^{-8} = 0.8[\underbrace{3\times 10^{-8}} + (1-h)\times 10^{-3}]$

why $h$ is not multiplied here as $h$ refers to hit rate. When there is miss then it will be $(1-h)$ miss rate with which secondary memory will be accessed but why hit rate is not considered when 2 level page table and corresponding frame is being accessed?

by Active
+1 vote

2 level virtual memory meaning 2 level of page tables+1 main memory+1 secondary memory

now all necessary page tables reside in main memory itself...DO NOT ASSUME PAGE FAULTS WHEN FETCHING PAGES OF PAGE TABLES..

so what we do is after cpu generates virtual address we access 2 levels of page tables from main memory successfully then we get the frame number and finally access main memory the third time to see if that frame is already in there or not ..

if its there its cool else access secondary memory..

so....=> 2×10^(-8) + H×10^(-8) + (1-H)×(10^-3+10^-8)

=> 3×10^(-8) + (1-H)×10^(-3)

=> as it's in the selected answer of @Arjun sir.

now "80 % OF MAXIMUM VALUE"----- maximum value means what maximum access time including all probability (hit miss ratios and all included in computing).

now access efficiency meaning minimum time in ideal case..so 2 time main memory access for page tables and then 1 time agin main memory access for frame.

so, 3×10^(-8)=0.8×[ 3×10^(-8) + (1-H)×10^(-3)]

=> h=99.99%

by Junior

1
2