[OSy] Zadani 1. semestralky
Martin Decky
decky at dsrg.mff.cuni.cz
Mon Oct 8 01:00:45 CEST 2007
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 zde nebo pozdeji v ramci konzultacniho cviceni, ktere
podle zajmu usporadame (ovsem na dotazy typu "Jak se na MIPSu zmeni hodnota
v registru R0?" cekejte spise velmi strucnou odpoved typu RTFM ..).
Priblizne 3 tydny pred datem odevzdani zakladniho zadani Vam posleme testy,
pomoci nichz budeme testovat spravnost Vaseho reseni v ramci zakladniho zadani
(a budou take slouzit jako pomocne kriterium pri hodnoceni rozsireneho zadani).
Na zaver pripominam nekolik dulezitych informaci:
* 8. a 10. 10. probehne cviceni zamerene na seznameni s procesorem MIPS,
simulatorem MSIM apod.
* Nejpozdeji do 14. 10. nahlaste slozeni svych skupin a preference zadani.
Bezprostredne pote Vam oznamime rozsirene zadani, na kterem budete pracovat,
a pristupove udaje k Vasemu SVN repository.
* Odevzdani zakladniho zadani 1. semestralky probehne 4. 11. Zcela presne
budeme testovat, zda projde testy zakladniho zadani revize s casovym
razitkem 5. 11. 2007 00:00 CET.
* Pokud Vase reseni neprojde testy nebo o to explicitne pozadate, pobezi Vam
od 5. 11. lhuta 7 dnu na opozdene odevzdani s penalizaci 1/10 z maximalniho
mozneho poctu bodu. Pri odevzdani pozdeji nez 11. 11. jiz nebudete moci
ziskat zapocet.
Hodne stesti!
M.D.
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
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 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
(tj. zakazani preruseni staci k zajisteni atomicity operaci).
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,
unsigned int flags)
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.
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.
* 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.
- 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 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.
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 korektne synchronizovany
a odladeny na konfiguraci s vice procesory, zakazani preruseni na jednom
procesoru tedy obecne nemusi zajistit atomicitu provadenych operaci.
Implementace nesmi byt omezena nejakym konkretnim poctem nakonfigurovanych
procesoru. 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
---------------------------------
* unsigned int 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 deadlockum
pri pouziti 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
-------------------
* jednoduche vyvazovani zateze jednotlivych procesoru tak, ze na kazdy
procesor bude strategii round-robin planovan priblizne stejny pocet
bezicich vlaken
* planovac se bude snazit nepresouvat vlakna mezi ruznymi procesory,
nebude-li to nezbytne nutne
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 zakazanovani
preruseni na aktualnim procesoru, coz opet snizi dobu vykonavani kriticke
sekce.
- 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 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 (vedle
standardni datove struktury seznam, kterou zrejme pouzijete jiz
v zakladnim zadani) take specialni druh seznamu, ktery bude implementovat
bezne operace tak, aby zachovaly konzistenci datove struktury i na
viceprocesorovem systemu a zaroven nevyzadovaly pouziti synchronizacnich
primitiv.
Navrhnete a implementujte take vhodny vicevlaknovy test, ktery bude obe
varianty implementace seznamu (standardni se synchronizaci a neblokujici)
testovat a merit dobu provadeni jednotlivych operaci. V dokumentaci potom
uvedte porovnani obou implementaci.
More information about the NSWI004
mailing list