W obecnej wersji Linuxa nie istnieje wymiana procesow, zarzadzanie pamiecia korzysta jedynie z mechanizmu wymiany stron. Jadro Linuxa, czyli struktury i dane sluzace do zarzadzania systemem nie moga byc przenoszone do pamieci pomocniczej. W przypadku przestrzeni wirtualnej procesow wszystkie rodzaje segmentow moga byc usuwane z tym, ze kod programu oraz biblioteki sa usuwane i w razie potrzeby wczytywane ponownie z plikow zrodlowych, natomiast dane, stos i pamiec dzielona sa przenoszone do specjalnych urzadzen dyskowych, zwanych dalej urzadzeniami wymiany stron. Linux wyroznia dwa rodzaje urzadzen dyskowych: blokowe i plikowe. Blokowe charakteryzuja sie tym, ze sa spojne na dysku i posiadaja bloki rozmiaru 4 kB, natomiast urzadzenia plikowe dzialaja dokladnie tak samo, jak zwykle pliki, czyli maja bloki rozmiaru 512 B i moga byc rozrzucone na calej powierzchni dyskowej. Dla urzadzen plikowych trzeba dodatkowo pamietac informacje, ktore bloki naleza do ktorej strony, co powoduje, ze urzadzenia blokowe sa wyraznie szybsze i latwiejsze w obsludze. Niemniej jednak w systemie plikow MSDOS mozna podlaczac tylko urzadzenia plikowe i stad ich implementacja.
Informacja o urzadzeniach wymiany stron przechowywana jest w tablicy swap_info. Kazdy element tej tablicy to struktura typu swap_info_struct opisujaca jedno urzadzenie wymiany stron. Urzadzenia powiazane sa w liste priorytetowa swap_list, ktora ma wskaznik na pierwszy element oraz na urzadzenie, z ktorego bedzie pobierana wolna ramka przy najblizszym zadaniu wolnej ramki na dysku. Na poczatku mapy pamieci znajduje sie tablica swap_cache, ktora przechowuje informacje o kopiach ramek pamieci na dysku. Ponizszy rysunek przedstawia przykladowa liste urzadzen i stan tablicy swap_cache:
W pliku include/linux/swap.h zdefiniowane jest ograniczenie na liczbe wszystkich urzadzen wymiany stron:
#define MAX_SWAPFILES 8 /* < 128, max liczba urzadzen wymiany stron w systemie */
Algorytm przydzialu wolnej ramki na urzadzeniu laczy przydzielane ramki w pakiety, ktorych wielkosc okreslona jest przez stala zdefiniowana w pliku include/linux/swap.h:
#define SWAP_CLUSTER_MAX 32 /* max liczba ramek w pakiecie */
Oto dokladna definicja struktury swap_info_struct z pliku include/linux/swap.h:
/* jedna struktura swap_info_struct dla kazego uzywanego urzadzenia wymiany stron */
struct swap_info_struct {
unsigned int flags;
kdev_t swap_device; /* numer urzadzenia blokowego na dysku */
struct inode * swap_file; /* i-wezel urzadzenia wymiany stron */
unsigned char * swap_map;
unsigned char * swap_lockmap;
int lowest_bit;
int highest_bit;
int cluster_next;
int cluster_nr; /* liczba wolnych ramek w biezacym pakiecie */
int prio;
int pages; /* liczba dostepnych ramek urzadzenia */
unsigned long max; /* maksymalny numer dostepnej ramki */
int next;
};
Dodatkowe wyjasnienia:
Ponizej omowione sa funkcje obslugujace urzadzenia wymiany stron: sys_swapon()
podlacza nowe urzadzenie wymiany stron do systemu, sys_swapoff()
probuje odlaczac urzadzenie; get_swap_page() obsluguje zadanie
wolnej ramki na dysku, wywolywana jest przez algorytm
wymiany stron z pamieci na dysk, scan_swap_map()
wyszukuje wolna ramke na podanym urzadzeniu, wolana jest przez poprzednia
funkcje; rw_swap_page() wczytuje i zapisuje strony na dysk, wczytywanie
odbywa sie przy wystapieniu bledu
braku strony oraz przy odlaczaniu urzadzen, natomiast zapisywanie
przy wymianie stron z pamieci na dysk; swap_free() zwalnia ramke
urzadzenia dyskowego, wywolywana jest podczas obslugi bledow braku strony
z zadaniem praw zapisu (to oznacza, ze bedzie zmieniona, wiec jej kopia
dyskowa staje sie bezuzyteczna), a takze przy zwalnianiu stron przez procesy
oraz przy odlaczaniu urzadzen dyskowych od systemu.
Podlacza nowe urzadzenie wymiany stron do systemu.
DEFINICJA: int sys_swapon(const char * specialfile, int swap_flags)
WYNIK: 0, gdy podlaczenie sie powiodlo
-kod bledu w przeciwnym przypadku:
kod bledu = EPERM (brak praw do podlaczenia urzadzenia lub
jest juz maksymalna liczba urzadzen w systemie)
EBUSY (i-wezel urzadzenia ma wiecej niz jedno
dowiazanie lub urzadzenie jest juz podlaczone)
EINVAL (zly rodzaj urzadzenia dyskowego, brak etykietki
"SWAP-SPACE" na pierwszej ramce
lub wszystkie ramki urzadzenia sa niedostepne)
ENODEV (nie ma takiego urzadzenia dyskowego)
ENOMEM (brak pamieci na struktury urzadzenia)
Pierwszym argumentem funkcji jest nazwa urzadzenia dyskowego. Ustawienie flagi SWAP_FLAG_PREFER powoduje pobranie priorytetu nowego urzadzenia z 15 najmniej znaczacych bitow parametru swap_flags, w przeciwnym przypadku priorytet nadawany jest z systemowgo licznika least_priority, ktory po kazdym pobraniu wartosci zmniejsza sie.
Funkcja inicjuje struktury danych opisujace nowe urzadzenie i podlacza je do systemu:
- sprawdza, czy uzytkownik, ktory wywolal funkcje, ma prawo podlaczania urzadzen - znajduje wolne miejsce w tablicy swap_info - ustawia priorytet - pobiera i-wezel zwiazany z nazwa urzadzenia i sprawdza, czy opisuje odpowiedni rodzaj urzadzenia - sprawdza typ urzadzenia i ustawia numer urzadzenia swap_device w strukturze swap_info_struct, jesli typ jest blokowy - identyfikuje etykietke (ostatnie dziesiec bajtow pierwszej ramki urzadzenia powinno zawierac napis "SWAP-SPACE") - wczytuje mape bitowa dostepnych ramek z pierwszej ramki urzadzenia - inicjuje mape bajtowa (dla ramek dostepnych ustawia wartosc 0, a dla niedostepnych wartosc 128) - ustawia flage urzadzenia SWP_WRITEOK (oznacza, ze urzadzenie jest uzywane i mozna do niego pisac) - wstawia urzadzenie do listy priorytetowej
Probuje odlaczyc urzadzenie od systemu.
DEFINICJA: int sys_swapoff(const char * specialfile)
WYNIK: 0 w przypadku sukcesu
-kod bledu, gdy nie udalo sie odlaczyc:
kod bledu = EPERM (uzytkownik nie ma praw do odlaczania urzadzen)
EINVAL (nie ma urzadzenia wymiany stron o podanej nazwie)
ENOMEM (brak pamieci na wczytanie stron z urzadzenia)
Argumentem funkcji jest nazwa urzadzenia na dysku.
Przed odlaczeniem urzadzenia funkcja musi przeniesc wszystkie potrzebne strony do pamieci. W tym celu przeglada wirtualna przestrzen adresowa wszystkich procesow i dla kazdej strony znajdujacej sie na tym urzadzeniu probuje wczytac ja do pamieci. Funkcja odlacza urzadzenie tylko wtedy, jesli uda jej sie wczytac wszystkie strony do pamieci. W przeciwnym przypadku zwraca blad ENOMEM. Kolejne czynnosci wykonywane przez funkcje:
- sprawdza, czy uzytkownik, ktory wywolal funkcje, ma prawo odlaczania urzadzen - pobiera i-wezel dla podanej nazwy - wyszukuje rekord tablicy swap_info opisujacy urzadzenie pobranego i-wezla - usuwa urzadzenie z listy priorytetowej - zaznacza, ze do danego urzadzenia nie mozna pisac - przeglada wirtualna przestrzen adresowa procesow w celu zwolnienia wszystkich ramek urzadzenia, jesli sie nie powiedzie, ponownie wstawia urzadzenie do listy priorytetowej, umozliwia zapis do niego i zwraca blad - zwalnia struktury zaalokowane przy podlaczaniu urzadzenia - ustawia flage, ze urzadzenie jest nieuzywane
- obsluguje zadanie wolnej ramki na dysku.
DEFINICJA: long get_swap_page(void)
WYNIK: kod pozycji przydzielonej ramki na dysku
0, jesli nie ma wolnych ramek na dysku
Ponizej przedstawiony jest sposob kodowania pozycji ramek na dysku (wynik funkcji):
Funkcja przeglada urzadzenia wymiany stron w poszukiwaniu wolnej ramki. Dla kazdego przegladanego urzadzenia wywoluje funkcje scan_swap_page(). Jesli ta funkcja znajdzie wolna ramke, to get_swap_page() zwraca kod tej ramki, w przeciwnym przypadku wybiera kolejne urzadzenie do przeszukiwania. Algorytm wyboru urzadzen wymiany stron przeglada najpierw urzadzenia od aktualnie wskazywanego przez swap_list.next posuwajac sie wzdluz listy priorytetowej, ale tylko do momentu, gdy zmniejszy sie priorytet urzadzen. Wtedy zaczyna przegladac wszystkie urzadzenia od poczatku listy zgodnie z priorytetem.
Implementacja funkcji: znacznik wrapped okresla, czy urzadzenia sa przeszukiwane od poczatku listy, type - numer urzadzenia w tablicy swap_info, p - struktura swap_info_struct przegladanego urzadzenia, offset - numer przydzielonej ramki.
{
wrapped=0;
type=swap_list.next;
powtarzarzaj w petli
{
p=swap_info[type];
if (ustawiona flaga SWP_WRITEOK)
/* urzadzenie p uzywane i mozna do niego pisac */
{
offset=scan_swap_map(p); /* przeszukanie urzadzenia p */
if (offset)
/* znalazl wolna ramke */
{
if (nastepne urzadzenie ma ten sam priorytet)
swap_list.next=nastepne urzadzenie
else
swap_list.next=poczatek listy;
return kod pozycji ramki(offset, type)
}
}
/* nie znalazl wolnej ramki na p lub urzadzenie nie bylo do zapisu*/
if (wrraped)
/* szukamy od poczatku listy */
{
if (koniec listy)
return 0;
else
type=nastepne urzadzenie na liscie;
}
else
/* przeszukujemy na razie tylko urzadzenia o rownych priorytetach */
{
if (nastepne urzadzenie ma mniejszy priorytet lub koniec listy)
{
type=poczatek listy;
wrapped=1;
}
else
type=nastepne urzadzenie na liscie;
}
}
}
- wyszukuje i przydziela wolna ramke na podanym urzadzeniu wymiany stron.
DEFINICJA: int scan_swap_map(struct swap_info_struct * si)
WYNIK: numer przydzielonej ramki na urzadzeniu
0 - jesli nie znalazl wolnej ramki na urzadzeniu
Argumentem jest struktura opisujaca urzadzenie dyskowe, na ktorym funkcja ma wyszukac wolna ramke.
Funkcja laczy przydzielane ramki w pakiety o rozmiarze SWAP_CLUSTER_MAX. Pakiety nie sa spojne w mapie ramek, funkcja dla kazdego pakietu przeglada mape ramek od poczatku i "zapycha dziury", tzn. przydziela kolejno znajdowane wolne ramki, az wyczerpie rozmiar pakietu (przyklad dzialania algorytmu).
Implementacja funkcji: offset - numer ramki w mapie ramek urzadzenia.
{
if (si->cluster_nr != 0)
/* nie wyczerpalismy pakietu */
{
offset = si->cluster_next;
while (offset <= si->highest_bit)
/* dopoki moga byc wolne ramki powyzej offset */
{
if (offset jest wolna i dostepna ramka)
{
zmniejsz ilosc ramek do przydzielenia w pakiecie si->cluster_nr;
si->swap_map[offset]=1; /* przydziela ramke procesowi */
zmniejsz ilosc wolnych ramek w systemie nr_swap_pages;
if (offset == si->highest_bit)
/* offset jest najwyzsza wolna ramka */
si->highest_bit--;
si->cluster_next = offset;
return offset;
}
}
}
/* trzeba zaczac nowy pakiet */
si->cluster_nr = SWAP_CLUSTER_MAX;
for (offset = si->lowest_bit; offset <= si->highest_bit ; offset++)
/* przeszukujemy w przedziale, w ktorym moga byc wolne ramki */
{
if (offset jest wolna i dostepna ramka)
{
zmniejsz ilosc ramek do przydzielenia w pakiecie si->cluster_nr;
si->swap_map[offset]=1; /* przydziela ramke procesowi */
zmniejsz ilosc wolnych ramek w systemie nr_swap_pages;
if (offset == si->highest_bit)
/* offset jest najwyzsza wolna ramka */
si->highest_bit--;
si->cluster_next = offset;
return offset;
}
}
return 0;
}
- Wczytuje strone z dysku do pamieci lub zapisuje ja na dysk.
DEFINICJA: void rw_swap_page(int rw, unsigned long entry, char * buf, int wait)
Pierwszy argument funkcji rw okresla, czy strona bedzie wczytywana, czy zapisywana. Argument entry to kod pozycji przydzielonej ramki na dysku, buf to adres ramki pamieci, znacznik wait okresla, czy proces ma czekac na wykonanie operacji.
Proces, ktory wykonuje operacje wczytania lub zapisania strony asynchronicznie, musi zaznaczyc, ze ramka pamieci tej strony ma byc odblokowana oraz przydzielona ramka na dysku ma byc odblokowana i zwolniona. Wtedy po zakonczeniu operacji zostanie wywolana funkcja swap_after_unlock_page(), ktora wykona te czynnosci. W przypadku urzadzen plikowych kazdy i-wezel przechowuje mape blokow opisujaca, ktore bloki naleza do ktorych ramek (ramka ma 4kB, a blok 512B, wiec kazda ramka jest zapisana na 8 blokach).
Implementacja funkcji:
{
wylicz numer urzadzenia i sprawdz, czy jest uzywane;
wylicz numer ramki na urzadzeniu, sprawdz, czy jest w zakresie dostepnych ramek
i czy jest uzywana;
while (set_bit(offset,p->swap_lockmap))
/* czeka, az ramka urzadzenia bedzie odblokowana i blokuje ja */
{
run_task_queue(&tq_disk);
sleep_on(&lock_queue);
}
page = mem_map + MAP_NR(buf);
atomic_inc(&page->count); /* zwieksza licznik dowiazan do ramki pamieci */
if (p->swap_device)
{
/* jesli urzadzenie jest blokowe */
if (!wait)
/* jesli operacja ma byc wykonana asynchronicznie */
{
zaznacza, ze ramka pamieci ma byc odblokowana po operacji
oraz jej licznik dowiazan ma byc zmniejszony;
zapamietuje kod przydzielonej ramki na dysku zaznaczajac,
ze ona rowniez ma byc odblokowana;
}
w przypadku operacji zapisu sprawdza, czy urzadzenie mozna zapisywac;
blokuje przydzielona ramke urzadzenia;
wykonuje operacje zytania lub zapisu;
if (!wait)
/* jesli asynchronicznie, nie czeka */
return;
wait_on_page(page);
}
else if (p->swap_file)
/* jesli urzadzenie jest plikowe */
{
pobiera i-wezel urzadzenia;
pobiera deskryptory buforow przydzielonych do danej ramki na urzadzeniu;
wykonuje operacje wczytania lub zapisu pomiedzy ramka i buforami;
zmniejsza licznik dowiazan do ramki pamieci;
odblokowuje ramke pamieci i ramke na urzadzeniu;
budzi pozostale procesy czekajace na ta operacje;
}
- zwalnia przydzielona ramke na dysku.
DEFINICJA: void swap_free(unsigned long entry)
Argumentem funkcji jest kod pozycji ramki na dysku.
Funkcja wylicza numer urzadzenia oraz numer ramki na urzadzeniu, sprawdza czy sa uzywane, zmniejsza licznik dowiazan do ramki, aktualizuje stan urzadzenia, i jesli urzadzenie, na ktorym zostala zwolniona ramka, ma wyzszy priorytet niz aktualnie wskazywane, to wskaznik jest przesuwany na poczatek listy priorytetowej.