5. cvičenie – copy on write fork

Copy-on-write fork pre xv6

Virtuálna pamäť umožňuje implementovať určitý spôsob presmerovania prístupu k dátam. Ak jadro označí PTE ako neplatný alebo iba na čítanie, prístup k danej stránke spôsobí výpadok stránky a jadro môže rozhodnúť, čo tento prístup znamená.

V počítačových systémoch existuje porekadlo, ktoré hovorí, že akýkoľvek systémový problém je možné vyriešiť presmerovaním. V tomto cvičení sa pozrieme na ďalší príklad – copy-on write fork.

Pred začiatkom práce prepnite repozitár do vetvy cow:

Problém

Systémové volanie fork() v xv6 kopíruje celý adresný priestor rodiča do priestoru potomka. Ak je adresný priestor rodiča veľký, kopírovanie môže trvať dlho (relatívne k rýchlosti procesora). Naviac sa týmto tiež zbytočne plytvá pamäťou – niektoré stránky nemodifikuje ani rodič, ani potomok. To znamená, že by mohli byť spoločné pre oba procesy. Najlepším príkladom neefektívnosti takéhoto kopírovania je volanie exec() v detskom procese, ktoré obvykle nasleduje hneď po forku. exec() uvoľní všetky ťažko nakopírované stránky zvyčajne bez toho, aby nejakú použil. Kopírovať stránku by sme v ideálnom prípade mali až vtedy, ak ju zdieľajú rodič aj dieťa a aspoň jeden chce do nej zapisovať.

Riešenie

Cieľom vašej implementácie copy-on-write (COW) forku je odložiť alokáciu a kopírovanie fyzickej pamäte pre detský proces, až kým kópie nie sú skutočne potrebné (t. j. buď rodič a/alebo dieťa sa pokúsi o zápis do spoločnej stránky).

COW fork() vytvorí iba tabuľku stránok pre detský proces. Záznamy v tabuľke (PTE) budú ukazovať na fyzické stránky (údaje v RAM) rodičovského procesu. Zároveň záznamy v tabuľke stránok oboch procesov budú označené iba na čítanie. Ak sa jeden z procesov pokúsi zapísať niečo do COW stránky, CPU vynúti výpadok stránky. Obsluha výpadkov stránky v jadre tento výpadok zachytí, alokuje stránku fyzickej pamäte pre proces, ktorý spôsobil výpadok, skopíruje obsah pôvodnej (spoločnej) stránky do novej stránky a upraví súvisiace záznamy v tabuľke stránok, aby ukazovali na novú stránku s príznakom PTE_W, ktorý umožní zapisovanie. Po návrate z obsluhy výpadku bude môcť užívateľský proces pokračovať v zápise do vlastnej kópie stránky.

Uvoľňovanie fyzických stránok procesov bude pri COW forku o niečo zložitejšie. Jedna fyzická stránka môže byť namapovaná vo viacerých procesoch. Uvoľnená by mala byť až po zániku poslednej referencie, teda keď ju odmapuje posledný proces, ktorý ju používa. V jednoduchom jadre, ako xv6, nie je zložité udržať informáciu o procesoch, v ktorých je namapovaná nejaká stránka. V produkčných jadrách to už môže byť náročnejšia úloha. Prečítajte si článok o tom, ako to robia v Linuxe: Patching until the COWs come home.

Implementácia copy-on write forku (ťažká)

Na otestovanie vašej implementácie môžete použiť program cowtest (jeho zdrojový súbor nájdete v user/cowtest.c). cowtest obsahuje niekoľko testov, na neupravenom kóde xv6 zlyhá hneď prvý test. Takto to vyzerá:

Test simple alokuje viac ako polovicu dostupnej fyzickej pamäte a potom zavolá fork(). Fork zlyhá, pretože nie je miesto na skopírovanie celého adresného priestoru rodiča.

Implementácia je korektná, ak úspešne prebehnú programy cowtest a usertests -q. Takto by to malo vyzerať:

Postupovať by ste mali takto:

1. Modifikujte funkciu uvmcopy()tak, aby namapovala fyzické stránky rodiča do dieťaťa namiesto alokácie nových stránok. Aj v rodičovi, aj v potomkovi vynulujte príznak PTE_W stránkam, ktoré ho majú nastavený.
2. Modifikujte funkciu usertrap()tak, aby rozoznala výpadky stránok. Ak pri zapisovaní nastane výpadok stránky na COW stránke, ktorá bola pôvodne zapisovateľná, alokujte novú stránku pomocou kalloc(), skopírujte obsah starej stránky do novej stránky a namapujte novú stránku do adresného priestoru procesu, ktorý výpadok spôsobil s nastaveným príznakom PTE_W. Stránky, ktoré boli pôvodne mapované len na čítanie (nemali nastavený príznak PTE_W, napríklad stránky zo segmentu text) by mali byť zdieľané medzi rodičom a potomkom len na čítanie. Ak sa rodič alebo potomok pokúsi zapisovať do takejto stránky, musí byť ukončený.
3. Ďalej zabezpečte, aby každá fyzická stránka bola uvoľnená až vtedy, keď je uvoľnená posledná PTE referencia (ale nie predtým, to by bolo pre procesy využívajúce danú stránku trochu posmutnejšie!). Pozrite sa do kalloc.c a pouvažujte, či by sa tam nehodilo implementovať počítanie referencií.
4. Na záver upravte copyout()tak, aby používal vyššie popísanú schému pri výpadku stránky COW.

Pomôcky:

1. Pre každý PTE môže byť užitočné uložiť si, či sa jedná o COW mapovanie. Môžete na to použiť RSW (reserved for software) bity v PTE (viď RISC-V špecifikácia).
2. Príkazom usertests -q môžete preskúšať situácie, ktoré cowtest netestuje. Nezabudnite preto skontrolovať výsledok oboch testov.
3. Na konci súboru kernel/riscv.h nájdete užitočné makrá a definície týkajúce sa príznakov tabuliek stránok.
4. Ak nastane COW výpadok stránky a nie je k dispozícii žiadna voľná pamäť, proces by mal byť ukončený.

Spustite príkaz make grade, aby ste overili správnosť svojho riešenia. 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.

Týmto je cvičenie ukončené. Svoje zmeny môžete commitnúť do repozitára.

Voliteľné úlohy

• Skombinujte COW s lenivou alokáciou.
• Odmerajte, o koľko bajtov menej xv6 nakopíruje a o koľko menej fyzických stránok alokuje pri COW implementácii. Nájdite a využite spôsob, ako tieto počty ešte zmenšiť.