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: [e-mail]

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