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 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 off_t long size_t unsigned int ssize_t int uchar unsigned char ushort unsigned short uint unsigned int ulong unsigned long 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 --------------------------------- * int putc (const char chr) Funkce vypise znak na konzoli. Vraci pocet vypsanych znaku. * int puts (const char * str) Funkce vypise retezec na konzoli. Vraci pocet vypsanych znaku. * 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. * int 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, 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 (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 (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, uint 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 (uint sec) * void thread_usleep (uint 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, uint usec, void (*) (struct timer *, void *) handler, 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, 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, uint 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, uint 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, uint usec) * int rwlock_write_lock_timeout (struct rwlock * rwl, uint 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, uint 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. -- Posledni modifikace: 2005/10/17 10:21