[OSy] Zadani 1. semestralky
Martin Decky
decky at nenya.ms.mff.cuni.cz
Sun Oct 15 11:25:32 CEST 2006
Zdravim vsechny,
na konci tohoto emailu se nachazi zadani 1. semestralni prace. Pokud je Vam
neco nejasneho, pouzijte tuto konferenci k polozeni dotazu, pokusime se
v kratkem case odpovedet (ovsem na dotazy typu "Jak se na MIPSu zmeni hodnota
v registru R0?" cekejte spise odpoved svych kolegu nez nasi ..).
Priblizne za tyden Vam posleme testy, pomoci nichz budeme castecne testovat
spravnost Vaseho reseni. Rozhodli jsme se take usporadat cviceni 23. a 26. 10.
jako "hromadnou konzultaci" (ucast je pochopitelne nepovinna), kde bychom
osobne vysvetlili pripadne nejasnosti.
Vzhledem k tomu, kolik skupin se prihlasilo na prvni zadani, jsme bohuzel
nuceni prezentace rozdelit rovnomerne mezi cviceni 6. a 9. 11. (konkretne tak,
ze 3 skupiny z pondeli budou prezentovat ve ctvrtek). Prezentace budou i tak
muset byt velmi kratke a strucne, takze bude stacit, kdyz za kazdou skupinu
bude prezentovat jen jeden clovek. Budeme radi, pokud uz nyni budou pondelni
skupiny uvazovat, kdo z nich by mohl pripadne prezentovat ve ctvrtek.
Na zaver pripominam, ze zavazne datum odevzdani je patek 10. 11. (na presnem
harmonogramu se jeste domluvime). Odevzdavat pozdeji (nejvyse vsak o 1 tyden)
je mozne, ale v takovem pripade muze skupina zistak maximalne 2/3 plneho poctu
bodu.
Hodne stesti!
M.D.
Zadani 1. semestralni prace: -------------------------------------------------
Cilem 1. semestralni prace je naprogramovat zaklad jadra operacniho
systemu, ktery bude pouzit pro navazujici semestralni prace. Zadani
ma formu rozhrani, ktere je nutno naimplementovat. K zajisteni rozumne
urovne funkcnosti pro navazujici skupiny je nutne, aby implementace
prosla sadou testu, ktere overuji jeji funkcnost.
Zakladem 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
z 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.
* definice typu
int8_t signed char
uint8_t unsigned char
int16_t signed short
uint16_t unsigned short
int32_t signed long
uint32_t unsigned long
int64_t signed long long
uint64_t unsigned long long
native_t int32_t
unative_t uint32_t
uintptr_t uint32_t
off_t uint32_t
size_t uint32_t
ssize_t int32_t
Uvedene typy odpovidaji beznym zvyklostem a architekture procesoru
a mohou byt pouzity v testech a specifikaci zadani.
* 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
- vyhybejte se vytvareni zdrojovych souboru, ktere
obsahuji nesouvisejici funkce
- 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 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 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, 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 getc_try (void)
Funkce precte a vrati znak z klavesnice. Pokud neni ve vyrovnavaci
pameti klavesnice zadny znak, vrati EWOULDBLOCK.
* 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.
Zakladni ladici prostredky
--------------------------
* makro assert(EXPR)
Pokud neni definovan symbol NDEBUG, makro 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 symbol
NDEBUG definovan, neudela nic.
* makro dprintk(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.
* void panic (const char * format, ...)
Funkce vypise formatovany retezec na konzoli (stejne jako printk),
vypise identifikator prave beziciho vlakna, obsah registru procesoru
a zablokuje jadro.
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)
Zjistit zdroj preruseni a obslouzit ho.
* address error (AdEL, AdES)
Nastava pri cteni/zapisu z/na nezarovnanou adresu a pri pristupu
do adresoveho prostoru jadra z uzivatelskeho rezimu. Panic.
* bus error (IBE, DBE)
Nastava pri pristupu na neplatnou fyzickou adresu. Panic.
* break point (BP)
Nastava pri vykonani instrukce BREAK. Ignorovat pokud neni instrukce
v branch delay slotu, jinak panic.
* reference to WatchHi/WatchLo address (WATCH)
Nastava pri pristupu do rozmezi adres definovaneho registry CP0
WatchHi a WatchLo. Ignorovat.
* reserved instruction (RI)
Nastava pri neznamem operacnim kodu instrukce, v principu neznama
instrukce -- da se pouzit k emulaci nekterych instrukci. Panic.
* coprocessor unusable (CpU)
Nastava pri pristupu na koprocesor, ktery neni neni oznacen jako
pristupny. Panic.
* trap exception (Tr)
Nastava pri provedeni podminenych instrukci Txx. Panic.
* arithmetic overflow (Ov)
Nastava pri preteceni dvojkoveho doplnku pri celociselnych operacich
(prenosy z bitu 31 a 30 se lisi). Panic.
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, rovnez inteligence
alokatoru nebude hodnocena.
* 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.
Jednoduchy planovac
-------------------
* preemptivni planovani vlaken k behu na procesoru
* strategie round-robin bez priorit
Rozhrani pro praci s vlakny
---------------------------
* 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
void thread_start (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.
* 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 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.
* 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.
* 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.
Obsluzna funkce bezi na ukor preruseneho vlakna.
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. Neni nutne uvazovat viceprocesorove
konfigurace simulatoru (tj. zakazani preruseni staci k zajisteni
atomicity operaci).
- 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.
Semafory budou pouzivany nasledujicim zpusobem:
struct semaphore sem;
sem_init (&sem, 100);
...
sem_destroy (&sem);
- 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.
- r/w 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 assignment-1.h, ktery bude
obsahovat deklarace vsech vyse uvedenych funkci. Typicky bude obsahovat
#include direktivy, ktere zajisti vlozeni vasich hlavickovych souboru s
prislusnymi deklaracemi.
Dale musi soubor obsahovat deklaraci funkce assignment_test (void),
kterou zavolate z vaseho jadra.
More information about the NSWI004
mailing list