[OSy] Zadani 3. semestralky
Martin Decky
decky at dsrg.mff.cuni.cz
Sun Oct 21 15:35:25 CEST 2007
Hezky den,
na konci tohoto emailu se nachazi zadani 3. semestralni prace. Zakladni
instrukce k vypracovani jsou shodne se zadanim predchozich semestralnich praci.
Testy pro 1. semestralni praci obdrzite v prubehu nasledujiciho tydne
(omlouvame se za zpozdeni), testy 3. semestralni obdrzite priblizne 3 tydny
pred datem odevzdani zakladniho zadani.
Pomoci testu budeme kontrolovat spravnost Vaseho reseni v ramci zakladniho
zadani (a budou take slouzit jako pomocne kriterium pri hodnoceni rozsireneho
zadani).
Na zaver pripominam nekolik dulezitych informaci:
* Odevzdani zakladniho zadani 3. semestralky probehne 6. 1. 2008. Zcela presne
budeme testovat, zda projde testy zakladniho zadani revize s casovym
razitkem 5. 1. 2008 00:00 CET.
* Pokud Vase reseni neprojde testy nebo o to explicitne pozadate, pobezi Vam
od 13. 1. 2008 lhuta 7 dnu na opozdene odevzdani s penalizaci 1/10
z maximalniho mozneho poctu bodu. Pri odevzdani pozdeji nez 12. 1. 2008
jiz nebudete moci ziskat zapocet.
Hodne stesti!
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.
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.
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 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 v uzivatelskem prostoru.
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
---------------------------------
* 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
vsech 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 uzivatelske pameti typicky pracuje s jednou
oblasti virtualni pameti, jejiz velikost je dana pametovymi naroky
procesu.
Implementace alokatoru uzivatelske pameti muze byt velmi jednoducha, ale
rozhodnete-li se napr. prevzit puvodni alokator z Kalista, musite jej
zdokumentovat a jeho kod upravit tak, aby odpovidal pozadavkum kladenym
na uroven zdrojovych kodu.
* 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. 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 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.
* 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.
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 (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.
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 nezbytnou
inicializaci (spravce pameti, popr. jine) a zavola main() funkci
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 ovladac read-only diskoveho blokoveho zarizeni
(s pouzitim zarizeni ddisk). Cteni bloku bude vhodnym rozhranim
zpristupneno uzivatelskemu prostoru.
Ovladac blokoveho zarizeni bude implementovat nekolik strategii pro
optimalizaci pristupu k blokum, mezi kterymi bude mozne prepinat v dobe
prekladu (nastavenim vhodneho makra). Navrhnete privatni rozhrani
ovladace tak, aby bylo snadne rozsirovat jej o dalsi optimalizacni
strategie.
Implementujte v kodu nejmene tyto optimalizacni strategie:
* FIFO
* Shortest Seek First
* Bidirectional Elevator
* Unidirectional Sweep
Navrhnete vhodny vicevlaknovy test v uzivatelskem prostoru, ktery bude
implementovane optimalizacni strategie testovat a merit dobu provadenych
operaci cteni. V dokumentaci potom uvedte porovnani jednotlivych
strategii.
Rozhrani pro praci s procesy
----------------------------
Zjednodusene 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 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 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.
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 (s pripadnymi pomocnymi oddelovacimi
strukturami).
More information about the NSWI004
mailing list