Implementacja pamięci wirtualnej w systemie Microsoft Windows NT

Arkadiusz Piwowarski

Grudzień 2002 r.

Ostatnia modyfikacja: 11 grudnia 2002 r.

Przestrzeń adresowa

System Windows NT wymaga od sprzętu by udostępniał 32-bitową szynę danych, tak by można było zaadresować do 4GB pamięci fizycznej. Pamięć ta jest udostępniana procesom poprzez adresowanie wirtualne, które umożliwia każdemu procesowi pełne wykorzystanie przestrzeni 4GB, niezależnie jak i ile pamięci używają pozostałe procesy.

Istnieje podział pamięci wirtualnej na część dostępną dla procesu i część zarezerwowaną przez system. W części systemowej znajdują się procedury i dane wykorzystywane przez system wspólne dla wszystkich procesów. Na część systemową są zarezerwowane górne 2GB. W nowszych systemach takich jak Windows 2000 Adwanced Server i Windows NT Server 4.0, Enterprise Edition, dla systemu jest zarezerwowane już tylko 1GB.

Adres wirtualny a pamięć fizyczna

Pamięć fizyczna podzielona jest na ramki wielkości 4KB (Page Frames). Podobnie przestrzeń adresowa każdego procesu osobno jest podzielona na strony wielkości 4KB. Strona pamięci procesu może być utożsamiona (przez system operacyjny) z dowolną ramką pamięci. Informacja o tym, jak pamięć jest podzielona na ramki, jest jednak przed procesami ukryta. Proces ma dostęp do swej przestrzeni adresowej za pomocą liniowego adresu wirtualnego. Dany adres wirtualny może oznaczać zupełnie inny adres fizyczny pamięci.

W systemie Windows NT jest utworzona osobno dla każdego procesu struktura danych (rysunek 1), która przechowuje informację, o tym jak zamienić adres wirtualny na adres fizyczny. Struktura ta odwzorowuje każdą stronę pamięci procesu w odpowiednią ramkę pamięci fizycznej. W obrębie ramki prosta arytmetyka pozwala już wybrać dla adresu wirtualnego pasujący adres fizyczny.

Katalog stron i tablice stron

Do przypisania każdej stronie pamięci odpowiedniej ramki służy tablica stron (Page Table). Każda komórka tablicy ma rozmiar 32 bitów (4 bajty), tak że mieści nr ramki pamięci (20 bitów) i pewne dodatkowe informacje.

Rysunek 1. Struktura danych używanych do tłumaczenia adresu wirtualnego na adres fizyczny

Ponieważ jedna tablica musi zmieścić się w jednej stronie pamięci (4KB), może zawierać informację o 1024 ramkach (1024 * 4 bajty = 4KB). Aby zamapować w ten sposób 4GB pamięci, potrzebne jest 1024 tablic. Do przechowania adresów każdej z tych tablic służy katalog (Page Directory). Zawiera on 1024 pola 4-bajtowe opisujące strony z tablicami (każde pole wskazuje na ramkę z zawartością odpowiedniej tablicy), daje to razem 4KB. Zatem katalog mieści się już w jednej stronie pamięci.

Tłumaczenie adresu wirtualnego na adres fizyczny

Adres pamięci w systemie Windows NT ma rozmiar 32 bitów. Adres wirtualny ma również 32 bity, przy czym trzeba pamiętać, iż są one tylko zbiorem informacji służącej do uzyskania adresu fizycznego. Informacja ta rozdzielona jest między trzy grupy bitów, jak na rysunku 2.

Rysunek 2. Interpretacja informacji zawartej w adresie wirtualnym

Pierwsza grupa to najstarsze 10 bitów adresu wirtualnego. Wyznacza ona indeks w katalogu stron. Pole o tym indeksie wskazuje adres właściwej tablicy stron.

Druga grupa to kolejne (środkowe) 10 bitów adresu wirtualnego. Wyznacza ona indeks w tablicy stron. Pole o tym indeksie przechowuje informację o danej stronie pamięci procesu i odpowiadającej jej ramce pamięci fizycznej.

Do wskazania fizycznego adresu w odszukanej ramce pamięci służy trzecia grupa bitów, składająca się z pozostałych (najmłodszych) 12 bitów adresu wirtualnego. Stanowią one przesunięcie względem początku ramki pamięci.

Rysunek 3. Obliczanie adresu liniowego na podstawie adresu wirtualnego

Bufor asocjacyjny - TLB

System Windows NT dla często wywoływanych adresów korzysta z wsparcia jakie daje sprzęt komputerowy i wykorzystuje bufor asocjacyjny TLB (Translation Lookaside Buffers). Każde pole TLB zawiera adres (nr) wirtualnej strony i odpowiadające jej pole z tablicy stron.

Pozwala to na ominięcie dwóch odczytów z pamięci (z katalogu stron, a potem z tablicy stron) i odczytanie tej samej co w polu tablicy stron informacji z dużo większą prędkością.

Bufor TLB ma ograniczenie (32 pola) i gdy zostanie wywołana strona, której nie ma w TLB, musi zostać wykonany wcześniejszy algorytm, zanim informacja o stronie znajdzie się w TLB. Jednak dzięki temu, iż w TLB jest trzymana informacja o stronie pamięci, jedno pole pozwala na obsługę do 4096 adresów, więc taka wymiana zdarza się stosunkowo rzadko. Dzięki temu jest to bardzo efektywny mechanizm.

Struktura pola opisu strony

Pole opisujące stronę pamięci (PTE - Page Table Entry) zawiera informację o numerze odpowiadającej ramki pamięci, prawach dostępu, pliku wymiany, oraz stanie odpowiedniej strony pamięci. Informacja ta mieści się w 32 bitach pola, jak na rysunku 4.

Rysunek 4. Struktura pola opisu strony (PTE)

Najstarsze 5 bitów pola określa prawa dostępu, takie jak dostęp do strony w trybie tylko do odczytu, dostęp do strony w trybie do zapisu i odczytu, lub brak dostępu do strony.

Kolejne 20 bitów określa nr ramki pamięci w której znajduje się strona. Pozwala to na ponumerowanie 1024 * 1024 ramek po 4KB co daje w sumie 4GB, czyli całą dostępną pamięć.

Następne 4 bity określają jeden z 16 plików stron.

Ostatnie (najmłodsze) 3 bity określają stan strony. Są to najważniejsze bity z punktu widzenia menadżera pamięci. Najstarszy z tych bitów określa czy strona jest w stanie przejściowym (T - Transition). Kolejny określa czy strona była modyfikowania i jeszcze nie zapisana (D - Dirty). Najmłodszy określa czy strona znajduje się w pamięci (P - Present).

Współdzielenie pamięci

Mechanizm adresowania wirtualnego umożliwia przypisanie dwóm (lub więcej) adresom wirtualnym jednego adresu fizycznego. Jednak proste przypisanie adresu tej samej ramki do różnych pól tablic stron spowodowałoby redundancję dodatkowych informacji. W przypadku zmiany stanu współdzielonej strony pamięci, trzeba by odszukać i aktualizować wszystkie pola w tablicach, które wskazują na ramkę z tą stroną.

Projektanci systemu Windows NT, chcąc uniknąć narzutu związanego z taką operacją, wprowadzili prototypowe pola opisujące współdzielone strony (Prototype Page Table Entry). Pola te są tworzone po jednym dla każdej współdzielonej strony pamięci. Informacje o współdzielonej stronie pamięci są w ten sposób trzymane w jednym miejscu. Procesy dołączają współdzieloną stronę pamięci do swojej przestrzeni adresowej poprzez wskazanie w odpowiednim polu tablicy na prototypowe pole współdzielonej strony.

Rysunek 5. Realizacja pamięci współdzielonej za pomocą prototypu pola tablicy opisu strony

Nieudane odwołania do stron

Przy odwoływaniu do pamięci może wystąpić błąd odwołania (Page Fault). Błąd ten może mieć dwa powody:

1. Proces naruszył uprawnienia danej strony, lub strona, do której się odwołał, nie należała do jego przestrzeni adresowej. W tym przypadku powodem jest błędne działanie programu i system zgłosi błąd naruszenia ochrony pamięci, oraz usunie proces.
2. Proces odwołał się do strony która aktualnie nie znajdowała się w pamięci. W tym przypadku system uruchomi procedurę załadowania odpowiedniej strony do pamięci i powtórzy ostatnią operację procesu.

Tablice i katalog również znajdują się w stronach pamięci, które mogą być zrzucone na dysk (informacja o tym znajduje się strukturze pola opisującego odpowiednią stronę i jej ramkę pamięci). Przy odwołaniu do pamięci mogą zatem wystąpić nawet 3 nieudane odwołania, kiedy w pamięci nie ma katalogu stron, odpowiedniej tablicy stron i szukanej strony pamięci. (W przypadku współdzielonej strony może jeszcze nie być strony z prototypem pola tablicy, co daje maksymalną liczbę 4 nieudanych odwołań)

Sytuacja ta jest łagodzona przez mechanizm bufora asocjacyjnego. Jeśli adres wirtualny znajduje się w TLB, może wtedy nie być w pamięci tablic prowadzących do opisu strony, ale ponieważ informacja o niej jest w TLB, cały koszt ograniczy się do ewentualnego załadowania do pamięci właściwej strony.

Menadżer pamięci

W systemie Windows NT istnieje dedykowany proces menadżera pamięci (Virtual-Memory Manager). Odpowiada on za operacje związane z obsługą mechanizmu pamięci wirtualnej, jego wydajne działanie i optymalną wymianę stron pamięci znajdujących się na dysku z tymi znajdującymi się w pamięci fizycznej komputera.

Baza danych stron-ramek

Menadżer pamięci korzysta z dedykowanej bazy danych stron-ramek (Page-Frame Database). Baza ta przechowuje informacje o wszystkich ramkach pamięci fizycznej. Informacje przechowywane w bazie dotyczą stanu ramki pamięci, ewentualnej strony znajdującej się w tej ramce i dodatkowych danych o tej stronie. Jeśli ramka zawiera stronę pamięci to informacja o ramce jest powiązana z informacją o stronie (w obie strony), jak na rysunku 6.

Rysunek 6. Powiązanie informacji w bazie danych stron-ramek

Ramki są pogrupowane w zbiory (listy) ramek o tym samym stanie. Każda ramka może przyjmować następujące stany:

Prawidłowa	Strona znajduje się w pamięci - jest w użyciu. W jej polu opisu (PTE) jest oznaczona jako prawidłowa.
Zmodyfikowana	Srona zmodyfikowana, lecz jeszcze nie zapisana na dysk. W PTE oznaczona jako nieprawdłowa zmieniona w stanie przejściowym.
Uśpiona	Ramka z przypisaną stroną oczekująca na przejście do zbioru wolnych ramek. Strona w PTE oznaczona jako nieprawidłowa w stanie przejściowym.
Wolna	Ramka nie przypisana do żadnego procesu. Może być użyta w trybie tylko do odczytu.
Wyzerowana	Ramka z wyzerowaną zawartością, która może być natychmiast przypisana do dowolnego procesu (zarówno do odczytu jak i do zapisu).
Uszkodzona	Ramka zawierająca uszkodzony obszar pamięci. Nie będzie użyta przez żaden proces.

Cykl zmiany stanów ramki pamięci fizycznej

Kiedy proces używa ramkę pamięci, ramka ta zawiera odpowiednią stronę i jest w zbiorze prawidłowych ramek. W odpowiednim czasie ramka jest wyłączana ze zbioru prawidłowych ramek, by, po ewentualnym zapisaniu na dysk, stać się dostępna do użycia przez byćmoże inny proces.

Po wyłączeniu ramki ze zbioru prawidłowych ramek, przechodzi, zależnie od stanu zawartej strony pamięci, albo do zbioru ramek zmodyfikowanych, albo do uśpionych.

Ramka zmodyfikowana, czeka na jej zapisanie na dysk, po czym przechodzi w stan uśpienia.

Kiedy ramka jest wyłączona ze zbioru aktywnych ramek, ale jeszcze nie została dołączona do zbioru wolnych ramek (znajduje się w zbiorze uśpionych lub zmodyfikowanych), nadal posiada odpowiadające PTE i całą stronę w nienaruszonym stanie. Jeśli w tym momencie proces ponownie zarząda załadowania tej strony, to wystarczy przywrócić ją do zbioru prawidłowych stron i przywrócić stan PTE, bez czasochłonnego ładowania strony z dysku.

Ramki w stanie uśpienia są stopniowo przenoszone do zbioru wolnych ramek. Od tego momentu magą być użyte przez dowolny proces w trybie tylko do odczytu (Jej zawartość przy takim wywołaniu i tak zostanie nadpisana).

Z czasem ramki ze zbioru wolnych ramek są zerowane i przenoszone do zbioru wyzerowanych ramek. Z tego zbioru mogą być następnie pobierane przez dla dowolnego procesu w dowolnym celu.

Proces menadżera pamięci

W systemie Windows NT menadżerem pamięci jest osobny proces (znajdujący się pliku NTOSKRNL.EXE). Ze względu na kluczowy dla wydajności systemu rodzaj czynności przezeń wykonywanych, zajmuje on w pamięci obszar ramek nie poddawanych wymianie na dysk (nonpaged pool). Proces ten pracuje cały czas w trybie jądra i jego 6 wątków wypełnia wszystkie operacje zarządzające pamięcią i bazą danych stron-ramek.

Wyróżnia się następujące wątki i ich role:

• Balance set manager - zarządca zbiorów ramek.
  Monitoruje i wyznacza pracę dla pozostałych wątków.
  Dba o odpowiednie ograniczanie zbioru aktywnych/prawidłowych ramek, zmniejszając ich ilość tak, by było trochę ramek gotowych do zaalokowania. Pilnuje prawidłowego datowania stron, tak by były prawidłowo wymieniane na dysk. Do wyboru ramki do wymiany stosuje algorytm oparty na kolejce FIFO, gdzie kolejność określa wiek ramki - zrzuca na dysk najstarszą ramkę.
  Stara się też zminimalizować liczbę nieudanych odwołań do pamięci, ładując do pamięci kilka kolejnych stron, kiedykolwiek zdarzy się nieudane odwołanie.
  Wymusza także działanie na wątku zapisującym zmodyfikowane strony, kiedykolwiek nie ma wolnych ani wyzerowanych stron, a są zmodyfikowane strony.
• Process stack swapper - wątek wymiany stosów.
  Odpowiada za zrzucenie na dysk starego stosu i załadowanie do pamięci stosu procesu (wątku) który będzie wykonywany. Operacja ta wykonywana jest przy zmianie contextu, tak by stos nowego procesu był już gotowy do użycia.
• Modified page writer - wątek zapisu zmodyfikowanych stron.
  Kontroluje zapisywanie zmienionych stron do ich plików wymiany. Jest budzony do działania, gdy trzeba zmniejszyć listę zmodyfikowanych stron, na konto listy wolnych ramek pamięci.
• Mapped page writer - zapasowy wątek zapisu zmodyfikowanych stron.
  Jest wywoływany, gdy wątek zapisu zmodyfikowanych stron spowoduje nieudane odwołanie do pamięci w momencie gdy miał zwolnić strony dla zarządcy zbiorów ramek. Zapisuje zmodyfikowane zamapowane pliki na dysk. Ma on za zadanie uchronić system przed blokadą.
• Dereference segment thread
  Kontroluje systemową pamięć podręczną i zarządza zwiększaniem pliku wymiany w miarę potrzeby.
• Zero thread - wątek zerujący.
  Ma za zadanie zerować wolne ramki pamięci, by mogły być przeniesione do zbioru wyzerowanych ramek. Jest wywoływany tylko wtedy, gdy jest to niezbędne i nic innego nie jest robione.

Rezerwacja pamięci

Menadżer pamięci zarządza informacją nie tylko o wszystkich ramkach pamięci, ale też o przestrzeni adresowej każdego procesu, oraz dostępnej pamięci w systemie. Jedną z funkcji jaką udostępnia do wykorzystania przez aplikacje jest rezerwacja pamięci.

Proces może zarezerwować pewien obszar w swojej przestrzeni adresowej, bez alokowania tej pamięci, mając na uwadze puźniejsze potrzeby. Ma to na celu zapewnienie procesowi możliwości zaalokowania tej pamięci w puźniejszym czasie.

Rezerwacja pamięci nie wymaga zmian w aktualnym zbiorze aktywnych stron, ani wymiany rezydującej w pamięci rzestrzeni adresowej pozostałych procesów.

Optymalizacja przez kopiowanie przy zapisie (Copy-on-Write)

Aplikacje systemu Windows mogą korzystać ze wspólnych zasobów takich jak biblioteki dll. Załóżmy, że dwie aplikacje korzystają z tej samej biblioteki. System Windows NT dopuki jest to możliwe nie tworzy drugiej kopii tego obszaru. Procesy współdzielą pamięć z zawartością wspólnego zasobu (np. biblioteki dll) do momentu gdy jeden z nich nie zechce zapisywać do tego obszaru. W tym momencie system kopiuje współdzielony obszar i zmienia mapowanie tego procesu tak, by wskazywało na skopiowany obszar. Drugi proces nie wie jakie zmiany wprowadził ten proces.

Rysunek 7. Procesy 1 i 2 wspólnie wykorzystują ramki A, B, C. Proces jeden chciał zapisać coś do B. Zasób B został skopiowany do ramki D i dopiero po tym proces 1 dokonuje zapisu.

System Windows NT oszczędza w ten sposób na tych zasobach, do których procesy ostatecznie nie wykonają zapisu. Oszczędza również, jeśli z pośród kilku procesów tylko część dokona zapisu do takiego obszaru.

Literatura

1. The Virtual-Memory Manager in Windows NT
   http://msdn.microsoft.com/library/en-us/dngenlib/html/msdn_ntvmm.asp
   Summary: Randy Kath Microsoft Developer Network Technology Group
   Created: December 21, 1992
   Abstract: This article provides an in-depth survey of the memory management system in Windows NT?. Specifically, these topics are explored in detail: Virtual memory
   Category = MSDN: MSDN - library

2. Virtual Memory: Windows NT Implementation
   http://www.mimuw.edu.pl/~janowski/VMpapers/buyssej-Term.pdf
   Submited By: Jacob Buysse
   Submited To: Dr. Barnicki
   Submited On: January 27, 2000

3. Memory Support and Windows Operating Systems
   http://www.microsoft.com/hwdev/platform/server/pae/paemem.asp
   Summary: Describes memory support under Microsoft Windows operating systems.
   Category = Developer Resources: hwdev

4. Virtual Memory Functions
   http://msdn.microsoft.com/library/en-us/memory/base/virtual_memory_functions.asp
   Summary: The virtual memory functions enable a process to manipulate or determine the status of pages in its virtual address space. They can perform the following operations: Reserve a range of a process's virtual address space. Reserving address space does
   Category = MSDN: MSDN - library

5. Memory Protection
   http://msdn.microsoft.com/library/en-us/memory/base/memory_protection.asp
   Summary: Memory that belongs to a process is implicitly protected by its private virtual address space. In addition, Windows provides memory protection using the virtual memory hardware. The implementation of this protection varies with the processor. For
   Category = MSDN: MSDN - library

Rysunki cytowane z [1] i [5].