37

Operaˇ cn´ı syst´ emy

Souborov´ e syst´ emy Petr Krajˇca

Katedra informatiky Univerzita Palack´eho v Olomouci

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

1 / 37

I/O: zaˇr´ızen´ı z´asadn´ı sloˇzka Von Neumannova architektury r˚ uzn´e pohledy na I/O zaˇr´ızen´ı: inˇzen´yrsk´y (dr´aty, motory) vs. program´atorsk´y (rozhran´ı) r˚ uzn´e rychlosti od 10 B/s (kl´avesnice) po 1 GB/s (PCI Express) r˚ uzn´e druhy pˇr´ıstupu Blokov´ a zaˇr´ızen´ı data jsou pˇren´aˇsena v bloc´ıch stejn´e velikosti (typicky 512 B aˇz 32 kB) moˇzn´e nez´avisle adresovat/zapisovat/ˇc´ıst data po jednotliv´ych bloc´ıch HDD, SSD, CD, DVD, p´aska?, . . . Znakov´ a zaˇr´ızen´ı proud znak˚ u/byt˚ u (nelze se posouvat) kl´avesnice, myˇs, tisk´arna, termin´al Ostatn´ı nespadaj´ı ani do jedn´e z kategori´ı hodiny (pˇreruˇsen´ı), grafick´e rozhran´ı (mapovan´a pamˇet’) Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

2 / 37

Blokov´a zaˇr´ızen´ı: HDD disk – plotny, stopy (=⇒ cylindry), sektory (typicky 512 B) p˚ uvodnˇe se adresovaly sektory ve formˇe CHS (praktick´a omezen´ı, mj. velikost disku) nahrazeno LBA (logical block addressing) low-level form´at =⇒ hlaviˇcka + data + ECC pˇripojen´e typicky pˇres (P)ATA, SATA rychlost pˇr´ıstupu ovlivˇ nuje nastaven´ı hlaviˇcky na pˇr´ısluˇsn´y cylindr (seek time; nejz´asadnˇejˇs´ı) rotace (nastaven´ı sektoru) pod hlaviˇcku pˇrenosov´a rychlost

nez´avisl´a cache (hromad´ı poˇzadavky =⇒ eliminuje pˇresuny)

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

3 / 37

HDD: optimalizace v´ıc poˇzadavk˚ u se bude ˇreˇsit najednou m´ısto sektor˚ u se pracuje s clustery sektor˚ u (velikost podle velikosti disku) cache disku cache OS =⇒ spoleˇcnˇe s VM; cachuje se na u ´rovni FS odpov´ıdaj´ıc´ı algoritmy – LRU, LFU, . . . , jejich kombinace zjednoduˇsen´ı OS =⇒ otevˇren´ı souboru namapov´an´ı do cache; demand paging write-through cache: data se po zapsan´ı zapisuj´ı pˇr´ımo na disk write-back cache: data se zapisuj´ı aˇz po ˇcase (moˇznost optimalizac´ı z´apisu) vynucen´ı uloˇzen´ı cache (flush) sekvenˇcn´ı ˇcten´ı read-ahead – data se naˇc´ıtaj´ı dopˇredu free-behind – proaktivnˇe uvolˇ nuje str´anky, pˇri naˇc´ıt´an´ı nov´ych

,,spolupr´ace” – OS & HW (spoon-feeding); datab´aze

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

4 / 37

Blokov´a zaˇr´ızen´ı: RAID SLED: Single Large Expensive Disk RAID: Redundant Array of Inexpensive/Independent disks Mean Time to Failure: M T T Fpole =

M T T Fdisk N

hardware vs. software RAID RAID-0 (stripping): zv´yˇsen´ı propustnosti, probl´em selh´an´ı poˇr´ad existuje RAID-1 (mirroring): zv´yˇsen´ı propustnosti (kopie), ˇreˇs´ı probl´em selh´an´ı RAID-2: dˇel´ı data na po bitech; Hamming˚ uv k´ od; disk pro paritu (napouˇz´ıv´a se) RAID-3: dˇel´ı data po bytech; XOR; disk pro paritu (z´atˇeˇz); zvl´adne v´ypadek jednoho disku RAID-4: jako RAID-3 pouˇz´ıv´a bloky (z´atˇeˇz) RAID-5: jako RAID-4; paritn´ı bloky jsou ale distribuov´any RAID-6: jako RAID-5; Reed-Solomon k´ od; dva paritn´ı bloky; v´ypadek aˇz dvou disk˚ u kombinace: RAID-0+1, RAID-1+0

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

5 / 37

Blokov´a zaˇr´ızen´ı: SSD, CD, DVD Solid-state Drives flash pamˇeti; rozhran´ı jako HDD bez rotuj´ıc´ıch ˇc´ast´ı =⇒ rychl´y pˇr´ıstup (v´yraznˇe v´ıc IOPS) problematick´y z´apis omezen´ı na poˇcet pˇreps´an´ı jednoho m´ısta pamˇet’ mus´ı b´yt nejdˇr´ıv vymaz´ana ˇcasto lze zapisovat po str´ank´ach, ale mazat je nutn´e po bloc´ıch =⇒ rychlˇejˇs´ı z´apis neˇz pˇrepis

wear levelling ˇz´adn´y – data se pˇrepisuj´ı na m´ıstˇe dynamick´y – zmˇenˇen´e bloky oznaˇceny jako neplatn´e a data zaps´any jinam (USB) statick´y – jako dynamick´y, ale pˇresouv´a i nezmˇenˇen´e data (SSD) hardwarov´a vs. softwarov´a implementace (JFFS2, LogFS)

garbage collection + TRIM

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

6 / 37

Compact Disc (CD) data um´ıstˇena ve spir´ale =⇒ pomal´e vyhled´av´an´ı; rychl´e sekvenˇcn´ı ˇcten´ı vysok´a redundance dat symbol - k zakod´av´an´ı 8 b se pouˇz´ıv´a 14 b 42 symbol˚ u tvoˇr´ı r´amec o velikosti 588 b (192 b data, zbytek ECC) jeden sektor obsahuj´ıc´ı 2048 B dat je tvoˇren 98 r´amci (zahrnuje 16 B hlaviˇcku a 288 B pro ECC) efektivita 28%! DVD, BR-D analogicky jako CD

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

7 / 37

Souborov´e syst´emy: Motivace potˇreba uchov´avat vˇetˇs´ı mnoˇzstv´ı dat (prim´arn´ı pamˇet’ nemus´ı dostaˇcovat) data mus´ı b´yt perzistent´ı (mus´ı pˇreˇz´ıt ukonˇcen´ı procesu) k soubor˚ um mus´ı b´yt umoˇznˇen soubˇeˇzn´y pˇr´ıstup =⇒ ˇreˇsen´ı v podobˇe ukl´ad´an´ı dat na vnˇejˇs´ı pamˇet’ (napˇr. disk) =⇒ data ukl´ad´ana do soubor˚ u tvoˇr´ıc´ı souborov´y syst´em (File System/FS) soubor jako proud byt˚ u (doprov´azen doplˇ nuj´ıc´ımi informacemi) souborov´y syst´em jako abstrakce (odst´ınˇen´ı od implementaˇcn´ıch detail˚ u) =⇒ Unix

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

8 / 37

Operace se soubory (1/2) create – vytvoˇren´ı souboru write/append – z´apis do souboru (na konec, popˇr. pˇrepis); souvisl´y bloky vs. postupn´y z´apis read – ˇcten´ı ze souboru (do pˇrichystan´eho bufferu) seek – zmˇena pozice erase – odstranˇen´ı souboru (uvolnˇen´ı m´ısta); (link & unlink) truncate – zkr´at´ı dan´y soubor na poˇzadovanou velikost ne vˇsechny souborov´e syst´emy (a zaˇr´ızen´ı podporuj´ı vˇsechny operace); napˇr. CD+ISO 9660 operace dostateˇcnˇe obecn´e =⇒ pˇr´ıstup k zaˇr´ızen´ım (disk, kl´avesnice, termin´al); ovl´ad´an´ı syst´emu =⇒ lze pouˇz´ıvat existuj´ıc´ı n´astroje pro pr´aci se soubory napˇr. vyuˇz´ıt´ı pˇri spr´avˇe OS (procfs, devfs, sysfs) roury, FIFO Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

9 / 37

Operace se soubory (2/2) open – otevˇre soubor, aby s n´ım ˇslo manipulovat pˇres popisovaˇc (file descriptor, file handle) ukazatel na strukturu v j´adˇre pˇr´ıstup pˇres jm´eno neefektivn´ı ,,soubory” nemus´ı m´ıt jm´eno jeden soubor m˚ uˇze b´yt otevˇren v´ıcekr´at (v´ıce ukazatel˚ u na pozici v souboru) close – uzavˇre soubor get/set attribute – pr´ace s attributy (metadaty) Typy soubor˚ u bˇeˇzn´e soubory, adres´aˇre, (Unix: speci´aln´ı soubory pro blokov´e a znakov´e zaˇr´ızen´ı) bin´arn´ı vs. ASCII soubory (ukonˇcen´ı ˇr´adk˚ u)

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

10 / 37

Organizace soubor˚ u (1/3) soubory jsou rozliˇsov´any podle nazv˚ u (ˇcasto specifick´e pro dan´y OS nebo FS) rozliˇsov´an´ı velk´ych a mal´ych p´ısmen (Unix vs. MS-DOS a Windows) MS-DOS: poˇzadavek na jm´eno souboru ve tvaru 8+3 (jm´eno + pˇr´ıpona) rozliˇsen´ı obsahu souboru podle pˇr´ıpony (Windows–asociace s konkr´etn´ı aplikac´ı) magick´a ˇc´ısla (Unix–podle u ´vodn´ıch byt˚ u je moˇzn´e identifikovat typ) podle metadat (informace o souboru jsou uloˇzeny vedle souboru, jako souˇc´ast FS)

typicky se soubory organizuj´ı do adres´aˇr˚ u (sloˇzek) kaˇzd´y adres´aˇr m˚ uˇze obsahovat bˇeˇzn´e (popˇr. speci´aln´ı) soubory i dalˇs´ı adres´aˇre =⇒ stromov´a struktura (pouˇz´ıvaly se i omezenˇejˇs´ı syst´emy – ˇz´adn´e, jedna, dvˇe u ´rovnˇe) v z´apisu cesty ve stromˇe se pouˇz´ıv´a lom´ıtek Unix: /usr/local/bin Windows: \usr\local\bin

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

11 / 37

Organizace soubor˚ u (2/3) k pˇr´ıstupu k souboru se pouˇz´ıvaj´ı absolutn´ı cesty /foo/bar/baz.dat relativn´ı cesty foo/bar.dat =⇒ kaˇzd´y proces m´a aktu´aln´ı adres´aˇr

operace s adres´aˇri: Create, Delete, OpenDir, CloseDir, ReadDir, Rename speci´aln´ı adres´aˇre v kaˇzd´em adres´aˇri ,,.” a ,,..” (aktu´aln´ı adres´aˇr, nadˇrazen´y adres´aˇr) =⇒ nutn´e pro navigaci v hierarchii adres´aˇr˚ u struktura nemus´ı b´yt hierarchick´a =⇒ obecn´y graf (acyklick´y, cyklick´y) hardlink – ukazatel na soubor (jeho tˇelo/obsah) symlink – soubor je odkaz na jin´y soubor (specifikovan´y cestou)

v Unixech bˇeˇzn´e, ve Windows delˇs´ı dobu (ale chybˇelo rozhran´ı)

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

12 / 37

Dˇelen´ı disku kaˇzd´y fyzick´y disk se skl´ad´a z jedn´e nebo v´ıce logick´ych ˇc´ast´ı (partition; odd´ıl); popsan´e pomoc´ı partition table dan´eho disku v kaˇzd´e partition m˚ uˇze existovat souborov´y syst´em (oznaˇcovan´y jako svazek) v Unixech je kaˇzd´y svazek pˇripojen (mounted) jako adres´aˇr (samostatn´y svazek pro /, /home, /usr) =⇒ Virtual File System (VFS) vyuˇzit´ı abstrakce =⇒ umoˇzn ˇuje kombinovat r˚ uzn´e FS do jednoho VFS specializovan´e FS pro spr´avu syst´emu (procfs, sysfs) =⇒ API OS moˇznost pˇripojit bˇeˇzn´y soubor jako svazek (i svazek je soubor) s´ıt’ov´e disky (NFS, CIFS)

ve Windows jednotliv´e svazky oznaˇceny (a:, b:, c:, . . . ); ale funguje i mountov´an´ı (preferovan´y jeden svazek pro vˇse)

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

13 / 37

Struktura soubor˚ u ˇcasto je soubor ch´ap´an jako proud byt˚ u sekvenˇcn´ı vs. n´ahodn´y pˇr´ıstup nˇekdy m˚ uˇze b´yt v´yhodn´a jin´a struktura rozdˇelen´ı jednoho souboru na v´ıce proud˚ u (napˇr. spoustiteln´y soubor – k´od + data) potˇrebn´a podpora ze strany FS i OS =⇒ streamy v NT spoleˇcnˇe s daty jsou k souboru pˇripojena metadata (atributy) vlastn´ık souboru pˇr´ıstupov´a pr´ava velikost souboru pˇr´ıznaky (skryt´y, archivace, spustiteln´y, syst´emov´y) ˇcas vytvoˇren´ı, ˇcas posledn´ıho pˇr´ıstupu

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

14 / 37

Pˇr´ıstup k soubor˚ um Zamyk´ an´ı sd´ılen´y pˇr´ıstup omezen´ı pˇr´ıstupu – souˇcasn´e ˇcten´ı (zabr´anˇen´ı z´apisu) S´ emantika konzistence chov´an´ı syst´emu pˇri souˇcasn´e pˇr´ıstupu v Unixech zmˇeny okamˇzitˇe viditeln´e immutable-shared-file – pokud je soubor sd´ılen´y nejde jej mˇenit (jednoduch´a implementace) Pr´ ava pˇr´ıstupu ACL (access control list) seznam uˇzivatel˚ u a jejich pˇr´ıstupov´ych pr´av (3 bity pro kaˇzd´y pˇr´ıstup) udrˇzovat seznam m˚ uˇze b´yt netrivi´aln´ı (moˇznost doplnit role) Denied ACL

UNIX ,,ACL” – pro vlastn´ıka, skupinu, zbytek Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

15 / 37

Implementace souborov´ych syst´em˚ u: oˇcek´avan´e vlasnosti (budeme pˇredpokl´adat souborov´e syst´emy pro pr´aci s disky) schopnost pracovat se soubory a disky adekv´atn´ı velikosti efektivn´ı pr´ace s m´ıstem (evidence voln´eho, n´ızk´a fragmentace) rychl´y pˇr´ıstup k dat˚ um eliminace roztrouˇsen´ı dat na disku odolnost proti poˇskozen´ı pˇri p´adu syst´emu (v´ypadku nap´ajen´ı) =⇒ rychl´e zotaven´ı Dalˇs´ı vlastnosti snapshoty komprese dat moˇznost zvˇetˇsovat/zmenˇsovat FS za bˇehu kontroln´ı souˇcty defragmentace za bˇehu spr´ava opr´avnˇen´ı atd. Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

16 / 37

Struktura disku pro jednoduchost pˇredpokl´ad´ame, ˇze struktura disku je line´arn´ı MBR – master boot record: informace o rozdˇelen´ı disku na svazky + zavadˇeˇc Tan. 400 sektor disku – obvykle velikost 512 B =⇒ pracuje se s vˇetˇs´ımi bloky 1-32 kB (ˇcasto 4 kB) =⇒ optim´aln´ı velikost bloku? (rychlost vs. u ´spora m´ısta) jednotliv´e svazky obsahuj´ı souborov´y syst´em (vlastn´ı organizace dat) VFS – virtualn´ı souborov´y syst´em (Sta. 567) je potˇreba si udrˇzovat informace o jednotliv´ych souborech (FCB, inody) cache

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

17 / 37

Alokace diskov´eho prostoru Alokace souvisl´ ych blok˚ u soubory jsou ukl´adany na disk za sebe v souvisl´ych bloc´ıch rychl´e sekvenˇcn´ı ˇcten´ı, probl´em s uvolnˇen´ymi soubory CD? Soubor jako spojov´ y seznam FS je rozdˇelen´y na bloky kaˇzd´y blok ma ukazatel na n´asleduj´ıc´ı rychl´e sekvenˇcn´ı ˇcten´ı; problematick´y n´ahodn´y pˇr´ıstup (nutnost ˇc´ıst vˇse) + poˇskozen´ı disku varianta: uchov´av´an´ı odkaz˚ u na bloky ve spec. tabulce (FAT) Indexov´ a alokace soubor si nese informaci o sv´em uloˇzen´ı v bloc´ıch (struktura na zaˇc´atku souboru) probl´em s velk´ymi soubory =⇒ v´ıce´ urovˇ nov´e tabulky Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

18 / 37

Evidence voln´eho m´ısta je potˇreba udrˇzovat informace o voln´em m´ıstˇe pouˇzit´ı spojov´eho seznamu voln´ych blok˚ u (moˇzn´e pouˇz´ıt voln´e bloky); jako u soubor˚ u vylepˇsen´ı =⇒ rozsahy voln´ych blok˚ u (probl´em pˇri fragmentaci) bitmapy – kaˇzd´y bit ud´av´a, jestli je dan´y blok voln´y (nutn´e m´ısto – obvykle m´enˇe neˇz promile kapacity) Pˇridˇ elov´ an´ı voln´ eho m´ısta je ˇz´adouc´ı zapisovat data do souvisl´ych voln´ych blok˚ u =⇒ eliminace pˇresun˚ u hlaviˇcky heuristick´e algoritmy (sloˇzit´e na testov´an´ı) problematick´e zaplnˇen´ı disku nad 95 % a souˇcasn´e zapisov´an´ı v´ıce velk´ych soubor˚ u

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

19 / 37

Adres´aˇre organizace adres´aˇr˚ u =⇒ vliv na v´ykon r˚ uzn´e struktury spojov´y seznam – jednoduch´a implementace; vˇetˇs´ı sloˇzitost hash tabulka (komplikace s implementac´ı) varianty B-strom˚ u (ˇcast´e u modern´ıch FS)

um´ıstˇen´ı informac´ı o souborech souˇc´ast adres´aˇre souˇc´ast souboru (UNIX) =⇒ probl´em: listov´an´ı adres´aˇre × moˇznost m´ıt soubor ve v´ıce nebo ˇz´adn´em adres´aˇri

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

20 / 37

Cache a selh´an´ı syst´emu kv˚ uli rychlejˇs´ımu pˇr´ıstupu nejsou ˇcasto data zapisov´ana pˇr´ımo na disk =⇒ nejdˇr´ıv do cache pˇri v´ypadku (p´ad syst´emu, v´ypadek nap´ajen´ı) nemus´ı b´yt data ve write-back cache zaps´ana =⇒ poˇskozen´ı FS potˇreba opravit FS (fsck, chkdsk) =⇒ ˇcasovˇe n´aroˇcn´e pˇr´ıpadn´e naruˇsen´ı syst´emu jeden uˇzivatel zap´ıˇse data na disk a smaˇze je druh´y uˇzivatel vytvoˇr´ı velk´y soubor a potom zapsan´ı metadat vyvol´a v´ypadek po restartu ˇcte data prvn´ıho uˇzivatele

ˇ sen´ı Reˇ synchronn´ı z´apis =⇒ zpomalen´ı, konzistence nemus´ı b´yt zaruˇcena soft updates – uspoˇr´ad´an´ı z´apis˚ u podle urˇcit´ych pravidel (*BSD) ˇzurn´alov´an´ı

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

21 / 37

ˇ alov´an´ı Zurn´ data se zapisuj´ı v transakc´ıch (pˇresun FS z jednoho konzistentn´ıho stavu do druh´eho) nejdˇr´ıv se transakce zap´ıˇse do ˇzurn´alu (logu) po zaps´an´ı do ˇzurn´alu je z´aznam oznaˇcen spec. znaˇckou a data se m˚ uˇzou zapsat na disk po zaps´an´ı na disk je z´apis z ˇzurn´alu odstranˇen pˇri pˇripojen´ı FS se kontroluje stav ˇzurn´alu z´apis z´aznamu do ˇzurn´alu nebyl dokonˇcen (transakce se neprovede) pˇr´ıpadnˇe, transakse se provede podle informac´ı ze ˇzurn´alu

ˇcasto se ˇzurn´aluj´ı jen metadata ˇzurn´al je cyklick´y; pˇri zaplnˇen´ı se zap´ıˇs´ı/uvoln´ı data ze zaˇc´atku je potˇreba atomick´ych z´apis˚ u na disk cache & buffery komplikuj´ı implementaci

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

22 / 37

FAT souborov´y syst´em pro MSDOS (pˇreˇzil se aˇz do Windows ME) jednoduch´y design soubory se jm´eny ve tvaru 8.3, nepodporuje opr´avnˇen´ı nem´a metody proti poˇskozen´ı dat disk rozdˇelen´y na bloky (clustery) soubory pops´any pomoc´ı File Allocation Table (FAT) – spojov´y seznam disk rozdˇelen na u ´seky: bootsector (rezervovan´a oblast) + informace o svazku 2× FAT koˇrenov´y adres´aˇr data

adres´aˇre jako soubory; koˇrenov´y adres´aˇr je vytvoˇren pˇri inicializaci p˚ uvodn´ı FAT nepodporoval adres´aˇre

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

23 / 37

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

24 / 37

FAT: varianty FAT12, 16, 32: podle velikosti clusteru; (max. kapacity – 32 MB, 2 GB, 8 TB) dalˇs´ı omezen´ı na velikost souboru Virtual FAT podpora dlouh´ych jmen (LFN) aˇz 256 znak˚ u soubor m´a dvˇe jm´ena – dlouh´e a ve tvaru 8.3 dlouh´a jm´ena uloˇzena jako dalˇs´ı z´aznamy v adres´aˇri exFAT urˇcen pro flash pamˇeti podpora vˇetˇs´ıch disk˚ u (512 TB/64 ZB) podpora v novˇejˇs´ıch Windows (povednˇe Windows CE 6) zat´ıˇzen patenty

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

25 / 37

UFS: Unix File System (1/2) v r˚ uzn´ych variant´ach pˇr´ıtomn´y v unixov´ych OS – *BSD, Solaris, System V, Linux (ext[234]) disk se skl´ad´a: bootblock – m´ısto pro zavadˇeˇc OS superblock – informace o souborov´em syst´emu m´ısto pro inody m´ısto pro data

Inoda struktura popisuj´ıc´ı soubor informace o souboru typ souboru, vlastn´ıka (UID, GID), opr´avnˇen´ı (rwx) ˇcasy (vytvoˇren´ı, pˇr´ıstup) poˇcet ukazatel˚ u, poˇcet otevˇren´ych popisovaˇc˚ u

informace o uloˇzen´ı dat patn´act ukazatel˚ u na bloky na disku bloky 0-11 ukazuj´ı na bloky dat blok 12 – nepˇr´ım´y blok 1. u ´rovnˇe blok 13 – nepˇr´ım´y blok 2. u ´rovnˇe blok 14 – nepˇ r ´ ım´ y blok 3. u ´rovnˇe KMI/YOS: Pˇredn´aˇska V. Petr Krajˇ ca (UP)

12. prosinec, 2014

26 / 37

Inode

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

27 / 37

UFS: Unix File System (2/2) struktura inody umoˇzn ˇuje m´ıt ˇr´ıdk´e soubory adres´aˇr je soubor obsahuj´ıc´ı sekvenci dvojic (jm´eno souboru, ˇc´ıslo inody) k evidenci voln´eho m´ısta a inod se pouˇz´ıvaj´ı bitmapy svazek m˚ uˇze b´yt rozdˇeln´y na nˇekolik tzv. skupin – kaˇzd´a maj´ıc´ı vl´astn´ı inody, bitmapy, atd. + kopie superblocku =⇒ slouˇcen´ı souvisej´ıc´ıch dat =⇒ eliminace pˇresun˚ u hlaviˇcky velikost bloku =⇒ rychlejˇs´ı pˇr´ıstup k vˇetˇs´ım soubor˚ um vs. nevyuˇzit´e m´ısto moˇznost rozdˇelit blok na nˇekolik fragment˚ u konkr´etn´ı detaily se mohou liˇsit napˇr. FreeBSD pˇrid´av´a moˇznost dˇelat snapshoty

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

28 / 37

Inode

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

29 / 37

FS v Linuxu Linux nem´a jeden hlavn´ı FS nejˇcastˇeji se pouˇz´ıv´a: Ext2/3/4 n´azev souboru m˚ uˇze m´ıt aˇz 256 znak˚ u (s vyj´ımkou znak˚ u \ a \0) vych´az´ı z UFS ext2: maxim´aln´ı velikost souboru 16 GB–2 TB, disku: 2 TB – 16 TB ext3: pˇrid´av´a ˇzurn´al (3 u ´rovnˇe – journal, ordered, unordered), bin´arnˇe kompatibiln´ı s ext2 ext4: pˇrid´av´a vylepˇsen´ı maxim´aln´ı velikost souboru 16 TB–2 TB, disku: 1 EB podpora extent˚ u (m´ısto mapov´an´ı blok˚ u je moˇzn´e alokovat blok aˇz do velikosti 128 MB) optimalizace alokac´ı lepˇs´ı pr´ace s ˇcasem

dalˇs´ı FS: ReiserFS, BtrFS, JFS, XFS, . . .

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

30 / 37

´ NTFS: Uvod hlavn´ı souborov´y syst´em Windows NT koˇreny v OS/2 a jeho HPFS (vyv´ıjen od roku 1993) velikost clusteru podle velikosti svazku (512 B–4 KB) =⇒ max. velikost disku 256 TB max. velikost souboru 16 TB oproti FAT (souborov´emu syst´emu W9x) ochrana pˇred poˇskozen´ım + pr´ava ˇzurn´alov´an´ı a transakce podpora v´ıce stream˚ u v jednom souboru dlouh´e n´azvy (255 znak˚ u) + unicode podpora standardu POSIX; hardlinky, symlinky komprese a ˇr´ıdk´e soubory Adres´ aˇre opˇet technicky soubory; jm´ena v B+ stromech nˇekter´a metadata soubor˚ u jsou souˇc´ast´ı adres´aˇre Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

31 / 37

NTFS: Struktura disku (1/2) na zaˇc´atku disku: boot sector 12 % MFT (Master File Table); 88 % data soubor˚ u MFT je soubor popisuj´ıc´ı vˇsechny soubory na FS (MFT je taky soubor) MFT se skl´ad´a ze z´aznam˚ u o velikosti 1 KB kaˇzd´y soubor je pops´an t´ımto z´aznamem 32 prvn´ıch soubor˚ u m´a speci´aln´ı urˇcen´ı ($MFT, $MFTMirr, $LogFile, $Volume, $Bitmap, $Boot, $BadClus, . . . ) informace o souborech vˇcetnˇe jm´ena, ˇcas˚ u, atd. uloˇzeny jako z´aznam v MFT jako dvojice atribut-hodnota tˇelo souboru je taky atribut =⇒ uniformn´ı pˇr´ıstup; moˇznost uloˇzit mal´e soubory pˇr´ımo do MFT alternativn´ı proudy =⇒ opˇet atributy v pˇr´ıpadˇe potˇreby m˚ uˇze jeden soubor zabrat v´ıc z´aznam˚ u v MFT pˇr´ıpadnˇe lze pouˇz´ıt m´ısto mimo MFT (rezidentn´ı a nerezidentn´ı atributy) Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

32 / 37

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

33 / 37

NTFS: Struktura disku (2/2) data v souboru jsou pops´ana pomoc´ı (atributu) tabulky mapuj´ıc´ı VCN (virtual cluster number) na LCN (logical cluster number) VCN – ˇc´ıslo clusteru v souboru (indexov´ano od nuly) LCN – ˇc´ıslo clusteru ve svazku kaˇzd´y z´aznam v tabulce je ve tvaru: VCN, LCN, poˇcet cluster˚ u, napˇr. VCN LCN poˇcet 0 42 4 4 123 8 32 456 15 Komprese ˇr´ıdk´e soubory moˇznost transparentnˇe komprimovat obsah (vˇzdy po 16 clusterech) =⇒ bloky dat zarovn´any na 16 cluster˚ u; pokud zab´ır´a m´ıˇ n m´ısta, je komprimov´an ˇcten´ı i z´apis prov´ad´ı (de)kompresi (LZ77) =⇒ dopad na v´ykon Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

34 / 37

ISO-9660 souborov´y syst´em pro CD-ROM; podpora vˇsech OS z´apis jen jednou; sekvenˇcn´ı ˇcten´ı =⇒ nen´ı potˇreba dˇelat kompromisy logick´y sektor 2048 B (m˚ uˇze b´yt i vˇetˇs´ı) na disku m˚ uˇze b´yt v´ıc logick´ych svazk˚ u; svazek m˚ uˇze b´yt na v´ıce disc´ıch na zaˇc´atku 16 rezervovan´ych blok˚ u + 1 blok (Primary Volume Descriptor) =⇒ informace o disku; odkaz na koˇrenov´y adres´aˇr adres´aˇr pops´an pomoc´ı z´aznam˚ u promˇenliv´e d´elky (viz Tan. 432) textov´a data v ASCII bin´arn´ı 2× (little- i big-endian)

moˇznosti form´atu urˇceny u ´rovnˇemi a rozˇs´ıˇren´ımi Level 1 – soubory 8.3; vˇsechny soubory spojit´e; 8 u ´rovn´ı adres´aˇr˚ u Level 2 – jm´ena aˇz 31 znak˚ u Level 3 – nespojit´e soubory (jednotliv´e souvisl´e bloky se mohou opakovat)

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

35 / 37

ISO-9660: Rozˇs´ıˇren´ı Rock Ridge kompatibilita s unixy pˇrid´av´a dlouh´a jm´ena neomezen´e zanoˇren´ı adres´aˇr˚ u unixov´a opr´avnˇen´ı podpora symbolick´ych odkaz˚ u; moˇznost m´ıt na disku soubory zaˇr´ızen´ı Joliet kompatibilita s Windows pˇrid´av´a dlouh´a jm´ena + podporu Unicode neomezen´e zanoˇren´ı adres´aˇr˚ u

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

36 / 37

UDF: Universal Disk Format n´ahrada za ISO-9660 pouˇz´ıv´an pˇrev´aˇznˇe pro DVD a Blue-ray disky dlouh´e n´azvy, soubory aˇz 1EB r˚ uzn´e varianty form´atu: Plain build – z´akladn´ı form´at (data lze pˇrepisovat pokud m´edium podporuje; pˇrepis konkr´etn´ıch sektor˚ u – DVD-RAM, DVD+RW) Virtual Allocation Table – inkrement´aln´ı z´apisy (CD-R) Spare build – pokud to m´edium podporuje, lze data pˇrepisovat; zahrnuta obrana proti opotˇreben´ı sektor˚ u

Petr Krajˇ ca (UP)

KMI/YOS: Pˇredn´ aˇska V.

12. prosinec, 2014

37 / 37