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.
Z punktu widzenia efektywności przetwarzania koszt wymiany można utożsamiać z czasem realizacji wymiany. W celu uproszczenia analizy przyjmuje się, że koszt usunięcia strony stanowi stałą część kosztu jej sprowadzenia. Koszt wynika zatem z czasu sprowadzania, który w ogólności zależy od:
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ń.
Konieczność sprowadzenia strony pojawia się dopiero przy wystąpieniu błędu strony. Sprowadzanie stron w okolicznościach innych niż obsługa błędu strony nie ma sensu, ale jak wynika z zaprezentowanej analizy, w ramach obsługi błędu strony sensowne może być sprowadzenie kilku stron, przewidując przeszłe odniesienia. Koszt sprowadzenia jest więc ściśle uzależniony od liczby błędów strony i liczby transmisji stron.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.
Zasadnicze problemy wymiany stron dotyczą decyzji odnośnie usuwanej strony oraz zagwarantowania dostępności wszystkich stron wymaganych do realizacji cyklu rozkazowego.
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ść można rozważać w dwóch aspektach: czasowym i przestrzennym. Lokalność czasową można sprowadzić do wielokrotnego odwołania w krótkim czasie do tej samej strony. Przypadek taki ma miejsce przy wykonywaniu programu, chyba że występują częste i dość dalekie (wychodzące poza stronę) skoki. Przypadek taki dotyczy również danych, np. tablic, a nawet pojedynczych zmiennych, gdyż programiści definiują często kilka zmiennych na potrzeby obsługi jakiegoś krótkiego fragmentu programu, np. pętli. Z punktu widzenia stronicowania oznacza to, że jeśli strona zostanie sprowadzona do pamięci operacyjnej, przyda się wielokrotnie w czasie wykonywania określonego fragmentu programu. Własność lokalności czasowej wykorzystywana jest często przy podejmowaniu decyzji o usunięciu strony z pamięci.
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).
Podstawą efektywnego funkcjonowania pamięci wirtualnej jest oczywiście precyzyjna identyfikacja zbioru stron aktywnych. Wykorzystanie tej informacji polega na utrzymaniu stron aktywnych w pamięci. Jeśli ze względu na zbyt duże potrzeby procesów strony aktywne muszą być usuwane z pamięci, to i tak trzeba ponieść koszt ich ponownego sprowadzenia. W tego typu sytuacji dochodzi najczęściej do migotania stron (szamotania, ang. trashing), jednak identyfikacja stron aktywnych umożliwia wykrycie takiego ryzyka i podjęcie pewnych działań zapobiegawczych.
Sama identyfikacja wynikać może z różnych przesłanek, a precyzja tej identyfikacji uzależniona jest od zasadności przyjętych przesłanek.
Klasyfikacja związana jest z okolicznościami, w jakich podejmowana jest decyzja o sprowadzeniu lub usunięciu strony. W algorytmach wymiany na żądanie zarówno sprowadzanie, jak i usuwanie wykonywane jest wówczas, gdy jest absolutna konieczność. W przypadku sprowadzania oznacza to, że jeśli strony nie ma w pamięci, to nie zostanie sprowadzona wcześniej, niż po wystąpieniu odniesienia do niej (zaadresowania jej przez procesor). W przypadku usuwania absolutna konieczność występuje dopiero wówczas, gdy brakuje miejsca w pamięci operacyjnej (nie ma wolnej ramki), a ze względu na występujące odniesienia do stron, znajdujących się poza pamięcią operacyjną, konieczne jest zwolnienie ramki na potrzeby sprowadzanej strony. Ponieważ strona do sprowadzenia jest jednoznacznie określona przez stan systemu (stan pamięci oraz adres wystawiony przez procesor), specyfika algorytmu tej klasy zależy od wyboru strony usuwanej z pamięci.
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.
Klasyfikacja wiąże się z zakresem ramek uwzględnianych przy poszukiwaniu ofiary. W przypadku zastępowania lokalnego proces dysponuje pewną liczbą ramek, w których muszą się pomieścić jego strony. Błąd strony tego procesu skutkuje ewentualnym usunięciem innej jego strony. Można w ten sposób ograniczyć (ale nie zlikwidować) negatywny wpływ zbyt częstego generowania błędów strony przez proces na efektywność działania całego systemu.
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.
Klasyfikacja związana jest z adaptacją przydziału zasobów do zmieniających się potrzeb procesów. W przydziale statycznym proces otrzymuje pewną liczbę ramek na cały czas cyklu przetwarzania. W przydziale dynamicznym liczba ramek przydzielonych procesowi może się zmienić zależnie od intensywności generowania błędów strony. Jeśli liczba błędów strony, generowanych przez proces, jest stosunkowo duża to w zależności od możliwości, jakimi dysponuje system, można przydzielić dodatkowe ramki. Dodatkowe ramki mogą pochodzić z puli ramek odebranych procesom, które generowały mało błędów strony.
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ć: