so:alg_zast_str

Pytanie: “Algorytmy zastępowania stron”

# Zastępowanie stron

Wprowadzenie:

- Strony sprowadzane są z pamięci logicznej(wirtualnej) do pamięci fizycznej(operacyjnej) wtedy gdy jest ona potrzebna(jakiś proces zgłasza zapotrzebowanie na tę stronę).

- Przerwanie braku strony następuje wtedy kiedy proces odwołuje się do strony której nie ma w pamięci operacyjnej. W trakcie obsługi braku strony jedna z instrukcji które należy wykonać to:

Znalezienie wolnej ramki pamięci operacyjnej

W przypadku gdy nie możliwe jest wykonanie tej instrukcji tzn wystąpił brak strony a nie ma już wolnych ramek trzeba wybrać jedną z ramek i zastąpić obecną w niej stronę poprzez żądaną stronę.

Jedną z czynności wykonywanych podczas zastępowania strony jest

Znalezienie strony ofiary, która ma być usunięta z pamięci.

Tą czynnością zajmują się właśnie algorytmy zastępowania stron. Najważniejszym kryterium ich oceny jest częstość braków stron. Im jest ona mniejsza, tym algorytm lepszy.

## First-In-First-Out (FIFO)

Przy tym algorytmie ofiarą staje się strona, która najdłużej przebywa w pamięci. Algorytm FIFO w ogóle nie bierze pod uwagę właściwości obsługiwanych procesów i w zasadzie zastępuje strony na chybił-trafił. Zaletą jest prostota jego implementacji i niewielkie narzuty związane z jego obsługą.

Wady:

Czasami zdarza się że zwiększenie pamięci spowolnia działanie systemu(im więcej ramek tym więcej braków stron). Ten nieoczekiwany rezultat nosi nazwę anomalii Beladiego.

## Algorytm optymalny

Przy tym algorytmie ofiarą staje się strona, która będzie nieużywana przez najdłuższy okres. Jest to algorytm teoretyczny, który służy do oceny jakości innych algorytmów. Nie da się go zaprogramować ponieważ nie da się przewidzieć przyszłych odwołań do pamięci .

## Least Recently Used (LRU)

Przy tym algorytmie ofiarą staje się strona, która nie była używana przez najdłuższy okres. Daje mniej braków stron niż FIFO (bardziej efektywny)

Implementacja LRU Implementacja trudna, gdyż każde odwołanie do pamięci musi pozostawiać jakiś ślad do późniejszego wyznaczenia ofiar. Konieczne są specjalne udogodnienia sprzętowe, gdyż realizacja programowa byłaby zbyt wolna.

LRU można zaimplementować za pomocą liczników.

Każda strona ma specjalne pole licznika. Gdy jakiś proces odwołuje się do strony, do tego licznika kopiuje się stan zegara systemowego. Gdy trzeba wybrać ofiarę, szuka się strony z najmniejszą wartością tego licznika. Ustawianie licznika strony musi odbywać się sprzętowo.

Inna możliwość to wykorzystanie stosu.

Na stosie trzymamy numery stron, do których były odwołania. Odwołanie do strony powoduje przesunięcie jej numeru na wierzchołek tego stosu. Gdy stos ma postać listy dwukierunkowej, przeniesienie na wierzchołek oznacza konieczność zmiany 6 wskaźników. To powoduje, że taka implementacja może być efektywna przy zastosowaniu oprogramowania systemowego albo mikroprogramów.

## Przybliżenia LRU

Implementacja LRU wymaga bardzo wymyślnych udogodnień sprzętowych, które istnieją w niewielu systemach. Dlatego zwykle przybliża się algorytm LRU za pomocą jakiegoś innego algorytmu. Zwykle również do tego są potrzebne specjalne udogodnienia sprzętowe, takie jak bit odwołania. Wstępnie ma on wartość 0, ale przy odwołaniu do strony jest on sprzętowo ustawiany na 1. Algorytmy przybliżające LRU jako ofiarę wybierają strony, dla których bit odwołania jest równy 0. Jeden z takich algorytmów opisano poniżej.

## Algorytm drugiej szansy

W wypadku algorytmu drugiej szansy utrzymuje się kolejkę ładowanych stron tak jak w wypadku algorytmu FIFO i jako ofiarę wybiera się pierwszą stronę z tej kolejki. Jest tylko jeden wyjątek: jeśli ta strona ma bit odwołania równy 1, to dostaje ona “drugą szansę”, tzn.

1. Jej bit odwołania jest ustawiany na 0.

2. Jest ona pozostawiana w pamięci.

3. Jest ona przenoszona na koniec kolejki stron.

4. Kandydatką na ofiarę jest następna strona w kolejce (ta strona również może dostać drugą szansę).

## Algorytmy zliczające

Algorytmy zliczające korzystają ze związanego z każdą stroną licznika odwołań. Oczywiście taki licznik musi być zrealizowany sprzętowo, ponieważ każde odwołanie danej strony powoduje zwiększenie jej licznika o jeden. Można wskazać dwa takie algorytmy oparte na przeciwstawnych założeniach. Oba algorytmy nie są dość popularne, ponieważ ich implementacja jest dość kłopotliwa, a obu daleko do algorytmu optymalnego.

### Least Frequently Used (LFU)

Przy tym algorytmie ofiarą staje się strona, do której było najmniej odwołań. Zakłada się tu, że strony o dużych licznikach odwołań są aktywnie użytkowane i nie należy ich usuwać z pamięci.

### Most Frequently Used (MFU)

Przy tym algorytmie ofiarą staje się strona, do której było najwięcej odwołań. Zakłada się tu, że strony o małych licznikach odwołań zostały właśnie załadowane i wkrótce będą jeszcze używane