7. cvičenie – zámky

Zámky

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:

  • Kapitola 6: Locking a príslušný kód.
  • Sekcia 3.5: „Code: Physical memory allocator“
  • Sekcia 8.1 až 8.3: „Overview“, „Buffer cache layer“, a „Code: Buffer cache“

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.

Pamäťový alokátor (stredná)

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ť):

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.

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. Názvy zámkov, ktoré vytvoríte musia začínať na 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.

Pomôcky:

  • Použite konštantu NCPU definovanú v kernel/param.h.
  • Funkcia freerange() môže prideliť všetku voľnú pamäť tomu CPU, ktoré ju zavolá.
  • Funkcia 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í.
  • Ak chcete nejakým spôsobom formátovať reťazce (pre názvy zámkov), pozrite sa do súboru kernel/sprintf.c. Nie je ale žiadny problém, ak všetky zámky pomenujete kmem.

Po úspešnom dokončení úlohy nezabudnite vytvoriť commit!

Cache bufferov (ťažká)

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:

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

Upravte cache blokov tak, aby sa počet 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.

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:

  • Keď dva procesy konkurentne používajú rovnaké číslo bloku. bcachetest test0 to nerobí.
  • Keď dva procesy konkurentne minú cache (hľadaný blok v nej nenájdu) 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 haše padnú do rovnakého bucketu v hašovacej 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 hašovacej 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 8.1 – 8.3).
  • Môžete použiť fixný počet bucketov a hašovacia tabuľka nemusí dynamicky meniť veľkosť. Ako počet bucketov zvoľte prvočíslo (napr. 13) na zníženie pravdepodobnosti hašovacích konfliktov.
  • Vyhľadávanie buffera v hašovacej 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 bucket. 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ý haš. Avšak dávajte pozor, nový blok môže mať rovnaký haš ako starý. Ošetrite uviaznutie v takom prípade.
  • Počas implementácie sa vám môže stať, že chybným kódom porušíte integritu súborového systému. Ak vidíte zvláštne chyby, urobte make clean pre obnovenie súborového systému.
  • Tipy na ladenie: implementujte zámky bucketov, ale zamknutie a odomknutie globálneho zámku 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é.

Voliteľná úloha

  • 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á?