6. cvičenie – vlákna

Vlákna

Na tomto cvičení sa oboznámite s programovaním pomocou vlákien (multithreading). Vašou úlohou bude implementovať prepínanie medzi vláknami v module pre užívateľské vlákna. Potom sa presuniete z xv6 do prostredia unix a pomocou knižnice pthreads urýchlite program a na záver implementujete bariéru.

Než sa pustíte do písania kódu, prečítajte si kapitolu Chapter 7: Scheduling z xv6 knižky a preštudujte si príslušný kód.

Ak chcete pracovať s počítačmi v učebni, postupujte podľa sekcie Stiahnutie repozitára na cvičení na stránke Synchronizácia repozitára.

Prepnite sa do vetvy thread:

Uthread: prepínanie medzi vláknami (stredná)

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.cuser/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. Po dokončení by make grade mal ohlásiť, že prechádzate testom uthread.

Keď budete hotoví, spustite program uthread. 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

Jednou z funkcií, ktorú musíte dokončiť je thread_create(). Táto funkcia musí vytvoriť a inicializovať vlákno tak, aby sa funkcia thread_switch() po prvom prepnutí do tohto vlákna vrátila do funkcie určenej argumentom func so správne nastaveným zásobníkom 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.

Kód musíte pridať do funkcií thread_create() a thread_schedule() v súbore user/uthread.c a thread_switch() v súbore user/uthread_switch.S. Musíte zabezpečiť, aby pri prvom spustení vlákna funkcia thread_schedule() spustila funkciu, ktorá bola uvedená ako argument vo volaní funkcie thread_create(). Toto vlákno by malo mať svoj vlastný zásobník. Ďalej musíte zabezpečiť, aby funkcia thread_switch() uložila registre vlákna, z ktorého sa prepína a obnovila registre vlákna, do ktorého sa prepína. Registre je potrebné obnoviť do takého stavu, v ktorom sa vlákno nachádzalo pred prepnutím. Musíte sa rozhodnúť kde uložíte a obnovíte registre. Uložiť ich do štruktúry struct thread je dobrý nápad. Z funkcie thread_schedule() musíte zavolať thread_switch(). Do thread_switch() môžete 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 contextkernel/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 gdb-multiarch alebo riscv64-linux-gnu-gdb, 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 uthread.c. Breakpoint môže (ale 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(). Ak ste zastavili na breakpointe z iného procesu, zadávajte príkaz continue, až kým nezastavíte v procese uthread. 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.

Použitie vlákien (stredná)

V tejto časti cvičenia si vyskúšate paralelné programovanie s vláknami a zámkami s použitím hašovacej tabuľky. Toto cvičenie by ste mali robiť na Linuxe alebo macOS (použiteľný je aj WSL alebo iná emulácia POSIX prostredia), nie na xv6 a qemu. Počítač by mal mať viac jadier. Virtuálka, ktorú sme vám poskytli na začiatku semestra na túto úlohu postačuje, ak ste nezmenili počet jadier na 1.

V tejto úlohe použijete UNIX knižnicu pthread na prácu s vláknami. Informácie o nej sa môžete dozvedieť z manuálovej stránky man pthreads, prípadne z internetu, napríklad tu, tu a tu.

Súbor notxv6/ph.c obsahuje implementáciu hašovacej tabuľky, ktorú je korektne možné použiť len z jedného vlákna. V koreňovom priečinku xv6 (pravdepodobne ~/xv6-labs-2023) zadajte do terminálu tieto príkazy:

Všimnite si, že na zostavenie programu ph použije nástroj make kompilátor gcc prislúchajúci vášmu systému (nie RISC-V verziu). Argument programu ph špecifikuje počet vlákien, ktoré vykonávajú operácie put a get na hašovacej tabuľke. Program bude chvíľu bežať a potom vypíše takýto výstup:

Čísla môžu byť na vašom počítači odlišné, v závislosti od rýchlosti vášho počítača, počtu jadier procesora a jeho aktuálnej záťaže.

ph spúšťa dva testy. Najprv do hašovacej tabuľky pridá veľké množstvo kľúčov volaním funkcie put() a vypíše dosiahnutú rýchlosť počtu volaní funkcie put za sekundu. Potom z hašovacej tabuľky vytiahne uložené kľúče pomocou funkcie get(). Na terminál vypíše počet kľúčov, ktoré v tabuľke chýbali (v tomto prípade nula) a taktiež počet volaní funkcie get() za sekundu.

Aby program ph použil viac vlákien, treba ho spustiť s argumentom väčším ako jedna. Napríklad ph 2:

Na prvom riadku výstupu môžeme vidieť, že keď do hašovacej tabuľky pridávajú položky konkurentne dve vlákna, celková rýchlosť sa zväčšila približne dvojnásobne na 53 044 položiek za sekundu. Toto je najlepšie „paralelné zrýchlenie“, aké môžeme dosiahnuť s dvoma jadrami (t. j. dve jadrá zdvojnásobili počet operácií na jadro).

Dva riadky nižšie (16579 keys missing) nám ale hovoria, že veľké množstvo kľúčov sa z tabuľky stratilo. Počas operácií put muselo dôjsť k nejakej chybe. Prezrite si súbor notxv6/ph.c, obzvlášť funkcie put() a insert().

Prečo v tabuľke chýbali kľúče, keď sme použili dve vlákna, ale všetko bolo v poriadku pri jednom vlákne? Nájdite postupnosť udalostí v dvoch vláknach, ktoré spôsobia takýto problém. Odpoveď s vysvetlením napíšte do answers-thread.txt.
Aby ste tento problém vyriešili, vložte na správne miesta do kódu zamknutia a odomknutia zámkov. Jedná sa o funkcie put a get v súbore notxv6/ph.c. Po spustení programu ph s dvoma vláknami by mal byť počet stratených kľúčov nulový. Z knižnice pthread by ste mali použiť tieto volania:

Správnosť riešenia si overte spustením make grade. Mali by ste prejsť testom ph_safe. Test ph_fast ešte nemusí prechádzať.

Nezabudnite zavolať pthread_mutex_init(). Najprv otestujte kód s jedným vláknom, potom s dvoma. Nestratil sa ani jeden kľúč? Je paralelná verzia programu rýchlejšia (dosahuje väčší počet operácií na jedno jadro) ako jednovláknová?

V niektorých prípadoch je možné pristupovať k hašovacej tabuľke konkurentne. Vtedy sa pamäť dvoch put operácií neprekrýva (nezapisujú na to isté miesto) a takéto prístupy nie je nutné zamknúť. Viete upraviť ph.c, aby ste využili takúto situáciu a zrýchlili niektoré put() operácie? Pomôcka: čo tak jeden zámok na jeden hašovací bucket?

Upravte kód, aby niektoré operácie put mohli bežať paralelne a zároveň bola zachovaná korektnosť tabuľky. Úlohu máte hotovú, keď v make grade zbehnú testy ph_safe a ph_fast. Test ph_fast vyžaduje, aby bol výkon dvoch vlákien aspoň 1,25-krát rýchlejší ako jedno vlákno.

Bariéra (stredná)

V tejto úlohe budete implementovať synchronizačný dátový typ bariéra: jedná sa o presne určené miesto v aplikácii, kde sa musia všetky bežiace vlákna počkať a pokračovať môžu až vtedy, keď všetky dosiahli toto miesto. Na implementáciu použijete podmienkové premenné, ktoré fungujú podobne ako sleep a wakeup v xv6.

Podobne ako prechádzajúcu úlohu, aj túto by ste mali robiť na počítači s Linuxom, macOS alebo iným UNIX-kompatibilným systémom (okrem xv6).

Súbor notxv6/barrier.c obsahuje pokazenú bariéru.

Argument 2 špecifikuje počet vlákien, ktoré sa pred bariérou synchronizujú (premenná nthread v súbore barrier.c). Každé vlákno vykonáva cyklus. V každom cykle vlákno volá funkciu barrier() a potom sa uspí na náhodný počet milisekúnd. Predpoklad i == t zlyhá, pretože jedno vlákno opustí bariéru ešte predtým ako ju druhé vlákno dosiahne. Ak by bariéra fungovala správne, všetky vlákna sa zablokujú na volaní barrier(), až kým nthreads vlákien nezavolalo barrier().

Vašou úlohou je dosiahnuť korektné správanie bariéry. Z knižnice pthreads budete potrebovať funkcie, ktoré sme už spomenuli vyššie a ešte tieto dve: tu a tu.

Vaše riešenie musí prejsť testom barrier v make grade.

Po zavolaní funkcie pthread_cond_wait() je mutex uvoľnený. Zamkne sa až keď sa proces zobudí (po jeho zobudení bude mutex automaticky zamknutý).

V projekte nájdete hotovú funkciu barrier_init(). Vašou úlohou je implementovať funkciu barrier() tak, aby nenastala chyba assert. Štruktúra struct barrier je tiež definované, jej položky môžete používať.

Počas riešenia narazíte na niekoľko problémov:

  • Keďže vlákna bežia v cykle, musíte implementovať bariéru, ktorá je znovupoužiteľná. Jedno dosiahnutie bariéry všetkými vláknami nazveme kolo. Premenná bstate.round označuje aktuálne kolo. Túto premennú by ste mali inkrementovať vždy, keď všetky vlákna dosiahnu bariéru.
  • Musíte ošetriť prípad, v ktorom jedno vlákno obehne cyklus predtým, ako stihnú zvyšné vlákna opustiť bariéru. Špecifický prípad, ktorý musíte ošetriť je, keď jedno vlákno opustí bariéru a navýši premennú bstate.round ešte počas toho, ako ju používajú vlákna z predchádzajúceho kola.

Otestuje svoj kód s jedným, dvoma a viacerými vláknami.

Spustite príkaz make grade, aby ste overili správnosť svojho riešenia. 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.

Týmto je cvičenie ukončené. Svoje zmeny môžete commitnúť do repozitára.

Voliteľné úlohy pre uthread

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 12.11.2023 pre cvičenie v piatok a 19.11.2023 pre cvičenia v stredu a štvrtok.

  1. 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.)

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

  3. Pridajte zámky, podmienené premenné, bariéry, atď. do vášho modulu vlákien v xv6.