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, ktere overuji jeji funkcnost. 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. Neni tedy nutne uvazovat viceprocesorove konfigurace simulatoru (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. * 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. * 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 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, 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. 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 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. 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, 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 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. * 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. 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. - 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. Integrace s testy ----------------- K integraci s testy vytvorite hlavickovy soubor api.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 extern funkce run_test(void), kterou zavolate z vaseho jadra. Rozsirene zadani ----------------------------------------------------------- Rozsirene zadani vychazi ze zakladniho zadani, musi tedy implementovat vsechny funkce pozadovaneho 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. Vhodne, aby se jiz behem implenetace 2. a 3. zakladniho zadani pouzivaly korektne synchronizacni primitiva a dalsi postupy pro spravny pristup ke sdilenym datum s vyhledem pro pouziti s vice procesory, byt danem v okamziku jeste nemusi byt tyto casti kodu odladeny na viceprocesorovych konfiguracich. Implementace nesmi byt omezena nejakym konstantnim poctem nakonfigurovanych procesoru (vyjma omezeni vyplyvajici primo z vlastnosti simulatoru, resp. MIPSu). Je vhodne, aby zakladni inicializace jadra probihala na jedinem procesoru (tzv. bootstrap processor), zatimco ostatni procesory (tzv. application processors) byly pouzity az pro planovani 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. 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 v systemu. Jednoduchy planovac ------------------- * kazdy procesor bude strategii round-robin nezavisle planovat vlakna * priblizne rovnomerneho vyuziti vsech procesoru se bude dosahovat pouze statickym rozmistovanim vlaken na procesory ve funkci thread_create(), neni nutne implementovat dynamicky load ballancing Synchronizacni primitiva ------------------------ Pasivni synchronizacni primitiva implementujte pokud mozno s malou latenci, tedy vyuzitim kritickych sekci ochranenych aktivnim synchronizacnim primitivem (spinlockem). Je take typicky 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 (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) * 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 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); - 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 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 klasicke implementaci 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 s SC. Navrhnete a implementujte take vhodny vicevlaknovy test a 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: 2010/10/10 19:40