Michał Siwak
2001-11-30
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 | ![]() |
pamięć ISA DMA |
ZONE_NORMAL | 16MB - 896MB | pamięć stale odwzorowywana przez jądro |
ZONE_HIGHMEM | ![]() |
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:
,
gdzie
jest liczbą
megabajtów dostępnej pamięci fizycznej.
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.
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:
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
bloków stronicowych o poniższych własnościach:
W powyższym przykładzie bliźniakami są grupy jednostronicowe o numerach
i
oraz
i
, nie są nimi
natomiast grupy czterostronicowe rozpoczynające się na pozycjach
i
(bo
nie jest
wielokrotnością
).
Przydział
stron pamięci odbywa się według następującego algorytmu: jeśli dysponujesz conajmniej jedną wolną
grupą
-stronicową, to przydziel tę grupę, wpp. znajdź najmniejsze takie
, że
i dysponujesz wolną grupą
-stronicową.
Przydziel blok wielkości
, resztę podziel na grupy rozmiaru
(na
podstawie wzoru
).
Podczas zwalniania bloku -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
i powtarza
procedurę dla powstałego w ten sposób bloku. Scalanie bloków kończy się, gdy uzyskamy blok wielkości
lub gdy
bliźniak zwolnionego bloku będzie zajęty.
Deskryptor każdej ze stref zawiera m.in. pole free_area[10]. Jest to tablica
dziesięciu pól typu *free_area_t. Pole
-te tablicy
zawiera:
Każdy bit w mapie bitowej free_area[i]->map opisuje status dwóch sąsiednich obszarów
o wielkości .
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
.
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):
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].
Proces może zażądać przydzielenia grupy
bloków
stronicowych wywołując jedną z pięciu funkcji zdefiniowanych w pliku mm/page_alloc.c:
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.) |
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).
Zwolnienie grupy
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.
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.
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ść
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.