[OSy] Zadani 3. semestralky
Martin Decky
decky at dsrg.mff.cuni.cz
Sun Dec 10 19:25:32 CET 2006
Hezky vecer,
na konci emailu posilam zadani 3. semestralni prace. Jadro, na kterem budete
po predchozich skupinach pokracovat v implementaci, zasleme jednotlive kazde
skupine. Zatim vyuzijte cas k promysleni zadani a pokud je Vam neco nejasneho,
poslete svuj dotaz do konference.
Priblizne za tyden Vam take posleme testy, pomoci nichz budeme castecne
testovat spravnost sveho reseni. Testy budou mit tentokrat formu uzivatelskeho
procesu, ktery pobezi nad Vasim jadrem.
Cviceni 18. a 21. 12. budou mit opet formu "hromadne konzultace" s nepovinnou
ucasti, kde budeme zive odpovidat na dotazy.
Pripominam, ze prezentace Vasich reseni se budou konat 8. a 11. 1. 2007 a
zavazne datum odevzdani je patek 12. 1. 2007. Odevzdavat pozdeji (nejvyse vsak
o 1 tyden) je mozne, ale v takovem pripade muze skupina ziskat maximalne 2/3
plneho poctu bodu.
Hodne stesti!
P.S.: Jak jste si mozna vsimnuli, webove a emailove adresy koncici na
nenya.ms.mff.cuni.cz se behem tohoto tydne zmenily na dsrg.mff.cuni.cz.
Preferujeme pouzivani nove domeny, ale stara pochopitelne zustava v provozu.
M.D.
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, zejmena pak spravu
uzivatelske pameti.
Zadani ma formu rozhrani, ktere je nutno naimplementovat. Toto rozhrani je
urceno pro uzivatelske procesy, na rozhrani infrastruktury v jadre nejsou
kladeny specificke pozadavky, s vyjimkou obecnych pozadavku na uroven kodu
a systematicnost. Implementace rozhrani musi projit sadou testu, ktere
overi jeji zakladni funkcnost.
Systemova volani nutna pro realizace uvedeneho rozhrani nejsou predmetem
zadani, nicmene je nutne je zdokumentovat.
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 vstupne/vystupni operace
---------------------------------
* unsigned int putc (const char chr)
Funkce vypise znak na konzoli. Vraci pocet vypsanych znaku.
* unsigned int puts (const char * str)
Funkce vypise retezec na konzoli. Vraci pocet vypsanych znaku.
* unsigned int 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) bez modifikatoru na zarovnavani a platne cislice. 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.
* int 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.
Pozn.: Za nevhodnou se z implementacniho hlediska povazuje realizace
vyse uvedenych funkci primo formou systemovych volani.
Zakladni ladici prostredky
--------------------------
* makro assert(EXPR)
Pokud neni definovan symbol NDEBUG, makro 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
symbol NDEBUG definovan, neudela nic.
* makro dprintf(ARGS...)
Pokud neni definovan symbol NDEBUG, makro vypise na konzoli informaci
o nazvu funkce a cislo radku, na kterem bylo pouzito a formatovany
retezec ARGS. Pokud je symbol NDEBUG definovan, neudela nic.
Dynamicky alokovana pamet
-------------------------
Nasledujici funkce umoznuji uzivatelskemu procesu dynamicky alokovat a
uvolnovat pamet. Spravce uzivateslke pameti typicky pracuje s jednou
oblasti virtualni pameti, jejiz velikost je dana pametovymi naroky
procesu.
* 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.
Rozhrani pro praci s vlakny
---------------------------
Rozhrani pro praci s vlakny vychazi ze specifikace POSIX, je vsak misty
velmi zjednodusene, popr. obsahuje nektere funkce, ktere puvodni POSIX
specifikace neobsahuje.
* int thread_create (
thread_t * thread_ptr, void * (* thread_start) (void *), void * arg)
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.
* 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 vlakna 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 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. 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.
* 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.
Synchronizacni primitiva
------------------------
Stejne jako rozhrani pro vlakna vychazi rozhrani pro praci se
synchronizacnimi primitivy rovnez vychazi ze specifikace POSIX, je
vsak v rade pripadu zjednodusene a v navaznosti na predchozi
semestralni prace pouziva odlisne nazvy funkci a jine typy pro
synchronizacni primitiva.
- semafor (s casovym limitem)
* 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 zablokovany nejake thready, 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)
* void 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 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.
- mutex (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 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 symbol DEBUG_MUTEX >= 1, bude
implementace mutexu hlidat, zda je odemykan vlaknem, ktere ho puvodne
zamknulo. Pokud bude mutex odemykat jine vlakno, vyvola panic.
- 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 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 zablokovany nejake thready,
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 * 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.
Integrace s testy
-----------------
K integraci s testy vytvorite hlavickovy soubor librt.h, ktery bude
obsahovat deklarace vsech vyse uvedenych funkci. Typicky bude obsahovat
#include direktivy, ktere zajisti vlozeni vasich hlavickovych souboru
s prislusnymi deklaracemi. Test bude dodan jako zdrojovy kod uzivatelskeho
procesu.
Dale je nutne pripravit knihovnu librt.a, ktera bude obsahovat kod behoveho
prostredi procesu. S touto knihovnou bude slinkovan kod procesu. Start
procesu vypada tak, ze jadro spusti proces od urcite adresy, kde bude
typicky vstupni bod behoveho prostredi, ktere provede nezbytnout
inicializaci (spravce pameti, popr. jine) a zavola main () funkci
uzivatelskeho procesu. Pri navratu z funkce main () pak behove prostredi
ukonci proces.
More information about the NSWI004
mailing list