Zarządzanie pamięcią operacyjną
ŁF
LINUX - Zarządzanie pamięcią operacyjną.
1. Podstawowe zagadnienia
Podstawowym zadaniem każdego systemu operacyjnego jest wykonywanie programów. Przed wykonaniem, kod programu i jego dane muszą być umieszczone przynajmniej częściowo w pamięci operacyjnej. Zwykle w każdym systemie dochodzi do sytuacji, gdy zaczyna brakować pamięci dla wykonywanych programów lub nawet dla jednego programu. Z tego względu pamięć operacyjna należy do najważniejszych zasobów każdego systemu komputerowego, a zarządzanie tą pamięcią stanowi jedno z głównych zadań systemu operacyjnego. W tym artykule prezentujemy podstawowe zagadnienia dotyczące zarządzania pamięcią operacyjną. Opisujemy szczegółowo strategię stronicowania na żadanie zastosowaną w systemie Linux. Omawiamy strukturę pamięci wirtualnej procesu. Przedstawiamy mechanizm odworowania plików w pamięci oraz realizujące go funkcje systemowe.
Celem zarządzania pamięcią operacyjną jest:
- przydział pamięci fizycznej poszczególnym procesom,
- odwzorowanie logicznej przestrzeni adresowej procesu na fizyczną przestrzeń adresową pamięci,
- ochrona zawartości pamięci,
- współdzielenie obszarów pamięci przez różne procesy.
(1.1) Realizacja wieloprogramowości
Systemy wieloprogramowe dają możliwość jednoczesnego uruchamiania wielu programów. Każdy z działających programów musi mieć przydzielony odpowiedni obszar pamięci operacyjnej. System może to zapewnić poprzez:
- podział pamięci operacyjnej pomiędzy działające procesy,
- wymianę procesów w pamięci.
Podział dynamiczny polega na przydzielaniu obszarów o zmiennym rozmiarze w zależności od potrzeb uruchamianych procesów. Proces przechowuje dwa parametry każdego z przydzielonych obszarów:
- adres początkowy (bazowy) obszaru,
- rozmiar (granicę) obszaru.
Z podziałem pamięci wiąże się nieodłącznie problem fragmentacji pamięci. Polega on na pozostawianiu niewykorzystanych fragmentów pamięci wewnątrz lub pomiędzy przydzielonymi obszarami.
Fragmentacja zewnętrzna występuje poza przydzielonymi obszarami o zmiennej długości, gdy pozostałe fragmenty wolnej pamięci są zbyt małe dla innych procesów.
Fragmentacja wewnętrzna występuje wewnątrz przydzielonych obszarów o stałej długości, gdy rozmiar procesu jest mniejszy niż suma przydzielonych mu obszarów. Niewykorzystany pozostaje wtedy fragment ostatniego z przydzielonych obszarów.
Wymiana procesów (ang. swapping) polega na okresowym przesłaniu procesu z pamięci operacyjnej do pamięci pomocniczej, aby umożliwić sprowadzenie innego procesu z pamięci pomocniczej do zwolnionego obszaru pamięci operacyjnej.
W systemach z podziałem pamięci wymiana umożliwia wykonywanie większej liczby procesów niż może pomieścić pamięć operacyjna. Powoduje to zwiększenie stopnia wieloprogramowości, co zwykle poprawia efektywność systemu.
W systemach bez podziału pamięci wymiana procesów stwarza jedyną możliwość uzyskania wieloprogramowości.
(1.2) Przestrzenie adresowe
Adres wytworzony przez procesor w wyniku wykonania rozkazu programu nosi nazwę adresu logicznego (ang. logical address). Zbiór wszystkich adresów logicznych generownych przez program tworzy logiczną przestrzeń adresową procesu.
Adres fizyczny wskazuje konkretną komórkę pamięci operacyjnej. Zbiór wszystkich adresów fizycznych tworzy fizyczną przestrzeń adresową.
Wiązanie adresów polega na odwzorowaniu adresów logicznych generowanych w programie na adresy fizyczne w pamięci operacyjnej. Może następować w dowolnych z poniższych etapów:
- w czasie kompilacji, czyli tworzenia programu,
- w czasie ładowania programu do pamięci,
- w czasie wykonania programu.
Jeśli początkowy adres w pamięci nie jest znany w czasie tworzenia programu, to wiązanie adresów musi być opóźnione do momentu ładowania programu do pamięci. Po załadowaniu program nie może być już przemieszczany w pamięci podczas wykonywania, ponieważ adresy logiczne i fizyczne są już takie same. Zmiana adresu początkowego pociąga za sobą konieczność ponownego załadowania całego programu, począwszy od nowego adresu w pamięci.
Największe możliwości swobodnego przemieszczania programu w pamięci daje wiązanie adresów w czasie wykonywania programu. Adresy logiczne muszą być jednak tłumaczone na bieżąco na adresy fizyczne, co wymaga zastosowania specjalnego sprzętu. Zajmuje się tym jednostka zarządzania pamięcią (ang. memory management unit - MMU). Złożoność tej jednostki warunkuje wybór strategii zarządzania pamięcią.
(1.3) Zwiększenie logicznej przestrzeni adresowej procesu
Ograniczenie logicznej przestrzeni adresowej procesu do rozmiaru pamięci operacyjnej stanowiło przez długi czas poważne ograniczenie w systemach operacyjnych, uniemożliwiając wykonywanie dużych programów. Opracowane zostały dwie metody rozwiązania tego problemu:
- nakładki,
- pamięć wirtualna.
Znacznie większe możliwości i większą wygodę oferuje technika pamięci wirtualnej. Pamięć wirtualna umożliwia wykonywanie programów, które nie znajdują się w całości w pamięci operacyjnej. Udostępnia procesom dużą ciągłą przestrzeń adresową nieograniczoną rozmiarem fizycznej pamięci operacyjnej. Separuje w ten sposób pamięć logiczną procesu od pamięci fizycznej. System operacyjny zajmuje się odwzorowaniem pamięci wirtualnej używanej przez procesy, częściowo na pamięć operacyjną a częściowo na pamięć pomocniczą.
Ponieważ procesy nie muszą znajdować się w całości w pamięci operacyjnej, każdy z nich zajmuje mniejszy obszar tej pamięci. Dzięki temu w pamięci można umieścić więcej procesów, zwiększając stopień wieloprogramowości. Zmniejsza się liczba operacji wejścia-wyjścia związanych z ładowaniem lub wymianą procesów. W efekcie wzrasta przepustowość systemu.
(1.4) Strategie zarządzania pamięcią
Systemy bez pamięci wirtualnej wykorzystują jedną ze strategii zarządzania pamięcią wymienionych w tablicy 7.1:
- przydział ciągły pojedyńczego obszaru,
- przydział ciągły wielu obszarow,
- stronicowanie,
- segmentacja,
- segmentacja stronicowana.
| Strategia | Charakterystyka |
| przydział ciągły pojedyńczego obszaru |
|
| przydział ciągły wielu obszarów |
|
| stronicowanie |
|
| segmentacja |
|
| segmentacja stronicowana |
|
Wszystkie wymienione wyżej strategie wymagają, żeby cały proces został umieszczony w pamięci operacyjnej przed rozpoczęciem wykonywania. Ograniczenie to nie występuje w systemach wykorzystujących pamięć wirtualną. Do implementacji pamięci wirtualnej może posłużyć jedna ze strategii:
- stronicowanie na żądanie,
- segmentacja na żądanie.
Większość współczesnych systemów operacyjnych wykorzystuje stronicowanie na żądanie do realizacji pamięci wirtualnej. W dalszej części niniejszej lekcji zostanie omówiona przykładowa implementacja w systemie Linux.
Segmentację na żądanie stosuje system OS/2.
(1.5) Dzielenie i ochrona pamięci
Współdzielenie obszarów pamięci przez różne procesy jest możliwe do realizacji w systemach, które przydzielają po kilka lub więcej obszarów każdemu procesowi. Wówczas obszary, które zawierają kod programu lub dane przeznaczone wyłącznie do odczytu, mogą być użytkowane wspólnie z innymi procesami. Dotyczy to strategii stronicowania i segmentacji pamięci. Określone pozycje tablic stron lub segmentów kilku procesów wskazują wtedy na te same ramki lub segmenty w pamięci operacyjnej.
Podstawowa ochrona pamięci obejmuje sprawdzanie:
- poprawności adresów,
- praw dostępu do poszczególnych obszarów pamięci, zwłaszcza obszarów współdzielonych.
W zaawansowanych strategiach zarządzania pamięcią ochrona może być powiązana ze stronami lub segmentami. Dla każdej strony lub segmentu zdefiniowany jest zestaw bitów, przechowywanych w tablicy wraz z adresem bazowym. Zestaw ten zawiera zwykle:
| bit poprawności | - | określa, czy obszar należy do przestrzeni adresowej procesu oraz czy znajduje się obecnie w pamięci operacyjnej, |
| bity ochrony | - | opisują prawa dostępu do danego obszaru pamięci: prawo do czytania, pisania i wykonywania. |
(1.6) Wspomaganie sprzętowe
Wybór strategii zarządzania pamięcią operacyjną jest silnie uzależniony od możliwości sprzętu komputerowego. Wspomagania sprzętowego wymaga przede wszystkim:
- przekształcanie adresów logicznych na fizyczne,
- sprawdzanie poprawności adresu.
W najprostszym przypadku przydziału pojedyńczego obszaru, potrzebny jest tylko jeden rejestr bazowy, przechowujący adres bazowy obszaru użytkownika. Przydział wielu obszarów wymaga już użycia dwóch rejestrów: rejestru bazowego i rejestru granicznego. Po wybraniu procesu przez planistę, dyspozytor ładuje do tych rejestrów odpowiednio adres początkowy i rozmiar przydzielonego procesowi obszaru. Porównanie adresu logicznego z wartością w rejestrze granicznym umożliwia sprawdzenie poprawności adresu, a przez dodanie wartości z rejestru bazowego uzyskuje się adres fizyczny w pamięci. Mechanizm ten ilustruje rys. 7.1. W ten sposób sprzęt realizuje wiązanie adresów i jednocześnie ochronę innych obszarów pamięci.
 |
| Rys. 7.1 Sprzęt do obsługi wielu ciągłych obszarów |
Znacznie większego wsparcia sprzętowego wymaga stronicowanie pamięci. Na rys. 7.2 przedstawiono podstawowy sprzęt stronicujący.
 |
| Rys. 7.2 Sprzęt do stronicowania |
Podczas przełączania kontekstu procesu, jego tablica stron musi być załadowana do sprzętowej tablicy stron systemu. Adres logiczny składa się z numeru strony s i odległości na stronie o. Numer strony wybiera odpowiednią pozycję w tablicy stron, zawierającą adres bazowy ramki w pamięci fizycznej. Sprzęt stronicujący sprawdza ponadto bit poprawności, aby stwierdzić, czy strona o podanym numerze należy do logicznej przestrzeni adresowej procesu i czy jest sprowadzona do pamięci operacyjnej. Odległość na stronie nie wymaga sprawdzania, gdyż rozmiar tej części adresu jest odpowiednio dobrany do rozmiaru strony (i ramki). Przykładowo, przy rozmiarze adresu N-bitów i rozmiarze strony 2n słów, numer strony zajmuje N-n bardziej znaczących bitów, a odległość na stronie - n mniej znaczących bitów.
Najbardziej złożony sprzęt, przedstawiony na rys. 7.3, jest potrzebny do realizacji segmentacji pamieci.
 |
| Rys. 7.3 Sprzęt do segmentacji |
Podczas przełączania kontekstu procesu, jego tablica segmentów musi być załadowana do sprzętowej tablicy segmentów systemu. Adres logiczny zawiera numer segmentu s, który jest indeksem w tablicy segmentów. Wybrana pozycja tablicy zawiera adres bazowy i granicę segmentu w pamięci fizycznej. Zadaniem sprzętu jest jeszcze porównanie odległości d w segmencie z jego granicą oraz dadanie odległości do adresu bazowego segmentu, aby otrzymać adres fizyczny.
Sprzętowa tablica stron lub segmentów może być zrealizowana na kilka sposobów:
- zbiór rejestrów specjalnego przeznaczenia, przechowujących całą tablicę stron procesu,
- rejestry asocjacyjne, zwane również buforami translacji bliskiego otoczenia, przechowujące tylko wybrane pozycje tablicy stron i uzupełniane w miarę potrzeb z tablicy stron w pamięci,
- rejestr bazowy tablicy stron wskazujący jej położenie w pamięci operacyjnej.
2. Strategia stronicowania na żadanie w systemie Linux
W systemie Linux zastosowano strategię stronicowania na żądanie do realizacji pamięci wirtualnej. Punktem wyjścia dla takiej strategii było stronicowanie pamięci z wymianą całych procesów. Podstawowa zmiana polega na tym, że zamiast wymieniać całe procesy pomiędzy pamięcią operacyjną i pomocniczą, system wymienia w miarę potrzeb tylko pojedyńcze strony tych procesów.
Stronicowanie na żądanie wykorzystuje następujące mechanizmy:
- stronicowanie pamięci z możliwością wykonywania procesu wprowadzonego tylko częściowo do pamięci operacyjnej,
- sprowadzanie brakującej strony do pamięci operacyjnej na żądanie procesu, gdy wystąpi odwołanie do tej strony,
- zastępowanie stron, gdy brakuje wolnych ramek pamięci na nowe strony potrzebne procesowi.
(2.1) Podział pamięci
Pamięć fizyczna podzielona jest na ramki, czyli obszary o ustalonym rozmiarze. Rozmiar ramki jest uzależniony od platformy sprzętowej i zwykle wynosi 4096 B (4 KB) lub 8192 B (8 KB).
Pamięć logiczna procesu, zwana również pamięcią wirtualną, podzielona jest na strony o tym samym rozmiarze. W pamięci wirtualnej musi być odwzorowany kod programu wykonywanywanego przez proces. Cały kod nie musi jednak znajdować się w pamięci operacyjnej. Wystarczy, że znajdą się tam tylko niektóre strony zawierające początek kodu, aby proces mógł rozpocząć wykonywanie programu. Strony zawierające pozostałą część kodu oraz inne dane będą sprowadzane do pamięci operacyjnej, gdy proces będzie próbował się do nich odnosić.
Pamięć pomocnicza jest również podzielona na obszary o rozmiarze strony i przeznaczona do przechowywania stron czasowo usuniętych z pamięci operacyjnej w wyniku zastępowania. Pamięć pomocnicza jest określana jako przestrzeń wymiany i może być zrealizowana na urządzeniu wymiany lub w pliku wymiany.
(2.2) Przydział i zwalanianie ramek
Wszystkie ramki pamięci fizycznej w systemie opisane są przez listę struktur mem_map_t inicjowaną w czasie startu systemu. Każda struktura mem_map_t reprezentuje pojedyńczą ramkę pamięci.
Informacje o wolnych ramkach przechowywane są w tablicy free_area[]. Sąsiednie wolne ramki grupowane są w bloki o rozmiarze będącym potęgą liczby 2. Element tablicy free_area[i] wskazuje listę bloków o rozmiarze 2i ramek, gdzie i=0, 1,..., N-1. Zatem element free_area[0] wskazuje listę bloków składających się z jednej ramki, element free_area[1] - listę bloków składających się z dwóch ramek, element free_area[2] - listę bloków składających się z czterech ramek, itd. Rozmiar tablicy wynosi N=10 na większości platform sprzętowych, co oznacza że największe bloki mogą składać się z 29 ramek. Ze względu na to, że ramki w bloku tworzą ciągły obszar pamięci, każdy blok jest reprezentowany na liście tylko przez początkową ramkę. Rysunek 7.4 ilustruje opisany sposób reprezentacji wolnych ramek.
 |
| Rys. 7.4 Reprezentacja wolnych ramek |
Przydziałem i zwalnianiem ramek zajmuje się podprogram jądra nazywany dyspozytorem ramek. Wykorzystuje w tym celu algorytm bliźniaków (ang. buddy algorithm). Dyspozytor przydziela procesom ciągłe bloki pamięci składające się z 2i ramek.
Po otrzymaniu zlecenia przydziału n ramek pamięci, dyspozytor przegląda tablicę free_area[] w celu znalezienia najmniejszego bloku o rozmiarze nie mniejszym od zamówionego 2i >=n. Najpierw poszukuje bloku o rozmiarze dokładnie pasującym do zamówienia, potem bloku dwukrotnie większego i kolejnych. Jeśli znajdzie wolny blok o rozmiarze 2i+1 ramek, to dokonuje podziału na dwa mniejsze bloki o rozmiarze 2i . Jeden z tych bloków przydziela procesowi, a drugi dołącza do listy wolnych bloków wskazywanych przez free_area[i].
Zwalniane bloki ramek są dołaczane do odpowiednich list w tablicy free_area[]. Dyspozytor stara się przy tym łączyć każde dwa sąsiednie bloki ramek o rozmiarze 2i w jeden większy blok o rozmiarze 2i+1 .
(2.3) Tablice stron i wiązanie adresów
W zależności od platformy sprzętowej Linux dopuszcza adresowanie pamięci 32-bitowe (np. Intel x86) lub 64-bitowe (np. Alpha). Rozmiar wirtualnej przestrzeni adresowej wynosi wtedy odpowiednio 232 B (4 GB) lub 264 B. Dla tak dużej przestrzeni adresowej potrzebna jest wielka tablica stron. Już przy 32-bitowym adresie i stronie 4 KB tablica stron powinna zawierać 220 pozycji. Przechowywanie takiej tablicy w pamięci wymaga zaalokowania dużego ciągłego obszaru.
Z tego powodu system Linux stosuje stronicowanie wielopoziomowe, dzieląc tablicę stron na mniejsze części. Rysunek 7.xx przedstawia 3-poziomową reprezentację tablicy stron procesu. Adres bazowy tablicy stron wskazuje na tablicę 1-go poziomu, nazywaną katalogiem stron. Każda z pozycji w katalogu wskazuje na jedną z tablic 2-go poziomu, określaną jako pośredni katalog stron. Pozycja w tym katalogu wskazuje na jedną z tablic 3-go poziomu, nazywaną po prostu tablicą stron. Nie wszystkie platformy sprzętowe wykorzystują 3 poziomy stronicowania. Przy adresowaniu 32-bitowym wystarcza na ogół tablica 2-poziomowa, w której pomija się katalogi pośrednie. Każda pozycja w katalogu stron interpretowana jest wtedy jako pośredni katalog stron o rozmiarze 1.
Adres wirtualny zawiera numer strony w przestrzeni wirtualnej procesu i odległość na stronie. Jednostka MMU procesora przekształca ten adres na adres liniowy, wyróżniając odpowiednią liczbę poziomów adresu (2 lub 3). Następnie adres liniowy przekształcany jest na adres fizyczny w sposób przedstawiony na rysunku 7.5.
 |
| Rys. 7.5 Przekształcanie adresu linowego na adres fizyczny |
Adres 1-go poziomu wybiera pozycję w katalogu stron (tablicy 1-go poziomu), czyli jeden z katalogów pośrednich. Adres 2-go poziomu wybiera pozycję w katalogu pośrednim, wskazującą jedną z tablic stron. Adres 3-go poziomu wybiera już konkretną stronę w tablicy stron. Uzyskuje się w ten sposób adres bazowy ramki w pamięci operacyjnej, a odległość na stronie wskazuje konkretny bajt.
Oprócz adresu bazowego ramki, pozycja w tablicy stron zawiera bity przechowujące dodatkowe informacje o stronie, m.in.:
| bit poprawności | - | określa, czy strona znajduje się w pamięci operacyjnej, |
| bit modyfikacji | - | określa, czy strona była modyfikowana od momentu sprowadzenia do pamięci operacyjnej, |
| bit odniesienia | - | określa, czy nastąpiło ostatnio jakieś odniesienie do strony, |
| bity ochrony | - | opisują prawa dostępu do danego obszaru pamięci: prawo do czytania, pisania i wykonywania. |
(2.4) Sprowadzanie stron na żądanie
</p>Pamięć wirtualna daje możliwość wykonywania procesu, który nie znajduje się w całości w pamięci operacyjnej. Stwarza to jednak możliwość odwołania do strony, która nie została jeszcze sprowadzona do pamięci. Sytuację taką wykrywa sprzęt stronicujący na podstawie bitu poprawności w tablicy stron. Generowany jest wtedy błąd braku strony, czyli pułąpka. Błąd taki musi być niezwłocznie obsłużony przez jądro systemu.
Obsługa błędu braku strony obejmuje następujące czynności:
- zapamiętanie kontekstu procesu,
- sprawdzenie poprawności adresu wirtualnego, ewentualne wysłanie sygnału SIGSEGV do procesu,
- sprawdzenie, czy typ dostępu do strony był dozwolony, ewentualne wysłanie sygnału SIGSEGV do procesu,
- znalezienie i przydział wolnej ramki,
- sprowadzenie potrzebnej strony do przydzielonej ramki,
- modyfikacja odpowiedniej pozycji w tablicy stron,
- wzowienie wykonania instrukcji kodu programu.
(2.5) Zastępowanie stron
Brakująca strona może zostać sprowadzona bezpośrednio z pliku na dysku lub z przestrzeni wymiany na dysku (z pamięci pomocniczej), jeśli była już wcześniej używana i została zastąpiona.</p>
Przed sprowadzeniem strony na żądanie system musi przydzielić procesowi nową ramkę. Jeżeli brakuje wolnych ramek pamięci, to pojawia się konieczność wykorzystania jednej z ramek wykorzystywanych dotychczas i zastąpienia przechowywanej strony nową stroną.
Zastępowanie stron obejmuje następujące czynności:
- znalezienie ofiary, czyli ramki, której zawartość zostanie zastąpiona,
- wysłanie przechowywanej w ramce strony do przestrzeni wymiany, jeżeli strona była modyfikowana (ustawiony bit modyfikacji),
- modyfikacja odpowiedniej pozycji w tablicy stron procesu, do którego należała strona,
- sprowadzenie potrzebnej strony z pamięci pomocniczej do zwolnionej ramki,
- modyfikacja odpowiedniej pozycji w tablicy stron procesu, dla którego sprowadzono stronę.
System Linux stosuje algorytm LFU z liniowym postarzaniem stron. Funkcja realizująca ten algorytm sprawdza kolejno strony wszystkich procesow i wybiera do zastąpienia stronę najmniej używaną, czyli taką, do której nastąpiło ostatnio najmniej odniesień. Funkcja zastępowania stron, realizująca ten algorytm, jest wołana w dwóch sytuacjach:
- zabrakło wolnych ramek do przydziału,
- demon wymiany kswpd stwierdził, że liczba wolnych ramek w systemie jest zbyt mała.
W celu ustalenia liczby odniesień, z każdą ramką pamięci związany jest licznik przechowujący wiek strony. Wiek może się zmieniać w zakresie od 0 do 20, przy czym mniejsza liczba oznacza starszą (rzadziej używaną) stronę. Gdy strona jest po raz pierwszy wprowadzana do ramki pamięci operacyjnej, system nadaje jej wartość początkową wiek = 3. Następnie stosowany jest mechanizm postarzania stron, które nie są używane. Wiek wszystkich stron jest zmniejszany o 1 za każdym razem, gdy demon wymiany zostaje obudzony. Jeśli strona zostaje użyta, jej wiek jest zwiększany o 3. Strony stare, które osiągnęły wiek = 0 mogą być usunięte z pamięci operacyjnej.
Wybrana strona musi być wysłana do przestrzeni wymiany tylko wtedy, gdy była modyfikowana w pamięci i ma ustawiony bit modyfikacji. W przeciwnym przypadku strona może być zapomniana, ponieważ można ją ponownie odczytac z pliku lub z przestrzeni wymiany, gdzie była zapisana wcześniej. Modyfikacji wymaga jeszcze pozycja strony w tablicy stron procesu. Zerowany jest bit poprawności strony, a zamiast adresu ramki może być zapisany wskaźnik położenia strony w przestrzeni wymiany.
3. Pamięć wirtualna procesu
Każdy proces w systemie dysponuje niezależną wirtualną przestrzenią adresową. Jej rozmiar jest uzależniony od rozmiaru adresu w konkretnej implementacji systemu Linux. Rysunek 7.6 przedstawia strukturę pamięci wirtualnej procesu.
 |
| Rys. 7.6 Struktura pamięci wirtualnej procesu |
Zawartość pamięci wirtualnej procesu opisuje struktura mm_struct. Jądro utrzymuje równolegle dwie reprezentacje tej pamięci:
- podział na strony opisany w wielopoziomowej tablicy stron procesu,
- podział na obszary reprezentowane przez struktury vm_area_struct.
- adresy początku i końca obszaru w pamięci wirtualnej,
- i-węzeł pliku odwzorowanego na ten obszar,
- atrybuty ochrony obszaru,
- wskaźniki umożliwiające powiązanie struktur wszystkich obszarów na dwa sposoby:
- w listę jednokierunkową,
- w drzewo AVL (ang. Adelson-Velskii and Landis tree), umożliwiające szybkie przeszukiwanie.
4. Odwzorowanie plików w pamięci
System Linux umożliwia odwzorowanie zawartości pliku w pamięci wirtualnej procesu. Zawartość pliku nie jest od razu kopiowana do pamięci operacyjnej, a jedynie dołączana jako nowy obszar do pamięci wirtualnej procesu. Plik może być wtedy traktowany jak ciągły obszar w pamięci procesu, dostępny poprzez bezpośrednie operacje pobrania i podstawienia wartości. Wszystkie modyfikacje dokonane w pamięci są później zapisywane w pliku na dysku. Unika się w ten sposób stosowania funkcji systemowych do operacji na plikach i pośredniego etapu kopiowania danych do podręcznej pamięci buforowej.
Mechanizm odwzorowania pamięci znajduje kilka zastosowań:
- odwzorowanie plików z kodem wykonywanywalnym w pamięci procesów, które ten kod wykonują (realizacja funkcji exec()),
- dynamiczne ładowanie modułów programu i bibliotek dynamicznych,
- odwzorowanie plików w pamięci procesu w celu ułatwienia i przyspieszenia operacji na ich zawartości,
- współdzielenie przez wiele procesów obszarów pamięci, których zawartość przechowywana jest w odwzorowanych plikach niezależnie od tworzenia i kończenia procesów.
Funkcja systemowa mmap() tworzy odwzorowanie fragmentu lub całej zawartości pliku na obszar w pamięci wirtualnej procesu.
void mmap(void *start, size_t lenght, int prot, int flags, int fd, off_t offset);
gdzie:| start | - | początkowy adres odwzorowanego obszaru w pamięci, |
| lenght | - | rozmiar odwzorowanego obszaru w bajtach, |
| prot | - | ochrona obszaru pamięci, |
| flags | - | flagi, |
| fd | - | deskryptor otwartego pliku, |
| offset | - | przesunięcie w pliku, określające początek obszaru, który ma być odwzorowany w pamięci. |
Początek fragmentu pliku, który ma być odwzorowany, wskazywany jest przez argument offset. Jego długość określa argument lenght. Funkcja odwzorowuje ten fragment pliku w pamięci, począwszy od adresu start. Podany adres musi być wyrównany do strony, czyli wskazywać na początek strony w pamięci. Rozmiar strony jest uzależniony od platformy sprzętowej i może być odczytany funkcją getpagesize(). Najczęściej jednak podaje się wartość 0 (lub stałą symboliczną NULL) pozwalając, aby jądro systemu wybrało adres początkowy obszaru w pamięci. Adres ten jest zwracany jako wartość funkcji mmap().
Argument prot pozwala określić sposób ochrony odwzorowanego obszaru pamięci. Może przyjmować następujące wartości lub ich sumę bitową:
| PROT_EXEC | - | strony obszaru mogą być wykonywane, |
| PROT_READ | - | strony obszaru mogą być odczytywane, |
| PROT_WRITE | - | strony obszaru mogą być zapisywane, |
| PROT_NONE | - | strony obszaru nie są dostępne. |
Znaczniki ustawione argumentem flags określają parametry odwzorowania pamięci. Najważniejsze z nich, opisane w standardzie POSIX, zamieszcono poniżej:
| MAP_FIXED | - | odwzorowanie powinno nastąpić od wskazanego adresu start lub zakończyć się błędem, |
| MAP_PRIVATE | - | tworzy prywatne odwzorowanie pamięci dla procesu a wprowadzone w pamięci zmiany nie są zapisywane do pliku i nie są widoczne dla innych procesów, |
| MAP_SHARED | - | tworzy odworowanie współdzielone z innymi procesami, wszystkie wprowadzone w pamięci zmiany są zapisywane do pliku i stają się widoczne dla innych procesów. |
Każde odworowanie wymaga podania jednej z flag: MAP_PRIVATE lub MAP_SHARED. Użycie konkretnej flagi ma znaczenie tylko dla obszarów z prawem do pisania.
Adres początkowy obszaru w pamięci i przesunięcie w pliku powinny być wielokrotnością rozmiaru strony. Funkcja getpagesize() zwraca rozmiar strony pamięci w bajtach.
size_t getpagesize(void);
Usunięcie odwzorowania pamięci realizuje funkcja munmap() poprzez odłączenie odpowiedniego obszaru od wirtualnej przestrzeni adresowej procesu.
int munmap(void *start, size_t lenght);
gdzie:| start | - | początkowy adres odwzorowanego obszaru w pamięci, |
| lenght | - | rozmiar odwzorowanego obszaru w bajtach. |
Funkcja msync() umożliwia zsynchronizowanie zawartości obszaru pamięci z obrazem pliku na dysku. Bez wywołania tej funkcji nie ma pewności, że zmiany dokonane w pamięci zostaną zapisywane na dysku przed usunięciem odwzorowania.
int msync(const void *start, size_t lenght, int flags);
gdzie:| start | - | początkowy adres odwzorowanego obszaru w pamięci, |
| lenght | - | rozmiar odwzorowanego obszaru w bajtach, |
| flags | - | flagi. |
W dziale źródła/C++ znajdują się przykładowe programy do tego i pozostałych artykułów z tego cyklu.
Wszelkie pytania proszę kierować na adres L.Fronczyk@elka.pw.edu.pl