Przydział i zwalnianie bloków stronicowych, demon kswapd

Michał Siwak

2001-11-30

Strefy

W starych procesorach Intela adres fizyczny komórki pamięci reprezentowany był jako 32-bitowa liczba całkowita bez znaku. Umożliwiało to zaadresowanie do 4GB pamięci. Współczesne procesory obsługują dodatkowo tzw. PAE (Physical Address Extensions). Powoduje to rozszerzenie zwykłego, 32-bitowego adresu fizycznego o cztery dodatkowe bity, co pozwala zaadresować do 64GB pamięci. Jednakże adres liniowy w systemie Linux ciągle reprezentowany jest przez liczbę 32-bitową. Z tego względu w danej chwili jądro może stale odwzorowywać jedynie 4GB RAMu.

Z drugiej strony, w trybie DMA dostępne jest tylko pierwsze 16MB pamięci. Powyższe dwa fakty sprawiły, że Linux dzieli całą dostępną w komputerze pamięć na trzy strefy (include/linux/mmzone.h):

Nazwa Zakres Typ pamięci
ZONE_DMA $<$16MB pamięć ISA DMA
ZONE_NORMAL 16MB - 896MB pamięć stale odwzorowywana przez jądro
ZONE_HIGHMEM $>$896MB pamięć nie odwzorowywana stale przez jądro - tylko bufor stron i procesy użytkownika

Informacje o każdej ze stref przechowywane są w strukturze typu zone_struct. Jej najważniejsze pola to:

Pola pages_high, pages_low, pages_min inicjowane są podczas startu systemu przez funkcję free_area_init_core znajdującą się w pliku mm/page_alloc.c. Ich domyślne wartości to odpowiednio: $3n, 2n, n$, gdzie $n$ jest liczbą megabajtów dostępnej pamięci fizycznej.

Zajmowanie i zwalnianie bloków pamięci

Linux przydziela i zwalnia bloki stronicowe korzystając z tzw. algorytmu bliźniaków (buddy algorithm). Poniżej znajduje się krótki opis jego zasady działania.

Algorytm bliźniaków

Wszystkie bloki stronicowe w systemie rozdzielone są między ciągłe obszary stron o rozmiarach $2^i$ stron dla $i = 0, 1, \ldots, 9$. Kolejny numer pierwszego bloku stronicowego obszaru jest wielokrotnością rozmiaru grupy. Innymi słowy blok składający się z 32 stron może zaczynać się jedynie na pozycji o numerze postaci $32x$ dla pewnego $x\in N$.

Dla przykładu, załóżmy, że pewien system dysponuje szesnastoma stronami pamięci RAM, z czego jedna (12) jest zajęta. Wówczas podział na grupy mógłby wyglądać tak:

rys. 1

Grupy czterostronicowe zaczynają się na pozycjach 4 i 8, a grupy dwustronicowe - na pozycjach 2 i 14, spełniona jest więc powyższa definicja.

Bliźniakami nazywamy dwie grupy $G_1, G_2$ bloków stronicowych o poniższych własnościach:

W powyższym przykładzie bliźniakami są grupy jednostronicowe o numerach $0$ i $1$ oraz $12$ i $13$, nie są nimi natomiast grupy czterostronicowe rozpoczynające się na pozycjach $4$ i $8$ (bo $4$ nie jest wielokrotnością $8$).

Przydział $2^n$ stron pamięci odbywa się według następującego algorytmu: jeśli dysponujesz conajmniej jedną wolną grupą $2^n$-stronicową, to przydziel tę grupę, wpp. znajdź najmniejsze takie $k$, że $k > n$ i dysponujesz wolną grupą $2^k$-stronicową. Przydziel blok wielkości $2^n$, resztę podziel na grupy rozmiaru $2^{n+i}$ (na podstawie wzoru $2^k - 2^n = \sum^{k-n-1}_{i=0}2^{n+i}$).

Podczas zwalniania bloku $2^n$-stronicowego system sprawdza, czy przypadkiem jego bliźniak nie jest zaznaczony jako wolny. Jeśli tak, to łączy oba bloki w jeden o wielkości $2^{n+1}$ i powtarza procedurę dla powstałego w ten sposób bloku. Scalanie bloków kończy się, gdy uzyskamy blok wielkości $2^9$ lub gdy bliźniak zwolnionego bloku będzie zajęty.

Struktura tabeli free_area[]

Deskryptor każdej ze stref zawiera m.in. pole free_area[10]. Jest to tablica dziesięciu pól typu *free_area_t. Pole $i$-te tablicy zawiera:

Każdy bit w mapie bitowej free_area[i]->map opisuje status dwóch sąsiednich obszarów o wielkości $2^i$. Jeśli bit jest wyłączony, oznacza to, że oba obszary są wolne lub oba są zajęte, wpp. dokładnie jeden z nich jest zajęty.

UWAGA: Gdy oba sąsiednie obszary są wolne, są one traktowane jako część większego obszaru o rozmiarze $2^{i+1}$.

A oto schematyczne przedstawienie zawartości pola free_area dla przykładowej strefy zawierającej 16 stron (strona 12 jest używana, pozostałe są wolne; ,,S'' oznacza strażnika):

rys. 2.

Zawartość odpowiednich map bitowych przedstawia poniższa tabela:

free_area[0]->map 0 0 0 0 0 0 1 0
free_area[1]->map 0 0 0 1
free_area[2]->map 0 1
free_area[3]->map 1

UWAGA: Rysunek nie jest całkowicie poprawny. Dlaczego?
Odp: Przedstawiona sytuacja nigdy nie zdarzy się w prawdziwym systemie. Bloki 0 i 1 są bliźniakami, więc zostałyby połączone w większy blok 0-1. Ten natomiast zostałby połączony z blokiem 2-3, a powstały blok z blokiem 4-7. Ostatecznie otrzymalibyśmy blok 0-7 umieszczony na liście free_area[3].

Zajmowanie pamięci - get_free_pages

Różne sposoby wywołania get_free_pages

Proces może zażądać przydzielenia grupy $2^{order}$ bloków stronicowych wywołując jedną z pięciu funkcji zdefiniowanych w pliku mm/page_alloc.c:

Parametr mask

Parametr mask może być alternatywą bitową kilku flag, które wpływają na zachowanie się funkcji get_free_pages w następujący sposób:

Flaga Znaczenie
__GPF_DMA Przydziel pamięć w strefie DMA
__GPF_HIGHMEM Przydziel pamięć w strefie pamięci wysokiej
__GPF_WAIT Czy możemy po obudzeniu demona kswapd wywołać planistę i oddać procesor?
__GPF_IO Czy możemy zainicjować operację I/O?
__GPF_FS Czy możemy korzystać bezpośrednio z systemu plików (swap)?
__GPF_HIGH Czy mamy wysoki priorytet? (Najczęściej oznacza to, że żądanie pochodzi od procesu działającego w trybie jądra.)

Kilka funkcji pomocniczych

Funkcja __alloc_pages(mask, order, zonelist)

Całą pracę związaną z przydziałem pamięci wykonuje funkcja __alloc_pages(mask, order, zonelist) wywoływana przez opisane wyżej funkcje z rodziny *get*page(s). Jej parametry to:

Algorytm działania tej funkcji opiszę w dwóch krokach. Najpierw pokażę, w jaki sposób przydzielana jest znaleziona już grupa wolnych bloków stronicowych, później opiszę sposób w jaki te strony są odnajdowane i odzyskiwane (pre-paging).

Funkcja __alloc_pages - przydział grupy bloków stronicowych

  1. Znajdź strefę, w której suma bloków pustych i nieaktywnych oraz wolnych jest większa od wskaźnika poziomu limit (PAGES_MIN, PAGES_LOW lub PAGES_HIGH). Jeśli nie ma takiej strefy, zwróć NULL.
  2. Zajmij lock zone->lock.
  3. Znajdź najmniejsze takie $k$, że: $order \leq k \leq 9$ oraz lista free_area[k]->free_list jest niepusta. Niech B będzie pierwszym blokiem z tej listy (rozmiaru $2^k$). Zwróć NULL jeśli nie uda się znaleźć takiego bloku.
  4. Usuń B z listy free_area[k]->free_list.
  5. Uaktualnij zawartość mapy bitowej free_area[k]->map zmieniając bit odpowiadający blokowi B na przeciwny.
  6. Zmniejsz licznik wolnych bloków stronicowych zone->free_pages.
  7. while $(logarytm\; rozmiaru\; B) > order$ do
    podziel $B$ na dwóch bliźniaków $B_1$ i $B_2$;
    $B_1$ wstaw na listę free_area[k-1]->free_list;
    zmień na przeciwny bit odpowiadający $B_1$ w free_area[k-1]->map;
    $B$ := $B_2$;
    end
  8. Zwolnij lock zone->lock.
  9. Zaznacz, że strona jest używana.

Funkcja __alloc_pages - pre-paging

  1. if istnieje strefa taka, że (free_pages $\geq$ pages_low)
    then alokuj pamięć w tej strefie
    (* Alokujemy pamięć w strefie, w której jest dużo nieużywanej jeszcze pamięci, bo nie zawiera ona danych, które trzebaby swapować. *)
  2. if (free_pages $<$ pages_min)
    then obudź demona kreclaimd
    (* Demon kreclaimd przenosi strony z listy inactive_clean na listy wolnych stron free_list. *)
  3. if istnieje strefa taka, że (free_pages + inactive_clean_pages $\geq$ pages_high)
    then alokuj pamięć w tej strefie
    (* Jeśli w systemie działa dużo procesów, to najprawdopodobniej tutaj nam się uda, gdyż strony są w takiej sytuacji szybko dezaktywowane. *)
  4. if istnieje strefa taka, że (free_pages + inactive_clean_pages $\geq$ pages_low)
    then alokuj pamięć w tej strefie
    (* Jeśli w systemie jest dużo pamięci i nie zostało zaalokowanych wiele nieciągłych obszarów pamięci, to najprawdopodobniej tutaj nam się uda. *)
  5. Obudź demona kswapd;
    if (GPF_WAIT)
    then schedule()
    (* Oddajemy procesor, by dać kswapd szansę zwolnienia trochę pamięci. *)
  6. Spróbuj alokować pamięć w strefie takiej, że free_pages + inactive_clean_pages $\geq$ pages_min. Demon kswapd powinien za chwilę zwolnić trochę pamięci i sytuacja wróci do normy.
  7. if $order > 0$
    then
    page_launder();
    while lista inactive_clean_pages jest niepusta do
    przenieś stronę z inactive_clean_pages na odpowiednią listę free_list;
    spróbuj zaalokować pamięć;
    end
    (* Czyścimy nieaktywne, brudne strony i przenosimy strony z listy inactive_clean_list na odpowiednie listy free_pages, aby uzyskać duży, ciągły obszar wolnej pamięci. *)
  8. if $order == 0$ && GFP_WAIT
    then
    try_to_free_pages();
    if udało się coś zwolnić
    then goto 1
    else zwróć NULL
    (* Jeśli chcemy zaalokować tylko jedną stronę, działamy w pętli do skutku. Jeśli potrzebny blok jest większy, poddajemy się, aby nie zawiesić się w pętli nieskończonej w przypadku dużej fragmentacji pamięci. *)
  9. Nie udało się, zwróć NULL

Zwalnianie pamięci - free_pages

Zwolnienie grupy $2^{order}$ bloków stronicowych zawierającej blok znajdujący się pod adresem addr, następuje w wyniku wywołania funkcji free_pages(addr, order). Jest to krótka funkcja, która sprawdza, czy addr nie jest równy NULL oraz czy strona jest rzeczywiście zaalokowana. Jeśli tak, wywołana zostaje funkcja __free_pages_ok(page, order), która wykonuje za nas całą czarną robotę. Oto algorytm jej działania.

  1. Sprawdź, czy strona kwalifikuje się do usunięcia (tzn. nie jest brudna, aktywna, zablokowana, nie znajduje się w podręcznej pamięci wymiany, etc.).
  2. Wylicz adres początku grupy bloków stronicowych, do której należy strona page. Niech będzie to $B$.
  3. Zajmij lock zone->lock.
  4. Zwiększ licznik free_pages wolnej pamięci w strefie.
  5. while $(logarytm\; rozmiaru\; B) < 10$ do
    zmień bit odpowiadający $B$ w mapie bitowej map na przeciwny;
    if bliźniak $B_2$ bloku $B$ jest zaalokowany
    then przerwij pętlę;
    else
    usuń $B_2$ z listy wolnych bloków;
    $B := B \cup B_2$;
    (* Skończymy scalanie bloków, gdy bliźniak zwalnianego bloku będzie używany lub gdy uzyskamy ciągłą grupę $2^9$ bloków stronicowych. *)
  6. Dodaj $B$ do listy wolnych bloków zone->free_area[k]->free_list, gdzie k jest logarytmem wielkości bloku $B$.
  7. Zwolnij lock zone->lock.

Działanie demona kswapd

W czasie działania funkcji __alloc_pages budzony jest demon kswapd. Cóż to takiego? Jest to wątek jądra aktywujący odzyskiwanie pamięci. Jest on uaktywniany co sekundę oraz w chwili, kiedy jądro ,,zauważy'', że liczba wolnych bloków stronicowych w danej strefie spadła poniżej wartości pages_low. Wątek ten wykonuje w pętli nieskończonej funkcję kswapd(), której algorytm jest przedstawiony poniżej.

  1. if nr_free_pages + nr_inactive_clean_pages $<$ freepages.high
    then do_try_to_free_pages()
  2. if udało się odzyskać wystarczająco dużo pamięci
    then zaśnij na sekundę
    else
    if w systemie jest bardzo mało wolnej pamięci
    then oom_kill();

Dodatkowo co sekundę wątek kswapd wykonuje następujące dwie czynności:

Funkcja oom_kill() zabija w sytuacji krytycznej jakiś proces, aby odzyskać trochę pamięci. Próbuje ona zgadnąć, zabicie którego procesu pozwoli na odzyskanie maksymalnej ilości pamięci oraz nie będzie zbyt uciążliwe dla użytkownika. Do oceny, który proces najlepiej spełnia to kryterium służy funkcja badness. Oblicza ona wartość

\mathcal{B} =

gdzie $[\varphi] = 1$, gdy $\varphi$ prawdziwe, $0$ wpp.

Proces o największej wartości badness zostaje zabity.

Funkcja do_try_to_free_pages() próbuje odzyskać trochę pamięci. W tym celu: czyści brudne strony, dezaktywuje pewne strony i odzyskuje nieużywaną pamięć wymiany alokatora płytowego. Dokładny opis działania tej funkcji został przedstawiony w innym referacie.