% Impala Operating System
%
% Copyright (C) 2009 University of Wroclaw. Department of Computer Science
%    http://www.ii.uni.wroc.pl/
% Copyright (C) 2009 Mateusz Kocielski, Artur Koninski, Pawel Wieczorek
%    http://bitbucket.org/wieczyk/impala/
% All rights reserved.
%
% Redistribution and use in source and binary forms, with or without
% modification, are permitted provided that the following conditions
% are met:
% 1. Redistributions of source code must retain the above copyright
%  notice, this list of conditions and the following disclaimer.
% 2. Redistributions in binary form must reproduce the above copyright
%  notice, this list of conditions and the following disclaimer in the
%  documentation and/or other materials provided with the distribution.
%
% THIS SOFTWARE IS PROVIDED BY AUTHOR AND CONTRIBUTORS ``AS IS'' AND
% ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
% IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
% ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
% FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
% DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
% OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
% HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
% LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
% OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
% SUCH DAMAGE.
%
% $Id$


\section{Zarządzanie pamięcią.}
\label{VM}

Ten podrozdział zawiera między innymi pobieżne opisy mechanizmów związanych
z~zarządzaniem pamięcią w~systemie operacyjnym.
O wiele bogatszy opis można znaleźć w~pozycji \cite{silber}, a~dokładne
omówienie aspektów technicznych w~\cite{intel}.

Komórki (bajty) pamięci komputera są adresowane 32 bitowymi liczbami\footnote{
Co daje $2^{32}$ różnych adresów, czyli możliwość zaadresowania 4GB pamięci.},
adresy używane przez sprzętową jednostkę pamięci nazywamy adresami fizycznymi, 
a adresy używane w~instrukcjach procesora adresami wirtualnymi. 

Pamięć wirtualna jest techniką umożliwiającą tworzenie wielu wirtualnych
przestrzeni adresowych. W~tym celu wykorzystywany jest tak zwany mechanizm
stronicowania, realizowany przez procesor komputera. Stronicowanie polega
na~podziale pamięci fizycznej na~bloczki o~ustalonym rozmiarze, zwane ramkami
\footnote{ramka - page frame}.
Pamięć wirtualna jest również podzielona na~takie bloczki, zwane stronami
\footnote{strona - page}.
Stronicowanie to przypisywanie stronom odpowiednich ramek, co można
zinterpretować jako ustalanie jaka ramka pamięci fizycznej kryje się za~daną
stroną pamięci wirtualnej. Adresy wirtualne z~instrukcji procesora są
tłumaczone sprzętowo na~adresy fizyczne.

Jest to~istotny element dla~wielozadaniowości ponieważ zwykle programy nie
współdzielą pamięci, a~posługują się tymi samymi adresami. Łatwo się
o~tym przekonać pisząc prosty program w~języku C drukujący na~ekran adres
jakiejś swojej zmiennej. Jeżeli uruchomimy jednocześnie wiele kopii naszego
programu to~każdy wydrukuje ten sam adres, mimo że~każdy ma~swoją własną
pamięć.


Moduł pamięci wirtualnej jest podzielony na kilka warstw:
\begin{itemize}
 \item \texttt{vm\_pmap} (\emph{page map}) -
obsługa odwzorowania stron
na~ramki.
 \item \texttt{vm\_seg} -
zarządzanie wirtualnymi segmentami.
 \item \texttt{vm\_space} -
zarządzanie wirtualnymi przestrzeniami adresowymi.

\end{itemize}

Obsługa pamięci wirtualnej powstała pod wpływem materiałów 
omawiających zarządzanie pamięcią wirtualną w~systemach SVR4\footnote{
Jest to skrócona nazwa systemu jednej z~wersji systemu UNIX: 
,,System V: release 4''.}
i~Mach\cite{unixjadro}\footnote{
W dzisiejszych systemach operacyjnych pochodzących z~UNIXa można znaleźć
następców tych modulów: System Solaris wywodzi się z systemu piątego, a pamięć
wirtualna systemu Mach przeniknęła do~BSD.
} Nazewnictwo procedur było wzorowane na~drugim z~wymienionych modułów.


\subsection{Mapa pamięci.}

Mapa pamięci jest z~góry ustalona (rys \ref{vm:mmap}).
Dla programów użytkownika
są przeznaczone adresy poniżej 3GB, zwane niższymi, a~dla jądra adresy
powyżej, zwane wyższymi. Każdy program wykonywany przez procesor wymaga
stosu oraz sterty. Stertą nazywamy segment dynamicznie przydzielanej
pamięci przez program podczas działania.

Mapa pamięci użytkownika jest narzucona przez obsługiwany format plików
wykonywalnych A.out, omówiony w~\ref{tech:aout}. 
Stosy wątków użytkownika są przydzielane
przez system na~końcu jego przestrzeni adresowej. Ten sposób
postępowania jest uzasadniony tym, że sterta programu musi być ciągła
(z~punktu widzenia jądra), a~nowe wątki, wraz z~ich zapotrzebowaniem na~stos,
mogą przybywać podczas pracy programu.

Przestrzeń jądra wygląda podobnie, wpływ na~nią wywarł format ELF omówiony
w~\ref{tech:elf}. Z tych samych względów stosy wątków jądra oraz
stosy alternatywne wątków użytkownika są umieszczane w końcowych adresach.

Rozkład pamięci fizycznej różni się od przedstawionego powyżej (wirtualnego).
Zawartość pamięci w~adresach poniżej 1MB jest związana ze starszymi modelami
procesorów oraz BIOSem (kod podprogramów obsługi przerwań w~trybie rzeczywistym
itp.),
stąd na rysunku pojawiła się nazwa BIOS. Między
innymi w~tej pamięci jest odwzorowana pamięć karty graficznej, a system
operacyjny umieszcza tam bufory dla DMA\footnote{Direct Memory Access -
technologia pozwalająca kopiować dane między pamięcią RAM a urządzeniem
przez szynę, bez udziału procesora. Używanie DMA zwalnia programistę z~ręcznego
(udział procesora) wysyłania (odbierania) bajtów z (do)~urządzenia.} szyny
ISA, na której znajduje się kontroler stacji dyskietek.


\begin{figure}
 \centering
 \includegraphics{work/vm_mmap}
 \caption{Mapa pamięci a) wirtualnej, b) fizycznej. Strzałki oznaczają w~którą
stronę dany segment rośnie.}
 \label{vm:mmap}

\end{figure}


\subsection{Odwzorowania stron.}

Moduł pamięci wirtualnej opisuje ramki pamięci za~pomocą typu 
\texttt{vm\_page\_t}. Zawarte informacje to licznik odniesień, w~ilu
odwzorowaniach dana ramka się znajduje, oraz adres fizyczny. 
Na wewnętrzne potrzeby modułu przy niektórych stronach zapisywana jest także
informacja o~adresie wirtualnym strony, w~jaki jest ta~ramka odwzorowana.

Opisy wszystkich ramek w komputerze są umieszczone w~tablicy
\texttt{vm\_pages}. Jeżeli przy niektórych ramkach została zapisana
informacja o~adresie wirtualnym, to tablica może posłużyć też jako
odwrotna tablica stron - tzn. do tłumaczenia adresu fizycznego
na~adres wirtualny.

Przy rozruchu systemu
każda ramka znajdująca się za~jądrem jest wpinana w~listę wolnych ramek
\texttt{vm\_free\_pages}.

Tłumaczenie adresów przez procesor odbywa się w~dwóch etapach.
Pierwszy etap to~segmentacja, gdzie adresy z~instrukcji są tłumaczone na~adresy
liniowe. Procesor podczas tłumaczenia korzysta z~tablicy deskryptorów, z~której
między innymi odczytuje informacje o~adresie bazowym i~długości segmentu.
Adres liniowy powstaje poprzez przesunięcie adresu z~instrukcji o~adres bazowy
danego segmentu\footnote{Sama segmentacja spełnia jeszcze rolę ochronną,
sprawdza czy program nie wyskoczył za~segment oraz czy ma odpowiednie prawa
dostępu.}. Ta~właściwość nie jest wykorzystywana w~naszym systemie, dlatego
wszystkie adresy bazowe wynoszą 0, dzięki czemu adres liniowy jest tożsamy
z~adresem instrukcji\footnote{Z tego mechanizmu nie korzysta się
w~ogólnym zarządzaniu pamięcią, jedynie przy implementacji prywatnych
segmentów dla~wątków użytkownika. Prawdopodobnie jest to~spowodowane tym,
że~język C nie wspiera
wykorzystania tego mechanizmu. Przesunięcia spowodowałyby, że~użycie adresów
z~segmentu stosu na~kodzie operującym na~segmencie danych byłoby nieprawidłowe.
Stąd nie można byłoby używać np procedury \texttt{strlen} do~tablic będących
zmiennymi lokalnymi jak i~do~tablic będących zmiennymi globalnymi. Wsparcie
wymagałoby wprowadzenia nowego typu wskaźników, w~których oprócz samego adresu
byłby zapisany deskryptor segmentu - stare kompilatory języka C na~system DOS
w~tym celu rozszerzały język  o~słówko kluczowe \texttt{far}.}.

Drugim etapem jest przetłumaczenie adresu na~adres fizyczny z~użyciem katalogu
stron. Sam katalog stron nie opisuje z~powodów technicznych wszystkich stron
w~pamięci, ponieważ stron może być aż $2^{24}$ to~taki katalog zajmowałby zbyt
dużą ilość pamięci (biorąc pod uwagę, że każda przestrzeń adresowa ma swój
katalog stron). Katalog zajmuje jedną stronę pamięci i~jest tablicą o~1024
elementach. Każda pozycja w~katalogu zawiera adres fizyczny tablicy stron
opisującej 4MB pamięci. Ponieważ $1024\cdot 4MB=4GB$ to~katalog stron~opisuję całą
pamięć jaką mogą adresować instrukcje procesora. Tablica stron ma taką samą
budowę jak katalog, z tym że jej pozycje opisują fizyczne adresy
(zatem każda pozycja tablicy stron opisuje 4kB pamięci) ramek.

Procesor posiada rejestr kontrolny (CR3), w którym trzyma fizyczny adres
katalogu
stron. Każda przestrzeń adresowa posiada swój własny katalog stron, którego
adres jest wpisywany w ten rejestr przy zmianie kontekstu. Warstwa pamięci
wirtualnej odpowiedzialna za~zarządzanie odwzorowaniami stron dla
każdej ramki przydzielonej na~katalog lub stronę zapisuje jej adres wirtualny,
pod którym jest widziana w przestrzeni jądra. Dzięki temu operując na katalogu
stron, w którym wskaźniki do tablic są adresami fizycznymi, może szybko znaleźć
prawidłowy adres wirtualny.

Odwzorowanie stron jest opisane przez typ
\texttt{vm\_pmap\_t}. Przed programistą systemu dwustopniowa konstrukcja
katalogu jest ukryta, ponieważ nie jest to~istotne w~ogólnym zarządzaniu
pamięcią oraz zrobiłoby moduł mniej przenośnym\footnote{
Rozszerzenie procesora pozwalające używać 48-bitowych adresów pamięci
(zwiększając ograniczenie pamięci powyżej 4GB) wprowadza trójstopniową
strukturę katalogu - dzięki ukryciu budowy zaprogramowanie obsługi
takiego rozszerzenia wiązałoby się z~mniejsza ilością zmian w~kodzie.}.

Operacje na odwzorowaniu zarządzają licznikiem odniesień do ramki, odpowiednio
zwiększając oraz zmniejszając przy dodawaniu i~kasowaniu wpisów. Ramki
z~wyzerowanym licznikiem trafiają ponownie na listę wolnych ramek i~nadają się
do~ponownego użycia. Dodatkowymi operacjami są ręczne tłumaczenie adresów
wirtualnych na~fizyczne oraz kopiowanie stron pomiędzy odwzorowaniami,
wykorzystywane przy współdzieleniu pamięci.

Jądro musi być odwzorowane w~każdej przestrzeni adresowej, ponieważ w~każdej
chwili musi znajdować się w pamięci wirtualnej kod podprogramów obsługi
przerwań oraz zleceń od programu użytkownika.

Odwzorowanie jądra w~każdą przestrzeń adresową wiąże się z~dwiema trudnościami
technicznymi. Pierwsza, czyszczenie pamięci podręcznej procesora,
przechowującej fragmenty tablic stron, przy każdej zmianie aktualnej
przestrzeni adresowej. Ponieważ kod jądra jest w~ciągłym użyciu (zegar
systemowy oraz obsługa programów) to~procesor będzie musiał ściągnąć
z~aktualnego katalogu i~tablic stron wpisy, które przed chwilą wykasował.
Druga trudność wynika z~posiadania własnego katalogu przez każdą przestrzeń.
Dodanie nowych tablic stron opisujących pamięć jądra wymaga edycji
wszystkich katalogów.

Pierwsza trudność została rozwiązana sprzętowo przez firmę Intel w~procesorach
Pentium Pro (i686) przez wprowadzenie specjalnego atrybutu GP\footnote{
Global Page - strona globalna.} informującego procesor. że dany wpis znajduje
się we~wszystkich tablicach stron opisujących te~same 4MB pamięci.
Druga trudność została rozwiązana przez przydzielenie wszystkich tablic stron
mogących opisywać przestrzeń jądra podczas rozruchu systemu. Dzięki temu
katalog stron każdej nowo utworzonej przestrzeni zawiera wpisy ze~wszystkimi
tablicami jakie mogą zostać użyte przez jądro i~nie wymaga późniejszej edycji. Wadą tego
rozwiązania jest to, że jądro może nigdy podczas swojej pracy nie użyć
wszystkich tablic. Dla przestrzeni jądra o~rozmiarze 1GB należy przydzielić
256 tablic stron, co łącznie daje koszt 4MB.

\subsection{Wirtualne segmenty i przestrzenie adresowe.}

\begin{figure}
\centering
\includegraphics{work/vm_space}
\caption{Techniczne ujęcie przestrzeni adresowej.}
\label{vm:space}
\end{figure}

Wirtualna przestrzeń adresowa jest dzielona na trzy wirtualne segmenty:
segment tekstu (kodu), danych (sterta i dane z~pliku) oraz stosów. Segmenty
danych i~stosu są we wzajemnej relacji, ponieważ ich wzrost przybliża
koniec jednego do~początku drugiego, zatem system musi pilnować momentu,
w którym segmenty mogłyby się spotkać - taki moment oznacza koniec pamięci
dla programu.

Przestrzeń adresowa jest opisywana przez typ \texttt{vm\_space\_t}, który
zawiera w~sobie odwzorowanie stron pamięci oraz opisy trzech wyżej wspomnianych
segmentów.

Segment jest opisywany przez adres bazowy, aktualny rozmiar oraz ograniczenie
górne na~rozmiar. Przydzielanie i~niszczenie stosów podczas pracy programu
i~jądra oraz odwzorowywanie różnych fragmentów pamięci w~stercie jądra
i~niszczenie tych odwzorowań 
powoduje fragmentację tych segmentów. Z~tego powodu
wirtualne segmenty nie muszą być ciągłymi przestrzeniami, lecz mogą być
dynamicznie zmieniającymi się obszarami. W~związku z~tym segment zawiera
w~sobie listę ciągłych obszarów, opisywanych przez typ \texttt{vm\_region\_t}.

Rysunek \ref{vm:space} przedstawia opis przestrzeni adresowej używany
w~module pamięci wirtualnej.


\subsection{Sterta jądra.}

Stertą jądra zarządza algorytm opracowany przez Jeffa Bonwicka dla~Sun
Microsystems, przedstawiony na~konferencji USENIX\cite{bonwick}. Ten algorytm,
zwany alokatorem płytowym\footnote{alokator płytowy - slab allocator},
przeniknął również do innych systemów operacyjnych jak FreeBSD, Linux, NetBSD.

Algorytm jest nadbudową na obsługę segmentu realizowaną przez
pamięć wirtualną. Idea opiera się o~pojęcię schowka (\texttt{kmem\_cache\_t}),
który przechowuje w~sobie elementy o~ustalonym rozmiarze.

Schowek przechowuje elementy na płytach, które są tablicami elementów.
