Problemy implementacji algorytmów wymiany

Zagadnienia implementacyjne


Jak już wcześniej wspomniano, kluczowa dla efektywności funkcjonowania systemu z pamięcią wirtualną jest minimalizacja liczby błędów strony. W celu ograniczenia kosztów czasowych dostępu do pamięci stosowane są odpowiednie algorytmy wymiany. Na przykładzie algorytmów FIFO i LRU wyjaśnione zostaną natomiast zagadnienia związane z kosztem działania samego algorytmu.

  • Implementacja algorytmu FIFO
  • Implementacja algorytmu LRU
    • Algorytmy przybliżające metodę LRU

      • algorytm dodatkowych bitów odwołań
      • algorytm drugiej szansy (FINUFO)
      • ulepszony algorytm drugiej szansy

Implementacja algorytmu FIFO


Implementacja algorytmu FIFO bazuje na kolejce FIFO, którą można łatwo zaimplementować za pomocą listy jednokierunkowej.

Warto zwrócić uwagę, że aktualizacja listy następuje w ramach obsługi błędu strony, gdyż stronę umieszczamy na liście po sprowadzeniu. W przypadku usuwania na żądanie, również usuwanie strony z listy wykonywane jest przy obsłudze błędu strony.

  • Utrzymywanie listy numerów stron w kolejności ich sprowadzania do pamięci
  • Umieszczanie numeru sprowadzanej strony na końcu listy
  • Usuwanie z pamięci (i z listy) strony, której numer znajduje się na początku listy

Implementacja algorytmu LRU


Rozwiązanie z licznikiem wymaga zwiększenia licznika odniesień do pamięci i stosownej aktualizacji opisu strony (lub ramki). Jest to operacja stosunkowo szybka w porównaniu z wyszukiwaniem strony do usunięcia w przypadku konieczności zwolnienia ramki. Pewnym problemem jest ryzyko przepełnienia licznika.

W przypadku rozwiązania opartego na stosie jest odwrotnie. Aktualizacja stosu zbudowanego na liście wymaga zmiany zaledwie kilku wskaźników, ale wyszukanie strony w głębi stosu jest bardziej czasochłonne. Wybór strony do usunięcia w przypadku konieczności zwolnienia ramki jest za to natychmiastowy.

Porównując oba podejścia należałoby zauważyć, że błąd strony jest zjawiskiem nieporównywalnie rzadszym niż odniesienie do strony. W przeciwnym przypadku stosowanie pamięci wirtualnej nie miałoby żadnego sensu. Preferowane byłoby zatem rozwiązanie licznikowe. Jednak implementacja tego rozwiązania na poziomie systemu operacyjnego wymaga przekazania sterowania do programu jądra przy każdym odniesieniu do strony. Nawet jeśli aktualizacja licznika i tablicy stron wymaga wykonania zaledwie kilku rozkazów, to i tak powoduje to kilkunastokrotne spowolnienie każdego dostępu do pamięci. Programowe rozwiązanie oparte na stosie byłoby jeszcze bardziej czasochłonne.

Mogłoby się zatem okazać, że koszt algorytmu LRU pochłania zysk, wynikający z trafności decyzji co do stron wymienianych. Konieczne jest zatem odpowiednie wsparcie na poziomie architektury komputera.

  • Licznik — przy każdym odniesieniu do pamięci zwiększana jest wartość pewnego licznika i wpisywana do odpowiedniej pozycji opisującej stronę w tablicy stron (lub w innej specjalnej strukturze systemu operacyjnego). Z pamięci usuwana jest wówczas strona z najmniejszą wartością tego licznika, co wymaga przejrzenia całej tablicy stron.
  • Stos — numery stron, do których następuje odniesienie, odkładane są na szczycie stosu. Przed odłożeniem na szczycie numer strony musi być wydobyty ze środka stosu, czyli z miejsca, gdzie był ostatnio odłożony. W tej implementacji z pamięci usuwana jest strona, która jest na dnie stosu.

Algorytmy przybliżające metodę LRU


Implementacja na poziomie architektury komputera nie może być zbyt kosztowana, gdyż nie wiadomo, jaki algorytm wymiany będzie implementowany w systemie operacyjnym i czy w ogóle realizowana będzie pamięć wirtualna z wymianą stron. Jeśli zatem dostarczane jest wsparcie dla implementacji wymiany, powinno ono być na tyle uniwersalne, żeby można była je zaadaptować do różnych algorytmów.

W ramach wsparcia na poziomie architektury jednostka zarządzania pamięcią ustawia odpowiednie bity na właściwej pozycji w tablicy stron w przypadku wykrycia odniesienia do strony:

  • bit odniesienia (ang. reference bit) — ustawiany dla danej strony zawsze, gdy następuje zapis lub odczyt jakieś komórki na tej stronie,
  • bit modyfikacji (ang. modify bit) — ustawiany dla danej strony zawsze, gdy następuje zapis na tej stronie. (Wspomniany przy omawianiu problemu wymiany).

W dalszej części omówione zostaną 3 algorytmy, w których wykorzystywane jest omówione wspomaganie sprzętowe:

  • algorytm dodatkowych bitów odniesienia (wykorzystanie bitu odniesienia),
  • algorytm drugiej szansy (wykorzystanie bitu odniesienia),
  • ulepszony algorytm drugiej szansy (wykorzystanie bitu odniesienia i bitu modyfikacji).

Poza tym, bity te wykorzystywane są w niektórych algorytmach wymiany ze sprowadzaniem na żądanie.

  • Niezbędne wspomaganie sprzętowe:
    • bit odniesienia (ang. reference bit) — ustawiany, gdy następuje odniesienie do strony,
    • bit modyfikacji (ang. modify bit) — ustawiany, gdy następuje zapis na stronie.
  • Algorytmy korzystające ze wspomagania sprzętowego:
    • algorytm dodatkowych bitów odniesienia — wykorzystuje bit odniesienia,
    • algorytm drugiej szansy — wykorzystuje bit odniesienia,
    • ulepszony algorytm drugiej szansy — wykorzystuje bit odniesienia i bit modyfikacji.

Algorytm dodatkowych bitów odniesienia


W algorytmie dodatkowych bitów odniesienia okresowo sprawdzane są bity odniesienia każdej ze stron i kopiowane do dodatkowej struktury, zwanej tablicą dodatkowych bitów odniesienia. Bity kopiowane są na najbardziej znaczącą pozycje, ale przed skopiowaniem następuje logiczne przesunięcie bitów w prawo na każdej pozycji. Bit najmniej znaczący jest tracony. Tablica przechowuje zatem informacje o wystąpieniu błędu strony w kilku ostatnich okresach kontrolnych. Ciąg samych zer oznacza, że nie było żadnego odniesienia w ostatnim czasie. Ogólnie im mniejsza wartość tym bardziej odległe w czasie jest ostatnie odniesienie lub mniejsza jest liczba odniesień. Horyzont czasowy tej informacji zależy od liczby bitów na każdej pozycji oraz długości okresu kontrolnego. Oczywiście im dłuższy okres kontrolny, tym mniej precyzyjna jest informacja, gdyż reprezentowana jest tylko przez 1 bit.

W przypadku konieczności wymiany poszukiwana jest strona, dla której wartość w tablicy jest najmniejsza, a ramka tej strona jest użyta do wymiany. Precyzja działania algorytmu wymaga uwzględnienia również bieżącej wartości bitu odniesienia na najbardziej znaczącej pozycji wektora. Można przyjąć, że tuż przed wybraniem strony ofiary następuje przesunięcie bitów w tablicy i skopiowanie bitów odniesienia.

slajd 26

Algorytm drugiej szansy


Algorytm drugiej szansy (FINUFO, ang. First In Not Used First Out) jest jednym z tzw. algorytmów zegarowych (wskazówkowych), w których numery stron (lub ramek, w tym przypadku ramek danego procesu) tworzą listę cykliczną (tarczę zegara), a wskazówka wskazuje kandydatkę do usunięcia z pamięci w przypadku błędu strony. Jeśli jednak strona, wskazywana do usunięcia była ostatnio adresowana (ma ustawiony bit odniesienia), otrzymuje drugą szansę. Bit odniesienia dla tej strony jest kasowany, a wskazówka przesuwa się na stronę następną. Sprowadzana strona zastępuje więc stronę na wskazanej ostatecznie pozycji, po czym wskazówka przesuwa się do następnej strony.

W przedstawionym przykładzie wskazywana jest strona nr 5, ale bit odniesienia do tej strony jest ustawiony, więc po jego skasowaniu wskazówka przesuwa się na stronę nr 2. Dla tej strony bit odniesienie jest skasowany, więc nastąpi jej usunięcie, konkretnie ramka tej strony zostanie użyta do wymiany, a wskazówka przesunie się na stronę nr 4.

W niektórych publikacjach odróżnia się algorytm zegarowy od algorytmu drugiej szansy (FINUFO), przedstawiając ten drugi, jako algorytm FIFO, w którym strona na czole kolejki jest:

  • usuwana, jeśli nie ma ustawionego bitu odniesienia, albo
  • przesuwana jest na koniec, jeśli jest ustawiony bit odniesienia, który jest przy tym kasowany.

Algorytm zegarowy natomiast przedstawia się jako listę cykliczną ramek, w których wymieniane są strony zgodnie z położeniem wskazówki.

slajd 27

Ulepszony algorytm drugiej szansy


Ulepszenie algorytmu drugiej szansy w tym przypadku polega na uwzględnieniu bitu modyfikacji. W celu redukcji kosztów unika się po prostu wymiany stron modyfikowanych, które muszą być dodatkowo zapisane na urządzeniu wymiany. Wyszukiwanie strony do wymiany polega więc na analizie wartości 2-bitowej, złożonej z bitu odniesienia na bardziej znaczącej pozycji i bitu modyfikacji na mniej znaczącej pozycji. W przestawionym przykładzie „najlepsza” do usunięcia zgodnie z obiegiem wskazówki jest strona nr 6, gdyż ma wyzerowane oba bity.

slajd 28

Algorytmy ze sprowadzaniem na żądanie


Istotą algorytmów ze sprowadzaniem na żądanie jest zwalnianie ramek, uznanych za nie wykorzystywane, wcześniej niż to wynika z potrzeb realizacji samej wymiany. Celem wcześniejszego zwalniania jest uzyskanie ramek na potrzeby innych procesów, którym tych ramek brakuje. W skrajnych przypadkach niewystarczająca liczba ramek może być przyczyną zawieszenie procesu i przeniesienia całego obrazu w obszar wymiany. Uzyskanie wolnych ramek umożliwia z kolei aktywację procesu — wprowadzenie do pamięci operacyjnej niezbędnych jego stron.

Algorytm VMIN (ang. Variable-space MIN) jest optymalny w klasie algorytmów ze sprowadzaniem na żądanie, ale oparty jest na znajomości przyszłego ciągu odniesień do stron. Decyzja o usunięci strony z pamięci wynika z porównania kosztu ponownego sprowadzenia, oraz kosztu utrzymania do czasu następnego odniesienia. Jeśli koszt ponownego sprowadzania jest mniejszy, strona jest usuwana.

Algorytm WS (ang. Working Set) oparty jest na koncepcji zbioru roboczego , czyli zbioru stron, do których było odniesienie w ostatnim okresie czasu w przeszłości. Długość tego okresu mierzona liczbą odniesień, jest parametrem algorytmu. Algorytm WS wymaga monitorowania odniesień do pamięci, więc wymaga wsparcia sprzętowego. Wykorzystywany jest tutaj bit odniesienia.

Przybliżoną realizacją idei zbioru roboczego, wykorzystującą bit odniesienia, jest również algorytm WSClock.

Algorytmy PFF (ang. Page Fault Frequency) i VSWS (ang. Variable-Interval Sampled Working Set) dają efekt podobny do zbioru roboczego, przy czym oparte są na częstość generowania błędów strony.

  • VMIN — usuwane są strony, których koszt utrzymania w pamięci jest większy od kosztu ponownego sprowadzenia
  • WS — usuwane są strony, do których nie było odniesień przez określony czas
  • WSCIock — przybliżona wersja algorytmu WS, oparta na bicie odniesienia
  • PFF, VSWS — przydział i zwalnianie ramek procesów realizowane jest na podstawie częstości zgłaszania błędów strony

Zbiór roboczy


Przedstawione definicje — zbioru roboczego oraz okna zbioru roboczego — oznaczają właściwie to samo. Pierwsza definiuje zbiór roboczy w oparciu o pojęcie okna, a druga definiuje okno w oparciu o pojęcie zbioru roboczego. Z punktu widzenia strony, pozostaje ona w zbiorze roboczym tak długo, jak długo ostatnie odniesienie do niej pozostaje w bieżącym oknie. Oznacza to, że od momentu ostatniego zaadresowania strony, pozostaje ona w zbiorze roboczym przez ? odniesień.

Ogólna (teoretyczna) koncepcja zbioru roboczego polega utrzymywaniu takiego zbioru dla każdego procesu. Strony, należące do zbioru roboczego, pozostawiane są w pamięci, natomiast ramki stron spoza zbioru roboczego są zwalniane. Zapotrzebowanie na ramki w systemie jest sumą mocy zbiorów roboczych wszystkich procesów. Jeśli liczba ta jest większa niż dostępna liczba ramek, może dojść do szamotania. Zadaniem zarządcy pamięci jest wówczas przeniesienie całego obrazu któregoś z procesów w obszar wymiany i odzyskanie jego ramek. Po uzyskaniu odpowiednio dużej liczby wolnych ramek (w przypadku zmniejszenia się zbiorów roboczych) można aktywować któryś z procesów zawieszonych. Wybór procesu do usunięcia lub aktywowania jest zadaniem planisty średnioterminowego.

Osobnym problemem jest dobór wielkości okna. Okno powinno być na tyle duże, żeby objąć tzw. strefę, czyli zbiór stron niezbędnych do wykonania określonego fragmentu programu (np. procedury). W praktyce zależy to od częstości generowania błędów strony przez proces.

  • Zbiór roboczy procesu (ang. working-set) — zbiór stron, które zostały zaadresowane w ciągu ostatnich τ odniesień do pamięci (w tzw. oknie zbioru roboczego)
  • Okno zbioru roboczego (ang. working-set window) — zakres odniesień do pamięci, które adresują strony należące do zbioru roboczego
  • Zbiór roboczy w chwili t przy rozmiarze okna τ oznaczony będzie jako W (t, τ)
  • Algorytm zbioru roboczego usuwa z pamięci wszystkie strony, które nie należą do zbioru roboczego.

Przykład zbioru roboczego


Dla przykładowego ciągu odniesień przedstawiono 2 zbiory robocze przy rozmiarze okna 4 oraz 2 zbiory robocze przy rozmiarze okna 6. Ze względu na powtarzające się odniesienia moc zbioru roboczego (liczba elementów) może być mniejsza niż rozmiar okna, co widać w przypadku okna o rozmiarze 6.

slajd 31

Przykład wymiany stron w oparciu o zbiór roboczy


Przykład pokazuje realizację ciągu odniesień z poprzedniego slajdu przy rozmiarze okna 5. Proces ma więc do dyspozycji 5 ramek. Początkowo wymiana przebiega tak samo, jak w przypadku FIFO lub LRU. Ciekawym momentem jest drugie odniesienie do strony nr 2. Formalnie strona nr 2 została właśnie usunięta ze zbioru roboczego, ale nastąpiło do niej odniesienie. Jest więc błąd strony, chociaż jego obsługa nie wymaga sprowadzania strony ponownie z pliku wymiany. Podobna sytuacja ma miejsce przy następnym odniesieniu do pamięci — do strony nr 4. Po kolejnym odniesieniu — ponownie do strony nr 4 — poza bieżącym oknem znajduje się ostatnie odniesienie do strony nr 5, więc strona ta jest usuwana ze zbioru roboczego i tym samym z pamięci operacyjnej. Po ostatnim odniesieniu do strony numer 4 zbiór roboczy redukuje się do 3 stron.

slajd 32

Koncepcja identyfikacji zbioru roboczego


Precyzyjna identyfikacja zbioru roboczego mogłaby być zaimplementowana podobnie jak algorytm LRU. Zaprezentowana koncepcja jest adaptacją licznika odniesień do stron. Problemem podobnie, jak w przypadku LRU, jest monitorowanie odniesień do stron oraz złożoność struktur danych na potrzeby pamiętania licznika. Ze względu na koszt takiej realizacji algorytm WS implementowany jest w sposób przybliżony.

  • Dla każdej ramki utrzymywany jest wirtualny (mierzony odniesieniami do pamięci) czas ostatniego odniesienia do niej.
  • Po każdym odniesieniu do strony zwiększana jest wartość licznika odniesień i wpisywana do odpowiedniej tablicy na pozycji odpowiadającej ramce, w której znajduję się adresowana strona.
  • Do zbioru roboczego należą te strony, dla których różnica pomiędzy bieżącą wartością licznika odniesień, a wartością wpisaną w tablicy jest mniejsza lub równa rozmiarowi okna zbioru roboczego.

Przybliżona realizacja koncepcji zbioru roboczego


Czas wirtualny i tym samym czas odniesienia do strony wyznaczany jest w sposób przybliżony — z dokładnością do okresu kontrolnego, wyznaczanego przez czasomierz lub błąd strony. Wystąpienie odniesienia do strony sprawdzane jest na podstawie bitu odniesienia w tablicy stron. Bieżąca wartość licznika staje się wirtualnym czasem odniesienia dla tych stron, dla których bit odniesienia jest ustawiony. Brak odniesienia do strony może oznaczać, że ostatnie odniesienie jest już poza oknem i stronę należy usunąć. W tym celu sprawdzana jest różnica pomiędzy bieżącą wartością licznika (bieżącym czasem wirtualnym), a czasem ostatniego odniesienia, odczytanym dla danej strony/ramki z przeznaczonej na to tablicy.

Upływ czasu wirtualnego musi być rejestrowany oddzielnie dla każdego procesu i tylko wówczas, gdy jest on wykonywany. Przerwanie zegarowe powinno więc zwiększać licznik w tym procesie, w kontekście którego jest obsługiwane.

Pomimo uniknięcia konieczności monitorowania wszystkich odniesień do pamięci, implementacja tego algorytmu i tak jest kosztowana, gdyż po każdym przerwaniu zegarowym wymagane jest testowanie bitu odniesienia każdej ze stron procesu.

  • Wspomaganie sprzętowe — bit odniesienia.
  • Okresowe (wyznaczone przez czasomierz lub przez wystąpienie błędu strony) zwiększanie licznika reprezentującego upływ czasu wirtualnego oraz sprawdzanie bitu odniesienia dla każdej z ramek.
  • Jeśli bit odniesienia jest ustawiony, to skasowanie bitu odniesienia i wpisanie bieżącej wartości licznika do odpowiedniej tablicy na pozycji odpowiadającej ramce.
  • Jeśli bit odniesienia jest skasowany, to sprawdzenie różnicy pomiędzy bieżącą wartością licznika a wartością wpisaną na odpowiedniej pozycji w tablicy i usunięcie strony, gdy różnica jest większa niż rozmiar okna.

Algorytm WSClock


Jak sama nazwa wskazuje, algorytm łączy podejście oparte na zbiorze roboczym z koncepcją algorytmu zegarowego. Podobnie jak w przybliżonej realizacji algorytmu zegarowego, utrzymywany jest wirtualny czas ostatniego odniesienia do strony, mierzony osobno dla każdego procesu.

Warto zwrócić uwagę na dwie istotne cechy algorytmu:

  • lista cykliczna (tarcza zegara) obejmuje wszystkie ramki w systemie, a nie ramki procesu, jak w przypadku klasycznego algorytmu zegarowego,
  • próba usunięcia strony podejmowana jest w reakcji na błąd strony, co oznacza, że jest to właściwie algorytm wymiany na żądanie.

Zasadniczą różnicą w stosunku do algorytmów wymiany na żądanie jest zastępowanie globalne. Podobieństwo do koncepcji zbioru roboczego przejawia się natomiast w usuwaniu pierwszej napotkanej strony, nie należącej do zbioru roboczego swojego procesu.

  • Dla każdej ramki (strony w ramce) utrzymywany jest wirtualny czas (przybliżony) ostatniego odniesienia.
  • Wszystkie ramki pamięci (niezależnie od przynależności do procesu) powiązane są w cykl.
  • W wyniku wystąpienia błędu strony sprawdzany jest bit odniesienia do strony wskazywanej jako kolejna do usunięcia.
  • Jeśli bit odniesienia jest ustawiony, zostaje on skasowany, po czym następuje wskazanie następnej ramki w cyklu i sprawdzenie bitu odniesienia.

Postępowanie w drugiej części algorytmu jest podobne, jak w przypadku właściwego przybliżenia algorytmu WS, czyli strona, do której nie było odniesienia, weryfikowana jest pod kątem przynależności do zbioru roboczego. Wyszukiwanie kończy się jednak na znalezieniu pierwszej ramki ofiary. Brak takiej ramki (brak strony ofiary) zgodnie z ideą zbioru roboczego oznacza, że suma rozmiarów zbiorów roboczych wyczerpuje limit dostępnych ramek pamięci fizycznej i należy zwiesić jakiś proces.

  • Jeśli bit odniesienia jest skasowany, sprawdzana jest różnica pomiędzy wirtualnym czasem bieżącym, a czasem ostatniego odniesienia do wskazywanej strony:
    • jeśli różnica jest większa od rozmiaru okna zbioru roboczego, następuje wymiana strony w ramce,
    • w przeciwnym razie strona pozostaje i następuje wskazanie i sprawdzenie ramki następnej.
  • W przypadku wykonania pełnego obiegu przez wskazówkę i stwierdzenia braku stron do wymiany następuje zawieszenie jakiegoś procesu.

Przykład działania algorytmu WSClock


W przykładzie wskazana do usunięcia jest strona nr 5, więc od ramki tej strony rozpocznie się poszukiwanie ofiary. Strona 5 ma ustawiony bit odniesienia więc z założenia jest w zbiorze roboczym i nie zostanie usunięta z pamięci. Wyzerowany zostanie jedynie bit odniesienia i ustawiony wirtualny czas odniesienia do strony na wartość aktualną dla bieżącego procesu, czyli 51. Dla uproszczenia przyjmijmy, że strony 2, 4 i 5 należą do tego samego procesu.

Kolejną kandydatką na liście jest strona nr 4. Bit odniesienia jest dla tej strony skasowany, ale ostatni czas użycia nie jest jeszcze poza oknem (45>51–10), więc strona pozostaje w pamięci, a czas jej użycia się nie zmienia. Następna na liście jest strona nr 2, której ostatnie użycie, zgodnie z wirtualnym czasem, jest poza oknem zbioru roboczego. Strona nr 2 we wskazanej ramce zostanie zastąpiona.

slajd 37

Algorytm zegarowy dwuwskazówkowy


Algorytm dwuwskazówkowy stosowany jest w niektórych systemach rodziny UNIX, np. SVR4. Realizuje on strategię, określaną jako NRU (Not Recently Used), która w tym przypadku oznacza, że jeśli w czasie pomiędzy przejściem wskazówki wiodącej a nadejściem zamykającej nie został ustawiony bit odniesienia, to strona jest usuwana. Czas pomiędzy przejściem tych wskazówek zależy od tempa przeglądania oraz rozstawu wskazówek. Parametry te są natomiast ustawiane zależnie od liczby wolnych ramek w systemie.

Jeśli uruchomienie algorytmu nie doprowadzi do uzyskania wystarczająco dużej liczby wolnych ramek, następuje zawieszenie jakiegoś procesu i zwolnienie jego ramek.

  • Wszystkie strony pamięci (niezależnie procesu) powiązane są w listę cykliczną
    • Lista przeglądana jest okresowo przez 2 wskazówki:

      • wiodąca (przednia) zeruje bit odniesienia,
      • zamykająca (tylna) wskazuje stronę do usunięcia.
    • Jeśli bit odniesienia przed nadejściem tylnej wskazówki zostanie ponownie ustawiony, strona pozostaje w pamięci, w przeciwnym przypadku jest usuwana.
      • Algorytm sterowany jest następującymi parametrami:

        • tempo przeglądania,
        • rozstaw wskazówek.

Przykład działania algorytmu zegarowego dwuwskazówkowego


Wskazówka wiodąca w przykładzie ustawiana jest na stronie nr 5, której bit jest zerowany. Wskazówka zamykająca ustawiona jest na stronie nr 3, dla której bit odniesienia nie został ustawiony, więc nastąpi jej usunięcie. Warto zwrócić uwagę, że bit odniesienie został ustawiony dla strony nr 7, więc po przejściu wskazówki zamykającej strona ta pozostanie w pamięci. W międzyczasie może zostać ustawiony bit odniesienia do strony nr 8. Jeśli jednak nie nastąpi to przed nadejściem zamykającej wskazówki, strona ta zostanie usunięta.

slajd 39

Algorytm PFF


Algorytmy bazujące na zbiorze roboczym są trudne w implementacji, gdyż ze względu na brak możliwości monitorowania odniesień do stron muszą być realizowane w sposób przybliżony.

Podobne efekty przy mniejszym koszcie implementacji można uzyskać stosują podejście oparte na kontroli częstości błędów strony. Podejście jest łatwiejsze w implementacji, gdyż wymaga aktualizacji struktur danych tylko w przypadku wystąpienia błędu strony, którego obsługa jest i tak dość czasochłonna.

Ogólna idea polega na tym, żeby zabierać ramki procesom zgłaszającym mało błędów strony, a przydzielać procesom, które często generują błędy strony. W przypadku przekroczenia dolnego progu można rozważać dwie strategie postępowania: żwawą i opieszałą. W strategii żwawej zwalniane są wszystkie ramki, dla których bit odniesienia jest skasowany, a w strategii opieszałej zwalniana jest tylko jedna ramka.
Implementacja algorytmu może być oparta na:

  • liczeniu błędów strony, czyli rzeczywistym wyznaczaniu częstotliwości błędów,
  • mierzeniu okresu pomiędzy błędami strony.
  • Jeśli częstotliwość błędów strony generowanych przez proces przekroczy ustalony poziom fH, to dla stron tego procesu sprowadzanych do pamięci przydzielana są nowe ramki.
    • Jeśli częstotliwość błędów strony spadnie poniżej ustalonego poziomu fL, to

      • zwalniana jest jedna ramka procesu lub
      • zwalniane są wszystkie ramki ze stronami, do których nie było odniesienia od chwili wystąpienia ostatniego błędu strony w danym procesie.
    • W szczególności fH= fL

    Implementacja algorytmu PFF — kontrola częstości błędów strony


    Kontrola częstości błędów strony wymaga wykonania dodatkowego zadania okresowego, wyznaczanego przez czasomierz, niezależnego od błędu strony. Umożliwia to oparcie decyzji o przydziale lub odebraniu ramek na średniej z dłuższego okresu, w przeciwieństwie do implementacji opartej na sprawdzaniu okresu między kolejnymi błędami strony.

    • Przy każdym błędzie strony generowanym przez proces zwiększany jest licznik błędów strony danego procesu oraz zerowane są bity odniesienia do jego stron.
    • W określonych interwałach czasu, wyznaczanych przez czasomierz, sprawdzane są (a następnie zerowane) liczniki poszczególnych procesów.
    • Jeśli wartość licznika jest większa od górnej granicy, to procesowi przydzielana jest dodatkowa ramka.
      • Jeśli wartość licznika jest mniejsza od ustalonej dolnej granicy, to zwalniana jest:

        • jedna ramka lub
    • wszystkie ramki z wykasowanym bitem odniesienia.

    Implementacja algorytmu PFF — kontrola okresu pomiędzy błędami strony


    Sprawdzanie okresu między kolejnymi błędami strony nie wymaga dodatkowej kontroli poza obsługą błędu strony, gdyż czas odmierzany jest przez jądro na podstawie taktów zegara, niezależnie od zastosowanego podejścia do wymiany stron. Problemem może być jednak pewna destabilizacja przydziału ramek, wynikająca ze zbyt szybkiej reakcji na przypadkowe błędy strony występujące w krótkim czasie. W teorii automatycznej regulacji można by to podsumować jako dominację członu różniczkującego (duży czas wyprzedzenia).

    • Przy każdym błędzie strony sprawdzany jest czas jaki upłynął od poprzedniego błędu strony.
    • Jeśli czas jest mniejszy od ustalonej wielkości Tmin, to na potrzeby sprowadzanej strony przydzielana jest dodatkowa ramka.
      • Jeśli czas jest większy od ustalonej wielkości Tmax, to

        • zwalniana jest jedna ramka lub
        • zwalniane są wszystkie ramki z wykasowanym bitem odniesienia.
      • Bit odniesienia dla stron pozostających w pamięci jest kasowany.

    Algorytm VSWS


    W zależności od implementacji, algorytm PFF albo słabo (wolno) dostosowuje się do zmieniającej się strefy w procesie, albo reaguje zbyt gwałtownie. Wolne dostosowanie polega na tym, że po wejściu w nową strefę zbyt długo utrzymywane są strony ze starej strefy. Może to powodować chwilowy wzrost zapotrzebowania na ramki z wszystkimi negatywnymi skutkami, np. zawieszaniem procesów. Zbyt gwałtowana reakcja może spowodować usunięcie stron potrzebnych do dalszego przetwarzania.

    Algorytm VSWS (zbioru roboczego ze zmiennym okresem próbkowania) przez odpowiednią parametryzację umożliwia lepsze dostosowanie do tego typu sytuacji. Jego istotą jest wcześniejsze lub późniejsze reagowanie na zmieniającą się strefę, zależnie od liczby błędów strony. Czas reakcji jest jednak obustronnie ograniczony, więc reakcja nie będzie ani zbyt szybka (gwałtowna), ani znacząco spóźniona.

    • Przy każdym błędzie strony zwiększany jest licznik błędów strony danego procesu — n.
    • Co pewien okres czasu Tt, wynikający ze stanu wymiany, następuje kontrola odniesień do stron.
      • W ramach kontroli wykonywane są następujące czynności:

        • strony, do których nie było odniesienia są usuwane (ich ramki sązwalniane),
        • bity odniesienia stron pozostających na następny okres (do których było odniesienie) są kasowane,
        • wartość licznika n jest zerowana.

    Wielkość interwału czasu dla algorytmu VSWS


    Interwał czasu pomiędzy kolejnymi kontrolami należy do przedziału obustronnie domkniętego od Tmin do Tmax , przy czym konkretna wartość zależy od momentu osiągnięcia liczby nmax błędów strony. Jeśli liczba błędów strony jest duża i osiągnie wartość nmax przed upływem czasu Tmin, to kontrola następuje po czasie Tmin. Jeśli upłynął czas Tmin, to kontrola nastąpi zaraz po osiągnięciu nmax błędów strony, nie później jednak niż po czasie Tmax. A więc najpóźniej kontrola wystąpi po czasie Tmax, niezależnie do liczby błędów strony.

    • Algorytm sterowany jest następującymi parametrami:
      • Tmax — maksymalna wielkość interwału czasu,
      • Tmin— minimalna wielkość interwału czasu,
      • nmax — maksymalna liczba błędów strony.
    • Kontrola następuje w chwili t, po czasie Tt od momentu poprzedniej kontroli, ustalanym następująco:
    • nt < nmaxTt = Tmax

      ntnmaxTminTtTmax

      Techniki poprawy efektywności wymiany


      Przedstawione techniki służą do zmniejszenia czasu obsługi błędu strony. Są one szczególnie przydatne w algorytmach ze sprowadzaniem na żądanie.

      Jeśli na potrzeby wymiany została znaleziona ramka, zawierająca zmodyfikowaną stronę, a w systemie dostępne są inne wolne ramki, to zamiast wymiany stron, wymagającej czasochłonnego zapisu, dla sprowadzanej strony przydzielana jest nowa ramka. Ramka z brudną stroną dołączana jest natomiast do puli ramek zwolnionych. W ten sposób następuje wymiana ramek zamiast wymiany stron.

      Ramki zwolnione w przypadku stosowania algorytmów ze sprowadzaniem na żądanie nie zawsze są natychmiast wykorzystywane na potrzeby innych procesów. Można więc pozostawić zawartość strony bez zmian do czasu przydziału tej ramki. Jeśli jednak przed ponownym przydziałem wystąpi żądanie dostępu do usuniętej strony, to błąd strony można obsłużyć bez wykonywania czasochłonnej operacji wejścia-wyjścia, przydzielając ramkę ze stroną ponownie.

      Czasami system jest niedociążony przez bieżące przetwarzanie. Taki chwilowy okres przestoju można wykorzystać do zapisu zmodyfikowanych stron. Kasowany jest wówczas bit modyfikacji i stronę łatwiej jest wymienić.

      W przypadku zwalniania ramek stron modyfikowanych operację zapisu w obszarze wymiany można odłożyć w czasie, dołączając ramkę do specjalnej listy. W miarę dostępności zasobów system stopniowo będzie zapisywał strony w ramkach z tej listy w obszarze wymiany i dołączał ramki do puli oczyszczonych wolnych ramek, gotowych w każdej chwili do użycia.

      • Wymiana ramek zamiast wymiany stron — przyspieszenie wymiany brudnej strony
      • Buforowanie usuniętych stron zamiast usuwania — mniej kosztowna obsługa błędu strony
      • Czyszczenie stron — ułatwienie ewentualnej wymiany
      • Utrzymywanie listy brudnych stron do usunięcia — opóźnienie zapisu stron w obszar wymiany

      Algorytmy wstępnego stronicowania


      Sens wstępnego sprowadzania wynika z analizy efektywności wymiany, przedstawionej wcześniej. W praktyce, skuteczność tego podejścia zależy od trafności decyzji o wstępnym sprowadzeniu. Na koszt wymiany wpływa również trafność decyzji o usuwaniu stron, ale sprowadzanie wstępne nie jest obligatoryjne, a więc daje potencjalny zysk, jednak obarczony ryzykiem. Przed omówieniem algorytmów warto przypomnieć, że sprowadzanie (również wstępne) przeprowadza się w wyniku wystąpienia błędu strony.

      Algorytm DPMIN (ang. Demand Prepaging MIN) — jest optymalny w klasie algorytmów ze sprowadzaniem na żądanie, ale oparty jest (podobnie jak wcześniej przedstawione algorytmy optymalne) na znajomości przyszłego ciągu odniesień do stron. W wyniku wystąpienia błędu strony wszystkie dostępne ramki są wypełniane stronami, do których nastąpi odniesienie w najbliższej przyszłości.

      Algorytm OBL (ang. One Block Lookahead) wykorzystuje założenie o lokalności przestrzennej odniesień do pamięci i wraz ze stroną, której zaadresowanie spowodowało błąd, sprowadza stronę następną (jeśli nie ma jej jeszcze w pamięci). Skojarzenie stron ma tu charakter statyczny.

      Algorytm SL (ang. Spatial Lookahead) również wykorzystuje założenie o lokalności przestrzennej, ale informacja o powiązaniu stron budowana jest w czasie działania algorytmu, ma więc charakter dynamiczny.

      Algorytm FDPA (ang. Fixed-space Demand Prepaging) opiera się na wskazówkach programisty lub wnioskach ze statycznej analizy kodu, przekazywanych do systemu poprzez wykonania specjalnych instrukcji. Instrukcje to dotyczą zarówno wskazania stron potrzebnych w przyszłości, jak i zbędnych. Algorytm uwzględnia więc również wskazówki odnośnie usuwania stron.

      • DPMIN — sprowadzane są wszystkie strony potrzebne w najbliższej przyszłości, które mieszczą się dostępnych ramkach
      • OBL — sprowadzana jest strona żądana oraz strona następna (wg. numeracji w tablicy stron)
      • SL — na podstawie wcześniejszych odniesień i błędów strony budowana jest tablica skojarzeń stron sprowadzanych po sobie i informacja taka wykorzystywana jest prze następny sprowadzaniu
      • FDPA — podejście uwzględniające sugestie programisty co do stron potrzebnych w przyszłości

      Algorytm SL


      Krótka charakterystyka algorytmów DPMIN i OBL przy opisie wcześniejszego slajdu jest wystarczająca, natomiast omówienia wymaga algorytm SL.

      Celem tablicy pred jest przechowywanie informacja o numerze strony, którą należy sprowadzić wstępnie w przypadku błędu braku strony. Jeśli więc wystąpi błąd strony przy odniesieniu do strony p , to wstępnie sprowadzona zostanie również strona, której numer jest na pozycji p w tablicy pred — pred[p]. Początkowo przyjmujemy, że będzie to strona następna, tak jak w przypadku OBL.

      Zmienna u przechowuje numer strony, do której odniesienie spowodowało ostatnio obsłużony błąd strony. Jeśli zatem następny błąd strony występuje przy adresowaniu strony p (p jest kolejną sprowadzaną stroną po stronie u ), to być może jest jakiś związek pomiędzy tymi stronami i w przyszłości również warto po wystąpieniu błędu strony przy dostępie do strony u wstępnie sprowadzić stronę p . Numer strony — p — powinien zostać zapisany w tablicy pred na pozycji odpowiadającej stronie u. Należy się jednak upewnić, że dotychczasowe skojarzenie dla strony u jest nieodpowiednie. Jeśli zatem przy sprowadzaniu strony u nie było wstępnego sprowadzenia innej strony lub strona wstępnie sprowadzona nie została użyta, skojarzenie dla u lepiej zmienić.

      Na końcu następuje wstępne sprowadzenie strony, wynikające z bieżącego skojarzenia dla p . To, czy skojarzenie jest właściwe, okaże się przy wystąpieniu następnego błędu strony. W tym celu wartość p podstawiana jest do zmiennej u.

      • System utrzymuje dodatkową tablicę pred, gdzie dla każdej strony pamiętana jest strona, sprowadzona po niej do pamięci. Początkowo pred[i] = i + 1.
      • u jest zmienną przechowującą nr strony ostatnio sprowadzanej do pamięci w wyniku odniesienia do niej.
      • W chwili wystąpienia błędu strony następuje sprowadzenie żądanej strony — p. Jeśli przy poprzedniej wymianie nie dokonano wstępnego sprowadzenia lub nie było odniesienia do strony wstępnie sprowadzonej do chwili obecnej pred[u] := p.
      • Jeśli strona q = pred[p] nie znajduje się w pamięci, to
        następuje również jej sprowadzenia.
      • u:=p

      Algorytm FDPA


      W wyniku analizy kodu w odpowiednich miejscach w programie pojawiają się instrukcje dla systemu operacyjnego, informujące o przyszłych potrzebach (lub ich braku) w odniesieniu do pewnych stron. Zgodnie z tymi instrukcjami w tablicy stron lub innej strukturze ustawiane są odpowiednie bity. W toku realizacji wymiany bity te są kasowane.

      Bit P oznacza, że strona będzie w najbliższej przyszłości potrzebna, a jego wykasowanie nastąpi przy odwołaniu do strony po jej sprowadzaniu do pamięci.

      Bit D oznacza, że strona nie będzie na razie potrzebna. Gdyby jednak strona została usunięta z pamięci i ponownie sprowadzana w wyniku błędu strony, bit ten zostanie skasowany.

      • W programie występują dodatkowe instrukcje dla systemu operacyjnego:
        • FREE(p) — strona p nie będzie wykorzystywana w niedalekiej przyszłości.
        • PRE(3) — strona p będzie wkrótce wykorzystywana.
      • Wykonanie takiej instrukcji skutkuje ustawieniem odpowiednich bitów dla strony:
        • bitu usunięcia — D,
          • bitu wstępnego sprowadzenia — P.

      System sprowadza oczywiście strony na żądanie i dokonuje wymiany w przypadku braku wolnych ramek. Usuwane są strony z ustawionym bitem D , a gdy takich nie ma, zgodnie z innym algorytmem, np. LRU lub w praktyce z którymś z jego przybliżeń. Algorytm usuwania nie jest tu najbardziej istotny poza preferencją dla stron „wskazanych” przez bit D.

      Strona z ustawionym bitem P może być zarówno w pamięci, jak i poza nią. Będąc poza pamięcią, strona taka czeka na sprowadzenie. Bit P ustawiony dla strony przebywającej w pamięci operacyjnej oznacza, że stronę tę wstępnie sprowadzono, ale nie było do niej jeszcze odniesienia, dlatego nie powinna być usunięta przy wymianie.

      System stara się sprowadzać do pamięci wszystkie strony z ustawionym bitem P w miarę dostępnych ramek. W bilansie ramek uwzględnia się zwolnienie ramek przez strony z ustawionym bitem D. Jak już wcześniej wspomniano, gdyby bit D ustawiony był dla strony sprowadzanej, to zostanie wykasowany.

      • W przypadku wystąpienia błędu strony sprowadzana jest strona żądana, ewentualnie wymieniana z jakąś stroną z ustawionym bitem D. Jeśli nie ma takiej strony stosowany jest inny algorytm usuwania np. LR U, z pominięciem stron, dla których ustawiony jest bit P.
      • Jeśli w systemie są wolne ramki lub mogą zostać zwolnione przez usunięcie stron z ustawionym bitem D, to sprowadza się tyle stron z ustawionym bitem P, na ile pozwala potencjalna liczba wolnych ramek.
      • W przypadku odniesienia do strony z ustawionym bitem P, bit ten jest kasowany.

      Segmentacja w systemie pamięci wirtualnej


      W niektórych systemach (między innymi IBM OS/2) podjęto próbę realizacji segmentacji na żądanie. Zarządzanie wymianą segmentów jest jednak znacznie bardziej skomplikowane, gdyż sprowadzenie segmentu do pamięci może wymagać upakowania i/lub przesunięcia w obszar wymiany jednego lub kilku segmentów znajdujących się w pamięci fizycznej. Optymalizacja decyzji w takim przypadku jest więc procedurą czasochłonną. W przypadku stronicowania czas sprowadzenia stron do pamięci oraz zapisu na dysku jest zmienną losową, w przypadku segmentacji, ze względu na zróżnicowany rozmiar segmentów, sam czas przesyłania danych i tym samym czas oczekiwania w kolejce do dysku jest trudniej przewidzieć.

      • Segmentacja na żądanie — wymiana segmentów pomiędzy pamięcią pierwszego i drugiego rzędu
      • Skomplikowana wymiana — zróżnicowany rozmiar segmentów
      • Mniejsza przewidywalność czasu dostępu — zróżnicowany czas przesyłania zawartości segmentu