‹#›/38 PB153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ Vnější paměti 13 ‹#›/38 lPrimární paměti ●nejrychlejší ●energeticky závislé ●Cache, hlavní (operační) paměť lSekundární paměti ●středně rychlé ●energeticky nezávislé ●Také nazývané „on-line storage“ ●flash disky, magnetické disky lTerciální paměti ●levná typicky vyměnitelná média ●pomalé ●energeticky nezávislé ●také nazývané „off-line storage“ ●floppy disky, magnetické pásky, optické disky PAMĚŤOVÁ HIERARCHIE PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ registry cache main memory electronic disk magnetic disk optical disk magnetic tapes ‹#›/38 MAGNETICKÉ DISKY PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ platter rotation read-write head arm assembly spindle track t sector s cylinder c arm ‹#›/38 lDiskové mechanismy se adresují jako velká 1-dimensionální pole logických bloků ●logické bloky jsou nejmenší jednotkou přenosu dat l1-dimensionální pole logických bloků je zobrazováno do sektorů disku sekvenčně ●sektor 0 ●první sektor na první stopě vnějšího cylindru ●zobrazování pokračuje po této stopě, ● potom po ostatních stopách tohoto cylindru, ● a potom po cylindrech směrem ke středu STRUKTURA DISKU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/38 lOS je odpovědný za efektivní používání hardware ●pro disky: co nejrychlejší přístup a co největší šířka pásma lDoba přístupu (access time) je dána: ●dobou vystavení (seek time) – na cylindr se stopou s adresovaným sektorem ●dobou rotačního zpoždění – dodatečná doba do průchodu adresovaného sektoru pod čtecí/zápisovou hlavou lMinimalizace doby vystavení ●doba vystavení » vystavovací vzdálenosti ●řeší plánování činnosti disku lRotační zpoždění ●shora omezeno konstantou lŠířka pásma ●počet přenesených bytů / doba od zadání skupiny požadavků do jejich ukončení ●převzatý pojem z telekomunikací PLÁNOVÁNÍ DISKU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/38 lExistuje celá řada algoritmů pro plánování přístupu na disk. ●„Disk scheduling“ lPříklad: vzorová fronta požadavků na přístup k disku (máme cylindry 0-199). l 98, 183, 37, 122, 14, 124, 65, 67 l l Hlavička disku vystavena na pozici 53 PLÁNOVÁNÍ DISKU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/38 lCelkem přesun o 640 cylindrů FCFS PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 14 37 53 67 65 98 122 124 183 199 head starts at 53 queue = 98, 183, 37, 122, 14, 124, 65, 67 ‹#›/38 lZ fronty požadavků vybírá ten požadavek, který vyžaduje minimální dobu vystavení od současné pozice hlavičky lSSTF (shortest seek time first) algoritmus je variantou algoritmu SJF (shortest job first); může způsobit stárnutí požadavků. lNáš příklad vyžaduje přesun o 236 cylindrů l SSTF PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/38 SSTF PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 14 37 53 67 65 98 122 124 183 199 head starts at 53 queue = 98, 183, 37, 122, 14, 124, 65, 67 ‹#›/38 lHlavička disku začíná na jedné straně disku a přesunuje se při splňování požadavků ke druhé straně disku. Pak se vrací zpět a opět plní požadavky. lNěkdy nazývané algoritmus typu výtah (elevator). lNáš příklad vyžaduje přesun o 208 cylindrů. l SCAN PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/38 SCAN PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 0 14 37 53 67 65 98 122 124 183 199 head starts at 53 queue = 98, 183, 37, 122, 14, 124, 65, 67 ‹#›/38 lPoskytuje jednotnější čekací dobu než SCAN lHlavička se posouvá z jednoho konce disku na druhý a zpracovává požadavky. Potom se vrací zpět bez vyřizování požadavků a opět začíná vyřizovat požadavky z prvního konce. lCylindry považuje za kruhový seznam, který za posledním cylindrem pokračuje opět prvním cylindrem. l C-SCAN PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/38 C-SCAN PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 14 37 53 67 65 98 122 124 183 199 head starts at 53 queue = 98, 183, 37, 122, 14, 124, 65, 67 ‹#›/38 lObdoba C-SCAN, ale hlavička jen potud do kraje, pokud existují požadavky. lPak se vrací zpět C-LOOK PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/38 C-LOOK PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 14 37 53 67 65 98 122 124 183 199 head starts at 53 queue = 98, 183, 37, 122, 14, 124, 65, 67 ‹#›/38 lSSTF je přirozený, má přirozené chápání lSCAN a C-SCAN jsou vhodnější pro těžkou zátěž disku lVýkon závisí na počtu a typech požadavků lPožadavky na disk mohou být ovlivněny metodami organizace souborů v souborovém systému lPlánovací algoritmus by měl být napsán jako samostatný modul, aby plánovací algoritmus OS bylo možné zaměňovat lČastá implicitní volba bývá SSTF nebo LOOK VÝBĚR ALGORITMU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/38 lU moderních disků nemusí být známé mapování logických bloků na fyzické adresy lDisku předáme skupinu požadavků a disk si pořadí optimalizuje sám lOS přesto může mít zájem na vlastním řazení požadavků ●priorita I/O operací z důvodu výpadků stránek ●Pořadí operací zápisu dat a metadat souborového systému MODERNÍ HW PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/38 lK dispozici několik plánovacích algoritmů l l l lFronty v řadiči disku mohou měnit pořadí od OS ●Fronta na desítky až stovky požadavků lAlgoritmy ●Noop ●Anticipatory ●Deadline ●CFQ (Completely Fair Queue) PŘÍKLAD: LINUX PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ # cat /sys/block/sda/queue/scheduler noop anticipatory deadline [cfq] # echo noop >/sys/block/sda/queue/scheduler ‹#›/38 lNemění pořadí požadavků lJen pokud nově příchozí navazuje na předchozí požadavek, požadavky budou sloučeny ●To stejně obvykle řeší už vrstva blokového zařízení nebo vrstva souborového systému. NOOP PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/38 lVychází z algoritmu SCAN lPřidává deadline (do kdy má být požadavek vyřízen) lPo dávce požadavků se vzrůstajícími čísly sektorů (SCAN) kontroluje deadline ●Pokud je třeba vytvoří speciální dávku pro vyřešení požadavků s expirovaným deadline. lUpřednostňuje čtení před zápisem DEADLINE PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/38 lJako deadline, ale přidává očekávání, že při sekvenčním přístupu k souboru přijde po jednom požadavku brzy požadavek následující. Proto chvíli vyčká (opravdu) … lUmožňuje i krátké přesuny zpět ●Penalizuje dvojnásobnou vzdáleností lNeodlišuje požadavky čtení a zápisu lOdlišuje asynchronní požadavky od synchronních lNeobjevuje se v linuxovém jádře od verze 2.6.33 ANTICIPATORY SCHEDULER (AS) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/38 lSnaží se být spravedlivý k procesům lKaždý proces dostává určitý časový díl (slice) kdy má exkluzivní přístup pro synchronní požadavky lParametry ●slice_sync – délka slice v ms (bere v úvahu I/O prioritu procesu) ●quantum – počet požadavků l17 front (pro každou prioritu jedna) pro asynchronní požadavky lKaždá fronta získává určitý slice a fronty jsou obsluhovány algoritmem RR COMPLETELY FAIR QUEUING PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/38 CFQ PARAMETRY PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ Turnable Defalt value Purpose back_seek_max 16384 (KiB) Max. backward seek back_seek_penalty 2 reverse seek bias fifo_expire_sync 125 (ms) deadline for synchronous requests fifo_expire_async 250 (ms) deadline for asynch requests quantum 4 Maximum requests to service in each batch in each round slice_async 40 (ms) base time slise for asynch. requests slice_sync 100 (ms) base time slise for synch. requests slice_async_rq 2 base number of async requests per round slice_idle 8 (ms) maximum idle time between requests ‹#›/38 lPříkaz ionice (od 2.6.13 pro CFQ) I/O PRIORITA PROCESŮ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ Schedulling class Number Possible priority real time 1 8 priority levels are defined denoting how big a time slice a given process will receive on each schedulling window. best-effort 2 0–7, with lower number being higher priority idle 3 Nil (does not také a priority argument) ‹#›/38 lDva aspekty ●šířka pásma, bandwidth ●zpoždění, latency lŠířka pásma se měří v B/s ●podporovaná šířka pásma ●průměrná rychlost přenosu dat během velkého přenosu ●počet B / doba přenosu ●efektivní šířka pásma ●Průměr za celou dobu I/O operace, vč. vystavení, nalezení umístění, přepnutí svazku atd. RYCHLOST TERCIÁLNÍCH PAMĚTÍ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/38 lZpoždění při přístupu ●doba potřebná pro vyhledání dat ●na disku – vystavení, natočení, určitě < 35 ms ●na pásce – vč. přetočení pásky na požadovaný blok, desítky až stovky sekund ●pásky jsou typicky 1000x pomalejší než disky lNízká cena terciární paměti je dána tím, že se pracuje s mnoha levnými svazky v malém počtu drahých mechanismů lVyměnitelná knihovna se nejlépe využije pro ukládání řídce používaných dat ●uspokojuje se malý počet I/O požadavků RYCHLOST TERCIÁLNÍCH PAMĚTÍ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/38 lPevný disk je asi spolehlivější než vyměnitelný disk nebo páska lOptický disk je asi spolehlivější než magnetický páska lPadnutí hlav v pevném disku obvykle znamená zničení dat lPorucha pásky nebo optického disku obvykle neznamená zničení všech dat SPOLEHLIVOST PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/38 lOperační paměť je mnohem dražší než disková paměť lCena MB na pevném disku je srovnatelná s cenou MB na pásce (dříve pásky levnější) lKapacity magnetických pásek nedržely v posledních letech krok s nárůstem kapacit pevných disků lTerciální paměť může ušetřit peníze pouze když se používá mnohem více svazků než mechanismů CENA PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/38 lRAID: Redundant Arrays of Independent (Inexpensive) Disks ●organizace disků řízená tak, že poskytuje objem jednoho disku ●s velkou kapacitou a rychlostí díky tomu, že mnoho disků pracuje paralelně ●s velkou spolehlivostí, data se uchovávají redundantně, lze je obnovit i po poruše některého z disků lPravděpodobnost, že některý disk z množiny N disků selže je mnohem vyšší, než pravděpodobnost, že selže jediný disk ●N = 100 disků, každý má MTTF = 100 000 hodin (cca 11 let), celý systém bude mít MTTF = 1000 hodin (cca 41 dní) ●techniky na bázi redundance chránící před ztrátou dat jsou pro systémy s velkým počtem komponent (disků) kritické lPůvodní záměr ●levná alternativa nahrazující velké drahé disky ●„I“ je interpretováno jako „independent“ TECHNOLOGIE RAID PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/38 lRedundance ●nadbytečnost, doplňková informace použitelná pro obnovu informace po poruše (disku) lZrcadlení (stínování), Mirroring (shadowing) ●každý disk je duplikován, 1 logický disk je tvořen 2 fyzickými disky ●každý zápis se provede na obou discích, čte se z jednoho disku ●jestliže se jeden disk porouchá, data jsou k dispozici na druhém disku ●ke ztrátě dat dojde při výpadku obou disků, když zrcadlový disk selže dříve, než se systém opraví ●průměrná doba do ztráty dat závisí na průměrné době do poruchy a průměrné doby opravy ●Např. MTTF = 100 000 hodin, průměrná doba opravy 10 hodin, dává u zrcadlené dvojice disků průměrnou dobu ztráty dat 500*106 hodin (čili 57 000 let), když budeme ignorovat požáry apod. RAID: ZVÝŠENÍ SPOLEHLIVOSTI PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/38 lDva hlavní cíle paralelismu v diskových systémech ●zvýšení propustnosti vyvážením zátěže malými přístupy ●paralelizace velkých přístupů s cílem zkrácení doby odpovědi lZvýšení přenosové rychlosti paralelním zápisem do více disků (dělení, striping) ●bit-level striping ●dělení bitů každého bytu mezi samostatné disky ●v poli 8 disků se zapisuje bit i každého bytu na disk i ●čtení dat probíhá 8x rychleji než z jednoho disku ●vystavení je delší než v případě jednoho disku ●dnes se bit-level striping de facto už nepoužívá ●blok-level striping ●systém s n disky, blok souboru i se zapisuje na disk (i mod n) + 1 ●požadavky na různé bloky se mohou realizovat paralelně, jestliže bloky leží na různých discích ●požadavek na dlouhou posloupnost bloků může použít všechny disky paralelně RAID: ZVÝŠENÍ VÝKONU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/38 lRAID Level 0: Žádná redundance, jen souběžnost lRAID Level 1: Spolehlivost dosažená zrcadlením disků lRAID Level 2: Hamming code error correction lRAID Level 3: 1 kontrolní disk na skupinu, dělení bitů lRAID Level 4: Nezávislé operace read/write, dělení bloků lRAID Level 5: Data/parity přes všechny disky (více souběžný přístup) lRAID Level 6: Odolnost při více než jedné poruše disku ÚROVNĚ RAID, PŘEHLED PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ schema-raid-levels.png (a) RAID 0: non-redudant striping. (b) RAID1: mirrored disks. (c) RAID 2: memory-style error-correcting codes. (d) RAID 3: bit-interleaved parity. (e) RAID 4: block-interleaved parity. (f) RAID 5: block-interleaved distributed parity. (g) RAID 6: P + Q redundacy. ‹#›/38 BĚŽNĚ POUŽÍVANÝ RAID PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ 325px-RAID_1_svg 325px-RAID_0_svg Zdroj: en.wikipedia.org ‹#›/38 lVětšina OS pracuje s vyměnitelnými disky (např. disketami, ZIP disky) stejně jako s pevnými disky ●nový svazek je formátován a na disku se generuje prázdný souborový systém lPásky ●jsou prezentované jako „holé“ (raw) paměťové médium ●aplikace na páskách nemají k dispozici souborový systém ●otevírají celý páskový mechanismus jako zařízení ●páskové mechanismy se vesměs nesdílejí, jsou dedikované konkrétní aplikaci ●OS nepodporují na páskách souborové systémy, aplikace musí samy řešit jak používat bloky dat ●pásku pak obvykle může používat pouze aplikace, pro kterou byla páska vytvářena (protože jako jediná zná strukturu dat na pásce) API PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/38 CENA MB RAM (1981-2004) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ Dnes: asi $0.025/MB (4GB) 1280 640 320 160 80 40 20 10 5 2 1.2 0.8 1982 1984 1986 1988 1990 1992 1994 1996 1998 2000 2002 2004 64 KB 16 KB 256 KB 1 MB 4 MB simm 32 MB 128 MB 512 MB Year $ / MB ‹#›/38 CENA MB PEVNÝCH DISKŮ (1981-2004) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ Dnes: asi 0,0001$/MB (1TB) 1982 1984 1986 1988 1990 1992 1994 1996 1998 2000 2002 2004 Year $ / MB 0.004 0.001 0.02 0.05 0.2 0.5 2 5 20 50 100 10 MB 20 MB 120 MB 1.2 GB 2 GB 19 GB 45 GB 80 GB ‹#›/38 CENA MB PÁSEK (1981-2004) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ Dnes: asi 0,0001$/MB (0.8TB) 0.001 0.025 0.1 0.5 2 8 20 40 1986 1988 1990 1992 1994 1996 1998 2000 2002 2004 1984 $ / MB Year 60 MB 120 MB 1.2 GB 4 GB 72 GB 320 GB ‹#›/38 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Í