5. cvičenie – lenivá alokácia

Lenivá alokácia stránok v xv6

Programátori OS dokážu robiť všelijaké triky s pamäťovým hardvérom. Príkladom je lenivá alokácia na halde pre užívateľské programy. Aplikácie na xv6 si môžu vypýtať pamäť na halde od operačného systému pomocou systémového volania sbrk(). V jadre, ktoré vyvíjate, sbrk() alokuje fyzickú pamäť požadovanej veľkosti a namapuje ju do virtuálneho adresného priestoru procesu. Existujú však programy, ktoré takýmto spôsobom alokujú veľké množstvo pamäte, a takáto alokácia môže trvať dlhý čas. Napríklad pre jeden gigabajt je potrebné alokovať 262 144 stránok pamäte s veľkosťou 4 kB. Aj keď je alokácia jednej stránky relatívne rýchla, pri takomto veľkom počte alokovaných stránok je dĺžka tejto operácie nezanedbateľná. Naviac, niektoré programy alokujú pamäť, ktorú celú nikdy nepoužijú – napr. riedke polia (polia, v ktorých má väčšina prvkov nulovú hodnotu) alebo alokujú pamäť veľmi skoro pred jej samotným použitím. Sofistikované jadrá pre tento prípad alokujú pamäť lenivo. To znamená, že sbrk() nealokuje fyzickú pamäť – iba si zapamätá adresný rozsah, na ktorom proces očakáva alokovanú pamäť na halde. Keď proces prvýkrát pristúpi k stránke v tomto rozsahu, CPU vyvolá výpadok stránky, ktorý jadro obslúži alokáciou fyzickej pamäte, jej vynulovaním a a namapovaním. V tomto cvičení sa budeme venovať implementácii tohto mechanizmu do xv6.

Než sa vrhnete do programovania, prečítajte si štvrtú kapitolu z knižky o xv6 a súbory, ktoré budete upravovať:

  • kernel/trap.c
  • kernel/vm.c
  • kernel/sysproc.c

Začneme prepnutím repozitára do vetvy lazy.

Odstránenie alokácie v sbrk() (ľahká)

Vašou prvou úlohou je odstrániť alokáciu v systémovom volaní sbrk(n). Jeho implementáciu sys_sbrk() nájdete v súbore sysproc.c. Systémové volanie sbrk(n) zväčší pamäť procesu o n bajtov a vráti smerník na začiatok alokovaného regiónu (pôvodnú veľkosť, ak pamäť počítame od nuly). Vaša nová implementácia sbrk(n) iba navýši počítadlo veľkosti procesu (myproc()->sz) o n a vráti pôvodnú veľkosť. Novú pamäť nebude alokovať – volanie growproc() musíte odstrániť (ale veľkosť procesu musíte aj tak zvýšiť!).

Teraz si skúste tipnúť, čo sa stane, ak po tejto modifikácii naštartujeme systém. Čo sa pokazí?

Ukončite stávky prosím!

Naštartujte xv6, do shellu napíšte echo hi. Mali by ste uvidieť niečo takéto:

Správa usertrap(): … pochádza z obsluhy užívateľských výnimiek v trap.c. Ďalej vidíme, že takýto druh výnimky obsluha nepozná (unexpected scause). Uistite sa, že rozumiete, prečo došlo k výpadku stránky. Hodnota stval=0x0..04008 nám napríklad hovorí, že virtuálna adresa, ktorá spôsobila výnimku je 0x4008.

Lenivá alokácia (stredná)

Upravte kód v trap.c, aby obslúžil výpadok stránky z užívateľského priestoru namapovaním novo-alokovanej stránky fyzickej pamäte na adresu výpadku. Po obsluhe zabezpečte návrat do užívateľského priestoru, aby mohol proces pokračovať vo vykonávaní. Obsluhu by ste mali napísať pred volaním printf, ktoré spôsobilo vyššie uvedený výpis. Upravte zvyšok kódu jadra, aby ste mohli spustiť echo hi.

Pomôcky:

  • Výnimka je výpadok stránky vtedy, ak z funkcie usertrap() zavoláte r_scause() a tá vám vráti 13 alebo 15.
  • r_stval() vráti register stval, ktorý obsahuje virtuálnu adresu, ktorá spôsobila výpadok stránky.
  • Požičajte si (rozumej ukradnite) kód z funkcie uvmalloc() vo vm.c. Tento kód používa aj sbrk() (cez growproc()). V riešení zavoláte dve funkcie: kalloc() a mappages().
  • Nezabudnite zarovnať virtuálnu adresu nadol na najbližšiu hranicu stránky pomocou makra PGROUNDDOWN(va).
  • uvmunmap() bude panikáriť; modifikujte ju tak, aby nevyvolala panic, ak nejaké stránky nie sú namapované.
  • Ak jadro spadne, otvorte disassemblovaný kód jadra zo súboru kernel/kernel.asm a nájdite v ňom problémovú inštrukciu na adrese sepc.
  • Nezabudnite využiť funkciu na vypísanie tabuliek stránok, ktorú ste si napísali na treťom cvičení.
  • Ak vám kompilátor vypíše chybu incomplete type proc, includnite spinlock.h a za ním proc.h.

Ak všetko dopadlo dobre, mali by ste dosiahnuť stav, v ktorom viete spustiť echo hi. V shelli by mal nastať aspoň jeden alebo dva výpadky stránok (a po nich lenivá alokácia).

Lazytests a Usertests (stredná)

Užívateľský program lazytests dôsledne otestuje váš lenivý pamäťový alokátor. Opravte svoj kód tak, aby prešli všetky testy programov lazytests a usertests.

  • Obslúžte volania sbrk() so zápornými argumentami.
  • Ukončite proces, ktorý pristúpil k virtuálnej adrese vyššej ako tej, ktorú mal alokovanú pomocou sbrk().
  • Obslúžte volanie fork() korektne.
  • Ošetrite prípad, v ktorom proces použije validnú adresu z rozsahu od sbrk() v systémovom volaní read alebo write, ale pamäť pre danú oblasť ešte nebola alokovaná.
  • Ošetrite stav, v ktorom systém nemá voľnú pamäť: ak kalloc() zlyhá počas obsluhy výpadku stránky, ukončite aktuálny proces.
  • Ošetrite výpadky na neplatnej stránke pod zásobníkom.

Vaše riešenie je hotové, ak prejde testami lazytests a usertests:

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 lenivú alokáciu s jednoduchým copyin z tretieho cvičenia.