Na tomto cvičení získate skúsenosti s redizajnovaním kódu s cieľom zvýšenia paralelizmu. Častým symptómom slabého paralelizmu na viacjadrových strojoch je veľké súperenie o zámky. Súperenie nastáva, keď jedno vlákno chce pristúpiť k zámku, ktorý je zamknutý iným vláknom. Zlepšiť paralelizmus je možné zmenou dátových štruktúr a stratégií zamykania tak, aby bolo súperenie znížené. Na tomto cvičení to urobíte pre pamäťový alokátor v xv6 a cache blokov.
Pred písaním kódu si prečítajte tieto časti z xv6 knižky:
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 lock:
|
1 2 3 |
$ git fetch $ git switch lock $ make clean |
Riešenia úloh z tohto cvičenia ukladajte do vetvy lock.
Program user/kalloctest zaťaží pamäťový alokátor xv6: tri procesy zväčšujú a zmenšujú svoj adresný priestor, čo vyvolá veľa volaní funkcií kalloc() a kfree(). Tieto dve funkcie zamykajú zámok kmem.lock. kalloctest vypisuje počet iterácií vo funkcii acquire, počas ktorých kontroluje, či je zámok zamknutý iným vláknom (#test-and-set). Vypisuje ich pre zámok kmem a ešte niekoľko ďalších zámkov. Vypísaný počet iterácií acquire vyjadruje približnú mieru súperenia o zámky. Výstup kalloctest pred začatím cvičenia vyzerá takto (počty sa môžu na vašom PC odlišovať):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
$ <kbd>kalloctest</kbd> start test1 test1 results: --- lock kmem/bcache stats lock: kmem: #test-and-set 18820 #acquire() 433058 lock: bcache: #test-and-set 0 #acquire() 1744 --- top 5 contended locks: lock: uart: #test-and-set 97375 #acquire() 117 lock: virtio_disk: #test-and-set 96764 #acquire() 183 lock: proc: #test-and-set 45428 #acquire() 522884 lock: proc: #test-and-set 25506 #acquire() 522875 lock: kmem: #test-and-set 18820 #acquire() 433058 tot= 18820 test1 FAIL start test2 total free number of pages: 32463 (out of 32768) .......... test2 OK start test3 ..........child done 10000 test3 OK start test4 ..........child done 100000 --- lock kmem/bcache stats lock: kmem: #test-and-set 135309 #acquire() 3006254 lock: bcache: #test-and-set 0 #acquire() 1860 --- top 5 contended locks: lock: wait_lock: #test-and-set 37427486 #acquire() 40008 lock: proc: #test-and-set 3108381 #acquire() 1689532 lock: proc: #test-and-set 207812 #acquire() 1588761 lock: kmem: #test-and-set 135309 #acquire() 3006254 lock: uart: #test-and-set 97375 #acquire() 1303 tot= 135309 test4 FAIL m 59382 n 135309 $ |
Pravdepodobne budete vidieť iné počty ako uvedené vyššie a taktiež rozdielne poradie piatich zámkov s najväčším súperením.
Funkcia acquire() si pre každý zámok ukladá počet jej volaní a počet cyklov, počas ktorých sa pokúsila získať zámok, ale nepodarilo sa jej to. kalloctest zavolá systémové volanie, ktoré vypíše tieto počty pre zámky kmem a bcache (ktoré sú hlavným bodom záujmu tohto cvičenia) a pre 5 najviac zaťažených zámkov. Ak nastáva súperenie o zámky, počet cyklov bude vysoký. Systémové volanie vracia súčet cyklov pre zámky kmem a bcache.
Na toto cvičenie musíte použiť nezaťažený stroj s viacerými jadrami. Ak používate virtuálny stroj, uistite sa, že využíva aspoň 2 jadrá vášho fyzického procesora. Stroj musí byť nezaťažený, ináč výpisy kalloctestu nebudú mať význam.
Súperenie o zámky v kallocteste je spôsobené najmä tým, že kalloc() má jeden zoznam voľných stránok chránený jedným zámkom. Na odstránenie súperenia o zámky musíte zmeniť návrh alokátora, aby nepoužíval iba jeden zoznam s jedným zámkom. Základnou ideou nového návrhu je použiť jeden zoznam na jedno CPU, každé s vlastným zámkom. Alokácie a uvoľnenia stránok budú vďaka tomu môcť prebiehať na rôznych CPU paralelne. Najväčšou výzvou je prípad, kedy jednému CPU dôjdu stránky, zatiaľ čo iné CPU ich ešte majú. Vtedy musí jeden CPU ukradnúť niekoľko stránok CPU, ktoré ešte nejaké stránky má. Proces kradnutia môže spôsobiť nejaké súperenie o zámky, ale v menšej miere, ako je tomu teraz.
kmem. To znamená, že pre každý zámok zavoláte funkciu initlock() a ako argument použijete meno, ktoré začína na kmem. Spustením kalloctest môžete zistiť, či vaša implementácia zmiernila súperenie o zámky. Či je možné alokovať celú fyzickú pamäť overíte testom usertests skbrkmuch. Výstup by mal vyzerať podobne ako je uvedené nižšie, ale konkrétne čísla sa môžu líšiť. Počty súperení by mali byť nižšie. Skontrolujte tiež, či prejdete testami usertests -q. make grade by mal hlásiť, že ste prešli všetkými testami kalloctests.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
$ kalloctest start test1 test1 results: --- lock kmem/bcache stats lock: kmem: #test-and-set 0 #acquire() 117911 lock: kmem: #test-and-set 0 #acquire() 169464 lock: kmem: #test-and-set 0 #acquire() 145786 lock: bcache: #test-and-set 0 #acquire() 1744 --- top 5 contended locks: lock: virtio_disk: #test-and-set 93747 #acquire() 183 lock: proc: #test-and-set 44010 #acquire() 526316 lock: proc: #test-and-set 24347 #acquire() 526309 lock: wait_lock: #test-and-set 11726 #acquire() 12 lock: pr: #test-and-set 4579 #acquire() 5 tot= 0 test1 OK start test2 total free number of pages: 32463 (out of 32768) .......... test2 OK start test3 ..........child done 10000 test3 OK start test4 ..........child done 100000 --- lock kmem/bcache stats lock: kmem: #test-and-set 3673 #acquire() 827384 lock: kmem: #test-and-set 3449 #acquire() 1215152 lock: kmem: #test-and-set 1924 #acquire() 1236349 lock: kmem: #test-and-set 0 #acquire() 1014 lock: kmem: #test-and-set 0 #acquire() 1014 lock: kmem: #test-and-set 0 #acquire() 1014 lock: kmem: #test-and-set 0 #acquire() 1014 lock: kmem: #test-and-set 0 #acquire() 1014 lock: bcache: #test-and-set 0 #acquire() 1860 --- top 5 contended locks: lock: wait_lock: #test-and-set 39121537 #acquire() 40020 lock: proc: #test-and-set 6853704 #acquire() 1672258 lock: proc: #test-and-set 214194 #acquire() 1614201 lock: uart: #test-and-set 195773 #acquire() 1459 lock: virtio_disk: #test-and-set 93747 #acquire() 183 tot= 9046 test4 OK $ <kbd>usertests sbrkmuch</kbd> usertests starting test sbrkmuch: OK ALL TESTS PASSED $ <kbd>usertests -q</kbd> ... ALL TESTS PASSED $ |
Pomôcky:
NCPU definovanú v kernel/param.h.freerange() môže prideliť všetku voľnú pamäť tomu CPU, ktoré ju zavolá.cpuid() vracia číslo aktuálneho CPU, ale volať ju a používať jej návratovú hodnotu môžete len vtedy, keď sú vypnuté prerušenia. Použite push_off() a pop_off() na vypnutie a zapnutie prerušení.kmem.|
1 2 3 4 |
$ make clean $ make KCSAN=1 qemu $ kalloctest .. |
Test kalloctest môže zlyhať, ale nemali by ste vidieť žiadne súbehy. Ak detektor súbehov deteguje súbeh, vypíše dva výpisy zásobníka, ktoré vyzerajú takto::
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
== race detected == backtrace for racing load 0x000000008000ab8a 0x000000008000ac8a 0x000000008000ae7e 0x0000000080000216 0x00000000800002e0 0x0000000080000f54 0x0000000080001d56 0x0000000080003704 0x0000000080003522 0x0000000080002fdc backtrace for watchpoint: 0x000000008000ad28 0x000000008000af22 0x000000008000023c 0x0000000080000292 0x0000000080000316 0x000000008000098c 0x0000000080000ad2 0x000000008000113a 0x0000000080001df2 0x000000008000364c 0x0000000080003522 0x0000000080002fdc ========== |
Názvy funkcií s číslami riadkov k týmto výpisom môžete získať pomocou príkzu addr2line:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
$ riscv64-linux-gnu-addr2line -e kernel/kernel 0x000000008000ab8a 0x000000008000ac8a 0x000000008000ae7e 0x0000000080000216 0x00000000800002e0 0x0000000080000f54 0x0000000080001d56 0x0000000080003704 0x0000000080003522 0x0000000080002fdc # STLAČTE ctrl-d kernel/kcsan.c:157 kernel/kcsan.c:241 kernel/kalloc.c:174 kernel/kalloc.c:211 kernel/vm.c:255 kernel/proc.c:295 kernel/sysproc.c:54 kernel/syscall.c:251 |
Detektor súbehov nemusíte spúšťať, ale môže sa vám hodiť. Pri zapnutom detektore súbehov je systém xv6 výrazne spomalený, preto v ňom asi nebudete chcieť spúšťať usertests.
Po úspešnom dokončení úlohy nezabudnite vytvoriť commit!
Druhá časť zadania je nezávislá od prvej. Na tejto úlohe môžete začať pracovať bez toho, aby ste mali hotovú prvú úlohu.
Funkcie sys_pause() a sys_uptime() v xv6 čítajú globálnu premennú ticks. Keďže táto premenná môže byť konkurentne upravovaná funkciou clockintr(), spomenuté dve funkcie musia pred prečítaním premennej ticks získať zámok tickslock. Vďaka tomu nemôže funkcia clockintr() konkurentne upravovať premennú ticks, ale zároveň viacero jadier nemôže čítať premennú ticks naraz, čo by bolo v poriadku (konkurentné čítanie hodnotu nemodifikuje). Pri čítaní je teda spinlock zbytočný a znižuje priepustnosť systému.
Štandardné riešenie tohto problému je použitie read-write zámku. Read-write zámky rozlišujú dva druhy držiteľov zámku: čitateľov a zapisovateľov. Zámok môže držať naraz najviac jeden zapisovateľ (ak ho drží zapisovateľ, čitateľ ho nemôže získať), ale ľubovoľný počet čitateľov (ak ho nedrží zapisovateľ). Typické rozhranie read-write zámku vyzerá takto (pozri kernel/defs.h):
|
1 2 3 4 5 |
void initrwlock(struct rwspinlock*); void read_acquire(struct rwspinlock*); void read_release(struct rwspinlock*); void write_acquire(struct rwspinlock*); void write_release(struct rwspinlock*); |
Jeden nepatrný problém, ku ktorému pri read-write zámkoch dochádza je, že ak jeden zámok drží veľa čitateľov, zapisovatelia sa k zámku nikdy nemusia dostať. Inými slovami, aj napriek tomu, že čitatelia získavajú a uvoľňujú zámok, nikdy nenastane situácia, pri ktorej zámok nedrží ani jeden čitateľ. Zapisovateľ teda nikdy nemôže získať zámok. Na vyriešenie tohto problému read-write zámky obvykle implementujú schému priority zapisovateľov: akonáhle sa zapisovateľ pokúsi získať zámok, nasledujúci čitatelia musia počkať, až kým zapisovateľ získa a uvoľní zámok (samozrejme, pred tým musí počkať, kým všetci aktuálni čitatelia uvoľnia zámok).
Implementujte read-write spinlock pre xv6 podľa rozhrania a sémantiky popísanej vyššie. Make sure that readers do not starve writers: if there’s any pending writers, no more readers can acquire the lock.
Vyplňte útržky funkcií rozhrania pre read-write spinlock v súbore kernel/spinlock.c a upravte definíciu štruktúry struct rwspinlock v súbore kernel/spinlock.h.
Implementáciu otestujte spustením testu rwlktest. Mali by ste dostať podobný výstup:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
$ <kbd class="toolbar-overlay:false">rwlktest</kbd> rwspinlock_test: step 1 rwspinlock_test: step 2 rwspinlock_test: step 3 rwspinlock_test: step 4 rwspinlock_test: step 5 rwspinlock_test: step 6 rwspinlock_test: step 7 rwspinlock_test(0): 0 rwspinlock_test(2): 0 rwspinlock_test(1): 0 rwlktest: passed 3/3 $ |
Skontrolujte tiež, či usertests -q prejdú. Po dokončení úlohy by mali prejsť všetky testy make grade.
Pomôcky:
sys_rwlktest() v súbore kernel/spinlock.c; implementáciu by ste mali byť schopní overiť priebežne po krokoch.acquire() a release() v write/read_acquire_inner a write/read_release_inner musíte nahradiť vašou vlastnou implementáciou. Spustite príkaz make grade, aby ste overili správnosť svojho riešenia. Po úspešnom dokončení úlohy nezabudnite vytvoriť commit! 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 aj túto zmenu commitnite do repozitára. Týmto je cvičenie ukončené.
Nie je 🙁