Vlákna

Na tomto cvičení sa oboznámite s multithreadingom. Vašou úlohou bude implementovať prepínanie medzi vláknami v module pre užívateľské vlákna. Týmito vláknami potom urýchlite program a na záver implementujete bariéru.

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

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 vytvorí a inicializuje vlákno tak, aby keď plánovač prepne do tohto 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.

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 thread_schedule() spustí 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 obnovilo 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 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 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:

  (gdb) file user/_uthread Reading symbols from user/_uthread... (gdb) b uthread.c:60

  1 2 3

  (gdb) file user/_uthread Reading symbols from user/_uthread... (gdb) b uthread.c:60

  Týmto sme nastavili breakpoint na riadku 60 v súbore uthread.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:

  (gdb) p/x *next_thread

  1	(gdb) p/x *next_thread

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

  (gdb) x/x next_thread->stack

  1	(gdb) x/x next_thread->stack

  Krokujte inštrukciami assembly pomocou step instruction:

  (gdb) si

  1

  (gdb) si

  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ý by mal byť aj WSL), 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 plne postačuje.

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-2021) zadajte do terminálu tieto príkazy:

Všimnite si, že na zostavenie ph Makefile použije 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().

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?

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še riešenie musí prejsť testom barrier v make grade.