Obecny vzorec pro horni odhad poctu vypadku stranek
Napsal: 6. 6. 2007 01: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.
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.