W tym dokumencie są opisane metody, jakie jądro Linuxa wykorzystuje do zwalniania pamięci, tj. algorytm wyboru ramki do zwolnienia i metody zwalniania pojedynczych ramek, w tym obsługa logicznych urządzeń wymiany.
Domyślnie, kiedy do ramki jest zapisywana nowa strona, jej początkowy wiek jest ustalany na 3. Przy każdym odwołaniu do strony, jej wiek zwiększa się o 3, zaś demon kswapd okresowo (przy każdej nieudanej próbie usunięcia z pamięci) zmniejsza wiek nieużywanych stron o 1. Strona może być usunięta z pamięci, gdy jej wiek spada do 0.
Ta metoda, zwana liniowym postarzaniem, jest nietypowa, gdyż w większości systemów stosuje się postarzanie wykładnicze.
Każda pozycja tablicy procesów posiada pole mm typu mm_struct, zawierające wskaźniki do struktury danych opisującej przestrzeń adresową procesu. Ta struktura to zbiór struktur typu vm_area_struct, z których każda opisuje spójny obszar pamięci wirtualnej przydzielonej procesowi. Dla każdego obszaru pamiętany jest m. in. jego (wirtualny) adres początkowy i końcowy, rodzaj (np. dzielony) i prawa dostępu.
Na zbiór tych obszarów nałożone są 3 struktury:
Pierwsze dwie nałożone struktury służą do przeszukiwania pamięci wirtualnej procesu. Lista jednokierunkowa służy do liniowego przeszukiwania pamięci w celu przejrzenia kolejnych stron przydzielonych procesowi. Drzewo AVL jest przeznaczone do szybkiego wyszukiwania obszaru pamięci zawierającego podany adres. Ta operacja jest wykonywana na tyle często (np. przy każdym błędzie braku strony), że trzeba było tu zastosować tak skomplikowaną strukturę danych.
Trzecia nałożona struktura, dwukierunkowa lista cykliczna, jest wykorzystywana tylko przy obszarach pamięci dzielonej i łączy obszary należące do przestrzeni adresowych różnych procesów. Służy ona do uzyskiwania dostępu do stron pamięci dzielonej.
Można się zastanawiać, czy rzeczywiście użycie takiej algorytmicznej "armaty" jaką są drzewa AVL bylo tu niezbędne. Nowy obszar pamięci wirtualnej procesu jest tworzony przy każdym powiększeniu się procesu (np. w wyniku wywołania funkcji systemowej brk), a także przy mapowaniu pliku dyskowego do pamięci wirtualnej. Autorzy tego fragmentu jądra piszą, że zazwyczaj liczba takich obszarów dla jednego procesu oscyluje w granicach 6, choć w pewnych sytuacjach może osiagnąć 3000.
Każdy obszar pamięci wirtualnej może mieć przypisany zbiór operacji (pamiętany w polu vm_ops) właściwych dla stron tego obszaru przy zapisywaniu ich na dysk, odczytywaniu, obsłudze błędów strony itp. Przy wykonywaniu takich operacji najpierw sprawdzane jest, czy odpowiednia funkcja jest zdefiniowana, a jeżeli tak, to jest ona wykonywana. Jeżeli nie, wykonywana jest operacja domyślna. W praktyce, specjalne operacje są zdefiniowane dla stron pamięci dzielonej i dla obrazów plikow dyskowych.
W pierwszych wersjach Linuxa, zwalnianie pamięci głównej następowało dopiero wtedy, gdy liczba wolnych ramek spadała poniżej tego poziomu i było wykonywane bezpośrednio przez jądro, przy czym jądro było zajęte wyłącznie tą operacją aż do chwili, gdy się ona powiodła. To powodowało przestoje w pracy systemu. Z tego powodu w nowszych wersjach jądra wprowadzono demona kswapd, który jest wątkiem jądra i pracuje przez cały czas działania systemu. Jest on odpowiedzialny za to, aby procedura zwalniania ramki "za wszelką cenę" była wykonywana jak najrzadziej.
Kswapd ma za zadanie utrzymywać liczbę wolnych ramek w pamięci powyżej pewnego poziomu, opisanego zmiennymi free_pages_low (standardowo 72) i free_pages_high (96). Jeżeli liczba wolnych ramek nie spada poniżej free_pages_high, demon pozostaje uśpiony. Jeśli jednak jest inaczej, demon budzi się i co pewien czas (standardowo 4 razy na sekundę) próbuje zwolnić pewną liczbę ramek pamięci głównej (standardowo 4). Jeśli liczba wolnych ramek spada poniżej free_pages_low, demon zaczyna budzić się 2 razy częściej niż zwykle.
Zazwyczaj kswapd dopuszcza niepowodzenie operacji zwolnienia ramki. Jeśli po przejrzeniu części zasobów stwierdzi, że nie udało się nic zwolnić, przerywa poszukiwania i czeka na następne przebudzenie. Jednak wraz ze zmniejszaniem się ilości wolnej pamięci głównej przeszukiwanie obejmuje coraz większą część zasobów i może trwać coraz dłużej. Jeżeli liczba wolnych ramek spadnie poniżej min_free_pages, demon zwalnia ramki aż do chwili, gdy wzrośnie ona z powrotem do tego poziomu.
Za każda próbą zwolnienia ramki pamięci demon wykonuje następujący algorytm.
Poniżej opisany proces przeszukiwania zasobów systemu jest wielostopniowy: najpierw wybieramy metodę zwalniania pamięci, później proces, którego stronę usuniemy, następnie obszar jego pamięci wirtualnej, później stronę. Jeżeli podczas przeszukiwania jakiegoś zasobu (np. procesu) algorytm stwierdzi, że nie udało się nic zwolnić, cofa się o krok i kontynuuje przeszukiwanie, próbując przejrzeć następny zasób (np., w tym wypadku, proces).
Są 3 metody zwalniania ramek pamięci głównej: przez usuwanie prywatnych stron procesów (funkcja swap_out), stron pamięci dzielonej (shm_swap) i stron będących obrazami plików dyskowych (shrink_mmap). Te metody są wykonywane cyklicznie, przy czym jeżeli użycie którejś z nich zaowocowało zwolnieniem ramki, za kolejną próbą będzie ona wykonana ponownie.
Usuwanie stron SHM jest opisane w rozdziale o pamięci dzielonej. Usuwanie obrazów plików dyskowych jest opisane w rozdziale o stronicowaniu plików. Teraz opiszę usuwanie prywatnych stron procesów.
W tej metodzie, najpierw przeszukiwana jest tablica procesów, w celu znalezienia procesu posiadającego ustawiony atrybut swappable i zajmującego jakieś ramki w pamięci głównej (pole mm->rss>0). Przeszukiwanie rozpoczyna się od miejsca, w którym skończyło się poprzednie. Przeszukiwana jest większa lub mniejsza część tablicy procesów, w zależności od priorytetu, jaki został przydzielony całej operacji. Ten priorytet wzrasta, gdy poprzednia próba zwolnienia ramki zakończyła się niepowodzeniem i zmniejsza się w przeciwnym wypadku. Jest on też zwiększany, gdy liczba wolnych ramek w systemie spada poniżej wartości min_free_pages.
Po znalezieniu odpowiedniego procesu, ustalana jest liczba ramek, jakie będą mu odbierane (standardowo jest to 1/32 zajmowanych ramek, ale nie mniej niż 4). Za jednym razem będzie usuwana tylko jedna strona, ale ustalona wartość będzie zapamiętana i wykorzystana przy przyszłych próbach zwalniania pamięci.
Następnie, przeszukiwana jest pamięć wirtualna wybranego procesu. I znowu, przeszukiwanie rozpoczyna się od adresu, na którym zakończylo się poprzednie przeszukiwanie dla tego procesu. Przeszukiwane są kolejne obszary przydzielonej procesowi pamięci (pierwszy obszar do przeszukania jest znajdowany przy użyciu drzewa AVL obszarów, kolejne - liniowo przy pomocy listy jednokierunkowej).
Dla każdego obszaru, o ile nie jest on zablokowany lub dzielony, przeszukujemy go "po stronie wirtualnej". Dla każdej strony wirtualnej odnajdujemy jej fizyczny adres przy pomocy trzypoziomowych (na i386 - dwupoziomowych) katalogów i tablic stron (p. stronicowanie).
Po odnalezieniu wybranej strony w tablicach stron procesu, próbujemy ją usunąć z pamięci (p. Usuwanie strony z pamięci).
Jeżeli usunięcie strony się nie powiodło (np. była ona zbyt młoda), cofamy się o krok i szukamy dalej. Podobnie na wszystkich szczeblach tego algorytmu: jeśli nie udało się np. zwolnić żadnej strony z obszaru pamięci wirtualnej, szukamy w następnym; podobnie z procesami itd.
Następnie podejmujemy decyzję, co zrobić ze stroną, na podstawie nastepujących informacji:
Dla każdego urządzenia wymiany pamięta się m.in. i-węzeł odpowiadającego urządzenia blokowego oraz mapę bajtową tego urządzenia. W jednym bajcie mapy pamięta się licznik odwołań do odpowiedniej ramki urządzenia. Gdy ten licznik spada do zera, można zwolnić ramkę pamięci pomocniczej do dalszego wykorzystania.
Przy przydzielaniu ramek urządzenia, system stara się przydzielać je pakietami. Pakiety nie muszą być spójne na dysku, ale kolejne ramki w pakiecie powinny być na dysku uporządkowane rosnąco. Dopiero po przydzieleniu całego pakietu ramek poszukiwanie wolnych ramek urządzenia rozpoczyna się od początku urządzenia blokowego. To ma na celu zmniejszenie średniego czasu dostępu (dyskowego) do ramki pamięci pomocniczej. (Domyślna wielkość pakietu to 32).
Logiczne urządzenia wymiany są powiązane w listę priorytetową. Upraszczając, przy poszukiwaniu wolnej ramki pamięci pomocniczej najpierw są przeszukiwane urządzenia o najniższym priorytecie.
Przy kopiowaniu strony z pamięci głównej do pomocniczej, najpierw znajdowana jest wolna ramka na ktorymś urządzeniu wymiany, a nastepnie przy pomocy funkcji rw_swap_page strona jest kopiowana na tę ramkę.