Stosowanie pamięci wirtualnej ma wiele zalet nie tylko związanych z możliwością powiększenia zasobów pamięci ponad dostępną pamięć fizyczną. Umożliwia bardziej racjonalne wykorzystanie pamięci operacyjnej, gdyż programy tworzone są często z nadmiarem w stosunku do typowych potrzeb. Na przykład rozmiary tablic statycznych ustala się z nadmiarem w stosunku do typowych potrzeb, w kodzie uwzględnia się obsługę sytuacji wyjątkowych do których może nigdy nie dojść. Ten nadmiar nie musi być ładowany do pamięci. Zastosowanie pamięci wirtualnej może też zmniejszyć czas odpowiedzi, gdyż skraca czas ładowania kodu, który często odwzorowywany jest w przestrzeń adresową procesu bezpośrednio z pliku i sprowadzany w niewielkich porcjach na żądanie.
Celem wykładu jest przedstawienie zasady działania i problemów realizacji pamięci wirtualnej oraz omówienie algorytmów wymiany stron pomiędzy pamięcią operacyjną a pamięcią drugiego rzędu (obszarem wymiany).
Rozwiązanie problem wyboru ofiary bazuje na przesłankach o charakterze losowym i związane jest ściśle z algorytmem wymiany. Klasyfikacja i omówienie algorytmów wymiany stanowią ostatnią część wykładu.
Adresowanie stron odbywa się tak samo, jak w prostym stronicowaniu, omówionym w poprzednim module. W tablicy stron przechowywany jest jednak bit poprawności, informujący o stanie strony. Strona poprawna (ang. valid) to taka, która zlokalizowana jest w pamięci operacyjnej. Odniesienie do takiej strony nie wymaga jej sprowadzania. Jeśli zgodnie z wartością bitu poprawności strona jest uznana za niepoprawną, występuje błąd braku strony i zgłaszane jest odpowiednie przerwanie diagnostyczne. W ramach obsługi błędu strony następuje sprowadzenie strony z obszaru wymiany (ang. swap space), umieszczenie w wolnej ramce i ponowne wykonanie rozkazu. Takie działanie nazywa się leniwą wymianą (ang. lazy swapping).
Urządzeniem wymiany jest najczęściej dysk, na którym znajduje się plik wymiany lub specjalnie wyodrębniona strefa (tzw. partycja wymiany).
W dalszej części wykładu zamiennie będzie używane sformułowanie: adresowanie strony i odniesienie do strony , oznaczające wystawienie przez procesor adresu logicznego komórki, zlokalizowanej na tej stronie.
Ramkę, która jest użyta do wymiany określa się jako ramkę ofiarę (ang. victim frame), chociaż to raczej strona jest ofiarą. W dalszej części używane będą zależnie od kontekstu terminy: ramka ofiara , strona ofiara , lub po prostu ofiara.
Brak bitu modyfikacji w tablicy stron oznacz konieczność zapisania strony na urządzeniu wymiany, jeśli strona to mogła być potencjalnie modyfikowana. Jeśli bit modyfikacji istnieje, ustawiany jest przed jednostkę zarządzania pamięcią zawsze, gdy wystąpił cykl maszynowy zapisu na tej stronie, nawet jeśli zapis niczego w stanie strony nie zmienił (np. nastąpiło wpisanie do komórki pamięci takiej samej wartości, jaka była tam wcześniej).
Jeśli bit modyfikacji nie jest ustawiony, to znaczy, że w obszarze wymiany jest aktualna kopia strony, która znajduje się również w pamięci. Zastąpienie takiej strony sprowadza się do jej nadpisania w pamięci. Przy ustawionym bicie modyfikacji strona zastępowana musi być najpierw zapisana w obszarze wymiany, co istotnie zwiększa koszt operacji wymiany.
Przyjmując funkcję kosztu sprowadzenia zbioru stron — h , koszt realizacji wymiany jest po prostu sumą kosztów w chwilach odniesienie do pamięci. Jeśli żadna strona nie jest sprowadzana, koszt wynosi 0. Jeśli sprowadzana jest jedna strona, koszt wynosi 1.
W przypadku dysku żądanie odczytu bloków czeka w kolejce, aż urządzenie dyskowe będzie wolne, czyli skończy obsługę wcześniej zgłoszonych żądań. Czas oczekiwania nie zależy od wielkości zgłaszanego żądania, ale wielkość ta ma wpływ na łączny czas dostępu, na który składa się czas wyszukiwania ścieżki, opóźnienie obrotowe, czas przesyłania. Czas dostępu dotyczy każdego sektora, można jedynie minimalizować czas wyszukiwania i opóźnienie obrotowe, gdyż sektory z zawartością strony są lokalizowane blisko siebie.
Jak wynika z własności funkcji kosztu dla dysku, sprowadzenie kilku stron w wyniku realizacji jednego żądania jest bardziej kosztowne niż sprowadzenie jednej strony, ale mniej kosztowne niż sprowadzanie poszczególnych stron w wyniku osobnych żądań.
Liczba błędów strony wpływa również na długość kolejki żądań dostępu do dysku, co wydłuża czas oczekiwania. Można zatem wyciągnąć ogólny wniosek, że w celu redukcji kosztów wymiany należy minimalizować liczbę błędów strony, gdyż wpływa ona pośrednio lub bezpośrednio na wszystkie składowe kosztu.
Usunięcie z pamięci strony, która będzie potrzebna przyszłości, oznacza konieczność ponownego sprowadzenia jej do pamięci, a więc koszt, którego być może dałoby się uniknąć. Nasilenie tego zjawiska określane jest jako migotanie i oznacza drastyczny spadek efektywności działania systemu komputerowego, gdyż większość czasu cyklu przetwarzania proces spędza w stanie oczekiwania na gotowość urządzenia dyskowego. Rozwiązanie problemu wyboru ofiary oparte jest na przesłankach o charakterze losowym.
Problem wznawiania rozkazów wiąże się z koniecznością ponownego wykonania całego cyklu rozkazowego, w którym wystąpił błąd strony. Cykl rozkazowy może składać się z kilku cykli maszynowych, z których każdy może się wiązać z odniesieniem do innej strony pamięci. W niesprzyjających okolicznościach mogłoby dojść do sytuacji, w której w wyniku obsługi błędu strony następuje usunięcie z pamięci innej strony, adresowanej w tym samym cyklu rozkazowym. Wznowienie rozkazu ponownie zakończy się błędem strony w jednym z cykli maszynowych. W skrajnym przypadku rozkaz mógłby się nigdy nie wykonać. Problem wznawiania rozkazów można rozwiązać, zapewniając procesowi pewną minimalną liczbę ramek — nie mniejszą niż liczba różnych adresów, wystawianych na magistrali w jednym cyklu rozkazowym.
Problem z wyborem ofiary wynika z faktu, że nie znamy przyszłego ciągu odniesień do stron. Przyszłe odniesienia możemy jedynie przewidywać z pewnym prawdopodobieństwem na podstawie różnych przesłanek z odniesień w przeszłości. Większość typowych programów charakteryzuje się własnością lokalności. Często również optymalizatory kodu dokonują takiego rozmieszczenia obiektów, aby w trakcie wykonywania ujawniała się taka własność.
Lokalność przestrzenna sprowadza się do wnioskowania na podstawie odniesień do pewnych stron o przyszłych odniesieniach do innych stron. Podstawą takiego skojarzenia może być numeracja stron. Jeśli program lub większa struktura danych (tablica) zajmuje kilka kolejnych stron, to prawdopodobne jest, że po odniesieniu do pierwszej z tych stron nastąpi odniesienie do drugiej, a później do trzeciej. Skojarzenie takie można również oprzeć o obserwację wcześniejszych odniesień. Jeśli strona p2 często była adresowana zaraz po stronie p1 , to być może na stronie p1 jest skok do instrukcji, znajdującej się na stronie p2 . Ten rodzaj lokalności można wykorzystać przy podejmowaniu decyzji o usuwaniu, ale również przy sprowadzaniu stron, kiedy stosowane jest tzw. sprowadzanie wstępne (sprowadzanie kilku stron w wyniku jednego błędu strony).
Sama identyfikacja wynikać może z różnych przesłanek, a precyzja tej identyfikacji uzależniona jest od zasadności przyjętych przesłanek.
W klasie algorytmów wymiany ze sprowadzaniem na żądanie o specyfice algorytmu również decyduje sposób wyboru strony usuwanej, a często stron usuwanych. W tych algorytmach strona (lub kilka stron) może być usunięta w dowolnym momencie, niekoniecznie przy okazji obsługi błędu strony.
W klasie algorytmów ze wstępnym sprowadzaniem odniesienie do strony nieobecnej w pamięci operacyjnej skutkuje błędem strony, ale przy okazji jego obsługi może nastąpić sprowadzenie oprócz strony żądanej innych stron. Istotą algorytmów tej klasy jest wybór stron wstępnie sprowadzanych, można więc przyjąć dowolny sposób usuwania, łącząc w ten sposób ideę wstępnego sprowadzania z różnymi koncepcjami utrzymania stron w pamięci.
W zastępowaniu globalnym poszukiwanie ramki ofiary dotyczy całej puli ramek niezależnie od bieżącego przydziału. Może więc dojść do podkradania ramek, kiedy jeden proces traci ramkę na rzecz innego. Takie podejście ułatwia adaptację liczby ramek używanych przez procesy do zróżnicowanych potrzeb, ale jest niebezpieczne dla efektywności całego systemu, gdy liczba ramek jest zbyt mała. Może wówczas dojść do zjawiska szamotania.
Zastępowanie globalne w naturalny sposób prowadzi do przydziału dynamicznego, nie ma natomiast sensu w przypadku przydziału statycznego. Przydział statyczny wymaga zastępowania lokalnego, ale w przypadku zastępowania lokalnego również można zastosować przydział dynamiczny. W ramach obsługi błędu strony wymiana jest lokalna, ale okresowo liczba ramek może się np. zwiększyć, co wyeliminuje na jakiś czas problem zastępowania w przypadku kolejnych błędów strony. Liczba ramek przydzielonych procesowi może też oczywiście się zmniejszyć.
Z przydziałem ramek wiąże się ustalanie ich liczby. Jest to szczególnie istotne w przydziale statycznym, ale dotyczy również początkowej liczby ramek w przydziale dynamicznym. Niezależnie od sposobu przydziału proces, który jest w pamięci powinien mieć do dyspozycji pewną minimalną liczbę ramek, gwarantującą uniknięcie problemu wznawiania rozkazów. Liczba ramek powinna być nie mniejsza, niż maksymalna liczba różnych adresów, jakie mogą być wystawione na magistrali w jednym cyklu rozkazowym.
Zakładając, że spełnione jest minimum dla każdego procesu przebywającego w pamięci, liczba ramek może być:
Algorytm MIN oparty jest na nierealnej przesłance, wymagającej znajomości przyszłego ciągu odniesień. Z drugiej strony jest to algorytm optymalny w tej klasie, dlatego wykorzystywany jest dla celów porównawczych. Można w ten sposób sprawdzać, ile tracimy, opierając się na przesłankach z historii dotychczasowych odniesień. Jest to zatem swego rodzaju miara zasadności tych przesłanek.
Algorytmy FIFO i LIFO oparte są na kolejności sprowadzania stron do pamięci. FIFO usuwa strony w kolejności ich sprowadzania LIFO w kolejności odwrotnej. FIFO sprawdza się dobrze w przypadku programów, w których jest prosty, sekwencyjny przepływ sterowania od początku programu do końca, z małą liczbą pętli, czy wywołań podprogramów. LIFO natomiast właściwy jest dla przypadków pętli, gdyż ponowne przejście sterowania do tej samej instrukcji nastąpi dopiero w następnej iteracji. Dla pętli istnieje jeszcze inny algorytm — LD (ang. loop detection), którego prezentację tu pominięto.
Algorytmy LRU, LFU i MFU oparte są na przesłankach, wymagających monitorowania odniesień do pamięci. Dla LRU istotny jest czas ostatniego odniesienia, a dla LFU i MFU liczba odniesień w przeszłości. LRU jest typowym algorytmem dla programów, charakteryzujących się lokalnością czasową odniesień do pamięci. Algorytmy LFU i MFU (tzw. algorytmy licznikowe) oparte są na zupełnie przeciwnych przesłankach: LFU usuwa stronę, do której było najmniej odniesień do początku przetwarzania lub od momentu sprowadzenia do pamięci (są to dwa warianty algorytmów licznikowych), a MFU usuwa stronę, do której było najwięcej odniesień.
Usunięcie tej samej strony w przypadku algorytmów LFU i LRU oraz MFU i LIFO jest przypadkowe i kolejna wymiana w przypadku tych algorytmów może wykazać różnice.
Warto też przy tej okazji zwrócić uwagę, że dla algorytmów licznikowych wybór może być niejednoznaczny, gdyż liczba odniesień do różnych stron może być taka sama. Jako kryterium rozstrzygnięcia można przyjąć czas sprowadzenia, czyli strony z taką samą wartością licznika usuwane są w kolejności FIFO.
Przy założeniu, że strony sprowadzane są pojedynczo nie ma tego problemu w algorytmach opartych na kolejności zdarzeń w czasie, czyli MIN, FIFO, LIFO i LRU.
W przypadku 4 ramek początek jest bardziej optymistyczny, gdyż po 4 pierwszych odniesieniach z błędem, wypełnione ramki zdają się gwarantować stabilność przetwarzania. Jednak sprowadzenie strony nr 5 powoduje usunięcie strony numer 1, która sprowadzana jest jako następna, usuwając z kolei potrzebną później stronę nr 2 itd. Ostatecznie mamy 10 błędów strony pomimo zwiększenia liczby ramek . Paradoks ten, nazywany anomalią Belady’ego, dotyczy wybranych algorytmów, między innymi algorytmu FIFO. Anomalia nie ujawnia się być może zbyt często, ale może wzbudzać obiekcje co do efektów przydziału dodatkowych zasobów.
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.
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.
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:
W dalszej części omówione zostaną 3 algorytmy, w których wykorzystywane jest omówione wspomaganie sprzętowe:
Poza tym, bity te wykorzystywane są w niektórych algorytmach wymiany ze sprowadzaniem na żądanie.
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.
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:
Algorytm zegarowy natomiast przedstawia się jako listę cykliczną ramek, w których wymieniane są strony zgodnie z położeniem wskazówki.
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.
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.
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.
Warto zwrócić uwagę na dwie istotne cechy algorytmu:
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.
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.
Jeśli uruchomienie algorytmu nie doprowadzi do uzyskania wystarczająco dużej liczby wolnych ramek, następuje zawieszenie jakiegoś procesu i zwolnienie jego ramek.
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:
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).
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.
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
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.
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 .
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.
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.
