Systemy Operacyjne – semestr drugi

Wyk ad dziesi ty

ł

ą

Zarz dzanie pami ci w Linuksie

ą

ę ą

Podsystem zarz dzania pami ci jest jedn z najbardziej skomplikowanych cz

ci j dra Linuksa. Przyczyn takiego stanu rzeczy jest to, e system ten jest tworzony

ą

ę ą

ą

ęś

ą

ą

ż

z my l o pracy na wielu platformach, w których obs uga pami ci mo e diametralnie si ró ni . Ró nice nie tylko dotycz wielko ci adresu, ale równie sposobu

ś ą

ł

ę

ż

ę

ż ć

ż

ą

ś

ż

zarz dzania ni . Cz

procesorów, jak np.: procesory Intela wykorzystuje segmentacj , inne w ogóle nie korzystaj z tej techniki, jak np.: procesory Alpha. Wi kszo

ą

ą

ęść

ę

ą

ę

ść

ze wspó czesnych popularnych systemów komputerowych pozwala na korzystanie z pami ci wirtualnej, ale dedykowane systemy czasu rzeczywistego i systemy

ł

ę

wbudowane (ang. embedded) nie korzystaj z niej, gdy jest to technika za wolna jak na wymagania czasowe, które musz spe nia . Te wszystkie cech poszczególnych

ą

ż

ą

ł

ć

architektur musz uwzgl dnia twórcy kodu j dra Linuksa.

ą

ę

ć

ą

J dro Linuksa korzysta w zarz dzaniu pami ci ze sprz towego mechanizmu stron, którego obecno jest cech wspóln wi kszo ci architektur na których Linux jest

ą

ą

ę ą

ę

ść

ą

ą

ę

ś

dost pny. Adresowanie stron jest trójpoziomowe (czteropoziomowe od wersji 2.6.11) i u ywa Globalnego Katalogu Stron, Po redniego Katalogu Stron oraz Tablicy Stron.

ę

ż

ś

W architekturach 32 – bitowych Po redni Katalog Stron sk ada si tylko z jednej pozycji. W przypadku procesorów Intela wykorzystywany jest cz

ciowo mechanizm

ś

ł

ę

ęś

segmentacji, g ównie do ochrony pami ci. Wykorzystywanych jest pi

rodzajów deskryptorów opisuj cych segmenty pami ci: deskryptor kodu j dra, deskryptor danych

ł

ę

ęć

ą

ę

ą

j dra, deskryptor kodu u ytkownika, deskryptor danych u ytkownika i deskryptor lokalnej tablicy deskryptorów (LDT). Cztery pierwsze rodzaje deskryptorów s u

do

ą

ż

ż

ł żą

zdefiniowania segmentów które obejmuj ... ca dost pn pami ci. Segmenty ró ni si prawami dost pu do pami ci jakie przys uguj j dru i procesom u ytkownika.

ą

łą

ę

ą

ę

ż ą

ę

ę

ę

ł

ą ą

ż

Z ka d stron fizyczn (ramk ) w pami ci komputera jest zwi zana struktura typu

ż ą

ą

ą

ą

ę

ą

struct page, zawieraj ca dane o stronie umieszczone w tej ramce. Do tych danych

ą

nale

mi dzy innymi: licznik odwo a do strony, flagi okre laj ce stan strony, wska nik na struktur opisuj c przestrze adresow , na któr dana strona jest

żą

ę

ł ń

ś

ą

ź

ę

ą ą

ń

ą

ą

odwzorowywana, oraz adres wirtualny danej strony. Nie wszystkie ramki

1

i strony w pewnych architekturach s traktowane jednakowo. Linux wprowadza podzia

ą

ł

pami ci fizycznej na trzy strefy: ZONE_DMA – strefa grupuj ca strony i ramki nadaj ce si do realizacji operacji DMA (zasz o

z czasów urz dze ISA, obejmuje

ę

ą

ą

ę

ł ść

ą

ń

pierwsze 16MB pami ci fizycznej), ZONE_NORMAL – strefa zwyk ych odwzorowa , ZONE_HIGHMEM – strefa grupuj ca strony w wysokiej pami ci (dla architektur

ę

ł

ń

ą

ę

x86 jest to pami

fizyczna powy ej 896MB, dla innych architektur ta strefa jest pusta), które nie s domy lnie odwzorowywane w przestrzeni adresowej. J dro, je li

ęć

ż

ą

ś

ą

ś

nie jest to okre lone w wywo aniu, przydziela domy lnie pami

ze strefy ZONE_NORMAL, chyba e nie ma tam ju wolnych stron. Wówczas strony s przydzielane

ś

ł

ś

ęć

ż

ż

ą

z dowolnej z pozosta ych stref. Z ka d stref (jest ich maksymalnie trzy) skojarzone s struktury typu

ł

ż ą

ą

ą

struct zone. S to stosunkowo du e struktury i zawieraj takie

ą

ż

ą

informacje, jak: nazwa strefy: „DMA”, „Normal”, „HighMem” i liczba wolnych ramek w strefie (j dro stara si , aby ta liczba nie spad a poni ej warto ci, która jest

ą

ę

ł

ż

ś

umieszczona w polu pages_min). Struktura ta zawiera równie rygiel p tlowy

ż

ę

lock, który s u y do jej ochrony, nie blokuje natomiast dost pu do poszczególnych stron

ł ż

ę

znajduj cych si w strefie.

ą

ę

Ze wzgl du na wymagania urz dze maj cych dost p do pami ci za pomoc DMA, oraz celem zminimalizowania zmian zawarto ci buforów TLB j dro Linuksa stara si

ę

ą

ń

ą

ę

ę

ą

ś

ą

ę

przydziela pami

obszarami ci g ymi, których rozmiar stanowi wielokrotno rozmiaru strony wyra on pot g dwójki. Zarz dzaniem tym przydzia em i zwalnianiem

ć

ęć

ą ł

ść

ż

ą

ę ą

ą

ł

zajmuje si mechanizm, dzia aj cy w oparciu o algorytm bli niaków (

ę

ł ą

ź

ang. buddy system). Algorytm ten grupuje w odpowiednich strukturach obszary wolnych ramek,

które s rozmieszczone w

ą

sposób ci g y w pami ci i stara si spe nia

dania przydzia u pami ci przydzielaj c te obszary lub w razie konieczno ci dziel c je na

ą ł

ę

ę

ł

ć żą

ł

ę

ą

ś

ą

mniejsze. Je li w

ś

wyniku zwolnienia pami ci powstan dwa wolne obszary, które przylegaj do siebie, to s one czone w jeden wi kszy obszar. Ten niskopoziomowy

ę

ą

ą

ą

łą

ę

mechanizm alokacji udost pnia pi

funkcji, które umo liwiaj przydzielenie pami ci:

ę

ęć

ż

ą

ę

alloc_pages(gfp_mask, order) – przydziela

stron pami ci i zwraca wska nik na struktur

ę

ź

ę page opisuj c pierwsz z nich.

ą ą

ą

alloc_page(gfp_mask) – przydziela pojedyncz stron i zwraca wska nik na jej struktur

ą

ę

ź

ę page,

get_zeroed_page(gfp_mask) – przydziela pojedyncz stron , wype nia j zerami i zwraca jej adres logiczny (stosowana przy przydziale pami ci dla procesów

ą

ę

ł

ą

ę

u ytkownika),

ż

__get_free_page(gfp_mask) – przydziela pojedyncz stron i jej adres logiczny,

ą

ę

__get_free_pages(gfp_mask, order) – przydziela

stron i zwraca adres logiczny pierwszej z nich.

Je li dysponujemy wska nikiem na struktur

ś

ź

ę page, to adres logiczny strony, któr ona opisuje mo emy uzyska pos uguj c si funkcj

ą

ż

ć

ł

ą

ę

ą page_address(). Warto ci jakie

ś

mo e przyjmowa argument

ż

ć

gfp_mask b d opisane pó niej. Po wykonaniu operacji przydzielania nale y sprawdzi , czy si ona powiod a. Do zwalniana przydzielonej

ę ą

ź

ż

ć

ę

ł

przez powy sze funkcje pami ci s u

inne funkcje alokatora:

ż

ę

ł żą

void _free_pages(struct page *page, unsigned int order) – zwalnia grup

ę

stron rozmieszczonych w sposób ci g y, identyfikowan struktur

ą ł

ą

ą page

pierwszej z tych stron,

void free_pages(unsigned long addr, unsigned int order) – zwalnia grup

ę

stron identyfikowan adresem pierwszej z nich,

ą

void free_page(unsigned long addr) – zwalnia pojedyncz stron pami ci.

ą

ę

ę

Zwalniaj c pami

nale y pami ta o przekazaniu prawid owych argumentów do funkcji zwalniaj cych pami

. Warto ci argumentów wywo a tych funkcji nie s

ą

ęć

ż

ę ć

ł

ą

ęć

ś

ł ń

ą

weryfikowane. Nale y te unika wycieków pami ci. Je li potrzebny jest nam fizycznie ci g y obszar pami ci o dowolnym rozmiarze, to mo emy skorzysta z funkcji

ż

ż

ć

ę

ś

ą ł

ę

ż

ć

kmalloc, której prototyp jest nast puj cy:

ę

ą

void *kmalloc(size_t size, int flags). Funkcja to przydziela tyle pami ci, ile jest okre lone parametrem

ę

ś

size, lub wi cej, nigdy

ę

za mniej. Je li przydzia si nie powiedzie, to zwracana jest warto

NULL. Do zwolnienia pami ci przydzielonej przez

ś

ś

ł

ę

ść

ę

kmalloc i tylko takiej pami ci s u y funkcja

ę

ł ż

void kfree(const void *ptr); Nale y zadba o poprawno

przekazywanych jej wywo aniu argumentów, gdy funkcja sprawdza jedynie czy przekazany jej wska nik nie

ż

ć

ść

ł

ż

ź

ma warto ci NULL. Argument

ś

gfp_mask okre la znacznik identyfikuj cy charakter operacji przydzielania pami ci. Znaczniki podzielone s na trzy kategorie:

ś

ą

ę

ą

modyfikatory czynno ciowe, modyfikatory stref i znaczniki typu. Modyfikatory czynno ciowe s to sta e okre laj ce, jakie czynno ci podczas przydzielania pami ci mo e

ś

ś

ą

ł

ś

ą

ś

ę

ż

wykona alokator (zawieszanie,

ć

operacje wej cia – wyj cia). Modyfikatory stref (s tylko dwa – dla stron DMA i nale

cych do pami ci wysokiej) okre laj z której strefy

ś

ś

ą

żą

ę

ś

ą

pami

b dzie przydzielana. Modyfikatory obu kategorii mo na czy za pomoc operatora sumy logicznej. Znaczniki typów s takimi w a nie sumami logicznymi.

ęć

ę

ż

łą

ć

ą

ą

ł ś

Poniewa te znaczniki s najcz

ciej wykorzystywane zostan tu szerzej omówione:

ż

ą

ęś

ą

GFP_ATOMIC – przydzia wysokiego priorytetu, bez mo liwo ci zawieszenia procesu wywo uj cego. Z tego znacznika korzystaj g ownie procedury obs ugi

ł

ż

ś

ł ą

ą ł

ł

przerwa i dolne po ówki,

ń

ł

GFP_NOIO – przydzia z mo liwo ci zawieszenia, ale bez mo liwo ci inicjalizacji operacji dost pu do dysku. Stosowany w kodzie blokowych operacji

ł

ż

ś ą

ż

ś

ę

1

które w przypadku Linuksa najcz

ciej nazywane s stronami fizycznymi.

ęś

ą

1

Systemy Operacyjne – semestr drugi

wej cia wyj cia, aby wyeliminowa zjawisko zakleszczenia,

ś

ś

ć

GFP_NOFS – przydzia z mo liwo ci zawieszenia i inicjalizacji operacji dost pu do dysku, ale bez mo liwo ci korzystania z systemu plików.

ł

ż

ś ą

ę

ż

ś

GFP_KERNEL – zwyk y przydzia z mo liwo ci zawieszenia, stosowany w kontek cie procesu.

ł

ł

ż

ś ą

ś

GFP_USER – zwyk y przydzia z mo liwo ci zawieszenia, stosowany w przydzia ach inicjowanych przez procesy u ytkownika.

ł

ł

ż

ś ą

ł

ż

GFP_HIGHUSER – jak wy ej, ale pami

jest przydzielana w obszarze wysokim.

ż

ęć

GFP_DMA – przydzia pami ci, która mo e by wykorzystana w trybie DMA.

ł

ę

ż

ć

Je li obszar, który chcemy aby zosta nam przydzielony nie musi by ci g y fizycznie, ale logicznie, to mo emy u y funkcji

ś

ł

ć

ą ł

ż

ż ć

vmalloc, o prototypie: void *vmalloc

(unsigned long size). Pami

przydzielona t funkcj musi by zwolniona przy pomocy

ęć

ą

ą

ć

vfree: void vfree(void *addr).

J dra systemów operacyjnych bardzo cz sto przydzielaj i zwalniaj pami

operacyjn na struktury danych. Poniewa proces alokacji pami ci jest zawsze

ą

ę

ą

ą

ęć

ą

ż

ę

czasoch onny mo na okre li bufory takich struktur podczas inicjalizacji j dra i w razie konieczno ci stworzenia jednej ze struktur takiego rodzaju, po prostu przekaza

ł

ż

ś ć

ą

ś

ć

wska nik do niej, natomiast po zwolnieniu nie trzeba jej niszczy tylko umie ci z powrotem we wspomnianym buforze. Na tym pomy le bazuje alokator plastrowy

ź

ć

ś ć

ś

2

(ang. slab), który zosta wynaleziony przez firm SUN Microsystem i po raz pierwszy wykorzystany w ich systemie operacyjnym Solaris. Budowie takiego alokatora

ł

ę

przy wieca y nast puj ce za o enia:

ś

ł

ę

ą

ł ż

Podstawowe struktury danych s cz sto przydzielane i zwalniane, wi c korzystne jest ich buforowanie.

ą

ę

ę

Cz ste przydzia y i zwolnienia pami ci prowadz do fragmentacji. Aby j wyeliminowa pami w której b d si znajdowa struktury powinna by ci g a.

ę

ł

ę

ą

ą

ć

ęć

ę ą

ę

ć

ć

ą ł

Lista struktur wolnych pozwala na zwi kszenie wydajno ci operacji przydzia u i zwalniania pami ci.

ę

ś

ł

ę

Je li cz

bufora uczyni specyficzn dla danego procesora, to przydzia y i zwalniania pami ci da si przeprowadzi bez blokowania procesów.

ś

ęść

ć

ą

ł

ę

ę

ć

Obiekty (struktury) przechowywane w buforze mog by kolorowane, co zapobiega odwzorowywaniu tych samych fragmentów bufora do ró nych obiektów.

ą

ć

ż

W Linuksie alokator palstrowy tworzy pami ci podr czne dwóch rodzajów: ogólne i dedykowane. Z pami ci ogólnych korzysta on sam, z dedykowanych – pozosta e

ę

ę

ę

ł

cz

ci j dra. Na ka dy typ buforowanej struktury przypada jedna dedykowana pami

podr czna. Nazwa tej pami ci wskazuje jakiego rodzaju struktury s w niej

ęś

ą

ż

ęć

ę

ę

ą

przechowywane (np.: task_struct_cachep). Pami

podr czna jest podzielona na plastry, które sk adaj si z jednej (zazwyczaj) lub wielu ramek. Ka dy z

ęć

ę

ł

ą

ę

ż

plastrów

zawiera pewn liczb buforowanych struktur, które s nazywane obiektami. Plastry mo na podzieli na puste, pe ne i cz

ciowo zaj te. Struktur s przydzielane

ą

ę

ą

ż

ć

ł

ęś

ę

ą

w pierwszej kolejno ci z plastrów cz

ciowo zaj tych. Je li takich nie ma, to z pustych. Pami

podr czn opisuje struktura

ś

ęś

ę

ś

ęć

ę

ą

kmem_cache_s, a poszczególne plastry są

reprezentowane przez deskryptory, które s strukturami typu

ą

struct slab. Te deskryptory s przechowywane w ogólnych pami ciach podr cznych lub bezpo rednio

ą

ę

ę

ś

w plastrach. Nowy plaster jest tworzony za pomoc funkcji

ą

kmem_getpages(), a niszczony przy pomocy kmem_freepages(). Tworzeniem i zwalnianiem plastrów zajmuje

si automatycznie alokator plastrowy. Programista j dra mo e stworzy w asn dedykowan pami

podr czn korzystaj c z funkcji

ę

ą

ż

ć

ł

ą

ą

ęć

ę

ą

ą

kmem_cache_create(). Pierwszy

argument wywo ania tej funkcji okre la, jak maj by przydzielane obiekty w tej pami ci (czy ich rozmiary maj by wyrównywane do wielko ci linii sprz towej pami ci

ł

ś

ą

ć

ę

ą

ć

ś

ę

ę

podr cznej, czy strony, na których te obiekty b d umieszczone b d przydzielane ze strefy DMA, itd.). Dwa kolejne okre laj adres funkcji b d cych destruktorem

ę

ę ą

ę ą

ś

ą

ę ą

i konstruktorem struktur przechowywanych w pami ci – st d te struktury nazywane s obiektami. Najcz

ciej te argumenty maj warto NULL. Pami

podr czna

ę

ą

ą

ęś

ą

ść

ęć

ę

mo e zosta usuni ta, je li zwolnione s wszystkie plastry znajduj ce si w niej i nie jest do niej wykonywany wspó bie ny dost p przez inne w tki. Usuni cie jej

ż

ć

ę

ś

ą

ą

ę

ł

ż

ę

ą

ę

odbywa si za pomoc funkcji

ę

ą

kmem_cache_destroy(). Obiekty z tej pami ci s przydzielane przez

ę

ą

kmem_cache_alloc(), a zwalniane przez kmem_cache_free().

Odmian pami ci podr cznych tworzonych przez alokator plastrowy s pule pami ci (

ą

ę

ę

ą

ę

ang. memory pools). Maj one na celu zapewnienie, e dla krytycznych partii

ą

ż

kodu, dla których przydzia pami ci nie mo e zawie zawsze b d dost pne wolne obszary pami ci. Pula pami ci opisywana jest przez typ

ł

ę

ż

ść

ę ą

ę

ę

ę

mempool_t i mo e zosta

ż

ć

stworzona przez wywo anie

ł

mempool_create(). Funkcja ta przyjmuje cztery argumenty wywo ania. Pierwszy okre la minimaln liczb obiektów, które pula powinna

ł

ś

ą

ę

zawsze posiada , dwa nast pne s wska nikami do funkcji przydzielaj cej i funkcji zwalniaj cej obiekty, a ostatni argument jest wska nikiem na dane przekazywane

ć

ę

ą

ź

ą

ą

ź

do tych funkcji. Programista mo e napisa w asne funkcje alokuj ce i dealokuj ce obiekty z puli, lub u y funkcji

ż

ć

ł

ą

ą

ż ć

mempool_alloc() i mempool_free(), które mogą

korzysta z

ć funkcji dost pnych dla alokatora plastrowego. Pul mo na rozszerzy za pomoc

ę

ę

ż

ć

ą memory_resize(), a usun

za pomoc

ąć

ą memory_destroy().

Pisz c kod wywo a systemowych, czy innych cz

ci j dra korzystaj cych ze stosu procesu u ytkownika w j drze, nale y pami ta , e jest to bardzo ograniczona pod

ą

ł ń

ęś

ą

ą

ż

ą

ż

ę ć ż

wzgl dem wielko ci struktura, a jej przekroczenie nie jest kontrolowane. Nie zaleca si tworzenia du ych struktur danych na stosie, aby nie spowodowa jego

ę

ś

ę

ż

ć

przepe nienia, które mo e mie bardzo powa ne konsekwencje.

ł

ż

ć

ż

Strony nale

ce do strefy pami ci wysokiej nie s domy lnie odwzorowane w przestrzeni adresowej j dra. Mo emy proces odwzorowania przeprowadzi samodzielnie.

żą

ę

ą

ś

ą

ż

ć

Istniej dwa rodzaje takiego odwzorowania: trwa e, które jest dokonywane za pomoc funkcji

ą

ł

ą

kmap() i likwidowane za pomoc

ą kumap() oraz czasowe (nie powoduj ce

ą

zawieszenia) dokonywane za pomoc

ą kmap_atomic() i likwidowane za pomoc

ą kumap_atomic().

2

zwany te w polskiej literaturze alokatorem p ytowym.

ż

ł

2