[OSy] Zadani semestralnich praci
Martin Decky
decky at d3s.mff.cuni.cz
Sun Oct 7 21:52:34 CEST 2012
Vazeni kolegove,
v priloze tohoto emailu naleznete zadani semestralnich praci z predmetu
Operacni systemy a prislusne testy, ktere zadani doplnuji a ktere budou
slouzit pro vyhodnocovani Vasi uspesnosti v jednotlivych fazich.
Obsah prilozenych souboru je nasledujici:
assignment-1.txt ... zakladni a rozsirene zadani 1. semestralni prace
assignment-2.txt ... zakladni a rozsirene zadani 2. semestralni prace
assignment-3.txt ... zakladni a rozsirene zadani 3. semestralni prace
tests-as1.tar.bz2 ... testy pro 1. zakladni zadani
tests-as1e.tar.bz2 ... testy pro 1. rozsirene zadani
tests-as2.tar.bz2 ... testy pro 2. zakladni zadani
tests-as2e.tar.bz2 ... testy pro 2. rozsirene zadani
tests-as3.tar.bz2 ... testy pro 3. zakladni zadani
Prosim proctete si dukladne zadani a prohlednete si testy. Pokud by Vam
bylo cokoliv nejasneho, nevahejte poslat svuj dotaz do teto konference.
Na dotazy se pokusime v kratkem case odpovedet, pripadne Vas dotaz muze
slouzit jako namet pro obsah konzultacnich cviceni, ktera muzeme v
pripade zajmu vyhlasit pozdeji v prubehu semestru.
Konference by vsak nemela slouzit jako hot-line nahrazujici nutne
samostudium. Budeme ochotne reagovat na informovane otazky, ale na
trivialni dotazy typu "Jak se na MIPSu zmeni hodnota v registru R0?",
prosim necekejte vice nez strucnou vyzvu k dukladnejsimu prostudovani
manualu procesoru.
K testum: Zakladni pokyny pro integraci testu s Vasim resenim jsou
popsany v zadani. V pripade kernelovych testu (1. a 2. zadani) byste
meli testy zaintegrovat po vzoru testu v adresari kernel/tests/basic ve
zdrojovem strome Kalista. Cilem tedy je, aby bylo mozne testy co
nejsnadneji a pokud mozno bez lidskeho zasahu spustit a vyhodnotit
(krome rucniho vyhodnoceni nekolika interaktivnich testu).
Infrastrukturu testu si muzete pochopitelne upravit tak, aby odpovidala
zpusobu prekladu a pripadne dalsim specifikum Vaseho reseni (napr. v
pripade kolize nazvu globalnich symbolu/maker). Urcite vsak neni
dovoleno modifikovat logiku testu (tedy to, co testy fakticky testuji).
Testy zakladniho zadani je nutne splnit bez vyhrad pro postup do dalsi
faze reseni semestralni prace. Testy pro rozsirena zadani na druhou
stranu slouzi jen jako jedno z mnoha kriterii hodnoceni kvality Vaseho
reseni.
Pro 3. rozsirene zadani nemame specialni sadu testu (zpusob, jakym
budete implementovat spousteni procesu z diskoveho zarizeni, se muze
skupinu od skupiny dramaticky lisit). Pro testovani muzete napriklad
vyuzit testy zakladniho zadani, ktere budete poustet paralelne v
nekolika nezavislych procesech.
Na zaver pripojuji strucnou rekapitulaci nejblizsich dulezitych terminu
semestru:
* 8. a 10. 10. 2012 probehnou cviceni zamerena na seznameni s
prostredim pro vypracovani semestralnich praci.
* 15. a 17. 10. 2012 probehnou cviceni zamerena na podrobne seznameni se
zdrojovym kodem Kalista.
* Do 14. 10. 2012 mi prosim nahlaste slozeni sveho tymu a preference
rozsireneho zadani. Kratce po tomto datu posleme kazdemu prihlasenemu
studentu email s pristupovymi udaji k repository sveho tymu.
* Standardni termin pro odevzdani 1. zakladniho zadani je 11. 11. 2012.
Zcela presne budeme testovat, zda projde testy 1. zakladniho zadani
obsah Vaseho repository s casovym razitkem 12. 11. 2012 00:00 CET.
M.D.
-------------- next part --------------
Zadani 1. semestralni prace: -----------------------------------------------
Cilem 1. semestralni prace je naprogramovat kostru jadra operacniho
systemu, ktera bude pouzita pro navazujici semestralni prace. Zadani
ma formu rozhrani, ktere je nutno naimplementovat. K zajisteni rozumne
urovne funkcnosti je nutne, aby implementace prosla sadou testu.
Kostrou jadra je minen kod, ktery poskytuje zakladni prostredky pro
ladeni a budouci rozsireni. Ukolem tedy bude naprogramovat:
* zakladni vstupne/vystupni operace
* zakladni ladici prostredky
* obsluhu preruseni a vyjimek
* jednoduchy alokator pameti
* podporu pro vlakna
* jednoduchy planovac
* synchronizacni primitiva
* podporu pro casovace
Pri vypracovani muzete vychazet z vyukoveho jadra Kalisto a v jeho kodu
postupne nahrazovat pomerne jednoduche a omezene implementace nekterych
vyse uvedenych casti jadra.
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.
Poznamky k rozhranim
--------------------
V zadani naleznete primarne dva typy rozhrani k ruznym typum objektu
a datovych struktur. Rozhrani se lisi v mire skryvani implementacnich
detailu spravovanych objektu.
* Prvni typ rozhrani skryva implementacni detaily mene a pracuje primo
s ukazateli na datove struktury. Entity spravovane timto rozhranim
maji vetsinou staticky charakter, takze jsou alokovany uzivatelem bud
na zasobniku nebo jako staticke promenne. Rozhrani poskytuje funkce
xxx_init, ktere slouzi k inicializaci datovych struktur a xxx_destroy,
ktere slouzi k jejich "uklidu".
Je samozrejme mozne tyto entity alokovat i dynamicky, neni to ovsem
prilis casty pripad a za alokaci a uvolneni pameti je zodpovedny
uzivatel.
Tento typ rozhrani rovnez typicky nevraci chybove kody pri predani
neplatneho ukazatele na spravovany objekt, nebot chyba takoveho
charakteru je zpravidla fatalni (pro jadro). Pro ladici ucely je
vhodne do volani funkci tohoto typu pridat otestovani platnosti
ukazatele (non-NULL) a napr. otestovani integrity referencovane
struktury. Casto se pro ladici ucely nekam do struktury objektu
vklada atribut, ktery musi mit nejakou konstatni preddefinovanou
("magic") hodnotu.
Uvedeny typ rozhrani je pouzit napriklad pro vsechna synchronizacni
primitiva a casovace.
* Druhy typ rozhrani skryva implementacni detaily vice, tedy napriklad
to, ze pracuje s ukazateli. Uzivateli poskytuje obecny typ, ktery
slouzi k identifikaci objektu, at uz je implementaci rozhrani chapan
jako ukazatel, nebo jako identifikator. Rozhrani poskytuje funkci
xxx_create, ktera slouzi k vytvareni a potazmo "aktivaci" novych
objektu. To zahrnuje alokaci pameti pro slozitejsi datove struktury,
inicializaci a dalsi operace, jejich implementace ma byt pred
uzivatelem skryta.
Entity tohoto typu mivaji zpravidla dynamicky charakter, v ojedinelych
pripadech byvaji alokovany staticky, coz vsak byva pred uzivatelem
skryto.
Tento typ rozhrani vraci chybove kody pri neplatne identifikaci
spravovaneho objektu, nebot chyba takoveho charakteru nebyva vetsinou
fatalni (pro jadro).
Uvedeny typ ma i rozhrani k vlaknum operacniho systemu, kde napr.
funkce thread_create vedle alokace pameti pro ridici strukturu a
zasobnik vlakna a jeho inicializace zajistuje take zacleneni noveho
vlakna do struktur planovace.
Obecne pozadavky
----------------
* deklarace a pouzivani chybovych kodu
EOK = 0 "pseudo" chybovy kod, indikuje uspech
ENOMEM nedostatek pameti pro provedeni operace
EINVAL nektery z argumentu je neplatny
EKILLED vlakno, ktere bylo predmetem cekani, bylo zruseno
ETIMEDOUT vyprsel casovy limit pro provedeni operace
EWOULDBLOCK operace by zablokovala volajici vlakno
S vyjimkou EOK by chybovym kodum mela byt prirazena zaporna cisla.
* obecne datove typy
Definujte standardni prenositelne typy celych cisel pomoci generickych
celociselnych typu jazyka C na platforme MIPS:
int8_t, uint8_t, int16_t, uint16_t, int32_t, uint32_t, int64_t, uint64_t
(pro presne definice techto typu muzete vyuzit Kalisto)
Na zaklade techto typu definujte pomocne celociselne typy:
native_t int32_t (znamenkovy typ velikosti obecneho registru)
unative_t uint32_t (neznamenkovy typ velikosti obecneho registru)
uintptr_t uint32_t (typ pro prevod ukazatele na cislo)
off_t uint32_t (typ pro offset)
size_t uint32_t (typ pro velikost)
ssize_t int32_t (znamenkovy typ pro velikost)
* podpora pro ladeni
Pri implementaci rozhrani synchronizacnich primitiv a casovacu
vytvorte podporu pro kontrolu platnosti predanych ukazatelu, kterou
bude mozne aktivovat/deaktivovat definici nejakeho symbolu pri
prekladu jadra. Pouziti ladiciho mechanizmu zdokumentujte.
* zdrojove texty
Nasledujici doporuceni odrazi pozadavky na uroven zdrojovych textu,
ktere budou hodnoceny pri odevzdani prace.
- vyhybejte se pouzivani numerickych konstant primo v kodu, nahradte
je makry
- pouzivejte prazdne radky a blokove komentare k oddeleni logickych
casti 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
- komentujte obsah souboru, funkci a implementacni detaily; pro
inspiraci viz komentare ve stylu JavaDoc nebo Doxygen
Zakladni zadani ------------------------------------------------------------
Pro zakladni zadani postacuje, pokud budou veskere operace korektne
synchronizovany a odladeny na systemu vybavenem jedinym procesorem.
V tomto pripade zakazani preruseni staci k zajisteni atomicity operaci.
Zakladni vstupne/vystupni operace
---------------------------------
* size_t putc(const char chr)
Funkce vypise znak na konzoli. Vraci pocet vypsanych znaku.
* size_t puts(const char *str)
Funkce vypise retezec na konzoli. Vraci pocet vypsanych znaku.
* size_t printk(const char *format, ...)
Funkce vypise formatovany retezec na konzoli, stejne jako printf
v knihovne libc. Formatovaci kody by mely podporovat znaky (%c),
retezce (%s), cela cisla v desitkove (%d, %u, %i) a v sestnactkove
(%x) soustave a ukazatele (%p). Neni nutne implementovat modifikatory
pro zarovnavani a platne cislice. Funkce vraci pocet vypsanych znaku.
Poznamka: Pro implementaci variadickych funkci jsou potreba funkce
va_start(), va_arg(), va_end() apod. Neni prilis vhodne tyto funkce
implementovat rucne (prochazenim zasobniku), protoze tim se nezaruci
shoda chovani techto funkci s chovanim prekladace (napr. v pripade
zmeny ABI). Vhodnejsi je vyuzit builtin funkci a typu pro implementaci
variadickych funkci a typu, ktere poskytuje primo prekladac
(__builtin_va_list, __builtin_va_start atd.).
* char getc(void)
Funkce precte a vrati znak z klavesnice. Pokud neni ve vyrovnavaci
pameti klavesnice zadny znak, zablokuje volajici vlakno a ceka na
stisk klavesy. Cekani na znak by melo byt pasivni, aktivni polling
je velmi nevhodne reseni. Zaroven je vhodne, aby pasivni cekani
bylo implementovano maximalne genericky (pomoci synchronizacnich
primitiv), tedy ne napriklad "zadratovanim" algoritmu cekani na znak
primo do planovace.
Poznamka: Za dostatecnou implementaci klavesnicoveho bufferu je
povazovano pole konstantni velikosti. Pri zaplneni klavesnicoveho
bufferu je pripustne dalsi znaky "zahazovat". Pokud se rozhodnete
implementovat dynamicky klavesnicovy buffer, mejte na zreteli
komplikace, ktere mohou plynout napriklad z potreby alokovat pamet
pro novy znak v ramci obsluhy preruseni klavesnice.
I pri pouziti konstatniho klavesnicoveho bufferu je vsak nutne dodrzet
spravnou synchronizaci zapisu a cteni. Uvedomte si dobre, jaka jsou
uskali synchronizace pri pouziti reentrantnich a nereentrantnich
zpusobu obsluhy preruseni.
* int getc_try(void)
Funkce precte a vrati znak z klavesnice. Pokud neni ve vyrovnavaci
pameti klavesnice zadny znak, vrati EWOULDBLOCK.
* ssize_t gets(char *str, const size_t len)
Funkce precte nejvice len - 1 znaku z klavesnice do bufferu str. Cteni
je ukonceno pri precteni (a ulozeni) znaku '\n' nebo pri dosazeni
limitu. Prectene znaky jsou vzdy ukonceny znakem 0. Vraci EINVAL pokud
len == 0, jinak pocet znaku ulozenych do bufferu bez ukoncovaci 0.
Cekani na jednotlive znaky by opet melo byt reseno pasivne.
Zakladni ladici prostredky
--------------------------
* makro assert(EXPR)
Pokud neni definovano makro NDEBUG, makro assert() vyhodnoti vyraz EXPR
a pokud je vysledek nulovy, zavola panic s informaci o nazvu funkce,
souboru a cisle radku, na kterem nebyl splnen predpoklad EXPR. Pokud je
makro NDEBUG definovano, makro assert() neudela nic.
* makro dprintk(ARGS...)
Pokud neni definovano makro NDEBUG, makro dprintk() vypise na konzoli
informaci o nazvu funkce a cislo radku, na kterem bylo pouzito, a
formatovany retezec ARGS. Pokud je makro NDEBUG definovano, makro
dprintk() neudela nic.
* void panic(const char *format, ...)
Funkce vypise formatovany retezec na konzoli (stejne jako printk),
vypise identifikator prave beziciho vlakna, obsah registru procesoru
a zastavi beh jadra.
Obsluha preruseni a vyjimek procesoru
-------------------------------------
Napiste obsluznou rutinu pro obsluhu nasledujicich vyjimek procesoru.
Kostru pro obsluhu vyjimek a predani rizeni do obsluzne rutiny v jazyce
C naleznete ve vyukovem jadre Kalisto:
* interrupt (Int)
Zjistete zdroj preruseni a obsluzte jej. Uvedomte si, ze v jeden okamzik
muze indikovat preruseni vice zdroju soucasne.
* address error (AdEL, AdES)
Nastava pri cteni/zapisu z/na nezarovnanou adresu a pri pristupu
do adresoveho prostoru jadra z uzivatelskeho rezimu. Nastala-li vyjimka
v kernelu, vyvolejte panic, v opacnem pripade zabijte prislusne vlakno.
* bus error (IBE, DBE)
Nastava pri pristupu na neplatnou fyzickou adresu. Nastala-li vyjimka
v kernelu, vyvolejte panic, v opacnem pripade zabijte prislusne vlakno.
* break point (BP)
Nastava pri vykonani instrukce BREAK. Vyjimku je mozne ignorovat, pokud
neni instrukce v branch delay slotu. Byla-li instrukce v brach delay
slotu a nastala-li vyjimka v kernelu, vyvolejte panic, v opacnem pripade
zabijte prislusne vlakno.
* reference to WatchHi/WatchLo address (WATCH)
Nastava pri pristupu do rozmezi adres definovaneho registry CP0
WatchHi a WatchLo. Vyjimku je mozne ignorovat, pripadne pouzit pro
vlastni ladici ucely.
* reserved instruction (RI)
Nastava pri neznamem operacnim kodu instrukce, v principu neznama
instrukce -- da se pouzit k emulaci nekterych instrukci. Nastala-li
vyjimka v kernelu, vyvolejte panic, v opacnem pripade zabijte prislusne
vlakno.
* coprocessor unusable (CpU)
Nastava pri pristupu na koprocesor, ktery neni neni oznacen jako
pristupny. Nastala-li vyjimka v kernelu, vyvolejte panic, v opacnem
pripade zabijte prislusne vlakno.
* trap exception (Tr)
Nastava pri provedeni podminenych instrukci Txx. V ramci semestralni
prace nejsou tyto instrukce k nicemu vyuzivany, takze nastala-li vyjimka
v kernelu, vyvolejte panic, v opacnem pripade zabijte prislusne vlakno.
* arithmetic overflow (Ov)
Nastava pri preteceni dvojkoveho doplnku pri celociselnych operacich
(prenosy z bitu 31 a 30 se lisi). Nastala-li vyjimka v kernelu,
vyvolejte panic, v opacnem pripade zabijte prislusne vlakno.
Rizeni preruseni
----------------
* makro save_and_disable_interrupts(status)
Makro ulozi soucasny obsah stavoveho registru CP0 do promenne a
globalne zakaze preruseni procesoru.
* makro restore_interrupts(status)
Makro obnovi obsah stavoveho registru CP0 z promenne, cimz obnovi
globalni stav povoleni/zakazni preruseni, ktery predchazel pouziti
makra save_and_disable_interrupts().
* makro/funkce void disable_interrupts(void)
Funkce globalne zakaze preruseni na procesoru.
* makro/funkce void enable_interrupts(void)
Funkce globalne povoli preruseni na procesoru.
Jednoduchy alokator pameti
--------------------------
Pri behu operacniho systemu je casto nutne radu objektu alokovat
dynamicky. Vyukove jadro Kalisto ma implementovan jednoduchy alokator
pameti, ktery poskytuje funkce malloc() a free(). Tyto funkce by melo
poskytovat i vase jadro, pricemz je mozne ponechat puvodni implementaci.
Spravnost funkce alokatoru nebude testovana a inteligence alokatoru
nebude hodnocena, pokud pouzijete alokator z Kalista nebo vlastni
trivialni alokator podobnych vlastnosti. Budete-li dobrovolne
implementovat pokrocilejsi alokator, bude ocenen body navic.
* void *malloc(const size_t size)
Funkce alokuje blok pameti pozadovane velikosti z heapu. Vraci NULL
pokud nebylo mozne blok alokovat, jinak ukazatel na zacatek alokovaneho
bloku.
* void free(const void *ptr)
Funkce uvolni blok pameti, na ktery ukazuje ptr a ktery byl predtim
naalokovan funkci malloc().
Jednoduchy planovac
-------------------
Naimplementujte preemptivni planovani vlaken k behu na procesoru. Staci
zakladni strategie round-robin bez priorit.
Rozhrani pro praci s vlakny
---------------------------
* int thread_create(
thread_t *thread_ptr, void *(*thread_start)(void *), void *data,
const thread_flags_t flags)
Funkce vytvori nove (attached) vlakno. Vraci chybovy kod, pokud se
vlakno nepodari vytvorit, jinak EOK. Funkce
void *thread_start(void *data)
bude spustena v nove vytvorenem vlakne. Pocet vlaken v systemu je
omezen pouze dostupnou pameti.
Za vytvorenim vlakna se skryva alokace a inicializace ridici datove
struktury obsahujici informace o vlaknu, alokace zasobniku pro vlakno,
a zarazeni vlakna do struktur planovace. Z toho duvodu je vlakno
identifikovano pro uzivatele rozhrani "nepruhlednym" typem thread_t.
Parametr flags je mozne ignorovat, bude slouzit pro modifikaci chovani
funkce v navazujicich zadanich.
* thread_t thread_get_current(void)
Funkce vrati identifikaci prave beziciho vlakna.
* int thread_join(thread_t thr)
* int thread_join_timeout(thread_t thr, const unsigned int usec)
Funkce ceka na dokonceni behu uvedeneho vlakna a iniciuje uvolneni
pameti obsahujici ridici strukturu jadra a zasobnik. Vraci EINVAL
pokud je identifikace vlakna neplatna, pokud bylo vlakno odpojeno
pomoci thread_detach(), pokud jiz na vlakno ceka nekdo jiny, nebo
pokud vlakno vola funkci samo na sebe. Vraci EKILLED pokud bylo
vlakno zruseno volanim funkce thread_kill().
Varianta _timeout ceka (pasivne) na ukonceni vlakna nejdele usec
mikrosekund. Pokud vlakno neni ukonceno do uplynuti teto doby, vraci
ETIMEDOUT.
* int thread_detach(thread_t thr)
Funkce odpoji zadane vlakno. Vraci EINVAL pokud je identifikace
vlakna neplatna, vlakno je jiz odpojene, vlakno jiz nebezi a ceka
na join nebo pokud na vlakno jiz nekdo ceka v thread_join().
Odpojene (detached) vlakno se od pripojeneho (attached) vlakna lisi
tim, ze neni mozne cekat na jeho ukonceni a pri skonceni jadro
automaticky uvolni pamet alokovanou pro ridici strukturu jadra a
jeho zasobnik.
* void thread_sleep(const unsigned int sec)
* void thread_usleep(const unsigned int usec)
Funkce zablokuje prave bezici vlakno na zadanou dobu v sekundach
(resp. mikrosekundach). Vlakno nesmi byt zablokovano na kratsi dobu
nez bylo zadano, rozumne zduvodnene prodlouzeni teto doby lze
tolerovat. Cekani na vyprseni doby by melo byt realizovano pasivne,
aktivni polling neni pripustny.
Poznamka: V pripade varianty thread_sleep() je nutne zajistit spravne
fungovani pro cely rozsah typu "unsigned int" bez nebezpeci preteceni.
Cekani lze tedy realizovat opakovanym volanim thread_usleep().
* void thread_yield(void)
Vlakno volajici thread_yield() se vzda rizeni, dokud nebude znovu
naplanovano k behu.
* void thread_suspend(void)
Vlakno volajici thread_suspend() se zablokuje, dokud jej jine
vlakno neodblokuje pomoci funkce thread_wakeup().
* int thread_wakeup(thread_t thr)
Funkce odblokuje zadane vlakno. Volajici vlakno pokracuje v behu,
neni v dusledku tohoto volani preplanovano. Funkce vraci EINVAL
pokud je identifikace vlakna neplatna, jinak EOK.
* int thread_kill(thread_t thr)
Funkce zrusi zadane (bezici) vlakno. Vlakno, ktere ceka na ukonceni
ruseneho vlakna, je odblokovano. Funkce vraci EINVAL pokud je
identifikace vlakna neplatna, jinak EOK.
Podpora casovacu
----------------
Casovace slouzi k implementaci asynchronnich udalosti, pro ktere je
nevhodne (z duvodu moznosti selhani alokace pameti) vytvaret nove
vlakno. Obsluzne rutiny casovacu bezi na ukor vlakna, ktere bylo
casovacem preruseno, nebo v kontextu systemoveho vlakna pro obsluhu
casovacu (obe varianty maji ruzne vyhody, nevyhody a inherentni
omezeni kladena na obsluzne rutiny casovacu, proto sve rozhodnuti
vhodne zdokumentujte).
* int timer_init(
struct timer *tmr, const unsigned int usec,
void (*handler)(struct timer *, void *), void *data)
Funkce inicializuje strukturu casovace pro dobu usec mikrosekund.
Vraci EINVAL pokud je handler NULL, jinak OK. Casovac po inicializaci
neni aktivni, aktivace se provadi funkci timer_start().
* void timer_start(struct timer *tmr)
Funkce aktivuje casovac a prida ho do seznamu aktivnich casovacu.
Pri vyprseni casoveho limitu je zavolana obsluzna rutina
void handler(struct timer *self, void *data)
Parametr self odkazuje na strukturu casovace, ktera vedla k jejimu
vyvolani. Pri zavolani timer_start na jiz aktivni casovac dojde k jeho
restartovani.
* void timer_destroy(struct timer *tmr)
Funkce deaktivuje casovac, odebere ho ze seznamu aktivnich casovacu a
provede uklid ridici struktury. Vykonavani obsluzne rutiny casovace
neni preruseno, pokud jiz bezi.
* int timer_pending(struct timer *tmr)
Funkce vraci nenulovou hodnotu pokud je casovac aktivni, jinak 0.
Synchronizacni primitiva
------------------------
Pri implementaci predpokladejte, ze kod muze byt kdykoliv prerusen,
pokud nejsou zakazana preruseni.
- mutex (zamek, binarni semafor)
* void mutex_init(struct mutex *mtx)
Funkce inicializuje mutex do stavu odemceno.
* void mutex_destroy(struct mutex *mtx)
Funkce provede uklid ridici struktury mutexu. Pokud je rusen mutex,
na kterem jsou jeste zablokovana nejaka vlakna, funkce vyvola panic.
* void mutex_lock(struct mutex *mtx)
* int mutex_lock_timeout(struct mutex *mtx, const unsigned int usec)
Funkce se pokusi zamknout mutex. Pokud to neni mozne, zablokuje
vlakno na mutexu.
Varianta _timeout ceka (pasivne) na zamknuti mutexu nejdele usec
mikrosekund. Pokud se behem teto doby podari mutex zamknout, vraci EOK,
jinak ETIMEDOUT. Pokud je casovy limit 0, k zablokovani vlakna nedochazi.
* void mutex_unlock(struct mutex *mtx)
Funkce odemkne zadany mutex a vzbudi vlakna, ktera byla zablokovana
pri zamykani mutexu. Pokud je makro DEBUG_MUTEX >= 1, bude
implementace mutexu hlidat, zda je odemykan vlaknem, ktere ho puvodne
zamknulo. Pokud bude mutex odemykat jine vlakno, vyvola panic.
Integrace s testy
-----------------
K integraci s testy vytvorite hlavickovy soubor api.h, ktery bude typicky
obsahovat #include direktivy, ktere zajisti vlozeni vasich hlavickovych
souboru s prislusnymi deklaracemi.
Dale musi soubor api.h obsahovat deklaraci extern funkce run_test(void),
kterou zavolate z vaseho jadra pro spusteni testu.
Rozsirene zadani -----------------------------------------------------------
Rozsirene zadani vychazi ze zakladniho zadani, musi tedy implementovat
vsechny funkce rozhrani zakladniho zadani. Neni-li uvedeno jinak, zustavaji
pozadavky na jejich chovani nezmeneny.
Krome toho je nutne, aby byly vsechny operace vsech zakladnich zadani
korektne synchronizovany a odladeny na konfiguraci s vice procesory,
zakazani preruseni na jednom procesoru tedy obecne nemusi zajistit
atomicitu provadenych operaci. Je vhodne, aby se jiz behem implementace
2. a 3. zakladniho zadani pouzivaly korektne synchronizacni primitiva a
dalsi postupy pro spravny pristup ke sdilenym datum na vice procesorech.
Implementace nesmi byt omezena nejakym konstantnim poctem nakonfigurovanych
procesoru (vyjma omezeni, ktera vyplyvaji primo z vlastnosti simulatoru,
resp. procesoru MIPS) nebo predpokladat konkretni pocet procesoru. Je
vhodne, aby zakladni inicializace jadra probihala na jedinem procesoru
(tzv. "bootstrap processor"), zatimco ostatni procesory (tzv. "application
processors") byly pouzity az pro planovani beznych vlaken.
Zakladni vstupne/vystupni operace
---------------------------------
* size_t printk(const char *format, ...)
Funkce printk() by mela zajistit, aby vypis retezce z vlakna beziciho
na jednom procesoru nebyl prerusen vypisem retezce z vlakna beziciho
paralelne na jinem procesoru. Zaroven vsak nesmi dojit k deadlocku
pri pouziti printk() pro ladici ucely, pri vypisu panic hlasky apod.
Zakladni ladici prostredky
--------------------------
* void panic(const char *format, ...)
Krome identifikatoru prave beziciho vlakna a obsahu registru
aktualniho procesoru vypise funkce take identifikator procesoru, na
kterem byla vyvolana. Funkce rovnez zablokuje beh vsech procesoru.
Jednoduchy planovac
-------------------
Kazdy procesor bude strategii round-robin planovat vlakna nezavisle,
neni nutne implementovat dynamicky load ballancing. Priblizne rovnomerneho
vyuziti vsech procesoru staci dosahnout jednorazovym rozmistovanim vlaken
na procesory ve funkci thread_create().
Synchronizacni primitiva
------------------------
Pasivni synchronizacni primitiva implementujte pokud mozno s malou
latenci, tedy vyuzitim kritickych sekci ochranenych aktivnim
synchronizacnim primitivem (spinlockem).
Je take vhodne ponechat i pri pouzivani spinlocku zakazovani preruseni
na aktualnim procesoru, coz pomaha snizovat cistou dobu vykonavani kriticke
sekce a tim zvysuje celkovou propustnost systemu (zkracenim doby, po kterou
je omezen paralelismus systemu).
- spinlock (aktivni synchronizacni primitivum)
* void spinlock_init(struct spinlock *lock)
Funkce inicializuje spinlock do stavu odemceno.
* void spinlock_destroy(struct spinlock *lock)
Funkce provede uklid ridici struktury spinlocku. Pokud je rusen
spinlock, ktery je aktualne zamcen, funkce vyvola panic.
* void spinlock_lock(struct spinlock *lock)
Funkce se bude opakovane v aktivnim cyklu pokouset zamknout spinlock,
dokud se ji to nepovede. Test a zamknuti spinlocku musi byt zajisteno
operaci, ktera se provede v ramci celeho systemu a vsech procesoru
atomicky.
* void spinlock_unlock(struct spinlock *lock)
Funkce odemkne zadany spinlock.
- semafor
* void sem_init(struct semaphore *sem, const int value)
Funkce inicializuje semafor a nastavi ho na zadanou hodnotu.
* void sem_destroy(struct semaphore *sem)
Funkce provede uklid ridici struktury semaforu. Pokud je rusen
semafor, na kterem jsou jeste zablokovana nejaka vlakna, funkce
vyvola panic.
* int sem_get_value(struct semaphore *sem)
Funkce vrati hodnotu semaforu >= 0.
* void sem_up(struct semaphore *sem)
Funkce inkrementuje hodnotu semaforu a pripadne odblokuje jedno
z vlaken na nem zablokovanych.
* void sem_down(struct semaphore *sem)
* int sem_down_timeout(struct semaphore *sem, const unsigned int usec)
Funkce dekrementuje hodnotu semaforu, pokud je to mozne, jinak
vlakno na semaforu zablokuje.
Varianta _timeout ceka (pasivne) na dekrementovani hodnoty semaforu
nejdele usec mikrosekund. Pokud se behem teto doby podari semafor
dekrementovat, vraci EOK, jinak ETIMEDOUT. Pokud je casovy limit 0,
k zablokovani vlakna nedochazi.
Semafory budou pouzivany nasledujicim zpusobem:
struct semaphore sem;
sem_init(&sem, 100);
...
sem_destroy(&sem);
- read/write lock (rekurzivni)
* void rwlock_init(struct rwlock *rwl)
Funkce inicializuje ridici strukturu r/w zamku do stavu odemceno.
* void rwlock_destroy(struct rwlock *rwl)
Funkce provede uklid ridici struktury zamku. Pokud je rusen zamek,
na kterem jsou jeste zablokovana nejaka vlakna, funkce vyvola panic.
* void rwlock_read_lock(struct rwlock *rwl)
* void rwlock_write_lock(struct rwlock *rwl)
* int rwlock_read_lock_timeout(
struct rwlock *rwl, const unsigned int usec)
* int rwlock_write_lock_timeout(
struct rwlock *rwl, const unsigned int usec)
Funkce se pokusi zamknout zamek v pozadovanem rezimu, pokud to neni
mozne, zablokuje volajici vlakno na zamku.
Varianta _timeout ceka (pasivne) na zamknuti zamku nejdele usec
mikrosekund. Pokud se behem teto doby podari zamek zamknout, vraci EOK,
jinak ETIMEDOUT. Pokud je casovy limit 0, k zablokovani vlakna nedochazi.
* void rwlock_write_unlock(struct rwlock *rwl)
* void rwlock_read_unlock(struct rwlock *rwl)
Funkce odemkne zamek a odblokuje vlakna zablokovana na zamku.
- condition variable
* void cond_init(struct cond *cvar)
Funkce inicializuje ridici strukturu condition variable.
* void cond_destroy(struct cond *cvar)
Funkce provede uklid struktury condition variable. Pokud je rusena
condition variable, na ktere jsou jeste zablokovana nejaka vlakna,
funkce vyvola panic.
* void cond_signal(struct cond *cvar)
* void cond_broadcast(struct cond *cvar)
Funkce odblokuje jedno resp. vsechna vlakna cekajici na
condition variable.
* void cond_wait(struct cond *cvar, struct mutex *mtx)
* int cond_wait_timeout(
struct cond *cvar, struct mutex *mtx, const unsigned int usec)
Funkce atomicky odemkne mutex a zablokuje volajici vlakno na
condition variable. Po odblokovani opet zamkne mutex a vrati
rizeni volajicimu.
Varianta _timeout zablokuje vlakno nejdele na usec mikrosekund, resp.
na dobu odpovidajici limitu a dobu nutnou k opetovnemu zamceni mutexu.
Pokud behem teto doby dojde k odblokovani vlakna, vraci EOK, jinak
ETIMEDOUT. Pokud je casovy limit 0, k zablokovani vlakna nedochazi,
ale pred opetovnym zamcenim mutexu se vlakno jednou vzda procesoru.
Neblokujici seznamy
-------------------
V ramci vlastniho privatniho rozhrani navrhnete a implementujte specialni
variantu datove struktury spojoveho seznamu, ktera bude implementovat
operace "pridani prvku do seznamu" a "odebrani prvku ze seznamu"
bez pouziti synchronizacnich primitiv a zaroven zajisti konzistenci
seznamu i na viceprocesorovem systemu.
Rozhrani teto datove struktury by melo byt shodne nebo maximalne podobne
rozhrani klasicke implementace spojovych seznamu, ktera pro zajisteni
konzistence pouziva bezna synchronizacni primitiva.
Pro implementaci neblokujicich seznamu lze vyuzit libovolny vhodny
algoritmus, napriklad [1]. Vetsina takovych algoritmu vyzaduje pro svou
spravnou funkci atomickou operaci compare-and-swap, jejiz atomicitu
lze na platforme MIPS zajistit vhodnym pouzitim instrukci LL (load linked)
a SC (store conditional).
Navrhnete a implementujte take vhodny vicevlaknovy test/benchmark, ktery
bude obe varianty implementace spojovych seznamu testovat a merit dobu
provadeni ruznych operaci. V dokumentaci potom uvedte porovnani chovani
obou implementaci.
[1] Harris T. L.: A Pragmatic Implementation of Non-blocking Linked-Lists,
Proceedings of the 15th International Conference on Distributed
Computing, LNCS 2180, Springer-Verlag, 2001
http://research.microsoft.com/en-us/um/people/tharris/papers/2001-disc.pdf
--
Posledni modifikace: 2012/10/07 17:00
-------------- next part --------------
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 je nutne, aby implementace prosla sadou testu.
Ukolem bude naprogramovat:
* alokator fyzickych stranek (ramcu) pameti
* spravce 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 32bitovy
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.
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 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 (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
--------------------------
V kontextu operacniho systemu je virtualni adresovy prostor, nebo take
nazyvany 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 typicky
alokovan po souvislych 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 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.
Kostra kernelu z 1. semestralni prace dosud pracuje pouze s nezavislymi
vlakny, ktera bezi v rezimu jadra. Pro nasledny prechod k uzivatelskym
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.
Zakladni zadani ------------------------------------------------------------
Alokator fyzicke pameti
-----------------------
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.
* 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 je @cnt je rovno nule nebo alokace
nebyla uspesna, vraci ENOMEM. V opacnem pripade 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 ve @paddr (priznak VF_VA_AUTO), nebo se
pokusi o alokaci zacinajici na fyzicke adrese zadane volajicim ve
@paddr (priznak VF_VA_USER).
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.) nebo fyzicke stranky 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 staticky alokovanou
pamet pro kod a data jadra, struktury samotneho alokatoru apod.
Je pripustne, aby bylo nejprve pomoci jednoho volani funkce
frame_alloc() naalokovano nekolik fyzickych stranek a podintervaly
techto fyzickych stranek byly pote jednotlive uvolnovany opakovanym
volanim frame_free(). Podobne je mozne pomoci 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
fyzicke stranky nebo posloupnost @cnt po sobe jdoucich fyzickych stranek
nebyla drive alokovana pomoci frame_alloc().
Uprava stavajiciho alokatoru haldy
----------------------------------
Stavajici kernelovy alokator 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.
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 rozsirte chovani funkce thread_create() ze zadani
1. semestralni prace:
* int thread_create(
thread_t *thread_ptr, void *(*thread_start)(void *), 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.
Sprava virtualniho adresniho prostoru
-------------------------------------
Sprava oblasti virtualni pameti zahrnuje alokaci, manipulaci a
uvolnovani oblasti virtualni pameti v kontextu virtualniho adresoveho
prostoru prave beziciho vlakna. V ramci zakladniho zadani sestava
virtualni adresovy prostor z nejvyse MAX_AREAS souvislych oblasti.
Oblasti se nesmi prekryvat, velikost a zacatek oblasti musi byt
zarovnan na nejmensi velikost stranky podporovanou procesorem,
v pripade MIPS R4000 tedy 4 KiB.
Konstantu MAX_AREAS vhodne urcete tak, aby vyhovovala zamyslenym
pozadavkum vlaken na alokaci oblasti virtualni pameti. V ramci
zakladniho zadani je pripustne pro reprezentaci virtualniho adresoveho
prostoru pouzit staticky alokovane datove struktury, tedy datove
struktury napevno dimenzovane na MAX_AREAS oblasti virtualni pameti.
Zaroven je pripustne, aby operace nad temito datovymi strukturami
mely linearni slozitost v zavislosti na hodnote konstanty MAX_AREAS,
lze tedy napriklad pouzit staticke pole.
* int vma_map(
void **from, const size_t size, const vm_flags_t flags)
Funkce alokuje oblast ve virtualnim adresovem prostoru o velikosti
@size bajtu, pro tuto oblast alokuje fyzickou pamet (ne nutne souvislou)
a vytvori mapovani prave alokovane 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 nebo jiz bylo dosazeno MAX_AREAS oblasti
virtualni pameti.
* int vma_resize(const 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 nebo zvetseni
oblasti za hranici prislusneho segmentu.
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 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.
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 obsazeny.
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 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.
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.
Soucasne je nutne, aby pocet adresovych prostoru nebyl omezen rozsahem
platnych ASID hodnot. Pridelovani ASID hodnot je tedy nutne provadet
dynamicky, napriklad algoritmem LRU.
Kopirovani pameti mezi vlakny
-----------------------------
Pro testovaci ucely implementujte nasledujici funkce:
* int copy_from_thread(const 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(const 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 api.h, ktery bude typicky
obsahovat #include direktivy, ktere zajisti vlozeni vasich hlavickovych
souboru s prislusnymi deklaracemi.
Hlavickovy soubor api.h by mel take obsahovat makro FRAME_SIZE, jehoz
hodnota bude odpovidat velikosti fyzicke stranky (ramce), resp. virtualni
stranky v bajtech, kterou kernel pouziva.
Rozsirene zadani -----------------------------------------------------------
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.
Pozadavky na rozhrani pro spravu virtualni pameti zachovava chovani
pozadovane pro zakladni zadani, pocet oblasti virtualni pameti jiz vsak
nesmi byt omezen konstatnou, ale je dan pouze realne dostupnou pameti.
Pro spravu oblasti virtualni pameti pouzijte vhodnou datovou strukturu
(nikoliv staticky alokovanou), pricemz duraz je kladen na rozumne rychle
nalezeni oblasti virtualni pameti k dane virtualni adrese a i take nalezeni
odpovidajici fyzicke adresy. Casova slozitost takove operace by tedy mela
byt lepsi nez linearni vzhledem k poctu oblasti a velikosti oblasti.
Rozumnymi kandidaty na takovou datovou strukturu jsou naprikad stromove
struktury, hashovaci struktury nebo hierarchicke strankovaci tabulky.
Motivace a cile pro vyber pouzite datove struktury dukladne rozeberte
v dokumentaci.
* int vma_map(
void **from, const size_t size, const vm_flags_t flags)
Funkce alokuje oblast ve virtualnim adresovem prostoru o velikosti
@size bajtu, pro tuto oblast alokuje fyzickou pamet (ne nutne souvislou)
a vytvori mapovani prave alokovane 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.
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 obsazeny.
* int vma_resize(const 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 nebo zvetseni
oblasti za hranici prislusneho segmentu.
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 vma_remap(const void *from, const 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 vma_merge(const void *area1, const void *area2)
Funkce spoji oblasti zacinajici na @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, pokud spolu nesousedi
nebo pokud oblasti patri do ruznych segmentu.
* int vma_split(const void *from, const 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.
Novy alokator haldy
-------------------
Implementujte novy alokator kernelove haldy jako funkcni nahradu
jednoducheho alokatoru z 1. semestralni prace. Alokator bude vracet
pouze pamet ze segmentu KSEG0 virtualniho adresoveho prostoru procesoru,
tj. bude mozne k alokovane pameti pristupovat bez pouziti TLB.
Implementujte nejmene tyto alokacni strategie:
* first fit
* next fit
* best fit
* worst fit
Vyber pozadovane alokacni strategie bude mozny v dobe prekladu, napriklad
pomoci nastaveni hodnoty vhodneho makra na konstanty
MALLOC_STRATEGY_FIRST_FIT
MALLOC_STRATEGY_NEXT_FIT
MALLOC_STRATEGY_BEST_FIT
MALLOC_STRATEGY_WORST_FIT.
Privatni rozhrani alokatoru by melo byt navrzeno tak, aby umoznovalo snadne
rozsirovani o dalsi alokacni strategie.
Navrhnete a implementujte take vhodny vicevlaknovy test/benchmark, ktery
bude implementovane alokacni strategie testovat a merit dobu provadeni
ruznych operaci, pametovy overhead a fragmentaci. V dokumentaci potom
uvedte porovnani jednotlivych strategii.
Verejne rozhrani alokatoru odpovida 1. semestralni praci:
* void *malloc(const size_t size)
Funkce alokuje blok pameti pozadovane velikosti z heapu. Vraci NULL
pokud nebylo mozne blok alokovat, jinak ukazatel na zacatek alokovaneho
bloku.
* void free(const void *ptr)
Funkce uvolni blok pameti, na ktery ukazuje ptr a ktery byl predtim
naalokovan funkci malloc().
--
Posledni modifikace: 2012/10/07 20:00
-------------- next part --------------
Zadani 3. semestralni prace: -------------------------------------------------
Cilem 3. semestralni prace je rozsirit jadro z 2. semestralni prace
o podporu behu uzivatelskych procesu. Bude nutne vytvorit infrastrukturu
pro vytvareni a beh uzivatelskych procesu a pro systemova volani, ktera
budou zpristupnovat relevantni funkce jadra uzivatelskym procesum. Cast
teto infrastruktury bude nutne implementovat v uzivatelskem rezimu, kde je
potreba procesum poskytnout zakladni prostredi pro beh.
Zadani ma formu rozhrani, ktere je nutno naimplementovat. Toto rozhrani je
urceno pro uzivatelske procesy, na rozhrani infrastruktury v jadre nejsou
kladeny formalni pozadavky s vyjimkou obecnych pozadavku na uroven kodu
a systematicnost. Implementace rozhrani musi projit sadou testu, ktere
overi jeji zakladni funkcnost.
Konkretni podoba systemovych volani nutnych pro realizace uvedeneho rozhrani
neni soucasti zadani. Navrhnete tedy systemova volani dle vlastniho uvazeni
a dukladne je zdokumentujte.
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.
Zakladni zadani ------------------------------------------------------------
Rozhrani systemovych volani
---------------------------
Naimplementujte obecny mechanismus systemovych volani z uzivatelskeho
prostoru do kernelu, ktery umozni volat na strane uzivatelskeho prostoru
konkretni sluzby kernelu a predavat jim argumenty a na strane kernelu
psat obsluzne rutiny techto sluzeb.
Pri implementaci je kladen duraz na rozumnou rozsiritelnost o nove
sluzby a jejich obsluzne rutiny a dostatecne oddeleni abstrakce
(uzivatelske funkce nebudou predstavovat primo systemova volani, ale
jen jejich wrappery, kernelove obsluzne rutiny nebudou primo soucasti
obsluzne rutiny vyjimky, ale budou take oddeleny vhodnou strukturou).
Respektujte pravidlo, ze systemova volani by se mela pouzivat jen na ty
sluzby, ktere nelze snadno implementovat primo v uzivatelskem prostoru.
Kernel nelze chapat jako "sdilenou knihovnu", kterou pouzivaji uzivatelske
procesy pro delegaci beznych funkci, ktere lze plne implementovat
v uzivatelskem prostoru.
Kernelove obsluzne rutiny systemovych volani musi dusledne testovat
spravnost a konzistenci argumentu predanych z uzivatelskeho prostoru (zda
napriklad ukazatele ukazuji na korektne namapovanou pamet uzivatelskeho
procesu a tudiz pri praci s uzivatelskou pameti v kernelu nemuze vzniknout
vyjimka apod.). Na nespravne nebo nekonzistentni argumenty by mel kernel
reagovat chybovou navratovou hodnotou nebo ukoncenim procesu, nikoliv
zastavenim behu celeho systemu.
Podpora uzivatelskeho procesu
-----------------------------
Po uspesne inicializaci jadra dojde ke spusteni jedineho uzivatelskeho
procesu, jehoz binarni obraz bude nahran spolecne s kernelem a dalsimi
potrebnymi daty primo do pameti simulatoru.
Tento uzivatelsky proces bude vyuzivat behovou infrastrukturu
prostrednictvim staticky linkovane knihovny. Vytvorte ukazkovy
uzivatelsky proces, ktery bude ve vice uzivatelskych vlaknech
demonstrovat vystup na konzoli a synchronizaci.
Zakladni vstupne/vystupni operace
---------------------------------
* size_t putc(const char chr)
Funkce vypise znak na konzoli. Vraci pocet vypsanych znaku.
* size_t puts(const char *str)
Funkce vypise retezec na konzoli. Vraci pocet vypsanych znaku.
* size_t printf(const char *format, ...)
Funkce vypise formatovany retezec na konzoli, stejne jako v knihovne
libc. Formatovaci kody by mely podporovat znaky (%c), retezce (%s),
cela cisla v desitkove (%d, %u, %i) a v sestnactkove (%x) soustave,
ukazatele (%p). Neni nutne implementovat modifikatory pro zarovnavani
a platne cislice. Funkce vraci pocet vypsanych znaku.
* char getc(void)
Funkce precte a vrati znak z klavesnice. Pokud neni ve vyrovnavaci
pameti klavesnice zadny znak, zablokuje volajici vlakno a ceka na
stisk klavesy. Cekani na znak by melo byt pasivni, aktivni polling
je velmi nevhodne reseni.
* ssize_t gets(char *str, const size_t len)
Funkce precte nejvice len - 1 znaku z klavesnice do bufferu str. Cteni
je ukonceno pri precteni (a ulozeni) znaku '\n' nebo pri dosazeni
limitu. Prectene znaky jsou vzdy ukonceny znakem 0. Vraci EINVAL pokud
len == 0, jinak pocet znaku ulozenych do bufferu bez ukoncovaci 0.
Cekani na jednotlive znaky by opet melo byt reseno pasivne.
Poznamka: Za velmi nevhodnou se z implementacniho hlediska povazuje
realizace vsech vyse uvedenych funkci (predevsim printf() a gets()) primo
jako systemova volani (viz uvodni kapitola). Naopak implementovat funkce
putc(), puts() a getc() jako systemova volani je zrejme v poradku.
Zakladni ladici prostredky
--------------------------
* makro assert(EXPR)
Pokud neni definovano makro NDEBUG, makro assert() vyhodnoti vyraz EXPR
a pokud je vysledek nulovy, vypise informaci o nazvu funkce, souboru a
cisle radku, na kterem nebyl splnen predpoklad EXPR, a zavola exit().
Pokud je makro NDEBUG definovano, neudela makro assert() nic.
* makro dprintf(ARGS...)
Pokud neni definovano makro NDEBUG, makro dprintf() vypise na konzoli
informaci o nazvu funkce a cislo radku, na kterem bylo pouzito, a
formatovany retezec ARGS. Pokud je makro NDEBUG definovano, neudela makro
dprintf() nic.
Dynamicky alokovana pamet
-------------------------
Nasledujici funkce umoznuji uzivatelskemu procesu dynamicky alokovat a
uvolnovat pamet. Spravce uzivatelske pameti typicky pracuje s jednou
oblasti virtualni pameti, jejiz velikost je dana pametovymi naroky
procesu. Velikost teto oblasti by nemela byt fixni po celou dobu behu
procesu, ale v pripade potreby a dostatku fyzicke pameti by mela rust a
naopak v pripade, ze jsou na jejim konci nevyuzite stranky, by se mela
zmensovat.
Implementace samotneho algoritmu alokatoru uzivatelske pameti muze byt
velmi jednoducha, muzete napr. prevzit a upravit puvodni alokator
z Kalista. Je vsak nutne, aby alokator haldy v uzivatelskem procesu
a alokator kernelove haldy byly na sobe nezavisle.
* void *malloc(const size_t size)
Funkce alokuje blok pameti pozadovane velikosti. Vraci NULL pokud
nebylo mozne blok alokovat, jinak ukazatel na zacatek alokovaneho
bloku.
* void free(const void *ptr)
Funkce uvolni blok pameti, na ktery ukazuje ptr a ktery byl predtim
naalokovan funkci malloc().
Poznamka: Za velmi nevhodnou se z implementacniho hlediska povazuje
realizace vyse uvedenych funkci malloc() a free() jako systemova volani
(viz uvodni kapitola).
Rozhrani pro praci s vlakny
---------------------------
Rozhrani pro praci s vlakny vychazi ze specifikace POSIX, je vsak misty
velmi zjednodusene a obsahuje nektere funkce, ktere puvodni POSIX
specifikace neobsahuje.
* int thread_create(
thread_t *thread_ptr, void *(*thread_start)(void *), void *data)
Funkce vytvori nove (attached) vlakno. Vraci chybovy kod, pokud se
vlakno nepodari vytvorit, jinak EOK. Funkce @thread_start bude spustena
v nove vytvorenem vlakne. Pocet vlaken v systemu je omezen pouze
dostupnou pameti. Je-li @thread_ptr platny ukazatel, zapise do nej
identifikaci noveho vlakna.
* thread_t thread_self(void)
Funkce vrati identifikator prave beziciho vlakna.
* int thread_join(thread_t thr, void **thread_retval)
* int thread_join_timeout(
thread_t thr, void **thread_retval, const unsigned int usec)
Funkce zablokuje volajici vlakno dokud vlakno @thread neskonci. Pokud
je @thread_retval platny ukazatel, zapise ukazatel na navratovou
hodnotu vlakna na misto odkazovane @thread_retval. Vraci EINVAL pokud
je identifikace vlakna neplatna, pokud bylo vlakno odpojeno pomoci
thread_detach(), pokud jiz na vlakno ceka nekdo jiny, nebo pokud
vlakno vola funkci samo na sebe.
Varianta _timeout ceka (pasivne) na ukonceni vlakna nejdele usec
mikrosekund, pokud vlakno neni ukonceno do uplynuti teto doby, vraci
ETIMEDOUT.
* int thread_detach(thread_t thr)
Funkce odpoji zadane vlakno. Vraci EINVAL pokud je identifikace
vlakna neplatna, vlakno je jiz odpojene, vlakno jiz nebezi a ceka
na join nebo pokud na vlakno jiz nekdo ceka v thread_join().
Odpojene (detached) vlakno se od pripojeneho (attached) vlakna lisi
tim, ze neni mozne cekat na jeho ukonceni. Pri dobehnuti odpojeneho
vlakna je automaticky uvolnena pamet alokovana pro vlakno.
* int thread_cancel(thread_t thr)
Funkce zrusi zadane (bezici) vlakno. Vlakno, ktere ceka na ukonceni
ruseneho vlakna, je odblokovano (navratova hodnota je nastavena na
NULL). Funkce vraci EINVAL pokud je identifikace vlakna neplatna, jinak
EOK.
* void thread_sleep(const unsigned int sec)
* void thread_usleep(const unsigned int usec)
Funkce zablokuje prave bezici vlakno na zadanou dobu v sekundach
(resp. mikrosekundach). Vlakno nesmi byt zablokovano na kratsi dobu
nez bylo zadano, rozumne zduvodnene prodlouzeni teto doby lze
tolerovat. Cekani na vyprseni doby by melo byt realizovano pasivne,
aktivni polling neni pripustny.
Poznamka: V pripade varianty thread_sleep() je nutne zajistit spravne
fungovani pro cely rozsah typu "unsigned int" bez nebezpeci preteceni.
Cekani lze tedy realizovat opakovanym volanim thread_usleep().
* void thread_yield(void)
Vlakno volajici thread_yield() se vzda rizeni dokud nebude znovu
naplanovano k behu.
* void thread_suspend(void)
Vlakno volajici thread_suspend() se zablokuje, dokud jej jine
vlakno neodblokuje pomoci funkce thread_wakeup().
* int thread_wakeup(thread_t thr)
Funkce odblokuje zadane vlakno. Volajici vlakno pokracuje v behu,
neni v dusledku tohoto volani preplanovano. Funkce vraci EINVAL
pokud je identifikace vlakna neplatna, jinak EOK.
* void thread_exit(void *thread_retval)
Funkce ukonci provadeni volajiciho vlakna a zajisti zpristupneni
ukazatele @thread_retval vlaknu volajicimu thread_join na ukoncene
vlakno.
* void exit(void)
Funkce ukonci provadeni vsech vlaken aktualniho procesu, tedy
efektivne ukonci cely proces. Pri ukoncovani nesmi dojit k deadlocku.
Veskere prostedky procesu jsou uvolneny. Pokud v jadre jiz nebezi
zadny uzivatelsky proces, ukonci se beh celeho jadra.
Poznamka: Datovy typ vlakna v uzivatelskem prostoru by v zadnem pripade
nemel predstavovat primo strukturu, kterou pouziva kernel. Uzivatelsky
proces by nemel mit moznost zadnym nestandardnim zpusobem zasahnout do
kernelove implementace planovani vlaken nebo pomoci podvrzene kernelove
struktury jinym zpusobem zmenit chovani systemu.
Uzivatelsky datovy typ vlakna by mel predstavovat identifikator vlakna,
jehoz planost muze kernel jednoznacne overit.
Synchronizacni primitiva
------------------------
Stejne jako rozhrani pro vlakna vychazi rovnez rozhrani pro praci se
synchronizacnimi primitivy ze specifikace POSIX, je vsak zjednodusene
a v navaznosti na predchozi semestralni prace pouziva odlisne nazvy
funkci a jine typy pro synchronizacni primitiva.
- mutex (zamek, binarni semafor)
* int mutex_init(struct mutex *mtx)
Funkce inicializuje mutex do stavu odemceno. Pokud inicializace
probehne v poradku, vraci EOK, v opacnem pripade ENOMEM/EINVAL podle
charakteru chyby.
* int mutex_destroy(struct mutex *mtx)
Funkce provede uklid ridici struktury mutexu. Pokud je rusen mutex,
na kterem jsou jeste zablokovana nejaka vlakna, ukonci se aktualni
vlakno. Pokud je identifikator mutexu neplatny, funkce vraci EINVAL.
Probehne-li operace v poradku, funkce vraci EOK.
* int mutex_lock(struct mutex *mtx)
* int mutex_lock_timeout (struct mutex *mtx, const unsigned int usec)
Funkce se pokusi zamknout mutex, pokud to neni mozne, zablokuje
vlakno na mutexu.
Varianta _timeout ceka na zamknuti mutexu nejdele usec mikrosekund.
Pokud se behem teto doby podari mutex zamknout, vraci EOK, jinak
ETIMEDOUT. Pokud je casovy limit 0, k zablokovani vlakna nedochazi.
Pokud je identifikator mutexu neplatny, funkce vraci EINVAL.
* int mutex_unlock(struct mutex *mtx)
Funkce odemkne zadany mutex a vzbudi vlakna, ktera byla zablokovana
pri zamykani mutexu. Pokud je symbol DEBUG_MUTEX >= 1, bude
implementace mutexu hlidat, zda je odemykan vlaknem, ktere ho puvodne
zamknulo. Pokud bude mutex odemykat jine vlakno, ukonci se aktualni
vlakno. Pokud je identifikator mutexu neplatny, funkce vraci EINVAL.
Probehne-li operace v poradku, funkce vraci EOK.
Poznamka: Datovy typ mutexu v uzivatelskem prostoru by v zadnem pripade
nemel predstavovat primo strukturu, kterou pouziva kernel. Uzivatelsky
proces by nemel mit moznost zadnym nestandardnim zpusobem zasahnout do
kernelove implementace synchronizace nebo pomoci podvrzene kernelove
struktury jinym zpusobem zmenit chovani systemu.
Uzivatelsky datovy typ mutexu muze obsahovat identifikator kerneloveho
mutexu, jehoz planost muze kernel jednoznacne overit. Dalsi moznosti
je implementovat mutex ciste v uzivatelskem prostoru za pouziti jinych
primitivnich operaci.
Integrace s testy
-----------------
K integraci s testy vytvorite hlavickovy soubor librt.h, ktery bude typicky
obsahovat #include direktivy, ktere zajisti vlozeni vasich hlavickovych
souboru knihovny behove podpory s prislusnymi deklaracemi. Test bude dodan
jako zdrojovy kod uzivatelskeho procesu.
Dale je nutne pripravit knihovnu behove podpory librt.a, ktera bude obsahovat
kod behoveho prostredi procesu. S touto knihovnou bude slinkovan kod kazdeho
uzivatelskeho procesu.
Start uzivatelskeho procesu vypada tak, ze jadro zacne provadet kod procesu
od urcite adresy, kde bude typicky vstupni bod behoveho prostredi z knihovny
librt.a, ktery provede nezbytnou inicializaci (alokatoru pameti atd.) a
zavola funkci main() uzivatelskeho procesu. Pri navratu z funkce main() pak
behove prostredi ukonci proces (tj. vsechna jeho bezici vlakna).
Rozsirene zadani -----------------------------------------------------------
Diskove zarizeni
----------------
Implementujte v ramci jadra read-only ovladac diskoveho blokoveho zarizeni
(s pouzitim zarizeni ddisk v MSIMu). Moznost cteni bloku dat bude vhodnym
rozhranim zpristupneno uzivatelskym procesum.
Rozhrani pro praci s procesy
----------------------------
Implementujte jednoduche rozhrani v uzivatelskem prostoru, ktere umozni
pracovat s uzivatelskymi procesy, jez pobezi v oddelenych adresovych
prostorech.
* int process_create(
process_t *process_ptr, const void *img, const size_t size)
Funkce vytvori novy uzivatelsky proces s nezavislym adresovym
prostorem, jehoz binarni obraz velikosti @size bajtu bude nacten
z adresoveho prostoru aktualniho procesu z adresy @img.
Vraci chybovy kod, pokud se proces nepodari vytvorit, jinak EOK.
Je-li @process_ptr platny ukazatel, zapise do nej identifikaci noveho
procesu.
* process_t process_self(void)
Funkce vrati identifikator prave beziciho procesu.
* int process_join(process_t proc)
* int process_join(process_t proc, const unsigned int usec)
Funkce zablokuje volajici vlakno, dokud proces @proc neskonci. Vraci
EINVAL pokud je identifikace procesu neplatna, pokud jiz na proces
ceka nekdo jiny, nebo pokud vlakno vola funkci na svuj vlastni proces.
Varianta _timeout ceka (pasivne) na ukonceni procesu nejdele usec
mikrosekund, pokud proces neni ukoncen do uplynuti teto doby, vraci
ETIMEDOUT.
* int kill(process_t proc)
Funkce zrusi zadany (bezici) proces. Vlakno, ktere ceka na ukonceni
ruseneho procesu, je odblokovano. Funkce vraci EINVAL pokud je
identifikace procesu neplatna, jinak EOK.
Poznamka: Datovy typ procesu v uzivatelskem prostoru by v zadnem pripade
nemel predstavovat primo strukturu, kterou pouziva kernel. Uzivatelsky
proces by nemel mit moznost zadnym nestandardnim zpusobem zasahnout do
kernelove implementace planovani vlaken nebo pomoci podvrzene kernelove
struktury jinym zpusobem zmenit chovani systemu.
Uzivatelsky datovy typ procesu by mel predstavovat identifikator procesu,
jehoz planost muze kernel jednoznacne overit.
Spousteni uzivatelskych procesu
-------------------------------
V ramci zakladniho uzivatelskeho procesu (ktery bude spusten jadrem
z fyzicke pameti) umoznete cist a spoustet z blokoveho zarizeni dalsi
uzivatelske procesy.
Na blokovem zarizeni (disku) neni nutne implementovat zadny souborovy
system, postaci na nej linearne nahrat obsah binarnich obrazu jednotlivych
procesu, ktere se maji spustit, a vhodnou datovou strukturou ulozenou na
disku tyto procesy identifikovat.
--
Posledni modifikace: 2012/10/07 20:30
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tests-as1.tar.bz2
Type: application/x-bzip
Size: 6442 bytes
Desc: not available
URL: <http://d3s.mff.cuni.cz/pipermail/nswi004/attachments/20121007/38b39a3e/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tests-as1e.tar.bz2
Type: application/x-bzip
Size: 8440 bytes
Desc: not available
URL: <http://d3s.mff.cuni.cz/pipermail/nswi004/attachments/20121007/38b39a3e/attachment-0001.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tests-as2.tar.bz2
Type: application/x-bzip
Size: 20925 bytes
Desc: not available
URL: <http://d3s.mff.cuni.cz/pipermail/nswi004/attachments/20121007/38b39a3e/attachment-0002.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tests-as2e.tar.bz2
Type: application/x-bzip
Size: 17827 bytes
Desc: not available
URL: <http://d3s.mff.cuni.cz/pipermail/nswi004/attachments/20121007/38b39a3e/attachment-0003.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tests-as3.tar.bz2
Type: application/x-bzip
Size: 11743 bytes
Desc: not available
URL: <http://d3s.mff.cuni.cz/pipermail/nswi004/attachments/20121007/38b39a3e/attachment-0004.bin>
More information about the NSWI004
mailing list