Pamięć wirtualna w systemie Windows NT


Prezentacja: Projekt realizowany w ramach ćwiczeń z Systemów Operacyjnych 2002/2003


autor: Wojtek Kulik
nr indeksu 189413




Spis treści:

Implementacja pamięci wirtualnej w Windows NT

W Windows NT (od New Technology) każdy proces dysponuje własną przestrzenią adresową.
Aplikacje widzą w systemie 4GB pamięci (wirtualnej). Można to uzyskać stosując 32-bitowe adresy. Górna połówka tej pamięci jest zarezerwowana przez system, reszta może być wykorzystana przez aplikacje. Na większości dzisiejszych komputerów osobistych nie spotyka się pamięci fizycznej o rozmiarze 4GB, tak więc system operacyjny zajmuje się kwestiami adresowania wirtualnego i tłumaczenia adresów wirtualnych na fizyczne. W Windowsie NT te funkcje pełni VMM (Virtual Memory Manager).



Całe programy lub ich części mogą znajdować się w pamięci - w szczególności w pliku wymiany. Nie dotyczy to wszystkich procesów (wątków) - oczywiście VMM, czy wątki jądra nie powinny znaleźć się w pliku wymiany. W obszarze pamięci wirtualnej znajduje się zatem pula "niestronicowana", w której zawarte są wątki jądra i VMM.

System musi wiedzieć, w jaki sposób odzyskać adres fizyczny z danego adresu wirtualnego. W systemie Windows NT realizuje to trzypoziomowa struktura (można ją rozumieć jako B-drzewo). Jej pierwszy poziom to katalog stron (ang. Page Directory). Fizyczny adres katalogu stron znajduje się w rejestrze procesora CR3. Każdy proces w systemie ma swój katalog stron. Katalog stron sam jest stroną. W Windowsie NT strony są wielkości 4KB. Katalog stron zawiera 1024 32-bitowych pozycji, z których każda wskazuje na pewną tablicę stron (ang. Page Table).



Tablica stron także jest stroną, także z 1024 pozycjami. Pozycja w tablicy stron to PTE (ang. Page Table Entry), która wskazuje na ramkę (fizyczną). Ramka jest wielkości 4KB.

Rozmiar całej 3-poziomowej struktury wynosi ok. 4MB (1024*4096+4096=4198400), co stanowi niespełna 0,1% z 4GB - całkiem przyzwoity wynik, biorąc pod uwagę fakt, że "gdzieś" to trzeba pamiętać.

Translacja adresu

Jak zmienić 32-bitowy adres pamięci wirtualnej na adres fizyczny przy użyciu opisanej właśnie struktury? Na początek podzielmy 32-bitowy adres na 3 segmenty: offset katalogu stron, offset tablicy stron i offset strony fizycznej.



10-bitowy offset katalogu stron jest przesuwany w lewo o dwie pozycje (tzn. mnożony przez cztery), tak aby uzyskać podwójne słowo będące adresem w katalogu stron. Zaglądając pod ten adres uzyskujemy korespondującą tablicę stron. Wtedy korzystamy z 10-bitowego offsetu tablicy stron (ponownie mnożonego przez cztery) - uzyskujemy adres ramki pamięci. Ostatnie 12 bitów jest używane do przesunięcia w obrębie ramki.

Pozycja w tablicy stron jest miejscem, gdzie pamiętana jest informacja o statusie strony. Górne pięć bitów jest używane dla bezpieczeństwa - opisują one, czy proces pisał, czytał i czy w ogóle sięgał do tej strony. Następne 20 bitów opisuje fizyczny adres ramki. Kolejne 4 bity specyfikujš plik, który przechowuje stronę, a ostatnie 3 bity są używane do określenia stanu strony (czy strona jest na dysku czy w fizycznej pamięci, czy strona została zmodyfikowana od czasu poprzedniego wczytania, czy w przypadku odwołania do tej strony wystąpi błąd braku strony).



Błędy braku strony

Zawsze gdy ma miejsce odwołanie do strony nie znajdującej się aktualnie w pamięci, występuje błąd braku strony. Wtedy system uruchamia specjalny proces (ang. pager), który wczytuje stronę z dysku do pamięci. Proces pager sprawdza, czy proces, u którego miał miejsce błąd braku strony może przeczytać ten fragment pamięci (np. czy nie próbuje odwołać się do niedozwolonego obszaru?). Jeśli nie ma przeciwwskazań, to proces pager wczytuje stronę i oddaje sterowanie do systemu. Instrukcja, która spowodowała błąd braku strony jest ponawiana (a nawet ma priorytet!).

Instrukcja, która spowodowała błąd braku strony, sprawia, że cały proces wykonuje się wolniej. Mało tego - pojedyncza instrukcja może wywołać więcej niż jeden błąd braku strony. Najgorszy scenariusz to taki, w którym jedna instrukcja spowoduje wczytanie katalogu stron, tablicy stron i ramki pamięci. Taki przypadek może mieć miejsce, gdy np. inne procesy wykorzystały nasz obszar stron pamięci.

Aby współdzielić pamięć, procesy potrzebują wspólnej ramki pomiędzy nimi. W tym przypadku, w Windows NT zostanie zaalokowana struktura PPTE (ang. Prototype Page Table Entry), która wskazuje na współdzielone ramki. Gdy zawartość ramki się zmieni, tylko PPTE dotycząca tej ramki musi zostać zaktualizowana. To oznacza, że istnieje szansa, że pojedyncza instrukcja spowoduje 4 błędy braku strony - czwarty błąd braku strony dotyczyć może właśnie PPTE.



Baza danych stronicowania

Strony w Windowsie NT są podzielone na 8 kategorii: aktywne, w stanie tranzycji, oczekujące, zmodyfikowane, zmodyfikowane bez zapisu, wolne, wyzerowane i złe. Strony aktywne to takie, które mają jeden PTE wskazujący na nie (wczytane z pamięci). Strony w stanie tranzycji, to takie, które jeszcze nie są aktywne, np. wykonywana jest operacja we-wy, która spowoduje ich wczytanie. Strony zmodyfikowane, to takie, które jeszcze (po zmianie ich zawartości) nie zostały zapisane na dysk, itd.

W jaki sposób system przydziela stronę? W momencie gdy proces jest tworzony lub wywoływany nie wszystkie strony są alokowane. W systemie istnieje specjalny proces, który zajmuje się (w tle) sprzątaniem i realizowaniem żądań poszczególnych procesów (sprowadzanie na żądanie, przydzielenie wyzerowanej strony, przydzielenie strony o konkretnej zawartości). Ten proces korzysta z bazy danych stronicowania. Baza danych stronicowania zawiera informacje o wszystkich stronach używanych w systemie.
Poszczególne kategorie stron są połączone w listy, np. w bazie danych stronicowania grupuje się w listy strony, które nie są używane przez żaden proces. Żądanie przydzielenia strony polega na udostępnieniu pierwszej wolnej strony z listy wolnych lub wyzerowanych, ewentualnie usunięcie strony najdłużej rezydującej w strukturze (zgodnie ze strategią FIFO), po czym jej przydzielenie.

Zarządca Pamięci Wirtualnej (Virtual Memory Manager)

W Windowsie NT Zarządca Pamięci Wirtualnej (VMM) jest osobnym procesem - NTOSKRNL.EXE. VMM zarządza bazą danych stronicowania. Zarządca rozporządza 6-ma "służącymi" (wątkami). Poszczególne wątki zajmują się: usuwaniem stron (zgodnie ze strategią FIFO), czytaniem stron z wyprzedzeniem; podpinaniem stosu pod odpowiedni wątek przy przełączaniu kontekstu; zapisywaniem do pliku wymiany; zapisywaniem "brudnych" stron na dysk; kontrolowaniem pliku wymiany i wreszcie zerowaniem stron wolnych. Wszystkie te wątki współpracują z bazą danych stronicowania.



Wydajność

Jak się zachowuje system stronicowania na żądanie w Windowsie NT? Są dwa powody, dla których implementacja zachowuje się nieco lepiej niż w teorii. Po pierwsze, wykorzystanie sprzętowego TLB; po drugie, przełączanie kontekstu.



Przykładowo: na platformie x86 przeciętne przełączenie kontekstu trwa 17ms. Mając do dyspozycji procesor o mocy 5 milionów instrukcji na sekundę (MIPS-ów) i program, którego 30-50% instrukcji to odwołania do pamięci otrzymamy, że przełączenie kontekstu odbywa się co 25500-42500 instrukcji adresowych (patrz: AS/400).

Materiały, na podstawie których powstała niniejsza prezentacja

Powrót do strony głównej