[OSy] Zadani 2. semestralky
Martin Decky
decky at nenya.ms.mff.cuni.cz
Sun Nov 12 19:57:19 CET 2006
Hezky vecer,
na konci tohoto emailu se nachazi zadani 2. semestralni prace. Jadro, na
kterem budete po predchozich skupinach pokracovat v implementaci, zasleme
jednotlive kazde skupine.
Do te doby vyuzijte cas k promysleni zadani a pokud je Vam neco nejasneho,
pouzijte tuto konferenci k polozeni dotazu, pokusime se v kratkem case odpovedet.
Priblizne za tyden Vam take posleme testy, pomoci nichz budeme castecne
testovat spravnost sveho reseni. Cviceni 20. a 23. 11. budou mit opet formu
"hromadne konzultace" (ucast nepovinna), kde budeme diskutovat nad pripadnymi
potizemi.
Pripominam, ze 4. a 7. 12. se budou konat prezentace Vasich reseni a zavazne
datum odevzdani je patek 8. 12. (na presnem harmonogramu obojiho se jeste
domluvime). Odevzdavat pozdeji (nejvyse vsak o 1 tyden) je mozne, ale
v takovem pripade muze skupina ziskat maximalne 2/3 plneho poctu bodu.
Hodne stesti!
M.D.
Zadani 2. semestralni prace: -------------------------------------------------
Cilem 2. semestralni prace je rozsirit jadro z 1. semestralni prace o
spravu fyzicke pameti a mapovani virtualni pameti do fyzicke. Zadani ma
formu rozhrani, ktere je nutno naimplementovat. K zajisteni rozumne urovne
funkcnosti pro navazujici skupiny je nutne, aby implementace prosla sadou
testu, ktere overuji funkcnost implementace.
Ukolem bude naprogramovat:
* alokator oblasti virtualni pameti
* mapovani virtualni pameti do fyzicke
* pristup vlaken do virtualniho adresoveho prostoru
* obsluhu vyjimek TLB
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.
Obecne pozadavky tykajici se deklarace a pouzivani chybovych kodu,
definice zakladnich typu pouzivanych v zadani a pozadavky na formu
zdrojovych textu jsou shodne se zadanim 1. semestralni prace.
Virtualni adresovy prostor procesoru
------------------------------------
V zavislosti na aktualnim rezimu (user, supervisor, kernel) je virtualni
adresovy prostor procesoru MIPS R4000 rozdelen na nekolik segmentu.
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.
A konecne v rezimu jadra (kernel mode) jsou definovany 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) a KSEG3 v rozsahu
adres [0xE0000000,0xFFFFFFFF]. Adresy v segmentech KUSEG, KSSEG a KSEG2
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 (pouze odectenim pocatecni adresy segmentu).
Virtualni adresy segmentu KSEG0 jsou tedy mapovany na fyzicke adresy v
rozsahu [0x00000000,0x20000000), podobne je to i v pripade KSEG1.
Na realnem systemu se segmenty KSEG0 a KSEG1 lisi take v tom, ze
pristup na adresy KSEG0 obchazi cache procesoru.
Virtualni adresovy prostor procesu
----------------------------------
V kontextu operacniho systemu je virtualni adresovy prostor procesu,
nebo take mapa virtualni pameti (address space, virtual memory map, vmm),
datova struktura, ktera udrzuje informace o vyuziti adresoveho prostoru.
Rozdeleni virtualniho adresoveho prostoru procesoru na segmenty je
pevne dane. Protoze se zpracovani virtualnich adres procesorem v
jednotlivych segmentech lisi, je virtualni adresovy prostor procesu
typicky alokovan po oblastech (virtual memory area, vma) uvnitr techto
segmentu. Oblasti virtualni pameti reprezentuji souvisly blok 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 (operacnim
systemem), ktery ma moznost ovlivnovat obsah TLB.
Virtualni adresovy prostor procesu je jednim z prostredku sdilenych
vlakny uzivatelskeho procesu. Z bezpecnostnich duvodu ma kazdy proces
operacniho systemu svuj vlastni virtualni adresovy prostor a tedy i
mapovani do fyzicke pameti.
Zaklad jadra z 1. semestralni prace dosud pracuje pouze s nezavislymi
vlakny, ktere bezi v rezimu jadra. Pro nasledny prechod k procesum s
vice vlakny bezicimi v uzivatelskem rezimu (napln 3. semestralni prace)
je ovsem nejprve nutne vytvorit podporu pro virtualizaci pameti, jeji
mapovani do fyzicke pameti a sdileni tohoto mapovani vlakny.
Pristup vlaken do virtualniho adresoveho prostoru
-------------------------------------------------
Rozsirte stavajici implementaci vlaken v jadre o podporu pristupu
k virtualni pameti mapovane pres TLB v ramci virtualniho adresoveho
prostoru.
Pro ucely testovani implementujte funkci:
* int thread_create_new_map (
thread_t * thread_ptr, void (* thread_start) (void *), void * data)
Funkce vytvori nove vlakno podobne jako thread_create s tim rozdilem,
ze pro vlakno vytvori novy virtualni adresovy prostor. Nove vlakno tedy
nebude sdilet mapovanou virtualni pamet s volajicim vlaknem.
Funkce thread_create_new_map do jiste miry supluje funkci process_create
z rozhrani pro vytvareni a spravu procesu, jehoz zadani a implementace
je naplni 3. semestralni prace.
Sprava oblasti virtualni pameti
-------------------------------
Sprava oblasti virtualni pameti zahrnuje alokaci, manipulaci a
uvolnovani 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.
Pro spravu oblasti virtualni pameti pouzijte vhodnou datovou strukturu,
pricemz duraz je kladen na rozumne rychle nalezeni oblasti virtualni
pameti k dane virtualni adrese.
* int vmalloc (
void ** from, const size_t size, const unsigned int flags)
Funkce alokuje oblast ve virtualnim adresovem prostoru o velikosti
@size bajtu, pro tuto oblast alokuje fyzickou pamet a vytvori mapovani
prave alokovane virtualni pameti do fyzicke.
V zavislosti na hodnote bitoveho priznaku VF_VIRT_ADDR v argumentu
@flags funkce bud automaticky zvoli vhodnou adresu zacatku oblasti
virtualni pameti a vrati ji ve @from (hodnota VF_VA_AUTO), nebo se
pokusi vytvorit oblast na adrese zadane volajicim ve @from (hodnota
VF_VA_USER).
Bitove pole VF_ADDR_TYPE v argumentu @flags urcuje typ segmentu
virtualniho adresoveho procesoru, ve kterem bude virtualni oblast
alokovana. Hodnoty bitoveho pole 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.
Binarni format argumentu @flags je dan makry VF_VA_SIZE, VF_VA_SHIFT
a VF_AT_SIZE, VF_AT_SHIFT, ktere specifikuji velikost bitoveho pole
a jeho pozici ve slove.
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 vfree (void * from)
Funkce zrusi mapovani pameti pro oblast se zacatkem na adrese @from,
ktera byla predtim vytvorena volanim vmalloc(). Dale uvolni fyzickou
pamet, do ktere byla oblast mapovana a zrusi prislusnou oblast
virtualni pameti.
Vraci EOK pokud byla pamet uvolnena a mapovani zruseno, EINVAL pokud
@from neukazuje na zacatek oblasti vytvorene volanim vmalloc().
* int vresize (void * from, const size_t size)
Funkce zvetsi/zmensi velikost oblasti virtualni pameti jejiz zacatek
lezi na adrese @from na novou velikost @size bajtu. Nesmi pritom dojit
k prekryvu dvou ruznych oblasti virtualni pameti.
Vraci EOK, pokud byla velikost oblasti uspesne zmenena, EINVAL
pokud @from neukazuje na platnou oblast, pokud by melo dojit k
prekryvu s jinou oblasti v dusledku zvetseni, nebo pokud neni nova
velikost zarovnana, ENOMEM pokud nebylo mozne oblast zvetsit v kvuli
nedostatku pameti.
* int vremap (void * from, void * to)
Funkce premapuje oblast zacinajici na adrese @from na adresu @to.
Velikost oblasti a posloupnost mapovani virtualnich stranek na fyzicke
zustava zachovana. Prekryti virtualnich adres v oblasti @from a @to
je pripustne.
Vraci EOK pokud bylo premapovani uspesne, EINVAL pokud na adrese
@from neni platna oblast, pokud @to neni zarovnana adresa, nebo pokud
by pri presunu melo dojit k prekryti jiz existujici oblasti.
* int vmerge (void * area1, void * area2)
Funkce spoji oblasti @area1 a @area2 do jedne oblasti, pokud spolu
sousedi. Zacatek nove oblasti je na nizsi z pocatecnich adres obou
oblasti. Vraci EOK pokud bylo spojeni provedeno, EINVAL pokud jsou
jedna nebo obe oblasti neplatne, nebo pokud spolu nesousedi.
* int vsplit (void * from, void * split)
Funkce rozdeli oblast zacinajici na adrese @from na dve sousedici
oblasti, pricemz nove vznikla oblast bude zacinat na adrese @split.
Vraci EOK pokud bylo rozdeleni uspesne, EINVAL pokud @from neukazuje
na zacatek existujici oblasti, pokud @split neni uvnitr rozdelovane
oblasti, nebo pokud hodnota @split neni zarovnana.
Obsluha vyjimek TLB
-------------------
Pri prekladu virtualni adresy na fyzickou muze procesor vyvolat dva
druhy vyjimek. Prvni z vyjimek je TLB Refill, ktera je vyvolana v
pripade, ze pro pozadovanou virtualni adresu nebyl v TLB nalezen zaznam
s odpovidajici fyzickou adresou. 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 jadro vypise varovne hlaseni a vlakno, ktere
vyjimku vyvolalo, zrusi.
Pozn.: Moznost oznacit polozku TLB jako neplatnou lze pouzit napr. pri
implementaci copy-on-write mechanizmu nebo swapovani, v ramci zadani 2.
semestralni prace vsak pro jeho vyuziti neni prostor.
Uprava stavajiciho alokatoru pameti
-----------------------------------
Stavajici alokator pameti s rozhranim malloc/free alokuje pamet z haldy
umistene v segmentu KSEG0 virtualniho adresoveho prostoru procesoru.
Protoze soucasne s timto alokatorem bude stranky fyzicke pameti alokovat
take volani vmalloc(), je nutne zajistit, aby stejnou stranku fyzicke
pameti nepouzival alokator haldy a oblast virtualni pameti vytvorena
volanim vmalloc().
Upravte stavajici alokator tak, aby nedochazelo k uvedenym kolizim a
zaroven aby alokator vracel pouze pamet ze segmentu KSEG0 virtualniho
adresoveho prostoru procesoru, tj. aby bylo mozne k alokovane pameti
pristupovat bez pouziti TLB.
Kopirovani pameti mezi vlakny
-----------------------------
Pro testovaci ucely implementujte nasledujici funkce:
* int copy_from_thread (thread_t thr,
void * dest, const void * src, const size_t len)
Funkce zkopiruje data z virtualni pameti vlakna @thr do virtualni
pameti volajiciho vlakna. Vraci EOK pokud byla data zkopirovana,
EINVAL pokud je identifikace zdrojoveho vlakna neplatna.
* int copy_to_thread (thread_t thr,
void * dest, const void * src, const size_t len)
Funkce zkopiruje data z virtualni pameti volajiciho vlakna do
virtualni pameti vlakna @thr. Vraci EOK pokud byla data zkopirovana,
EINVAL pokud je identifikace zdrojoveho vlakna neplatna.
Integrace s testy
-----------------
K integraci s testy vytvorite hlavickovy soubor assignment-2.h, ktery bude
obsahovat deklarace vsech vyse uvedenych funkci. Typicky bude obsahovat
#include direktivy, ktere zajisti vlozeni vasich hlavickovych souboru s
prislusnymi deklaracemi.
Dale musi soubor obsahovat deklaraci funkce assignment_test (void),
kterou zavolate z vaseho jadra.
More information about the NSWI004
mailing list