[OSy] Zadani 1. tematu semestralni ulohy
Martin Decky
decky at d3s.mff.cuni.cz
Thu Oct 15 09:27:24 CEST 2015
Vazeni kolegove,
v priloze tohoto emailu naleznete rozsirene zadani 1. semestralni ulohy
z predmetu Operacni systemy. Prosim, venujte tomuto zadani pozornost i v
pripade, ze mate v planu prijit na nejblizsi cviceni a resit prezencni
ulohu -- zadani 1. prezencni ulohy se bude take tykat tematu
synchronizace a bude vyzadovat znalost latky z prednasky (pripadne z
doporucene literatury, ktera je uvedena na konci rozsireneho zadani).
Pokud se rozhodnete implementovat rozsirene zadani, tak sva reseni
muzete odevzdavat az do 29. 10. 2015 (vcetne). Odevzdani provadejte tak,
ze svou modifikaci Kalista (tj. vse, co je potreba ke spusteni,
otestovani a ohodnoceni Vaseho reseni) zabalite do archivu (ZIP, TAR.BZ2
apod.) a poslete jako prilohu na emailovou adresu
nswi004 at d3s.mff.cuni.cz
Budeme se snazit Vase reseni kontrolovat prubezne, ale bohuzel nemuzeme
reakcni dobu garantovat, proto prosim ve vlastnim zajmu nenechavejte
odevzdavani na posledni chvili. Take prosim, abyste se nesnazili o
"iterativni" odevzdavani ve stylu "zkousim to tolikrat, az to nakonec
projde", ale na druhou stranu, pokud Vasemu prvnimu reseni budeme moci
vytknout jen drobnosti, tak budete mit sanci nedostatky opravit a zkusit
odevzdat vylepsene reseni.
V pripade libovolnych dotazu k zadani nebo k formalnim zalezitostem
nevahejte vyuzit tento mailing list.
S pozdravem
Martin Decky
-------------- next part --------------
========================================================================
Semestralni uloha z predmetu
Operacni systemy
Tema 1.: Synchronizace
Rozsirene zadani
========================================================================
Datum zverejneni zadani: 15. 10. 2015
Datum odevzdani reseni: 29. 10. 2015
------------------------------------------------------------------------
Cilem 1. tematu semestralni ulohy je naprogramovat pasivni
synchronizacni primitivum. Zadani ma formu rozhrani, ktere je nutno
naimplementovat, a je doplneno sadou jednotkovych testu, jimiz musi
implementace uspesne projit.
Pri vypracovani vychazejte z vyukoveho jadra Kalisto ve verze 0.9.2,
do ktereho doplnte chybejici funkcionalitu. Kalisto ve verzi 0.9.2 je
k dispozici ke stazeni z URL:
http://d3s.mff.cuni.cz/osy/download/kalisto-0.9.2.tar.bz2
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 pomoci vhodnych
komentaru ve zdrojovem kodu reseni.
Poznamky k rozhranim ---------------------------------------------------
V zadani vsech semestralnich uloh 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.
* 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, ve velmi
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, 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 -------------------------------------------------------
Nasledujici doporuceni odrazi pozadavky na uroven zdrojovych textu,
ktere budou hodnoceny pri odevzdani reseni ulohy.
- 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.
Zadani ulohy -----------------------------------------------------------
V ramci jadra operacniho systemu Kalisto 0.9.2 naimplementujte
semafory jako standardni pasivni synchronizacni primitivum. Vase
implementace semaforu musi nabizet nize uvedene funkce jako verejne
rozhrani.
Semafory budou pouzivany nasledujicim zpusobem:
struct semaphore sem;
sem_init(&sem, 100);
...
sem_destroy(&sem);
Pri implementaci predpokladejte, ze kod muze byt kdykoliv prerusen,
pokud nejsou zakazana preruseni. Postacuje, pokud budou veskere
operace korektne synchronizovany a odladeny na systemu vybavenem
jedinym procesorem.
* void sem_init(struct semaphore *sem, const int value)
Funkce inicializuje semafor a nastavi ho na zadanou hodnotu.
* void sem_init_limit(struct semaphore *sem, const int value,
const int limit)
Funkce inicializuje semafor a nastavi ho na zadanou hodnotu. Krome
toho funkce nastavi, ze hodnota semaforu nebude nikdy vyssi nez
uvedeny limit.
Nastaveni vychozi hodnoty semaforu na 1 a limitu take na hodnotu 1
umoznuje pomoci semaforu implementovat takzvany binarni semafor (tez
znamy jako nerekurzivni mutex nebo jednoduse jako zamek).
* void sem_destroy(struct semaphore *sem)
Funkce provede uklid ridici struktury semaforu. Pokud je rusen
semafor, na kterem jsou jeste zablokovana nejaka vlakna, 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. Pokud je vysledna hodnota semaforu
vyssi nez nastaveny limit semaforu, tak se vysledna hodnota nastavi
rovna limitu.
* void sem_down(struct semaphore *sem)
Funkce dekrementuje hodnotu semaforu, pokud je to mozne, jinak
vlakno na semaforu zablokuje.
Pomocne rutiny ---------------------------------------------------------
Pro spravnou implementaci semaforu je vhodne vyuzit a pripadne
rozsirit implementaci dalsich funkci v jadre systemu Kalisto.
Nasleduje popis techto funkci a jejich chovani.
* 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_yield(void)
Vlakno volajici thread_yield() se vzda rizeni, dokud nebude znovu
naplanovano k behu.
Jednotkove testy -------------------------------------------------------
K overeni spravne funkcnosti implementace slouzi testy ulozene
v podstrome kernel/tests/sem zdrojoveho stromu Kalista 0.9.2.
Infrastruktura pro spousteni a vyhodnoceni techto jednotkovych testu
je implementovana pomoci skriptu tests-sem.sh. Pro splneni zadani je
potreba, aby reseni uspesne proslo vsemi dodanymi jednotkovymi testy,
pricemz neni dovoleno modifikovat logiku testu.
K integraci s jednotkovymi testy pridejte do hlavickoveho souboru
api.h vhodne #include direktivy, ktere zajisti vlozeni hlavickovych
souboru s potrebnymi deklaracemi.
Doporucena literatura --------------------------------------------------
[1] Studijni text k predmetu Operacni systemy, kapitola Process
Synchronization, http://d3s.mff.cuni.cz/~ceres/sch/osy/text/
[2] Wikipedia: Semaphore (programming),
https://en.wikipedia.org/wiki/Semaphore_(programming)
[3] Wikipedia: Load-link/store-conditional,
https://en.wikipedia.org/wiki/Load-link/store-conditional
[4] Downey A. B.: The Little Book of Semaphores,
http://greenteapress.com/semaphores/
More information about the NSWI004
mailing list