[OSy] Zadani semestralnich praci

Vojtech Horky horky at d3s.mff.cuni.cz
Wed Oct 9 10:00:06 CEST 2013


Vazeni kolegove,

v priloze tohoto emailu naleznete zadani semestralnich praci z predmetu
Operacni systemy a prislusne testy, ktere zadani doplnuji a ktere budou
slouzit pro vyhodnocovani Vasi uspesnosti v jednotlivych fazich.

Obsah prilozenych souboru je nasledujici:

assignment-1.txt   ... zakladni a rozsirene zadani 1. semestralni prace
assignment-2.txt   ... zakladni a rozsirene zadani 2. semestralni prace
assignment-3.txt   ... zakladni a rozsirene zadani 3. semestralni prace

tests-as1.tar.bz2  ... testy pro 1. zakladni zadani
tests-as1e.tar.bz2 ... testy pro 1. rozsirene zadani

tests-as2.tar.bz2  ... testy pro 2. zakladni zadani
tests-as2e.tar.bz2 ... testy pro 2. rozsirene zadani

tests-as3.tar.bz2  ... testy pro 3. zakladni zadani

Prosim, proctete si dukladne zadani a prohlednete si testy. Pokud by Vam
bylo cokoliv nejasneho, nevahejte poslat svuj dotaz do teto konference.
Na dotazy se pokusime v kratkem case odpovedet, pripadne Vas dotaz muze
slouzit jako namet pro obsah konzultacnich cviceni, ktera muzeme v
pripade zajmu vyhlasit pozdeji v prubehu semestru.

Konference by vsak nemela slouzit jako hot-line nahrazujici nutne
samostudium. Budeme ochotne reagovat na informovane otazky, ale na
trivialni dotazy typu "Jak se na MIPSu zmeni hodnota v registru R0?",
prosim necekejte vice nez strucnou vyzvu k dukladnejsimu prostudovani
manualu procesoru.


K testum: Zakladni pokyny pro integraci testu s Vasim resenim jsou
popsany v zadani. V pripade kernelovych testu (1. a 2. zadani) byste
meli testy zaintegrovat po vzoru testu v adresari kernel/tests/basic ve
zdrojovem strome Kalista. Cilem tedy je, aby bylo mozne testy co
nejsnadneji a pokud mozno bez lidskeho zasahu spustit a vyhodnotit
(krome rucniho vyhodnoceni nekolika interaktivnich testu).

Infrastrukturu testu si muzete pochopitelne upravit tak, aby odpovidala
zpusobu prekladu a pripadne dalsim specifikum Vaseho reseni (napr. v
pripade kolize nazvu globalnich symbolu/maker). Urcite vsak neni
dovoleno modifikovat logiku testu (tedy to, co testy fakticky testuji).

Testy zakladniho zadani je nutne splnit bez vyhrad pro postup do dalsi
faze reseni semestralni prace. Testy pro rozsirena zadani na druhou
stranu slouzi jen jako jedno z mnoha kriterii hodnoceni kvality Vaseho
reseni.

Pro 3. rozsirene zadani nemame specialni sadu testu (zpusob, jakym
budete implementovat spousteni procesu z diskoveho zarizeni, se muze
skupinu od skupiny dramaticky lisit). Pro testovani muzete napriklad
vyuzit testy zakladniho zadani, ktere budete poustet paralelne v
nekolika nezavislych procesech.


Na zaver pripojuji strucnou rekapitulaci nejblizsich dulezitych terminu
semestru:

* 10. a 14. 10. 2013 probehnou cviceni zamerena na seznameni s
    prostredim pro vypracovani semestralnich praci.

* 17. a 21. 10. 2013 probehnou cviceni zamerena na podrobne seznameni se
    zdrojovym kodem Kalista.

* Do 13. 10. 2013 prosim nahlaste slozeni sveho tymu a preference
    rozsireneho zadani (ne do konference). Kratce po tomto datu posleme
    kazdemu prihlasenemu studentu email s pristupovymi udaji k repository
    sveho tymu.

* Standardni termin pro odevzdani 1. zakladniho zadani je 10. 11. 2013.
    Zcela presne budeme testovat, zda projde testy 1. zakladniho zadani
    obsah Vaseho repository s casovym razitkem 11. 11. 2013 00:00 CET.


- Vojtech Horky

-------------- next part --------------
A non-text attachment was scrubbed...
Name: tests-as1.tar.bz2
Type: application/x-bzip2
Size: 6442 bytes
Desc: not available
URL: <http://d3s.mff.cuni.cz/pipermail/nswi004/attachments/20131009/5f9a7bd6/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tests-as1e.tar.bz2
Type: application/x-bzip2
Size: 8440 bytes
Desc: not available
URL: <http://d3s.mff.cuni.cz/pipermail/nswi004/attachments/20131009/5f9a7bd6/attachment-0001.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tests-as2.tar.bz2
Type: application/x-bzip2
Size: 20925 bytes
Desc: not available
URL: <http://d3s.mff.cuni.cz/pipermail/nswi004/attachments/20131009/5f9a7bd6/attachment-0002.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tests-as2e.tar.bz2
Type: application/x-bzip2
Size: 17827 bytes
Desc: not available
URL: <http://d3s.mff.cuni.cz/pipermail/nswi004/attachments/20131009/5f9a7bd6/attachment-0003.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tests-as3.tar.bz2
Type: application/x-bzip2
Size: 11743 bytes
Desc: not available
URL: <http://d3s.mff.cuni.cz/pipermail/nswi004/attachments/20131009/5f9a7bd6/attachment-0004.bin>
-------------- next part --------------
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.

  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.
  V tomto pripade 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.

      Poznamka: Pro implementaci variadickych funkci jsou potreba funkce
      va_start(), va_arg(), va_end() apod. Neni prilis vhodne tyto funkce
      implementovat rucne (prochazenim zasobniku), protoze tim se nezaruci
      shoda chovani techto funkci s chovanim prekladace (napr. v pripade
      zmeny ABI). Vhodnejsi je vyuzit builtin funkci a typu pro implementaci
      variadickych funkci a typu, ktere poskytuje primo prekladac
      (__builtin_va_list, __builtin_va_start atd.).

    * 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.

      Poznamka: Za dostatecnou implementaci klavesnicoveho bufferu je
      povazovano pole konstantni velikosti. Pri zaplneni klavesnicoveho
      bufferu je pripustne dalsi znaky "zahazovat". Pokud se rozhodnete
      implementovat dynamicky klavesnicovy buffer, mejte na zreteli
      komplikace, ktere mohou plynout napriklad z potreby alokovat pamet
      pro novy znak v ramci obsluhy preruseni klavesnice.

      I pri pouziti konstatniho klavesnicoveho bufferu je vsak nutne dodrzet
      spravnou synchronizaci zapisu a cteni. Uvedomte si dobre, jaka jsou
      uskali synchronizace pri pouziti reentrantnich a nereentrantnich
      zpusobu obsluhy preruseni.

    * 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 definovano makro NDEBUG, makro assert() 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
      makro NDEBUG definovano, makro assert() neudela nic.

    * makro dprintk(ARGS...)

      Pokud neni definovano makro NDEBUG, makro dprintk() vypise na konzoli
      informaci o nazvu funkce a cislo radku, na kterem bylo pouzito, a
      formatovany retezec ARGS. Pokud je makro NDEBUG definovano, makro
      dprintk() 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 zastavi beh jadra.


  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)

      Zjistete zdroj preruseni a obsluzte jej. Uvedomte si, ze v jeden okamzik
      muze indikovat preruseni vice zdroju soucasne.

    * address error (AdEL, AdES)

      Nastava pri cteni/zapisu z/na nezarovnanou adresu a pri pristupu
      do adresoveho prostoru jadra z uzivatelskeho rezimu. Nastala-li vyjimka
      v kernelu, vyvolejte panic, v opacnem pripade zabijte prislusne vlakno.

    * bus error (IBE, DBE)

      Nastava pri pristupu na neplatnou fyzickou adresu. Nastala-li vyjimka
      v kernelu, vyvolejte panic, v opacnem pripade zabijte prislusne vlakno.

    * break point (BP)

      Nastava pri vykonani instrukce BREAK. Vyjimku je mozne ignorovat, pokud
      neni instrukce v branch delay slotu. Byla-li instrukce v brach delay
      slotu a nastala-li vyjimka v kernelu, vyvolejte panic, v opacnem pripade
      zabijte prislusne vlakno.

    * reference to WatchHi/WatchLo address (WATCH)

      Nastava pri pristupu do rozmezi adres definovaneho registry CP0
      WatchHi a WatchLo. Vyjimku je mozne 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. Nastala-li
      vyjimka v kernelu, vyvolejte panic, v opacnem pripade zabijte prislusne
      vlakno.

    * coprocessor unusable (CpU)

      Nastava pri pristupu na koprocesor, ktery neni neni oznacen jako
      pristupny. Nastala-li vyjimka v kernelu, vyvolejte panic, v opacnem
      pripade zabijte prislusne vlakno.

    * trap exception (Tr)

      Nastava pri provedeni podminenych instrukci Txx. V ramci semestralni
      prace nejsou tyto instrukce k nicemu vyuzivany, takze nastala-li vyjimka
      v kernelu, vyvolejte panic, v opacnem pripade zabijte prislusne vlakno.

    * arithmetic overflow (Ov)

      Nastava pri preteceni dvojkoveho doplnku pri celociselnych operacich
      (prenosy z bitu 31 a 30 se lisi). Nastala-li vyjimka v kernelu,
      vyvolejte panic, v opacnem pripade zabijte prislusne vlakno.


  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 a ktery byl predtim
      naalokovan funkci malloc().


  Jednoduchy planovac
  -------------------

    Naimplementujte preemptivni planovani vlaken k behu na procesoru. Staci
    zakladni 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 (pasivne) 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.

      Poznamka: V pripade varianty thread_sleep() je nutne zajistit spravne
      fungovani pro cely rozsah typu "unsigned int" bez nebezpeci preteceni.
      Cekani lze tedy realizovat opakovanym volanim thread_usleep().

    * 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. 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 (zamek, 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 (pasivne) 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 makro 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 typicky
  obsahovat #include direktivy, ktere zajisti vlozeni vasich hlavickovych
  souboru s prislusnymi deklaracemi.

  Dale musi soubor api.h obsahovat deklaraci extern funkce run_test(void),
  kterou zavolate z vaseho jadra pro spusteni testu.


Rozsirene zadani -----------------------------------------------------------

  Rozsirene zadani vychazi ze zakladniho zadani, musi tedy implementovat
  vsechny funkce 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. Je vhodne, aby se jiz behem implementace
  2. a 3. zakladniho zadani pouzivaly korektne synchronizacni primitiva a
  dalsi postupy pro spravny pristup ke sdilenym datum na vice procesorech.

  Implementace nesmi byt omezena nejakym konstantnim poctem nakonfigurovanych
  procesoru (vyjma omezeni, ktera vyplyvaji primo z vlastnosti simulatoru,
  resp. procesoru MIPS) nebo predpokladat konkretni pocet 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 beznych 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, pri vypisu panic hlasky apod.


  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.


  Jednoduchy planovac
  -------------------

    Kazdy procesor bude strategii round-robin planovat vlakna nezavisle,
    neni nutne implementovat dynamicky load ballancing. Priblizne rovnomerneho
    vyuziti vsech procesoru staci dosahnout jednorazovym rozmistovanim vlaken
    na procesory ve funkci thread_create().


  Synchronizacni primitiva
  ------------------------

  Pasivni synchronizacni primitiva implementujte pokud mozno s malou
  latenci, tedy vyuzitim kritickych sekci ochranenych aktivnim
  synchronizacnim primitivem (spinlockem).

  Je take 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

    * 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 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.

    * 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 (pasivne) 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);


  - read/write 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 (pasivne) 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 zablokovana nejaka vlakna,
      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
  rozhrani klasicke implementace 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 (load linked)
  a SC (store conditional).

  Navrhnete a implementujte take vhodny vicevlaknovy test/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: 2012/10/07 17:00
-------------- next part --------------
Zadani 2. semestralni prace: -------------------------------------------------

  Cilem 2. semestralni prace je rozsirit jadro z 1. semestralni prace
  o spravu fyzicke pameti a mapovani virtualni pameti do fyzicke. Zadani ma
  formu rozhrani, ktere je nutno naimplementovat. K zajisteni rozumne urovne
  funkcnosti je nutne, aby implementace prosla sadou testu.

  Ukolem bude naprogramovat:

    * alokator fyzickych stranek (ramcu) pameti
    * spravce oblasti virtualni pameti
    * mapovani virtualni pameti do fyzicke
    * pristup vlaken do virtualniho adresoveho prostoru
    * obsluhu vyjimek TLB

  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.

  Obecne pozadavky tykajici se deklarace a pouzivani chybovych kodu,
  definice zakladnich typu pouzivanych v zadani a pozadavky na formu
  zdrojovych textu jsou shodne se zadanim 1. semestralni prace.


  Virtualni adresovy prostor procesoru
  ------------------------------------

    V zavislosti na aktualnim rezimu (user, supervisor, kernel) je 32bitovy
    virtualni adresovy prostor procesoru MIPS R4000 rozdelen na nekolik
    segmentu.

    V uzivatelskem rezimu (user mode) je pristupny pouze segment USEG
    v rozsahu adres [0x00000000,0x800000000), ktery je mapovany do fyzicke
    pameti pres TLB. Pristup na adresu mimo USEG vyvola vyjimku Address
    Error.

    V rezimu supervizora (supervisor mode) jsou definovany segmenty SUSEG
    v rozsahu adres [0x00000000,0x80000000) a segment SSEG v rozsahu adres
    [0xC0000000,0xE00000000). Adresy v obou segmentech jsou mapovany do
    fyzicke pameti pres TLB, pricemz segment SUSEG je analogii segmentu USEG
    v uzivatelskem rezimu. Pristup na adresy mimo SUSEG a SSEG vyvola
    vyjimku Address Error.

    Konecne v rezimu jadra (kernel mode) jsou definovany segmenty KUSEG
    v rozsahu adres [0x00000000,0x80000000), KSEG0 v rozsahu adres
    [0x80000000,0xA0000000), KSEG1 v rozsahu adres [0xA0000000,0xC0000000),
    KSSEG/KSEG2 v rozsahu adres [0xC0000000,0xE0000000) a KSEG3 v rozsahu
    adres [0xE0000000,0xFFFFFFFF]. Adresy v segmentech KUSEG, KSSEG a KSEG3
    jsou mapovany do fyzicke pameti pres TLB, pricemz segmenty KUSEG resp.
    KSSEG jsou analogii segmetu USEG resp. SSEG v uzivatelskem rezimu, resp.
    rezimu supervizora. Adresy v segmentech KSEG0 a KSEG1 jsou mapovany do
    fyzicke pameti primo pevnym identickym mapovanim (pouze odectenim
    pocatecni adresy segmentu). Virtualni adresy segmentu KSEG0 jsou tedy
    mapovany na fyzicke adresy v rozsahu [0x00000000,0x20000000), podobne
    je to i v pripade KSEG1. Na realnem systemu se segmenty KSEG0 a KSEG1
    lisi take v tom, ze pristup na adresy KSEG0 obchazi cache procesoru.


  Virtualni adresovy prostor
  --------------------------

    V kontextu operacniho systemu je virtualni adresovy prostor, nebo take
    nazyvany mapa virtualni pameti (address space, virtual memory map, vmm),
    datova struktura, ktera udrzuje informace o vyuziti adresoveho prostoru.

    Rozdeleni virtualniho adresoveho prostoru procesoru na segmenty je
    pevne dane. Protoze se zpracovani virtualnich adres procesorem
    v jednotlivych segmentech lisi, je virtualni adresovy prostor typicky
    alokovan po souvislych oblastech (virtual memory area, vma) uvnitr techto
    segmentu. Oblasti virtualni pameti reprezentuji souvisly blok adres ve
    virtualnim adresovem prostoru. V zavislosti na tom, v jakem segmentu
    adresoveho prostoru procesoru se urcita oblast nachazi, je pak mapovani
    rozsahu virtualnich adres oblasti do fyzicke pameti bud pevne dane
    (pripad segmentu KSEG0 a KSEG1) nebo definovane uzivatelem (operacnim
    systemem), ktery ma moznost ovlivnovat obsah TLB.

    Virtualni adresovy prostor je jednim z prostredku sdilenych vsemi vlakny
    jednoho uzivatelskeho procesu. Z bezpecnostnich duvodu ma kazdy proces
    operacniho systemu svuj vlastni virtualni adresovy prostor a tedy i
    mapovani do fyzicke pameti.

    Kostra kernelu z 1. semestralni prace dosud pracuje pouze s nezavislymi
    vlakny, ktera bezi v rezimu jadra. Pro nasledny prechod k uzivatelskym
    procesum s vice vlakny bezicimi v uzivatelskem rezimu (napln 3.
    semestralni prace) je ovsem nejprve nutne vytvorit podporu pro
    virtualizaci pameti, jeji mapovani do fyzicke pameti a sdileni tohoto
    mapovani vlakny.


Zakladni zadani ------------------------------------------------------------

  Alokator fyzicke pameti
  -----------------------

    Implementujte spravu fyzickych stranek (ramcu) pameti pro evidenci,
    ktere fyzicke stranky jsou jiz pouzity a ktere jsou stale volne.

    Pro spravu fyzicke pameti pouzijte vhodnou datovou strukturu, pricemz
    duraz je kladen na rozumne rychle nalezeni volnych fyzickych stranek.

    * int frame_alloc(void **paddr, const size_t cnt, const vm_flags_t flags)

      Funkce nalezne a alokuje @cnt po sobe jdoucich volnych fyzickych
      stranek pameti. V pripade, ze je @cnt je rovno nule nebo alokace
      nebyla uspesna, vraci ENOMEM. V opacnem pripade vraci EOK.

      V zavislosti na hodnote bitovych priznaku v argumentu @flags funkce
      bud automaticky zvoli vhodnou fyzickou adresu zacatku alokovanych
      fyzickych stranek a vrati ji ve @paddr (priznak VF_VA_AUTO), nebo se
      pokusi o alokaci zacinajici na fyzicke adrese zadane volajicim ve
      @paddr (priznak VF_VA_USER).

      Pokud je v argumentu @flags uveden bitovy priznak VF_AT_KSEG0, resp.
      VF_AT_KSEG1, alokace se uvazuje jen v te casti fyzicke pameti, ktera
      je pristupna ze segmentu KSEG0, resp. KSEG1 virtualniho adresoveho
      prostoru, tedy v rozsahu fyzickych adres [0x00000000,0x20000000).
      Naopak priznaky VF_AT_KUSEG, VF_AT_KSSEG a VF_AT_KSEG3 oznacuji moznost
      prednostne alokovat fyzicke stranky mimo tento rozsah (jsou-li
      k dispozici), aby nedochazelo ke zbytecnemu plytvani fyzickych
      stranek pristupnych z KSEG0, resp. KSEG1.

      Za volne fyzicke stranky se povazuji pouze ty, ktere lze bez omezeni
      pouzit, neobsahuji tedy staticky alokovanou pamet (kod a data jadra,
      struktury samotneho alokatoru apod.) nebo fyzicke stranky drive
      alokovane volanim funkce frame_alloc() a dosud neuvolnene.

    * int frame_free(const void *paddr, const size_t cnt)

      Uvolneni @cnt po sobe jdoucich fyzickych stranek zacinajicich na
      fyzicke adrese @paddr. Uvolnit lze pouze fyzicke stranky, ktere byly
      drive alokovany funkci frame_alloc(), tedy nikoliv staticky alokovanou
      pamet pro kod a data jadra, struktury samotneho alokatoru apod.

      Je pripustne, aby bylo nejprve pomoci jednoho volani funkce
      frame_alloc() naalokovano nekolik fyzickych stranek a podintervaly
      techto fyzickych stranek byly pote jednotlive uvolnovany opakovanym
      volanim frame_free(). Podobne je mozne pomoci frame_free() uvolnit
      souvisly interval fyzickych stranek, ktery byl vsak postupne naalokovan
      vice nez jednim volanim frame_alloc().

      Funkce vraci EOK, bylo-li uvolneni uspesne, nebo EINVAL, pokud @cnt je
      rovno nule, @paddr neobsahuje fyzickou adresu zarovnanou na pocatek
      fyzicke stranky nebo posloupnost @cnt po sobe jdoucich fyzickych stranek
      nebyla drive alokovana pomoci frame_alloc().


  Uprava stavajiciho alokatoru haldy
  ----------------------------------

    Stavajici kernelovy alokator s rozhranim malloc()/free() alokuje pamet
    primo z haldy umistene v segmentu KSEG0 virtualniho adresoveho prostoru.
    Protoze soucasne s timto alokatorem bude stranky fyzicke pameti alokovat
    take volani frame_alloc(), je nutne zajistit, aby alokator haldy pouzival
    jen fyzicke stranky pameti pridelene pomoci frame_alloc().

    Upravte stavajici alokator tak, aby pouzival jako svuj backend rozhrani
    frame_alloc()/frame_free() a zaroven aby vzdy vracel pouze pamet ze
    segmentu KSEG0 virtualniho adresoveho prostoru procesoru, tj. aby bylo
    mozne k alokovane pameti pristupovat bez pouziti TLB.


  Pristup vlaken do virtualniho adresoveho prostoru
  -------------------------------------------------

    Rozsirte stavajici implementaci vlaken v jadre o podporu pristupu
    k virtualni pameti mapovane pres TLB v ramci virtualniho adresoveho
    prostoru.

    Pro ucely testovani rozsirte chovani funkce thread_create() ze zadani
    1. semestralni prace:

    * int thread_create(
          thread_t *thread_ptr, void *(*thread_start)(void *), void *data,
          const thread_flags_t flags)

      Pokud bude argument @flags obsahovat priznak TF_NEW_VMM, pro nove
      vytvorene vlakno bude take vytvoren novy virtualni adresovy prostor.
      Nove vlakno tedy nebude sdilet mapovanou virtualni pamet s volajicim
      vlaknem.


  Sprava virtualniho adresniho prostoru
  -------------------------------------

    Sprava oblasti virtualni pameti zahrnuje alokaci, manipulaci a
    uvolnovani oblasti virtualni pameti v kontextu virtualniho adresoveho
    prostoru prave beziciho vlakna. V ramci zakladniho zadani sestava
    virtualni adresovy prostor z nejvyse MAX_AREAS souvislych oblasti.
    Oblasti se nesmi prekryvat, velikost a zacatek oblasti musi byt
    zarovnan na nejmensi velikost stranky podporovanou procesorem,
    v pripade MIPS R4000 tedy 4 KiB.

    Konstantu MAX_AREAS vhodne urcete tak, aby vyhovovala zamyslenym
    pozadavkum vlaken na alokaci oblasti virtualni pameti. V ramci
    zakladniho zadani je pripustne pro reprezentaci virtualniho adresoveho
    prostoru pouzit staticky alokovane datove struktury, tedy datove
    struktury napevno dimenzovane na MAX_AREAS oblasti virtualni pameti.
    Zaroven je pripustne, aby operace nad temito datovymi strukturami
    mely linearni slozitost v zavislosti na hodnote konstanty MAX_AREAS,
    lze tedy napriklad pouzit staticke pole.

    * int vma_map(
          void **from, const size_t size, const vm_flags_t flags)

      Funkce alokuje oblast ve virtualnim adresovem prostoru o velikosti
      @size bajtu, pro tuto oblast alokuje fyzickou pamet (ne nutne souvislou)
      a vytvori mapovani prave alokovane virtualni pameti do fyzicke.

      V zavislosti na bitovych priznacich v argumentu @flags funkce bud
      automaticky zvoli vhodnou adresu zacatku oblasti virtualni pameti
      a vrati ji ve @from (priznak VF_VA_AUTO), nebo se pokusi vytvorit
      oblast na adrese zadane volajicim ve @from (priznak VF_VA_USER).

      Dalsi bitove priznaky v argumentu @flags urcuji typ segmentu
      virtualniho adresoveho procesoru, ve kterem bude virtualni oblast
      alokovana. Hodnoty priznaku pro jednotlive segmenty jsou VF_AT_KUSEG,
      VF_AT_KSEG0, VF_AT_KSEG1, VF_AT_KSSEG a VF_AT_KSEG3. Alokace
      v segmentech KSEG0 a KSEG1 se vzajemne vylucuji, pokud jsou mapovany
      na stejne fyzicke adresy.

      Funkce vraci EOK pokud byla pamet alokovana a namapovana, EINVAL pokud
      nebylo mozne alokovat oblast se zacatkem na adrese @from v danem
      segmentu virtualniho adresoveho prostoru procesoru, nebo pokud
      @from ci @size nejsou zarovnany, ENOMEM pokud neni dostatek fyzicke
      pameti k provedeni operace nebo jiz bylo dosazeno MAX_AREAS oblasti
      virtualni pameti.

    * int vma_resize(const void *from, const size_t size)

      Funkce zvetsi/zmensi velikost oblasti virtualni pameti, jejiz zacatek
      lezi na adrese @from, na novou velikost @size bajtu. Nesmi pritom
      dojit k prekryvu dvou ruznych oblasti virtualni pameti nebo zvetseni
      oblasti za hranici prislusneho segmentu.

      Vraci EOK pokud byla velikost oblasti uspesne zmenena, EINVAL
      pokud @from neukazuje na platnou oblast, pokud by melo dojit
      k prekryvu s jinou oblasti v dusledku zvetseni, nebo pokud neni nova
      velikost zarovnana, ENOMEM pokud nebylo mozne oblast zvetsit v kvuli
      nedostatku pameti.

    * int vma_unmap(const void *from)

      Funkce zrusi mapovani pameti pro oblast se zacatkem na adrese @from,
      ktera byla predtim vytvorena volanim vma_map(). Dale uvolni fyzickou
      pamet, do ktere byla oblast mapovana a zrusi prislusnou oblast
      virtualni pameti.

      Vraci EOK pokud byla pamet uvolnena a mapovani zruseno, EINVAL pokud
      @from neukazuje na zacatek oblasti vytvorene volanim vma_map().

      Pro korektni implementaci operace vma_unmap() je nutne krome odstraneni
      mapovani oblasti v internich strukturach kernelu provest take operaci
      "TLB shootdown", cili odstraneni prislusnych zaznamu z TLB, jsou-li tam
      aktualne obsazeny.


  Obsluha vyjimek TLB
  -------------------

    Pri prekladu virtualni adresy na fyzickou muze procesor vyvolat dva
    druhy vyjimek. Prvni z vyjimek je TLB Refill, ktera je vyvolana
    v pripade, ze pro pozadovanou virtualni adresu nebyl v TLB nalezen
    zaznam s odpovidajici fyzickou adresou. Druhou z vyjimek je TLB Invalid,
    ktera je vyvolana v pripade, ze v TLB sice existuje polozka pro
    pozadovanou virtualni adresu, ale tato polozka je neplatna.

    Obsluha obou typu vyjimek by mela nalezt mapovani pro prislusnou virtualni
    adresu a naplnit TLB. Pokud nebude pro danou virtualni adresu mapovani
    existovat, ocekava se, ze jadro vlakno, ktere vyjimku vyvolalo, zrusi.

    Pozn.: Moznost oznacit polozku TLB jako neplatnou lze pouzit napr. pri
    implementaci copy-on-write mechanizmu nebo swapovani, v ramci zadani 2.
    semestralni prace vsak pro jeho vyuziti neni prostor.

    TLB procesoru MIPS R4000 muze v jednom okamziku obsahovat mapovani
    nalezejici vice adresovym prostorum (diky polozce ASID). Zadani pozaduje
    tuto vlastnost dusledne vyuzivat a vyhnout se tak zbytecnym drahym operacim
    "TLB flush" pri kazde zmene aktivniho adresoveho prostoru.

    Soucasne je nutne, aby pocet adresovych prostoru nebyl omezen rozsahem
    platnych ASID hodnot. Pridelovani ASID hodnot je tedy nutne provadet
    dynamicky, napriklad algoritmem LRU.


  Kopirovani pameti mezi vlakny
  -----------------------------

    Pro testovaci ucely implementujte nasledujici funkce:

    * int copy_from_thread(const thread_t thr,
          void *dest, const void *src, const size_t len)

      Funkce zkopiruje data z virtualni pameti vlakna @thr do virtualni
      pameti volajiciho vlakna. Vraci EOK pokud byla data zkopirovana,
      EINVAL pokud je identifikace zdrojoveho vlakna neplatna.

    * int copy_to_thread(const thread_t thr,
          void *dest, const void *src, const size_t len)

      Funkce zkopiruje data z virtualni pameti volajiciho vlakna do
      virtualni pameti vlakna @thr. Vraci EOK pokud byla data zkopirovana,
      EINVAL pokud je identifikace zdrojoveho vlakna neplatna.


  Integrace s testy
  -----------------

  K integraci s testy vytvorite hlavickovy soubor api.h, ktery bude typicky
  obsahovat #include direktivy, ktere zajisti vlozeni vasich hlavickovych
  souboru s prislusnymi deklaracemi.

  Hlavickovy soubor api.h by mel take obsahovat makro FRAME_SIZE, jehoz
  hodnota bude odpovidat velikosti fyzicke stranky (ramce), resp. virtualni
  stranky v bajtech, kterou kernel pouziva.


Rozsirene zadani -----------------------------------------------------------

  Sprava oblasti virtualni pameti
  -------------------------------

    Sprava oblasti virtualni pameti zahrnuje alokaci, manipulaci a
    uvolnovani oblasti virtualni pameti v kontextu virtualniho adresoveho
    prostoru prave beziciho vlakna. Oblasti se nesmi prekryvat, velikost a
    zacatek oblasti musi byt zarovnan na nejmensi velikost stranky
    podporovanou procesorem, v pripade MIPS R4000 tedy 4 KiB.

    Pozadavky na rozhrani pro spravu virtualni pameti zachovava chovani
    pozadovane pro zakladni zadani, pocet oblasti virtualni pameti jiz vsak
    nesmi byt omezen konstatnou, ale je dan pouze realne dostupnou pameti.

    Pro spravu oblasti virtualni pameti pouzijte vhodnou datovou strukturu
    (nikoliv staticky alokovanou), pricemz duraz je kladen na rozumne rychle
    nalezeni oblasti virtualni pameti k dane virtualni adrese a i take nalezeni
    odpovidajici fyzicke adresy. Casova slozitost takove operace by tedy mela
    byt lepsi nez linearni vzhledem k poctu oblasti a velikosti oblasti.
    Rozumnymi kandidaty na takovou datovou strukturu jsou naprikad stromove
    struktury, hashovaci struktury nebo hierarchicke strankovaci tabulky.
    Motivace a cile pro vyber pouzite datove struktury dukladne rozeberte
    v dokumentaci.

    * int vma_map(
          void **from, const size_t size, const vm_flags_t flags)

      Funkce alokuje oblast ve virtualnim adresovem prostoru o velikosti
      @size bajtu, pro tuto oblast alokuje fyzickou pamet (ne nutne souvislou)
      a vytvori mapovani prave alokovane virtualni pameti do fyzicke.

      V zavislosti na bitovych priznacich v argumentu @flags funkce bud
      automaticky zvoli vhodnou adresu zacatku oblasti virtualni pameti
      a vrati ji ve @from (priznak VF_VA_AUTO), nebo se pokusi vytvorit
      oblast na adrese zadane volajicim ve @from (priznak VF_VA_USER).

      Dalsi bitove priznaky v argumentu @flags urcuji typ segmentu
      virtualniho adresoveho procesoru, ve kterem bude virtualni oblast
      alokovana. Hodnoty priznaku pro jednotlive segmenty jsou VF_AT_KUSEG,
      VF_AT_KSEG0, VF_AT_KSEG1, VF_AT_KSSEG a VF_AT_KSEG3. Alokace
      v segmentech KSEG0 a KSEG1 se vzajemne vylucuji, pokud jsou mapovany
      na stejne fyzicke adresy.

      Funkce vraci EOK pokud byla pamet alokovana a namapovana, EINVAL pokud
      nebylo mozne alokovat oblast se zacatkem na adrese @from v danem
      segmentu virtualniho adresoveho prostoru procesoru, nebo pokud
      @from ci @size nejsou zarovnany, ENOMEM pokud neni dostatek fyzicke
      pameti k provedeni operace.

    * int vma_unmap(const void *from)

      Funkce zrusi mapovani pameti pro oblast se zacatkem na adrese @from,
      ktera byla predtim vytvorena volanim vma_map(). Dale uvolni fyzickou
      pamet, do ktere byla oblast mapovana a zrusi prislusnou oblast
      virtualni pameti.

      Vraci EOK pokud byla pamet uvolnena a mapovani zruseno, EINVAL pokud
      @from neukazuje na zacatek oblasti vytvorene volanim vma_map().

      Pro korektni implementaci operace vma_unmap() je nutne krome odstraneni
      mapovani oblasti v internich strukturach kernelu provest take operaci
      "TLB shootdown", cili odstraneni prislusnych zaznamu z TLB, jsou-li tam
      aktualne obsazeny.

    * int vma_resize(const void *from, const size_t size)

      Funkce zvetsi/zmensi velikost oblasti virtualni pameti, jejiz zacatek
      lezi na adrese @from, na novou velikost @size bajtu. Nesmi pritom
      dojit k prekryvu dvou ruznych oblasti virtualni pameti nebo zvetseni
      oblasti za hranici prislusneho segmentu.

      Vraci EOK pokud byla velikost oblasti uspesne zmenena, EINVAL
      pokud @from neukazuje na platnou oblast, pokud by melo dojit
      k prekryvu s jinou oblasti v dusledku zvetseni, nebo pokud neni nova
      velikost zarovnana, ENOMEM pokud nebylo mozne oblast zvetsit v kvuli
      nedostatku pameti.

    * int vma_remap(const void *from, const void *to)

      Funkce premapuje oblast zacinajici na adrese @from na adresu @to.
      Velikost oblasti a posloupnost mapovani virtualnich stranek na fyzicke
      zustava zachovana. Prekryti virtualnich adres v oblasti @from a @to
      je pripustne.

      Vraci EOK pokud bylo premapovani uspesne, EINVAL pokud na adrese
      @from neni platna oblast, pokud @to neni zarovnana adresa, nebo pokud
      by pri presunu melo dojit k prekryti jiz existujici oblasti.

    * int vma_merge(const void *area1, const void *area2)

      Funkce spoji oblasti zacinajici na @area1 a @area2 do jedne oblasti,
      pokud spolu sousedi. Zacatek nove oblasti je na nizsi z pocatecnich
      adres obou oblasti. Vraci EOK pokud bylo spojeni provedeno, EINVAL
      pokud jsou jedna nebo obe oblasti neplatne, pokud spolu nesousedi
      nebo pokud oblasti patri do ruznych segmentu.

    * int vma_split(const void *from, const void *split)

      Funkce rozdeli oblast zacinajici na adrese @from na dve sousedici
      oblasti, pricemz nove vznikla oblast bude zacinat na adrese @split.

      Vraci EOK pokud bylo rozdeleni uspesne, EINVAL pokud @from neukazuje
      na zacatek existujici oblasti, pokud @split neni uvnitr rozdelovane
      oblasti nebo pokud hodnota @split neni zarovnana.


  Novy alokator haldy
  -------------------

    Implementujte novy alokator kernelove haldy jako funkcni nahradu
    jednoducheho alokatoru z 1. semestralni prace. Alokator bude vracet
    pouze pamet ze segmentu KSEG0 virtualniho adresoveho prostoru procesoru,
    tj. bude mozne k alokovane pameti pristupovat bez pouziti TLB.

    Implementujte nejmene tyto alokacni strategie:

      * first fit
      * next fit
      * best fit
      * worst fit

    Vyber pozadovane alokacni strategie bude mozny v dobe prekladu, napriklad
    pomoci nastaveni hodnoty vhodneho makra na konstanty

    MALLOC_STRATEGY_FIRST_FIT
    MALLOC_STRATEGY_NEXT_FIT
    MALLOC_STRATEGY_BEST_FIT
    MALLOC_STRATEGY_WORST_FIT.

    Privatni rozhrani alokatoru by melo byt navrzeno tak, aby umoznovalo snadne
    rozsirovani o dalsi alokacni strategie.

    Navrhnete a implementujte take vhodny vicevlaknovy test/benchmark, ktery
    bude implementovane alokacni strategie testovat a merit dobu provadeni
    ruznych operaci, pametovy overhead a fragmentaci. V dokumentaci potom
    uvedte porovnani jednotlivych strategii.

    Verejne rozhrani alokatoru odpovida 1. semestralni praci:

    * 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 a ktery byl predtim
      naalokovan funkci malloc().

--
Posledni modifikace: 2012/10/07 20:00
-------------- next part --------------
Zadani 3. semestralni prace: -------------------------------------------------

  Cilem 3. semestralni prace je rozsirit jadro z 2. semestralni prace
  o podporu behu uzivatelskych procesu. Bude nutne vytvorit infrastrukturu
  pro vytvareni a beh uzivatelskych procesu a pro systemova volani, ktera
  budou zpristupnovat relevantni funkce jadra uzivatelskym procesum. Cast
  teto infrastruktury bude nutne implementovat v uzivatelskem rezimu, kde je
  potreba procesum poskytnout zakladni prostredi pro beh.

  Zadani ma formu rozhrani, ktere je nutno naimplementovat. Toto rozhrani je
  urceno pro uzivatelske procesy, na rozhrani infrastruktury v jadre nejsou
  kladeny formalni pozadavky s vyjimkou obecnych pozadavku na uroven kodu
  a systematicnost. Implementace rozhrani musi projit sadou testu, ktere
  overi jeji zakladni funkcnost.

  Konkretni podoba systemovych volani nutnych pro realizace uvedeneho rozhrani
  neni soucasti zadani. Navrhnete tedy systemova volani dle vlastniho uvazeni
  a dukladne je zdokumentujte.

  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.

  Obecne pozadavky tykajici se deklarace a pouzivani chybovych kodu,
  definice zakladnich typu pouzivanych v zadani a pozadavky na formu
  zdrojovych textu jsou shodne se zadanim 1. semestralni prace.


Zakladni zadani ------------------------------------------------------------

  Rozhrani systemovych volani
  ---------------------------

    Naimplementujte obecny mechanismus systemovych volani z uzivatelskeho
    prostoru do kernelu, ktery umozni volat na strane uzivatelskeho prostoru
    konkretni sluzby kernelu a predavat jim argumenty a na strane kernelu
    psat obsluzne rutiny techto sluzeb.

    Pri implementaci je kladen duraz na rozumnou rozsiritelnost o nove
    sluzby a jejich obsluzne rutiny a dostatecne oddeleni abstrakce
    (uzivatelske funkce nebudou predstavovat primo systemova volani, ale
    jen jejich wrappery, kernelove obsluzne rutiny nebudou primo soucasti
    obsluzne rutiny vyjimky, ale budou take oddeleny vhodnou strukturou).

    Respektujte pravidlo, ze systemova volani by se mela pouzivat jen na ty
    sluzby, ktere nelze snadno implementovat primo v uzivatelskem prostoru.
    Kernel nelze chapat jako "sdilenou knihovnu", kterou pouzivaji uzivatelske
    procesy pro delegaci beznych funkci, ktere lze plne implementovat
    v uzivatelskem prostoru.

    Kernelove obsluzne rutiny systemovych volani musi dusledne testovat
    spravnost a konzistenci argumentu predanych z uzivatelskeho prostoru (zda
    napriklad ukazatele ukazuji na korektne namapovanou pamet uzivatelskeho
    procesu a tudiz pri praci s uzivatelskou pameti v kernelu nemuze vzniknout
    vyjimka apod.). Na nespravne nebo nekonzistentni argumenty by mel kernel
    reagovat chybovou navratovou hodnotou nebo ukoncenim procesu, nikoliv
    zastavenim behu celeho systemu.


  Podpora uzivatelskeho procesu
  -----------------------------

    Po uspesne inicializaci jadra dojde ke spusteni jedineho uzivatelskeho
    procesu, jehoz binarni obraz bude nahran spolecne s kernelem a dalsimi
    potrebnymi daty primo do pameti simulatoru.

    Tento uzivatelsky proces bude vyuzivat behovou infrastrukturu
    prostrednictvim staticky linkovane knihovny. Vytvorte ukazkovy
    uzivatelsky proces, ktery bude ve vice uzivatelskych vlaknech
    demonstrovat vystup na konzoli a synchronizaci.


  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 printf(const char *format, ...)

      Funkce vypise formatovany retezec na konzoli, stejne jako 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). 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.

    * 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.


    Poznamka: Za velmi nevhodnou se z implementacniho hlediska povazuje
    realizace vsech vyse uvedenych funkci (predevsim printf() a gets()) primo
    jako systemova volani (viz uvodni kapitola). Naopak implementovat funkce
    putc(), puts() a getc() jako systemova volani je zrejme v poradku.


  Zakladni ladici prostredky
  --------------------------

    * makro assert(EXPR)

      Pokud neni definovano makro NDEBUG, makro assert() vyhodnoti vyraz EXPR
      a pokud je vysledek nulovy, vypise informaci o nazvu funkce, souboru a
      cisle radku, na kterem nebyl splnen predpoklad EXPR, a zavola exit().
      Pokud je makro NDEBUG definovano, neudela makro assert() nic.

    * makro dprintf(ARGS...)

      Pokud neni definovano makro NDEBUG, makro dprintf() vypise na konzoli
      informaci o nazvu funkce a cislo radku, na kterem bylo pouzito, a
      formatovany retezec ARGS. Pokud je makro NDEBUG definovano, neudela makro
      dprintf() nic.


  Dynamicky alokovana pamet
  -------------------------

    Nasledujici funkce umoznuji uzivatelskemu procesu dynamicky alokovat a
    uvolnovat pamet. Spravce uzivatelske pameti typicky pracuje s jednou
    oblasti virtualni pameti, jejiz velikost je dana pametovymi naroky
    procesu. Velikost teto oblasti by nemela byt fixni po celou dobu behu
    procesu, ale v pripade potreby a dostatku fyzicke pameti by mela rust a
    naopak v pripade, ze jsou na jejim konci nevyuzite stranky, by se mela
    zmensovat.

    Implementace samotneho algoritmu alokatoru uzivatelske pameti muze byt
    velmi jednoducha, muzete napr. prevzit a upravit puvodni alokator
    z Kalista. Je vsak nutne, aby alokator haldy v uzivatelskem procesu
    a alokator kernelove haldy byly na sobe nezavisle.

    * void *malloc(const size_t size)

      Funkce alokuje blok pameti pozadovane velikosti. 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 a ktery byl predtim
      naalokovan funkci malloc().


    Poznamka: Za velmi nevhodnou se z implementacniho hlediska povazuje
    realizace vyse uvedenych funkci malloc() a free() jako systemova volani
    (viz uvodni kapitola).


  Rozhrani pro praci s vlakny
  ---------------------------

    Rozhrani pro praci s vlakny vychazi ze specifikace POSIX, je vsak misty
    velmi zjednodusene a obsahuje nektere funkce, ktere puvodni POSIX
    specifikace neobsahuje.

    * 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 @thread_start bude spustena
      v nove vytvorenem vlakne. Pocet vlaken v systemu je omezen pouze
      dostupnou pameti. Je-li @thread_ptr platny ukazatel, zapise do nej
      identifikaci noveho vlakna.

    * thread_t thread_self(void)

      Funkce vrati identifikator prave beziciho vlakna.

    * int thread_join(thread_t thr, void **thread_retval)
    * int thread_join_timeout(
          thread_t thr, void **thread_retval, const unsigned int usec)

      Funkce zablokuje volajici vlakno dokud vlakno @thread neskonci. Pokud
      je @thread_retval platny ukazatel, zapise ukazatel na navratovou
      hodnotu vlakna na misto odkazovane @thread_retval. 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.

      Varianta _timeout ceka (pasivne) 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. Pri dobehnuti odpojeneho
      vlakna je automaticky uvolnena pamet alokovana pro vlakno.

    * int thread_cancel(thread_t thr)

      Funkce zrusi zadane (bezici) vlakno. Vlakno, ktere ceka na ukonceni
      ruseneho vlakna, je odblokovano (navratova hodnota je nastavena na
      NULL). Funkce vraci EINVAL pokud je identifikace vlakna neplatna, jinak
      EOK.

    * 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.

      Poznamka: V pripade varianty thread_sleep() je nutne zajistit spravne
      fungovani pro cely rozsah typu "unsigned int" bez nebezpeci preteceni.
      Cekani lze tedy realizovat opakovanym volanim thread_usleep().

    * 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.

    * void thread_exit(void *thread_retval)

      Funkce ukonci provadeni volajiciho vlakna a zajisti zpristupneni
      ukazatele @thread_retval vlaknu volajicimu thread_join na ukoncene
      vlakno.

    * void exit(void)

      Funkce ukonci provadeni vsech vlaken aktualniho procesu, tedy
      efektivne ukonci cely proces. Pri ukoncovani nesmi dojit k deadlocku.
      Veskere prostedky procesu jsou uvolneny. Pokud v jadre jiz nebezi
      zadny uzivatelsky proces, ukonci se beh celeho jadra.


    Poznamka: Datovy typ vlakna v uzivatelskem prostoru by v zadnem pripade
    nemel predstavovat primo strukturu, kterou pouziva kernel. Uzivatelsky
    proces by nemel mit moznost zadnym nestandardnim zpusobem zasahnout do
    kernelove implementace planovani vlaken nebo pomoci podvrzene kernelove
    struktury jinym zpusobem zmenit chovani systemu.

    Uzivatelsky datovy typ vlakna by mel predstavovat identifikator vlakna,
    jehoz planost muze kernel jednoznacne overit.


  Synchronizacni primitiva
  ------------------------

    Stejne jako rozhrani pro vlakna vychazi rovnez rozhrani pro praci se
    synchronizacnimi primitivy ze specifikace POSIX, je vsak zjednodusene
    a v navaznosti na predchozi semestralni prace pouziva odlisne nazvy
    funkci a jine typy pro synchronizacni primitiva.

  - mutex (zamek, binarni semafor)

    * int mutex_init(struct mutex *mtx)

      Funkce inicializuje mutex do stavu odemceno. Pokud inicializace
      probehne v poradku, vraci EOK, v opacnem pripade ENOMEM/EINVAL podle
      charakteru chyby.

    * int mutex_destroy(struct mutex *mtx)

      Funkce provede uklid ridici struktury mutexu. Pokud je rusen mutex,
      na kterem jsou jeste zablokovana nejaka vlakna, ukonci se aktualni
      vlakno. Pokud je identifikator mutexu neplatny, funkce vraci EINVAL.
      Probehne-li operace v poradku, funkce vraci EOK.

    * int 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.

      Pokud je identifikator mutexu neplatny, funkce vraci EINVAL.

    * int 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, ukonci se aktualni
      vlakno. Pokud je identifikator mutexu neplatny, funkce vraci EINVAL.
      Probehne-li operace v poradku, funkce vraci EOK.


    Poznamka: Datovy typ mutexu v uzivatelskem prostoru by v zadnem pripade
    nemel predstavovat primo strukturu, kterou pouziva kernel. Uzivatelsky
    proces by nemel mit moznost zadnym nestandardnim zpusobem zasahnout do
    kernelove implementace synchronizace nebo pomoci podvrzene kernelove
    struktury jinym zpusobem zmenit chovani systemu.

    Uzivatelsky datovy typ mutexu muze obsahovat identifikator kerneloveho
    mutexu, jehoz planost muze kernel jednoznacne overit. Dalsi moznosti
    je implementovat mutex ciste v uzivatelskem prostoru za pouziti jinych
    primitivnich operaci.


  Integrace s testy
  -----------------

  K integraci s testy vytvorite hlavickovy soubor librt.h, ktery bude typicky
  obsahovat #include direktivy, ktere zajisti vlozeni vasich hlavickovych
  souboru knihovny behove podpory s prislusnymi deklaracemi. Test bude dodan
  jako zdrojovy kod uzivatelskeho procesu.

  Dale je nutne pripravit knihovnu behove podpory librt.a, ktera bude obsahovat
  kod behoveho prostredi procesu. S touto knihovnou bude slinkovan kod kazdeho
  uzivatelskeho procesu.

  Start uzivatelskeho procesu vypada tak, ze jadro zacne provadet kod procesu
  od urcite adresy, kde bude typicky vstupni bod behoveho prostredi z knihovny
  librt.a, ktery provede nezbytnou inicializaci (alokatoru pameti atd.) a
  zavola funkci main() uzivatelskeho procesu. Pri navratu z funkce main() pak
  behove prostredi ukonci proces (tj. vsechna jeho bezici vlakna).


Rozsirene zadani -----------------------------------------------------------

  Diskove zarizeni
  ----------------

  Implementujte v ramci jadra read-only ovladac diskoveho blokoveho zarizeni
  (s pouzitim zarizeni ddisk v MSIMu). Moznost cteni bloku dat bude vhodnym
  rozhranim zpristupneno uzivatelskym procesum.


  Rozhrani pro praci s procesy
  ----------------------------

  Implementujte jednoduche rozhrani v uzivatelskem prostoru, ktere umozni
  pracovat s uzivatelskymi procesy, jez pobezi v oddelenych adresovych
  prostorech.

    * int process_create(
          process_t *process_ptr, const void *img, const size_t size)

      Funkce vytvori novy uzivatelsky proces s nezavislym adresovym
      prostorem, jehoz binarni obraz velikosti @size bajtu bude nacten
      z adresoveho prostoru aktualniho procesu z adresy @img.

      Vraci chybovy kod, pokud se proces nepodari vytvorit, jinak EOK.
      Je-li @process_ptr platny ukazatel, zapise do nej identifikaci noveho
      procesu.

    * process_t process_self(void)

      Funkce vrati identifikator prave beziciho procesu.

    * int process_join(process_t proc)
    * int process_join(process_t proc, const unsigned int usec)

      Funkce zablokuje volajici vlakno, dokud proces @proc neskonci. Vraci
      EINVAL pokud je identifikace procesu neplatna, pokud jiz na proces
      ceka nekdo jiny, nebo pokud vlakno vola funkci na svuj vlastni proces.

      Varianta _timeout ceka (pasivne) na ukonceni procesu nejdele usec
      mikrosekund, pokud proces neni ukoncen do uplynuti teto doby, vraci
      ETIMEDOUT.

    * int kill(process_t proc)

      Funkce zrusi zadany (bezici) proces. Vlakno, ktere ceka na ukonceni
      ruseneho procesu, je odblokovano. Funkce vraci EINVAL pokud je
      identifikace procesu neplatna, jinak EOK.


    Poznamka: Datovy typ procesu v uzivatelskem prostoru by v zadnem pripade
    nemel predstavovat primo strukturu, kterou pouziva kernel. Uzivatelsky
    proces by nemel mit moznost zadnym nestandardnim zpusobem zasahnout do
    kernelove implementace planovani vlaken nebo pomoci podvrzene kernelove
    struktury jinym zpusobem zmenit chovani systemu.

    Uzivatelsky datovy typ procesu by mel predstavovat identifikator procesu,
    jehoz planost muze kernel jednoznacne overit.


  Spousteni uzivatelskych procesu
  -------------------------------

  V ramci zakladniho uzivatelskeho procesu (ktery bude spusten jadrem
  z fyzicke pameti) umoznete cist a spoustet z blokoveho zarizeni dalsi
  uzivatelske procesy.

  Na blokovem zarizeni (disku) neni nutne implementovat zadny souborovy
  system, postaci na nej linearne nahrat obsah binarnich obrazu jednotlivych
  procesu, ktere se maji spustit, a vhodnou datovou strukturou ulozenou na
  disku tyto procesy identifikovat.

--
Posledni modifikace: 2012/10/07 20:30


More information about the NSWI004 mailing list