Obecny vzorec pro horni odhad poctu vypadku stranek

Přehledová přednáška obsahující základy teorie, koncepce a implementace operačních systémů.

Obecny vzorec pro horni odhad poctu vypadku stranek

Příspěvekod Angwin » 6. 6. 2007 00:08

Zavedeme funkci f(d, s), ktera bude vracet max. pocet stranek zabranych pomoci "d" bytu, pricemz velikost jedne stranky je "s" bytu.
Pr.:
f(1, 1024) = 1
f(2, 1024) = 2
f(3, 1024) = 2
f(1025, 1024) = 2
f(1026, 1024) = 3
atd.
Toto je nejlepsi si nakreslit pomoci prihradek.

Dale definujeme funkci g_m(d, s) takto:
g_1(d, s) = f(d, s)
g_2(d, s) = f(f(d, s), s)
g_3(d, s) = f(f(f(d, s), s), s)
atd.

A ted k vypoctu v uloze. Znaceni:
Velikost dat: d
Velikost stranky: s
Velikost instrukce: i
Pocet zaznamu v tabulce: #z
Pocet urovni: #u

Vypocet rozdelime na dve casti
1. pocet vypadku na nacteni instrukce
2. pocet vypadku na presun dat

ad 1.
A = f(i, s) + g_1(f(i, s), #z) + g_2(f(i, s), #z) + ... + g_m(f(i, s), #z)
kde m = #u - 1

ad 2.
B = 2 * [ f(d, s) + g_1(f(d, s), #z) + g_2(f(d, s), #z) + ... + g_m(f(d, s), #z) ]
kde m = #u - 1 (stejne jako v 1. akorat misto "i" je "d" a bere se vsechno dvakrat)

Vysledek: A+B

Po vhodne graficke uprave pri rozepisovani vzorcu to jde docela rychle (linearne k poctu urovni)

-----------------------------------------------------------------------------------------
Priklad:
Velikost dat: d = 8kB
Velikost stranky: s = 4kB
Velikost instrukce: i = 2B
Pocet zaznamu v tabulce: #z = 1024
Pocet urovni: #u = 3

Instrukce:
A = f(2B, 4kB) + f(f(2B, 4kB), 1024) + f(f(f(2B, 4kB), 1024), 1024) =
= 2 + f(2, 1024) + f(f(2, 1024), 1024) =
= 2 + 2 + 2
= 6
Data:
A = 2 * [f(8kB, 4kB) + f(f(8kB, 4kB), 1024) + f(f(f(8kB, 4kB), 1024), 1024) ] =
= 2 * [3 + f(3, 1024) + f(f(3, 1024), 1024) ] =
= 2 * [3 + 2 + 2 ]
= 14

Vysledek: A + B = 20

Pozn.: Vsechny kB jsou behem postupu prepocitavany na B. Uz jsem to tak podrobne nerozepisoval.
Angwin
 

Sqela prace

Příspěvekod Fairfax » 21. 6. 2007 21:43

Jeden z nejlepsich "navodu" co jsem kdy cetl. Pro ucely zkousky naprosto idealni. Behem ctvrthodiny to pochopi i cvicenej mroz.
Uživatelský avatar
Fairfax
Matfyz(ák|ačka) level I
 
Příspěvky: 28
Registrován: 17. 1. 2006 19:05
Typ studia: Matematika Mgr.
Login do SIS: vodrj5am

Re: Obecny vzorec pro horni odhad poctu vypadku stranek

Příspěvekod athlo » 29. 5. 2008 14:48

Jenom doplnim, ze

f(d, s) = ( (s-1) + d ) div s

ale snad to kazdemu doslo ;)
athlo
 

Re: Obecny vzorec pro horni odhad poctu vypadku stranek

Příspěvekod Wolda » 30. 5. 2008 20:03

A ja dodam, ze ten vzorec jde take prepsat nasledujicim zpusobem (minimalne pro me je v tehle forme prijemejsi):

definujme si funkce g_i nasledovne (f necht je funkce viz. vyse):
g_0(d, s) = d
g_i(d, s) = f(g_{i-1}(d,s), s)

potom
A = suma od k=0 do u-1: g_k(f(i,s), #z)
B = 2*suma od k=0 do u-1 g_k(f(d,s), #z)

Z toho je pomerne slusne videt, jak to napocitat velmi rychle, tak treba to tu nekomu pomuze ;-)
--
Wolda
Wolda
Matfyz(ák|ačka) level I
 
Příspěvky: 27
Registrován: 25. 10. 2006 21:27
Typ studia: Informatika Ph.D.
Login do SIS: volej6am

Re: Obecny vzorec pro horni odhad poctu vypadku stranek

Příspěvekod curly » 9. 2. 2010 18:56

athlo píše:Jenom doplnim, ze

f(d, s) = ( (s-1) + d ) div s

ale snad to kazdemu doslo ;)


tak moment...
napr.
f(2,1024) = ((1024-1) + 2) div 1024 = 1 ale ma to byt 2...

podle me je to spis:
f(d, s) = ( (d-2) div s ) + 2
curly
 


Zpět na SWI097 Základy operačních systémů

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník