9. cvičenie – užívateľské vlákna a alarm ⏲️

Užívateľské vlákna a alarm

Pomocou tohto cvičenia by sa vám malo rozjasniť, ako funguje ukladanie stavu procesu počas prepnutia kontextu a systémových volaní. Vašou úlohou bude implementovať prepínanie medzi vláknami v module pre užívateľské vlákna a alarm, ktorý bude odosielať programom udalosti podobné prerušeniam.

Než sa pustíte do písania kódu, prečítajte si kapitolky Chapter 4: Traps and device drivers a Chapter 6: Scheduling z xv6 knižky, preštudujte príslušný kód a prepnite sa do správnej vetvy:

Rozcvička: RISC-V assembly

Na toto cvičenie si musíte naštudovať trošku RISC-V assembly. Vo svojom repozitári nájdete súbor user/call.c. Preštudujte si ho (14 riadkov kódu). Po spustení príkazu make fs.img bude skompilovaný a okrem samotného spustiteľného súboru bude vytvorená aj disassemblovaná verzia programu user/call.asm. Tento súbor obsahuje kód assembly tohoto programu spolu s príslušnými riadkami jazyka C.

Prečítajte si kód v call.asm pre jednotlivé funkcie g(), f() a main(). Popis inštrukcií nájdete v doc/riscv-spec-v2.2.pdf. Po preštudovaní kódu odpovedajte na nasledovné otázky:

Ktoré registre obsahujú argumenty funkcií? V ktorom registri je napríklad uložené číslo 13 (argument funkcie printf())?
Kde je volanie funkcie f() z funkcie main()? Kde je volanie funkcie g()? (Pomôcka: Kompilátor môže funkcie inlinovať).
Na ktorej adrese sa nachádza funkcia printf()?
Aká hodnota je v registri ra hneď po jalr do funkcie printf() vo funkcii main()?

Uthread: prepínanie medzi vláknami

V tejto časti cvičenia navrhnete a implementujete mechanizmus prepnutia kontextu pre užívateľské vlákna. Na začiatok máte pripravené dva súbory: user/uthread.c a user/uthread_switch.S. Do súboru Makefile sme pridali pravidlo na skompilovanie programu uthread. Tento program už obsahuje väčšinu potrebného kódu,
vrátanie testu s troma vláknami. Do programu budete musieť doplniť kód na vytvorenie nového vlákna a prepínanie medzi vláknami.

Vašou úlohou je navrhnúť spôsob, ktorým budete vytvárať vlákna a ukladať/obnovovať registre na prepínanie medzi vláknami. Potom tento spôsob implementujte.

Keď budete hotoví, spustite program uthread v xv6. Výstup by mal vyzerať nasledovne (až na poradie vlákien, ktoré sa môže líšiť):

Tento výstup pochádza z troch testovacích vlákien. Každé z nich obsahuje cyklus, ktorý vypíše riadok a vzdá sa procesora pre iné vlákna.

Pri nezmenenom kóde neuvidíte žiadny výstup.

Postup

Musíte dokončiť funkciu thread_create(), ktorá vytvorí správne inicializované vlákno tak, aby keď plánovač prepne do tohoto vlákna po prvý raz, thread_switch() sa vráti do funkcie určenej argumentom func na zásobníku vlákna. Takže je potrebné správne inicializovať tie údajové štruktúry vlákna, z ktorých sa vo funkcii thread_switch() obnovuje hodnota registrov PC (program counter) a SP (stack pointer). Musíte sa rozhodnúť, kde uložiť/obnoviť registre. Existuje viacero možných riešení. Odporúčame, aby ste sa inšpirovali prepínaním kontextu vlákien jadra. K vášmu riešeniu musíte upraviť štruktúru thread. Vo funkcii thread_schedule() musíte zavolať thread_switch(); môžete jej poslať ľubovoľné argumenty, ktoré potrebujete, ale jej hlavným cieľom je prepnúť z vlákna t do vlákna next_thread.

Pomôcky:

  • thread_switch() robí presne to isté, čo funkcia swtch() v plánovači jadra, takže ju môžete celú skopírovať; zároveň však musíte použiť na uloženie kontextu vlákna rovnakú štruktúru, akú predpokladá funkcia swtch(), t.j. štruktúru context z kernel/proc.h.
  • Do struct thread môžete pridať polia, do ktorých uložíte registre (odporúčame štruktúru context z kernel/proc.h).
  • Na ladiace účely si môžete prezrieť assembly kód pre uthread v súbore user/uthread.asm.
  • Na testovanie kódu môžete krokovať funkciou thread_switch(). Použite riscv64-linux-gnu-gdb alebo gdb-multiarch, podľa vášho systému. Najprv si načítajte symboly pre užívateľský program uthread a vytvorte breakpoint:

    Týmto sme nastavili breakpoint na riadku 60 v súbore thread.c. Breakpoint môže (alebo nemusí) byť vyvolaný ešte pre spustením samotného programu uthread. Ako sa to môže stať?

    Po spustení shellu xv6, zadajte uthread a gdb zastaví na riadku vo funkcii thread_switch(). Teraz môžete preskúmať stav programu uthread:

    Pomocou x môžete zobraziť obsah pamäte:

    Krokujte inštrukciami assembly pomocou step instruction:

    On-line dokumentáciu pre gdb nájdete tu.

Alarm

V tejto časti cvičenia do xv6 pridáte funkcionalitu, ktorá periodicky informuje proces o tom, ako napr. zaťažuje procesor. Takáto funkcionalita sa hodí pre procesy, ktoré chcú obmedziť využívanie CPU alebo pre procesy, ktoré potrebujú vykonávať periodicky nejakú procedúru. Ináč povedané, budete implementovať primitívnu formu užívateľskej obsluhy prerušení/výpadkov; niečo podobné môžete napríklad využiť na obsluhu výpadkov stránok v aplikácii. Vaše riešenie je kompletné, ak prejde testami alarmtest a usertests.

Postup

Vytvorte nové systémové volanie sigalarm(interval, handler). Po tom, ako aplikácia zavolá sigalarm(n, fn), bude pravidelne každých n tikov procesora zavolaná funkcia fn. Po návrate z fn musí aplikácia pokračovať na tom mieste užívateľskej aplikácie, kde bola prerušená spustením funkcie fn. Pozn.: tik je nezávislá jednotka, jej veľkosť je určená hardvérovým časovačom.

Testovanie

Aby ste mohli svoju implementáciu otestovať, musíte mať implementované systémové volania sigalarm a sigreturn (viď. nižšie). V repozitári nájdete súbor user/alarmtest.c. Pridajte ho do Makefile, aby bol kompilovaný.

alarmtest() zavolá sigalarm(2, periodic) vo funkcii test0(). Týmto vyžiada od jadra, aby zavolalo funkciu periodic() každé 2 tiky. Assembly kód programu v
súbore user/alarmtest.asm sa vám môže hodiť na ladiace účely. Korektné riešenie by malo mať nasledovný výstup pre alarmtest (vrátane úspešných usertests):

Vašou prvou výzvou je zariadiť, aby obsluha alarmu bola vyvolaná, keď uplynie stanovený interval tikov. Na to musíte upraviť funkciu usertrap() v kernel/trap.c. Pýtate sa, ako ju upraviť? Musíte pochopiť, ako fungujú systémové volania (teda kód v kernel/trampoline.S a kernel/trap.c). Ktorý register obsahuje adresu užívateľskej inštrukcie, do ktorej sa má systémové volanie vrátiť?

Riešenie pozostáva iba z niekoľkých riadkov kódu, ale musíte nad nimi dobre porozmýšľať. Testovací súbor alarmtest.c neupravujte.

test0: vyvolanie obslužnej funkcie

Začnite úpravou jadra, aby skočil na obsluhu alarmu v užívateľskom priestore — v test0 vypíše alarm!. Zatiaľ vás nemusí zaujímať, čo sa stane po tomto výpise; je v poriadku, ak program padne. Pomôcky:

  • Už sme to napísali vyššie, ale pre istotu zopakujeme — musíte upraviť Makefile, aby bol alarmtest.c skompilovaný ako užívateľský program.
  • Do user/user.h pridajte tieto deklarácie (a zamyslite sa nad tým, čo znamenajú):
  • Upravte user/usys.pl (tento skript generuje súbor user/usys.S, kernel/syscall.h, and kernel/syscall.c) aby mohol alarmtest vyvolať systémové volanie sigalarm a sigreturn (nemusíte sa kvôli tomu učiť ?, stačí nahliadnuť do súboru).
  • Súbor kernel/syscall.c by ste mali rozšíriť o externé deklarácie funkcií sys_sigreturn() a sys_sigalarm(), a taktiež tabuľku obslužných funkcií systémových volaní. Spolu s tým súvisí úprava súboru kernel/syscall.h: treba priradiť číselné hodnoty novým systémovým volaniam.
  • Zatiaľ stačí, ak sys_sigreturn() (funkciu definujte v súbore kernel/sysproc.c) vráti nulu.
  • Funkcia sys_sigalarm() (tiež v tom istom súbore) by mala uložiť interval alarmu a smerník na obslužnú funkciu v nových poliach štruktúry proc (v kernel/proc.h) — musíte ich tam vytvoriť.
  • Musíte si tiež niekde ukladať koľko tikov uplynulo od posledného volania obslužnej funkcie (resp. koľko tikov zostáva do ďalšieho alarmu). Najvhodnejším miestom sa nám opäť zdá štruktúra proc (viď. bod vyššie). Polia štruktúry proc môžete inicializovať vo funkcii allocproc() v proc.c.
  • Ako počítať tiky? Hardvérové hodiny neustále tikajú a vyvolávajú prerušenia, ktoré sú obslúžené v usertrap(); mali by ste tam pridať nejaký kód
  • Počet tikov procesu by ste mali upraviť, len ak je proces prerušený časovačom; vyzerať by to malo nejako takto:
  • Funkciu obsluhy vykonajte iba vtedy, ak proces požiadal o alarm. Ale pozor, adresa funkcie môže byť aj nulová (napr. v alarmtest.asm, periodic() je na adrese 0).
  • S gdb sa ťažšie ladí kód výnimiek s viacerými procesormi. Uľahčite si prácu a povedzte qemu, aby použil iba jeden procesor:
  • Máte to hotové, ak alarmtest vypíše alarm!.

test1(): vrátenie do prerušeného kódu

S veľkou pravdepodobnosťou vám alarmtest padá v jednom z testov, prípadne po vypísaní alarm!, alebo alarmtest skončí bez výpisu test1 passed. Aby ste to opravili, musíte po ukončení obsluhy alarmu vrátiť riadenie na inštrukciu užívateľského programu, ktorá bola prerušená časovačom. Obsah registrov musí byť navrátený do stavu, v akom bol
pred prerušením, aby mohol program pokračovať po obsluhe alarmu. Taktiež musíte resetovať počítadlo alarmu pre daný proces, aby bol po stanovenom počte tikov
znovu vyvolaný.

Aby sa vám lepšie s touto úlohou začínalo, alarmový systém sme navrhli tak, aby každá obslužná funkcia alarmu zavolala systémové volanie sigreturn po dokončení obsluhy. V praxi to môžete vidieť vo funkcii periodic() v alarmtest.c. To znamená, že môžete pridať kód do usertrap() a sys_sigreturn(), ktorý pomáha riadne obnoviť proces po obsluhe alarmu.

Pomôcky:

  • Vo vašom riešení musíte uložiť a obnoviť registre—ktoré registre musíte uložiť a obnoviť, aby mohol prerušený kód bezproblémovo pokračovať? (Pomôcka: je ich fakt veľa).
  • Upravte usertrap tak, aby ste pred spustením funkcie alarmu uložili dostatočné množstvo informácií o stave užívateľského vlákna do struct proc, aby ste v obsluhe systémového volania sigreturn dokázali korektne obnoviť beh prerušeného užívateľského kódu.
  • Nevolajte obsluhu, ak obsluha ešte prebieha!!!

Keď prejdete testami test0 a test1, spustite usertests a skontrolujte, či ste nepoškodili nejaké iné časti jadra.

Týmto je cvičenie ukončené. Skontrolujte, či váš kód prechádza všetkými make grade testami. Na záver commitnite svoje zmeny do repozitára.

Voliteľná výzva pre uthread

Náš modul pre vlákna nespolupracuje pekne s operačným systémom. Napríklad, ak jedno užívateľské vlákno blokuje v systémovom volaní, iné užívateľské vlákna nebudú bežať, pretože plánovač užívateľských vlákien nevie o tom, že jedno vlákno bolo odplánované plánovačom xv6. Iný príklad: dve užívateľské vlákna nebudú bežať konkurentne na rôznych jadrách, pretože plánovač xv6 nevie o tom, že existujú viaceré vlákna, ktoré môžu bežať paralelne. Poznámka: ak by dve užívateľské vlákna mali bežať naozaj paralelne, táto implementácia by nefungovala z dôvodu viacerých súbehov (napr. dve rôzne vlákna na rôznych procesoroch môžu zavolať thread_schedule() konkurentne, vybrať rovnaké vlákno a bežať spolu na rôznych procesoroch.)

Tieto problémy je možné vyriešiť viacerými spôsobmi. Jedným z nich je použiť aktivácie plánovača; iné je použiť jedno vlákno jadra pre každý užívateľský proces (takto to robí Linux). Implementujte jeden z týchto spôsobov. Ľahké to nebude; budete musieť implementovať vyčistenie TLB pri aktualizácii tabuliek stránok pre
viacvláknový užívateľský proces.

Pridajte zámky, podmienené premenné, bariéry, etc. do vášho modulu vlákien.