4. cvičenie – tabuľky stránok

Tabuľky stránok

V tomto cvičení preskúmate tabuľky stránok a upravíte ich za účelom implementácie funkcionalít, ktoré sú bežné v operačných systémoch.

Než začnete programovať, prečítajte si kapitolu 3 xv6 knižky a pozrite si príslušné súbory:

  • V kernel/memlayout.h je znázornené usporiadanie pamäte.
  • kernel/vm.c obsahuje väčšinu kódu, ktorý pracuje s virtuánou pamäťou (VM).
  • kernel/kalloc.c obsahuje kód na alokáciu a uvoľnovanie fyzickej pamäte.

Nápomocný môže byť tiež manuál privilegovaných inštrukcií RISC-V.

Synchronizácia s repozitárom

Od tohto cvičenia môžete pracovať na vlastných laptopoch. Predpokladáme, že ste si na nich už nastavili synchronizáciu s vaším vzdialených repozitárom na GitHube podľa sekcie Stiahnutie repozitára na vlastný PC na stránke Synchronizácia repozitára. Ak chcete pracovať s počítačmi v miestnosti, postupujte podľa sekcie Stiahnutie repozitára na cvičení.

Úvod do cvičenia

Najprv sa prepnite do vetvy pgtbl:

Riešenia úloh z tohto cvičenia ukladajte do vetvy pgtbl.

Tabuľka stránok používateľského procesu (ľahká)

Vašou prvou úlohou bude vysvetliť tabuľku stránok používateľského procesu, aby ste pochopili, ako fungujú tabuľky stránok na architektúre RISC-V.

Zavolajte make qemu a potom spustite používateľský program pgtbltest. Funkcia print_pgtbl vypíše záznamy tabuľky stránok (PTE) pre prvých 10 a posledných 10 stránok procesu pgtbltest použitím systémového volania pgpte, ktoré bolo pridané v tomto cvičení. Výstup vyzerá takto:

Vysvetlite každý vypísaný záznam. Zaujíma nás, čo stránka logicky obsahuje a aké má bity oprávnení. Pomôcť vám pri tom môže obrázok 3.4 v xv6 knižke. Dajte ale pozor, lebo skúmaný proces môže mať trochu iné rozloženie stránok ako na obrázku. Ešte pripomíname, že virtuálne stránky, ktoré idú za sebou v poradí, nemusia byť v rovnakom poradí vo fyzickej pamäti. Inými slovami, môžu byť náhodne rozmiestnené po celej fyzickej pamäti.

Zrýchlenie systémových volaní (ľahká)

Niektoré operačné systémy (napr. Linux) zrýchľujú určité systémové volania zdieľaním dát medzi jadrom a používateľským priestorom v pamäťovej oblasti s prístupom iba na čítanie. Vďaka tomu je možné eliminovať prechody do jadra počas systémových volaní. Aby ste sa naučili, ako fungujú pamäťové mapovania, vašou prvou úlohou je implementovať túto optimizáciu pre systémové volaniegetpid() v xv6.

Vždy, keď je vytvorený nový proces, namapujte jednu stránku na čítanie na adresu USYSCALL (táto virtuálna adresa je definovaná v súbore memlayout.h). Na začiatku tejto stránky uložte štruktúru struct usyscall (tiež definovaná v memlayout.h) a inicializujte ju tak, aby v nej bolo uložené PID aktuálneho procesu. Pre tento lab je z používateľského priestoru k dispozícii funkcia ugetpid(), ktorá automaticky použije mapovanie USYSCALL. Za implementáciu tejto úlohy získate plný počet bodov, ak prejdete testom ugetpid v súbore testov pgtbltest.

Pomôcky:

  • Nezabudnite alokovať a inicializovať stránku vo funkcii allocproc(). Vhodné je tiež niekam uložiť referenciu na alokovanú stránku, napríklad do štruktúry proc, podobne ako sa ukladá proc->trapframe a proc->pagetable.
  • Mapovanie môžete nastaviť vo funkcii proc_pagetable() v súbore kernel/proc.c.
  • Nastavte správne príznaky, aby bola stránka z používateľského priestoru len na čítanie.
  • Funkcia mappages() sa vám môže hodiť.
  • Nezabudnite stránku uvoľniť vo funkcii freeproc() a odmapovať v proc_freepagetable().

Ktoré iné systémové volania môžu byť urýchlené prostredníctvom tejto zdieľanej stránky? Vysvetlite ako.

Odpovede zapíšte do príslušných súborov podľa testovacieho skriptu.

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

Vypísanie tabuľky stránok (ľahká)

Vašou ďalšou úlohou je napísať funkciu, ktorá vypíše obsah tabuľky stránok. Pomôže vám to pri vizualizícii tabuliek stránok v RISC-V a funkciu môžete v budúcnosti použiť pri ladení systému.

Do xv6 bolo pridané systémové volanie kpgtbl(), ktoré volá funkciu vmprint() v súbore vm.c. Má jeden argument typu pagetable_t. Vašou úlohou je vypísať tabuľku stránok vo formáte, ktorý je uvedený nižšie.

Keď spustíte test print_kpgtbl(), vaša implementácia by mala vypísať takýto výstup:

V prvom riadku je argument funkcie vmprint. Potom nasledujú riadky pre každý PTE, vrátane vnorených záznamov. Každý riadok PTE je odsadený znakmi .. podľa toho, ako hboko v strome sa nachádza. Každý riadok obsahuje virtuálnu adresu, bity pte a fyzickú adresu vytiahnutú z PTE. Nevypisujte neplatné záznamy. V príklade vyššie má tabuľka najvyššej úrovne mapovania pre záznamy 0 a 255. O úroveň nižšie, záznam 0 má namapovaný len index 0. Na najnižšej úrovni má tento index namapovaných niekoľko záznamov.

Fyzické adresy na vašom počítači môžu byť odlišné od tých v ukážke výstupu. Počet záznamov a virtuálne adresy by mali byť rovnaké.

Pomôcky:

  • Použite makrá na konci súboru kernel/riscv.h.
  • Inšpirujte sa funkciou freewalk().
  • Použite formátovaciu značku %p na výpis PTE a adries ako 64-bitové hexadecimálne číslo.

Vysvetlite logický význam každej dátovej stránky, ktorú vypísala funkcia vmprint(). Ku každej takej stránke tiež uveďte jej prístupové bity a ako súvisí s výstupom print_pgtbl() z prvej úlohy. Pomôžte si obrázkom 3.4 z xv6 knižky. Tento obrázok ale nemusí presne reprezentovať proces, ktorého adresný priestor skúmame.

Odpovede zapíšte do príslušných súborov podľa testovacieho skriptu.

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

Použitie superstránok (ťažká)

Stránkovací hardvér architektúry RISC-V podporuje okrem 4096-bajtových stránok taktiež stránky s veľkosťou 2 MB. Väčšie stránky sa vo všeobecnosti označujú ako superstránky (superpages) a 2 MB stránky označujeme ako megastránky (lebo RISC-V podporuje viac veľkostí). Pre vytvorenie superstránky musí operačný systém splniť dve podmienky: bity PTE_V a PTE_R musia byť nastavené na jednotku v PTE na úrovni 1 a číslo fyzickej stránky musí ukazovať na stránku a adresou, ktorá je násobkom dvoch megabajtov. Viac sa dočítate v manuáli privilegovaných inštrukcií, ak vyhľadáte reťazce megapage a superpage, obzvlášť na vrchu strany 112.

Použitie superstránok znižuje spotrebu fyzických stránok na tabuľky stránok a znižuje počet neúspešných prístupov do TLB kešky. Pre niektoré programy to môže výrazne zvýšiť ich výkon.

Vašou úlohou je implementovať podporu superstránok do jadra xv6. Kernel by mal použiť superstránky, ak sú splnené tieto podmienky:

  • program zavolal sbrk() s veľkosťou väčšou alebo rovnou 2 MB,
  • novo vytvorený adresný rozsah obsahuje aspoň jednu alebo viac oblastí zarovnaných na 2 MB s veľkosťou 2 MB a viac.

Úlohu ste úspešne vyriešili, ak prejdete testovacím prípadom superpg_test programu pgtbltest.

Pomôcky:

  • Prečítajte si implementáciu superpg_test() v súbore user/pgtbltest.c.
  • Začnite vo funkcii sys_sbrk() v súbore kernel/sysproc.c, ktorá je zavolaná zo systémového volania sbrk. Sledujte postupnosť programovaného kódu až do funkcie, ktorá alokuje pamäť pre sbrk.
  • Jadro bude potrebovať alokovať a uvolňovať dvojmegabajtové regióny pamäte. Upravte kalloc.c a rezervujte si niekoľko dvojmegabajtových blokov fyzickej pamäte. V rovnakom súbore implementujte funkcie superalloc() a superfree(), ktoré budú vykonávať alokáciu a uvoľňovanie týchto blokov. Bude vám stačiť iba niekoľko dvojmegabajtových oblastí.
  • Superstránky musia byť alokované, keď proces so superstránkami vyvolá fork. Podobne musia byť aj uvoľnené, keď sa proces ukončí. Na splnenie týchto podmienok upravte funkcie uvmcopy() a uvmunmap().

Skutočné operačné systémy dynamicky konvertujú množinu bežných stránok na superstránku. Tento zdroj vysvetľuje, prečo je to dobrý nápad a čo je ťažké na zložitejšom návrhu:: Juan Navarro, Sitaram Iyer, Peter Druschel, and Alan Cox. Practical, transparent operating system support for superpages. SIGOPS Oper. Syst. Rev., 36(SI):89-104, December 2002.

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

Čas

Týmto je cvičenie hotové. Skontrolujte, či vaše riešenie prejde všetkými testami make grade. 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 nezabudnite aj túto zmenu commitnúť do repozitára.

Odpovede

Odpovede na otázky napíšte do súboru answers-pgtbl.txt. Nekontrolujeme ich, slúžia pre vás na pochopenie a opakovanie preberanej látky. Súbor commitnite do repozitára.

make grade môže zlyhať aj v prípade, že testy osamote zbehnú v poriadku. Je to spôsobené časovým limitom testov. Môžete ho zvýšiť v príslušnom súbore grade-lab-pgtbl (parametre timeout). Časový limit zmeňte iba v takom prípade, že viete, že samotný test zbehne v poriadku a nič iné v súbore neupravujte.

Pre úspešné testovanie je potrebné použiť aspoň 3 jadrá vo VirtualBoxe.

Voliteľné úlohy

Prvý riešiteľ každej úlohy môže dostať bonusové body po kontrole riešenia. Informujte sa u prednášajúceho alebo cvičiaceho. Voliteľné úlohy môžete riešiť až po vyriešení všetkých úloh základnej časti cvičenia! Riešenia prijímame iba do konca piateho týždňa semestra.

  • Vylepšite dizajn superstránok, aby pripomínal skutočné OS.
  • Odmapujte prvú stránku používateľského procesu, aby dereferencia nulového smerníka viedla k výpadku stránky. Musíte zmeniť súbor user.ld, aby používateľský segment text začínal napríklad na adrese 4096 namiesto 0.