Rezidentna velkost moze byt fixna alebo variabilna, podla toho, ci proces dostane fixny pocet stranok v pamati, alebo nie. Rezidentny rozsah moze byt globalny a lokalny, podla toho ci ovplyvnuje dalsie procesy, alebo nie.
K nahrade stranok dochadza, ak vsetky ramce v HP su obsadene. Do pamate potrebujeme nahrat dalsiu stranku. A toto zabezpecime pomocou algoritmu nahrady stranok. Vacsina z nich pracuje na principe lokality.
Optimalny algoritmus
Optimalny algoritmus sa snazi nahradit stranku, ktora uz pouzivana nebude. Ak taka stranka neexistuje, tak nahradime stranku, ktora bude pouzivana za najdlhsiu dobu od tohto okamziku.
- kazdej stranke sa priradi cislo indikujuce, kolko instrukcii sa musi vykonat, kym bude stranka zase volana
- nahradime stranku s najvyssim cislom
Tento algoritmus dosahuje najlepsich vysledkov, ale musime poznat buducnost. Sluzi pre porvnavanie s ostanymi algoritmami, az kym niekto nevynajde stroj casu.
Not Recently Used
Kazdej stranke su priradene bity read a modify, ktore menime podla potreby. R bit je nastaveny na 1, ak ku stranke pristupujeme a M nastavujeme na 1, ak stranku modifikujeme. Bity su ulozene v tabulke stranok a ich modifikaciu sa stara HW. Vynulovane su pri spusteni (not R, not M). Bit R je nulovany periodicky, napriklad prerusenim casovaca. Podla toho vieme, ktore stranky boli pouzite nedavno: (R,M)
- C0: 0,0 - stranka nebola dlho citana ani modifikovana
- C1: 0,1 - stranka nebola dlho citana, ale bolo na nu zapisovane
- C2: 1,0 - stranka bola nedavno citana, ale nebolo na jej miesto zapisovane
- C3: 1,1 - stranka bola prednedavnom citana aj modifikovana
NRU nahradzuje od najnizsej kategorie.
Least Recently Used
Dobra aproximacia optimalneho algoritmu. Myslienka na prinicipe casovej lokality, a kstranky boli casto pouzivane v poslednej dobe, tak s velou pravdepodobnostou budu pouzite znovu. Pri vypadku nahradime stranku, ktora nebola pouzita po najdlhsiu dobu.
First In First Out
OS si udrzuje zoznam vsetkych stranok, ktore su v hlavnej pamati vo fronte. Takze tie na zaciatku budu najstarsie a tie na konci budu najmladsie. Pri vypadku stranky nahradzujeme prvu stranku. Tento pristup neuvazuje, ako casto sa ku stranke pristupuje.
Second Chance Algorithm
Jedna sa o FIFO s novou feature. Pridame bit R, ktore pocitaju, ako casto sa ku stranke pristupuje a periodicky sa nuluje. Zoznam prechadzame od zaciatku pri vypadku stranky. A R je 0 - stranka je stara a nepouzivana. Preto ju mozme nahradit. Ak R je 1, tak tento bit vynulujeme a stranku presunieme na koniec zoznamu.
The Clock Algorithm
SCA v cyklickej fronte v smere hodinovych ruciciek. Pri vypadku stranky zacneme hladat od stranky, na ktoru ukazuje rucicka. Ak R = 0, tak stranku nahradime, ak R = 1, tak bit opat vynulujeme a hladame dalej.
Aging Algorithm
NFU nezabuda a preto je tento alg. doplneny o princip starnutia. Obsah citaca je posunuty doprava o jeden bit pred pricitanim bitu R a nahradeny je ten, ktory ma najnizsiu hodnotu citaca.
Working Set Algorithm
Tentokrat trochu iny algoritmus. pre kazdy proces nadefinujeme aktualny virtualny cas a pracovnu mnozinu. Aktualny virtualny cas je mnozstvo casu CPU, ktore proces skutocne vyuzil a pracovna mnozina je mnozstvo stranok, ku ktorym proces pristupoval behom poslednych t jednotiek svojho aktualneho virtualneho casu. Okrem R referenced bit a M modified bit je v tabulke stranok este TLU - last used time. R a M bit upravujeme tak, ako pri NRU a definujeme vek aktualny virtualny cas - cas posledneho pouzitia. Prechadzame tabulku stranok a testujeme R bit.
- ak R == 1, tak CVT = TLU a R = 0
- ak R == 0 && Age > t - nahradime stranku
- ak R == 0 && Age <= t - stranku s najvacsim Age si zapamatame (ak ich je viac, tak vyberame nahodne)
WS-Clock Algorithm
Toto je WS algoritmus v cyklickom poli.
