pCDfs/pCDfs.d
7. ledna 2003
KIV/ZOS 2002/2003 Pr ˇedna ´s ˇka 11 a 12 Implementace souborovy ´ch syste ´mu ˚ ================================ * proble ´my: - jak bude fs vypadat pro uz ˇivatele? - jake ´ algoritmy a datove ´ struktury pouz ˇı ´t pro implementaci? => ru ˚ zna ´ ´ uroven ˇ abstrakce V dnes ˇnı ´ch OS nejme ´ne ˇ je implementace souboru ˚ rozde ˇlena nejme ´ne ˇ do 3 vrstev, a to na logicky ´ souborovy ´ syste ´m, modul organizace souboru ˚, a ovladac ˇe zar ˇı ´zenı ´. * logicky ´ souborovy ´ syste ´m (v ne ˇktery ´ch OS ”virtua ´lnı ´ souborovy ´ syste ´m”, VFS) - je vola ´n aplikacemi - tvor ˇı ´ rozhranı ´ s moduly organizace souboru ˚ - obsahuje ko ´d spolec ˇny ´ pro vs ˇechny typy fs - pr ˇeva ´dı ´ jme ´no souboru na informaci o souboru - udrz ˇuje informace o otevr ˇene ´m souboru (otevr ˇen pro c ˇtenı ´/za ´pis, pozice c ˇtenı ´/za ´pisu) - zodpove ˇdny ´ za ochranu a bezpec ˇnost * modul organizace souboru ˚ - implementuje konkre ´tnı ´ souborovy ´ syste ´m - c ˇte/zapisuje datove ´ bloky souboru . datove ´ bloky souboru jsou c ˇı ´slova ´ny od 0 do N-1 . pr ˇevod pr ˇevod c ˇı ´sla bloku souboru na diskovou adresu . vola ´nı ´ ovladac ˇe pro c ˇtenı ´/za ´pis bloku - spra ´va volne ´ho prostoru + alokace volny ´ch bloku ˚ - ´ udrz ˇba datovy ´ch struktur fs * nejniz ˇs ˇı ´ ´ uroven ˇ - ovladac ˇe zar ˇı ´zenı ´ - interpretujı ´ poz ˇadavky typu: pr ˇec ˇti logicky ´ blok 6456 ze zar ˇı ´zenı ´ 3 Pr ˇı ´klad (OS Linux):
application
VFS msdos fs floppy
ext2 ide
ext3 scsi
iso9660 cdrom
Implementace souboru ˚ -------------------* nejdu ˚lez ˇite ˇjs ˇı ´ ota ´zka - ktere ´ diskove ´ bloky patr ˇı ´ ktere ´mu souboru * probereme pouze nejza ´kladne ˇjs ˇı ´ metody * v dals ˇı ´m textu budeme pr ˇedpokla ´dat, z ˇe fs coby datova ´ struktura - je umı ´ste ˇna v ne ˇjake ´ oblasti (disk partition) - bloky v oblasti jsou oc ˇ´ ıslova ´ny od 0 Kontinua ´lnı ´ alokace ................... * nejjednodus ˇs ˇı ´ - soubor jako kontinua ´lnı ´ posloupnost diskovy ´ch bloku ˚ * napr ˇ. pr ˇi blocı ´ch velikosti 1 KB by soubor A o velikosti 4 KB zabı ´ral 4 po sobe ˇ na ´sledujı ´cı ´ bloky atd.
1
pCDfs/pCDfs.d
7. ledna 2003
2
A A A A B B B C C C C C C D D D D D D file A (4 blocks)
9 free blocks
* jednoducha ´ implementace: potr ˇebujeme zna ´t pouze c ˇı ´slo prvnı ´ho bloku a celkovy ´ poc ˇet bloku ˚ souboru (mu ˚z ˇe by ´t obsaz ˇeno napr ˇ. v adresa ´r ˇi) * c ˇtenı ´ je velmi rychle ´ - pr ˇesuneme hlavic ˇku na zac ˇa ´tek souboru, c ˇtene ´ bloky jsou za sebou * proble ´m - pr ˇi be ˇhu OS soubory vznikajı ´ a zanikajı ´, pr ˇı ´padne ˇ me ˇnı ´ velikost - na zac ˇa ´tku mu ˚z ˇeme zapisovat soubory se ´riove ˇ do volne ´ho mı ´sta na konci - po jeho zaplne ˇnı ´ budeme potr ˇebovat vyuz ˇı ´t volne ´ mı ´sto po zrus ˇeny ´ch souborech - abychom vybrali vhodnou dı ´ru, potr ˇebovali bychom zna ´t konec ˇnou de ´lku souboru - coz ˇ je informace, kterou ve ˇts ˇinou nema ´me * kontinua ´lnı ´ alokace se dnes pouz ˇı ´va ´ pouze na read-only a write-once me ´diı ´ch * napr ˇı ´klad v za ´kladnı ´ verzi souborove ´ho syste ´mu ISO 9660 pro CD ROMy Seznam diskovy ´ch bloku ˚ ...................... * mys ˇlenka sva ´zat diskove ´ bloky do seznamu - nebude vne ˇjs ˇı ´ fragmentace * na zac ˇa ´tku diskove ´ho bloku je uloz ˇen odkaz na dals ˇı ´ blok souboru, zbytek bloku obsahuje data souboru
5
2
3
4
9
6
7
8
13
10
A B B B B A A A A B B 0
1
2
3
4
5
6
7
8
9
10
A 11
12
13
* pro pr ˇı ´stup k souboru stac ˇı ´ zna ´t pouze c ˇı ´slo prvnı ´ho bloku souboru (mu ˚z ˇe by ´t v adresa ´r ˇi) * sekvenc ˇnı ´ c ˇtenı ´ bez potı ´z ˇı ´, ale pr ˇı ´my ´ pr ˇı ´stup je simulova ´n pomocı ´ sekvenc ˇnı ´ho - pomale ´ * ne ˇkdy mu ˚z ˇe by ´t nevy ´hodou, z ˇe velikost dat v bloku nenı ´ mocnina 2 (c ˇa ´st bloku je zabra ´na odkazem na dals ˇı ´ blok souboru) FAT ...
FAT 0
5
file A starts here
1
2
file B starts here
2
3
3
4
4 5
9 6
6
7
7
8
A B B B B A A A A B B
9
13 10
0
10
-1
8
1
2
3
4
5
6
7
8
9
10
A 11
12
disk partition Eof marker
11 12 13
13
-1
* vy ´s ˇe uvedene ´ nevy ´hody seznamu diskovy ´ch bloku ˚ lze odstranit pr ˇesunutı ´m odkazu ˚ do samostatne ´ tabulky
pCDfs/pCDfs.d
7. ledna 2003
* tato tabulka se nazy ´va ´ FAT (File Allocation Table) - kaz ˇde ´mu diskove ´mu bloku odpovı ´da ´ jedna poloz ˇka v tabulce FAT - poloz ˇka FAT obsahuje c ˇı ´slo dals ˇı ´ho bloku souboru (je to za ´roven ˇ odkaz na dals ˇı ´ poloz ˇku FAT) - r ˇete ˇzec odkazu ˚ je ukonc ˇen specia ´lnı ´ znac ˇkou, ktera ´ nenı ´ platny ´m c ˇı ´slem bloku * nevy ´hodou je velikost tabulky FAT: pr ˇedpokla ´dejme 80 GB disk, bloky velikosti 4 KB => 20 mil. poloz ˇek, kaz ˇda ´ alespon ˇ 3 byty => 60 MB FAT * FAT se pouz ˇı ´va ´ v MS DOSu, ..., Windows 98, Windows me (FAT-12, FAT-16, FAT-32) I-uzly ...... * s kaz ˇdy ´m souborem sdruz ˇena ´ datova ´ struktura i-uzel (angl. i-node, zkratka z index-node)
i-node attributes pointer to block 0 pointer to block 1 pointer to block 2 pointer to block 3 pointer to block 10 pointer to block of pointers disk partition A
A A A
A A A A
A
* i-uzel obsahuje atributy souboru, diskove ´ adresy prvnı ´ch N bloku ˚ a jeden nebo vı ´ce odkazu ˚ na diskove ´ bloky obsahujı ´cı ´ dals ˇı ´ diskove ´ adresy (pr ˇı ´padne ˇ obsahujı ´cı ´ odkazy na bloky obsahujı ´cı ´ adresy) * vy ´hoda - po otevr ˇenı ´ souboru mu ˚z ˇeme zave ´st i-uzel a pr ˇı ´padny ´ blok obsahujı ´cı ´ dals ˇı ´ adresy do pame ˇti => urychlı ´ pr ˇı ´stup k souboru * pouz ˇı ´vajı ´ tradic ˇnı ´ fs v UNIXu a Linuxu (viz JUU, str. 163) Implementace adresa ´ˇ r˚ u --------------------* pr ˇed c ˇtenı ´m musı ´ by ´t soubor otevr ˇen * otevr ˇenı ´ vola ´nı ´m open(jme ´no, jak) - zada ´me jme ´no, potr ˇebujeme pr ˇeve ´st na informaci potr ˇebnou pro nalezenı ´ dat * mapova ´nı ´ jme ´no -> informace o datech poskytujı ´ adresa ´r ˇe * v mnoha syste ´mech jsou adresa ´r ˇe specia ´lnı ´m typem souboru * typicky pole datovy ´ch struktur, 1 poloz ˇka na soubor * 2 za ´kladnı ´ uspor ˇa ´da ´nı ´: - adresa ´r ˇ obsahuje jme ´no souboru, atributy, diskovou adresu souboru (v za ´vislosti na implementaci souboru ˚ napr ˇ. adresu prvnı ´ho bloku apod.) - adresa ´r ˇ obsahuje pouze jme ´no + odkaz na jinou datovou strukturu obsahujı ´cı ´ dals ˇı ´ informace (napr ˇ. i-uzel) - be ˇz ˇne ´ jsou oba zpu ˚ soby i kombinace
attributes, disk address
mail
attributes, disk address prednasky attributes, disk address
mail prednasky
pracovni attributes, disk address
pracovni
a)
b)
attributes, disk address attributes, disk address
* zpu ˚sob (a) implementuje napr ˇ. MS DOS a Windows, zpu ˚sob (b) je
3
pCDfs/pCDfs.d
7. ledna 2003
4
pouz ˇı ´va ´n v UNIXu a Linuxu Pr ˇı ´klad (adresa ´r ˇe v syste ´mu UNIX v7) * * * * *
adresa ´r ˇ obsahuje pouze jme ´no souboru a c ˇı ´slo i-uzlu c ˇı ´slo i-uzlu je indexem do tabulky i-uzlu ˚ na disku kaz ˇdy ´ soubor a adresa ´r ˇ ma ´ pra ´ve ˇ jeden i-uzel v i-uzlu jsou vs ˇechny atributy a c ˇı ´sla diskovy ´ch bloku ˚ kor ˇenovy ´ adresa ´r ˇ ma ´ c ˇı ´slo i-uzlu 1
i-node 1 attributes
directory "/" 1 1 4 9
. .. bin etc
i-node 9 attributes
132
directory "/etc"
i-node 30
2
k 13
bloc
9 .
data
attributes
1 .. 30 passwd
406 638
data
* nalezenı ´ cesty k souboru /etc/passwd podle obra ´zku: - v kor ˇenove ´m adresa ´r ˇi najdeme poloz ˇku ”etc” - i-uzel c ˇ. 9 obsahuje adresy diskovy ´ch bloku ˚ pro adresa ´r ˇ ”/etc” - v adresa ´r ˇi ”/etc” (diskovy ´ blok 132) najdeme poloz ˇku ”passwd” - i-uzel 30 popisuje soubor ”/etc/passwd” [] Pr ˇı ´klad pouze pro zajı ´mavost (adresa ´r ˇe v syste ´mu Windows 98) * poloz ˇka adresa ´r ˇe obsahuje: - jme ´no souboru (8) - pr ˇı ´ponu (3) - atributy (1) - NT (1) - Windows 98 nepouz ˇı ´vajı ´ (rezetvova ´no pro WinNT) - datum a c ˇas vytvor ˇenı ´ (5) - c ˇas poslednı ´ho pr ˇı ´stupu (2) - hornı ´ch 16 bitu ˚ poc ˇa ´tec ˇnı ´ho bloku souboru (2) - c ˇas poslednı ´ho c ˇtenı ´/za ´pisu - spodnı ´ch 16 bitu ˚ poc ˇa ´tec ˇnı ´ho bloku souboru (2) - velikost souboru (4) * dlouha ´ jme ´na majı ´ pokrac ˇovacı ´ poloz ˇky * ves ˇkere ´ ”podivnosti” te ´to struktury jsou z du ˚vodu kompatibility s MS DOSem [] Sdı ´lenı ´ souboru ˚ ............... * pokud chceme, aby byl soubor nebo adresa ´r ˇ viditelny ´ ve vı ´ce podadresa ´r ˇı ´ch nebo pod vı ´ce jme ´ny - 2 zpu ˚soby implementace * pokud ma ´ kaz ˇdy ´ soubor datovou strukturu, ktera ´ ho popisuje (napr ˇ. i-uzel), mu ˚z ˇeme v adresa ´r ˇı ´ch vytvor ˇit vı ´ce odkazu ˚ na stejny ´ soubor (tzv. pevne ´ odkazy, hard links) - vs ˇechny odkazy (=vs ˇechna jme ´na souboru) jsou rovnocenne ´, soubor zanikne po zrus ˇenı ´ poslednı ´ho odkazu (jme ´na) - v popisu souboru musı ´ by ´t poc ˇet odkazu ˚ (pr ˇi vytvor ˇenı ´ souboru bude poc ˇet odkazu ˚ 1) * vytvor ˇı ´me novy ´ typ souboru, ktery ´ bude obsahovat jme ´no odkazovane ´ho souboru (symbolicky ´ odkaz); OS mı ´sto symbolicke ´ho odkazu otevr ˇe odkazovany ´ soubor - obecne ˇjs ˇı ´ (symbolicky ´ odkaz mu ˚z ˇe obsahovat cokoli), ale ma ´ ve ˇts ˇı ´ rez ˇii Spra ´va volne ´ho prostoru ....................... * jak udrz ˇovat informaci, ktere ´ bloky jsou volne ´?
pCDfs/pCDfs.d
7. ledna 2003
5
* nejc ˇaste ˇji pomocı ´ seznamu ˚ nebo pomocı ´ bitovy ´ch map * seznam: seznam diskovy ´ch bloku ˚, blok obsahuje odkazy na volne ´ bloky a adresu dals ˇı ´ho bloku (ktery ´ ope ˇt obsahuje obsahuje odkazy na volne ´ bloky a adresu dals ˇı ´ho bloku seznamu) - uvolne ˇnı ´ bloku ˚ - pr ˇida ´me adresy do seznamu, pokud nenı ´ mı ´sto blok zapı ´s ˇeme - potr ˇebujeme bloky pro soubor - pouz ˇı ´va ´me adresy ze seznamu, pokud nejsou pr ˇec ˇteme dals ˇı ´ blok adres volny ´ch bloku ˚ - pokud nenı ´ na disku volne ´ mı ´sto, seznam volny ´ch bloku ˚ je pra ´zdny ´ a nezabı ´ra ´ mı ´sto - proble ´m pokud pro soubor potr ˇebujeme volny ´ blok s urc ˇity ´mi vlastnostmi (napr ˇ. ve stejne ´m cylindru jako pr ˇedchozı ´ blok souboru)
* bitova ´ mapa - ma ´ konstantnı ´ velikost, snazs ˇı ´ vyhleda ´nı ´ volne ´ho bloku s urc ˇity ´mi vlastnostmi * ve ˇts ˇina souc ˇasny ´ch fs pouz ˇı ´va ´ bitovou mapu Kvo ´ty ..... * aby uz ˇivatele ´ nezabrali pr ˇı ´lis ˇ prostoru, mu ˚z ˇe spra ´vce kaz ˇde ´mu uz ˇivateli nastavit kvo ´tu = maxima ´lnı ´ poc ˇet bloku ˚ obsazeny ´ch soubory uz ˇivatele * ve vı ´ceuz ˇivatelsky ´ch OS, OS pro servery (UNIX, Windows 2000...) * implementace: { v ZS 2002 vynecha ´no } Spolehlivost fs ............... * ztra ´ta dat je ve ˇts ˇinou ve ˇts ˇı ´ katastrofa nez ˇ znic ˇenı ´ poc ˇı ´tac ˇe - pokud va ´m do poc ˇı ´tac ˇe pras ˇtı ´ blesk nebo pr ˇijdou za ´plavy, da ´ se v nejhors ˇı ´m pr ˇı ´pade ˇ koupit novy ´ - vas ˇe ztracena ´ data nekoupı ´te (diplomova ´ pra ´ce, databa ´ze za ´kaznı ´ku ˚...) * fs musı ´ by ´t nejspolehlive ˇjs ˇı ´ c ˇa ´st OS, snaz ˇı ´ se chra ´nit data - spra ´va vadny ´ch bloku ˚ (viz pr ˇedchozı ´ pr ˇedna ´s ˇka) - ne ˇktere ´ fs se snaz ˇı ´ rozprostr ˇı ´t du ˚lez ˇite ´ datove ´ struktury tak, aby fs byl (alespon ˇ c ˇa ´stec ˇne ˇ) c ˇitelny ´ i po pos ˇkozenı ´ konkre ´tnı ´ho povrchu (napr ˇ. ufs v UNIXu)
Pr ˇı ´klad souborove ´ho syste ´mu (fs z UNIXu v7) * struktura fs na disku - boot blok - fs nevyuz ˇı ´va ´, c ˇasto ko ´d pro zavedenı ´ OS - superblok - informace o fs: poc ˇet i-uzlu ˚ a datovy ´ch bloku ˚ apod. - i-uzly - tabulka pevne ´ velikosti, i-uzly c ˇı ´slova ´ny od 1 - datove ´ bloky - vs ˇechny soubory a adresa ´r ˇe
B S
D D D D D D D D i-nodes
superblock
D D
data blocks
boot block * implementace souboru ˚ - i-uzly - i-uzel obsahuje: . atributy . odkazy na prvnı ´ch 10 datovy ´ch bloku ˚ souboru . odkaz na blok obsahujı ´cı ´ odkazy na datove ´ bloky (nepr ˇı ´my ´ odkaz) . odkaz na blok obsahujı ´cı ´ odkazy na bloky obsahujı ´cı ´ odkazy na datove ´ bloky (dvojite ˇ nepr ˇı ´my ´ odkaz) . trojite ˇ nepr ˇı ´my ´ odkaz
pCDfs/pCDfs.d
7. ledna 2003
UNIX v7 i-node attributes pointer to block 0 pointer to block 1 pointer to block 2 pointer to block 3 pointer to block 10 pointer to block of pointers pointer to double indirect block pointer to triple indirect block
* implementace adresa ´r ˇ˚ u - tabulka obsahujı ´cı ´ jme ´no souboru a c ˇı ´slo jeho i-uzlu * informace o volny ´ch blocı ´ch - seznam, jeho zac ˇ´ atek je v superbloku * popsany ´ fs se pouz ˇı ´val v nejstars ˇı ´ch verzı ´ch OS UNIX, je velmi jednoduchy ´ ale ma ´ proble ´my s efektivitou * modernı ´ fs UNIXu a Linuxu (ufs, ext2 apod.) jsou zaloz ˇeny na podobny ´ch za ´kladnı ´ch mys ˇlenka ´ch (i-uzly apod.), ale eliminujı ´ nevy ´hody (struc ˇny ´ popis ufs je v JUU na str. 164) [] Konzistence fs .............. * OS pr ˇec ˇte blok souboru, zme ˇnı ´ ho, zapı ´s ˇe * co kdyz ˇ nastane hava ´rie pr ˇed tı ´m, nez ˇ jsou vs ˇechny modifikovane ´ bloky zapsa ´ny? => fs mu ˚z ˇe by ´t v nekonzistentnı ´m stavu * s ve ˇts ˇinou OS se doda ´va ´ syste ´movy ´ program, ktery ´ kontroluje konzistenci fs (UNIX: fsck, Windows: scandisk resp. chkdsk) * program je spus ˇte ˇn po hava ´rii syste ´mu * program mu ˚z ˇe prova ´de ˇt na ´sledujı ´cı ´ testy konzistence fs: - konzistence informace o diskovy ´ch blocı ´ch souboru ˚ (ve ve ˇts ˇine ˇ fs mu ˚z ˇe blok patr ˇit pouze jednomu souboru nebo by ´t volny ´) - konzistence adresa ´r ˇove ´ struktury (jsou vs ˇechny adresa ´r ˇe a soubory dostupne ´? apod.) * kontrola konzistence informace o diskovy ´ch blocı ´ch souboru ˚ - program vytvor ˇı ´ dve ˇ tabulky, obsahujı ´cı ´ c ˇı ´tac ˇ pro kaz ˇdy ´ blok . tabulka poc ˇtu vy ´skytu ˚ bloku v souboru . tabulka poc ˇtu vy ´skytu ˚ bloku v seznamu volny ´ch bloku ˚ . vs ˇechny poloz ˇky obou tabulek na poc ˇa ´tku inicializova ´ny na 0 - program procha ´zı ´ informace o souborech (napr ˇ. i-uzly) a pr ˇitom inkrementuje poloz ˇky odpovı ´dajı ´cı ´ bloku ˚m souboru v prvnı ´ tabulce - pak procha ´zı ´ seznam nebo bitmapu volny ´ch bloku ˚ a inkrementuje pr ˇı ´slus ˇne ´ poloz ˇky ve druhe ´ tabulce - je-li fs konzistentnı ´, bude mı ´t kaz ˇdy ´ blok 1 bud’ v prvnı ´ nebo ve druhe ´ tabulce * pro konzistentnı ´ fs bude tabulka vypadat napr ˇ. takto:
6
pCDfs/pCDfs.d c ˇı ´slo bloku: 0 vy ´skyt v souborech: 1 volne ´ bloky: 0
7. ledna 2003 1 1 0
2 0 1
3 0 1
4 1 0
5 0 1
6 0 1
7 1 0
8 1 0
9 11 12 13 14 15 1 1 0 1 0 0 0 0 1 0 1 1
* moz ˇne ´ chyby a jejich za ´vaz ˇnost: - 0-0: blok se nevyskytuje v z ˇa ´dne ´ tabulce (”missing block”) . nenı ´ za ´vaz ˇne ´, pouze redukuje kapacitu fs . opravı ´me vloz ˇenı ´m do seznamu volny ´ch bloku ˚ - 0-2: blok je dvakra ´t nebo vı ´cekra ´t v seznamu volny ´ch . proble ´m, blok by mohl by ´t alokova ´n dvakra ´t . opravı ´me seznam volny ´ch bloku ˚, aby se vyskytoval pouze jednou - 1-1: blok patr ˇı ´ souboru a za ´roven ˇ je na seznamu volny ´ch . proble ´m, blok by mohl by ´t alokova ´n podruhe ´ . blok vyjmeme ze seznamu volny ´ch bloku ˚ - 2-0: blok patr ˇı ´ do dvou nebo vı ´ce souboru ˚ . nejza ´vaz ˇne ˇjs ˇı ´ proble ´m, nejspı ´s ˇe dos ˇlo ke ztra ´te ˇ dat . alokujeme novy ´ blok, problematicky ´ blok do ne ˇj zkopı ´rujeme a upravı ´me i-uzel druhe ´ho souboru; uz ˇivatel by me ˇl by ´t informova ´n o proble ´mu Doma ´cı ´ ´ ukol: Jake ´ chyby odhalı ´te v na ´sledujı ´cı ´m fs a jak jsou za ´vaz ˇne ´? c ˇı ´slo bloku: 0 vy ´skyt v souborech: 1 volne ´ bloky: 0
1 2 0
2 0 1
3 0 1
4 1 0
5 0 0
6 0 1
7 1 0
8 1 0
9 11 12 13 14 15 1 1 1 1 0 0 0 0 1 0 1 1
[] * kontrola konzistence adresa ´r ˇove ´ struktury - tabulka c ˇı ´tac ˇ˚ u, jedna poloz ˇka pro kaz ˇdy ´ soubor - program procha ´zı ´ rekurzivne ˇ cely ´ adresa ´r ˇovy ´ strom - poloz ˇku pro soubor program zvy ´s ˇı ´ pro kaz ˇdy ´ vy ´skyt souboru v adresa ´r ˇi - pak zkontroluje zda odpovı ´da ´ poc ˇet odkazu ˚ v i-uzlu (”i”) s poc ˇtem vy ´skytu ˚ v adresa ´r ˇı ´ch (”a”) * moz ˇne ´ chyby: - i>a: soubor by nebyl zrus ˇen ani po zrus ˇenı ´ vs ˇech odkazu ˚ v adresa ´r ˇı ´ch . nenı ´ za ´vaz ˇne ´, ale soubor by zbytec ˇne ˇ zabı ´ral mı ´sto . r ˇes ˇı ´me nastavenı ´m poc ˇtu odkazu ˚ (v i-uzlu) na spra ´vnou hodnotu - i
0: ztraceny ´ soubor, na ktery ´ nenı ´ v adresa ´r ˇi odkaz . ve ve ˇts ˇine ˇ syste ´mu ˚ program soubor zviditelnı ´ na pr ˇedem urc ˇene ´m mı ´ste ˇ (napr ˇ. adresa ´r ˇ ”/lost+found” v Linuxu) * ru ˚zne ´ dals ˇı ´ heuristicke ´ kontroly - odpovı ´dajı ´ jme ´na souboru ˚ konvencı ´m OS? . pokud ne, soubor mu ˚ˇ ze by ´t nepr ˇı ´stupny ´ -> zme ˇnı ´me jme ´no - nejsou pr ˇı ´stupova ´ pra ´va nesmyslna ´? . pokud nema ´ vlastnı ´k pr ˇı ´stup k souboru, mu ˚z ˇe to by ´t proble ´m - atd. Vy ´konnost fs ............ * pr ˇı ´stup k disku je r ˇa ´dove ˇ pomalejs ˇı ´ nez ˇ pr ˇı ´stup do pame ˇti - napr ˇ. 5-10 ms bude trvat seek - pak rotac ˇnı ´ zpoz ˇde ˇnı ´ - c ˇeka ´me az ˇ bude poz ˇadovany ´ blok pod hlavou - pak se bude c ˇı ´st napr ˇ. 10 MB/s (cca 40x pomalejs ˇı ´ nez ˇ pr ˇı ´stup do hlavnı ´ pame ˇti) * proto pr ˇi na ´vrhu fs ru ˚zne ´ optimalizace, napr ˇ. - cachova ´nı ´ [kes ˇova ´nı ´] diskovy ´ch bloku ˚ v pame ˇti - pr ˇednac ˇı ´ta ´nı ´ (read-ahead) - do cache se pr ˇedem nac ˇı ´tajı ´ bloky, ktere ´
7
pCDfs/pCDfs.d
7. ledna 2003
se budou potr ˇebovat pr ˇi sekvenc ˇnı ´m c ˇtenı ´ souboru - redukce pohybu diskove ´ho rame ´nka pro po sobe ˇ na ´sledujı ´cı ´ bloky souboru - atd. Atomicke ´ transakce { vynecha ´no v ZS 2002 } -----------------Cele ´ transakce + implementace - viz mu ˚j c ˇla ´nec ˇek ”Distribuovane ´ transakce” na WWW. * Primitiva pro programova ´nı ´ transakcı ´ * Vlastnosti transakce * Implementace transakcı ´ - Stabilnı ´ pame ˇt’ (viz pr ˇedchozı ´ pr ˇedna ´s ˇka) - Soukroma ´ pracovnı ´ oblast - Tvorba z ˇurna ´lu . Inkrementa ´lnı ´ tvorba z ˇurna ´lu s bezprostr ˇednı ´ realizacı ´ zme ˇn . Inkrementa ´lnı ´ tvorba z ˇurna ´lu s odloz ˇenou realizacı ´ zme ˇn - Interference soube ˇz ˇny ´ch transakcı ´ - Zamykacı ´ protokoly - Optimisticke ´ r ˇı ´zenı ´ - Metoda c ˇasovy ´ch razı ´tek
Mechanismy ochrany -----------------* soubory je tr ˇeba chra ´nit pr ˇed neopra ´vne ˇny ´m pr ˇ´ ıstupem * krome ˇ souboru ˚ existujı ´ v OS dals ˇı ´ objekty, ktere ´ je tr ˇeba chra ´nit - mu ˚z ˇe by ´t HW (segmenty pame ˇti, I/O zar ˇı ´zenı ´), - SW objekty (procesy, semafory...) Pojem ”dome ´na” ............. * jako za ´klad pro diskusi ru ˚zny ´ch mechanismu ˚ zavedeme pojem dome ´na * dome ´na = mnoz ˇina uspor ˇa ´dany ´ch dvojic (objekt, mnoz ˇina pr ˇı ´stupovy ´ch pra ´v) - objekt je napr ˇ. soubor, segment pame ˇti apod. - pr ˇı ´stupove ´ pra ´vo je pra ´vo vykonat jednu z moz ˇny ´ch operacı ´ - jedna dome ´na ve ˇts ˇinou odpovı ´da ´ jednomu uz ˇivateli Pr ˇı ´klad (dve ˇ dome ´ny): Dome ´na 1: (soubor1, { R }) (soubor2, { R,W }) (tiska ´rna1, { W })
Dome ´na 2: (soubor1, { R,W }) (soubor3, { R })
V dome ´ne ˇ 1 je ”soubor1” pr ˇı ´stupny ´ pouze pro c ˇtenı ´, zatı ´mco v dome ´ne ˇ 2 je tenty ´z ˇ soubor pr ˇı ´stupny ´ i pro za ´pis. [] * kaz ˇdy ´ proces be ˇz ˇı ´ v dane ´m okamz ˇiku v ne ˇktere ´ z dome ´n => - existuje mnoz ˇina objektu ˚, ke ktery ´m mu ˚z ˇe proces pr ˇistupovat - proces ma ´ pro kaz ˇdy ´ objekt mnoz ˇinu pra ´v Pr ˇı ´klad (UNIX): * procesy uz ˇivatele be ˇz ˇı ´ s dany ´m UID a GID (User Identifier a Group Identifier) * UID a GID definujı ´ dome ´nu: moz ˇne ´ vytvor ˇit ´ uplny ´ seznam objektu ˚, ke ktery ´m mu ˚z ˇe proces s dany ´m UID a GID pr ˇistupovat * ve chvı ´li pr ˇepnutı ´ do ja ´dra docha ´zı ´ k pr ˇepnutı ´ dome ´ny - ja ´dro mu ˚z ˇe pr ˇistupovat ke vs ˇem objektu ˚m v syste ´mu. [] Jak urc ˇit, ktere ´ jaka ´ jsou pra ´va objekty patr ˇı ´ do ktere ´ dome ´ny?
8
pCDfs/pCDfs.d
7. ledna 2003
* koncepc ˇne ˇ matice ochrany (protection matrix) - r ˇa ´dky dome ´ny - sloupce objekty Vy ´s ˇe uvedeny ´ pr ˇı ´klad by po pr ˇevodu do matice ochrany vypadal takto: (soubor1, { R }) (soubor2, { R,W }) (tiska ´rna1, { W })
(soubor1, { R,W }) (soubor3, { R })
soubor1 soubor2 soubor3 tiska ´rna ,---------.---------.-------.--------. Dome ´na 1 | { R } | { R,W } | -| { W } | +---------+---------+-------+--------| Dome ´na 2 | { R,W } | -| { R } | -| ‘---------+---------+-------+--------’ * nad maticı ´ ochrany 6 za ´kladnı ´ch operacı ´: create object, delete object, create domain, delete domain, insert right, remove right * pr ˇepnutı ´ dome ´ny mu ˚z ˇe by ´t snadno zac ˇlene ˇno do matice - dome ´na pr ˇida ´na jako objekt, operace pr ˇepnutı ´ Enter soubor1 soubor2 soubor3 tiska ´rna dome ´na1 dome ´na2 ,---------.--------.--------.--------.-------+-------. Dome ´na 1 | { R } | { R,W } | -| { W } | -| -| +---------+---------+-------+--------+-------+-------| Dome ´na 2 | { R,W } | -| { R } | -| Enter | -| ‘---------+--------+--------+--------+-------+-------’ * matice je r ˇı ´dka ´, ve ve ˇts ˇine ˇ dome ´n nenı ´ pr ˇı ´stup ke vs ˇem objektu ˚m => v praxi se uz ˇı ´va ´ zr ˇı ´dka v te ´to podobe ˇ * pouz ˇı ´vajı ´ se dve ˇ prakticke ´ metody implementace - obe ˇ ukla ´dajı ´ jen nepra ´zdne ´ prvky matice ochrany: - uloz ˇenı ´ matice po sloupcı ´ch (ACL) - uloz ˇenı ´ matice po ˇ ra ´dcı ´ch (C-seznamy) Mechanismus ACL (Access Control Lists) ...................................... * ACL = uloz ˇenı ´ matice ochrany po sloupcı ´ch * s kaz ˇdy ´m objektem sdruz ˇen seznam dome ´n, ktere ´ mohou pr ˇistupovat k objektu + jaky ´m zpu ˚sobem (= seznam pra ´v) Pr ˇı ´klady ACL (podle vy ´s ˇe uvedene ´ tabulky): * pu ˚vodnı ´ pr ˇı ´klad, budeme pr ˇedpokla ´dat, z ˇe Dome ´na 1 = uz ˇivatel A, Dome ´na 2 = uz ˇivatel B * s kaz ˇdy ´m objektem sdruz ˇeno ACL, popisujı ´cı ´ kdo ma ´ k objektu jaky ´ pr ˇı ´stup: soubor1:
A:R, B:RW
soubor2:
A:RW
soubor3:
B:R
tiska ´rna: A:W
[] Pr ˇı ´klad (implementace ACL pro UNIX): * za ´kladnı ´ fs pro UNIX mechanismus ACL nema ´, ale ma ´ ho mnoho modernı ´ch fs * ACL by bylo moz ˇne ´ doimplementovat napr ˇ. takto: - v i-uzlu by byla c ˇa ´st tabulky ACL, pokud by se neves ˇla cela ´ do i-uzlu tak take ´ odkaz na diskovy ´ blok, obsahujı ´cı ´ zbytek ACL - dome ´na je urc ˇena c ˇı ´sly UID a GID, pr ˇı ´padne ˇ ”*” = vs ˇichni - pr ˇı ´stupova ´ pra ´va implementova ´na N bitovy ´m slovem, 1=pra ´vo pr ˇide ˇleno a 0=pra ´vo odejmuto * pr ˇı ´klad obsahu tabulky ACL:
9
pCDfs/pCDfs.d
7. ledna 2003 UID Jan
GID *
jinySoubor:
Luki *
* rwstudent r--
Tiska ´rna:
* *
* -wzlobic ˇi ---
MujSoubor:
pr ˇı ´st.pra ´va rwx
* pro MujSoubor ma ´ ACL jednu poloz ˇku, uz ˇivatel Jan mu ˚z ˇe soubor c ˇı ´st, zapisovat i spous ˇte ˇt * jinySoubor mohou c ˇlenove ´ skupiny student c ˇı ´st, uz ˇivatel Luki i zapisovat * na tiska ´rnu mohou zapisovat vs ˇichni krome ˇ uz ˇivatelu ˚ ve skupine ˇ ”zlobic ˇi” [] * v praxi najdeme dals ˇı ´ pra ´va, napr ˇ. pra ´vo soubor zrus ˇit, pr ˇejmenovat... * ACL pouz ˇı ´va ´ mnoho modernı ´ch fs (NTFS ve Windows NT apod.) Mechanismus C-seznamu ˚ (”capabilities”) ...................................... * uloz ˇenı ´ matice ochrany po r ˇa ´dcı ´ch, tj. po dome ´na ´ch * s kaz ˇdy ´m procesem sdruz ˇen seznam objektu ˚ ke ktery ´m mu ˚z ˇe pr ˇistupovat a jaky ´m zpu ˚sobem (jiny ´mi slovy - jeho dome ´na) * seznam nazy ´va ´n ”capability list” (C-list = C-seznam) a jednotlive ´ poloz ˇky ”capabilities” * struktura ”capability” ma ´ prvky: - typ objektu - pra ´va - obvykle bitova ´ mapa popisujı ´cı ´ dovolene ´ operace nad objektem - odkaz na objekt, napr ˇ. c ˇı ´slo i-uzlu Pr ˇı ´klad (”capability list” pro vymys ˇlenou dome ´nu 3) typ soub soub tisk
pra ´va r-rwx w
objekt (odkaz na) soubor3 (odkaz na) soubor4 (odkaz na) tiska ´rnu1
* proble ´m - zjis ˇte ˇnı ´, kdo vs ˇechno ma ´ k objektu pr ˇı ´stup + zrus ˇenı ´ pr ˇı ´stupu velmi obtı ´z ˇne ´ - najı ´t pro objekt vs ˇechny capability + odejmout pra ´va * r ˇes ˇenı ´ zrus ˇenı ´ pr ˇı ´stupu - odkaz neukazuje na objekt, ale na nepr ˇı ´my ´ objekt; syste ´m mu ˚z ˇe zrus ˇit nepr ˇı ´my ´ objekt Pouz ˇı ´va ´ se podstatne ˇ r ˇı ´dc ˇeji nez ˇ ACL, napr ˇ. spı ´s ˇe v distribuovany ´ch syste ´mech. Pr ˇı ´padova ´ studie: OS UNIX - viz JUU, kap. 13 #########################
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Za´veˇrecˇna´ prosba: Pokud v za´pisu prˇedna´sˇek nenı´ neˇco srozumitelne´ nebo najdete neˇjake´ chyby, prosı´m abyste mne na to upozornili. Deˇkuji peˇkneˇ. !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
10
