Zámky

Na tomto cvičení získate skúsenosti s redizajnovaním kódu s cieľom zvýšiť paralelizmus. Častým symptómom slabého paralelizmu na viacjadrových strojoch je vysoké 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 znížené súperenie. Na tomto cvičení to urobíte pre nový pamäťový alokátor v xv6 a cache blokov.

Pred písaním kódu sa uistite, že ste si prečítali kapitolu 4 Locking z knižky xv6, preštudovali príslušný kód a prepli vetvu v repozitári:

  $ git fetch
  $ git checkout lock

1 2	$ git fetch $ git checkout lock

Pamäťový alokátor

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 vypíše počet inštrukcií test-and-set, ktoré zlyhali pri získavaní zámku kmem (a ešte nejakých iných zámkov), čo nám poskytuje približnú mieru súperenia o zámky:

$ kalloctest
start test0
test0 results:
=== lock kmem/bcache stats
lock: kmem: #test-and-set 161724 #acquire() 433008
lock: bcache: #test-and-set 0 #acquire() 812
=== top 5 contended locks:
lock: kmem: #test-and-set 161724 #acquire() 433008
lock: proc: #test-and-set 290 #acquire() 961
lock: proc: #test-and-set 240 #acquire() 962
lock: proc: #test-and-set 72 #acquire() 907
lock: proc: #test-and-set 68 #acquire() 907
test0 FAIL
start test1
total allocated number of pages: 200000 (out of 32768)
test1 OK

$ kalloctest

start test0

test0 results:

=== lock kmem/bcache stats

lock: kmem: #test-and-set 161724 #acquire() 433008

lock: bcache: #test-and-set 0 #acquire() 812

=== top 5 contended locks:

lock: kmem: #test-and-set 161724 #acquire() 433008

lock: proc: #test-and-set 290 #acquire() 961

lock: proc: #test-and-set 240 #acquire() 962

lock: proc: #test-and-set 72 #acquire() 907

lock: proc: #test-and-set 68 #acquire() 907

test0 FAIL

start test1

total allocated number of pages: 200000 (out of 32768)

test1 OK

acquire() si pre každý zámok ukladá počet jej volaní a počet inštrukcií test-and-set, ktoré zámok neuzamkli. kalloctest zavolá systémové volanie, ktoré vypíše tieto počty pre zámky kmem a bcache (o ktoré sa v tomto cvičení zaujímame) a pre 5 najviac zaťažených zámkov. Ak nastáva súperenie o zámky, počet inštrukcií test-and-set bude vysoký, pretože táto inštrukcia je volaná v cykle veľakrát, kým sa zámok neuvoľní. Systémové volanie vracia celkový počet inštrukcií test-and-set 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. Počítač na cloude má 4 jadrá. 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 a zámok. 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.

Vašou úlohou je implementovať zoznamy voľných stránok pre každé CPU a proces kradnutia, keď nejaké CPU minie všetky svoje stránky. Spustením kalloctestu môžete zistiť, či vaša implementácia zmiernila súperenie o zámky a či je možné alokovať celú fyzickú pamäť. Výstup by mal vyzerať podobne ako nižšie, ale kokrétne čísla sa môžu líšiť. Skontrolujte tiež to, či prejdete usertestami.

$ kalloctest
start test0
test0 results:
=== lock kmem/bcache stats
lock: kmem: #test-and-set 0 #acquire() 33167
lock: kmem: #test-and-set 0 #acquire() 200114
lock: kmem: #test-and-set 0 #acquire() 199752
lock: bcache: #test-and-set 0 #acquire() 28
=== top 5 contended locks:
lock: proc: #test-and-set 22303 #acquire() 180082
lock: proc: #test-and-set 4162 #acquire() 180130
lock: proc: #test-and-set 4115 #acquire() 180129
lock: proc: #test-and-set 342 #acquire() 180070
lock: proc: #test-and-set 39 #acquire() 180070
test0 OK
start test1
total allocated number of pages: 200000 (out of 32768)
test1 OK
$
$ usertests
...
ALL TESTS PASSED
$

$ kalloctest

start test0

test0 results:

=== lock kmem/bcache stats

lock: kmem: #test-and-set 0 #acquire() 33167

lock: kmem: #test-and-set 0 #acquire() 200114

lock: kmem: #test-and-set 0 #acquire() 199752

lock: bcache: #test-and-set 0 #acquire() 28

=== top 5 contended locks:

lock: proc: #test-and-set 22303 #acquire() 180082

lock: proc: #test-and-set 4162 #acquire() 180130

lock: proc: #test-and-set 4115 #acquire() 180129

lock: proc: #test-and-set 342 #acquire() 180070

lock: proc: #test-and-set 39 #acquire() 180070

test0 OK

start test1

total allocated number of pages: 200000 (out of 32768)

test1 OK

$ usertests

...

ALL TESTS PASSED

Zámky v initlock() pomenujte s prefixom kmem. To znamená, že pre každý zámok musíte zavolať initlock() s menom, ktoré začína na kmem.

Pomôcky:

Použite konštantu NCPU definovanú v kernel/param.h
Nechajte freerange() dať všetku voľnú pamäť CPU, ktoré ju vykoná.
Funkcia cpuid() vracia číslo aktuálneho CPU, ale volať ju a použiť 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í

Cache bufferov

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:

$ bcachetest
start test0
test0 results:
=== lock kmem/bcache stats
lock: kmem: #test-and-set 0 #acquire() 33026
lock: kmem: #test-and-set 0 #acquire() 50
lock: kmem: #test-and-set 0 #acquire() 73
lock: bcache: #test-and-set 186438 #acquire() 65650
=== top 5 contended locks:
lock: bcache: #test-and-set 186438 #acquire() 65650
lock: proc: #test-and-set 52912 #acquire() 66921
lock: proc: #test-and-set 14693 #acquire() 66568
lock: proc: #test-and-set 13379 #acquire() 66568
lock: proc: #test-and-set 12117 #acquire() 66568
test0: FAIL
start test1
test1 OK

$ bcachetest

start test0

test0 results:

=== lock kmem/bcache stats

lock: kmem: #test-and-set 0 #acquire() 33026

lock: kmem: #test-and-set 0 #acquire() 50

lock: kmem: #test-and-set 0 #acquire() 73

lock: bcache: #test-and-set 186438 #acquire() 65650

=== top 5 contended locks:

lock: bcache: #test-and-set 186438 #acquire() 65650

lock: proc: #test-and-set 52912 #acquire() 66921

lock: proc: #test-and-set 14693 #acquire() 66568

lock: proc: #test-and-set 13379 #acquire() 66568

lock: proc: #test-and-set 12117 #acquire() 66568

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

Upravte cache blokov tak, aby sa počet inštrukcií test-and-set pre všetky zámky v bcache počas testu bcachetest blížil k nule. Celkový počet týchto inštrukcií 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ť podmienku, aby najviac jedna kópia bloku bola kešovaná. Keď to budete mať hotové, váš výstup by mal vyzerať podobne ako nižšie (nebude úplne identický). Nezabudnite skontrolovať usertesty.

$ bcachetest
start test0
test0 results:
=== lock kmem/bcache stats
lock: kmem: #test-and-set 0 #acquire() 32968
lock: kmem: #test-and-set 0 #acquire() 53
lock: kmem: #test-and-set 0 #acquire() 53
lock: bcache: #test-and-set 0 #acquire() 598
lock: bcache.bucket: #test-and-set 0 #acquire() 4139
lock: bcache.bucket: #test-and-set 0 #acquire() 4131
lock: bcache.bucket: #test-and-set 0 #acquire() 2360
lock: bcache.bucket: #test-and-set 0 #acquire() 4307
lock: bcache.bucket: #test-and-set 0 #acquire() 2419
lock: bcache.bucket: #test-and-set 0 #acquire() 4420
lock: bcache.bucket: #test-and-set 0 #acquire() 4934
lock: bcache.bucket: #test-and-set 18 #acquire() 8692
lock: bcache.bucket: #test-and-set 0 #acquire() 6457
lock: bcache.bucket: #test-and-set 0 #acquire() 6197
lock: bcache.bucket: #test-and-set 0 #acquire() 6191
lock: bcache.bucket: #test-and-set 0 #acquire() 6210
lock: bcache.bucket: #test-and-set 0 #acquire() 6198
=== top 5 contended locks:
lock: proc: #test-and-set 1113301 #acquire() 68753
lock: proc: #test-and-set 845107 #acquire() 68685
lock: proc: #test-and-set 822143 #acquire() 68685
lock: proc: #test-and-set 808826 #acquire() 68685
lock: proc: #test-and-set 664514 #acquire() 68727
test0: OK
start test1
test1 OK
$ usertests
  ...
ALL TESTS PASSED
$

$ bcachetest

start test0

test0 results:

=== lock kmem/bcache stats

lock: kmem: #test-and-set 0 #acquire() 32968

lock: kmem: #test-and-set 0 #acquire() 53

lock: bcache: #test-and-set 0 #acquire() 598

lock: bcache.bucket: #test-and-set 0 #acquire() 4139

lock: bcache.bucket: #test-and-set 0 #acquire() 4131

lock: bcache.bucket: #test-and-set 0 #acquire() 2360

lock: bcache.bucket: #test-and-set 0 #acquire() 4307

lock: bcache.bucket: #test-and-set 0 #acquire() 2419

lock: bcache.bucket: #test-and-set 0 #acquire() 4420

lock: bcache.bucket: #test-and-set 0 #acquire() 4934

lock: bcache.bucket: #test-and-set 18 #acquire() 8692

lock: bcache.bucket: #test-and-set 0 #acquire() 6457

lock: bcache.bucket: #test-and-set 0 #acquire() 6197

lock: bcache.bucket: #test-and-set 0 #acquire() 6191

lock: bcache.bucket: #test-and-set 0 #acquire() 6210

lock: bcache.bucket: #test-and-set 0 #acquire() 6198

=== top 5 contended locks:

lock: proc: #test-and-set 1113301 #acquire() 68753

lock: proc: #test-and-set 845107 #acquire() 68685

lock: proc: #test-and-set 822143 #acquire() 68685

lock: proc: #test-and-set 808826 #acquire() 68685

lock: proc: #test-and-set 664514 #acquire() 68727

test0: OK

start test1

test1 OK

$ usertests

...

ALL TESTS PASSED

Zámky pomenujte s prefixom 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 hashovacej tabuľky, ktorá má jeden zámok na jeden hashovací bucket.

V týchto prípadoch je v poriadku, ak má vaše riešenie konflikty zámkov:

Keď dva procesy konkurentne používajú rovnaké číslo bloku. bcachetest test0 to nerobí.
Keď dva procesy konkurentne minú cache a musia nájsť voľný blok na výmenu. bcachetest test0 to nerobí
Keď dva procesy konkurentne používajú bloky, ktoré majú konflikt vo vašej schéme blokov a zámkov. Napríklad ak dva procesy používajú bloky, ktorých hashe padnú do rovnakého slotu v hashovacej tabuľke. bcachetest test0 to v závislosti od vášho návrhu môže urobiť, ale ideálne je, aby ste váš návrh nastavili tak, aby ste minimalizovali konflikty (napr. zmenou veľkosti hashovacej tabuľky).

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:

Prečítajte si popis blokovej cache v xv6 knižke (sekcia 7.2).
Môžete použiť fixný počet bucketov a hashovacia tabuľka nemusí dynamicky meniť veľkosť. Ako počet bucketov zvoľte prvočíslo (napr. 13) na zníženie pravdepodobnosti hashovacích konfliktov.
Vyhľadávanie buffera v hashovacej tabuľke a alokovanie záznamu pre tento buffer v prípade, ak buffer nebol nájdený musí byť atomická operácia.
Odstráňte zoznam všetkých bufferov (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.
Časť kódu v bget(), ktorá vyberie nový buffer na použitie, keď hľadaný buffer nie je v cache je možné serializovať.
Vaše riešenie bude musieť v niektorých prípadoch držať dva zámky; napríklad počas recyklácie buffera budete musieť držať zámok bcache a jeden zámok bucketu. Dávajte pozor na uviaznutie.
Keď nahrádzate blok, budete musieť presunúť struct buf z jedného bucketu do iného, pretože nový blok bude mať iný hash. Avšak dávajte pozor, nový blok sa môže mať rovnaký hash ako starý. Ošetrite uviaznutie v takom prípade.

Voliteľné:

Urobte vyhľadávanie blokov bez zámkov. Pomôcka: použite funkcie __sync_* z kompilátora gcc. Ako overíte, či je vaša implementácia korektná?

Spustite make grade na overenie, či váš kód prechádza všetkými testami.

Týmto je cvičenie ukončené. Teraz môžete urobiť commit svojich zmien do repozitára.

10. cvičenie – zámky ?

Zámky

Pamäťový alokátor

Cache bufferov