‹#›/43 PB153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ Virtuální paměť 11 ‹#›/43 lVirtuá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 lTechniky implementace ●Stránkování na žádost, Demand Paging ●Segmentování na žádost, Demand Segmentation ZÁKLADNÍ PRINCIPY PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/43 lČást procesu umístěnou ve FAP nazýváme „rezidentní množinou“ (resident set) lOdkaz mimo rezidentní množinu způsobuje přerušení výpadek stránky (page fault) lOS označí proces za „čekající“ lOS spustí I/O operace a provede nutnou správu paměti pro zavedení odkazované části do FAP lMezitím běží jiný proces (jiné procesy) lPo zavedení odkazované části se generuje I/O přerušení ●OS příslušný proces umístí mezi připravené procesy lPřeklad adresy LAP na adresu FAP se dělá indexováním tabulky PT/ST pomocí hardware CPU BĚH PROCESŮ VE VIRTUÁLNÍ PAMĚTI PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/43 lVe 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ý lLze 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) VIRTUÁLNÍ PAMĚŤ – VLASTNOSTI PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/43 lVIRT - 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. lRES - Resident size (kb) ●The non-swapped physical memory a task has used. lSHR - 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. PŘÍKLAD: LINUX PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/43 lUlož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 lStrá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 lOS musí být schopen organizovat tok stránek / segmentů mezi vnitřní a vnější pamětí VIRTUÁLNÍ PAMĚŤ – VLASTNOSTI PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/43 LAP VĚTŠÍ NEŽ FAP PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ physical memory memory map virtual memory page 0 page 1 page 2 page v ‹#›/43 lStrá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 lPř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 ● KDY ZAVÁDĚT STRÁNKU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/43 lSegmentace ●best-, first-, worstfit lStránkování ●nemusíme řešit lKombinace segmentování + stránkování ●nemusíme řešit KAM STRÁNKU ZAVÉST? PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/43 lUplatňuje se v okamžiku, kdy je FAP plný lTypicky v okamžiku zvýšení stupně multitaskingu lKterou stránku „obětovat“ a vyhodit z FAP (politika výběru oběti)? lPolitika 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, … ● KTEROU STRÁNKU NAHRADIT? PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/43 lStránka se zavádí do FAP jen když je potřebná lPřínosy ●méně I/O operací ●menší požadavky na paměť ●rychlejší reakce ●může pracovat více uživatelů lKdy 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 STRÁNKOVÁNÍ NA ŽÁDOST PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/43 lS 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 lPři překladu adresy ●jestliže je bit valid/invalid roven 0, generuje se přerušení typu „page fault“ BIT VALID-INVALID PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ Frame # valid-invalid bit 1 1 1 1 0 . . . 0 0 page table ‹#›/43 PŘÍKLAD: TABULKA STRÁNEK PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 1 A 2 B 3 C 4 D 5 E 6 F 7 G 0 1 2 3 4 A 5 6 C 7 8 9 F 10 11 12 13 14 15 logical memory A B E D C F G H physical memory 0 4 v 1 i 2 6 v 3 i 4 i 5 9 v 6 i 7 i page table frame valid-invalid bit ‹#›/43 lPokud se stránka nenachází ve FAP je aktivován OS pomocí přerušení „page fault“ (výpadek stránky) lOS zjistí: ●nelegální reference → procesu je informován (např. signál SIGSEGV) ●legální reference, ale stránka chybí v paměti → zavede ji lZavedení 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 lPak se opakuje instrukce, která způsobila „page fault“ VÝPADEK STRÁNKY PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/43 ZPRACOVÁNÍ VÝPADKU STRÁNKY PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ load M free frame i physical memory operating system page table 1 6 5 4 2 3 restart instruction reference reset page table trap page is on backing store bring in missing page ‹#›/43 lpokud 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 lPotřebujeme algoritmus pro hledání „oběti“ a řešení náhrady ●kritérium optimality algoritmu: nejméně výpadků stránek VOLNÝ RÁMEC PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/43 lOdkazy na instrukce programu a na dat mají tendenci tvořit shluky lČ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ů l→ lze dělat rozumné odhady o částech programu/dat potřebných v nejbližší budoucnosti lvnitřní paměť se může zaplnit ●něco umístit do FAP pak znamená nejdříve něco odložit z FAP ● PRINCIP LOKALITY PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/43 NÁHRADA STRÁNKY PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 4 victim f physical memory 3 1 swap desired page in swap out victim page frame valid-invalid bit page table 2 reset page table for new page change to invalid 0 f i v ‹#›/43 lKritérium optimality ●nejmenší pravděpodobnost výpadku stránky lČím více rámců máme, tím méně často dojde k výpadku stránky l l l l l l l ALGORITMY URČENÍ OBĚTI PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ number of frames 1 2 3 4 5 6 2 4 6 8 10 12 14 16 ‹#›/43 lPouze základní typy ●existují desítky variant lOptimá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í lAlgoritmus LRU (Least Recently Used) ●oběť = nejdéle neodkazovaná stránka lAlgoritmus FIFO (First-In-First-Out) ●oběť = stránka nejdéle zobrazená ve FAP lAlgoritmus 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 ALGORITMY URČENÍ OBĚTI PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/43 lPosloupnost odkazů stránek: l 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 l l5 stránek l3 rámce (3 stránky mohou být ve FAP) l l4 rámce ●Beladyho anomálie ●více rámců → více výpadků ALGORITMUS FIRST-IN-FIRST-OUT PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 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ů 4 4 3 ‹#›/43 BELADYHO ANOMÁLIE PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ number of frames 1 2 3 4 5 6 7 2 4 6 8 10 12 14 16 ‹#›/43 lHodnocení 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í ALGORITMUS FIRST-IN-FIRST-OUT PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 7 reference string page frames 0 7 1 0 7 3 0 2 3 4 2 1 0 2 1 0 2 3 0 2 1 0 7 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 ‹#›/43 lObětí je nejpozdější ze všech následných odkazů na stránky lPotřebuje znát budoucí posloupnost referencí lPří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 OPTIMÁLNÍ ALGORITMUS PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 1 2 3 4 4 5 ‹#›/43 lDalší příklad: OPTIMÁLNÍ ALGORITMUS PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 7 reference string page frames 0 7 1 0 7 3 0 2 3 4 2 1 0 2 1 0 2 3 0 2 1 0 7 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 ‹#›/43 ANIMACE: OPTIMÁLNÍ ALGORITMUS PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/43 lObě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 lPříklad: ●proces s 5 stránkami, k dispozici 4 rámce ●1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 ALGORITMUS LRU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 5 2 4 3 1 2 3 4 1 2 5 4 1 2 5 3 1 2 4 3 ‹#›/43 lDalší příklad: l ALGORITMUS LRU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 7 reference string page frames 0 7 1 0 7 3 0 2 3 0 4 1 0 2 2 3 1 2 3 0 7 0 1 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 2 0 4 2 3 4 2 0 1 ‹#›/43 ANIMACE: ALGORITMUS LRU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/43 lV 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í lZá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ěť“) lAproximace: 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 l IMPLEMENTACE POLITIKY LRU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ reference string 4 7 0 7 1 0 1 2 1 2 7 1 2 2 1 0 7 4 7 2 1 0 4 stack before a stack after b a b ‹#›/43 ANIMACE: IMPLEMENTACE POLITIKY LRU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/43 lTaké nazývané „Máš ještě šanci“ lVýběr oběti – cyklické procházení (podobně jako FIFO) lOdkazem na stránku stránka se nastaví příznak ●ani násobné odkazy příznak nezvyšují, jen nastavují lOběť, která nemá nastaven příznak a je na řadě při kruhovém procházení je nahrazovaná lExperimenty ukazují, že optimalita algoritmu se blíží skutečnému LRU l DRUHÁ ŠANCE PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/43 lImplementace ●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 DRUHÁ ŠANCE (2) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/43 DRUHÁ ŠANCE (3) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 0 0 1 1 0 1 1 reference bits pages circular queue of pages (a) circular queue of pages (b) next victim 0 0 0 0 0 1 1 reference bits pages ‹#›/43 lOPT ●super, ale nutnost znát budoucnost lLRU ●časové čítače u rámců, ∆t + 1, nulované odkazem ●oběť = rámec s nejvyšší hodnotou čítače ●Implementace má vysokou režii lFIFO ●snadná implementace, cyklický seznam ●špatná heuristika lDruhá š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 SROVNÁNÍ ALGORITMŮ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/43 lint data[128][128]; lJeden řádek odpovídá jedné stránce lProgram 1 l 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 lProgram 2 ● for (i = 0; i < 128; i++) for (j = 0; j < 128; j++) data[i,j] = 0; ●128 výpadků stránky l STRUKTURA PROGRAMU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/43 THRASHING PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ degree of multiprogramming thrashing ‹#›/43 1.A alokuje 64K 2.B alokuje 128K 3.C alokuje 64K 4.D alokuje 128K BUDDY ALOKAČNÍ ALGORITMUS PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 5.C uvolňuje paměť 6.A uvolňuje paměť 7.B uvolňuje paměť 8.D uvolňuje paměť 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K t = 0 1024K t = 1 A-64K 64K 128K 256K 512K t = 2 A-64K 64K B-128K 256K 512K t = 3 A-64K C-64K B-128K 256K 512K t = 4 A-64K C-64K B-128K D-128K 128K 512K t = 5 A-64K 64K B-128K D-128K 128K 512K t = 6 128K B-128K D-128K 128K 512K t = 7 256K D-128K 128K 512K t = 8 1024K ‹#›/43 PŘÍKLAD: LINUX 2.4 PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ Zdroj: RedHat Bash httpd mozilla Standard C Library (glibc) Kernel Subsystems: VF S Network Syscalls Disk Driver Slab Allocator kswapd bdflush zoned buddy allocator MMU Disk VM Subsystem Physical Memory User Space Processes ‹#›/43 PŘÍKLAD: LINUX 2.4 PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ Zdroj: RedHat Free Active Inactive Clean Inactive Laundry Active Dirty accessed/kscand accessed kupdated/bdflush ‹#›/43 lKscand lKswapd ●Prochází paměť a hledá stránky k uvolnění pokud dochází paměť lKupdated [dirty pages; pravidelně] + Bdflush (2.4) [dirty buffers; v případě potřeby] lPdflush (2.6) [dirty pages] ●Zapisuje na disk PŘÍKLAD: LINUX 2.4 PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/43 lCurrently (2.6.32), these files are in /proc/sys/vm: DOCUMENTATION/SYSCTL/VM.TXT PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ¢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 ¢block_dump ¢dirty_background_bytes ¢dirty_background_ratio ¢dirty_bytes ¢dirty_expire_centisecs ¢dirty_ratio ¢dirty_writeback_centisecs ¢drop_caches ¢hugepages_treat_as_movabl ¢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 ‹#›/43 Výukovou pomůcku zpracovalo Servisní středisko pro e-learning na MU http://is.muni.cz/stech/ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ