SO2_wyklad_10.sxw

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

ł żą

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

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

ś ą

które w przypadku Linuksa najcz

ciej nazywane s stronami fizycznymi.

ęś

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

ś ć

(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

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().

zwany te w polskiej literaturze alokatorem p ytowym.