Podręcznik

Praktycznym rozwiązaniem problemu przedstawionego w poprzednim rozdziale jest stronicowanie pamięci. W rozwiązaniu tym pamięć logiczna (adresowana przez procesor) jest podzielona na strony (Rys. 6). Z kolei pamięć fizyczna (RAM) jest podzielona na ramki o takim samym rozmiarze. Pewien proces działający w pamięci logicznej zajmuje konkretną liczbę ramek (tu 4). Ramki mogą być umieszczone w dowolnych stronach pamięci RAM. Odwzorowanie stron w ramki jest opisane w tablicy stron. Zwykle każdy proces ma taką swoją tablicę. Indeks (numer komórki) w tablicy stron oznacza numer strony, natomiast zawartość komórki oznacza odpowiadającą stronie ramkę. Więc strona 0 znajduje się w ramce 2, strona 1 w ramce 7 itd. Przy takim odwzorowaniu proces, który ma ciągłą przestrzeń adresową w pamięci logicznej, może być dowolnie porozrzucany do różnych ramek w pamięci RAM. Nie występuje tu fragmentacja zewnętrzna. Natomiast może wystąpić fragmentacja wewnętrzna. Nie można procesowi przydzielić ułamka ramki. Więc jedna ramka może nie być w pełni wykorzystana. Fragmentacja wewnętrzna jest jednak niewielkim problemem w porównaniu z fragmentacją zewnętrzną.

Rys. 6. Model stronicowania pamięci

Stronicowanie powoduje straty czasowe w dostępie do pamięci. Można zauważyć, że tablica stron jest strukturą tworzoną również w pamięci RAM. Każdy dostęp do pamięci powoduje konieczność odwołania się do tej tablicy. Zatem dostęp do pamięci wymaga dwóch odwołań do pamięci. Powoduje to dwukrotne wydłużenie czasu dostępu do pamięci, co w ogromnej większości przypadków jest nieakceptowalne. W celu wyeliminowania tego wydłużenia dostępu do pamięci stosuje się buforowanie najczęściej używanych stron z całej tablicy stron (Rys. 7). Są to tzw. bufory TLB (ang. Transaction Lookaside Buffers). Tablice stron są najczęściej tworzone dla poszczególnych procesów. W momencie wykonywania procesu ładowana jest jego tablica stron. Te strony, do których są odwołania, są zapisywane w rejestrach TLB. Powtórne odwołanie do strony jest realizowane bardzo szybko, jako że kojarzenie stron z buforów TLB zachodzi w jednym takcie zegara. Również dostęp do nich jest niemal natychmiastowy. Wadą tego rozwiązania jest dość duży koszt.
Ponieważ każdy proces ma swoją tablicę stron, jest ich stosunkowo dużo. W systemie 32 bitowym logiczna przestrzeń adresowa wynosi 4 GB. Strony i ramki dla procesów są zazwyczaj 4 kB. Potrzeba zatem milion wpisów w tablicy stron, aby opisać tą przestrzeń. Jeden wpis w tablicy stron zajmuje 4 B. Rozmiar tablicy stron wynosiłby więc 4 MB na proces. To dużo biorąc pod uwagą, że proces zwykle wykorzystuje mały ułamek pełnej logicznej przestrzeni adresowej. Rozwiązaniem tego problemu jest wielopoziomowa tablica stron. W 32 bitowym systemie stosuje się dwupoziomową tablicę stron (Rys. 8). Sama tablica stron jest podzielona na mniejsze fragmenty. Fragmenty te (ich położenie) jest opisywane przez zewnętrzną tablicę stron. Mamy więc dwie struktury w pamięci RAM. Jednak gdy proces wykorzystuje tylko niewielki fragment pamięci, tworzona jest zewnętrzna tablica stron i tylko te elementy tablicy stron, które są wykorzystywane. Daje to dużą oszczędność w zużyciu pamięci. Jednak teraz dostęp do danych wymaga aż trzech dostępów do pamięci. W tym przypadku bufory TLB są już niezbędne. W systemach 64 bitowych tablica stron jest aż pięcio-poziomowa. 

Rys. 7. Sprzęt stronicujący z buforami TLB
 
Rys. 8. Dwupoziomowa tablica stron