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.
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:
1 2 3 |
$ git fetch $ git switch thread $ make clean |
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ť):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
$ make qemu ... $ uthread thread_a started thread_b started thread_c started thread_c 0 thread_a 0 thread_b 0 thread_c 1 thread_a 1 thread_b 1 ... thread_c 99 thread_a 99 thread_b 99 thread_c: exit after 100 thread_a: exit after 100 thread_b: exit after 100 thread_schedule: no runnable threads $ |
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.
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 context
z kernel/proc.h.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:
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 (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:
1 |
(gdb) p/x *next_thread |
Pomocou x môžete zobraziť obsah pamäte:
1 |
(gdb) x/x next_thread->stack |
Krokujte inštrukciami assembly pomocou step instruction:
1 |
(gdb) si |
On-line dokumentáciu pre gdb nájdete tu.
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:
1 2 |
$ make ph $ ./ph 1 |
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:
1 2 3 |
100000 puts, 3.991 seconds, 25056 puts/second 0: 0 keys missing 100000 gets, 3.981 seconds, 25118 gets/second |
Čí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:
1 2 3 4 5 |
$ ./ph 2 100000 puts, 1.885 seconds, 53044 puts/second 1: 16579 keys missing 0: 16579 keys missing 200000 gets, 4.322 seconds, 46274 gets/second |
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()
.
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:
1 2 3 4 |
pthread_mutex_t lock; // deklarácia zámku pthread_mutex_init(&lock, NULL); // inicializácia zámku pthread_mutex_lock(&lock); // zamkni/získaj zámok pthread_mutex_unlock(&lock); // odomkni/uvoľni zámok |
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?
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.
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.
1 2 3 |
$ make barrier $ ./barrier 2 barrier: notxv6/barrier.c:42: thread: Assertion `i == t' failed. |
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()
.
1 2 3 4 |
pthread_cond_wait(&cond, &mutex); // zaspí na premennej cond, uvoľní zámok // mutex, ktorý po opätovnom zobudení zamkne pthread_cond_broadcast(&cond); // zobudí všetky vlákna, ktoré spia na // podmienkovej premennej cond |
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:
bstate.round
označuje aktuálne kolo. Túto premennú by ste mali inkrementovať vždy, keď všetky vlákna dosiahnu bariéru.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.
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.
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, atď. do vášho modulu vlákien v xv6.