Memory management
-=-=-=-=-=-=-=-=-=-
The human mind ordinarily operates at only ten percent of its capacity
-- the rest is overhead for the operating system.
Správa paměti vychází z toho, že v rozumném OS je neúnosné,
aby jednotlivé procesy si navzájem videly do paměti (nebo do paměti
jádra) a nebo dokonce tam mohli něco měnit. Proto OS většinou pro
proces vytváří iluzi, že na počítači běží sám. Proces potom má
k dispozici například následující rozložení paměti:
začátek adresovatelného prostoru konec prostoru
v v
+-------------------------+-------------------------------------------------+
| (read only) | (read write) (nic) (read write) |
| Kód procesu | halda ------> díra <----------stack|
| | |
+-------------------------+-------------------------------------------------+
^ ^
brk stack pointer
Proces tedy je v paměti sám. Má ji k dispozici celou (tedy 2GB
na Intelu). Halda a zásobník většinou rostou proti sobě a tak jsou
v principu neomezené. Veprostřed je díra. Při zápisu nebo čtení
proces spadne, protože paměť tam prostě není. Pokud chce zvětšit
haldu nebo zásobnik, posune stack pointer, nebo brk a OS mu kus
paměti přidá (tu napřed pečlive snuluje, aby proces náhodou nedostal
nějaká tajná data).
Virtuální paměť
Pokud dojde fyzická ram, většina OS začne swapovat na disk.
To je celkem jednoduché - OS si vede statistiky o používanosti
jednotlivých stránek paměti, vybere ty méně používané a uloží je
na disk. Pokud proces chce na stránku přistupovat, OS mu ji opět
nahraje z disku.
Ale i zde je co měnit. Samotné algoritmy na určení co swapovat
ven jsou složité. Klasický UNIX dělal paging (odložení celého
procesu na disk) a swaping (odložení jenom některých stránek). Linux
dělá jenom swaping. Existuje mnoho algoritmů na určení přístupových
patternů, tedy nějakých informací o tom, jak který proces paměť
využívá apod.
Základní rozdíl ale je mezi synchroním a asycnroním swapováním.
Vstup a výstup většinou funguje tak, že jádro nečeká na pomalý disk
až práci dodělá a mezi tím může normálně souštět procesy. Pokud je
ale swapování synchroní (aktivované v tom okamžiku, kdy proces chce
nějakou paměť, ale jádro ji nemá), proces nemůže fungovat. Pokud
není žádný jiný proces schopný běhu, nezbývá než čekat. Staré jádra
Linuxu měly synchroní swapování. Často se stávalo, že došla paměť,
disk řádil jak divý, nic nešlo ale systém hrdě hlásil, že má 99%
volného času. A byla to pravda, jenom nebyl schopen tento čas nijak
využít.
Nyní v systému běží swapovací daemon. Ten se aktivuje v situaci,
kdy počet volných stránek klesne pod určené minimum a začne swapovat
na pozadí. Bežící procesy tedy čekat nemusí. Horší situace je
při nahrávání stránek zpět. Ale i zde lze situaci zlepšit pomocí
přístupových patternů a readaheadu.
Účinou metodou je i swap cache. Ta funguje vpodstatě opačně,
než klasická cache. Pokud se nějaká stránka nahraje zpět z disku
do paměti, na disku se nezruší až do té doby, dokud ji program
nezmění. Pokud se mezitím ma znova odswapovad, neukládá se a použije
se stará pozice.
Další šikovné rozšíření je to, že v případě, že v paměti je
kopie nějakého souboru na disku (třeba spustitelný kód programu),
swapování ven se provede tak, že se paměť prostě zahodí
a při swapování zpět se zase nahraje z disku. I toto má Linux
implementované.
Zpožděné přidělování paměti
Často se stává, že proces si sice řekne pro paměť ale nakonec
ji nepotřebuje. I to ale lze vyřešit. Pokud proces zažádá o paměť
pomocí sbrk, paměť nedostane, pouze systém si někde poznačí,
že ji v budoucnosti dostat má. A v případě, že proces na paměť začne
přistupovat, paměť se mu přidělí. A tak se často stává, že procesy
v paměti zabírají několikanásobně méně místa, než si o sobě myslí.
Podobný systém lze použít při vznikání procesu. V UNIXu vzniká
každý proces pomocí volání fork. To proces rozdělí na dva identické.
Pokud chcete sputit jiný program, napřed proces forkem rozdělíte
na dva a potom jeden z nich pomocí volání exec spustí vlastní
program (exec proste vymění kód procesu - po zkončení programu
se už stary program nevrání). To způsobovalo hodně zpomalení.
Například pokud máte desetimegový program, co se rozhodne vypsat
adresář, napřed se 10MB paměti zdvojí a pak se vymění za malý ls.
To rozhodně není nejlepší nápad. Jedno řešení je zavédst volání
spawn (jako v DOSu, Windows apod.), které prostě sputí program bez
nutnosti forku. Jiné řešení použili ve SystemuV, kde zavedli vfork
- což je fork, který nerozdvojuje paměť a tak tedy oba procesy
chvíli paměť sdílí. Nejlepší řešení ale je to, že při forku paměť
fyzicky nerozdvojíte, jenom označíte, že se v budoucnosti paměť má
rozdvojit. A tak oba procesy paměť sdílí. Ale v okamžiku, kdy jeden
do paměti zapíše, vyvolá se přerušení a OS danou stránku (pouze 4KB)
rozdvojí. A tak se rozdvojí opravdu jenom to co je nezbytně nutné
a fork je opravdu rychlý.
Sdílení paměti
Sdílení paměti je šikovný prostředek pro komunikaci. Například
kreslící program může pustit nějaký filtr, který bude přistupovat
přímo do obrázku v paměti kreslícího programu. Jiné části paměti
kreslícího programu mít přístupné nebude. Toto lze velmi jednodušše
udělat přes mapování stránek. Sdílená paměť má ale ještě jedno
zajímavé využití. Pokud v systému běží více kopíí jednoho programu
(což je velmi časté například u interpretru příkazů), mohou sdílet
kód. To je také důvod, proč spustitelný kód v UNIXu je read only.
Sdílené knihovny versus dynamicky linkované
Bežně program používá mnoho knihoven. Ty jsou celkem
velké a hlavně u malých programů často větší než program sám.
Zalinkovávání knihoven přímo do programu (jako v DOSu) je tedy
zbytečné mrháním místem na disku. Proto vznikly DLL knihovny.
Ty jsou ve speciálním souboru a teprve při startu programu se
zalinkují. To ušetří místo na disku ale zpomalí start programu
(zalinkovávání není nejjednodušší).
Aby se knihovny nemusely složitě linkovat, většinou se kompilují
tak, aby byly nezávislé na pozici v paměti. Navíc mají tabulku
odskoků, přes kterou skáčou na zalinkované funkce. Při startu
programu se potom všechny knihovny nahrajou do paměti a udělá se
resolving - vyplní se tabulky. Potom není nutné patchovat přímo
kód knihoven a je možně (za cenu docela maláho zpomalení) sdílet
knihovny v paměti mezi programy.
Jiné řešení jsou klasické sdílené knihovny. Ty vyházejí
z jednoduchého nápadu. V paměti programu se vynechá místo například
mezi zásobníkem a koncem adresovatelného prostoru na knihovny.
Každá knihovna se potom zkompiluje pro nějakou pozici. Tyto knihovny
se potom přidají do programu po zpuštění a program je může normálně
volat tak, jako kdyby s nimi byl slinkován. Toto má výhodu v tom,
že start programu je mnohem rychlejší (není nutné dělat žádné
linkování). Podobný mechanizmus používají staré a.out programy
v Linuxu a dalších OS.
Přináší to ale potíže s tím, že když zkompilujete dvě knihovny
pro stejné místo v paměti, kolidují spolu a není možné je použít
zároveň. Také to přináší zbytečné plýtvání adresovatelným prostorem.
Pokud uděláte novou verzi knihovny, adresy se změní a je nutné
všechny programy překompilovat.
Formát ELF v Linuxu to proto řeší ještě jinak. Přívá stejný
mechanizmus jako DLL knihovny ale nedělá resolving. Používa tzv.
late-binding. Při startu programu se žádný resolving nedělá.
Všechny odkazy v tabulce se vyplní tak, aby skákaly na jednu
funkci (dinamický linker) Pokud program nějakou funkci zavolá,
skočí se do linkeru. Ten zjistí, jakou funkci se program pokouší
spustit, najde patřičnou sdílenou knihovnu (ani knihovny se
nezavádí na začátku ale až v případě prvního použití) a nahradí
odskok zavoláním správné funkce. Podruhé se už dynamický linker
nevolá a zavolá se rovnou daná funkce. Start je mnohem rychleší,
neresolvují se zbytečně všechny funkce, jenom ty potřebné a navíc,
pokud program sice používá nějakou knihovnu, která na disku není,
spadne až v době, kdy ji poprvé zavolá. To se stát nemusí v případě,
že to je nějaký driver apod.
Toto řešení se ukazuje jako nejpoužitelnější kompromis mezi
rychlostí a flexibilitou. Linkování je stále velmi rychlé a přitou
je možné bezpečně měnit verze knihoven.
Page demand loading
Další problém je zavádění programu. Bežný postup, kdy se program
prostě zavede do paměti a spustí se ukazuje neefektivní. Programy
často nevyužijí celý svůj kód (třeba obsahují ovladač, který není
vůbec třeba) a musí čekat dokud nejsou zavedeni do paměti.
To lze obejít tím, že se zavede pouze začátek programu a ten
se zpustí. Pokud program skočí do části, která se zatím nenahrála,
dohraje se. To způsobí, že se nahrají jen ty části programu,
které jsou třeba. Na druhou stranu to ale přináší zbytečné seekování
po disku, protože program se většinou neprovádí lineárně. Tomu ale
docela účině zabraňuje readahead, který čte stránky dopředu. Protože
běží asynchroně protgram se dokonce může nahrávat v době, kdy se už
provádí.
To že všechny tyto techniky jsou dohromady poměrně účiné snad
ukáže příklad:
PID USER PRI NI SIZE RSS SHARE STAT LIB %CPU %MEM CTIME COMMAND
217 root 0 0 480 160 120 S 0 0.0 1.0 0:00 /bin/login
Ten říká, že proces login sice požádal celkově o 480KB paměti
ale dostal pouze 160 a sdíli 120KB s jinými programy.
Mmap
Možná si teď říkáte, že memorymanagement je velmi komplikovaný.
Častečně to je pravda, ale všechny tyto funkce lze velmi elegantně
implementovat pomocí funkce mmap. Ta navíc přináší možnost,
aby programy použily tyto schopnosti i pro jiné účely. Funkce
mmap umožňuje "namapovat" libovolnou část souboru na libovolnou
pozici v paměti s libovolnými přistupovými právy (read, write,
exec a kombinace). Je také možné mapovat "anonymní" stránky - tedy
novou paměť a mapovat fyzickou paměť (přes "soubor" /dev/mem, který
fyzickou paměť obsahuje).
Navíc je možné sdílet mapování (pokud si více procesů namapuje
stejný soubor, bude pouze jednou v paměti a mohou tak tedy
komunikovat). Pomocí mmap lze implementovat všechny popsané věci -
spustitelný soubor se napřed namapuje na začátek paměti, knihovny se
zase mapují doprostřed, posouvání brk je vlastně zvětšování anonymní
namapované paměti. Navíc ale procesy můžou svoji paměť rozdělit
jinak (to využívá například DOSemu), pokud na to mají práva, mohou
si namapovat videoram kamkoliv do svého adresovatelného prostoru,
nadělat si do své paměti díry, spřístupnit svůj kód pro zápis apod.
Mmap je právě jedna z věcí, které se velmi těžko implementují
na mikrojádrových systémech. Většina popsaných služeb potřebuje
mnoho spolupráce mezi jednotlivýmí částmi systému, která většinou
není v mikrojádrovém OS možná.
výheň