Do spisu tresci tematu 4

4.1.2 Stronicowanie




Spis tresci

Wprowadzenie

Linux jest systemem za stronicowaniem, czyli podzialem pamieci na bloki ustalonego rozmiaru oraz odwolywanie sie do nich nie bezposrednio, lecz poprzez tablice tlumaczace (mapujace??) (ang: page mapping). Pozwala to na sprawniejsze zarzadzanie pamiecia. Nie wystepuje fragmentacja zewnetrzna. Znacznie ulatwiona jest wymiana stron, czyli ich zwalnianie przy braku miejsca w pamieci fizycznej oraz wczytywanie. Niemozliwa jest implementacja tego mechanizmu bez wsparcia sprzetowego.

W dalszej czesci opisu bede uzywal pojecia strona na okreslenie bloku pamieci widzianego przez proces do ktorego odwoluje sie on przez mechanizm tlumaczenia adresu na jego fizyczne polozenie w pamieci. Blok o tym samym rozmiarze w pamieci fizycznej jest nazywany ramka. Adres liniowy jest to adres z ciaglej przestrzeni adresowej procesu uzyskany w procesie segmentacji

Struktury danych


Wprowadzenie

Rozmiar strony/ramki definiowany jest w pliku asm/page.h. Podkatalog asm w kodzie źródłowym linuxa skrótem (soft-link) do katalogu dotyczącego procesora na który kompilowane jest jądro, np. asm-i386, asm-mips czy asm-alpha. Automatycznie więc definicje dotyczące stronicowania będą odpowiadać wybranemu procesorowi. W przypadku procesora i386 i wyższych jest to 4kB = 4096 bajtow ustalone na sztywno (procesor nie ma możliwości ustalenia innej wielkości strony). Funkcja kmalloc umożliwia obsługę pamięci dla rozmiarów strony 4 i 8kB. W efekcie bez dopisywania kodu mozna uzywac tych rozmiarow ramek. Mniejsze byc nie moga z powodu sposobu przechowywania informacji w pozycjach tablicy stron. Natomiast wieksze mozna probowac zaimplementować.

Organizacja katalogow jadra i uzytkownika

Proces uzytkownika widzi (przez segmenty) spojna przestrzen adresowa 0-4 GB. Gorny gigabajt (3-4GB) jest widoczny tylko w trybie jadra. W trybie uzytkownika dane sa rozmieszczane w zakresie 0-3GB. Taka organizacja ustalana jest w pliku arch/i386/kernel/head.S (asembler). Tam tez tworzony jest katalog stron jadra (swapper_pg_dir) i ustawiany jest pierwszy wpis w tym katalogu, który odwzorowuje pierwsze 4MB pamieci identycznosciowo. Jadro tworzy sobie specjalny katalog BAD_PAGE uzywany tylko przy bledach braku strony, kiedy brak jest pamieci fizycznej i dyskowej. Poprzednie wersje systemu konczyly proces w trybie jadra, co moglo powodowac niezwalnianie pamieci uzytkownika. W dalszej fazie inicjacji swapper_pg_dir zostaje rozszerzony identycznosciowo na cala pamiec fizyczna. Fizyczna strona zerowa zostaje wyzerowana i nigdy nie jest potem zapisywana. Rowniez dla jadra zostaje zabezpieczona przed zapisem, aby wykryc odwolania przez wskaznik NULL.

Adresowanie pamieci

Sposob organizacji tablic sluzacych do stronicowania jest w Linuxie bardzo podobny do organizacji adresowania pamieci przez procesory Intela (powyzej 386, w trybie wirtualnym). Ponizszy rysunek ilustruje ten proces.

tu jest rysunek adresowania pamieci przez Intela

Kazdy proces ma swoj wlasny katalog tablic stron. (Rozmiaru jednej ramki - tak, jak i tablica stron). Wskaznik do niego znajduje sie w strukturze mm_struct pod nazwa pgd. Przy zmianie kontekstu Linux dba o to by zaladowac odpowiedni rejestr procesora jego wartoscia. Przesuniecie w adresie liniowym jest rownoczesnie przesunieciem wzgledem poczatku wyznaczonej ramki. Nie wymaga to chyba specjalnych wyjasnien. Procesor Intela znajduje adres danej strony przez wskaznik podwojnie posredni. Linux implementuje organizacje tablic zawierajacych adresy ramek trojpoziomowo. Poprzez odpowiednie dyrektywy #define srodkowa tablica jest traktowana jako pojedynczy wpis w katalogu tablic stron. W tej sytuacji procedury dotyczace srodkowych tablic czesto tylko wywoluja te dotyczace tablic trzeciego poziomu w petli while wykonujacej zawsze jeden obrot.
Nie wystarczy jednak zmienic stale, aby system mogl dzialac na procesorze o potrojnie posrednim odwolaniu do pamieci, poniewaz wiele procedur zaklada, ze srodkowe tablice nie istnieja. Np. funkcja alokujaca pamiec na ta tablice jest pusta.

Tablice stron

Ostatnia tablica stron (czyli posrednia w Linuxie jako trzecia) zawiera adresy ramek (o ile sa rezydentne w pamieci). Poniewaz adres ramki jest wielokrotnoscia 4kB to najmlodsze 12 bitow sa zawsze zerami. Linux wykorzystuje 7 z nich do przechowywania dodatkowych informacji o stronie.
Pola adres sa jednobajtowe, najmlodsze z nich ma 4 najmlodsze bity zerowe. Duzymi literami oznaczone sa bity informacyjne strony. Maja one dokladnie te same nazwy i uklad, co bity obslugiwane sprzetowo w procesorze Intel.

Element tablicy stron
 adres   adres   adres  4M DIRTY ACCESSED PCD PWT USER RW PRESENT=1

Opis poszczegolnych bitow:

PRESENT
Kiedy procesor odwoluje sie do danej strony i bit ten jest ustawiony na 1 oznacza to, ze ramka znajduje sie w pamieci. Pola adres zawieraja wtedy prawidlowy adres ramki w pamieci fizycznej. Jesli przy odwolaniu do pamieci bit ten jest rowny zero, to nastepuje blad braku strony, a wszystkie pozostale bity maja inne znaczenie zwiazane z obsluga bledu.

RW
Ustawiony na 1 oznacza pozwolenie na zapis na danej stronie. Na danej stronie mozna zapisac jesli zezwala na to mechanizm segmentacji. Bit ten sluzy do organizacji wspoldzielenia stron. Ustawiony na 1 pozwala na zapis bezposredni na strone, a gdy jest rowny zero, to przy zapisie wywolywany jest blad ochrony strony.

Bit mowiacy o poziomie ochrony: uzytkowy/systemowy.

PWT
Niezdefiniowany w Linuxie 2.x (ang. Page Write Through - obsluga sprzetowej pamieci podrecznej)

PCD
Nieuzywany w Linuxie 2.x (ang. Page Cache Disable - obsluga sprzetowej pamieci podrecznej)

ACCESSED
Linux zaklada, ze bit ten jest sprzetowo ustawiany na jeden w momencie odwolania do strony i wykorzystuje ten fakt do postarzania ramek. Postarzanie jest opisane przy wyrzucaniu ramek na dysk.

DIRTY
Ustawiany sprzetowo na 1 przy zapisie na strone. Ulatwia wymiane stron.

4M
Oznacza rozmiar ramki wielkosci 4MB. Jedyne wykorzystanie: jesli kompilujemy na Pentium to segment jadra odwzorowujacy identycznosciowo pamiec liniowa na fizyczna jest skladany recznie z takich ramek.
Ponadto caly element tablicy stron moze miec wartosc 0. Linux zaklada, ze odwolujac sie do takiej strony procesor wywoluje procedure obslugi bledu braku strony. Linux przydziela fizyczna ramke procesowi dopiero w momencie odwolania sie do niej. Zero jest poczatkowa wartoscia na jaka ustawiane sa zwykle wpisy w katalogu i tablicach stron. (Patrz opis new_page_tables )

Implementacja operacji na pamieci


Wprowadzenie

Zadna operacja dotyczaca tablic stron nie jest udostepniana przez funkcje systemowa. Procedury operujace na tych tablicach sa wywolywane tylko przez inne czesci jadra i wykonuja one kilka sprawdzen oraz robia proste rzeczy typu: zmiana bitow w pozycji tablicy stron w danym zakresie, kopiowanie tablic (potrzebne do fork) odwzorowywanie pamieci w dany obszar, zwalnianie tablic. Kod Linuxa obsluguje tez przy tych operacjach pamiec podreczna procesora, wychodzac z zalozenia, ze system operacyjny moze w duzym stopniu przewidywac przyszle uzycie danej ramki. Na Intelu wlasciwosc ta jest niewykorzystywana.

Do wazniejszych funkcji operujacych na pamieci logicznej naleza:


Funkcja get_empty_page()

Interesujaca ciekawostka na temat Linuxa jest fakt, ze alokujac nowa pamiec dla procesu jadro dokonuje tego tylko logicznie - poprzez wpisy w tablicy stron i tablicy segmentow. Dla jadra natomiast pamiec alokowana jest od razu - znajdowana jest ramka w pamieci fizycznej. System nie wierzy uzytkownikowi i stara sie optymalizowac jego ewentualne nadmierne zadania.

Myli sie jednak ten kto sadzi, ze opisze tutaj sposob alokowania pamieci. Alokowanie pamieci dla procesu odbywa sie przez rozszerzenie segmentu, co jest opisane w dokumencie o sys_brk. Natomiast uzyskiwanie pamieci fizycznej jest realizowane w systemie zarzadzania ramkami

O funkcji get_empty_page powiem tyle, ze uzyskuje ramke od wyzej wymienionego modulu zeruje ja i zwraca jej adres fizyczny. Stad wniosek, ze program dostaje nowa pamiec wyzerowana.

Funkcja new_page_tables()

Tworzy nowy katalog stron, czyli dostaje ramke, wypelnia ja zerami a przestrzen 3-4 GB odwzorowuje na pamiec jadra. (Po prostu przepisujac wpisy z katalogu swapper_pg_dir) Zera w katalogu stron oraz w tablicy stron, jak juz wczesniej wspomnialem, sa traktowane jako strona alokowana przy pierwszym dostepie. Gorny gigabajt jest przy przepisywaniu ustawiany na systemowy (bit USER).

Bibliografia

  1. Pliki zrodlowe Linuxa:
  2. Kernel Hacker's Guide Czesc dotyczaca pamieci.
    Uwaga: mozna to przeczytac tylko jako wstep, poniewaz opisuje starsze wersje Linuxa i daje dobre ogolne wyobrazenie, natomiast zawiera nieaktualne dane.
  3. Ryszard Goczynski, Michal Tuszynski, Mikroprocesory 80286, 80386 i i486, HELP 1991

Pytania i odpowiedzi

1. Ile pamieci moge sobie maksymalnie zazyczyc w swoim programie ?

Na pewno ograniczeniem nie jest tu stronicowanie. Ono ustala limit na jeden proces rzedu 3GB. O to aby proces nie mogl dostac wiecej niz trzeba dba procedura sys_brk.

2. Jak to jest na procesorach, ktore nie robia tylu rzeczy sprzetowo ?

Linux nieprzypadkowo ma wiele operacji zdefiniowanych przez dyrektywy #define. Dla Intela zdarzaja sie dyrektywy puste, ktore w przypadku innych architektur wykonuja niewielki kawalek kodu w asemblerze np: zaznaczajacy bit uzycia strony. Procedury na wyzszym poziomie nie musza wiedziec jak sa zaznaczane odpowiednie bity. Jest jednak pewien zasob czynnosci, ktore procesor musi umiec wykonywac np:adresowanie pamieci przez tablice stron, ochrona pamieci nieprzydzielonej oraz dzielonej do odczytu.

Autor: Andrzej Topolewski