[OSy] Zadani 3. tematu semestralni ulohy
Martin Decky
decky at d3s.mff.cuni.cz
Thu Nov 19 00:37:55 CET 2015
Vazeni kolegove,
v priloze tohoto emailu naleznete rozsirene zadani 3. 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 3. prezencni ulohy se bude take tykat tematu
virtualni 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 3. 12. 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
I s rizikem, ze to nekomu bude uz pripad otravne, tak po zkusenostech s
predchozimi ulohami opet DURAZNE APELUJEME, abyste vypracovani reseni
nenechavali na posledni chvili a meli tak pripadne realnou moznost
reagovat na nasi zpetnou vazbu k Vasemu reseni, Podrobneji viz zadani 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 3.: Virtualni pamet
Rozsirene zadani
========================================================================
Datum zverejneni zadani: 19. 11. 2015
Datum odevzdani reseni: 3. 12. 2015
------------------------------------------------------------------------
Cilem 3. tematu semestralni ulohy je naprogramovat mapovani virtualni
pameti do 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.4,
do ktereho doplnte chybejici funkcionalitu. Kalisto ve verzi 0.9.4 je
k dispozici ke stazeni z URL:
http://d3s.mff.cuni.cz/osy/download/kalisto-0.9.4.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.
Virtualni adresovy prostor z pohledu operacniho systemu ----------------
V kontextu operacniho systemu predstavuje virtualni adresovy prostor
(take nazyvany mapa virtualni pameti, address space, virtual memory
map ci zkracene VMM) datovou strukturu, ktera udrzuje informace
o vyuziti adresoveho prostoru.
Rozdeleni virtualniho adresoveho prostoru na segmenty je na procesoru
MIPS R4000 pevne dane. Protoze se zpracovani virtualnich adres
procesorem v jednotlivych segmentech lisi, je virtualni adresovy
prostor typicky alokovan po souvislych oblastech (virtual memory area,
zkracene VMA) uvnitr techto segmentu. Oblasti virtualni pameti
reprezentuji souvisly blok virtualnich adres ve virtualnim adresovem
prostoru. V zavislosti na tom, v jakem segmentu adresoveho prostoru
procesoru se urcita oblast nachazi, je pak mapovani rozsahu
virtualnich adres oblasti do fyzicke pameti bud pevne dane (pripad
segmentu KSEG0 a KSEG1) nebo definovane uzivatelem (resp. operacnim
systemem), ktery ma moznost ovlivnovat obsah TLB.
Virtualni adresovy prostor je jednim z prostredku sdilenych vsemi
vlakny jednoho uzivatelskeho procesu. Z bezpecnostnich duvodu ma kazdy
proces operacniho systemu svuj vlastni virtualni adresovy prostor
a tedy i mapovani do fyzicke pameti.
Jelikoz jadro Kalisto nabizi pouze implementaci nezavislych vlaken,
ktera bezi v rezimu jadra, pozaduje zadani 3. semestralni ulohy
implementovat vytvareni novych kernelovych vlaken, ktera nesdili svou
mapovanou pamet s drive vytvorenymi vlakny.
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 -----------------------------------------------------------
1. Pristup vlaken do virtualniho adresoveho prostoru
Rozsirte stavajici implementaci vlaken v jadre Kalisto o podporu
pristupu k virtualni pameti mapovane pres TLB v ramci virtualniho
adresoveho prostoru.
Rozsirte chovani existujici funkce thread_create():
* int thread_create(thread_t *thread_ptr, thread_fn entry,
void *data, const thread_flags_t flags)
Pokud bude argument @flags obsahovat priznak TF_NEW_VMM, pro nove
vytvorene vlakno bude take vytvoren novy virtualni adresovy
prostor. Nove vlakno tedy nebude sdilet mapovanou virtualni pamet
s volajicim vlaknem.
2. Sprava virtualniho adresniho prostoru
Sprava oblasti virtualni pameti zahrnuje vytvareni, manipulaci
a ruseni oblasti virtualni pameti v kontextu virtualniho adresoveho
prostoru prave beziciho vlakna. Oblasti se nesmi prekryvat, velikost
a zacatek oblasti musi byt zarovnan na nejmensi velikost stranky
podporovanou procesorem, v pripade MIPS R4000 tedy 4 KiB.
Pocet oblasti virtualni pameti neni v principu omezen, jejich
maximalni pocet je dan pouze realne dostupnou pameti. Pro spravu
oblasti virtualni pameti tedy pouzijte vhodnou datovou strukturu
(nikoliv staticky alokovanou), pricemz duraz je kladen na rozumne
rychle nalezeni oblasti virtualni pameti k dane virtualni adrese
a take na rozumne rychle nalezeni odpovidajici fyzicke adresy.
Casova slozitost techto operaci by tedy mela byt lepsi nez linearni
vzhledem k poctu oblasti a velikosti oblasti. Rozumnymi kandidaty na
takovou datovou strukturu jsou naprikad stromove datove struktury,
hashovaci datove struktury nebo hierarchicke strankovaci tabulky
(viz [3]).
Pro spravu virtualniho adresoveho prostoru aktualne beziciho vlakna
implementujte tyto funkce:
* int vma_map(void **from, const size_t size,
const vm_flags_t flags)
Funkce vytvori oblast ve virtualnim adresovem prostoru o velikosti
@size bytu, pro tuto oblast alokuje fyzickou pamet (ne nutne
souvislou) a vytvori mapovani prislusne virtualni pameti do
fyzicke.
V zavislosti na bitovych priznacich v argumentu @flags funkce bud
automaticky zvoli vhodnou adresu zacatku oblasti virtualni pameti
a vrati ji ve @from (priznak VF_VA_AUTO), nebo se pokusi vytvorit
oblast na adrese zadane volajicim ve @from (priznak VF_VA_USER).
Dalsi bitove priznaky v argumentu @flags urcuji typ segmentu
virtualniho adresoveho procesoru, ve kterem bude virtualni oblast
alokovana. Hodnoty priznaku pro jednotlive segmenty jsou
VF_AT_KUSEG, VF_AT_KSEG0, VF_AT_KSEG1, VF_AT_KSSEG a VF_AT_KSEG3.
Alokace v segmentech KSEG0 a KSEG1 se vzajemne vylucuji, pokud
jsou mapovany na stejne fyzicke adresy.
Funkce vraci EOK, pokud byla pamet alokovana a namapovana; EINVAL,
pokud nebylo mozne alokovat oblast se zacatkem na adrese @from
v danem segmentu virtualniho adresoveho prostoru procesoru, nebo
pokud @from ci @size nejsou zarovnany; ENOMEM, pokud neni dostatek
fyzicke pameti k provedeni operace.
* int vma_unmap(const void *from)
Funkce zrusi mapovani pameti pro oblast se zacatkem na adrese
@from, ktera byla predtim vytvorena volanim vma_map(). Dale uvolni
fyzickou pamet, do ktere byla oblast mapovana, a zrusi prislusnou
oblast virtualni pameti.
Funkce vraci EOK, pokud byla pamet uvolnena a mapovani zruseno;
EINVAL, pokud @from neukazuje na zacatek oblasti vytvorene volanim
vma_map().
Pro korektni implementaci operace vma_unmap() je nutne krome
odstraneni mapovani oblasti v internich strukturach kernelu
provest take operaci "TLB shootdown", cili odstraneni prislusnych
zaznamu z TLB, jsou-li tam aktualne ulozeny.
3. Obsluha vyjimek TLB
Pri prekladu virtualni adresy na fyzickou muze procesor MIPS R4000
vyvolat dva druhy vyjimek. Prvni z vyjimek je TLB Refill, ktera je
vyvolana v pripade, ze pro pozadovanou virtualni adresu nebyl v TLB
nalezen odpovidajici zaznam. Druhou z vyjimek je TLB Invalid, ktera
je vyvolana v pripade, ze v TLB sice existuje polozka pro
pozadovanou virtualni adresu, ale tato polozka je neplatna.
Obsluha obou typu vyjimek by mela nalezt mapovani pro prislusnou
virtualni adresu a naplnit TLB. Pokud nebude pro danou virtualni
adresu mapovani existovat, ocekava se, ze vlakno, ktere vyjimku
vyvolalo, nebude nadale planovano (jednodussi forma vynuceneho
zruseni/ukonceni vlakna).
Pozn.: Moznost oznacit polozku TLB jako neplatnou lze pouzit napr.
pri implementaci copy-on-write mechanizmu nebo swapovani. V ramci
zadani semestralni ulohy vsak pro jeho vyuziti neni prostor.
TLB procesoru MIPS R4000 muze v jednom okamziku obsahovat mapovani
nalezejici vice adresovym prostorum (diky polozce ASID). Zadani
pozaduje tuto vlastnost dusledne vyuzivat a vyhnout se tak zbytecnym
drahym operacim "TLB flush" pri kazde zmene aktivniho adresoveho
prostoru.
Pozn.: Pro ucely zadani semestralni ulohy lze predpokladat, ze
maximalni pocet adresovych prostoru spravovanych kernelem muze byt
beze zbytku pokryt rozsahem platnych ASID hodnot na procesoru MIPS
R4000. Neni tedy potreba implementovat algoritmus LRU nebo jemu
podobny pro pridelovani ASID hodnot adresovym prostorum.
Jednotkove testy -------------------------------------------------------
K overeni spravne funkcnosti implementace slouzi testy ulozene
v podstrome kernel/tests/vmm zdrojoveho stromu Kalista 0.9.4.
Infrastruktura pro spousteni a vyhodnoceni techto jednotkovych testu
je implementovana pomoci skriptu tests-vmm.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: Virtual memory,
https://en.wikipedia.org/wiki/Virtual_memory
[3] Wikipedia: Page table,
https://en.wikipedia.org/wiki/Page_table
More information about the NSWI004
mailing list