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 # alebo git checkout lock $ make clean |
Riešenia úloh z tohto cvičenia ukladajte do vetvy lock. Túto vetvu budeme kontrolovať v rámci priebežnej kontroly repozitárov. Viac informácií k hodnoteniu repozitárov nájdete na príslušnej stránke.
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 (#fetch-and-add). 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 dokončení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 |
$ <kbd>kalloctest</kbd> start test1 test1 results: --- lock kmem/bcache stats lock: kmem: #fetch-and-add 83375 #acquire() 433015 lock: bcache: #fetch-and-add 0 #acquire() 1260 --- top 5 contended locks: lock: kmem: #fetch-and-add 83375 #acquire() 433015 lock: proc: #fetch-and-add 23737 #acquire() 130718 lock: virtio_disk: #fetch-and-add 11159 #acquire() 114 lock: proc: #fetch-and-add 5937 #acquire() 130786 lock: proc: #fetch-and-add 4080 #acquire() 130786 tot= 83375 test1 FAIL |
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. 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 |
$ kalloctest start test1 test1 results: --- lock kmem/bcache stats lock: kmem: #fetch-and-add 0 #acquire() 42843 lock: kmem: #fetch-and-add 0 #acquire() 198674 lock: kmem: #fetch-and-add 0 #acquire() 191534 lock: bcache: #fetch-and-add 0 #acquire() 1242 --- top 5 contended locks: lock: proc: #fetch-and-add 43861 #acquire() 117281 lock: virtio_disk: #fetch-and-add 5347 #acquire() 114 lock: proc: #fetch-and-add 4856 #acquire() 117312 lock: proc: #fetch-and-add 4168 #acquire() 117316 lock: proc: #fetch-and-add 2797 #acquire() 117266 tot= 0 test1 OK start test2 total free number of pages: 32499 (out of 32768) ..... test2 OK $ usertests sbrkmuch usertests starting test sbrkmuch: OK ALL TESTS PASSED $ usertests ... 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.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: #fetch-and-add 0 #acquire() 33035 lock: bcache: #fetch-and-add 16142 #acquire() 65978 --- top 5 contended locks: lock: virtio_disk: #fetch-and-add 162870 #acquire() 1188 lock: proc: #fetch-and-add 51936 #acquire() 73732 lock: bcache: #fetch-and-add 16142 #acquire() 65978 lock: uart: #fetch-and-add 7505 #acquire() 117 lock: proc: #fetch-and-add 6937 #acquire() 73420 tot= 16142 test0: FAIL start test1 test1 OK |
Váš výstup bude pravdepodobne odlišný, ale počet cyklov 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. 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: #fetch-and-add 0 #acquire() 32954 lock: kmem: #fetch-and-add 0 #acquire() 75 lock: kmem: #fetch-and-add 0 #acquire() 73 lock: bcache: #fetch-and-add 0 #acquire() 85 lock: bcache.bucket: #fetch-and-add 0 #acquire() 4159 lock: bcache.bucket: #fetch-and-add 0 #acquire() 2118 lock: bcache.bucket: #fetch-and-add 0 #acquire() 4274 lock: bcache.bucket: #fetch-and-add 0 #acquire() 4326 lock: bcache.bucket: #fetch-and-add 0 #acquire() 6334 lock: bcache.bucket: #fetch-and-add 0 #acquire() 6321 lock: bcache.bucket: #fetch-and-add 0 #acquire() 6704 lock: bcache.bucket: #fetch-and-add 0 #acquire() 6696 lock: bcache.bucket: #fetch-and-add 0 #acquire() 7757 lock: bcache.bucket: #fetch-and-add 0 #acquire() 6199 lock: bcache.bucket: #fetch-and-add 0 #acquire() 4136 lock: bcache.bucket: #fetch-and-add 0 #acquire() 4136 lock: bcache.bucket: #fetch-and-add 0 #acquire() 2123 --- top 5 contended locks: lock: virtio_disk: #fetch-and-add 158235 #acquire() 1193 lock: proc: #fetch-and-add 117563 #acquire() 3708493 lock: proc: #fetch-and-add 65921 #acquire() 3710254 lock: proc: #fetch-and-add 44090 #acquire() 3708607 lock: proc: #fetch-and-add 43252 #acquire() 3708521 tot= 128 test0: OK start test1 test1 OK $ usertests ... 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 buffery 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 namiesto neho označujte buffery časom ich posledného použitia (použite ticks z kernel/trap.c). S touto zmenou brelse() nemusí získať zámok bcache a bget() môže vybrať najdávnejšie použitý blok vďaka časovým pečiatkam.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é.
__sync_* z kompilátora gcc. Ako overíte, či je vaša implementácia korektná?