1. cvičenie – utility

Xv6 a unixové nástroje

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

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 a prejdite do vetvy util:

Repozitár xv6-labs-2021 sa o niečo odlišuje od verzie xv6 popísanej v sprievodnej knihe kurzu; je tam niekoľko súborov naviac. Ak ste zvedaví, pozrite si históriu repozitára:

Súbory, ktoré budeme potrebovať na tomto a ďalších cvičeniach budú distribuované pomocou Gitu. Pred chvíľou ste vytvorili novú vetvu (git branch util) na uloženie riešení tohto cvičenia. Viac informácií o gite 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 jedno z cvičení a chcete si uložiť svoj postup, môžete svoje zmeny uložiť (commitnúť) pomocou:

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-2021 obdržali. origin/xv6-labs-2021 je názov vetvy, v ktorej sa nachádza pôvodný kód, ktorý ste si stiahli.

Skompilujte a spustite xv6:

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

Tieto súbory vytvorí 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: Ctrl-a 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 UNIXový 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
  • Skontrolujte, či main() volá exit() na ukončenie programu.
  • 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.

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

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.

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 Unixový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.

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

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 a/b):

xargs (stredná)

Napíšte jednoduchú verziu UNIX programu xargs, ktorá prečíta riadky zo štandardného vstupu a spustí príkaz pre každý riadok, pričom daný riadok použije ako argument k príkazu. 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.

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ýhdne 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íkazu zo súboru namiesto z konzoly a vypíše $ pre každý príkaz v súbore.

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 svoje zmeny commitnúť do repozitára.

Voliteľné úlohy

  • Napíšte program uptime, ktorý vypíše ako dlho je počítač zapnutý v tikoch použitím systémového volania uptime(). (ľahká)

  • 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 hocičo iné, čo by ste chceli, aby váš shell robil. (Ak sa cítite dobrodružne, môžete upraviť aj jadro systému o funkcionality, ktoré potrebujete; samotný xv6 toho veľa nepodporuje.)