PB 153 Operační systémy a jejich rozhraní1 Virtuální paměť PB153 Operační systémy a jejich rozhraní PB 153 Operační systémy a jejich rozhraní2 Základní principy  Virtuální paměť  separace LAP a FAP  ve FAP se mohou nacházet pouze části programů nutné pro bezprostřední řízení procesů  LAP může být větší než FAP  adresové prostory lze sdílet mezi jednotlivými procesy  lze efektivněji vytvářet procesy  Techniky implementace  Stránkování na žádost, Demand Paging  Segmentování na žádost, Demand Segmentation PB 153 Operační systémy a jejich rozhraní3 Běh procesů ve virtuální paměti  Část procesu umístěnou ve FAP nazýváme „rezidentní množinou“ (resident set)  Odkaz mimo rezidentní množinu způsobuje přerušení výpadek stránky (page fault)  OS označí proces za „čekající“  OS spustí I/O operace a provede nutnou správu paměti pro zavedení odkazované části do FAP  Mezitím běží jiný proces (jiné procesy)  Po zavedení odkazované části se generuje I/O přerušení  OS příslušný proces umístí mezi připravené procesy  Překlad adresy LAP na adresu FAP se dělá indexováním tabulky PT/ST pomocí hardware CPU PB 153 Operační systémy a jejich rozhraní4 Virtuální paměť – vlastnosti  Ve FAP lze udržovat více procesů najednou  čím více je procesů ve FAP, tím je větší pravděpodobnost, že stále bude alespoň jeden připravený  Lze realizovat procesy požadující více paměti než umožňuje FAP  aniž se o řešení tohoto problému stará programátor / kompilátor  jinak bychom museli použít překryvy (overlays) PB 153 Operační systémy a jejich rozhraní5 Příklad: Linux  VIRT - Virtual Image (kb)  The total amount of virtual memory used by the task. It includes all code, data and shared libraries plus pages that have been swapped out.  RES - Resident size (kb)  The non-swapped physical memory a task has used.  SHR - Shared Mem size (kb)  The amount of shared memory used by a task. It simply reflects memory that could be potentially shared with other processes. PB 153 Operační systémy a jejich rozhraní6 Virtuální paměť – vlastnosti  Uložení obrazu LAP (virtuální paměti) v externí paměti  nepoužívá se standardní systém souborů OS, používají se speciální metody, optimalizované pro tento účel  speciální partition/slice disku  Stránkování / segmentaci musí podporovat hardware správy paměti  stránkování na žádost  segmentování na žádost  žádost – dynamicky kontextově generovaná indikace nedostatku  OS musí být schopen organizovat tok stránek / segmentů mezi vnitřní a vnější pamětí PB 153 Operační systémy a jejich rozhraní7 LAP větší než FAP PB 153 Operační systémy a jejich rozhraní8 Kdy zavádět stránku  Stránkování na žádost (Demand paging)  stránka se zobrazuje do FAP při odkazu na ni, pokud ve FAP není již zobrazena  počáteční shluky výpadků stránek  Předstránkování (Prepaging)  umístění na vnější paměti sousedních stránek v LAP bývá blízké („sousedi“)  princip lokality  zavádí se více stránek než se žádá  vhodné při inicializaci procesu PB 153 Operační systémy a jejich rozhraní9 Kam stránku zavést?  Segmentace  best-, first-, worstfit  Stránkování  nemusíme řešit  Kombinace segmentování + stránkování  nemusíme řešit PB 153 Operační systémy a jejich rozhraní10 Kterou stránku nahradit?  Uplatňuje se v okamžiku, kdy je FAP plný  Typicky v okamžiku zvýšení stupně multitaskingu  Kterou stránku „obětovat“ a vyhodit z FAP (politika výběru oběti)?  Politika nahrazování  určení oběti • politika přidělování místa • kolik rámců přidělit procesu? • intra/extra (local/global) množina možných obětí • oběti lze hledat jen mezi stránkami procesu, který vyvolal výpadek stránky? • oběti lze hledat i mezi stránkami ostatních procesů (např. podle priorit procesů)?  nelze obětovat kteroukoliv stránku • někde rámce jsou „zamčeny“ • typicky I/O buffery, řídicí struktury OS, … PB 153 Operační systémy a jejich rozhraní11 Stránkování na žádost  Stránka se zavádí do FAP jen když je potřebná  Přínosy  méně I/O operací  menší požadavky na paměť  rychlejší reakce  může pracovat více uživatelů  Kdy je stránka potřebná?  byla odkazovaná  legální reference • Nachází se ve FAP, přeloží se logická adresa na fyzickou  nelegální reference (porušení ochrany) → abort procesu  reference stránky, která není ve FAP → její zavedení do FAP • zprostředkovává OS PB 153 Operační systémy a jejich rozhraní12 Bit Valid-Invalid  S každým řádkem PT je spojen bit V/I (valid/invalid) (1 → je ve FAP, 0 → není právě ve FAP)  iniciálně jsou všechny V/I bity nastaveny na 0  Při překladu adresy  jestliže je bit valid/invalid roven 0, generuje se přerušení typu „page fault“ 1 1 1 1 0 0 0  Frame # valid-invalid bit page table PB 153 Operační systémy a jejich rozhraní13 Příklad: tabulka stránek PB 153 Operační systémy a jejich rozhraní14 Výpadek stránky  Pokud se stránka nenachází ve FAP je aktivován OS pomocí přerušení „page fault“ (výpadek stránky)  OS zjistí:  nelegální reference → procesu je informován (např. signál SIGSEGV)  legální reference, ale stránka chybí v paměti → zavede ji  Zavedení stránky  získání prázdného rámce  zavedení stránky do tohoto rámce  úprava tabulky, nastaven bit valid/invalid na 1  Pak se opakuje instrukce, která způsobila „page fault“ PB 153 Operační systémy a jejich rozhraní15 Zpracování výpadku stránky PB 153 Operační systémy a jejich rozhraní16 Volný rámec  pokud není žádný rámec aktuálně označen jako volný, musíme nějaký uvolnit  nalezneme se „oběť“ – nepotřebnou stránku ve FAP (nevíme, co je nepotřebné, můžeme pouze odhadovat)  je-li to nutné, před uvolněním stránky ji zapíšeme na disk • pokud se do ní nezapsalo, její kopie na disku je aktuální • zda se do stránky zapsalo zjistíme v bitu modify (dirty) • bit modify nastavuje HW automaticky při zápisu do stránky  Potřebujeme algoritmus pro hledání „oběti“ a řešení náhrady  kritérium optimality algoritmu: nejméně výpadků stránek PB 153 Operační systémy a jejich rozhraní17 Princip lokality  Odkazy na instrukce programu a na dat mají tendenci tvořit shluky  Časová lokalita a prostorová lokalita  provádění programu je s výjimkou skoků a volání podprogramů sekvenční  programy mají tendenci zůstávat po jistou dobu v rámci nejvýše několika procedur (nelze jen něco volat a hned se vracet)  většina iterativních konstruktů představuje malý počet často opakovaných instrukcí  často zpracovávanou datovou strukturou je pole dat nebo posloupnost záznamů  → lze dělat rozumné odhady o částech programu/dat potřebných v nejbližší budoucnosti  vnitřní paměť se může zaplnit  něco umístit do FAP pak znamená nejdříve něco odložit z FAP PB 153 Operační systémy a jejich rozhraní18 Náhrada stránky PB 153 Operační systémy a jejich rozhraní19 Algoritmy určení oběti  Kritérium optimality  nejmenší pravděpodobnost výpadku stránky  Čím více rámců máme, tím méně často dojde k výpadku stránky PB 153 Operační systémy a jejich rozhraní20 Algoritmy určení oběti  Pouze základní typy  existují desítky variant  Optimální algoritmus  příští odkazy na oběť je nejpozdější ze všech následných odkazů na stránky  generuje nejmenší počet výpadků stránek  neimplementovatelný, neboť neznáme budoucnost  používá se jen pro srovnání  Algoritmus LRU (Least Recently Used)  oběť = nejdéle neodkazovaná stránka  Algoritmus FIFO (First-In- First-Out)  oběť = stránka nejdéle zobrazená ve FAP  Algoritmus poslední šance  FIFO + vynechávání z výběru těch stránek, na které od posledního výběru bylo odkázáno PB 153 Operační systémy a jejich rozhraní21 Algoritmus First-In-First-Out  Posloupnost odkazů stránek: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5  5 stránek  3 rámce (3 stránky mohou být ve FAP)  4 rámce  Beladyho anomálie  více rámců → více výpadků 1 2 3 1 2 3 4 1 2 5 3 4 9 výpadků 1 2 3 1 2 3 5 1 2 4 5 10 výpadků 44 3 PB 153 Operační systémy a jejich rozhraní22 Beladyho anomálie PB 153 Operační systémy a jejich rozhraní23 Algoritmus First-In-First-Out  Hodnocení FIFO strategie  často používané stránky jsou v mnoha případech právě ty nejstarší • pravděpodobnost výpadku takové stránky je vysoká • tj. algoritmus zbytečně odkládá často používané stránky  jednoduchá implementace • stačí udržovat ukazatelem vazbu do cyklického pořadí PB 153 Operační systémy a jejich rozhraní24 Optimální algoritmus  Obětí je nejpozdější ze všech následných odkazů na stránky  Potřebuje znát budoucí posloupnost referencí  Příklad  proces s 5 stránkami  k dispozici máme 4 rámce  Posloupnost přístupů: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5  celkem 6 výpadků stránky 1 2 3 4 4 5 PB 153 Operační systémy a jejich rozhraní25 Optimální algoritmus  Další příklad: PB 153 Operační systémy a jejich rozhraní26 Algoritmus LRU  Obětí je nejdéle neodkazovaná stránka  princip lokality říká, že pravděpodobnost jejího brzkého použití je velmi malá  výkon blízký optimální strategii  Příklad:  proces s 5 stránkami, k dispozici 4 rámce  1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 5 2 4 3 1 2 3 4 1 2 5 4 1 2 5 3 1 2 4 3 PB 153 Operační systémy a jejich rozhraní27 Algoritmus LRU  Další příklad: PB 153 Operační systémy a jejich rozhraní28 Implementace politiky LRU  V položkách PT se udržuje (HW) čítač (sekvenční číslo nebo logický čas) posledního přístupu ke stránce  čítač má konečnou kapacitu  problém jeho přečtení  Zásobník  zásobník čísel stránek, při přístupu ke stránce je položka odstraněna ze zásobníku a přemístěna na vrchol (na spodu je „oběť“)  Aproximace: iniciálně je bit nastaven na 0, při každém přístupu je nastaven bit přístupu na 1  neznáme pořadí přístupu ke stránkám  víme jen které stránky byly použity PB 153 Operační systémy a jejich rozhraní29 Druhá šance  Také nazývané „Máš ještě šanci“  Výběr oběti – cyklické procházení (podobně jako FIFO)  Odkazem na stránku stránka se nastaví příznak  ani násobné odkazy příznak nezvyšují, jen nastavují  Oběť, která nemá nastaven příznak a je na řadě při kruhovém procházení je nahrazovaná  Experimenty ukazují, že optimalita algoritmu se blíží skutečnému LRU PB 153 Operační systémy a jejich rozhraní30 Druhá šance (2)  Implementace  Množina rámců kandidujících na nahrazení je organizována jako cyklický buffer  Když se stránka nahradí, ukazatel se posune na příští rámec v bufferu  Pro každý rámec se nastavuje „use bit“ na 1 když • se do rámce zavede stránka poprvé • kdykoliv se odpovídající stránka referencuje  Když se má nalézt oběť, nahradí se stránka v prvním rámci s „use bit“ nastaveným na 0. • Při hledání kandidáta na nahrazení se každý „use bit“ nastavený na 1 nastavuje na 0 PB 153 Operační systémy a jejich rozhraní31 Druhá šance (3) PB 153 Operační systémy a jejich rozhraní32 Srovnání algoritmů  OPT  super, ale nutnost znát budoucnost  LRU  časové čítače u rámců, ∆t + 1, nulované odkazem  oběť = rámec s nejvyšší hodnotou čítače  Implementace má vysokou režii  FIFO  snadná implementace, cyklický seznam  špatná heuristika  Druhá šance  upravené FIFO  z výběru obětí se vynechává alespoň jednou odkázaná stránka od posledního výběru  use_bit = (počátečně) 0 / po odkazu 1  úprava druhá šance • use_bit = 0 / 1, doplněný modified_bit = 0 / 1 • pořadí výběru: 00, 01, 1x • 0x šetří výpis nemodifikované stránky PB 153 Operační systémy a jejich rozhraní33 Struktura programu  int data[128][128];  Jeden řádek odpovídá jedné stránce  Program 1 for (j = 0; j <128; j++) for (i = 0; i < 128; i++) data[i,j] = 0;  128 x 128 = 16,384 výpadků stránky  Program 2 for (i = 0; i < 128; i++) for (j = 0; j < 128; j++) data[i,j] = 0;  128 výpadků stránky PB 153 Operační systémy a jejich rozhraní34 Thrashing PB 153 Operační systémy a jejich rozhraní35 Buddy alokační algoritmus 1. A alokuje 64K 2. B alokuje 128K 3. C alokuje 64K 4. D alokuje 128K 5. C uvolňuje paměť 6. A uvolňuje paměť 7. B uvolňuje paměť 8. D uvolňuje paměť PB 153 Operační systémy a jejich rozhraní36 Příklad: Linux 2.4 Zdroj: RedHat PB 153 Operační systémy a jejich rozhraní37 Příklad: Linux 2.4 Zdroj: RedHat PB 153 Operační systémy a jejich rozhraní38 Příklad: Linux 2.4  Kscand  Kswapd  Prochází paměť a hledá stránky k uvolnění pokud dochází paměť  Kupdated [dirty pages; pravidelně] + Bdflush (2.4) [dirty buffers; v případě potřeby]  Pdflush (2.6) [dirty pages]  Zapisuje na disk PB 153 Operační systémy a jejich rozhraní39 Documentation/sysctl/vm.txt  Currently (2.6.32), these files are in /proc/sys/vm:  block_dump  dirty_background_bytes  dirty_background_ratio  dirty_bytes  dirty_expire_centisecs  dirty_ratio  dirty_writeback_centisecs  drop_caches  hugepages_treat_as_movable  hugetlb_shm_group  laptop_mode  legacy_va_layout  lowmem_reserve_ratio  max_map_count  memory_failure_early_kill  memory_failure_recovery  min_free_kbytes  min_slab_ratio  min_unmapped_ratio  mmap_min_addr  nr_hugepages  nr_overcommit_hugepages  nr_pdflush_threads  nr_trim_pages  numa_zonelist_order  oom_dump_tasks  oom_kill_allocating_task  overcommit_memory  overcommit_ratio  page-cluster  panic_on_oom  percpu_pagelist_fraction  stat_interval  swappiness  vfs_cache_pressure  zone_reclaim_mode