Polityki Zamiany Stron: FIFO, LRU, Clock i Optymalna

Dlaczego pamięć potrzebuje polityki wywosu

Pamięć wirtualna pozwala procesowi adresować więcej pamięci niż fizycznie istnieje, przechowując tylko najczęściej używane strony (working set) w RAM-ie, a resztę na dysku. Gdy proces odwołuje się do strony, która nie jest zamieszkana, występuje błąd stronicowania, i jeśli wszystkie ramki są pełne, system operacyjny musi wywlec jedną, aby zrobić miejsce. Którą stronę wywlec to kluczowe pytanie – wywlec niewłaściwą stronę, a program natychmiast zawiedzie, próbując ją przywrócić, tracąc dostęp dyskowy, który może być pięć razy wolniejszy niż dostęp pamięciowy.

FIFO i anomalia Bélády

Najprostsza polityka, FIFO, wydala dowolną stronę, która była w pamięci najdłużej, niezależnie od tego, czy właśnie została użyta kilka chwil temu. Jest to tanie – wystarczy kolejka – ale całkowicie ignoruje lokalność odniesienia i posiada słynącą patologię: anomalię Bélády, odkrytą przez Lászlóa Béládya w 1969 roku, gdzie dodawanie większej liczby ram fizycznych może zwiększyć liczbę błędów stron dla tej samej sekwencji odniesień pod FIFO. Algorytmy typu stos, takie jak optymalny (LRU) i inne, które są dowodowo nie mogą wykazywać tej anomalii – zbiór stron zamieszkujących k ram jest zawsze podzbiorem zbioru zamieszkującego k+1 ram – ale FIFO nie jest algorytmem typu stos, więc więcej pamięci może, paradoksalnie, sprawić, że będzie wolniejszy.

reference string: 1 2 3 4 1 2 5 1 2 3 4 5
FIFO, 3 frames  -> 9 faults
FIFO, 4 frames  -> 10 faults   (Bélády's anomaly: more RAM, more faults)

LRU: praktyczny standard

Najmniej Używana Ostatnio (Least Recently Used - LRU) usuwa stronę, która nie była używana najdłużej czasu, przy założeniu, że ostatnie użycie przewiduje bliskie przyszłe użycie – zasadę lokalności, którą wykazują prawie wszystkie rzeczywiste obciążenia robocze. LRN jest algorytmem opartym na stosie, więc nigdy nie doświadcza anomali Bélády i empirycznie zbliża się do optymalnej polityki dla typowych programów. Jego problemem jest koszt: dokładne LRU wymaga znaczników czasu lub uporządkowanej listy aktualizowanej przy każdej referencji dostępu do pamięci, co jest znacznie zbyt drogie do zrobienia w sprzęcie lub oprogramowaniu ze względu na pełną prędkość dostępu do pamięci.

Algorytm zegara dobrze aproksymuje LRU tanio

Prawie każda produkcyjna jądro zamiast tego wykorzystuje algorytm zegara (zwany również drugą szansą): każdy ramka pamięci zawiera jeden sprzętowo utrzymywany bit referencyjny, ustawiony na 1 za każdym razem, gdy strona jest dostępna. Ręka przesuwa się obwodem po ramkach; w przypadku błędu sprawdza ramkę pod ręką – jeśli bit referencyjny wynosi 1, bit jest wyzerowany i stronie udziela się drugiej szansy, przechodząc do następnej ramki; jeśli bit jest już zerowy, strona jest usuwana. Kosztuje to jeden bit na ramkę i amortyzowany czas O(1) na błąd, a jego zachowanie dobrze aproksymuje LRU, tak że różnica w współczynniku błędów zwykle jest niewielka.

// Clock / second-chance
while (true) {
  const p = frames[hand];
  if (p.referenceBit === 0) { evict(p); frames[hand] = newPage; break; }
  p.referenceBit = 0;              // give it a second chance
  hand = (hand + 1) % frames.length;
}

Optymalny algorytm Belady’ego (MIN) jako nieosiągalny punkt odniesienia

Algorytm optymalnego Belady’ego (MIN) usuwa dowolną stronę zamieszkaną, która zostanie najdalej odwołana w przyszłości – lub w ogóle. Dowodowo minimalizuje liczbę błędów stron dla jakiegokolwiek ciągu odwołań, co czyni go miarą, z której mierzone są wszystkie rzeczywiste polityki. Nie jest to implementacja online, ponieważ wymaga wiedzy o przyszłych odwołaniach, ale można łatwo obliczyć go offline dla znanego przebiegu, a jego liczba błędów wynosi liczbę, do której starają się zbliżyć wszystkie praktyczne algorytmy.

Przepływ (Thrashing)

Gdy suma zestawień procesów w pamięci roboczej przekracza dostępną pamięć fizyczną, system przechodzi w stan przepłytwania: strony są usuwane i natychmiast ponownie trafiają do pamięci (refaultują), co powoduje upadek wykorzystania CPU, ponieważ procesy spędzają prawie całą 시간을 czekając na dysk. Dodanie kolejnych procesów pogarsza sytuację dramatycznie, a nie poprawia jej. Rozwiązaniem nie jest bardziej inteligentna polityka wymiany stron, lecz kontrola przyjmowania procesów – model zestawienia roboczego lub monitorowanie częstotliwości błędów w dostępie do pamięci, które suspenduje procesy, aż dostępna będzie wystarczająca ilość pamięci dla pozostałego zestawienia, aby nie powodowało ciągłych błędów w dostębie.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Page Replacement i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.