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.
Obecny vzorec pro horni odhad poctu vypadku stranek
- 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
- Kontaktovat uživatele:
Sqela prace
Jeden z nejlepsich "navodu" co jsem kdy cetl. Pro ucely zkousky naprosto idealni. Behem ctvrthodiny to pochopi i cvicenej mroz.
Re: Obecny vzorec pro horni odhad poctu vypadku stranek
Jenom doplnim, ze
f(d, s) = ( (s-1) + d ) div s
ale snad to kazdemu doslo
f(d, s) = ( (s-1) + d ) div s
ale snad to kazdemu doslo
-
- Matfyz(ák|ačka) level I
- Příspěvky: 27
- Registrován: 25. 10. 2006 22:27
- Typ studia: Informatika Ph.D.
- Login do SIS: volej6am
- Kontaktovat uživatele:
Re: Obecny vzorec pro horni odhad poctu vypadku stranek
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
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
Re: Obecny vzorec pro horni odhad poctu vypadku stranek
tak moment...athlo píše:Jenom doplnim, ze
f(d, s) = ( (s-1) + d ) div s
ale snad to kazdemu doslo
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