[OSy] Zadani 2. tematu semestralni ulohy
Martin Decky
decky at d3s.mff.cuni.cz
Thu Oct 29 00:29:37 CET 2015
Vazeni kolegove,
v priloze tohoto emailu naleznete rozsirene zadani 2. semestralni ulohy
z predmetu Operacni systemy. Prosim, venujte tomuto zadani pozornost i v
tom pripade, ze mate v planu prijit na nejblizsi cviceni a resit
prezencni ulohu -- zadani 2. prezencni ulohy se bude take tykat tematu
spravy pameti a bude vyzadovat znalost latky z prednasky (pripadne z
doporucene literatury, ktera je uvedena na konci rozsireneho zadani).
Pokud se rozhodnete implementovat rozsirene zadani, tak sva reseni
muzete odevzdavat az do 12. 11. 2015 (vcetne). Odevzdani provadejte opet
tak, ze svou modifikaci Kalista (tj. vse, co je potreba ke spusteni,
otestovani a ohodnoceni Vaseho reseni) zabalite do archivu (ZIP, TAR.BZ2
apod.) a poslete jako prilohu na emailovou adresu
nswi004 at d3s.mff.cuni.cz
Pro uspesne vyreseni 2. rozsirene ulohy budete pravdepodobne muset
napsat rozsahem ponekud vice kodu nez v pripade 1. rozsirene ulohy,
nicmene celkova narocnost by mela byt srovnatelna. Proto opet apelujeme,
abyste vypracovani nenechavali na posledni chvili. Dalsi podminky
zustavaji stejne jako v pripade 1. ulohy [1].
V pripade libovolnych dotazu k zadani nebo k formalnim zalezitostem
nevahejte vyuzit tento mailing list.
[1] https://d3s.mff.cuni.cz/pipermail/osy/2015-October/002164.html
S pozdravem
Martin Decky
-------------- next part --------------
========================================================================
Semestralni uloha z predmetu
Operacni systemy
Tema 2.: Sprava pameti
Rozsirene zadani
========================================================================
Datum zverejneni zadani: 29. 10. 2015
Datum odevzdani reseni: 12. 11. 2015
------------------------------------------------------------------------
Cilem 2. tematu semestralni ulohy je naprogramovat spravu fyzicke
pameti. Zadani ma formu rozhrani, ktere je nutno naimplementovat, a je
doplneno sadou jednotkovych testu, jimiz musi implementace uspesne
projit.
Pri vypracovani vychazejte z vyukoveho jadra Kalisto ve verzi 0.9.3,
do ktereho doplnte chybejici funkcionalitu. Kalisto ve verzi 0.9.3 je
k dispozici ke stazeni z URL:
http://d3s.mff.cuni.cz/osy/download/kalisto-0.9.3.tar.bz2
Pokud zadani nespecifikuje nejaky detail, je zavazne chovani, ktere
ocekavaji testy. Pokud testy dane chovani netestuji, zadani si podle
uvazeni dodefinujte a sve rozhodnuti zdokumentujte pomoci vhodnych
komentaru ve zdrojovem kodu reseni.
Virtualni adresovy prostor procesoru -----------------------------------
V zavislosti na aktualnim rezimu behu (user, supervisor, kernel) je
32bitovy virtualni adresovy prostor procesoru MIPS R4000 rozdelen na
nekolik segmentu. Rozdeleni virtualniho adresoveho prostoru procesoru
na segmenty je na MIPSu pevne dane. Mapovani virtualnich adres do
fyzicke pameti je bud pevne dane (pripad segmentu KSEG0 a KSEG1, viz
dale) nebo definovane uzivatelem (operacnim systemem), ktery ma
moznost ovlivnovat obsah TLB.
V uzivatelskem rezimu (user mode) je pristupny pouze segment USEG
v rozsahu adres [0x00000000,0x800000000), ktery je mapovany do fyzicke
pameti pres TLB. Pristup na adresu mimo USEG vyvola vyjimku Address
Error.
V rezimu supervizora (supervisor mode) jsou definovany segmenty SUSEG
v rozsahu adres [0x00000000,0x80000000) a segment SSEG v rozsahu adres
[0xC0000000,0xE00000000). Adresy v obou segmentech jsou mapovany do
fyzicke pameti pres TLB, pricemz segment SUSEG je analogii segmentu
USEG v uzivatelskem rezimu. Pristup na adresy mimo SUSEG a SSEG vyvola
vyjimku Address Error.
Konecne v rezimu jadra (kernel mode) jsou definovany tyto segmenty:
* KUSEG v rozsahu adres [0x00000000,0x80000000)
* KSEG0 v rozsahu adres [0x80000000,0xA0000000)
* KSEG1 v rozsahu adres [0xA0000000,0xC0000000)
* KSSEG/KSEG2 v rozsahu adres [0xC0000000,0xE0000000)
* KSEG3 v rozsahu adres [0xE0000000,0xFFFFFFFF]
Adresy v segmentech KUSEG, KSSEG a KSEG3 jsou mapovany do fyzicke
pameti pres TLB, pricemz segmenty KUSEG, resp. KSSEG jsou analogii
segmetu USEG, resp. SSEG v uzivatelskem rezimu, resp. rezimu
supervizora.
Adresy v segmentech KSEG0 a KSEG1 jsou mapovany do fyzicke pameti
primo pevnym identickym mapovanim (tj. pouze odectenim pocatecni
adresy segmentu). Toto identicke mapovani nelze zmenit. Virtualni
adresy segmentu KSEG0 jsou tedy mapovany na fyzicke adresy v rozsahu
[0x00000000,0x20000000), stejne je to i v pripade KSEG1. Na realnem
hardwaru se segmenty KSEG0 a KSEG1 lisi take tim, ze pristup na
adresy v KSEG1 obchazi cache procesoru.
Obecne pozadavky -------------------------------------------------------
Nasledujici doporuceni odrazi pozadavky na uroven zdrojovych textu,
ktere budou hodnoceny pri odevzdani reseni ulohy.
- Vyhybejte se pouzivani numerickych konstant primo v kodu, nahradte
je makry.
- Pouzivejte prazdne radky a blokove komentare k oddeleni logickych
casti kodu.
- Pouzivejte vhodnym zpusobem mezery pro zprehledneni a usnadneni
porozumeni kodu. Snazte se, aby styl vaseho kodu pokud mozno
odpovidal stylu jiz existujiciho kodu.
- Vyhybejte se psani prilis dlouhych funkci nebo funkci s prilis
velkou urovni vnorenych bloku.
- Vyhybejte se vytvareni zdrojovych souboru, ktere obsahuji
nesouvisejici funkce, pripadne umistovani zdrojovych souboru do
nevhodnych adresaru.
- Pouzivejte makra ci inline funkce k nahrade slozitych podminkovych
vyrazu.
- Pouzivejte jednotny jazyk pro komentare.
- Pouzivejte jednotny jazyk pro identifikatory funkci a promennych
a pro nazvy souboru.
- Pouzivejte systematicke identifikatory funkci a promennych.
Zadani ulohy -----------------------------------------------------------
Implementujte spravu fyzickych stranek (ramcu) pameti pro evidenci,
ktere fyzicke stranky jsou jiz pouzity a ktere jsou stale volne.
Pro spravu fyzicke pameti pouzijte vhodnou datovou strukturu, pricemz
duraz je kladen na rozumne rychle nalezeni volnych fyzickych stranek.
Velikost fyzicke stranky zvolte vhodne tak, aby tyto fyzicke stranky
bylo mozne mechanismy virtualizace pameti procesoru MIPS mapovat na
virtualni stranky (napr. 4 KiB).
* int frame_alloc(void **paddr, const size_t cnt,
const vm_flags_t flags)
Funkce nalezne a alokuje @cnt po sobe jdoucich volnych fyzickych
stranek pameti. V pripade, ze @cnt je rovno nule nebo alokace nebyla
uspesna, vraci ENOMEM. V pripade uspesne alokace vraci EOK.
V zavislosti na hodnote bitovych priznaku v argumentu @flags funkce
bud automaticky zvoli vhodnou fyzickou adresu zacatku alokovanych
fyzickych stranek a vrati ji v @paddr (priznak VF_VA_AUTO), nebo se
pokusi o alokaci zacinajici na fyzicke adrese zadane volajicim
v @paddr (priznak VF_VA_USER). Pokud @paddr neobsahuje fyzickou
adresu zarovnanou na pocatek stranky, funkce vraci EINVAL.
Pokud je v argumentu @flags uveden bitovy priznak VF_AT_KSEG0, resp.
VF_AT_KSEG1, alokace se uvazuje jen v te casti fyzicke pameti, ktera
je pristupna ze segmentu KSEG0, resp. KSEG1 virtualniho adresoveho
prostoru, tedy v rozsahu fyzickych adres [0x00000000,0x20000000).
Naopak priznaky VF_AT_KUSEG, VF_AT_KSSEG a VF_AT_KSEG3 oznacuji
moznost prednostne alokovat fyzicke stranky mimo tento rozsah
(jsou-li k dispozici), aby nedochazelo ke zbytecnemu plytvani
fyzickych stranek pristupnych z KSEG0, resp. KSEG1.
Za volne fyzicke stranky se povazuji pouze ty, ktere lze bez omezeni
pouzit, neobsahuji tedy staticky alokovanou pamet (kod a data jadra,
struktury samotneho alokatoru apod.) a fyzicke stranky jiz drive
alokovane volanim funkce frame_alloc() a dosud neuvolnene.
* int frame_free(const void *paddr, const size_t cnt)
Uvolneni @cnt po sobe jdoucich fyzickych stranek zacinajicich na
fyzicke adrese @paddr. Uvolnit lze pouze fyzicke stranky, ktere byly
drive alokovany funkci frame_alloc(), tedy nikoliv statickou pamet
kodu a dat jadra, struktury samotneho alokatoru apod.
Je pripustne, aby bylo nejprve pomoci jednoho volani funkce
frame_alloc() naalokovano nekolik fyzickych stranek a podintervaly
tohoto rozsahu fyzickych stranek byly pote jednotlive uvolnovany
opakovanym volanim frame_free(). Podobne je mozne pomoci jednoho
volani frame_free() uvolnit souvisly interval fyzickych stranek,
ktery byl vsak postupne naalokovan vice nez jednim volanim
frame_alloc().
Funkce vraci EOK, bylo-li uvolneni uspesne, nebo EINVAL, pokud @cnt
je rovno nule, @paddr neobsahuje fyzickou adresu zarovnanou na
pocatek stranky nebo posloupnost @cnt po sobe jdoucich fyzickych
stranek nebyla drive alokovana pomoci frame_alloc().
* Uprava stavajiciho alokatoru haldy
Stavajici kernelovy alokator haldy s rozhranim malloc()/free()
alokuje pamet primo z haldy umistene v segmentu KSEG0 virtualniho
adresoveho prostoru. Protoze soucasne s timto alokatorem bude
stranky fyzicke pameti alokovat take volani frame_alloc(), je nutne
zajistit, aby alokator haldy pouzival jen fyzicke stranky pameti
pridelene pomoci frame_alloc().
Upravte stavajici alokator tak, aby pouzival jako svuj backend
rozhrani frame_alloc()/frame_free() a zaroven aby vzdy vracel pouze
pamet ze segmentu KSEG0 virtualniho adresoveho prostoru procesoru,
tj. aby bylo mozne k alokovane pameti pristupovat bez pouziti TLB.
Jednotkove testy -------------------------------------------------------
K overeni spravne funkcnosti implementace slouzi testy ulozene
v podstrome kernel/tests/mm zdrojoveho stromu Kalista 0.9.3.
Infrastruktura pro spousteni a vyhodnoceni techto jednotkovych testu
je implementovana pomoci skriptu tests-mm.sh. Pro splneni zadani je
potreba, aby reseni uspesne proslo vsemi dodanymi jednotkovymi testy,
pricemz neni dovoleno modifikovat logiku testu.
K integraci s jednotkovymi testy pridejte do hlavickoveho souboru
api.h vhodne #include direktivy, ktere zajisti vlozeni hlavickovych
souboru s potrebnymi deklaracemi.
Doporucena literatura --------------------------------------------------
[1] Studijni text k predmetu Operacni systemy, kapitola Memory
Management, http://d3s.mff.cuni.cz/~ceres/sch/osy/text/ch03.html
[2] Wikipedia: Memory management,
https://en.wikipedia.org/wiki/Memory_management
[3] OSDev Wiki: Page Frame Allocation,
http://wiki.osdev.org/Page_Frame_Allocation
More information about the NSWI004
mailing list