Virtualizace paměti, stránkování

BI-SPOL.21-18
  • Princip překladu virtuálních adres na fyzické
  • Struktura tabulek stránek
  • Algoritmy pro nahrazování stránek

Adresování do fyzické paměti

  • přímé adresování
  • všechny procesy mají pouze jeden adresní prostor
  • Bezpečnost je nízká
  • Používáním dochází k fragmentaci

Virtuální adresní prostor

  • Každý proces má vlastní virtuální adresní prostor
  • nutnost přepínat kontexty
  • Každý proces může adresovat ohromné množství paměti 2^bit šířku procesoru
  • Používá virtuální adresy
  • neřeší fragmentaci

Stránkování

  • Proces kdy je fyzická paměť rozdělná na rámce
  • Virtuální prostor na stránky o stejné velikosti
  • Dochází pouze k výměně stránek podle potřeby
  • řeší fragmentaci

Virtuální paměť se stránkováním

  • (VAS) Virtuální adresový prostor
  • Adresa ve virtuálním adresním prostoru je číslo stránky + offset(pozice na stránce)
  • Každý proces má vlastní
  • Mapuje se do fyzické paměti
  • Konkretně záleží na CPU a OS
  • Některé struktury mohou být umisťovány na náhodné adresy pro bezpečnost

Virtualizace paměti pomocí stránkování

  • Fyzická paměť je rozdělena na stejně velké úseky – rámce (frames), např. 4 kB
  • VAS je rozdělený na stejně velké úseky – stránky (pages)
  • Velikost rámce = velikost stránky
  • Stránky VAS se nahrávají do volných rámců fyzické paměti
  • OS si pamatuje
    • volné rámce
    • rámce přidělené jednotlivým procesům (tabulka stránek)
  • Princip virtuální paměti
    • Situace
      • Každý proces může teoreticky adresovat např. 2 64 B
      • Prakticky ale využívá jen zlomek
    • Problém
      • VAS jednoho procesu může být větší než fyzicky dostupná paměť
      • OS spouští současně tisíce procesů
      • součet VAS je opět větší
    • Řešení
      • Ve fyzické paměti jsou pouze aktuálně využívané části VAS
      • Zbytek může být na disku
      • Kombinace se stránkováním
    • Virtuální paměť se stránkováním
      • Proces používá virtuální adresy
      • VAS je rozdělen na virtuální stránky
      • Rámce stránek (page frames):: korespondující úseky ve fyzické paměti
      • V hlavní paměti musí být alespoň aktuálně používané stránky
    • Memory management unit (MMU)
      • Zajišťuje procesu iluzi, že má k dispozici celou hlavní paměť
      • Překládá virtuální adresy na fyzické
      • Výpadek stránky (page fault)
        • Virtuální stránka není v hlavní paměti
        • MMU instruuje OS, aby stránku nahrál z disku
        • OS najde volný rámec nebo nějaký uvolní na disk a stránku tam nahraje

Překlad logických adres na fyzické

  • OS mapuje rámce fyzické paměti na VAS stránky jednotlivých procesů
    • Použití následujících struktur podle architektury procesoru
    • Pro urychlení navíc TLB (translation lookaside buffer) – cache posledních překladů
  • Implementace stránkování
    • Tabulka stránek
      • každý proces má svou
      • Pro každou stránku VAS daného procesu jeden řádek
        • Číslo fyzického rámce
        • Kontrolní bity
          • Present -> zda je stránka v hlavní paměti
          • Reference -> zda se ke stránce přistupovalo
          • Modify -> zda byl obsah stránky změněn
          • atd.
      • Obsahuje zbytečně prázdné řádky s volnými stránkami
    • Víceúrovňová tabulka stránek
      • Tabulky tabulek až do 4. úrovně
      • Ušetření místa na úkor zpomalení překladu (navíc TLB - cache)
      • Virtuální adresa je rozdělena na několik částí, každá část v jedné úrovni
      • Pouze první úroveň je přítomná vždy
    • Invertovaná tabulka stránek
      • Ukládá pro každý rámec informaci o tom co v něm je, komu to patří, a kontrolní bity, index zřetězení (kvůli hash funkci)
      • Jedna tabulka pro kompletní RAM
      • Hashovací tabulka stránek
      • Zřetězení v případě kolize
      • Ušetření místa na úkor zpomalení překladu (navíc TLB - cache)
  • Translation lookaside buffer (TLB)
    • Cache naposledy překládaných adres
    • n-way cache
    • číslo stránky - číslo rámce
    • obsahuje i ID adresspace odkud je stránka
    • Pokud aplikace alokuje velkou část VAS, často může docházet k výpadku (miss)
  • Segmentace
    • U jednorozměrného VAS problémy při implementaci na fyzické paměti
      • Fragmentace
      • Problém se sdílením struktur mezi procesy
    • Proto navíc tabulka segmentů pro každý proces
      • Několik segmentů s různými vlastnostmi
      • Segment obsahuje tabulku stránek

Algoritmy pro nahrazování stránek

  • Když je fyzická paměť plná, OS hledá rámec, který by mohl uvolnit
  • Požadavky na algoritmus
    • Minimalizace počtu výpadků stránek
    • Maximalizace rychlosti
    • Jednoduchá implementace
  • Princip algoritmů -> prostorová a časová lokalita
    • Většinou jsou data v programu uložena přímo za sebou
    • Stejně tak instrukce se vykonávají sekvenčně
  • Optimální algoritmus
    • Nahradí se stránka, na kterou se bude přistupovat za nejdelší čas
    • Nereálné, ale použitelné pro porovnávání ostatních algoritmů
  • NRU (Not recently used)
    • Periodicky se resetuje Reference bit v tabulce stránek
    • Podle Reference a Modified bitu jsou stránky seřazeny a nahrazovány
    • Jednoduché, málo výpadků
  • FIFO (First in, first out)
    • Frontu stránek v paměti, vložení při načtení stránky
    • První stránka ve frontě je nahrazena
    • Nezohledňuje čas přístupu, velký počet výpadků
  • Clock
    • Kruhová fronta stránek
    • Ručička shazuje Reference bit, pokud již je shozený, stránku vyřazuje
    • Two-handed clock -> dvě ručičky, první shazuje, druhá vyřazuje, jejich rozevření je časové okno
  • LRU (Least recently used)
    • Vyřazuje stránku, ke které se nepřistupovalo nejdelší dobu
    • Problematická implementace (pomocí HW čítače)
  • Aging algoritmus
    • SW simulace LRU (méně přesná)
    • Pro každou stránku Reference bit a n-bitový čítač, obojí začíná na 1
    • Periodicky čítač dělí dvěma a nastavuje nejvyšší bit na hodnotu Reference
    • Vyřazuje stránku s nejnižší hodnotou čítače

Vytvořeno: 9. 6. 2026, 13:06
Poslední aktualizace: 9. 6. 2026, 13:16