Virtuální paměť

Teorie

Pokud vás tato tématika zajímá, doporučuji 7. přednášku BI-APS (Virtuální paměť). Je to tam vše hezky vysvětlené.

Virtuální paměť
(Screenshot z BI-APS / 7. přednáška / 14. slajd)

Formát jednoho řádku Page table (tzv. Page Table Entry - PTE)

  • Frame number/Číslo rámce = horní bity adresy
  • Přístupová práva:
    • R W X
    • User/Supervisor (uživatelský přístup nebo pouze OS)
    • Write-Through/Write-back (zapisovací strategie pro stránku)
    • Cache enabled/disabled
    • Accessed
    • Executable
    • Dirty
  • P: Presence bit (respektive v OSY "Present bit")
    • 1-> stránka je platná, je přítomná v hlavní paměti/RAM a v řádku PT je frame number/číslo rámce
    • 0-> Odpovídající stránka není v hlavní paměti

(Pro OSY: na řádce TLB je uložené číslo rámce, Presence/Reerence/Modify bit, access rights, cache disabled/enabled)

  • Konvenční stránkovací tabulka (page table):

    Každý proces běžíší v OS má vlastní stránkovací tabulku (resp. strom stránkovacích tabulek). Její počáteční adresa je součástí kontextu každého procesoru a je uložena v BTBR (není moc podstatné pro OSY, ale good to know). Tabulky můžou být několikaúrovňové (v testech se setkáte s jednoúrovňovou) - proces hledání stránky v několikaúrovňové Page Tables se nazývá Page (table) walk.

  • Inverzní stránkovací tabulka:

    Všechny procesy sdílejí jedinou inverzní stránkovací tabulku

  • TLB (Translation lookaside buffer)
    Zjednodušeně nehledáme rovnou v Page table, ale koukneme se na nacachované stránky. (Podobně jako u L1 - L3 u CPU)

TLB
(Screenshot z BI-APS / 7. přednáška / 25. slajd)

TLB Typicky obsahuje:

  • V: validity bit
  • Tag: číslo stránky
  • Frame number: číslo rámce
  • ASID: Identifikátor adresního prostoru (Address Space ID)
  • G: Global flag (pokud G = 1, pak se ASID ignoruje)
  • C: Cache policy
  • Access permissions: klasicky R W X

(Pro OSY: Valid bit, číslo stránky/rámce, ASID, Reference/Modify bit)

Vzorečky/"řešené" příklady:

Systém používá virtuální paměť se stránkováním. Velikost stránky/rámce je B, velikost logické adresy je bitů, velikost fyzické adresy je bitů. Systém používá TLB o velikosti položek (řádek). Na systému právě běží uživatelských procesů. Každému uživatelskému procesu je alokováno pouze na nejnižších adresách <nepodstatné> bytů pro kód a haldu a na nejvyšších adresách <nepodstatné> bytů pro zásobník. Pro náhradu stránek se používá algoritmus <taky nepodstatné :)>.

  1. Logická adresa se skládá z čísla stránky o velikosti bitů, offset je .
  2. Fyzická adresa se skládá z čísla rámce o velikosti bitů, offset je .
    • klasická tabulka stránek:

      Pro různě velké stránky je velikost offsetu různá.
      Offset definuje pozici dat uvnitř rámce
      Při překladu adresy se číslo stránky používá jako index do TLB

    • invertovaná tabulka stránek:

      Při překladu adresy lze použít rozptylovací funkci k urychlení překladu
      Pří překladu adresy hledáme číslo rámce, do kterého se stránka nahrála

    • klasická tabulka stránek:

      Jádro systému si musí pamatovat aspoň tabulek stránek (počet uživatelských procesů)
      Jádro systému si musí pamatovat pro každý proces právě jednu tabulku

    • invertovaná tabulka stránek:
      (nic není správně z výběru :D)
    • klasická tabulka stránek:

      Na řádce klasické tabulky stránek je uložené číslo rámce
      Na řádce klasické tabulky stránek je uložený Modify bit
      Na řádce klasické tabulky stránek je uložený Reference bit

    • invertovaná tabulka stránek:

      Na řádce invertované tabulky stránek je uložené číslo stránky
      Na řádce invertované tabulky stránek je uložené číslo procesu
      Na řádce invertované tabulky stránek je uložený Present bit
      Na řádce invertované tabulky stránek je uložený Modify bit
      Na řádce invertované tabulky stránek je uložený Reference bit

  6. Na řádce TLB je uložený Present bit
    Na řádce TLB je uložený Reference bit
    Na řádce TLB je uložený Modify bit
    Na řádce TLB je uložené číslo rámce
    Na řádce TLB je uložené číslo stránky

  7. Cache hit ratio TLB se může zvýšit, pokud systém bude používat pro proces větší stránky
    Současné serverové a desktopové procesory umožňují používat různě velké stránky pro různé procesy

  8. V případě klasické tabulky: Tabulka stránek bude obsahovat řádek. Používáme informaci z logické adresy.
    V případě invertované tabulky: Tabulka stránek bude obsahovat řádek. Používáme informaci z fyzické adresy.

Menší doporučení k 8. otázce, používejte bc. Ze standardních kalkulaček můžou vypadnout nehezké věci.