1. cvičenie – utility

Xv6 a UNIX-ové nástroje

Toto cvičenie vás zoznámi s operačným systémom xv6 a jeho systémovými volaniami.

Pripravenie virtuálky na cvičení

Počas prvých troch cvičení musíte pracovať na školských počítačoch, keďže všetky testy budete riešiť v prostredí virtuálneho stroja. Je teda užitočné, aby ste sa s týmto prostredím zoznámili a prípadne skonzultovali akékoľvek problémy s cvičiacimi. Teraz vytvoríte virtuálku, ktorú budete používať. Postupujte podľa tohto návodu:

  1. Otvorte Oracle VM VirtualBox z odkazu na pracovnej ploche alebo cez Štart.
  2. V paneli nástrojov kliknite na Import (alebo cez FileAppliance, skratka Ctrl+I).
  3. V priečinku C:\work zvoľte obraz virtuálneho stroja (os2023.ova). Ak tam nie je, nájdete ho na sieťovom disku na adrese J:\work alebo \\home31\apps\.
  4. Po importe virtuálneho stroja otvorte jeho nastavenia (pravý klik na virtuálku ➙ Settings).
  5. V časti System na karte Motherboard upravte veľkosť RAM a na karte Processor počet jadier podľa tabuľky nižšie.

    Miestnosť C-117 C-119 CPU
    RAM 6 GB 3 GB 3 GB
    CPU 10 4 3

    Po nastavení potvrďte dialóg tlačidlom OK.

  6. Otvorte Virtual Media Manager (v ponuke File). Vyberte disk importovanej virtuálky a nastavte jeho typ na Immutable (v dolnej časti okna na karte Attributes). Potvrďte tlačidlom Apply.
  7. Virtuálka je teraz pripravená na spustenie a môžete pokračovať ďalšou sekciou.

Synchronizácia s repozitárom

Na prvých troch cvičeniach musíte pracovať na školských počítačoch, aby ste si zvykli na prostredie, ktoré budete používať na všetkých troch testoch. Začnite teda cvičenie tým, že si vytvoríte repozitár na službe GitHub podľa pokynov na stránke Synchronizácia repozitára. Keď to budete mať hotové, môžete pokračovať hlavným obsahom cvičenia. V prípade otázok sa neváhajte opýtať cvičiacich.

Bootovanie xv6 (ľahká)

Aby ste mohli začať pracovať s xv6, musíte mať nainštalované všetky nástroje, vrátane operačného systému xv6. Ak používate nami poskytnutý virtuálny stroj, všetko je už pripravené a sťahovanie repozitára môžete preskočiť.

Stiahnite zdrojáky xv6:

Repozitár je nastavený tak, aby sa po naklonovaní automaticky prepol na vetvu util. Môžete si to overiť príkazom git status:

Repozitár xv6-labs-2023 sa trochu líši od systému xv6-riscv popísaného v sprievodnej knihe kurzu. Repozitár, ktorý ste práve naklonovali obsahuje niekoľko súborov naviac. Ak ste zvedaví, pozrite si históriu repozitára príkazom:

Súbory, ktoré budeme potrebovať na tomto a ďalších cvičeniach budú distribuované pomocou Gitu. Na každom cvičení prepnete repozitár na inú vetvu, ktorá obsahuje verziu xv6 špeciálne pripravenú pre dané cvičenie. Napríklad na vetvu util sa prepnete príkazom git switch util. Viac informácií o programe git nájdete v používateľskom manuáli. Git vám umožní zaznamenať zmeny, ktoré urobíte v kóde. Napríklad, keď dokončíte jednu úlohu z cvičenia, svoje zmeny uložíte (commitnete) takto:

Vysvetlenie: Príkazom git add sme pridali upravené/nové súbory, ktoré sa stanú súčasťou commitu. Príkazom git commit potom vyžiadame uskutočnenie commitu. Prepínačom -m môžete priamo v príkaze uviesť správu ku commitu. Bez prepínača je otvorený textový editor (nastavený v súbore ~/.gitconfig), v ktorom je možné správu upraviť. Pripomíname, že commity vo vašich repozitároch musia spĺňať náležitosti uvedené v špecifikácii Conventional Commits 1.0.0.

Svoje aktuálne zmeny môžete sledovať pomocou príkazu git diff. Týmto príkazom zobrazíte zmeny, ktoré ste urobili od posledného commitu a príkazom git diff origin/util zobrazíte všetky zmeny od stavu, v akom ste repozitár xv6-labs-2023 obdržali. origin/util uvedený v príkaze je názov vetvy, v ktorej sa nachádza pôvodný kód z MIT, ktorý ste si stiahli na začiatku cvičenia (origin štandardne označuje vzdialený repozitár, z ktorého sťahujete kód).

Riešenia úloh z tohto cvičenia ukladajte do vetvy util. Túto vetvu budeme kontrolovať v rámci priebežnej kontroly repozitárov.

Skompilujte a spustite xv6:

Ak do príkazového riadka napíšete ls, mali by ste uvidieť podobný výstup:

Tieto súbory vytvorí program mkfs počas inicializácie súborového systému; väčšina z nich sú programy, ktoré môžete spustiť. Pred chvíľou ste jeden z nich spustili: ls.

xv6 nemá príkaz ps, ale ak stlačíte Ctrl+P, jadro vypíše informácie o každom procese. Ak to vyskúšate teraz, uvidíte dva riadky: jeden pre init a druhý pre sh.

Na vypnutie qemu stlačte postupne: spolu Ctrl+A a potom samostatne X.

Hodnotenie

Svoje riešenie môžete otestovať hodnotiacim programom zavolaním make grade. V jeho výstupe zistíte, ktoré úlohy ste vyriešeili správne. Plný počet bodov však neznamená, že váš kód je bezchybný.

sleep (ľahká)

Naimplementujte UNIX-ový program sleep pre xv6; vaša implementácia programu sleep by sa mala pozastaviť na užívateľom definovaný počet tikov. Jeden tik je definovaný jadrom xv6 ako čas medzi dvoma prerušeniami časovacieho čipu. Svoje riešenie uložte do user/sleep.c.

Pomôcky:

  • Než začnete programovať, prečítajte si kapitolu 1 z xv6 knižky.
  • Pozrite sa na zdrojový kód iných programov v priečinku user/ (napr. user/echo.c, user/grep.c, a user/rm.c), aby ste zistili ako načítať argumenty príkazového riadku zadané pri spustení programu.
  • Ak užívateľ zabudne uviesť argument, sleep by mal vypísať chybovú hlášku.
  • Argument príkazového riadku je reťazec; na celé číslo ho môžete skonvertovať pomocou funkcie atoi() (viď user/ulib.c).
  • Použite systémové volanie sleep().
  • Užitočné časti zdrojového kódu nájdete v týchto súboroch:
    kernel/sysproc.c
    implementácia systémového volania sleep() (hľadajte sys_sleep())
    user/user.h
    definícia volania sleep() z užívateľského programu
    user/usys.S
    kód assembly, ktorý prechádza z užívateľského módu do módu jadra
  • Funkcia main() by mala ako posledné volanie zavolať exit(0).
  • Pridajte svoj program sleep do premennej UPROGS v súbore Makefile. Keď to máte hotové, príkazom make qemu skompilujete program a môžete ho spustiť z xv6 shellu.
  • Na vylepšenie zručností v programovacom jazyku C si prečítajte knižku Programovací jazyk C (v origináli The C programming language) od Kernighana a Ritchieho. Ak radi sledujete video tutoriály, pozrite si opakovanie jazyka C od vášho kolegu Mariána Šebeňu.

Spustite program z xv6 shellu:

Ak sa váš program pozastavil, vaše riešenie je správne. Spustite make grade, či program sleep prejde všetkými testami.

make grade spúšťa všetky testy, aj tie, ktoré ešte nemáte vypracované. Ak chcete spustiť len jeden test, napíšte:

Týmto spustíte testy, ktoré obsahujú „sleep“. Druhý spôsob:

urobí to isté.

Po úspešnom dokončení úlohy nezabudnite vytvoriť commit!

pingpong (ľahká)

Napíšte program, ktorý použije systémové volania UNIX na poslanie bajtu medzi dvoma procesmi prostredníctvom dvojice rúr, jednej pre každý smer. Rodič by mal poslať jeden bajt detskému procesu, dieťa by po prijatí bajtu malo vypísať <pid>: received ping, kde <pid> je ID procesu, zapíše bajt do rúry rodičovi a ukončí činnosť. Rodič by mal prečítať bajt od dieťaťa, vypísať <pid>: received pong a ukončiť činnosť. Vaše riešenie uložte do súboru user/pingpong.c.

Pomôcky:

  • Použite pipe() na vytvorenie rúr.
  • Použite fork() na vytvorenie detského procesu.
  • Použite read() na prečítanie dát z rúry a write() na zápis do rúry.
  • Použite getpid() na zistenie ID volajúceho procesu.
  • Pridajte program do premennej UPROGS v súbore Makefile.
  • Používateľské programy v xv6 majú obmedzené množstvo dostupných knižničných funkcií. Ich zoznam nájdete v súbore user/user.h; ich kód (okrem systémových volaní) je v user/ulib.c, user/printf.c, and user/umalloc.c.

Spustite program z xv6 shellu. Mali by ste vidieť takýto výstup:

Vaše riešenie je správne ak program vymení bajt medzi dvoma procesmi a vypíše vyššie uvedený výstup.

Po úspešnom dokončení úlohy nezabudnite vytvoriť commit!

primes (stredná/ťažká)

Napíšte konkurentnú verziu prvočíselného sita pomocou rúr. Tento nápad pochádza od Douga McIlroya, vynálezcu UNIX-ových rúr. Obrázok na tejto stránke a sprievodný text vysvetľujú ako na to. Svoje riešenie uložte do súboru user/primes.c.

Vaším cieľom je použiť pipe() a fork() na zostavenie „potrubia“. Prvý proces vloží čísla od 2 po 35 do potrubia. Pre každé prvočíslo sa vytvorí jeden proces, ktorý bude prijímať dáta od ľavého suseda cez rúru a zapisovať pravému susedovi cez inú rúru. Keďže xv6 má obmedzený počet deskriptorov a procesov, prvý proces musí prestať pri čísle 35.

Pomôcky:

  • Nezabudnite uzatvoriť súborové deskriptory, ktoré nepotrebujete, pretože váš program vyčerpá všetky zdroje xv6 ešte predtým, ako prvý proces dosiahne 35.
  • Keď prvý proces odošle číslo 35, mal by počkať až kým sa celé potrubie neukončí, vrátane všetkých detí, vnukov, pravnukov etc. To znamená, že hlavný proces programu primes sa ukončí, až keď všetok výstup bol vypísaný na obrazovku a všetky prvočíselné procesy sa ukončili.
  • read() vráti nulu keď je zapisovacia strana rúry zatvorená.
  • Najjednoduchšie je do rúry priamo zapísať 32-bitové (4-bajtové) celé číslo (int) ako používať formátované ASCII znaky.
  • Procesy v potrubí vytvárajte iba vtedy, keď ich potrebujete.
  • Pridajte program do premennej UPROGS v súbore Makefile.
  • Ak kompilátor vyhadzuje falošnú chybu infinite recursion detected, umiestnite nad definíciu vašej rekurzívnej funkcie atribút kompilátora __attribute__((noreturn)). Urobte tak iba v prípade ak ste presvedčený, že je vaša implementácia korektná!

Vaše riešenie je správne, ak implementuje prvočíselné sito založené na rúrach a má takýto výstup:

Po úspešnom dokončení úlohy nezabudnite vytvoriť commit!

find (stredná)

Napíšte jednoduchú verziu UNIX programu find: nájde všetky súbory v priečinku s určeným názvom. Svoje riešenie uložte do súboru user/find.c.

Pomôcky:

  • Naštudujte si user/ls.c, aby ste vedeli prečítať obsah priečinkov.
  • Použite rekurziu, aby find mohol zostúpiť do podpriečinkov.
  • Nepoužívajte rekurziu na . a ...
  • Zmeny v súborovom systéme zotrvajú aj po reštarte qemu. Na inicializáciu súborového systému spustite make clean a potom make qemu.
  • V tomto programe musíte použiť reťazce jazyka C. Na pripomenutie si prečítajte K&R (Programovací jazyk C), napríklad sekciu 5.5.
  • Na porovnanie reťazcov použite funkciu strcmp().
  • Pridajte program do premennej UPROGS v súbore Makefile.

Vaše riešenie je správne, ak vyprodukuje takýto výstup (za predpokladu, že súborový systém obsahuje súbory b, a/b a a/aa/b):

Po úspešnom dokončení úlohy nezabudnite vytvoriť commit!

xargs (stredná)

Napíšte jednoduchú verziu UNIX-ového programu xargs: jeho argumenty určujú príkaz, ktorý sa má spustiť. Po spustení xargs prečíta riadky zo štandardného vstupu a spustí zložený príkaz pre každý riadok tak, že pripojí načítaný riadok k argumentom príkazu, ktorý dostal ako argument. Riešenie uložte do súboru user/xargs.c.

Teto príklad ilustruje správanie programu xarg:

Samotný príkaz je echo bye a ďalšie argumenty sú hello too. Úplný príkaz, ktorý bol spustený je echo bye hello too a jeho výstup je bye hello too.

Program xargs na UNIX-e optimalizuje spustenie príkazu tak, že do príkazu pošle viacero argumentov zo štandardného vstupu naraz. Túto optimalizáciu nemusíte implementovať. Ak si chcete porovnať správanie UNIX-ového xargs s vašou implementáciou, použite parameter -n s hodnotou 1. Napríklad:

Pomôcky:

  • Použite fork() a exec() na vyvolanie príkazu na každý riadok vstupu. V rodičovi použite wait, aby počkal kým dieťa vykoná príkaz.
  • Aby ste vedeli oddeliť riadky na vstupe, čítajte ho znak po znaku, až kým neprečítate znak nového riadku ('\n').
  • V súbore kernel/param.h je deklarovaná konštanta MAXARG, ktorá vám môže byť užitočná na deklaráciu poľa argv.
  • Pridajte program do premennej UPROGS v súbore Makefile.
  • Zmeny v súborovom systéme zotrvajú aj po reštarte qemu. Na inicializáciu súborového systému spustite make clean a potom make qemu.

xargs, find, a grep sa dajú výhodne použiť dokopy. Príkaz

spustí „grep hello“ na každom súbore s názvom b v priečnikoch pod aktuálnym (.) priečinkom.

Na otestovanie správnej funkcionality xargs spustite shell skript xargstest.sh. Vaše riešenie je správne, ak má takýto výstup:

Ak takýto výstup nevidíte, budete musieť opraviť chyby vo vašom programe find. Výstup obsahuje veľa dolárov ($), pretože shell xv6 nerozozná, že spracúva príkaz zo súboru namiesto z konzoly a vypíše $ pre každý príkaz v súbore.

Po úspešnom dokončení úlohy nezabudnite vytvoriť commit!

Týmto je cvičenie hotové. Skontrolujte, či vaše riešenie prejde všetkými testami make grade. Aby ste prešli posledným testom time, musíte vytvoriť nový súbor time.txt, v ktorom uvediete počet hodín, ktorý ste strávili nad zadaním ako celé číslo. Na záver nezabudnite aj túto zmenu commitnúť do repozitára.

Voliteľné úlohy

Prvý riešiteľ každej úlohy môže dostať bonusové body po kontrole riešenia. Informujte sa u prednášajúceho alebo cvičiaceho. Voliteľné úlohy môžete riešiť až po vyriešení všetkých úloh základnej časti cvičenia! Riešenia prijímame iba do konca druhého týždňa semestra.

  • Naprogramujte podporu regulárnych výrazov pre program find. V súbore grep.c nájdete zjednodušenú implementáciu regulárnych výrazov, ktorú môžete použiť. (ľahká)

  • Shell xv6 (user/sh.c) je iba ďalší užívateľský program, ktorý môžete vylepšiť. Jeho implementácia je minimalistická a chýba v ňom veľa funkcií, ktoré nájdete v skutočných shelloch. Tu je niekoľko funkcionalít, ktoré do shellu môžete pridať:
    • Upravte shell tak, aby nevypisoval $ počas spracovania príkazov zo súboru. (stredná)
    • Implementujte podporu wait. (ľahká)
    • Modifikujte shell, aby umožnil spustiť zoznam príkazov oddelených bodkočiarkou. (stredná)
    • Implementujte podporu pod-shellov implementáciou znakov ( a ). (stredná)
    • Pridajte podporu dopĺňania tabulátorom. (ľahká)
    • Upravte shell, aby udržoval históriu predchádzajúcich volaných príkazov. (stredná)

    Alebo implementujte hocijakú inú funkcionalitu, ktorú chcete, aby váš shell podporoval. (Ak sa cítite dobrodružne, môžete pridať do jadro systému funkcionality, ktoré potrebujete; samotný xv6 toho veľa nepodporuje.)