Straničenje na zahtjev

Kada je međuspremnik pun, a stranica koja se zahtjeva nije u međuspremniku/spremniku, potrebno je odrediti koju ćemo stranicu izbaciti, odnosno nadomjestiti s novom stranicom. (U procesu straničenja potrebno je primjeniti jednu od metoda pomoću koje će se prije dohvaćanja potrebne stranice iz sekundarnog spremnika u primarni odlučiti koja će se stranica izbaciti iz primarnog spremnika.) Za to postoji mnoštvo metoda (teorijskih i praktičnih) od kojih su najpoznatije slijedeće strategije izbacivanja stranica: FIFO, LRU, LFU i OPT.

FIFO (First In First Out) strategija - iz radnog se spremnika (primarnog spremnika) izbacuje stranica koja je najdulje u radnom spremniku.

LRU (Least Recently Used) strategija - izbacuje se stranica koja se najdulje u prošlosti nije upotrebljavala.

LFU (Least Frequently Used) strategija - izbacuje se ona stranica od onih u radnom spremniku koja se najrjeđe koristila.

OPT (Optimal) strategija - izbacuje se ona stranica koja će se najkasnije u budućnosti koristiti.

Inačica LRU algoritma koja se koristi u više inačica operacijskog sustava UNIX naziva se satnim algoritmom (Clock algorithm). Algoritam djeluje tako da se sve stranice u radnom spremniku slažu u kružnu listu po redu prispijeća. Prilikom traženja stranice za izbacivanje posebnom se kazaljkom pretražuje lista, počevši od stranice iza zadnja učitane u primarni spremnik. Ukoliko stranica ima oznaku (zastavicu) A=1 (stranica se koristila u nekom prethodnom "bliskom" trenutku) ta se oznaka postavlja na 0 te se pomiče na slijedeću stranicu. Ako stranica ima oznaku A=0 tada se dotična stranica izbacuje iz radnog spremnika i na isto mjesto se učitava nova stranica. Prilikom učitavanja nove stranice, kazaljka se ne pomiče dalje, već se samo zastavica A postavlja u jedinicu (u programu je to potrebno izravno napraviti, dok u stvarnim MMU sklopovima se to automatski postavlja samim korištenjem te stranice - bit pristupa).

ZADATAK

Studenti čiji matični broj završava s 0 ili 1 trebaju ostvariti simulaciju FIFO strategije izbacivanja stranica.
Studenti čiji matični broj završava s 2 ili 3 trebaju ostvariti simulaciju LRUstrategije izbacivanja stranica.
Studenti čiji matični broj završava s 4 ili 5 trebaju ostvariti simulaciju LFU strategije izbacivanja stranica.
Studenti čiji matični broj završava s 6 ili 7 trebaju ostvariti simulaciju OPT strategije izbacivanja stranica.
Studenti čiji matični broj završava s 8 ili 9 trebaju ostvariti simulaciju satnog mehanizma.
 

UPUTA

Za svaku od strategija potrebna je odgovarajuća prateća podatkovna struktura. Pretpostaviti da će na raspolaganju biti samo 4-10 okvira za stranice u radnom spremniku (broj stranica je parametar i zadaje se u komandnoj liniji) te da će zahtjeva biti između 10 i 100 (također parametar komandne linije). Program treba na početku generirati zahtjeve za stranicama (redni brojevi stranica se kreću od 1 do 8) te koristeći zadanu strategiju ispisivati povijest radnog spremnika. Pretpostaviti da je u početku radni spremnik prazan.

Primjer ispisa programa za FIFO metodu:

$ ./str_fifo 4 10

Zahtjevi: 5,2,3,8,2,3,4,1,2,4

#N  1   2   3   4

------------------

5  [5]  -   -   -

2   5  [2]  -   -

3   5   2  [3]  -

8   5   2   3  [8]

2   5  (2)  3   8   #pogodak

3   5   2  (3)  8   #pogodak

4  [4]  2   3   8

1   4  [1]  3   8

2   4   1  [2]  8

4  (4)  1   2   8

 

Kod FIFO strategije za svaki od okvira potrebno je pamtiti: stranicu koja se u njemu nalazi te nekakvu oznaku vremena.

Npr. za ispisani primjer stanja varijabli po okvirima mogla bi biti:

 

#N  1   2   3   4     (n,t) (n,t) (n,t) (n,t)

---------------------------------------------

5  [5]  -   -   -     (5,1) (0,0) (0,0) (0,0)

2   5  [2]  -   -     (5,1) (2,2) (0,0) (0,0)

3   5   2  [3]  -     (5,1) (2,2) (3,3) (0,0)

8   5   2   3  [8]    (5,1) (2,2) (3,3) (8,4)

2   5  (2)  3   8     (5,1) (2,2) (3,3) (8,4)

3   5   2  (3)  8     (5,1) (2,2) (3,3) (8,4)

4  [4]  2   3   8     (4,5) (2,2) (3,3) (8,4)

1   4  [1]  3   8     (4,5) (1,6) (3,3) (8,4)

2   4   1  [2]  8     (4,5) (1,6) (2,7) (8,4)

4  (4)  1   2   8     (4,5) (1,6) (2,7) (8,4)

 

Stranica sa najmanjom vremenskom oznakom se izbacuje.

 

Kod LRU strategije može se gornja metoda modificirati tako da se i za pogodke upisuje nova vremenska oznaka u "pogođeni" okvir te primijeni isti princip (stranica sa najmanjom vremenskom oznakom se izbacuje).

 

Kod LFU strategije se umjesto vremenske oznake za svaki okvir koristi poseban brojač. Prvi se puta (kada se stranica učita u okvir) brojač postavlja na 1, a svaki se slijedeći put (pogodak) vrijednost tog brojača povećava za jedan. Izbacuje se ona stranica sa najmanjom vrijednošću brojača. Ako više okvira ima istu vrijednost odabir je proizvoljan (odabrati okvir s najmanjim brojem).

 

Kod optimalne strategije lista zahtjeva pretražuje se prema naprijed te se može za svaki okvir izračunati kada će se (za koliko iteracija) pojaviti zahtjev za stranicom (u okviru) u budućnosti. Odabire se okvir s najvećim brojem. Ukoliko se stranica ne pojavljuje u budućnosti vrijednost brojača postaviti na maksimalnu (definirati neku vrijednost, npr. 100). Ako više okvira ima istu vrijednost odabir je proizvoljan (odabrati okvir s najmanjim brojem).

 

Kod strategije satnog mehanizma predvidjeti polje za zastavice (za svaki okvir) te jednu varijablu za kazaljku. U početku sve zastavice imaju vrijednost nula te kazaljka pokazuje na prvi okvir.