58
Inżynieria
oprogramowania
www.sdjournal.org
Software Developer’s Journal 8/2006
Zarządzanie pamięcią
w systemach operacyjnych
W
poprzednim artykule (SDJ 7/2006) omówi-
liśmy podstawowy sposób zarządzania pa-
mięcią w trybie chronionym, czyli segmenta-
cję. Teraz przedstawię, jak wykorzystać pewnego rodza-
ju alternatywę jaką jest stronicowanie. Nie jest to mecha-
nizm w pełni alternatywny, ponieważ segmentacji nie
można wykluczyć w procesorach x86, a stronicowanie
można uznać jedynie za pewnego rodzaju nakładkę po-
zwalającą efektywniej wykorzystać pamięć RAM. Sama
nazwa wskazuje, że podstawą mechanizmu stronico-
wania jest strona, czyli obszar pamięci logicznej o z gó-
ry ustalonym rozmiarze. Obecne procesory mają możli-
wość programowego wybierania rozmiaru z 4KB, 4MB
i 2MB. Omówimy jedynie opcję 4KB, ponieważ pozosta-
łe rozmiary zostały wprowadzone w późniejszych mo-
delach procesorów Intela i nie można ich uznać za stan-
dardowe dla trybu chronionego. Przy włączonym stro-
nicowaniu translacja adresu przebiega dwuetapowo.
W pierwszej fazie odbywa się proces segmentacji. 16-
bitowy selektor segmentu wskazuje na rekord adresowy
w tablicy deskryptorów. Do uzyskanego w ten sposób
adresu podstawowego dodaje się 32-bitowe przesunię-
cie. Dopiero generowany w powyższy sposób adres li-
niowy podlega transformacji na fizyczny adres obiektu.
Transformacja ta stanowi sedno mechanizmu stronico-
wania, a jej istota polega na innej interpretacji adresu li-
niowego.
32-bitowe słowo adresowe dzieli się na trzy grupy.
W pierwszych dziesięciu najstarszych bitach przecho-
wywany jest numer rekordu w katalogu stron (ang. Pa-
ge Directory). Katalog zawiera 1024 takie rekordy, a każ-
dy z nich wskazuje na tablicę stron (ang. Page Tables).
Pierwszy rekord w katalogu stron wskazuje adres bazo-
wy tablicy stron o numerach 0 – 1023, drugi dotyczy ta-
blicy 1024 – 2047, a ostatni odnosi się do stron o nume-
rach 1 047 552 – 1 048 575. 10 kolejnych bitów adresu
liniowego (ang. Page) wskazuje na jeden z 1024 rekor-
dów w danej tablicy. Same rekordy w tablicach stron sta-
nowią z kolei wskaźniki do stron, z których każda ma wy-
miar 4KB. Adresowany obiekt ulokowany jest w obrębie
danej strony. Jego dokładną pozycję ustala się na pod-
stawie pola Offset – dwunastu najmłodszych bitów adre-
su liniowego (
2^2 = 4KB
). Gdy procesor odnajdzie już da-
ną pozycję w tablicy stron, pobiera jej wartość i dodaje
do niej wcześniej wyliczony Offset. W ten sposób otrzy-
mujemy adres fizczyny. Aby włączyć stronicowanie nale-
ży zapalić 31-szy bit w rejestrze kontrolnym
cr0
, a w re-
jestrze
cr3
podać fizyczny adres katalogu stron pamięci.
Listing 1 przedstawia funkcję odblokowującą stronicowa-
nie dla procesorów x86. Dodatkowo wykonujemy krótki
skok, tak jak sugeruje to Intel w swojej dokumentacji.
Tablice stron,
czyli mapy translacji adresów
Kolejną czynnością, jaką musimy wykonać jest stwo-
rzenie i wypełnienie katalogu stron pamięci.
Grzegorz Pełechaty
Autor jest od 7 lat programistą języka C. Interesuje się
zagadnieniami systemów operacyjnych, elektroniką i sie-
ciami neuronowymi. Obecnie pracuje nad projektem dar-
mowego systemu sieciowego, opartego o jądro monoli-
tyczne http://netcorelabs.org, oraz w pełni zgodnego ze
standardami POSIX. System jest rozpowszechniany na
warunkach licencji General Public License v2.
Kontakt z autorem: reqst@o2.pl
Słowniczek
• Pamięć wirtualna (ang. virtual memory) – technika pro-
gramowego, a także sprzętowego gospodarowania pa-
mięcią operacyjną RAM, pozwalająca na przydziela-
nie pamięci dla wielu procesów, zwalnianie jej i powtór-
ne przydzielanie, w ilości większej niż rzeczywista ilość
pamięci fizyczne zainstalowanej w komputerze poprzez
przeniesienie danych z ostatnio nie używanej pamięci
do pamięci masowej (np. twardego dysku) w sytuacji,
gdy procesor odwołuje się do danych z pamięci prze-
niesionej na dysk, przesuwa się te dane do pamięci w
wolne miejsce, a gdy brak wolnej pamięci zwalnia się ją
przez wyżej opisane przerzucenie jej na dysk.
• Przestrzeń adresowa procesu (ang. Address spa-
ce)– przestrzeń pamięci logicznej o z góry ustalo-
nym rozmiarze, w której proces może dokonywać
operacji alokacji bądź też zwalniania bloków.
• Urządzenie wymiany (ang. Swap device) – urządze-
nie potrafiące magazynować dane i udostępniać je
do odczytu. Są nimi urządzenia pamięci masowej,
np. dyski twarde.
• Mapowanie pamięci (ang. Memory mapping) – przy-
pisywanie adresu fizycznego adresowi wirtualnemu
przy pomocy jednostki stronicowania.
• Strona (ang. Page) – fragment pamięci logicznej
o z góry ustalonym rozmiarze (najczęściej 4KB).
Listing 1.
Odblokowanie stronicowania
void
paging_enable
(
void
)
{
__asm__
__volatile__
(
"movl %cr0, %eax
\n
"
"orl $0x80000000,%eax
\n
" "movl %eax, %cr0
\n
"
"jmp 1f
\n
" "1:
\n
" "movl $1f, %eax
\n
"
"jmp *%eax
\n
" "1:"
);
}
Zarządzanie pamięcią w systemach operacyjnych
59
www.sdjournal.org
Software Developer’s Journal 8/2006
Sam katalog ma rozmiar jednej strony (4KB), ale potrzebu-
jemy jeszcze tablic stron, aby zdefiniować przestrzeń adresową
jądra. W większości systemów jest to obszar 1GB, dlatego też
potrzebujemy 256 tablic. Tablice te określane są mianem ma-
py translacji adresów, ponieważ zawierają informacje w jaki spo-
sób adresy wirtualne mają zostać zinterpretowane. Wypełnianie
tablicy stron polega na wpisaniu odpowiedniego adresu fizycz-
nego wraz z atrybutami strony w konkretne miejsce tablicy. Aby
zdefiniować adres fizyczny dla pierwszych 4KB pamięci, należy
w pierwszej tablicy stron w pierwszych 4b wpisać ten adres wraz
z atrybutami. Dokładny opis atrybutów znajduje się na Listingu 2.
Listing 3 przedstawia w jaki sposób można stworzyć i wypeł-
nić katalog stron pamięci wraz z tablicami stron. Jak zapewne
zauważyliście, wypełniliśmy jedynie pierwszą tablicę. Resztę bę-
dziemy wypełniać dynamicznie podczas pracy systemu. Powód
jest prosty – gdy przypisujemy adres fizyczny do adresu logicz-
nego wyznaczonego przez tablice stron (ang. Mapping) deklaru-
jemy jednoznacznie, że dana ramka pamięci RAM jest już zajęta.
Dlatego przy inicjacji jądra rezerwujemy jedynie 4MB, aby zaosz-
czędzić pamięć. Ten obszar zwany jest obszarem nie stronico-
wanym (ang. non-paged area) i wykorzystywany jest głównie do
alkoacji danych statycznych, niezbędnych do prawidłowego funk-
cjonowania systemu. Najczęsciej znajdują się w nim tablice stron
dla przestrzeni adresowej jądra, katalog stron, pamięć dla kontro-
lera DMA oraz bitmapa zajętości ramek (o tym w dalszej części
artykułu). Obowiązuje również zasada, że w tym obszarze adres
wirtualny równy jest adresowi fizycznemu.
Aby dokończyć inicjację stronicowania wystarczy, że zała-
dujemy rejestr cr3 fizycznym adresem katalogu stron i wywo-
łamy funkcję odblokowującą
paging _ enable()
. Przykładowa
funkcja ustawiająca rejestr cr3 widoczna jest na Listingu 4. Ja-
ko jej argument podajemy nową wartość rejestru.
Alokacja ramek
Gdy mamy już w pełny działający mechanizm stronicowania,
możemy napisać prosty alokator pamięci, przydzielający ram-
ki, czyli odpowiedniki stron w pamięci fizycznej. Jak już wcze-
śniej wspomniałem podstawą alokatora będzie bitmapa zaję-
tości ramek. Jest to obszar pamięci, w którym każde 4KB pa-
mięci fizycznej jest reprezentowane przez 1bit. Gdy bit jest
zgaszony oznacza to, że ramka jest wolna, w przeciwnym ra-
zie użyta. Alokator ma za zadanie przeszukać całą bitmapę w
poszukiwaniu wolnej ramki, a gdy już znajdzie zapalić bit re-
prezentujący ją. Do tego celu potrzebujemy zdefiniować trzy
funkcje do manipulacji bitami w języku C. Są to:
set _ bit()
,
clr _ bit()
oraz
tst _ bit()
. Ich przykładowa implementacja
znajduje się na Listingu 5.
Jak widać funkcje zawierają przedrostek
_ _ inli-
ne _ _
dla przyspieszenia operacji. Dzięki tym funkcjom
możemy w prosty sposób napisać alokator ramek, któ-
rego implementacja znajduje się na Listingu 6. Zmien-
na
max _ frames
przechowuje ilość dostępnych ramek.
Jest wiele sposobów na określenie ilości pamięci zain-
Listing 2.
Opis podstawowych atrybutów strony
#define PAGE_PRESENT 0x1
// mówi systemowi, czy strona znajduje się w pamięci
// fizycznej, czy też na urządzeniu wymiany. Jeżeli bit ten
// jest zgaszony procesor przy próbie odwołania się do
// strony wygeneruje wyjątek 14 – błąd strony (ang. Page
// fault)
#define PAGE_READ_ONLY 0x0
// jeden z atrybutów określających prawa dostępu do
// strony, w tym wypadku zapalenie tego bitu
// oznacza, że strona jest wyłącznie do odczytu
#define PAGE_RDWR
// oznacza, że na stronie można dokonywać operacji zapisu
// i odczytu
0x2
#define PAGE_USER 0x4
// strona użytkownika (DPL3)
#define PAGE_SUPERVISOR 0x0
// strona kernela (DPL0)
Listing 3.
Tworzenie katalogu stron pamięci oraz tablic
stron dla 1GB przestrzeni adresowej jądra
unsigned
long
*
kpgt
=(
unsigned
long
*)
0x200000
;
unsigned
long
*
kpgd
=(
unsigned
long
*)
0x201000
;
void
create_paging_structures
(
void
)
{
int
i
;
kpgd
[
0
]
=
(
unsigned
long
)(
kpgt
)
|
PAGE_SUPERVISOR
|
PAGE_PRESENT
|
PAGE_RDWR
;
for
(
i
=
0
;
i
<
1024
;
i
++)
{
kpgt
[
i
]
=
(
uint32
)(
i
<<
12
)
|
PAGE_
SUPERVISOR
|
PAGE_RDWR
|
PAGE_PRESENT
;
}
for
(
i
=
1
;
i
<
256
;
i
++)
{
kpgd
[
i
]
=
(
uint32
)(
kpgt
+(
i
<<
12
))
|
PAGE_USER
|
PAGE_PRESENT
|
PAGE_RDWR
;
}
}
Listing 4.
Funkcja ładująca fizyczny adres katalogu stron
do rejestru kontrolnego cr3
void
set_pgd
(
void
*
pgd
)
{
__asm__
__volatile__
(
"movl %0, %%eax
\n
"
"movl %%eax, %%cr3"
::
"m"
(
pgd
));
}
Listing 5.
Przykładowa implementacja funkcji do
manipulacji bitami w pamięci
__inline__
void
set_bit
(
unsigned
char
tab
[]
,
unsigned
long
pos
)
{
tab
[
pos
/8
]
=
(
tab
[
pos
/8
]
|
(
1
<<
(
pos
%
8
)));
}
__inline__
void
clr_bit
(
unsigned
char
tab
[]
,
unsigned
long
pos
)
{
tab
[
pos
/8
]
=
(
tab
[
pos
/8
]
&
~
(
1
<<
(
pos
%
8
)));
}
__inline__
sint32
tst_bit
(
unsigned
char
tab
[]
,
unsigned
long
pos
)
{
if
((
tab
[
pos
/8
]
&
(
1
<<
(
pos
%
8
)))!=
0
)
return
1
;
else
return
0
;
}
60
Inżynieria
oprogramowania
www.sdjournal.org
Software Developer’s Journal 8/2006
Listing 6.
Implementacja alokatora ramek
stalowanej w komputerze, jednak najprościej skorzystać
z informacji zawartych w bloku informacyjnym multiboot.
bitmap _ cache
zawiera numer ostatniej wolnej ramki. Dzię-
ki temu nie musimy przeszukiwać od nowa całej bitma-
py za każdym wywołaniem funkcji alokującej. Jeżeli zwal-
niamy jakąś ramkę, jej numer jest zapamiętywany właśnie
w tej zmiennej. Cała bitmapa opisująca 4GB pamięci zaj-
muje dokładnie 256KB.
Alokacja pamięci sterty
Sterta to wydzielony obszar przestrzeni adresowej, w któ-
rym możemy dokonywać operacji alokacji oraz zwalniania
bloków pamięci. Jądro systemu obsługuje zazwyczaj dwa
algorytmy przydziału pamięci ze sterty. Pierwszy – to me-
chanizm, który zostanie wykorzystany przez kernel, drugi
natomiast służy do alokacji pamięci przez proces. Niekie-
dy stosowana jest metoda alokacji na poziomie użytkowni-
ka. Polega ona na zaimplementowaniu alokatora w biblio-
tece, dołączanej do programu dynamicznie lub statycznie
oraz umieszczeniu w jądrze jedynie podstawowych funk-
cji do alokacji i zwalniania ramek, a następnie mapowaniu
ich do przestrzeni adresowej. Teraz przedstawię kilka algo-
rytmów, które są najczęściej wykorzystywane w takich wy-
padkach.
Listy wolnych obszarów o rozmiarze potęg dwójki
W tym rozwiązaniu wykorzystuje się zbiór list wolnych ob-
szarów. Każda lista przechowuje bufory o określonym roz-
miarze, a wszystkie rozmiary są potęgami dwójki. Każdy
bufor ma nagłówek rozmiaru jednego słowa, który zmniej-
sza obszar użytkowy bufora o tę ilość miejsca. Gdy bu-
for jest wolny, w jego nagłówku przechowuje się wskaźnik
do następnego wolnego bufora. Gdy bufor jest przydzielo-
ny, jego nagłówek wskazuje na tę listę wolnych obszarów,
do której należy go zwrócić. W niektórych implementacjach
w nagłówku przechowuje się rozmiar bufora. Umożliwia to
wykorzystanie niektórych błędów, ale podprogram
free()
musi obliczać położenie listy wolnych obszarów dla te-
go rozmiaru. W celu przydzielenia pamięci klient wywołu-
je funkcję
malloc()
, przekazując jej zamawiany rozmiar jako
argument. Moduł przydzielający oblicza rozmiar najmniej-
szego bufora, który jest wystarczająco duży, aby zrealizo-
wać zlecenie. Obliczanie to polega na dodaniu do zamawia-
nego rozmiaru miejsca na nagłówek i zaokrągleniu wyniku
w górę do najbliższej potęgi dwójki. Moduł przydzielający
usuwa następnie bufor z odpowiedniej listy wolnych bufo-
rów, a wskaźnik do tej listy zapisuje w nagłówku. W wyniku
przekazuje wskaźnik do bajtu znajdującego się bezpośred-
nio za nagłówkiem bufora. Gdy klient zwalnia bufor, wy-
static
unsigned
char
*
bitmap
=(
uint8
*)
0x301000
;
static
unsigned
long
max_frames
;
static
unsigned
long
bitmap_cache
;
void
bitmap_BitIO
(
unsigned
long
n
,
unsigned
long
count
,
unsigned
char
on
)
{
unsigned
long
i
;
if
(
count
+
n
>
0x100000
)
{
puts
(
"Error : bitmap_BitIO() failed, out of RAM"
);
return
;
}
for
(
i
=
n
;
i
<
n
+
count
;
i
++)
{
if
(
on
)
{
set_bit
(
bitmap
+
i
/8,
i
%
8
);
}
else
{
clr_bit
(
bitmap
+
i
/8,
i
%
8
);
}
}
}
unsigned
long
bitmap_alloc
(
unsigned
long
count
)
{
unsigned
long
checked_frames
=
0
;
unsigned
long
cFrame
=
bitmap_cache
;
unsigned
long
passed
=
0
;
while
(
1
)
{
if
(
tst_bit
(
bitmap
+
cFrame
/8,
cFrame
%
8
)==
0
)
{
passed
++;
if
(
passed
==
count
)
{
bitmap_BitIO
(
cFrame
-
count
+
1,
count
, 1
);
if
(
cFrame
+
1
<=
max_frames
)
{
bitmap_cache
=
cFrame
+
1
;
}
else
{
bitmap_cache
=
0
;
return
(
cFrame
-
count
+
1
);
}
}
else
{
passed
=
0
;
}
cFrame
++;
if
(
cFrame
>
max_frames
)
{
cFrame
=
0
;
}
checked_frames
++;
if
(
checked_frames
>=
max_frames
)
{
return
0
;
}
}
}
void
bitmap_free
(
unsigned
long
n
,
unsigned
long
count
)
{
bitmap_BitIO
(
n
,
count
, 0
);
bitmap_cache
=
n
;
}
Listing 7.
Struktury natywnego alokatora pamięci
typedef
long
sint32
;
typedef
unsigned
long
uint32
;
struct
free_cache_slice
{
uint32
s_addr
;
uint32
s_size
;
struct
free_cache_slice
*
n_slice
;
struct
free_cache_slice
*
p_slice
;
}
;
struct
used_cache_slice
{
uint32
s_size
;
}
;
struct
cache_area
{
uint32
a_addr
;
uint32
a_size
;
uint32
a_used
;
struct
free_cache_slice
*
fsl
;
spinlock
a_mutex
;
}
;
62
Inżynieria
oprogramowania
www.sdjournal.org
Software Developer’s Journal 8/2006
Listing 8.
Implementacja natywnego alokatora
void
cache_pushInList
(
struct
cache_area
*
cache_area
,
struct
free_cache_slice
*
slice
)
{
cache_area
->
fsl
->
p_slice
->
n_slice
=
slice
;
slice
->
p_slice
=
cache_area
->
fsl
->
p_slice
;
slice
->
n_slice
=
cache_area
->
fsl
;
cache_area
->
fsl
->
p_slice
=
slice
;
}
void
cache_popFromList
(
struct
free_cache_slice
*
slice
)
{
slice
->
p_slice
->
n_slice
=
slice
->
n_slice
;
slice
->
n_slice
->
p_slice
=
slice
->
p_slice
;
}
struct
cache_area
*
create_cache
(
uint32
a_addr
,
uint32
a_size
)
{
uint32
t_size
=
a_size
-
sizeof
(
struct
cache_area
);
uint32
t_addr
=
a_addr
+
sizeof
(
struct
cache_area
);
struct
cache_area
*
cache_area
=
(
struct
cache_area
*)
a_addr
;
cache_area
->
a_addr
=
t_addr
;
cache_area
->
a_size
=
t_size
;
cache_area
->
a_used
=
0
;
cache_area
->
fsl
=(
struct
free_cache_slice
*)
t_addr
;
cache_area
->
fsl
->
s_addr
=
t_addr
;
cache_area
->
fsl
->
s_size
=
t_size
;
cache_area
->
fsl
->
n_slice
=
cache_area
->
fsl
->
p_slice
=
cache_area
->
fsl
;
futex_cls
(&(
cache_area
->
a_mutex
));
return
cache_area
;
}
void
*
cache_popSlice
(
struct
cache_area
*
cache_area
,
uint32
m_size
)
{
uint32
toreturn
=
0
;
uint32
p_size
=
0
;
uint32
t_size
;
uint32
t_na
=
0
;
t_size
=
m_size
+
sizeof
(
struct
used_cache_slice
);
struct
free_cache_slice
*
free_slice
;
free_slice
=
cache_area
->
fsl
->
p_slice
;
do
{
free_slice
=
free_slice
->
n_slice
;
if
(
free_slice
->
s_size
>=
t_size
)
{
struct
free_cache_slice
copy
;=
copy
.
n_slice
=
free_slice
->
n_slice
;
copy
.
p_slice
=
free_slice
->
p_slice
;
copy
.
s_size
=
free_slice
->
s_size
;
if
(
free_slice
->
s_size
>
t_size
&&
(
free_slice
->
s_size
<
t_size
+
0x10
)
&&
free_slice
!=
cache_area
->
fsl
)
{
t_size
=
free_slice
->
s_size
;
}
else
if
(
free_slice
->
s_size
>=
t_size
&&
(
free_
slice
->
s_size
<
t_size
+
0x10
)
&&
free_
slice
==
cache_area
->
fsl
)
{
break
;
}
t_na
=(
free_slice
->
s_addr
+
free_slice
->
s_size
-
t_size
);
struct used_cache_slice *new_slice
=
(
struct used_cache_slice *
)
t_na
;
new_slice
->
s_size
=
t_size
;
toreturn
=
t_na
;
if
(
new_slice
->
s_size
==
copy
.
s_size
)
{
cache_popFromList
(&
copy
);
}
else
{
free_slice
->
s_size
-=
t_size
;
}
break
;
}
}
while
(
free_slice
->
n_slice
!=(
struct
free_cache_slice
*)
cache_area
->
fsl
);
return
(
void
*)
toreturn
;
}
void
cache_fitSlicePair
(
struct
cache_area
*
cache_area
,
struct
used_cache_slice
*
m_slice
,
struct
free_cache_slice
**
left
,
struct
free_cache_slice
**
right
)
{
uint32
t_size
=
m_slice
->
s_size
;
uint32
t_addr
=(
uint32
)
m_slice
;
struct
free_cache_slice
*
t_slice
=
cache_area
->
fsl
->
p_slice
;
do
{
t_slice
=
t_slice
->
n_slice
;
if
(
t_slice
->
s_addr
==
t_addr
+
t_size
)
{
*
right
=
t_slice
;
}
else
if
(
t_slice
->
s_addr
+
t_slice
->
s_size
==
t_addr
)
{
*
left
=
t_slice
;
}
}
while
(
t_slice
->
n_slice
!=
cache_area
->
fsl
);
}
void
cache_pushSlice
(
struct
cache_area
*
cache_area
,
struct
used_cache_slice
*
m_slice
)
{
struct
free_cache_slice
*
left
=
null
,
*
right
=
null
;
cache_fitSlicePair
(
cache_area
,
m_slice
,
&
left
,
&
right
);
if
(
left
)
{
left
->
s_size
+=
m_slice
->
s_size
;
if
(
right
)
{
left
->
s_size
+=
right
->
s_size
;
cache_popFromList
(
right
);
}
}
else
if
(
right
)
{
uint32
old_size
=
m_slice
->
s_size
;
struct
free_cache_slice
*
nSlice
=(
struct
free_cache_slice
*)
m_slice
;
nSlice
->
s_size
=
old_size
+
right
->
s_size
;
nSlice
->
s_addr
=(
uint32
)
nSlice
;
cache_popFromList
(
right
);
cache_pushInList
(
cache_area
,
nSlice
);
}
else
{
uint32
old_size
=
m_slice
->
s_size
;
struct
free_cache_slice
*
nSlice
=(
struct
free_cache_slice
*)
m_slice
;
nSlice
->
s_size
=
old_size
;
nSlice
->
s_addr
=(
uint32
)
nSlice
;
cache_pushInList
(
cache_area
,
nSlice
);
} }
sint32
cache_expand
(
struct
cache_area
*
,
cache_area
,
uint32
,
ex_size
)
{
struct
used_cache_slice
*
m_slice
=(
struct
used_cache_slice
*)(
cache_area
->
a_addr
+
cache_area
->
a_size
);
m_slice
->
s_size
=
ex_size
;
cache_area
->
a_size
+=
ex_size
;
cache_pushSlice
(
cache_area
,
m_slice
);
}
sint32
cache_free
(
struct
cache_area
*
,
cache_area
,
void
*
,
m_addr
)
{
cache_pushSlice
(
cache_area
,
m_addr
-
0x4
);
}
63
Zarządzanie pamięcią w systemach operacyjnych
www.sdjournal.org
Software Developer’s Journal 8/2006
wołuje podprogram
free()
, przekazując mu jako argument
wskaźnik uzyskany od funkcji
malloc()
. Użytkownik nie mu-
si określić rozmiaru zwalnianego bufora. Charakterystycz-
ne jest to, że zwalnia się cały bufor otrzymany od funkcji
malloc
. Nie ma możliwości zwolnienia jedynie części przy-
dzielonego bufora. Podprogram
free()
przesuwa wskaźnik
o cztery bajty do tyłu, żeby odczytać nagłówek. Z nagłów-
ka odczytuje wskaźnik do listy wolnych obszarów i umiesz-
cza bufor na tej liście. Podczas inicjowania modułu przy-
dziela się wstępnie pewną liczbę buforów do każdej listy al-
bo pozostawia się puste i wywołuje moduł przydziału stron,
żeby wypełnić je w miarę potrzeb. Jeśli w trakcie działania
systemu pewna lista opróżni się, moduł przydzielający mo-
że na trzy sposoby obsłużyć nowe zlecenie
malloc()
doty-
czące tego rozmiaru:
• wstrzymać realizację zlecenia, dopóki nie zwolni się bufor
odpowiedniego rozmiaru
• zrealizować zlecenie, wykorzystując większy bufor, rozpo-
czynając wyszukiwanie od następnej listy i kontynuując aż
do do napotkania listy niepustej
• uzyskać dodatkową pamięć od modułu przydziału stron
i utworzyć z niej dodatkowe bufory zamawianego rozmiaru
Opisany algorytm jest prosty i wystarczająco szybki. Je-
go urok polega na tym, że unika się długiego liniowego wy-
szukiwania wolnych obszarów i całkowicie eliminuje się pro-
blem fragmentacji. Jeśli bufor jest dostępny, pesymistyczny
czas wykonania algorytmu jest dobrze określony. Są rów-
nież poważne wady. Zaokrąglanie rozmiaru zleceń do naj-
bliższej potęgi dwójki często zostawia wiele niewykorzy-
stanego miejsca w buforze, powodując słabe wykorzysta-
nie pamięci. Problem pogarsza się jeszcze wobec koniecz-
ności przechowywania w przydzielonych buforach nagłów-
ka. Wiele zleceń dotyczy buforów o rozmiarze będącym do-
kładną potęga dwójki. W takich wypadkach straty wynoszą
prawie 100%, ponieważ zlecenie trzeba zaokrąglić do na-
stępnej potęgi dwójki, tak aby zrobić miejsce na nagłówek.
Przykładowo zlecenie rozmiaru 512 bajtów spowoduje zu-
życie bufora wielkości 1024 bajtów. Nie ma możliwości łą-
czenia sąsiednich wolnych buforów, żeby zrealizować więk-
sze żądania. Na ogół rozmiar każdego bufora nie zmienia
się w czasie jego istnienia. Jedyną elastycznością jest to, że
większe bufory można czasem wykorzystać do zrealizowa-
nia mniejszych zleceń.
Natywny algorytm przydziału pamięci ze sterty
Dla alokacji pamięci kernela należy skorzystać z algoryt-
mu, który oferuje nam najmniejszą prędkość oczekiwania
na zrealizowanie zlecenia, a zarazem nie powoduje frag-
mentacji pamięci. Przedstawię teraz algorytm, który spełnia
te wymagania i jest coraz częściej używany w nowych sys-
temach operacyjnych. Jego struktura opiera się o listy wol-
nych i zajętych obszarów. Gdy klient zechce zaalokować pa-
mięć, funkcja alokacyjna przeszukuje jedynie wolne obszary
w celu odnalezienia tego, którego rozmiar jest wystarczają-
co duży do wykonania zlecenia. Natomiast, gdy klient zwal-
nia pamięć, wolny obszar trafia z powrotem do listy i sca-
la się z ze stykającymi obszarami w celu zmaksymalizowa-
nia swojej objętości. Taki sposób rozwiązania problemu jest
wystarczająco szybki i elastyczny, aby został wykorzystany
w naszym jądrze. Listing 7 zawiera definicję struktur, nie-
zbędnych do napisania prostego alokatora, którego imple-
mentacja przedstawiona jest na Listingu 8. Aby wykorzystać
ten sposób alokacji pamięci, niezbędne jest utworzenie spe-
cjalnego obszaru za pomocą funkcji
create _ cache()
. Jako
paramtery podajemy początek sterty oraz jej rozmiar. Przy
każdym kolejnym wywołaniu funkcji alokującej lub zwal-
niającej dany blok pamięci będziemy musieli podać adres
wcześniej utworzonej struktury reprezentującej stertę, do
której odnoszą się te operacje.
Co zrobić, gdy kończy nam się RAM?
Istnieją dwa sposoby na rozwiązanie tego problemu. Jądro
może zasygnalizować brak dostępnych zasobów i odmówić
dalszego wykonywania. Takie działanie nie jest jednak opty-
malne, ponieważ jesteśmy w stanie przenieść nieużywane
obszary RAM na urządzenie wymiany a następnie wyko-
rzystać w ten sposób zwolnioną pamięć na nowe dane. Taki
mechanizm nazywamy algorytmem wymiany. Jego rola po-
lega na odnalezieniu najrzadziej używanych fragmentów pa-
mięci fizycznej, a następnie przeniesieniu ich na urządzenie
pamięci masowej. Jest to najczęściej realizowane poprzez
wyjątek braku strony, który zostaje wywołany przy odwoła-
niu się do strony nieistniejącej lub też nie będącej w danym
czasie w pamięci fizycznej. Dzięki temu stronę można spro-
wadzić z powrotem i ponowić wykonanie instrukcji, która
wcześniej spowodowała wyjątek. Taki mechanizm jest sed-
nem pamięci wirtualnej.
Podsumowanie
W tej części kursu omówiliśmy algorytmy przydziału pa-
mięci, dowiedzieliśmy się czym jest stronicowanie oraz zro-
zumieliśmy działanie alokatora pamięci. Wszystkie te infor-
macje możemy wykorzystać w naszym jądrze, aby było
ono bardziej rozwinięte i profesjonalne. Pamiętajcie, że do-
brze napisany moduł zarządzania pamięcią jest podstawą
sukcesu naszego systemu. W części ostatniej przedstawię
jak zaimplementować wieloprocesowość (ang. Multitasking)
w sposób programowy (poprzez zmianę stosów) oraz
sprzętowy z wykorzystaniem Segmentów Stanu Zadania
(TSS). n
Listing 8 cd.
Implementacja natywnego alokatora
void
*
cache_alloc
(
struct
cache_area
*
,
cache_area
,
uint32
,
m_size
)
{
void
*
toreturn
=
cache_popSlice
(
cache_area
,
m_size
);
if
(
toreturn
)
{
toreturn
+=
0x4
;
}
return
toreturn
;
}
Literatura
• [1] Piotr Metzger, Michał Siemieniacki, Anatomia PC wydanie
IX, Helion 2004,
• [2] Uresh Vahalia, Jądro systemu Unix – nowe horyzonty, Wy-
dawnictwa Naukowo-Techniczne Warszawa 2001