6. 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 invalidný 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. Príkladom je lenivá alokácia z predchádzajúceho cvičenia. 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() hneď po forku. exec() uvoľní všetky ťažko nakopírované stránky, bez toho, aby nejakú použil. Treba však mať neustále na pamäti, že až vtedy, ak by rodič či dieťa chceli zapísať do spoločnej stránky, až potom je potrebné urobiť kópiu údajov, ktoré sa v nej nachádzajú.

Riešenie

Cieľom 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é ako nezapisovateľné. 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 systém 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 so zapisovateľným príznakom PTE_W. Po návrate z obsluhy výpadku bude môcť takto 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.

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

Vašou úlohou je implementovať copy-on-write fork pre jadro xv6. Korektnosť implementácie môžete overiť programami cowtest a usertests.

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. 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.
  2. Modifikujte funkciu usertrap()tak, aby rozoznala výpadky stránok. Ak nastane výpadok stránky na COW stránke, 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.
  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. Na predchádzajúcom cvičení ste sa oboznámili s kódom virtuálnej pamäte systému xv6. Toto cvičenie by ste ale nemali zakladať na lenivej alokácii. Namiesto toho začnite na vetve cow, ako bolo uvedené vyššie.
  2. 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).
  3. Program usertests preskúša situácie, ktoré cowtest netestuje. Nezabudnite preto skontrolovať oba testy.
  4. 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.
  5. 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 z minulého cvičenia.
  • 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ť.