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