Metoda LRU a výpady

[Ellrohir]

omlouvám se, že možná neumím svůj problém přesně pojmenovat, ale na http://s0cketka.php5.cz/skola/zzos.php koukám na řešenou otázku

Kód: Vybrat vše

11. otazka:
mame 4 ramce (na zacatku prazdne), sekvenci pristupu nize zadanou, pouzivame metodu LRU. ke kolika vypadkum dojde?
sekvence: 1 2 3 4 5 6 2 4 2 3 1
odpoved:
9

LRU ... pro ucely tohoto prikladu (pro vypocet na papire):
kazda stranka ma citac, do ktereho se pri kazdem pouziti zapise cas. obeti vyhazovu se potom stane ta stranka, ktera je 'nejstarsi' (nejdele nebyla pouzita). tedy budeme si zapisovat stranky do rady, ty starsi vlevo, mladsi vpravo. reseni po krocich:
1) 1 2 3 4 (4 vypadky)
2) 2 3 4 5 (1 vypadek)
3) 3 4 5 6 (1 vypadek)
4) 4 5 6 2 (1 vypadek)
5) 5 6 2 4 (bez vypadku)
6) 5 6 4 2 (bez vypadku)
7) 6 4 2 3 (1 vypadek)
8) 4 2 3 1 (1 vypadek)
celkem tedy: 9 vypadku

a vůbec nechápu, kde se berou počty těch výpadků ? podle čeho se to určuje ?

[Návštěvník]

tie vypadky su pocty stranok ktore tam nenajdes. na zaciatku su 4 preto, lebo dotycny spojil 4 kroky. tie vyzeraju asi tak, ze pristupis na stranku, ktora neni namapovana na ramec, pretoze ten je volny = vypadok.

dalsie kroky su uz len o tom ci tam tu stranku vo svojich 4 ramcoch mas alebo nemas. ak nemas mas page fault a najstarsiu stranku vymenis za pozadovanu.

[mhb]

Kód: Vybrat vše

sekvence: 1 2 3 4 5 6 2 4 2 3 1

Metoda LRU - Least Recently Used - vyhodíme tu, která jsme použili v co největší minulosti.
Výpadek nastává, když to číslo, které požaduješ, v cachi není. To znamená na začátku "1 2 3 4" máš 4 výpadky, protože cache byla prázdná. Dále se vyhazuje podle LRU pravidla. V tom příkladu Ti radí, aby sis to simuloval tak, že si zapisuješ čísla, která máš v cachi, číslo nejvíce napravo je to poslední použité, číslo nejvíce nalevo je to nejpozději použité, tedy pokud dojde k výpadku (v těch 4 číslech co máš napsané/uložené v cachi není to, které požadujeme), tak si zleva jedno smaž, napravo si napiš to nové číslo a stávající čísla se o jedno políčkou "šoupnou" doleva - jejich doba použití se změní.

Snad je to trochu z toho blábolu vidět. Není to nic těžkého. V podstatě si stačí pamatovat co znamená LRU a vykoume se to samo )

PS: Někdo mne předběhl, ale což, stejně to postnu.

[DH]

zdravim, no me to prijde, ze je to trochu jinak... podle http://en.wikipedia.org/wiki/Page_repla ... ond-Chance je LRU o dost slozitejsi, a to co in bere jako LRU mi spis prijde jen jako takovy zdokonaleny FIFO ktery bere jako "in" i precteni te stranky... kdezto podle wikipedie se to chova tak (jestli jsem to spravne pochopil), ze si pamatuje kolikrat byla ktera stranka pouzita za nejakej (kratkej) cas, a podle toho to vyhodi tu, ktera byla nejmin...
Ale ja uz se v tom taky nevyznam takze to co jsem napsal berte jen jako inspiraci k prostudovani toho a ne jako pravdu

[DH]

* to co on bere

[mhb]

Je třeba rozlišovat algoritmus Least Recently Used a Not Frequently Used. První z nich se skutečně neohlíží na počet přístupů (takže se může stát, že pokud 1000krát přistoupíme na jednu hodnotu a pak 1x na všechny ostatní, nakonec ta tisícovka bude vyhozena), zatímco druhý se na něj ohlíží (s nebezpečím že položky nestárnou, což řeší tzv. "aging").

Na wiki (na té správné stránce) se taky píše, že jedna (výkonově dost nanic) implentace LRU je právě použítí spojáku (linked listu) a přehazování prvků, což je přesně ten způsob použítý ve vzorovém řešení.

Bulej navíc píše že NFU je SW řešení LRU, čímž to ještě více zamotává

EDIT: Kecám blbiny, díval jsem se na špatnou stránku na wikipedii.