Każdy proces może działać w dwóch trybach. W trybie użytkownika proces wykonuje kod programu użytkownika, w trybie jądra -- kod jądra (systemu operacyjnego). W trybie jądra proces ma dostęp do wszystkich zasobów komputera, w trybie użytkownika tylko do tych, które zostaną mu przyznane przez jądro systemu operacyjnego. Proces działający w trybie użytkownika nie może mieć dostępu do struktur danych jądra, zatem przestrzeń adresowa w trybie użytkownika musi różnić się od przestrzeni adresowej w trybie jądra.
Istotnym wymaganiem jest też żądanie, aby procesy nie zakłócały nawzajem swojego działania. Z tego powodu przestrzenie adresowe procesów muszą być rozłączne. Uzyskuje się to m. in. dzięki mechanizmowi pamięci wirtualnej: adres wirtualny jest dla każdego procesu tłumaczony na adres fizyczny w pamięci operacyjnej, przy czym każdy proces ma przydzielone inne adresy fizyczne.15.4 W Linuksie każdy proces w trybie użytkownika ma inną przestrzeń adresową, natomiast przestrzeń adresowa w trybie jądra jest taka sama dla wszystkich procesów.15.5
Rozmiar przestrzeni adresowej jest zwykle dużo większy niż rozmiar pamięci operacyjnej (np. dla x86 -- 4GB, bowiem adresy są 32-bitowe), przez co nie wszystkie adresy wirtualne są prawidłowe. Prawidłowe adresy wirtualne należą do tzw. obszarów pamięci procesu. Prawidłowość adresu wirtualnego w trybie użytkownika jest sprawdzana sprzętowo.
Rozłączne przestrzenie adresowe w trybie użytkownika i w trybie jądra powodują, że wymiana danych między tymi przestrzeniami wymaga pewnych dodatkowych zabiegów, np. zapis z przestrzeni jądra pod wskazany adres wirtualny w przestrzeni adresowej użytkownika wiąże się ze sprawdzeniem, czy adres ten jest prawidłowy. Sprawdzenie to nie może się odbywać sprzętowo, gdyż proces działa w przestrzeni adresowej trybu jądra, a sprawdzić należy wskaźnik w przestrzeni adresowej trybu użytkownika.15.6 Aby sprawdzić adres, należy odszukać obszar, do którego on należy. Za znalezienie obszaru jest odpowiedzialna funkcja find_vma().
Struktury danych jądra opisują dla każdego procesu zbiór jego obszarów w przestrzeni adresowej trybu użytkownika. W bloku kontrolnym każdego obszaru pamięta się przedział adresów, jakie obszar obejmuje, prawa dostępu (odczyt, zapis, wykonywanie) oraz informacja, gdzie przechowywane są dane (np. w pamięci fizycznej, na urządzeniu wymiany, w pliku itp.). Obszary nie mogą na siebie zachodzić, mogą się natomiast stykać.
Bloki kontrolne obszarów należących do jednego procesu są zorganizowane w drzewo AVL i posortowane względem adresów końcowych. Sprawdzenie wskaźnika polega na wyszukaniu obszaru w drzewie AVL.
W pierwszej wersji Linuksa obszary były ułożone w jednokierunkową listę, posortowaną względem adresów końcowych.15.7 Dopóki nie zaimplementowano mechanizmów IPC oraz mapowania plików, takie rozwiązanie wystarczało, gdyż liczba obszarów dla pojedynczego procesu wynosiła od kilku do kilkunastu. Mechanizm IPC udostępnił domyślnie do 128 obszarów, natomiast mapowanie plików może dla architektury x86 dać w ekstremalnym przypadku kilkaset tysięcy rozłącznych obszarów.15.8 Według autorów Linuksa w praktyce można spotykać programy wykorzystujące do kilku tysięcy obszarów, powstałych głównie z mapowania plików.
Większość programów korzysta z co najwyżej kilkudziesięciu obszarów.
Na rys. 7.1 (HTML: niedostępne) przedstawiono dwa przykładowe drzewa AVL,
dla przestrzeni adresowych programów Java i Netscape Navigator.
W pracy badane będą dane związane z wywołaniami funkcji find_vma().
Wywołanie tej funkcji odbywa się zarówno przy zmianie przestrzeni adresowej
(dodawanie, usuwanie obszarów), jak i przy zwykłym szukaniu obszarów. Interesować
nas będzie tylko złożoność wyszukiwania w strukturach danych, natomiast
koszt związany z samą manipulacją na węzłach struktur zostanie pominięty.