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:
|
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 |
$ <kbd>kalloctest</kbd> start test1 test1 results: --- lock kmem/bcache stats lock: kmem: #test-and-set 83375 #acquire() 433015 lock: bcache: #test-and-set 0 #acquire() 1260 --- top 5 contended locks: lock: kmem: #test-and-set 83375 #acquire() 433015 lock: proc: #test-and-set 23737 #acquire() 130718 lock: virtio_disk: #test-and-set 11159 #acquire() 114 lock: proc: #test-and-set 5937 #acquire() 130786 lock: proc: #test-and-set 4080 #acquire() 130786 tot= 83375 test1 FAIL start test2 total free number of pages: 32497 (out of 32768) ..... test2 OK start test3 child done 1 child done 100000 test3 OK start test2 total free number of pages: 32497 (out of 32768) ..... test2 OK start test3 child done 1 child done 100000 test3 OK |
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 |
$ kalloctest start test1 test1 results: --- lock kmem/bcache stats lock: kmem: #test-and-set 0 #acquire() 42843 lock: kmem: #test-and-set 0 #acquire() 198674 lock: kmem: #test-and-set 0 #acquire() 191534 lock: bcache: #test-and-set 0 #acquire() 1242 --- top 5 contended locks: lock: proc: #test-and-set 43861 #acquire() 117281 lock: virtio_disk: #test-and-set 5347 #acquire() 114 lock: proc: #test-and-set 4856 #acquire() 117312 lock: proc: #test-and-set 4168 #acquire() 117316 lock: proc: #test-and-set 2797 #acquire() 117266 tot= 0 test1 OK start test2 total free number of pages: 32499 (out of 32768) ..... test2 OK start test3 child done 1 child done 100000 test3 OK $ usertests sbrkmuch usertests starting test sbrkmuch: OK ALL TESTS PASSED $ usertests -q ... 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. Môžete začať pracovať na tejto úlohe bez toho, aby ste mali hotovú prvú úlohu.
Ak viacero procesov intenzívne používa súborový systém, budú pravdepodobne súperiť o zámok bcache.lock, ktorý chráni cache blokov disku v kernel/bio.c. bcachetest vytvorí niekoľko procesov, ktoré opakovane čítajú rôzne súbory, čo spôsobí súperenie o zámok bcache.lock; jeho výstup (pred dokončením cvičenia) vyzerá takto:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
$ bcachetest start test0 test0 results: --- lock kmem/bcache stats lock: kmem: #test-and-set 0 #acquire() 33035 lock: bcache: #test-and-set 16142 #acquire() 65978 --- top 5 contended locks: lock: virtio_disk: #test-and-set 162870 #acquire() 1188 lock: proc: #test-and-set 51936 #acquire() 73732 lock: bcache: #test-and-set 16142 #acquire() 65978 lock: uart: #test-and-set 7505 #acquire() 117 lock: proc: #test-and-set 6937 #acquire() 73420 tot= 16142 test0: FAIL start test1 test1 OK |
Váš výstup bude pravdepodobne odlišný, ale počet inštrukcií test-and-set pre zámok bcache bude veľký. Ak sa pozriete na kód v kernel/bio.c, uvidíte, že bcache.lock chráni zoznam kešovaných blokových bufferov, počet referencií (b->refcnt) v každom blokovom bufferi a identity kešovaných blokov (b->dev and b->blockno).
acquire cyklov pre všetky zámky v bcache počas testu bcachetest blížil k nule. Celkový súčet cyklov pre všetky zámky by mal byť ideálne nulový, ale nám stačí ak sa bude pohybovať pod 500. Modifikujte bget() a brelse(), aby konkurentné vyhľadávanie a uvoľňovanie rôznych blokov z bcache spôsobilo konflikt zámkov len pri veľmi malom počte prípadov (nie všetky musia čakať na bcache.lock). Musíte dodržať invariant, aby najviac jedna kópia bloku bola kešovaná. Keď budete mať úlohu hotovú, váš výstup by mal vyzerať podobne ako nižšie (nebude úplne identický). Nezabudnite skontrolovať usertests -q. V make grade by mali prejsť všetky testy.
|
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 |
$ bcachetest start test0 test0 results: --- lock kmem/bcache stats lock: kmem: #test-and-set 0 #acquire() 32954 lock: kmem: #test-and-set 0 #acquire() 75 lock: kmem: #test-and-set 0 #acquire() 73 lock: bcache: #test-and-set 0 #acquire() 85 lock: bcache.bucket: #test-and-set 0 #acquire() 4159 lock: bcache.bucket: #test-and-set 0 #acquire() 2118 lock: bcache.bucket: #test-and-set 0 #acquire() 4274 lock: bcache.bucket: #test-and-set 0 #acquire() 4326 lock: bcache.bucket: #test-and-set 0 #acquire() 6334 lock: bcache.bucket: #test-and-set 0 #acquire() 6321 lock: bcache.bucket: #test-and-set 0 #acquire() 6704 lock: bcache.bucket: #test-and-set 0 #acquire() 6696 lock: bcache.bucket: #test-and-set 0 #acquire() 7757 lock: bcache.bucket: #test-and-set 0 #acquire() 6199 lock: bcache.bucket: #test-and-set 0 #acquire() 4136 lock: bcache.bucket: #test-and-set 0 #acquire() 4136 lock: bcache.bucket: #test-and-set 0 #acquire() 2123 --- top 5 contended locks: lock: virtio_disk: #test-and-set 158235 #acquire() 1193 lock: proc: #test-and-set 117563 #acquire() 3708493 lock: proc: #test-and-set 65921 #acquire() 3710254 lock: proc: #test-and-set 44090 #acquire() 3708607 lock: proc: #test-and-set 43252 #acquire() 3708521 tot= 128 test0: OK start test1 test1 OK $ usertests -q ... ALL TESTS PASSED $ |
Zámky pomenujte s prefixom bcache. To znamená, že pre každý zámok musíte zavolať initlock() s menom, ktoré začína na bcache.
Zníženie súperenia o zámky v cache blokov je zložitejšie ako pre kalloc, pretože buffre bcache sú zdieľané medzi procesmi (teda zároveň aj CPU). Pre kalloc ste súperenie eliminovali vlastným alokátorom pre každé CPU. Avšak toto nebude fungovať pre cache blokov. Odporúčame vám vyhľadať čísla blokov v keške pomocou hašovacej tabuľky, ktorá má jeden zámok na jeden hašovací bucket.
V týchto prípadoch je v poriadku, ak má vaše riešenie konflikty zámkov:
bcachetest test1 používa viac blokov ako je k dispozícii bufferov, čo preverí väčšie množstvo kódu súborového systému.
Pomôcky:
bcache.head atď.) a neimplementujte LRU (least recently used). S touto zmenou brelse() nemusí získať zámok bcache. Vo funkcii bget() môžete vybrať ľubovoľný blok, ktorého refcnt == 0, namiesto najdávnejšie použitého bloku.bget môžete (t. j. časť funkcie bget, ktorá vyberá buffer na recykláciu, ak vyhľadávanie v keške bolo neúspešné).bget(), ktorá vyberie nový buffer na použitie, keď hľadaný buffer nie je v cache je možné serializovať.bcache a jeden zámok bucket. Dávajte pozor na uviaznutie.struct buf z jedného bucketu do iného, pretože nový blok bude mať iný haš. Avšak dávajte pozor, nový blok môže mať rovnaký haš ako starý. Ošetrite uviaznutie v takom prípade.bcache.lock nechajte na začiatku/konci funkcie bget, aby bol kód dočasne serializovaný. Keď ste si istí, že kód beží správne bez žiadnych súbehov, odstráňte globálne zámky a overte funkcionalitu. Hodiť sa vám tiež môže beh na jednom jadre pomocou make CPUS=1 qemu.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é.
Prvý riešiteľ úlohy môže dostať bonusové body po kontrole riešenia. Informujte sa u prednášajúceho alebo cvičiaceho. Voliteľnú úlohú môžete riešiť až po vyriešení všetkých úloh základnej časti cvičenia! Riešenia prijímame iba do 26.11.2023.
__sync_* z kompilátora gcc. Ako overíte, či je vaša implementácia korektná?