Valid HTML 4.01!


Zarządzanie pamięcią

Spis treści


Podręczna pamięć stron

Podręczna pamięć stron (ang. page cache) służy do buforowania fizycznych stron. Pomysł wziął się z Uniksa SVR4, gdzie podręczna pamięć stron zastąpiła podręczną pamięć buforową wejścia-wyjścia (buffer cache), lecz w Linuksie został uogólniony.

W podręcznej pamięci stron są przechowywane strony następujących typów:

W każdym przypadku te dane pochodzą z jakiegoś pliku.

Praktycznie wszystkie operacje read() i write() przechodzą przez podręczną pamięć stron (z wyjątkiem plików otwartych z flagą O_DIRECT - w tym przypadku są wykorzystywane bufory w przestrzeni adresowej procesu).

Rozważając różnice pomiędzy buforowaniem bloków dyskowych wchodzących w skład pliku a buforowaniem stron, na których są przechowywane fragment plików należy pamiętać o tym, że:

Każdy deskryptor strony zawiera pola mappingi i index, które wiążą stronę z podręczną pamięcią stron. Pierwsze wskazuje na obiekt address_space, a drugie przesunięcie w ramach 'przestrzeni adresowej' właściciela strony.

Pamięć podręczna stron może zawierać wiele kopii tych samych danych dyskowych. Na przykład do tego samego 4 KB bloku danych zwykłego pliku można sięgać w następujący sposób:

Zatem te same dane pojawiają się w dwóch stronach, do których sięga się poprzez dwa różne obiekty address_space.

Struktura address_space jest pewnego rodzaju programowym MMU, odwzorowującym wszystkie strony jednego obiektu (np. i-węzła) w inną abstrakcję (zwykle fizyczne bloki dyskowe). Można na nią patrzeć jak na przestrzeń adresową pliku odwzorowanego do pamięci. Struktura address_space jest zdefiniowana w include/linux/fs.h:


struct address_space {
  struct inode            *host;          /* owner: inode, block_device */
  struct radix_tree_root  page_tree;      /* radix tree of all pages */
  unsigned long           nrpages;        /* number of total pages */
  struct address_space_operations *a_ops; /* methods */
  ... 
};

Metody obiektu pozwalają na wykonywanie na nim operacji wejścia-wyjścia bez potrzeby bezpośredniego odwoływania się do operacji systemu plików.


struct address_space_operations {
     int (*writepage)(struct page *page, struct writeback_control *wbc);
     int (*readpage)(struct file *, struct page *);
     int (*sync_page)(struct page *);
     int (*prepare_write)(struct file *, struct page *, unsigned, unsigned);
     int (*commit_write)(struct file *, struct page *, unsigned, unsigned);
     sector_t (*bmap)(struct address_space *, sector_t);
     int (*releasepage) (struct page *, gfp_t);
     ....
};

Obsługa podręcznej pamięci stron znajduje się w pliku mm/filemap.c, include/linux/pagemap.h.


Odwzorowywanie plików do pamięci

Funkcja do_mmap() tworzy nowy obszar pamięci dla procesu. Jeśli parametry file i offset są różne od NULL, to wskazują na obszar pliku, z którym będzie związany nowo tworzony obszar pamięci.


static inline unsigned long do_mmap(struct file *file, 
       unsigned long addr,
       unsigned long len, unsigned long prot,
       unsigned long flag, unsigned long offset)
{
   unsigned long ret = -EINVAL;
   if ((offset + PAGE_ALIGN(len)) < offset)
        goto out;
   if (!(offset & ~PAGE_MASK))
        ret = do_mmap_pgoff(file, addr, len, prot, flag, offset >> PAGE_SHIFT);
out:
    return ret;
}

Do usuwania istniejącego odwzorowania z przestrzeni adresowej procesu służy funkcja do_munmap().


int do_munmap(struct mm_struct *mm, unsigned long addr, size_t len)

Przerwanie błędu braku strony

Obsługa błędu braku strony w dużej mierze zależy od architektury. Dla i386 kod procedury obsługi przerwania braku strony do_page_fault znajduje się w pliku arch/i386/mm.c. Błędny adres (address) jest przekazywany przez rejestr cr2. Po sprawdzeniu, że istnieje poprawny kontekst pamięci woła się funkcję find_vma, która przegląda drzewo RB w poszukiwaniu właściwego vm_area_struct.


    vma = find_vma(mm, address);

Jeśli dla podanego adresu nie istnieje VMA, to jest wysyłany sygnał SIGSEGV (segmentation fault). Jeśli osiągnięto dno stosu, to stos zostanie rozszerzony (wywołanie expand_stack()). Jeśli adres jest poprawny, to sprawdza się prawa dostępu do strony, po czym wywołuje funkcję handle_mm_fault() (plik mm/memory.c), która sprowadzi stronę.

W funkcji handle_mm_fault() zakłada się blokadę na tablicę stron i przydziela odpowiednie pozycje tablic stron PMD i PTE (pmd_alloc() i pte_alloc()). Dalsze czynności wykonuje funkcja handle_pte_fault() Możliwe są cztery przypadki:

  1. Strony nie ma w pamięci i nigdy nie istniała: wywołuje się funkcję do_no_page(), która próbuje utworzyć nowe odwzorowanie strony. Jeśli jest to zwykła strona na pamięć, to funkcja do_anonymous_memory() przydziela pozycję na dowiązanie do strony i dodaje ją do tablic stron. Jeśli jest to strona tylko do czytania, to w PTE wstawia się adres globalnej systemowej strony wypełnionej zerami. Jeśli jest to strona z prawami do zapisu, to wywołuje się alloc_page().

  2. Strony nie ma w pamięci i strona istnieje: strona została kiedyś usunięta, więc wywołuje się funkcję do_swap_page(). Przeszuka ona podręczną pamięć wymiany i sprowadzi stamtąd stronę, gdy ją znajdzie, a wpp ściągnie ją z dysku.

  3. Strona jest w pamięci; zapis do strony: jeśli zapis do strony jest dozwolony, to strona jest oznaczana jako brudna i młoda, a TLB jest aktualizowane.

  4. Strona jest w pamięci i jest dozwolony jedynie odczyt; zapis do strony: jest to próba zapisu do strony, mimo że jest to niedozwolone. Wywołuje się funkcję do_wp_page(). Taki przypadek ma miejsce np. podczas tworzenia procesu w fork z kopiowaniem przy zapisie (copy-on-write). Funkcja docelowo wywołuje alloc_page() dla nowej strony i kopiuje starą stronę.

page fault


Wymiana stron

Linux nie nakłada żadnego ścisłego ograniczenia na całkowitą ilość RAM przydzielaną procesom jednego użytkownika. Nie nakłada także ograniczenia na rozmiar różnych pamięci pomocniczych stosowanych przez jądro. Kiedy obciążenie systemu jest niewielkie, RAM jest zajęty przez pamięci podręczne, z których z pożytkiem korzystają nieliczne wykonywane procesy. Kiedy zaś obciążenie systemu rośnie, RAM jest wypełniony głównie stronami procesów, a pamięci podręczne kurczą się, by zrobić miejsce na kolejne procesy.

W sytuacji, gdy w systemie zaczyna brakować pamięci głównej, np. dla utworzenia nowego lub dla powiększenia rozmiaru już istniejącego procesu, zachodzi potrzeba zwolnienia części pamięci. W takim wypadku jądro próbuje znaleźć w pamięci stronę zawierającą chwilowo niepotrzebne dane, po czym usuwa ją z pamięci, w razie potrzeby tworząc jej kopię w pamięci pomocniczej do przyszłego wykorzystania. Proces ten nazywa się wymianą lub wymiataniem (ang. swapping).

Algorytm odzyskiwania stron wyróżnia następujące rodzaje stron:

Podczas odzyskiwania ramek jądro musi także wziąć pod uwagę, czy strony są współdzielone, czy są używane tylko przez jeden proces (no bo COW lub procesy podmapowują ten sam plik).

Heurystyki stosowane przy zwalnianiu ramek:


Listy LRU - strony aktywne i nieaktywne

Linux utrzymuje dwie listy LRU: active - aktywnych stron i inactive - nieaktywnych stron (osobno w każdej strefie). Podczas procesu postarzania system stara się stwierdzić, poprzez bity w pozycji tablicy stron i bity ramki (page), które strony są najbardziej używane i przesuwa je do listy active.

Jeśli strona należy do listy LRU, to ma ustawioną flagę PG_lru, ponadto jeśli należy do listy aktywnych, to ma ustawioną flagę PG_active, a jeśli do nieaktywnych, to flaga jest zgaszona.

Flaga PG_referenced powoduje, że liczba dostępów do strony przed przesunięciem jej z jednej listy na drugą podwaja się. Jeśli strona nieaktywna, ma zgaszony bit PG_referenced, to przy pierwszym dostępie flaga jest podnoszona, a strona pozostaje na liście. Dopiero przy drugim dostępie, jeśli flaga jest podniesiona, to strona wędruje na listę aktywnych. Analogicznie przy przenoszeniu strony w drugą stronę.

Funkcja page_referenced() wywoływana dla każdej strony przeglądanej przez jądro podczas poszukiwania stron do wymiany, przekazuje 1 jeśli jest ustawiony bit PG_referenced w deskryptorze ramki, w której znajduje się ta strona lub któryś z bitów Accessed w pozycjach tablic stron odpowiadających danej ramce.

W sytuacji braku pamięci, system najpierw próbuje zwolnić pamięć przez odzyskiwanie jej z alokatora płytowego. Jeśli w ten sposób nie da się odzyskać odpowiednio dużo pamięci, to system próbuje ją odzyskać z pamięci podręcznej stron (page cache). Najpierw przegląda strony na liście active, przesuwając te mniej używane na listę inactive. Następnie przegląda listę inactive, synchronizując strony z buforami i próbując zwolnić strony, których nikt nie używa. Jeśli znajdzie takie strony i są one brudne, to inicjuje ich zapis.

Tak czy inaczej strony na listach active i inactive mogą być używane, tzn. mogą być odwzorowane przez jakieś procesy. Jeśli na liście inactive zostanie odnalezionych wiele odwzorowanych stron, to jest wołana funkcja, która usunie odwzorowanie.

Jeśli system nie może zwolnić stron z podręcznej pamięci stron, to próbuje zmniejszyć (ang. shrink) podręczne pamięci systemu plików: inode cache, dentry cache i quota cache.

Wreszcie jeśli system nadal nie jest w stanie odzyskać pamięci, to wybiera jeden aktywny proces i próbuje go zabić, żeby odzyskać jego pamięć.


Sprawdzanie zapotrzebowania na pamięć i kswapd

Funkcja kswapd() wykonuje się jako wątek jądra. Jej zadanie polega na wymianie stron, gdy zajdzie taka potrzeba, czyli gdy liczba wolnych stron w strefie spadnie poniżej pewnego poziomu.

Sprawdzanie zapotrzebowania na pamięć polega na badaniu, czy strefa wymaga przywrócenia równowagi, tzn. czy we wskazanej strefie liczba wolnych stron jest niewiększa niż znacznik zone->pages_high. Flaga oznaczająca konieczność poprawienia stanu wolnych stron jest ustawiana wówczas, gdy liczba wolnych stron jest niewiększa niż znacznik zone->pages_low.

Dla takich stref wywołuje się funkcję, która próbuje zwolnić strony ze wskazanej strefy, w razie potrzeby zwiększając priorytet, który określa determinację, z jaką powinny być zwalniane strony z pamięci każdego rodzaju. Jeśli nie uda się zwolnić tylu stron, ile trzeba, to wywołuje funkcję out_of_memory(), która zabije jakiś proces.


Usuwanie odwzorowania stron procesów

Jeśli w systemie jest dużo odwzorowanych stron na liście inactive, to trzeba rozpocząć usuwanie odwzorowania. Oznacza to, że będą przeglądane tablice stron procesów i sprawdzane wszystkie pozycje w tych tablicach. Na pozycjach, do których nikt ostatnio nie sięgał będą usuwane odwzorowania (unmapped), przy czym strony plików będą rzeczywiście czyszczone, a strony anonimowe będą odwzorowywane na adres w pliku wymiany. W obu przypadkach bit obecności w nowym PTE będzie zgaszony. Zatem proces-właściciel tej pozycji PTE nie będzie mógł się bezpośrednio odwołać do tej strony, lecz będzie powodował błąd braku strony przy każdej przyszłej próbie odwołania.


Urządzenia i pliki wymiany

Urządzenia i pliki wymiany zostały wprowadzone po to, by dostarczyć miejsce na dysku na strony, dla których usunięto odwzorowanie. Są trzy rodzaje stron obsługiwanych przez podsystem wymiany:

Identyfikator wymiecionej strony jest przechowywany w pozycji tablicy stron. Same zera na tej pozycji oznaczają, że strona nie należy do przestrzeni adresowej procesu lub że odpowiednia ramka jeszcze nie została przydzielona procesowi. Jeśli ostatni bit jest równy zero, a pozostałe 31 nie wszystkie są równe zero, to strona jest w podsystemie wymiany. Wpp strona jest w RAM.

Zapis i odczyt stron do/z pamięci pomocniczej odbywa się za pośrednictwem spójnych obszarów na dysku. Informacje o stanie dostępnych urządzeń moduł zarządzający pamięcią przechowuje w tablicy tzw. logicznych urządzeń wymiany swap_info. Maksymalna liczba urządzeń wymiany w systemie to (domyślnie) 32.

Dla każdego urządzenia wymiany pamięta się m.in. dentry (a w nim dowiązanie do i-węzła odpowiadającego mu urządzenia blokowego) oraz mapę bajtową tego urządzenia (swap_map). 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. Ma to na celu zmniejszenie średniego czasu dostępu (dyskowego) do ramki pamięci pomocniczej.

Logiczne urządzenia wymiany są powiązane w listę priorytetową. Upraszczając, przy poszukiwaniu wolnej ramki pamięci pomocniczej najpierw przeszukuje się urządzenia o najniższym priorytecie.

Przy kopiowaniu strony z pamięci głównej do pomocniczej, najpierw znajduje się wolną ramkę na którymś urządzeniu wymiany, a następnie kopiuje się stronę do tej ramki.


Janina Mincer-Daszkiewicz