1/38
PB153
OPERAČNÍ SYSTÉMY
A JEJICH ROZHRANÍ
Vnějšípaměti
11
2/38
 Primární paměti
● nejrychlejší
● energeticky závislé
● Cache, hlavní (operační) paměť
 Sekundární paměti
● středně rychlé
● energeticky nezávislé
● Také nazývané „on-line storage“
● flash disky, magnetické disky
 Terciá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
3/38
MAGNETICKÉ DISKY
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
platter
rotation
read-write
head
arm assembly
spindletrack t
sector s
cylinder c
arm
4/38
 Diskové mechanismy se adresují jako velká
1-dimensionální pole logických bloků
● logické bloky jsou nejmenší jednotkou přenosu dat
 1-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Í
5/38
 OS je odpovědný za efektivní používání hardware
● pro disky: co nejrychlejší přístup a co největší šířka pásma
 Doba 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
 Minimalizace doby vystavení
● doba vystavení vystavovací vzdálenosti
● řeší plánování činnosti disku
 Rotační zpoždění
● shora omezeno konstantou
 Šíř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Í
6/38
 Existuje celá řada algoritmů pro plánování
přístupu na disk.
● „Disk scheduling“
 Příklad: vzorová fronta požadavků na přístup k
disku (máme cylindry 0-199).
98, 183, 37, 122, 14, 124, 65, 67
Hlavička disku vystavena na pozici 53
PLÁNOVÁNÍ DISKU
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
7/38
 Celkem přesun o 640 cylindrů
FCFS
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
14 37 53 6765 98 122 124 183 199
head starts at 53
queue = 98, 183, 37, 122, 14, 124, 65, 67
8/38
 Z fronty požadavků vybírá ten požadavek, který
vyžaduje minimální dobu vystavení od současné
pozice hlavičky
 SSTF (shortest seek time first) algoritmus je
variantou algoritmu SJF (shortest job first); může
způsobit stárnutí požadavků.
 Náš příklad vyžaduje přesun o 236 cylindrů
SSTF
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
9/38
SSTF
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
14 37 53 6765 98 122 124 183 199
head starts at 53
queue = 98, 183, 37, 122, 14, 124, 65, 67
10/38
 Hlavič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.
 Někdy nazývané algoritmus typu výtah (elevator).
 Náš příklad vyžaduje přesun o 208 cylindrů.
SCAN
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
11/38
SCAN
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
0 14 37 53 6765 98 122 124 183 199
head starts at 53
queue = 98, 183, 37, 122, 14, 124, 65, 67
12/38
 Poskytuje jednotnější čekací dobu než SCAN
 Hlavič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.
 Cylindry považuje za kruhový seznam, který za
posledním cylindrem pokračuje opět prvním
cylindrem.
C-SCAN
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
13/38
C-SCAN
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
14 37 53 6765 98 122 124 183 199
head starts at 53
queue = 98, 183, 37, 122, 14, 124, 65, 67
14/38
 Obdoba C-SCAN, ale hlavička jen potud do kraje,
pokud existují požadavky.
 Pak se vrací zpět
C-LOOK
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
15/38
C-LOOK
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
14 37 53 6765 98 122 124 183 199
head starts at 53
queue = 98, 183, 37, 122, 14, 124, 65, 67
16/38
 SSTF je přirozený, má přirozené chápání
 SCAN a C-SCAN jsou vhodnější pro těžkou zátěž
disku
 Výkon závisí na počtu a typech požadavků
 Požadavky na disk mohou být ovlivněny metodami
organizace souborů v souborovém systému
 Plánovací algoritmus by měl být napsán jako
samostatný modul, aby plánovací algoritmus OS bylo
možné zaměňovat
 Častá implicitní volba bývá SSTF nebo LOOK
VÝBĚR ALGORITMU
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
17/38
 U moderních disků nemusí být známé mapování
logických bloků na fyzické adresy
 Disku předáme skupinu požadavků a disk si
pořadí optimalizuje sám
 OS 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Í
18/38
 K dispozici několik plánovacích algoritmů
 Fronty v řadiči disku mohou měnit pořadí od OS
● Fronta na desítky až stovky požadavků
 Algoritmy
● 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
19/38
 Nemění pořadí požadavků
 Jen 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Í
20/38
 Vychází z algoritmu SCAN
 Přidává deadline (do kdy má být požadavek
vyřízen)
 Po 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.
 Upřednostňuje čtení před zápisem
DEADLINE
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
21/38
 Jako 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) …
 Umožňuje i krátké přesuny zpět
● Penalizuje dvojnásobnou vzdáleností
 Neodlišuje požadavky čtení a zápisu
 Odlišuje asynchronní požadavky od synchronních
 Neobjevuje se v linuxovém jádře od verze 2.6.33
ANTICIPATORY SCHEDULER (AS)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
22/38
 Snaží se být spravedlivý k procesům
 Každý proces dostává určitý časový díl (slice) kdy má
exkluzivní přístup pro synchronní požadavky
 Parametry
● slice_sync – délka slice v ms (bere v úvahu I/O prioritu
procesu)
● quantum – počet požadavků
 17 front (pro každou prioritu jedna) pro asynchronní
požadavky
 Kaž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Í
23/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
24/38
 Pří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)
25/38
 Dva aspekty
● šířka pásma, bandwidth
● zpoždění, latency
 Šíř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Í
26/38
 Zpož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
 Ní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ů
 Vymě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Í
27/38
 Pevný disk je asi spolehlivější než vyměnitelný
disk nebo páska
 Optický disk je asi spolehlivější než magnetický
páska
 Padnutí hlav v pevném disku obvykle znamená
zničení dat
 Porucha pásky nebo optického disku obvykle
neznamená zničení všech dat
SPOLEHLIVOST
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
28/38
 Operační paměť je mnohem dražší než disková
paměť
 Cena MB na pevném disku je srovnatelná s cenou
MB na pásce (dříve pásky levnější)
 Kapacity magnetických pásek nedržely v posledních
letech krok s nárůstem kapacit pevných disků
 Terciá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Í
29/38
 RAID: 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ů
 Pravdě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é
 Pů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Í
30/38
 Redundance
● nadbytečnost, doplňková informace použitelná pro obnovu
informace po poruše (disku)
 Zrcadlení (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Í
31/38
 Dva 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
 Zvýš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Í
32/38
RAID Level 0:
Žádná redundance, jen souběžnost
RAID Level 1:
Spolehlivost dosažená zrcadlením disků
RAID Level 2:
Hamming code error correction
RAID Level 3:
1 kontrolní disk na skupinu, dělení bitů
RAID Level 4:
Nezávislé operace read/write, dělení bloků
RAID Level 5:
Data/parity přes všechny disky
(více souběžný přístup)
RAID 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Í
(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.
33/38
BĚŽNĚ POUŽÍVANÝ RAID
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
Zdroj: en.wikipedia.org
34/38
 Vě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
 Pá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Í
35/38
CENA MB RAM (1981-2004)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
Dnes: asi $0.01/MB (16GB)
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
36/38
CENA MB PEVNÝCH DISKŮ (1981-2004)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
Dnes: asi 0,00005$/MB (3TB)
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
37/38
CENA MB PÁSEK (1981-2004)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
Dnes: asi 0,00002$/MB (3TB)
0.001
0.025
0.1
0.5
2
8
20
40
1986 1988 1990 1992 1994 1996 1998 2000 2002 20041984
$ / MB
Year
60 MB
120 MB
1.2 GB
4 GB
72 GB
320 GB
38/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Í