40 - Systémy souborů, přidělování a evidence diskového prostoru

Question 1

Základní pojmy - soubor, fyzická a logická abstrakce,..

Answer 1

Soubor = abstraktní jednotka obsahující data s jednoznačnou identifikací
Fyzická abstrakce souboru = I/O po sektorech disku, adresa fyzického sektoru, bez práv a ochran
Logická abstrakce souboru = I/O po bajtech (nebo záznamech), identifikace souboru, práva souboru

Systém souborů poskytuje:

• strukturu souborů
• alokaci diskového prostoru
• souborové operace
• ochranu

Question 2

Struktury souborů (logická a vnitřní struktura souboru)

Answer 2

1. Logická struktura souboru = na úrovni rozhraní jádra OS
2. Bez struktury - pouhé pole bajtů (Unix)
3. Logické záznamy s pevnou délkou - rychlý náhodný přístup, lehké změny, velký prostor nevyužit pokud nejsou záznamy plné (interní fragmentace)
4. Logické záznamy s proměnnou délkou - pomalý přístup, špatná aktualizace, plné využití (externí fragmentace)
5. Index-sekvenční soubory - záznamy proměnné délky a index podle klíče (B-strom)
6. Vnitřní struktura souboru = na úrovni I/O

• Soubor je pole alokačních bloků.
• Alokační blok je několik souvislých sektorů.
• Je potřeba překlad z logického adresování na adresy bloků.
• Velikost alokačního bloku ovlivňuje rychlost a využití místa.
• Úzce souvisí s alokací diskového souboru (viz dále)

Question 3

Alokace alokačních bloků

Answer 3

• náhodný/sekvenční soubor
• malé soubory - hodně souborů, nesmí zabírat moc místa
• velké soubory - pokud možno sekvenčně kvůli rychlosti přístupu

Souvislá alokace = celý soubor vcelku
[+] rychlý přístup k celému souboru i při náhodném přístupu
[-] nutná prealokace místa
[-] externí fragmentace
[-] problém je vkládání dat jinam než na konec

Soubory jako Lineární seznamy = jednosměrně nebo obousměrně vázané seznamy bloků
[+] jednoduché vkládání, přidávání, rušení dat
[+] nulová externí fragmentace
[-] náhodný přístup pomalý (nutné sekvenční procházení seznamu)
[-] slabá lokalita, náhodné adresy sousedních logických bloků

!!! Index-sekvenční organizace - pevné alokační bloky

• Prostor alokován po blocích pevné velikosti
• Index obsahuje seznam alokačních bloků A JEJICH OFFSET
  [+] jednoduchá implementace
  [+] snadné zvětšování/zmenšování souborů
  [-] pro velké soubory pomalý průchod indexy

Problém velikosti tabulky

• Globální tabulka (FAT) - pevně daný počet alokačních bloků - globální index pro celý systém souborů
• Víceúrovňová tabulka (UFS) - je rychlejší, ale nevýhodná pro malé soubory (i-nodes)

!!! Index-sekvenční organizace - proměnné alokační bloky

• index alokačních bloků proměnné délky
• problém alokace bloků proměnné velikosti
• bloky mají velikost 2^n nejmenšího alokačního bloku

Question 4

Alokace diskového prostoru

Answer 4

v OS je potřeba nejen volit umístění a velikost jednotek, ale také mít přehled o volném místě a rozložení souborů

Velikost alokačního bloku

• menší bloky - pomalejší, lepší využití prostoru
• větší bloky - rychlejší, horší využití prostoru

Vyhledání volného místa

• souvislá alokace nebo alokace pevných bloků eviduje volné bloky
• alokace proměnné délky musí evidovat volné úseky a spojovat je nebo dělit
• pro optimalizaci diskových operací by bloky měly být co nejblíže u sebe

Okamžik alokace diskového prostoru pro soubor

• PREALOKACE omezuje fragmentaci souboru, ale nešetří místo
• DYNAMICKÁ ALOKACE při zápisu může vyvolat konflikt s jiným souborem
• ODLOŽENÁ ALOKACE čeká až na uložení stránky paměti

Question 5

Příklady implementace

Answer 5

Unix file system (UFS)

• Alokační blok: 1 sektor
• Volné bloky: index-sekvenční
• Alokace: první volný blok bez optimalizace
• Informace o souborech: i-node na začátku disku
• > Víceúrovňová tabulka i-node
• 10 prvních deset bloků přímo
• • 11. alokační blok - adresy alokačních bloků
• • • 12. alokační blok - adresy alokačních bloků s adresami alokačních bloků
• • • • 13. alokační blok - adresy bloků s adresami bloků s adresami bloků

BSD Fast file system

• založen na UFS
• Alokační blok: větší (4-16 kB)
• Volné bloky: bitová mapa
• Alokace: optimalizovaná (nejbližší volný blok, …)

EXT2/EXT3

• zjednodušená BSD FFS
• Alokační blok: menší (4kB)
• Volné bloky: bitová mapa
• Alokace: bez optimalizací (pouze prealokace při zápisu)
• ext3 DOPLŇUJE ŽURNÁL

LOG structured file system (LFS)

• každá zápis dat se zapíše do logu
• data se zapisují po velkých blocích na konec
• data se čtou z logu
• při zaplnění disku spuštěn cleaner (snaže staré duplicitní bloky)
• odolnost proti výpadku (data jsou v logu vícekrát, ztrácí se jen poslední změny)

NTFS (New Technology File System)

• Všechny soubory a adresáře jsou popsány v MFT (Master File Table, obdoba tabulky inodů) na začátku disku
• Položka MFT (1KB) obsahuje hlavičku (42 byte) a seznam atributů pro daný soubor (atribut Attribute List pokud se seznam atributů nevleze)

SSD

• náhodné čtení stejně rychlé jako sekvenční (není třeba defragmentace)
• zápis obvykle řádově pomalejší
• problém velikosti stránky (min. blok zápisu) – 4KB (32nm), 8KB (25nm) - nesnáší zápis malých bloků (sektory, write amplification)
• blok pro mazání značně větší, musí se mazat najednou celý (~256 KB, cca. 2 ms)
• počet zápisů do stejné stránky omezen (10k/5k/3k)
• rozpoznání uvolněných bloků (operace TRIM)
• vadí časté zápisy do stejného sektoru (např. aktualizace timestampu posledního přístupu v i-nodech nebo změnový žurnál)