Na tomto místě bude oficiální zadání vaší práce

Na tomto místě bude oficiální zadání vaší práce • Toto zadání je podepsané děkanem a vedoucím katedry, • musíte si ho vyzvednout na studiĳním oddělení Katedry počítačů na Karlově náměstí, • v jedné odevzdané práci bude originál tohoto zadání (originál zůstává po obhajobě na katedře), • ve druhé bude na stejném místě neověřená kopie tohoto dokumentu (tato se vám vrátí po obhajobě).

i

ii

České vysoké učení technické v Praze Fakulta elektrotechnická Katedra počítačů

Diplomová práce

Defragmentace dat na pevném disku Bc. Tomáš Dosoudil

Vedoucí práce: Ing. Ivan Šimeček, Ph.D.

Studĳní program: Elektrotechnika a informatika, strukturovaný, Navazující magisterský Obor: Výpočetní technika 30. prosince 2010

iv

v

Poděkování Mé velké díky patří rodičům, kteří mě nikdy nepřestali podporovat a vždy ve mně věřili a také mé přítulkyni Lucce, která mi byla vždy oporou. V neposlední řadě bych také rád poděkoval vedoucímu práce Ing. Ivanu Šimečkovi, Ph.D., díky kterému mohla tato práce vzniknout.

vi

vii

Prohlášení Prohlašuji, že jsem práci vypracoval samostatně a použil jsem pouze podklady uvedené v přiloženém seznamu. Nemám závažný důvod proti užití tohoto školního díla ve smyslu §60 Zákona č. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon).

V Praze dne 31. 12. 2010

.............................................................

viii

Abstract The main goal of this thesis is to describe problems of data fragmentation and how modern file systems deal with. The second part of this thesis is focused on UFS file system and deal with an implementation of a tool for defragmentation.

Abstrakt Cílem této práce je popsat problematiku fragmentace dat na pevném disku a také to, jak se jí moderní souborové systémy snaží předcházet. Druhá část práce se věnuje konkrétně souborovému systému UFS a zabývá se implementací programu na odstranění fragmentace v tomto souborovém systému.

ix

x

Obsah 1 Úvod

1

2 Projekt OpenBSD 2.1 Historie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Přednosti operačního systému . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 3 3

3 Souborový systém UFS 3.1 Historie . . . . . . . . . . . . . . . . . . 3.2 Naformátování nového diskového oddílu 3.3 Vnitřní struktura . . . . . . . . . . . . . 3.3.1 Boot block . . . . . . . . . . . . 3.3.2 Super-block . . . . . . . . . . . . 3.3.3 Cylinder group block . . . . . . . 3.3.3.1 Bitmapa . . . . . . . . 3.3.4 Inode block . . . . . . . . . . . . 3.3.5 Data block . . . . . . . . . . . . 3.3.6 Alokace nového inodu . . . . . . 3.3.7 Alokace nového datového bloku . 4 Fragmentace 4.1 Co je fragmentace . . . . . . . . 4.2 Stárnutí souborového systému . . 4.2.1 Vytváření nového souboru 4.2.2 Zvětšování souboru . . . . 4.2.3 Mazání souboru . . . . . 5 Pevný disk 5.1 Geometrie pevného disku 5.2 Hlava . . . . . . . . . . . 5.2.1 Settle time . . . . 5.2.2 Latency . . . . . . 5.2.3 Track-to-Track . . 5.2.4 Positioning . . . . 5.2.5 Full stroke . . . . . 5.3 Access time . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . .

. . . . . . . .

. . . . .

. . . . . . . .

xi

. . . . .

. . . . . . . .

. . . . .

. . . . . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . .

. . . . . . . . . . .

. . . . .

. . . . . . . .

. . . . . . . . . . .

5 . 5 . 5 . 6 . 6 . 6 . 8 . 9 . 9 . 10 . 10 . 12

. . . . .

. . . . .

15 15 16 16 17 17

. . . . . . . .

19 19 20 20 20 21 21 21 21

. . . . . . . .

xii

6 Předcházení fragmentace 6.1 Variabilita velikosti uložených dat 6.2 Rezerva volného místa . . . . . . . 6.3 Před-alokování . . . . . . . . . . . 6.4 Zpožďování alokace . . . . . . . . . 6.5 Extents . . . . . . . . . . . . . . . 6.6 Souborový systém UFS . . . . . . 6.6.1 Rezerva volného místa . . . 6.6.2 Skupiny cylindrů . . . . . . 6.6.3 Fronta přístupů na disk . .

OBSAH

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

23 23 24 24 25 25 25 25 26 26

7 Analýza a návrh řešení 7.1 Defragmentace oblasti Inode block . . . . . . . 7.2 Defragmentace oblasti Data block . . . . . . . . 7.3 Identifikace bloků . . . . . . . . . . . . . . . . . 7.3.1 Úvaha o velkém počtu malých souborů . 7.3.2 Úvaha o malém počtu velkých souborů . 7.3.3 Nejhorší stav pro identifikaci bloků . . . 7.4 Seřazení bloků . . . . . . . . . . . . . . . . . . 7.4.1 Optimalizace na souvislost . . . . . . . . 7.4.2 Optimalizace na počet přesunů . . . . . 7.4.3 Optimalizace na fragmenty . . . . . . . 7.5 Využití paměti . . . . . . . . . . . . . . . . . . 7.6 Přesuny bloků . . . . . . . . . . . . . . . . . . . 7.6.1 Bez možnosti ztráty dat . . . . . . . . . 7.6.2 Možnost ztráty jednoho souboru . . . . 7.6.3 Možnost ztráty celé skupiny cylindrů . . 7.7 Algoritmy pro přesun bloků . . . . . . . . . . . 7.7.1 Naivní algoritmus . . . . . . . . . . . . 7.7.2 Algoritmus úplného seřazení . . . . . . . 7.7.3 Algoritmus bez zbytečných přesunů . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 34 34 35 36

8 Implementace 8.1 Vstupní parametry a inicializace . . . . . . . . . . . . . . . 8.2 Namapování skupiny cylindrů do paměti . . . . . . . . . . . 8.2.1 Paměťové nároky . . . . . . . . . . . . . . . . . . . . 8.3 Identifikace bloků . . . . . . . . . . . . . . . . . . . . . . . . 8.3.1 Paměťové nároky . . . . . . . . . . . . . . . . . . . . 8.4 Seřazení bloků . . . . . . . . . . . . . . . . . . . . . . . . . 8.5 Výpis informací . . . . . . . . . . . . . . . . . . . . . . . . 8.6 Přístup k datům . . . . . . . . . . . . . . . . . . . . . . . . 8.6.1 Přímý přístup k blokům . . . . . . . . . . . . . . . . 8.6.2 Přístup k blokům s namapovanou skupinou cylindrů 8.7 Přesun bloků . . . . . . . . . . . . . . . . . . . . . . . . . . 8.7.1 Vyhledání volného bloku . . . . . . . . . . . . . . . . 8.7.2 Příprava přesouvaných bloků . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

39 40 41 42 42 44 45 45 46 46 46 47 47 48

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

OBSAH

8.8

xiii

8.7.3 Triple sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 8.7.4 Hop sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 Uvolnění prostředků . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

9 Testování funkčnosti 9.1 Testování defragmentace . 9.2 Testování konzistence dat 9.3 Velikost diskového oddílu 9.4 Testovaná data . . . . . . 9.5 Testovací nástroje . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

53 53 53 54 54 54

10 Měření 10.1 Měření 1 . . . . . . . . . . . . . . . . . . . . . . . 10.2 Měření 2 . . . . . . . . . . . . . . . . . . . . . . . 10.3 Měření 3 . . . . . . . . . . . . . . . . . . . . . . . 10.4 Zrychlení souborového systému po defragmentaci

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

55 55 55 56 56

. . . .

59 59 59 60 60

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

11 Závěr 11.1 Fragmentace souborových systémů 11.2 Vlastní implementace . . . . . . . 11.2.1 Potenciální vylepšení . . . . 11.3 Výsledky defragmentace . . . . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

A Seznam použitých zkratek

63

B Nástroj fragfile.sh

65

C Nástroj autofrag.sh

67

D Ukázka programu

71

E BSD licence

75

F Obsah přiloženého CD

77

xiv

OBSAH

Seznam obrázků 3.1 3.2 3.3

Rozložení souborového systému. . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Princip adresace pomocí přímých a nepřímých odkazů. . . . . . . . . . . . . . 11 Struktura bloku na disku, fragmentu a UFS bloku. . . . . . . . . . . . . . . . 12

4.1 4.2 4.3 4.4

Rozmístění fragmentů jednoho souboru. . . . . . . . . . . . . . . Rozdělení nového souboru z důvodu fragmentace volného místa. . Rozdělení stávajícího souboru po jeho zvětšení. . . . . . . . . . . Fragmentace v rámci oblasti. . . . . . . . . . . . . . . . . . . . .

5.1

Geometrie disku. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

7.1 7.2 7.3

Pohled na souborový systém po smazání jednoho ze souborů. . . . . . . . . . 32 Průběh zpracování u naivního algoritmu. . . . . . . . . . . . . . . . . . . . . . 36 Průběh zpracování u algoritmu bez zbytečných přesunů. . . . . . . . . . . . . 38

8.1 8.2 8.3 8.4 8.5

Průchod programem. . . . . . . . . Vazba mezi polem blockap a slink. Určení cílové pozice bloku. . . . . . Model funkcí pro přístup k datům. Přesun bloků metodou Triple sort.

. . . . .

xv

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

16 17 17 18

39 43 45 46 50

xvi

SEZNAM OBRÁZKŮ

Seznam tabulek 3.1

Přednastavené hodnoty pro UFS. . . . . . . . . . . . . . . . . . . . . . . . . .

6

7.1

Počet přístupů na disk.

8.1 8.2 8.3

Hodnoty kterých může nabývat proměnná flags ve struktuře GLBVAL. . . . . . 41 Hodnoty kterých může nabývat proměnná flags ve struktuře BLOCKARRS. . . . 44 Hodnoty kterých může nabývat proměnná flags ve struktuře SWPDATA. . . . . 48

10.1 10.2 10.3 10.4

Naměřené hodnoty při defragmentaci 1050 souborů. . . . . . . . . . . . . . Naměřené hodnoty při defragmentaci 850 souborů. . . . . . . . . . . . . . . Naměřené hodnoty při defragmentaci bloků, které jsou adresovány nepřímo. Rychlost čtení souborů v závislosti na velikostech fragmentů. . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

xvii

. . . .

56 56 56 58

xviii

SEZNAM TABULEK

Kapitola 1

Úvod Tato práce se zabývá problémem fragmentace uložených dat na souborovém systému. Snaží se vysvětlit co vlastně fragmentace je, a z jakých důvodů k ní dochází. To, jakým způsobem se data na pevném disku fragmentují, silně závisí na souborovém systému. Pro tuto práci jsem zvolil souborový systém UFS. Jedním z důvodů této volby bylo to, že se jedná o starší souborový systém, který je jednak implementován v řadě unixů a bsd systémů, ale také mnoho modernějších souborových systému funguje na podobných principech. Součástí práce je i program, který se do jisté míry snaží fragmentaci odstranit. Program je programovaný v souladu s normou ANSI C a využívá systémových hlaviček operačního systému OpenBSD. Výsledný zdrojový kód bude poskytnut komunitě pod licencí BSD. Kapitola 1: Seznámení se záměrem této práce. Kapitola 2: Seznámení s projektem OpenBSD, pro který je nástroj pro odstranění fragmentace implementován. Kapitola 3: Popis souborového systému UFS. Jelikož součástí této práce je implementace defragmentace, je naprosto nezbytné seznámit se s konkrétním souborovým systémem. Kapitola 4: Obecné vlastnosti fragmentace. Definice fragmentace a vysvětlení, proč nám fragmentace vadí. Kapitola 5: Popis pevného disku a princip vystavení čtecí a zapisovací hlavy disku. Rozdíly v časech u jednotlivých typů vystavení hlavy disku a vliv fragmentace. Kapitola 6: Jak se v praxi souborové systémy brání fragmentaci. Kapitola 7: Tato kapitola popisuje analýzu problému a současně navrhuje několik způsobů řešení. Kapitola 8: Samotná implementace defragmentace pro UFS. Obsahuje již konkrétní řešení, která byla navržena v předchozí kapitole. Kapitola 9: Testování funkčnosti programu a způsoby testování. Kapitola 10: Měření rychlosti defragmentace a zrychlení souborového systému po defragmentaci.

1

2

KAPITOLA 1. ÚVOD

Kapitola 11: Zhodnocuje výsledky implementace. Současně shrnuje nedostatky implementace a návrhy na jejich zlepšení.

Kapitola 2

Projekt OpenBSD Jelikož se většina této práce zabývá souborovým systémem UFS a konkrétně implementací pod operačním systémem OpenBSD, tak si v této kapitole projekt stručně popíšeme.

2.1

Historie

Operační systém BSD se začal vyvíjet v 70. letech na Kalifornské univerzitě v Berkley. Jednalo se o jakýsi protipól tehdejšího Unixu. Poslední verze, která byla pod záštitou univerzity vydána, byla 4.4BSD. Díky licenci BSD, která umožňovala v podstatě libovolné využití zdrojových kódů, zde mohli začít vznikat komunitní projekty. Za přímé následníky verze 4.3BSD a 4.4BSD se mohou považovat komunitní projekty FreeBSD a NetBSD. V roce 1995 se díky neshodám v komunitě NetBSD část vývojářů rozhodla tento projekt opustit a v čele s Theo de Raadtem zakládají nový projekt OpenBSD. V době psaní této práce vyšla nová verze OpenBSD 4.8, která podporuje 17 architektur, jako např. alpha, amd64, i386, sqi, sparc, vax atd.

2.2

Přednosti operačního systému

Celý projekt je zaměřen především na bezpečnost, která jde často na úkor uživatelské přívětivosti. Díky této filozofii, „Secure by default“ jak ji vývojáři často nazývají, zde za posledních 10 let byly jen dvě chyby, které umožňovaly vzdálené převzetí kontroly nad operačním systémem. Jelikož hlavní servery projektu jsou umístěny v Kanadě, tak se na ně nevztahuje restriktivní omezení tykající se šíření kryptografických materiálů jako na podobné projekty, které mají servery v USA. To vedlo k tomu, že součástí systému vždy byly pokročilé šifrovací metody. Součástí operačního systému OpenBSD je projekt OpenSSH, který slouží pro vzdálené přístupy, a který byl později naportován i do většiny linuxových systémů. Domovská stránka projektu je http://www.openbsd.org

3

4

KAPITOLA 2. PROJEKT OPENBSD

Kapitola 3

Souborový systém UFS 3.1

Historie

Souborový systém UFS doslova znamená Unix File Sytem a patří mezi jedny z nejstarších unixových souborových systémů. Do operačního systému BSD, konkrétně do verze 4.2BSD, byl poprvé implementován v roce 1984. O implementaci, a současně i o jeho dnešní podobu, se značně zasadil Marshall Kirk McKusick [5]. Za jednu z novodobých nevýhod se ukázala 32 bitová adresace bloků. Za předpokladu použití nejmenšího datového bloku, tj. 512 B, může být maximální kapacita souborového systému 2 TB. To se v dnešní době ukázalo jako nedostatečné, a proto se v roce 2003 přišlo se UFS2 souborovým systémem, který mimo jiné používá 64 bitovou adresaci.

3.2

Naformátování nového diskového oddílu

V BSD systémech se souborový systém vytváří pomocí příkazu newfs. Oproti jiným souborovým systémům se neformátuje přímo diskový oddíl. Disk, resp. diskový oddíl, je ještě třeba rozdělit pomocí nástroje disklabel. V rámci jednoho disku je možné provést rozdělení až na 15 oddílů značících se a-p, kde c reprezentuje celý disk a nelze jej modifikovat. Po rozdělení jsou jednotlivé oddíly zpřístupněny v adresáři /dev. Například první oddíl značící se a na prvním pevném disku, který je připojený pomocí rozhraní PATA, bude zpřístupněn jako /dev/wd0a. Po vytvoření oddílu lze vybraný oddíl naformátovat již zmíněným nástrojem newfs. Formátování lze ovlivnit několika parametry. Jedním z parametrů, který do značné míry ovlivňuje výkonnost celého souborového systému, je velikost bloku, kde blok je uvažován v kontextu souborového systému. Nejedná se tedy o diskový blok typické velikosti 512 B. Minimální velikost bloku je 4096 B. Tato velikost byla zvolena z toho důvodu, aby soubor o velikosti 232 B mohl být adresovatelný nanejvýše dvěma stupni indirekce. Blok se dále dělí na fragmenty. Fragment je nejmenší adresovatelná jednotka v rámci souborového systému a jeho minimální velikost je 512 B, což současně odpovídá typicky nejmenší adresovatelné jednotce pevného disku. Počet fragmentů v bloku může být 2, 4 nebo 8. Během formátování nového oddílu, se oddíl rozdělí na několik dalších skupin po sobě jdoucích cylindrů. V terminologii UFS se tyto skupiny cylindrů nazývají cylinder groups.

5

6

KAPITOLA 3. SOUBOROVÝ SYSTÉM UFS Parametr Velikost bloku Velikost fragmentu Počet fragmentů Velikost skupiny cylindrů Počet inodů na skupinu cylindrů Typ UFS

Hodnota 16384 B 2048 B 8 12958 bloků 25984 UFS1

Tabulka 3.1: Přednastavené hodnoty pro UFS. Vždy musí být vytvořeny alespoň 4 skupiny cylindrů. Shora je počet omezen jen maximální velikostí souborového systému. Tabulka 3.1 shrnuje hodnoty nejdůležitějších parametrů, které jsou přednastaveny, a nebo jsou typické pro většinu pevných disků. Pokud nebude řečeno jinak, tak se budou v následujícím textu u výpočtů uvažovat tyto hodnoty.

3.3

Vnitřní struktura

Obrázek 3.1 znázorňuje rozložení souborového systému UFS [6] na pevném disku, kterým se v této kapitole budeme podrobněji zabývat. Souborový systém se skládá z několika skupin cylindru, tj. cylinder groups, a na prvním z nich se nachází Boot block, který obsahuje informace potřebné k zavedení systému. Za ním následuje Super-block, který je umístěn stejně jako Boot block na pevně dané adrese, resp. offsetu, od začátku oddílu. Za Super-blockem následuje již rozložení, které se bude opakovat na všech ostatních skupinách cylindrů, tj. Cylinder group block, Inode block a Data block. Informace týkající se základního rozložení a struktury jednotlivých bloků lze nalézt v hlavičkovém souboru src/sys/ufs/ffs/fs.h.

3.3.1

Boot block

Jak již bylo řečeno, Boot block obsahuje potřebné informace k zavedení systému. Jedná se v podstatě o program napsaný v assembleru, který je umístěn na prvních 512 B diskového oddílu. Tomuto programu, resp. fázi bootování, se říká first-stage. Úkolem této fáze je načíst fázi dvě, tedy second-stage, která již načte kernel. Drobná komplikace v načítání kernelu je ta, že druhá fáze stále nerozumí souborovému systému. Řešení je takové, že kořenový adresář pro daný souborový systém má číslo inodu vždy 2. Inode se nachází na první skupině cylindrů, před kterou je pouze Super-block, který má ovšem svou velikost a pozici pevně danou.

3.3.2

Super-block

Super-block se nachází na první skupině cylindrů a primárně je jeho offset 8192 B, resp. 65536 B, dle typu UFS. Jelikož obsahuje několik kritických informací, jako např. geometrie disku nebo rozložení souborového systému, tak je současně nakopírován do skupin cylindrů, a to z důvodu prevence proti poškození. Většina těchto kritických informacích se zapíše

3.3. VNITŘNÍ STRUKTURA

7

Obrázek 3.1: Rozložení souborového systému.

během vytváření souborového systému a pozdější změny již nejsou možné. Super-block ovšem obsahuje i řadu informací, které jsou během užívání operačním systémem nastavovány, jako např. počet souborů a adresářů. Některé lze také nastavit pomocí nástroje tunefs. Veškeré informace obsažené v bloku jsou popsány strukturou struct fs. Mezi nejdůležitější položky patří: • fs_cblkno - Offset do prvního Cylinder group bloku. • fs_iblkno - Offset do prvního bloku inodů. • fs_dblkno - Offset do prvního datového bloku. • fs_cgoffset - Offset mezi skupinou cylindrů. • fs_ffs1_time - Čas posledního zápisu. • fs_ncg - Počet skupin cylindrů. • fs_bsize - Velikost bloku v bytech.

8

KAPITOLA 3. SOUBOROVÝ SYSTÉM UFS

• fs_fsize - Velikost fragmentu v bytech. • fs_minfree - Minimální počet volných bloků v procentech. • fs_frag - Počet fragmentů v bloku. • fs_cgsize - Velikost skupiny cylindrů v bytech. • fs_ncyl - Počet cylindrů. • fs_cpg - Počet cylindrů na skupinu. • fs_ipg - Počet inodů na skupinu cylindrů. • fs_fpg - Celkový počet fragmentů na skupinu cylindrů. • fs_clean - Clean flag. • fs_magic - Magic číslo1 pro UFS. Jedna z položek struktury, která přímo ovlivňuje fragmentaci, je fs_minfree. Ta udává minimální počet volných bloků v procentech. Defaultně je nastavena na 5%, což se považuje jako minimum, nicméně se doporučuje hodnotu nastavit alespoň mezi 10-15%. Uvažujeme-li 5% hodnotu, tak po vyčerpání 95% všech bloků již běžný uživatel nemůže dál vytvářet nové soubory na disku, resp. alokovat nové bloky. Pouze uživatel root může dál alokovat nové bloky. Toto omezení je zde právě kvůli omezení fragmentace souborů, jelikož po překročení určité meze alokovaných bloků, je již velmi obtížné nalézt souvislý úsek bloků na disku. Nutno poznamenat, že volný blok znamená, že v našem případě všech 8 fragmentů v bloku je nealokovaných. Pokud je alespoň jeden fragment obsazený, tak se již nejedná o volný blok, ačkoliv zbývajících 7 fragmentů může být volných. Tento fakt může vést např. k situaci, kdy nám operační systém hlásí, že je disk zaplněn, přestože nám např. příkaz df ukazuje, že je na něm stále dostatek místa. Teoreticky je možné, že po zaplnění pouze 1/8 datové oblasti souborového systému nám operační systém nedovolí vytvořit nový soubor o velikosti bloku z důvodu, že je již zaplněn. Tato situace může nastat, pokud se systém zaplní velkým počtem souborů, které jsou nanejvýš 2048 B velké, tj. o velikosti fragmentu. Pokud se následně konkrétní soubory smažou tak, že vždy v rámci jednoho bloku 7 souborů odstraníme a jeden zůstane, pak přestože bude souborový systém ze 7/8 volný, nebude možné vytvořit nový soubor o velikosti alespoň jednoho bloku.

3.3.3

Cylinder group block

Cylinder group block je rozdělen na tři části, a to na datovou strukturu struct cg a dvě bitmapy. Struktura obsahuje kromě konkrétních informací pro danou skupinu cylindrů také několik duplicitních informací, které již obsahuje Super-block. Mezi nejdůležitější položky patří: • cg_time - Čas posledního zápisu. 1

Magic číslo pro UFS2 je 0x19540119 a jedná se o „zakódované“ datum narození Marshalla Kirk McKusicka, tedy 19.1.1954.


9

• cg_cgx - Číslo skupiny cylindrů. • cg_ncyl - Počet cylindrů ve skupině. • cg_niblk - Počet inodů. • cg_ndblk - Počet datových bloků. • cg_cs - Jedná se o strukturu shrnující počet adresářů, bloků, fragmentů atd. • cg_iusedoff - Offset na bitovou mapu idnodů. • cg_freeoff - Offset na bitovou mapu volných fragmentů. Každá skupina cylindrů si současně shromažďuje informace o svém stavu alokovaných jednotek. Tyto informace jsou uloženy ve struktuře struct csum a obsahuje tyto položky: • cs_ndir - Počet adresářů nacházejících se na skupině cylindrů. • cs_nbfree - Počet volných bloků. • cs_nifree - Počet volných inodů. • cs_nffree - Počet volných fragmentů. 3.3.3.1

Bitmapa

Ve stejném bloku za strukturou struct cg, je umístěna bitová mapa použitých inodů. V bitové mapě je použitý inode nastaven na 1. Za mapou inodů je bitová mapa volných fragmentů, kde volný fragment je v bitové mapě nastaven na 1. Velikost skupiny cylindrů je mimo jiné limitována tím, že se struktura struct cg, bitová mapa inodů a především bitová mapa volných fragmentů, musí společně vejít do jednoho bloku.

3.3.4

Inode block

Inode block obsahuje tabulku inodů. Inode, neboli index node, je datová struktura uchovávající metadata o konkrétním souboru. Inode může mít dvě podoby, a to buď inode, který je v operační paměti nebo inode uložený na disku. Nás bude zajímat druhá varianta, tedy inode na disku, jemuž se také říká dinode. Velikost dinodu se odvíjí od verze UFS a je 128 B, resp. 256 B a popsána strukturou struct ufs1_dinode, resp. struct ufs2_dinode. Je třeba mít na paměti, že z důvodu velikosti dinodu není možné každý dinode přímo adresovat, ať už přímo na pevném disku nebo v rámci souborového systému. Pro přístup k jednotlivým dinodům je zapotřebí načíst celý blok, resp. fragment. Ofset fragmentu se vypočítá pomocí makra: #define ino_to_fsbo(fs, x)

((x) % INOPB(fs))

10


Kde fs je odkaz na struct fs a x je číslo požadovaného inodu. INOPB je počet dinodu na blok. Mezi nejdůležitější položky dinodu ve struktuře struct ufs1_dinode patří: • di_size - Velikost souboru. • di_db[NDADDR] - Přímé odkazy na datové bloky. • di_ib[NIADDR] - Nepřímé odkazy. • di_uid - UID vlastníka souboru. • di_gid - GID vlastníka souboru. Počet přímých odkazů je 12. Pokud soubor přesáhne velikost 192 kB, tak je třeba použít nepřímé odkazy. Tyto odkazy jsou celkem 3, a to odkazy první, druhé a třetí úrovně. V případě první nepřímé úrovně odkaz di_ib[0] ukazuje na datový blok, který místo samotných dat souboru, obsahuje odkazy na datové bloky a teprve tyto bloky obsahují data patřící souboru. Princip adresace pomocí přímých a nepřímých odkazů je zobrazen na Obrázku 3.2. To, kolik odkazů se vejde do bloku u nepřímé adresace, záleží jednak na velikosti bloku, a pak na velikosti, resp. datovém typu samotného odkazu. Pro UFS1 je velikost 4 B a pro UFS2 je to 8 B. Pro výpočet lze použít vzorec 3.1. V našem případě na jeden blok připadá 4096 odkazů. odkazu_v_bloku = velikost_bloku/velikost_odkazu

(3.1)

Informace týkající se dinodu jsou v hlavičkovém souboru src/sys/ufs/ufs/dinode.h.

3.3.5

Data block

Skládá se z bloků, které slouží k uložení dat ze souboru, nebo bloků obsahující nepřímé odkazy. V datové oblasti by alokovaný blok, resp. fragment, měl být pevně svázán s konkrétním inodem pomocí odkazu. To znamená, že pokud nedojde k chybě v systému, tak ke každému bloku, resp. fragmentu, bychom měli být schopni dohledat inode, který na něj ukazuje. Struktura bloku na disku, fragmentu a bloku UFS je znázorněna na Obrázku 3.3.

3.3.6

Alokace nového inodu

Alokaci nového inodu má na starosti funkce ffs_inode_alloc. Jejím prvním úkolem je zjistit, zda inode bude typu adresář či ne. Při výběru skupiny cylindrů a následného vhodného umístění, se bere v potaz řada parametrů. Jedná se o preference inodu na jeho umístění. Následující rutina je použita pro alokaci inodu typu soubor. Pokud v konkrétním bodě není možné požadavky uspokojit, přechází se na další. 1. Alokuj preferovaný inode. 2. Alokuj inode na stejné skupině cylindrů, kde je umístěn nadřazený adresář.


11

Obrázek 3.2: Princip adresace pomocí přímých a nepřímých odkazů.

3. Zvol jinou skupinu cylindrů pomocí kvadratické hashe a pokus se alokovat nový inode. Pokud inode alokovat nelze, pokračuj ve výběru dalších skupin cylindrů. Jestliže je výběr nového inodu bez preferencí na umístění, pak bude použit tento postup: 1. Alokuj inode na první skupině cylindrů. 2. Zvol jinou skupinu cylindrů pomocí kvadratické hashe a pokus se alokovat nový inode. Pokud inode alokovat nelze, pokračuj ve výběru dalších skupin cylindrů. Kvadratická hash se používá z důvodu její rychlosti naléznutí nepoužitého pole v téměř zaplněné tabulce. Pokud má souborový systém nastavenou alespoň 10 % rezervu, tak se použĳe jen zřídka. Pokud zde není žádná rezerva a souborový systém je téměř zaplněn, tak alokace probíhá spíše náhodně [4]. Pokud nový inode bude typu adresář, bude zavolána funkce ffs_dirpref, která bude mít na starost vybrat vhodnou skupinu cylindrů. Pří výběru se bere v úvahu několik kritérií.

12


Obrázek 3.3: Struktura bloku na disku, fragmentu a UFS bloku.

• Vyber stejnou skupinu cylindrů, jako nadřazený adresář. • Skupina cylindrů musí obsahovat dostatek místa pro následující soubory adresářů. • Zohledni počty adresářů na skupině cylindrů. • Omez počet adresářů, které by byly na skupinu cylindrů umístěny hned za sebou. • Pokud se jedná o první stupeň adresáře, umísti ho v jiné skupině cylindrů. Zmiňované funkce jsou umístěné v src/sys/ufs/ffs/ffs_alloc.c.

3.3.7

Alokace nového datového bloku

Při každém požadavku na alokaci nového bloku či fragmentu, je použita funkce ffs_alloc. Podobně jako při výběru nového inodu, tak i zde mohou být součástí výběru různá preferenční kritéria, podle kterých rozhodnou jaký blok vybrat. Kritériem je např. umístění inodu, umístění jiných bloků inodu nebo počet alokovaných bloků na konkrétní skupině cylindrů. Výběr vhodného bloku nastane v jednom z následujících kroků: 1. Alokuj požadovaný blok. 2. Alokuj blok na stejném cylindru. 3. Alokuj blok na stejné skupině cylindrů. 4. Zvol jinou skupinu cylindrů pomocí kvadratické hashe. Pokud nelze blok alokovat, pokračuj ve výběru dalších skupin cylindrů. Pokud je výběr bloku bez preferencí na umístění, pak bude použit tento postup: 1. Alokuj blok na stejné skupině cylindrů jako je inode. 2. Zvol jinou skupinu cylindrů pomocí kvadratické hashe. Pokud nelze blok alokovat, pokračuj ve výběru dalších skupin cylindrů.


13

Součástí kroku 2 bývala i podmínka, aby byl blok vzhledem k rotaci disku optimálně umístěn od předchozího bloku. Ačkoliv se v dokumentacích, a i v komentáři ve zdrojových kódech, tato podmínka často vyskytuje, tak již není pravdivá. Při alokaci bloku se rotace disku nezohledňuje2 .

2

Dle CVS byla tato vlastnost odstraněna v revizi 1.60.

14


Kapitola 4

Fragmentace V kapitole o fragmentaci si vysvětlíme co fragmentace vlastně je, jak je chápána v modernějších souborových systémech a jaký má vliv na výkonnost souborového systému [2]. Fragmentaci si budeme popisovat nezávisle na konkrétním typu souborového systému.

4.1

Co je fragmentace

Již ze samotného slova fragmentace je patrné, že se jedná o jakési fragmenty, tzn. menší části z celku. V kontextu souborového systému fragmentace souboru znamená jeho rozdělení na několik menších částí. Nejprve se pokusme definovat soubor, který není fragmentovaný. Definice 4.1.1. Soubor není fragmentovaný, pokud je zapsaný v jedné sekvenční posloupnosti na disku. Soubory, které této definici nevyhovují, jsou fragmentované. Za fragmentované soubory můžeme ve většině případů považovat i takové soubory, které sice jsou zapsány souvisle v jedné oblasti, ale nejsou zapsány sekvenčně. Příkladem může být soubor s přehozenými fragmenty na obrázku 4.1. Pro načtení druhého fragmentu je třeba překonat fragmenty 3, 4, 6, 5. Pokud budou fragmenty dostatečně veliké, např. větší než jeden cylindr, tak se již nebudou číst, ale přeskočí se. Záměrně se již bavíme o fragmentech, a ne o blocích, jelikož fragment se může skládat z několika bloků. Vyhovět definici 4.1.1 nejspíš mohly jen jedny z prvních souborových systémů. Modernější souborové systémy, jako např. popsaný UFS v kapitole 3, záměrně své datové oblasti rozdělují do menších částí. Jiné souborové systémy např. po určitém počtu bloků vkládají blok s meta-informacemi. To se provádí buď z důvodu snížení budoucí fragmentace, nebo kvůli jiným optimalizacím. S ohledem na modernější souborové systémy, již nemá smysl zabývat se fragmentací definovanou v 4.1.1, jelikož ta pro větší soubory nastane vždy. Budeme-li tedy brát v potaz nové trendy ve vývoji souborových systémů, a než samotnou fragmentací se budeme zabývat jen fragmentací, která má negativní vliv na výkon, pokusme se opět nejprve definovat fragmentaci, která nemá negativní vliv na výkonnost souborového systému.

15

16

KAPITOLA 4. FRAGMENTACE

Obrázek 4.1: Rozmístění fragmentů jednoho souboru.

Definice 4.1.2. K soubor, který je fragmentovaný a neovlivňuje negativně výkonnost souborového systému, by měl být přístup z pohledu souborového systému stejně rychlý, jako k souboru nefragmentovanému. Jinými slovy, pokud např. čteme fragmentovaný soubor, tak čas potřebný k vystavení čtecí hlavy disku na začátek následujícího fragmentu, by neměl ovlivnit dobu celkového čtení souboru. Tato podmínka nemusí být za všech okolností splněna. Například u UFS předem neznáme velikost segmentu na skupině cylindrů, a čas pro přístup na jinou skupinu cylindrů je závislý na vzdálenosti této skupiny. Nicméně definice 4.1.2 se pro naše účely defragmentace zdá být postačující. Z definice mimo jiné vyplývá, že jedním z úkolů defragmentace je buď úplně odstranit, nebo alespoň minimalizovat čas potřebný na přechody mezi fragmenty.

4.2

Stárnutí souborového systému

Stárnutí souborového systému, je pojmem pro aktivně používaný souborový systém [9]. Stárnutím se myslí sled událostí, jako např. přidávání, upravování a mazání souborů. Opomenemeli fakt, kdy fragmentaci vytváří samotný souborový systém, tak právě tyto události vytvářejí fragmentaci, kterou můžeme nazvat jako nežádoucí. V následujících podkapitolách si popíšeme tři nejčastější způsoby, jak během stárnutí souborového systému, fragmentace vzniká.

4.2.1

Vytváření nového souboru

Vytvořením nového souboru, na minimálně zaplněném souborovém systému, vzniká jen fragmentace, která je úmyslně vytvořená tímto systémem. Představme si ale situaci, kdy se na již používaném systému snažíme vytvořit nový soubor. Tento soubor chceme umístit do adresáře, obsahujícího několik menších souborů, z nichž několik bylo v nedávné době smazaných. Situace je vyobrazena na obrázku 4.2. Zd je vidět, že nový soubor se bude muset rozdělit na několik menších fragmentů, aby mohl být zapsán do volných pozic.

4.2. STÁRNUTÍ SOUBOROVÉHO SYSTÉMU

17

Obrázek 4.2: Rozdělení nového souboru z důvodu fragmentace volného místa.

4.2.2

Zvětšování souboru

V tomto případě uvažujeme již uložený soubor. V podstatě nás nezajímá, jestli je, či není fragmentovaný. Podstatné je, že pokud za určitou dobu od jeho vytvoření budeme chtít soubor rozšířit, tak se již za posledním blokem nemusí nacházet volná pozice. Tuto novou část budeme tedy muset uložit jako samostatný fragment, viz obrázek 4.3.

Obrázek 4.3: Rozdělení stávajícího souboru po jeho zvětšení.

4.2.3

Mazání souboru

Mazáním souborů vzniká fragmentace volného místa [10], jako je na obrázku 4.4. To samo o sobě nemá negativní vliv na výkonnost souborového systému, avšak následné ukládání nových dat již může způsobit fragmentaci těchto dat. V podstatě se jedná o kombinaci dvou předchozích způsobů, kdy se buď nový soubor může uložit do jedné volné pozice, ale pro následné zvětšení již nebude dostatek místa v pozici, nebo nelze celý soubor do volné pozice umístit, a musí být fragmentován hned při ukládání. Fragmentace volného místa je zajímavá ještě z jiného hlediska, a to z hlediska, kdy častou obranou před fragmentací je určitá rezerva volného místa. Představme si nyní minimálně zaplněný souborový systém, kde v adresáři vytváříme několik souborů A o velikosti SA . Pro velikost SA platí, že SA << Sf rag , kde Sf rag je maximální velikost souvislé oblasti dat jakou povoluje souborový systém, aniž by byl soubor nuceně fragmentován a fragment tedy uložen na jinou pozici. Současně se zvyšováním počtu souborů A se nám na disku začne vytvářet oblast, např. v terminologii UFS můžeme uvažovat skupinu cylindrů, která bude oproti zbytku značně zaplněná. Pokud se smaže několik souborů A a vytvoří se nový soubor B o velikosti SB , kde pro SB platí, že SA << SB <= Sf rag , pak soubor B bude nutně

18

KAPITOLA 4. FRAGMENTACE

Obrázek 4.4: Fragmentace v rámci oblasti.

fragmentovaný. S počtem adresářů podobných tomuto, poroste i počet takto zaplněných oblastí, kde podobné soubory B budou vždy fragmentované. 0 >S Uvažme nyní situaci, kdy se soubor B zvětší do velikosti SB f rag . Pak původní data, 0 0 −S o velikosti SB , budou stále fragmentovaná, ale zbytek, o velikosti SBZ = (SB f rag ), bude umístěn do jiné oblasti. V případě minimálně zaplněného souborového systému bude zbytek, 0 , umístěn souvisle. Pokud by platilo, že S 0 o velikosti SBZ BZ > Sf rag , tak se sice bude dále fragmentovat, ale již se bude jednat o úmyslnou fragmentaci. Předpokládáme-li stále, že je na disku dostatek místa, tak z výše uvedených faktů vyplývá, že velké soubory mají menší tendenci k fragmentaci, než malé soubory, kde za malé soubory uvažujeme soubory o velikosti menší než Sf rag . Tuto úvahu potvrzuje studie [9]. Pro zvětší části zaplněné souborové systémy to již platit nebude, jelikož zbytek o velikosti 0 , se již může rozdělit do více fragmentů o velikosti menší než S SBZ f rag .

Kapitola 5

Pevný disk V této kapitole si popíšeme některé části pevného disku a také to, jak fragmentace ovlivňuje práci disku. Hlavním důvodem, proč se budeme zabývat pevným diskem, tedy HDD a ne např. SSD diskem či USB flash diskem, je jednak princip jakým přistupuje k datům, ale také i to, že se stále jedná o nejčastější typ úložiště. Oproti SSD či USB flash disku je součástí pevného disku čtecí a zápisová hlava, která se vždy musí vystavit na začátek požadovaného bloku a v případě fragmentace, čím více je soubor fragmentován, tím vícekrát se bude muset hlava zbytečně přesouvat. V následném popisu pevného disku nebudeme zabíhat do technologických detailů, ale budeme se držet jen takových součástí, které jsou pro nás z hlediska fragmentace zajímavé, a to jsou zejména: Plotna: Jedná se o skleněnou či kovovou rotující desku pokrytou magnetickou vrstvou, pro uložení dat. Její velikost je typicky 2,5“ či 3,5“ a rychlost rotace u osobních počítačů bývá 4900 ot/min až 10000 ot/min. Plotna může mít dva povrchy. Hlava: Hlava slouží k čtení a zápisu dat. S hlavou pohybuje vystavovací mechanizmus a tím je buď krokový motor nebo lineární motor. V kombinaci s pohybem hlavy a pod ní rotující plotnou, může hlava přistoupit na kteroukoliv část plotny. Počet hlav závisí na počtu povrchů. Vyrovnávací paměť: Je integrovaná v pevném disku a nejen že vyrovnává rozdíly mezi rychlostmi všech zúčastněných složek, ale především uchovává před-načtená data.

5.1

Geometrie pevného disku

Každá plotna je rozdělena do několika dílčích částí, které jsou zobrazeny na obrázku 5.1. Stopa: Stopy neboli tracks jsou soustředné kružnice na plotně. Plotna obsahuje stopy v řádu tisíců. Jejich číslování je rostoucí od 0, kde směr číslování je od vnější stopy k vnitřní. Cylindr: Stopy, které jsou umístěny nad sebou se nazývají cylindr. Stopy jsou nad sebou právě proto, že všechny plotny v disku mají stejnou geometrii. Sektor: Nejmenší adresovatelný úsek je sektor a typicky je velký 512 B.

19

20

KAPITOLA 5. PEVNÝ DISK

Obrázek 5.1: Geometrie disku.

5.2

Hlava

Ať už má pevný disk jednu hlavu či více hlav, tak na rychlosti přístupu k datům se podílí dvě složky. Jednou je rychlost otáčení plotny, která je typicky u stolních počítačů 7200 ot/min. Druhá složka je rychlost hlavy, resp. čas potřebný k vystavení halvy. Tento čas potřebný k vystavení hlavy není konstantní, jelikož nejenže záleží o jak velký kus budeme hlavu posouvat, ale také se zde projeví např. latence a čas potřebný k ustálení hlavy. Jelikož v české literatuře nejsou všechny následující názvy ustáleny, tak použĳi anglické názvy tak, jak jsou popisovány v [7].

5.2.1

Settle time

Settle time je čas potřebný k ustálení hlavy. Při každém pohybu se hlava nepatrně rozkmitá a po přesunutí na požadovanou stopu je nutné vyčkat, než se ustálí. Typickým časem pro ustálení je méně než 0.1 ms.

5.2.2

Latency

Jelikož se plotny soustavně otáčejí, tak po přesunu na konkrétní stopu není zaručeno, že se požadovaná data budou nacházet zrovna pod hlavou. To znamená, že je ve většině případů nutné vyčkat až se požadované data pod hlavu dostanou. V nejhorším případě hlava vyčkává po dobu jedné otáčky plotny. Pro výpočet průměrné hodnoty se používá vzorec 5.1. prum_latence =

1 ∗ 2

1 rpm_disku 60

∗ 1000 [ms]

(5.1)

Jak z rovnice vyplývá, ovlivňujícím faktorem je počet otáček disku za minutu. Průměrná latence bývá 3-8 ms.

5.3. ACCESS TIME

5.2.3

21

Track-to-Track

V tomto případě se již jedná o pohyb hlavy a konkrétně o přechod na vedlejší stopu. Typický čas bývá 2,5 ms, včetně doby pro ustálení hlavy.

5.2.4

Positioning

Jedná se o pohyb hlavy na libovolně vzdálenou stopu. Tento čas hraje důležitou roli např. u aplikací, které nepřistupují k datům sekvenčně, jako jsou např. databáze. Typický čas je 10 ms.

5.2.5

Full stroke

Full stroke je čas potřebný k přesunu hlavy přes celou šíři plotny, tedy přesun z první na poslední stopu. V reálných případech tento pohyb hlavy není nejběžnější, ale výrobci jej často uvádějí. Důvodem je nejspíš i to, že společně s Track-to-Track tvoří meze pro positioning. Typický čas je 17 ms.

5.3

Access time

Z předchozí podkapitoly je zřejmé, že fragmentace, resp. z pohledu pevného disku zbytečný pohyb hlavy, bude mít negativní vliv na celkovou dobu přístupu. Tu lze pomocí vzorce 5.2 snadno vypočítat [1]. Taccess = Tseek + Tlatency + Tsettle + Trw

(5.2)

Poslední tři časy, včetně času pro zápis či čtení Trw , nelze z pohledu souborového systému nĳak ovlivnit, ale čas Tseek může být ovlivněn alespoň částečně. Čas Tseek je čas potřebný pro samotný pohyb hlavy, tedy jeden z typů Track-to-Track, Positioning nebo Full stroke. To, o jaký typ se bude jednat, lze ovlivnit mírou fragmentace. Budeme-li např. číst soubor bez fragmentace, tak se hlava bude pohybovat po stopách, tedy Track-to-Track. Jedna z optimalizací pevných disků je tzv. read-ahead [3]. To znamená před načítání dat, která budeme potenciálně v budoucnu potřebovat. V případě čtení libovolného úseku se zároveň před načte i několik dalších sektorů, či případně celá stopa. Pokud máme tedy fragmentovaný soubor v rámci před načtených dat, či např. přistupujeme k menším fragmentům v rámci jedné před načtené oblasti, tak se čtení provede jen jednou. Následné čtení se bude provádět z vyrovnávací paměti disku. Další optimalizací, která současně minimalizuje dopad fragmentace, je tzv. zero-latency. V předchozí podkapitole bylo popsáno, že čtecí hlava musí vyčkat, v nejhorším případě po dobu jedné otáčky plotny, než se požadovaná data dostanou pod hlavu. Princip zerolatency spočívá v tom, že čtecí hlava začne číst hned v momentě, kdy je přesunuta nad požadovanou stopu. Během jedné otáčky se přečte celá stopa, která se poté v paměti disku logicky přerovná. Dle vzorce 5.1 vychází, že v případě čtení více jak půl stopy se tato technika vždy vyplatí.

22

KAPITOLA 5. PEVNÝ DISK

Kapitola 6

Předcházení fragmentace V této kapitole si popíšeme obecné principy, a to jak moderní souborové systémy předcházejí fragmentaci a případně jak se s ní vypořádají. Z předchozí kapitoly 4 víme, že v některých případech fragmentaci souboru nelze zabránit. Nicméně, jak již bylo zmíněno, fragmentace souboru je pro nás negativním aspektem až v momentě, kdy ovlivňuje výkonnost práce s tímto souborem. Z toho mimo jiné vyplývá, že práci s fragmentovanými soubory značně ovlivňují i parametry pevného disku popsané v kapitole 5. Těmito parametry jsou především velikost vyrovnávací paměti, rychlost otáčení plotny a doba potřebná k vystavení čtecí a zapisovací hlavy. Jak jednotlivé souborové systémy předcházejí fragmentaci, lze jen těžko popsat obecně, avšak existují zde určité techniky, které buď přímo slouží k minimalizaci fragmentace, nebo je to jejich vedlejší efekt.

6.1

Variabilita velikosti uložených dat

Nejedná se ani tak o techniku, ale spíše o vlastnost ukládaných dat. Onou vlastností je, že fragmentace je do jisté míry úměrná variabilitě velikostí uložených souborů. Co to znamená, si ukážeme na třech případech, kdy budeme postupně uvažovat ukládání velkých a malých souborů, a poté jejich kombinaci. 1. Pokud souborový systém obsahuje pouze velké soubory, tak při jejich postupném ukládání je snaha o co největší souvislost. Pokud je soubor úmyslně fragmentován, tak fragmenty budou ukládány o své maximální velikosti, kterou definuje každý souborový systém zvlášť. Pouze poslední fragment souboru může mít rozdílnou velikost v závislosti na celkové velikosti souboru. V případě stárnutí souborového systému, jak bylo popsáno v podkapitole 4.2, se fragmentace projeví jen minimálně, jelikož kromě posledního fragmentu souboru, mají všechny stejnou velikost. 2. Podobně je to i s větším množstvím pouze malých souborů, ačkoliv oproti prvnímu případu, zde dochází k fragmentaci v daleko větší míře. V daleko větší míře dochází i k fragmentaci volného místa, ale jelikož ukládáme jen malé soubory, tak to nezpůsobuje takové komplikace, jako v následujícím případě.

23

24

KAPITOLA 6. PŘEDCHÁZENÍ FRAGMENTACE

3. Nejhorší, a také bohužel nejčastější varianta, je kombinace malých a velkých souborů. V momentě stárnutí souborového systému se začnou postupně malé soubory ukládat do volných míst, kde byly dříve fragmenty velkých souborů. Tím se postupně začne fragmentovat volné místo, což v tomto případě začne být komplikace pro velké soubory, které budou muset být rozděleny na více fragmentů o menší velikosti. Obecně tedy souborové systémy, resp. jejich alokační mechanizmy, nemají potíže s první variantou, a to i přes to, že souborový systém má malou rezervu volného místa. Důvodem je to, že fragmenty mají téměř konstantní velikost. Druhá varianta je poněkud komplikovanější v tom, že jsme si jasně nedefinovali velikost souborů. Předpokladem malých souborů můžeme tedy rozumět velikost menší, než velikost maximálního fragmentu. Ovšem, ne každý souborový systém musí soubory ukládat po fragmentech, či fragmentech tak malých, jako např. UFS. V tom případě musíme předpokládat velikost souboru mnohonásobně menší, než celkovou velikost souborového systému. Omezením velikosti jsme do jisté míry omezili i onu variabilitu velikostí souborů, avšak to nezabrání fragmentaci. Mnohem důležitější podmínkou je omezení samotné variability velikostí. Čím více si velikosti souborů budou podobné, tím více se bude tato varianta podobat první variantě. V posledním případě budou alokaci velkých souborů ztěžovat malé soubory. S touto situací si již alokační mechanizmy moc neporadí, jelikož jejich hlavním úkolem je výběr vhodného místa. Na řadu by tedy mohly přĳít přesuny malých souborů, resp. fragmentů, na vhodnější místo. To ovšem vede k redundantním zápisům, a proto se tato technika ve většině souborových systémů nepoužívá. Na řadu tedy přicházejí offline defragmentovací nástroje.

6.2

Rezerva volného místa

Minimální rezerva volného místa, či případně jen dostatek volného místa, obecně minimalizuje fragmentaci. Alokátor nemá problémy s výběrem nového vhodného místa. Jedinou překážkou v alokaci velkých souvislých fragmentů, může být větší počet malých souborů.

6.3

Před-alokování

Před-alokování, neboli preallocation je technika, která alokuje dopředu více bloků, než je skutečně potřeba. Důvodem je minimalizace volání metody starající se o alokaci bloků, a současně snaha mít více bloků pohromadě. Fragment tedy bude mít velikost minimálně takovou, jako je velikost před-alokovaného úseku. Například, budeme-li uvažovat souborový systém Ext3, který má bloky o velikosti 4 kB a nebude používat techniku před-alokování3 , tak pro zapsání 100 MB souboru se bude muset 25600 krát zavolat metoda starající se o alokaci bloků. V případě před-alokování by se musela volat jen 3200 krát a minimální velikost fragmentu by byla 32 kB4 . Nevýhoda z toho plynoucí je případná alokace nepotřebných bloků, které se opět musejí uvolnit. Proto 3 Skutečnost je taková, že souborový systém Ext3 má implementováno před-alokování, stejně jako jeho předchůdce Ext2. Nicméně kvůli nekompatibilitě s žurnálem jej nelze používat. 4 Přednastavená hodnota na před-alokování je 8 bloků.

6.4. ZPOŽĎOVÁNÍ ALOKACE

25

zde nutně musí existovat jisté omezení, aby se souborový systém nezahltil před-alokovanými bloky, které později nebudou potřebné. Tímto omezením, např. u Ext3, resp. Ext2 je, že každý inode může mít jen jedno před-alokované místo.

6.4

Zpožďování alokace

Zpožďování alokace, neboli delayed allocation [11] je technika, která se začala využívat v souborových systémech jako např. ZFS, XFS, Ext4. Bez použití této techniky se v momentě, kdy aplikace zavolá write(), ihned vyhledá a alokuje potřebné místo na disku, kam se budou data ukládat. K tomu dojde i přesto, že k zápisu nedochází bezprostředně, a data jsou po nějakou dobu ve vyrovnávací paměti. To je ovšem nevýhodné v případě, kdy dochází k soustavnému zapisování, a tím i zvětšování cílového souboru, jelikož za vybraným místem již nemusí byt dostatek prostoru a bude muset dojít k fragmentaci. Zpožďování alokace vybere vhodné místo pro data až v momentě, kdy jsou opravdu zapisována na disk.

6.5

Extents

Extents je další technika, jejímž úkolem není primárně zabránit fragmentaci, ale přesto je to jedna z jejích vlastností. Jak bylo vysvětleno v kapitole 3, tak ve většině případů jsou data na disku uložena po blocích, jejichž konkrétní velikost definuje souborový systém, a na každý tento blok je v inodu odkaz. Extents je v podstatě sloučení několika souvislých bloků, na který je v inodu pouze jeden odkaz. Jinými slovy se jedná o fragment, na který je v inodu jeden odkaz. Tato technika se většinou používá společně se zpožďováním alokace.

6.6

Souborový systém UFS

Souborový systém UFS neobsahuje žádné komplexní metody, které se přímo zabývají předcházením, či odstraňováním fragmentace. Nicméně UFS bylo navrhováno s ohledem na fragmentaci a obsahuje několik mechanismů, které zde sice nejsou primárně kvůli fragmentaci, ale přesto fragmentaci jistým způsobem pozitivně ovlivňují.

6.6.1

Rezerva volného místa

Jedná se o jedinou konkrétní zmínku, resp. parametr, který je určen pouze k minimalizaci fragmentace. Doporučená minimální hodnota je 10% volného místa. Důležité je, že rezerva je počítána z celého disku, a ne např. jen z konce disku, což by nám nĳak nepomohlo. Počítání rezervy z celého disku znamená, že na každé skupině cylindrů máme teoreticky také rezervu. V případě alokace nového úseku máme tedy šanci, že se úsek nebude dělit na více fragmentů v rámci skupiny. Pokud se ale jednou skupina cylindru zaplní, tak následující zápisy do této skupiny budou většinou znamenat fragmentaci, nehledě na celkovou rezervu volného místa. Proto je u UFS nejen velmi důležité mít rezervu volného místa, ale pokud možno tak tuto hranici 10% volného místa na disku nikdy nedosáhnout. Jakmile se jednou disk zcela zaplní, tak i

26

KAPITOLA 6. PŘEDCHÁZENÍ FRAGMENTACE

po následném uvolnění, např. z 30%, nebudeme mít přehled o fragmentaci volného místa na jednotlivých skupinách cylindrů. Pokud skutečně k fragmentaci volného místa dojde, tak v rámci UFS neexistuje opravný mechanismus, jak tuto fragmentaci odstranit.

6.6.2

Skupiny cylindrů

Samotný souborový systém UFS je navržen tak, že při formátování nového oddílu bude oddíl rozdělen do několika skupin cylindrů. To následně sice vede k nucené fragmentaci při vytváření větších souborů, ale snižuje to fragmentaci volného místa. Tím, že je soubor rozdělen do několika skupin cylindrů, se minimalizuje fragmentace v případě jeho smazání. Pokud bychom uvažovali, že by byl soubor souvislý, tak po jeho smazání by vzniklo volné místo, jakési okno o velikosti tohoto souboru. Následné vytváření souborů o velikosti menší, než volné místo v okně a průběžné mazaní, by mělo dříve či později za následek fragmentaci volného místa v tomto okně. Tím, že je ale soubor úmyslně rozdělen do několika skupin cylindrů, tak po jeho smazání zbyde oněch oken mnohem více a o menší velikosti. Sice stále může docházet k fragmentaci volného místa v jednotlivých oknech, ale celkový dopad bude méně znatelnější a je mnohem pravděpodobnější, že okno bude alokováno celé.

6.6.3

Fronta přístupů na disk

Jak bylo popsáno v kapitole 5, tak při požadavku na určitý soubor se nejprve musí vystavit čtecí a zapisovací hlava disku. K disku se obecně nepřistupuje s každým požadavkem, ale po určitých intervalech, kde jednotlivé požadavky na fragmenty, resp. bloky, jsou uloženy do fronty, a poté uspokojeny naráz. V případě velké fragmentace souboru, či požadavků na navzájem vzdálené bloky, by zde docházelo ke zbytečnému pohybu čtecí a zapisovací hlavy. Proto se k optimalizaci pohybu hlavy používá one-way scan algoritmus. Princip spočívá v tom, že se nejprve požadavky setřídí dle umístění bloků. Následně se rozdělí fronta na dvě části. Na bloky s vyšší adresou než je aktuální pozice hlavy disku, a na bloky s nižší adresou. Poté se již hlava disku postupně přesouvá, nejprve na bloky s vyšší adresou, a poté na ty, které měly adresu nižší než pozice hlavy. Implementace algoritmu není vždy zcela v rámci souborového systému UFS. V projektu FreeBSD tomu tak je, ale např. v OpenBSD je algoritmus implementován v části ovladače obsluhujícího pevný disk.

Kapitola 7

Analýza a návrh řešení Z kapitoly 3 zabývající se UFS, bychom nyní měli brát na zřetel alespoň to, že souborový systém je rozdělen do několika skupin cylindrů. Každá skupina obsahuje oblast Data block, která se skládá z bloků, a ty dále z fragmentů. Oblastí našeho zájmu bude Data block, který obsahuje data souborů. Všechny ostatní oblasti s výjimkou Inode block, jsou pro nás z hlediska defragmentace nezajímavé, jelikož mají pevně danou strukturu.

7.1

Defragmentace oblasti Inode block

V této podkapitole vysvětlím, proč se nedefragmentuje Inode block, přestože inody mohou být roztroušeny po celém souborovém systému, což z hlediska vystavování čtecí hlavy disku nemusí být vždy výhodné. V prvním případě by přesun inodu z jedné pozice do druhé znamenalo, že se pro daný soubor změní jeho inode číslo. To by ještě nemuselo znamenat vážný problém, ale se změnou inode čísla by se současně musel upravit inode adresář, ve kterém je tento soubor umístěn. Tento inode ve svých datových blocích obsahuje jména souborů v něm obsažených a toto jméno je svázáno právě s číslem inodu. Druhý důvod, a to daleko závažnější, vychází ze způsobu jakým se vybírá nepoužitý inode při vytváření nového souboru. Kritériem výběru je především, ve které skupině cylindrů se nachází inode adresáře, v kterém bude soubor umístěn. Dále jsou to shrnující informace v rámci každé skupiny cylindrů, která obsahuje počet použitých inodů uvnitř skupiny. V úvahu se bere i celkový počet již alokovaných datových bloků ve skupině. Pokud bychom tedy začali přesouvat jednotlivé inody, bylo by to spíše proti logice samotného UFS a jeho optimalizačním metodám. V úvahu může přicházet pouze přesun inodů z více zaplněné skupiny cylindrů, do méně zaplněné skupiny, kde zaplněnost se samozřejmě myslí v oblasti Inode block. Současně by se muselo pamatovat vždy na hierarchii podadresářů. Ovšem tyto přesuny by se spíše než fragmentací, zabývaly optimalizací vyváženosti mezi zaplněností v jednotlivých Inode blocích. Díky vyrovnávací paměti, v které se uchovávají naposledy použité inody, algoritmu pro výběr nového inodu a i snadnému přístupu k inodům, by jejich přesuny byly z pohledu optimalizace spíše sporadické.

27

28

KAPITOLA 7. ANALÝZA A NÁVRH ŘEŠENÍ

7.2

Defragmentace oblasti Data block

Oproti Inode block je Data block tou správnou oblastí, kterou defragmentovat. Je jasné, že po defragmentaci by ideální případ byl takový, že každý inode by měl datové bloky, na které odkazuje v jediné sekvenční posloupnosti a stejně by tomu bylo i s bloky neobsazenými. To samozřejmě z hlediska architektury UFS není vždy možné. Defragmentaci souborového systému lze rozdělit do několika vrstev dle toho, jak budeme vnímat datovou oblast. 1. Za datovou oblast budeme považovat Data blocky ze všech skupin cylindrů, tzn. jako jeden sekvenční úsek. 2. Datovou oblastí je jen Data block z konkrétní skupiny cylindrů. 3. Datovou oblastí je jeden, resp. více bloků souborového systému, a defragmentují se jen fragmenty uvnitř bloku. V prvním případě by taková defragmentace v podstatě znamenala odstranění skupin cylindrů, jelikož po jejím skončení by první skupiny byly zaplněné, kdežto poslední skupiny souborového systému by byly prázdné. To by ovšem bylo v rozporu s principem UFS, jelikož je zde snaha o to, aby všechny skupiny cylindrů byly zaplněny stejnoměrně. V úvahu tedy připadají jen poslední dvě možnosti. Defragmentovat datovou oblast jen v rámci konkretní skupiny cylindrů, resp. na úrovni fragmentů jednotlivých bloků, ale opět jen v rámci jedné skupiny cylindrů. To, proč stačí defragmentovat jen skupinu cylindrů, je dáno principem UFS.

7.3

Identifikace bloků

Než se vůbec s defragmentací začne, je třeba zjistit, v jakém stavu se Data block nachází. Pomocí bitové mapy můžeme zjistit které bloky, resp. fragmenty, jsou obsazené a které volné. U obsazených bloků, resp. fragmentů, musíme dále zjistit, ke kterému inodu patří. Důležité je uvědomit si, že tento krok je naprosto nezbytný, jelikož pokud chceme dále bloky přesouvat na jiné pozice, musíme vědět, ke kterému inodu náleží, abychom mohli změnit odkaz v inodu na novou pozici bloku. Problém tohoto hledání se skrývá v tom, že ze samotných bloků, resp. fragmentů, tuto informaci nezjistíme. Jediné řešení jak určit, zda blok k inodu patří je ta, že se prohledají všechny odkazy konkrétního inodu a nalezne se tam takový, který ukazuje na tento blok. Pokud tedy potřebujeme ke každému bloku v oblasti Data block zjistit, ke kterému inodu patří, musíme v nejhorším případě prohledat všechny inody, které se nacházejí v souborovém systému. Všechny inody se prohledávají z toho důvodu, že umístění datového bloku na konkrétní skupině cylindrů nám nic nevypovídá o tom, na které skupině cylindrů se nachází inode, který na tento blok odkazuje. Ačkoliv se na první pohled může zdát, že toto vyhledávání je časově velmi náročné, tak následující protichůdné úvahy ukáží, že tomu tak ve většině případů není. V obou úvahách předpokládáme nejčastější hodnoty souborového systému, tedy že skupina cylindrů obsahuje 12958 bloků a 25984 inodů.

7.3. IDENTIFIKACE BLOKŮ

7.3.1

29

Úvaha o velkém počtu malých souborů

Předpokládejme, že souborový systém obsahuje pouze velký počet malých souborů, takže počet využitých inodů se přiblížil k celkovému počtu všech inodů na skupině cylindrů. Z poměru bloků a inodů vyplývá, že mohou nastat tři situace: • Počet inodů je shodný s počtem bloků, tzn. každý inode ukazuje právě na jeden blok. • Počet inodů je vyčerpán, tj 25984 inodů je použito. Za předpokladu, že každý blok obsahuje 8 fragmentů připadají na každý inode necelé 4 fragmenty5 . • Kombinace obou předchozích případů. Důležité je si uvědomit, že v momentě, kdy je pro inode potřeba alokovat nový fragment a celkový počet fragmentů v inodu stoupne na 8, se tyto fragmenty automaticky překopírují do prázdného bloku tak, aby mohly tvořit jeden souvislý blok. Tím se i počet odkazů v inodu sníží ze 7 na jeden odkaz. Shrneme-li všechny tři situace, tak nám z nich vyplývá, že ať již bude počet inodů zcela vyčerpán, či se jejich počet bude pohybovat v rozmezí počtu bloků, tak všechny odkazy na bloky, resp. fragmenty, budou přímé. Budeme-li uvažovat tu horší variantu, že všechny inody jsou na skupině cylindrů použity, tak se nám nabízí dvě možnosti jak inody prohledat. 1. Celou oblast Inode block můžeme naráz načíst, resp. namapovat do paměti. Následný čas potřebný k přístupu k jednotlivým položkám inodu bude již zanedbatelný. Za předpokladu velikosti inodu 128 B a 25984 inodů bude třeba použít 3248 kB paměti. Samozřejmě v rámci optimalizace lze uvažovat i o načítání menších úseků. 2. Čtení jednotlivých bloků s inody. Předpokládáme-li, že se do bloku vejde celkem 128 inodů, tak bude třeba 203 přístupů na disk.

7.3.2

Úvaha o malém počtu velkých souborů

Opačná úvaha se zabývá malým počtem velkých souborů. Po vyčerpání 12ti přímých odkazů je inode nucen začít používat nepřímé odkazy. To pro nás mimo jiné znamená, že musíme načíst nový blok obsahující tyto odkazy. Jeden blok může pojmout 4096 odkazů, z čehož plyne, že tyto necelé 4 bloky mohou pokrýt celou oblast Data block. Pokud by se uvažoval pouze jeden inode, tzn. soubor zhruba o velikosti 202 MB, tak by bylo nutné provést celkem 6 čtení z disku. • Načíst inode. • Načíst blok z první nepřímé úrovně. • Načíst blok z druhé nepřímé úrovně. 5

Jedná se samozřejmě o zaokrouhlení (12958 * 8) / 25984. Nezapomínejme, že fragment je nejmenší adresovatelná oblast souborového systému.

30


• Načíst zbývající 3 bloky, jejichž adresu získáme z bloku ze 3 čtení. Tyto úvahy nám ukázaly dvě protichůdné situace, které mohou nastat při hledání odkazů na bloky v inodech. Z pohledu rychlosti vyhledávání a počtu přístupů na disk, by pro nás bylo výhodné, kdyby soubory patřily jen do jedné skupiny. Nicméně ve většině reálných souborových systémů jsou soubory jak malé, tak i velké, ale vždy když začne dominovat jedna skupina, tak je to na úkor druhé.

7.3.3

Nejhorší stav pro identifikaci bloků

Nejhorším stavem který může nastat je právě situace, kdy soubory svojí velikostí nepaří do skupiny malých a ani velkých souborů. To znamená stav, kdy je zde velký počet inodů ve skupině cylindrů, a současně každý z nich používá adresování pomocí nepřímé úrovně. Konkrétně jedna z nejhorších situací nastane, když každý inode ukazuje právě na 13 bloků, resp. 12 bloků a alespoň jeden fragment, ale pro jednoduchost výpočtu berme v úvahu 13 bloků. V takovém případě je prvních 12 bloků adresováno přímo a 13 blok nepřímo, k čemuž je nutné použít další blok pro adresaci. To ale znamená, že je nutné provést další přístup k disku. Celkem tedy tento inode zabere 14 bloků. Pokud je tedy na skupině cylindrů 12958 bloků, tak je možné, že zde bude cca 925 takovýchto inodů. To znamená, že nehledě na to jak se bude načítat oblast Inode block, tak zde bude dalších 925 přístupů na disk.

7.4

Seřazení bloků

V této fázi, která následuje po identifikaci bloků, již máme ke každému bloku informaci, zda je obsazený či ne. U obsazených bloků známe číslo inodu, který na ně ukazuje a i pořadí, v kterém na bloky ukazuje. Všechny tyto informace nám vytvářejí jakousi mapu oblasti Data block. Z této mapy můžeme nejen určit volné a zaplněné místa, ale i oblasti, kde jsou data souvislá či fragmentovaná. V této podkapitole se budeme zabývat tím, jak bloky vhodně uspořádat. Nicméně ve fázi řazení nebudeme bloky stále fyzicky přesouvat, budeme jen vypočítávat jejich budoucí pozici. Podobně jako jsme si vytvořili mapu oblasti Data block, která reprezentuje aktuální stav, tak si vytvoříme mapu, která nám bude reprezentovat oblast Data block po defragmentaci. Hlavním důvodem proč nepřesouvat bloky již v této fázi, bylo oddělit algoritmus řazení od samotných přesunů. Ideálním řešením by bylo, kdybychom měli funkci, které předáme aktuální mapu Data blocku, a ta by nám vrátila novou mapu, která by reprezentovala oblast po defragmentaci. Takový postup nám samozřejmě v budoucnu dovolí snadnou modifikaci algoritmu. Pokud bychom se zabývali řazením libovolných objektů v operační paměti, tak by postup byl vcelku zřejmý. Problém ovšem nastává s tím, že naše objekty jsou uloženy na pevném disku. To jest na médiu řádově pomalejším, odkud je vždy musíme načíst a poté na jinou pozici uložit. Proto nás kromě výsledného uspořádání bude zajímat i to, kolik přesunů bude třeba provést. V úvahu přicházejí tři způsoby jak bloky uspořádat. 1. Všechny bloky konkrétního inodu budou na skupině cylindrů uloženy souvisle.

7.4. SEŘAZENÍ BLOKŮ

31

2. Bude brán zřetel na souvislost, ale současně i na počet nutných přesunů nutných k dosažení souvislosti. 3. Přesuny fragmentů k dosažení maximálního počtu neobsazených bloků. V následujících podkapitolách si jednotlivé varianty probereme. Některé z nich je možné kombinovat, jako např 1 a 3 některé se zas navzájem vylučují. Ve fázi řazení nicméně nebudeme bloky stále fyzicky přesouvat, budeme jen vypočítávat jejich budoucí pozici.

7.4.1

Optimalizace na souvislost

Při této optimalizaci se snažíme dosáhnout toho, aby inode měl bloky na skupině cylindrů v co největších souvislých úsecích. Optimální stav je takový, když je zde jen jedna souvislá posloupnost bloků pro každý inode. Pokud jsou tyto posloupnosti umístěny za sebou, tak se současně zabraňuje fragmentaci volného místa. Vytvářejí-li se posloupnosti postupně od začátku datové oblasti, pak na konci datové oblasti vzniká souvislý úsek nepoužitých bloků. Tato optimalizace se snaží odstranit fragmentaci v největší míře a výsledný stav by měl být velice podobný stavu těsně po instalaci operačního systému, resp. po nakopírování dat na nově naformátovaný souborový systém. Nevýhodou je nutnost přesunutí velkého počtu bloků, který se často blíží počtu celkových bloků na skupině cylindrů.

7.4.2

Optimalizace na počet přesunů

Za ideální řešení by se mohl považovat jeden, či více větších souvislých úseků pro jeden inode, k čemuž by se došlo z minimálního počtu přesunutých bloků. Problémem je, že pokud je souborový systém fragmentovaný a z větší části zaplněn, tak se musí volit kompromis mezi: • Počtem přesunů. • Souvislostí bloků. • Fragmentací volného místa. Dalším problémem je to, jak určit, jestli je souvislý úsek již dostatečně velký. To znamená, nalezení takového úseku bloků, kdy po rozšíření o následující bloky již rychlost čtení nebude ovlivněna. Taková hodnota by se musela určit experimentálně u každého systému zvlášť, jelikož její hodnoty by se jistě lišily dle použitého hardwaru. Uvažujme zjednodušenou situaci, kdy jsme vytvořili současně tři soubory. Soubory byly nezávisle na sobě zvětšovány o rozdílný počet bloků. Poté byl jeden ze souborů smazán. Obrázek 7.1. zobrazuje teoretický stav, ve kterém by se souborový systém mohl nacházet. Defragmentace, která by se snažila o vytvoření co největších souvislých úseků společně s minimem přesunů, by musela volit mezi jedním z kompromisů:

32


Obrázek 7.1: Pohled na souborový systém po smazání jednoho ze souborů.

• Pokud S1 = A2 je možné přesunout A2 na pozici S1 . Současně ale rozhodni, zda je BK dostatečně velký úsek. Pokud ne, pak rozhodni, jestli není výhodnější přesunout blok BK−1 na pozici S1 , za předpokladu že BK−1 = S1 . Pokud je BK−1 < S1 , ale současně je i BK−1 << A2, stále může být přesun výhodnější i za cenu potenciálního vzniku fragmentace volného místa. • Pokud S1 < A2 je možné přesunout A1 a A2 do SF . Cenou bude počet přesunů rovnající se velikosti obou úseků. Druhou možností je rozdělit A2 na A2a a A2b . A2a o velikosti S1 by se přesunula do S1 a zbývající část A2b by se musela sloučit s A3 , samozřejmě pokud by sama A2b nebyla dostatečně velký úsek. • Pokud S1 > A2 , pak lze A2 přesunout do S1 , ale rozdíl S1 − A2 bude volné místo F. Pokud F nebude tvořit dostatečně velký úsek a BK se nebude přesouvat, pak bude obtížné F odstranit. Podaří se to jen v případě, že nalezneme soubor o velikosti F nebo minimalizovat F, pokud nalezneme dostatečný počet souborů, které budou přesunuty do F. Budeme muset volit mezi zbytečnými přesuny malých souborů, nebo fragmentací volného místa.

7.4.3

Optimalizace na fragmenty

Optimalizovat přesuny na fragmenty lze prakticky z jediného důvodu, a to z důvodu uvolnění bloku. Jelikož víme, že jeden inode může mít nanejvýš 7 fragmentů, které musejí být umístěny v jednom bloku, tak je zbytečné řešit souvislost fragmentů. Nicméně v jednom případě je užitečné přesouvat fragmenty, a to z důvodu uvolnění bloku. Může se stát, že souborový systém bude obsahovat mnoho malých souborů, např. o velikosti 2 fragmentů a zbytek bloku bude nevyužit. To povede nejen k velké fragmentaci volného místa, ale i k problémům při následné alokaci celých bloků. Tuto optimalizaci je možné zkombinovat s předešlými dvěmi. Stále ale platí, že se zvolený cílový blok snažíme fragmenty zaplnit a zdrojový blok uvolnit. Naopak následné přesuny takového bloku mohou být velmi nevýhodné, a to co se přístupu na disk týče. Uvědomíme-li si, že v bloku může být až 8 fragmentů z 8 inodů, tak přesun takového bloku by znamenal až potenciálních 18 přístupů na disk.

7.5

Využití paměti

Ačkoliv ještě nemáme jasně definované datové struktury programu, již bychom se měli zamyslet nad tím, kolik operační paměti bude naše implementace vyžadovat. V předchozích podkapitolách jsme si definovali jakousi mapu datové oblasti, která bude obsahovat potřebné informace o blocích. V tomto okamžiku ještě nemůžeme říct, kolik informací o jednom bloku budeme uchovávat a ani kolik místa zaberou. Můžeme ale dle velikosti

7.6. PŘESUNY BLOKŮ

33

skupiny cylindrů odhadnout, že velikost mapy bude nanejvýš 12958. Tato hodnota se poté vynásobí velikostí datových typů, které budou uchovávat informace o jednotlivých blocích a výsledek bude velikost potřebné paměti v bajtech. Dále budeme potřebovat načítat jednotlivé inody. Ty lze načíst minimálně po fragmentech, ale rozhodně bude výhodnější je číst po celých blocích, tj. o velikosti 16 kB. Jelikož úpravy v inodech budeme provádět velmi často, lze i uvažovat o načtení celého Inode blocku. Pokud uvažujeme 25984 inodů, kde každý má velikost 128 B, tak budeme potřebovat okolo 3.17 MB. To stále nemusí být dostatečné, jelikož Data block může obsahovat i bloky inodů, které nejsou ve stejné skupině cylindrů. Při přesunech bloků budeme potřebovat v paměti prostor minimálně pro dva bloky. Jelikož ale budou přesuny hlavní náplní programu, můžeme i uvažovat o načtení celé skupiny cylindrů do paměti. Pro celou skupinu cylindrů bychom potřebovali okolo 202 MB. Můžeme polemizovat, jestli je to v dnešní době mnoho či ne, nicméně neoddiskutovatelnou výhodou by bylo, že čtení by prakticky proběhlo v nejrychlejší možné míře. Nehledě na algoritmus pro přesuny bloků, musí se pamatovat na to, že pro přesun jednoho bloku musíme načíst jak samotný blok, tak i inode. V případě nepřímé adresace i bloky s adresami.

7.6

Přesuny bloků

V této podkapitole si popíšeme možnosti při přesunech bloků a rizika jsou s tím spojená. Efektivitu můžeme z velké části ovlivnit buď zvětšením rizika ztráty souboru, nebo zvětšením paměťových nároků. V momentě, kdy začneme s přesunem bloků, tak v podstatě začneme narušovat integritu souborů. V případě nečekaného ukončení programu mohou nastat tři varianty, v kterých se souborový systém bude nacházet. Ty jsou především závislé na stupni optimalizace zápisu.

7.6.1

Bez možnosti ztráty dat

Chceme-li se vyvarovat ztráty dat za všech okolností, tak musíme přesouvat bloky následujícím způsobem. V příkladě se uvažuje prohození dvou bloků b1 a b2 , dvou rozdílných inodů i1 a i2 , které jsou adresované přímo. V případě nepřímé adresace by se navíc musel uvažovat blok s adresou. 1. Načtení inodů a bloků. Celkem se jedná o 4 přístupy na disk. V případě, že jsou inody v jednom bloku, tak jen 3 přístupy. 2. Nyní se nahraje např. b1 do libovolného nevyužitého bloku. 3. Upraví se inode i1 a uloží se. 4. Nakopíruje se b2 na starou pozici b1 . 5. Upraví se inode i2 a uloží se. 6. Nakopíruje se b1 na starou pozici b2 . 7. Upraví se inode i1 a uloží se.

34


Celkem se tedy musí po prvních 4 čtení a 6 zápisech, provést 10 přístupů na disk. Výhodou této metody je ovšem to, že program může být ukončen v kterýkoliv okamžik, a to bez rizika ztráty dat.

7.6.2

Možnost ztráty jednoho souboru

Podstoupíme-li riziko ztráty jednoho souboru, tak můžeme uvažovat i zde příklad z předchozí podkapitoly. Rozdíl bude jen v tom, že v 2 a 3 kroku nebudeme blok a inode ukládat do dočasné pozice, ale ponecháme je jen v operační paměti a uložíme je v kroku 6 a 7. Pokud ovšem po kroku 4 nastane nečekané ukončení programu, bude soubor s inodem i1 ztracen. Toto riziko potrvá až do dokončení kroku 7.

7.6.3

Možnost ztráty celé skupiny cylindrů

V tomto případě uvažujeme, že jsme načetli celou skupinu cylindrů do paměti. Pokud bychom přesuny prováděli jen v rámci operační paměti, celý proces by se značně urychlil, a to díky jednomu čtení a po seřazení jednoho zápisu. Jen jedno čtení a zápis je za předpokladu, že není nutné přistupovat na jinou skupinu cylindrů kvůli inodům nebo nepřímých blokům. Pokud bychom přistupovali na jinou skupinu cylindrů, tak po první změně na této skupině by v případě náhlého ukončení programu došlo k poškození všech souborů, které byly na této skupině upravovány. Jestliže bychom nepotřebovali jiná data, než která jsou jsou již v paměti, tak by poškození souborů mohlo nastat jen v momentě, kdyby se skupina cylindrů kopírovala z operační paměti zpět na disk. V tomto případě by ovšem mohlo být ztraceno mnohem více dat.

7.7

Algoritmy pro přesun bloků

V této podkapitole budou popsány tři algoritmy pro přesouvání bloků. Jejich společnou charakteristikou je, že bloky, resp. veškerá potřebná data, se v jednom průchodu algoritmem, načtou z disku jen jednou. Počet přístupů na disk z důvodu ukládání je závislý na riziku, které jsme ochotni podstoupit v případě neplánovaného ukončení programu, viz podkapitola o přesunech bloků 7.6. V algoritmech budeme uvažovat, z pohledu přístupů na disk, tu nejnáročnější variantu, tedy bez možnosti ztráty dat. Abychom takto mohli bloky přesouvat, musíme mít kdekoliv na disku jeden blok neobsazený. Počet přístupů na disk, z důvodu načtení bloků, je závislý na způsobu jeho adresace. Pro názornost budeme v algoritmech předpokládat přímou adresaci. V případě nepřímé adresace by se musely načítat i bloky s adresami. Zápis by se ale nezměnil, jelikož místo upravených inodů, by se ukládaly upravené bloky s adresami. V nejhorším případě se tedy počet přístupů na disk zvetší o tři čtení na jeden požadovaný blok.

7.7.1

Naivní algoritmus

Jedná se o jednoduchý algoritmus, který prochází postupně inody ve skupině cylindrů a jejich odkazy na bloky, viz Obrázek 7.2. Pokud se bloky nacházejí na aktuální skupině cylindru, tak se budou přesouvat.

7.7. ALGORITMY PRO PŘESUN BLOKŮ

35

Algoritmus: 1. Nastav ukazovátko na začátek oblasti Data block. 2. Pro všechny obsazené inody ve skupině cylindrů. 3. Načti inode. 4. V inodu pro všechny odkazy na bloky jenž se nacházejí ve skupině cylindrů. • Pokud žádný blok není, pokračuj v bodě 3. 5. Načti blok na který ukazuje. 6. Načti blok na který ukazuje ukazovátko. 7. Proveď výměnu. 8. Zvětši ukazovátko a pokračuj v bodě 4.

Pokud je pozice, na kterou ukazuje ukazovátko prázdná, tak se prázdný blok nekopíruje, jen se přenastaví bitmapa. Výhody: + Není třeba fáze řazení popsané v 7.4. + Aktuální inode a nepřímé bloky se načtou jen jednou a pak se zpracovávají. Nevýhody: - Bloky inodů mimo skupinu cylindrů nejsou seřazeny. - Při výměně bloků je většinou jeden z nich umístěn na pozici, z které bude dále přesouván.

7.7.2

Algoritmus úplného seřazení

Pro tento algoritmus je již nezbytné znát cílové pozice pro všechny bloky na skupině cylindru. Toho se docílí řazením, viz. podkapitola 7.4. Postupně se pak procházejí všechny seřazené bloky a dle informací o jejich cílové pozici se přesouvají. Pokud je cílová pozice prázdná, tak se prázdný blok nekopíruje, jen se přenastaví bitmapa. Výhody: + Seřadí všechny bloky na skupině cylindrů bez ohledu na to, kde se nachází inode. Nevýhody: - Při výměně bloků je většinou jeden z nich umístěn na pozici, z které bude dále přesouván. - Nepřesunou se všechny bloky inodu na jedno načtení inodu, případně bloku s nepřímými adresami.

36


Obrázek 7.2: Průběh zpracování u naivního algoritmu. Algoritmus: 1. Pro všechny obsazené datové bloky v mapě. 2. Načti informace o bloku. 3. Zjisti jestli je blok již na cílové pozici. • Pokud ano, přejdi na následující blok. • Pokud ne, načti informace o bloku, který je na cílové pozici. 4. Načti oba bloky a proveď výměnu. 5. Pokračuj v bodě 2.

7.7.3

Algoritmus bez zbytečných přesunů

Nevýhodou předchozích algoritmů byly jejich zbytečné přesuny. Ve většině případů se na požadovanou pozici dostal jen jeden ze dvou bloků. Druhý blok se přesouval na svou cílovou pozici až tehdy, když na něj přišla řada. To nejen znamená, že se musí do operační paměti načíst inode a poté blok, který již v paměti jednou byl, ale musí se i znovu přesouvat a poté zapsat. Bylo by tedy vhodné nalézt takový způsob přesunu, aby se blok, který se jednou načte, uložil vždy na svou cílovou pozici. Problém tohoto požadavku je, že obecně dva bloky nelze navzájem přesunout s tím, aby oba byly na cílové pozici. Řešením se z části ukázalo zahrnutí třetího bloku do přesunů. Algoritmus si popíšeme na konkrétním příkladě tří bloků A, B, C, přesunovaných ve dvou fázích, viz. Obrázek 7.3. V první fázi se přesune B na svou cílovou pozici a v druhé fázi se přesune A na svou cílovou pozici. Při přesunech budou cílové pozice bloků obsazeny.

7.7. ALGORITMY PRO PŘESUN BLOKŮ

Operace Načtení A,B,C Ulož dočasně A Ulož B Ulož dočasně C Ulož A

37

Čtení 6

Zápis 2 2 2 2

Tabulka 7.1: Počet přístupů na disk. Vstupem algoritmu je blok, který se nenachází na cílové pozici, a současně je třeba znát cílové pozice bloků. Po ukončení algoritmu je vždy jeden či více bloku na cílové pozici. Počet bloků, které se přesunou není předem znám, záleží vždy na jejich cílových pozicích. Algoritmus: 1. Vstupem je blok B. 2. Načteme informace o bloku a přejdeme k jeho cílové pozici. 3. Na této pozici se nachází blok A, načteme jeho informace. • V případě, že je pozice prázdná, přesune se blok B a skončíme. 4. Blok A má svou cílovou pozici obsazenou C, přesouvá se tedy do neobsazené pozice. • Pokud by A měl cílovou pozici volnou, přesunul by se a vrátili bychom se k přesunu bloků B a algoritmus by skončil. 5. Cílová pozice B je nyní volná a blok se přesouvá. Práce s blokem B končí. 6. Blok C se přesouvá do nové volné pozice po B. • Pokud by cílová pozice C byla prázdná, blok by se na ni přesunul a práce s blokem C by se ukončila. 7. Blok A se může přesunout do své cílové pozice. 8. Nyní jsou minimálně blok A a B na cílových pozicích. Za předpokladu, že C není na cílové pozici, přecházíme do bodu 2 s blokem C, ale již nemusíme z disku nic načítat. Výhoda, která nemusí být na první pohled zřejmá je, že čtení inodů a bloků A, B, C proběhne jen jednou. Při opakovaných přesunech z dočasného umístění již nemusíme bloky ani inody znovu načítat. Celkový počet přístupů na disk při prvním průchodem algoritmu je v tabulce 7.1 Celkový počet přístupů na disk je tedy 14. V porovnání s předchozími algoritmy, které měly jen 10 přístupů na disk na jeden průchod algoritmem, jsme si znatelně pohoršili. Nicméně při všech dalších průchodech již nebudeme muset znovu načítat C, jen A a B, tudíž počet přístupů nám klesne na 12. Hlavním rozdílem ale je, že po jednom průchodu

38


Obrázek 7.3: Průběh zpracování u algoritmu bez zbytečných přesunů.

algoritmem budou 2 bloky na cílové pozici, kdežto v předchozích algoritmech to ve většině případů byl jen jeden blok. Pokud zanedbáme první načtení C, které se již dále nebude provádět, tak se počet přístupů na disk zefektivní až o 40%. Výhody: + Dva bloky se vždy přesunou na cílovou pozici. + Možnost přesunutí až tří bloků na cílovou pozici. Nevýhody: - Nepřesunou se všechny bloky inodu na jedno načtení inodu, případně bloku s nepřímými adresami.

Kapitola 8

Implementace V této kapitole si popíšeme vlastní implementaci programu na odstranění defragmentace, pro který jsem zvolil název udef, což je odvození z UFS defragmentation. Na obrázku 8.1 je znázorněn zjednodušený úspěšný průchod programem. Pro implementaci byl zvolen programovací jazyk C a program byl rozdělen do sedmi souborů.

Obrázek 8.1: Průchod programem.

39

40

KAPITOLA 8. IMPLEMENTACE

udef.c Obsahuje funkci main() a hlavní náplní je zpracování parametrů a poté volání jednotlivých funkcí v závislosti na vstupních parametrech. io.c Zajišťuje ukládání a načítání bloků a inodů buď z paměti nebo z pevného disku. Přepočítává relativní adresu bloku na absolutní adresu. Jedná se v podstatě o nejnižší vrstvu programu obsahující systémové funkce jako pread() a pwrite(). cgmmap.c Stará se o namapování skupiny cylindrů do paměti pomocí funkce mmap(). V případě namapování skupiny cylindrů se stará o ukládání a načítání bloků. udefcg.h Alokuje potřebnou paměť pro pole reprezentující skupinu cylindrů. Identifikuje jednotlivé bloky a určí jejich cílovou pozici. udef_stat.c Výpis souhrnných informací o skupině cylindrů a o blocích nacházejících se na ní. sortcg.c Zajišťuje přesouvání bloků. To mimo jiné znamená veškerou přípravu s tím spojenou, jako příprava zdrojové a cílové pozice a dále zpřístupnění bloků s adresami a nastavení bitmapy. Obsahuje metodu Triple sort pro přesouvání bloků. hop_sort.c Obsahuje jedinou funkci starající se o přesun bloků pomocí metody Hop sort.

8.1

Vstupní parametry a inicializace

Program definuje 8 přepínačů, které mohou být uživatelem nastaveny. Jeden z nich vyžaduje argument, a to číslo skupiny cylindrů. Syntaxe příkazu je následující: udef [-pbsmrih -c ncyl] device Vstupní parametry: -c Definuje číslo skupiny cylindrů a požaduje tedy argument. Výchozí hodnota bez použití parametru je 0. -p Vypiš informace o blocích na skupině cylindrů a jejich cílové pozice po provedení defragmentace. -b Vypiš bitmapu bloků na skupině cylindrů. -s Vypiš pořadí, v jakém budou bloky přesouvány. -m Namapuj skupinu cylindrů do paměti. -r Spusť defragmentaci. -i Jako metodu pro přesun bloků použĳ Hop sort. -h Vypiš nápovědu.

8.2. NAMAPOVÁNÍ SKUPINY CYLINDRŮ DO PAMĚTI Parametr GLBCGISMMAP GLBRUNINSEC

41

Popis Využívá se mapování do paměti. Použĳe se metoda Hop sort pro přesun bloků.

Tabulka 8.1: Hodnoty kterých může nabývat proměnná flags ve struktuře GLBVAL. Po zpracování vstupních parametrů se zavolá funkce open_disk(), pomocí které se otevře zařízení. Současně se přečte Super-block a uloží do jediné globální proměnné afs. Následně se načte hlavička skupiny cylindrů a inicializuje se proměnná glb. Proměnná glb je typu GLBVAL, což je struktura obsahující klíčové informace, které se využívají v jednotlivých částech programu. typedef struct { int fd; void **blockap; void **slink; int slink_size; void memcg; struct cg *acg; uint32_t flags; } GLBVAL; Položky struktury GLBVAL jsou: fd File descriptor pro otevřené zařízení. blockap Pole ukazatelů reprezentuje mapu bloků na aktuální skupině cylindrů. slink Pole které ukazuje na stejné položky jako blockap, ale ukazatelé jsou v pořadí, v jakém se budou postupně zpracovávat. slink_size Velikost pole slink, tzn. počet bloků, které se budou přesouvat. memcg V případě, že se mapovala celá oblast skupiny cylindrů do paměti, tak obsahuje ukazatel na začátek této paměti. flags Obsahuje bitové hodnoty některých parametrů, popsaných v tabulce 8.1.

8.2

Namapování skupiny cylindrů do paměti

Pokud bylo parametrem vynuceno mapovaní skupiny cylindrů do paměti, tak se tak učiní ve funkci cgmmap(). Samotné mapování se provede pomocí systémové funkce mmap(), která mimo jiné má jako parametr velikost mapované oblasti. Velikost se musí získat z hlavičky

42


konkrétní skupiny cylindrů, která se načte funkcí read_cgblock_ft(). Součástí namapování je i volání funkce pre_read(), která vynutí načtení všech bloků z disku do paměti. Pro přístup k blokům se v případě namapování skupiny cylindrů používají funkce cgm_read_fs_block() a cgm_write_fs_block(). Zápis bloků, tj. překopírování z paměti, je uskutečněn pomocí funkce memcpy(). Skutečný zápis z namapované oblasti na disk je z důvodu optimalizace přenechán na operačním systému, proto tedy nelze zcela přesně určit, kdy se změněný blok skutečně zapíše.

8.2.1

Paměťové nároky

Paměťové požadavky na namapování celé skupiny cylindrů závisí pouze na velikosti a počtu bloků. Uvažujeme-li tedy výchozích hodnoty, pak skupina cylindrů obsahuje 12958 bloků, kde každý blok má velikost 16 kB. K namapování skupiny cylindrů bude tedy zapotřebí 203 MB operační paměti.

8.3

Identifikace bloků

Identifikace bloků, tak jak byla popsána v podkapitole 7.3, se spustí funkcí udefcg(). Ta obsahuje volání několika dalších funkcí spojených s identifikací bloků. Jedna z prvních funkcí, která se musí zavolat, je alokace pole ukazatelů reprezentující mapu skupiny cylindrů, tedy blockap. Ta se provede ve funkci allock_blockap(). Následuje alokace pole ukazatelů slink, která ukazuje na stejné položky jako blockap, ale již v pořadí, v jakém se budou postupně přesouvat. Hlavními funkcemi, které slouží k identifikaci bloků, jsou fill_array(), fill_array_inode() a fill_array_dbib(). Funkce fill_array() se skládá ze dvou vnořených cyklů, kde vnější cyklus prochází všechny skupiny cylindrů na disku a vnitřní postupně načítá všechny inody na skupině cylindrů. Načtený inode, resp. dinode, se předá funkci fill_array_inode(). Ta má za úkol předat pole s přímými adresami bloků funkci fill_array_dbib(). V případě přímé adresace se předá jen pole di_db, které je součástí každého dinodu a obsahuje prvních 12, resp. NDADDR odkazů. První stupeň indirekce předává blok přímých odkazů, který se načte z adresy obsažené v di_ib[0] a obsahuje NINDIRS odkazů. Druhý a třetí stupeň indirekce funguje na podobném principu, kdy se přes di_ib[1], resp. di_ib[2], postupně načítají bloky s nepřímými odkazy až do okamžiku, kdy se načte blok s přímými odkazy, který se předá funkci fill_array_dbib(). Ve funkci fill_array_dbid() se postupně projdou všechny odkazy z předaného bloku a provede se kontrola, zda-li tyto odkazy ukazují do aktuální skupiny cylindrů. Pokud ano, tak se vytvoří nová proměnná typu BLOCKARRS a vloží se do pole blockap na pozici, která koresponduje s umístěním bloku na aktuální skupině cylindrů. Současně se přidá odkaz na položku do pole slink. Vazba mezi polem slink a blockap je zobrazena na obrázku 8.2. Pole slink v podstatě reprezentuje frontu a dle toho se i plní. Důvodem, proč bylo pro reprezentaci fronty zvoleno pole a ne např. spojový seznam, je menší náročnost na paměť. V případě spojového seznamu bychom museli použít ukazatel na následující prvek, čímž by se velikost z původního jednoho ukazatele zdvojnásobila. Pokud by následně skupina

8.3. IDENTIFIKACE BLOKŮ

43

cylindrů byla zaplněna více jak z poloviny, což se u fragmentace v celku předpokládá, tak by potom spojový seznam zabíral více paměti než pole ukazatelů.

Obrázek 8.2: Vazba mezi polem blockap a slink.

typedef struct blockarrs { ino_t ino; uint32_t apindx; uint32_t blkindx; uint32_t blkdest; uint32_t flags; FRAGARRS *frag; } BLOCKARRS; Položky struktury BLOCKARRS jsou: ino Číslo inodu. apindx Index, resp. relativní adresa bloku od začátku skupiny cylindrů. blkindx Index datového bloku. Jedná se o absolutní hodnotu, tedy 0 až N, kde N je celkový počet bloků patřící inodu. blkdest Index, resp. relativní adresa cílové pozice. Ta se určí až během řazení bloků. flags Obsahuje bitové hodnoty některých parametrů, popsaných v tabulce 8.2. frag Odkaz na spojový seznam obsahující jednotlivé fragmenty. V případě, že je blok rozdělen do více fragmentů na které ukazují rozdílné inody, tak se pro jednotlivé další fragmenty využĳe spojový seznam, kde každá položka je datový typ FRAGARRS.

44

KAPITOLA 8. IMPLEMENTACE Parametr BLCKFREE BLCKNOMOVE BLCKLAST BLCKALONE

Popis Neobsazený blok. Nepřesunutelný blok. Poslední blok inodu. Blok byl alokován celý, tzn. není fragmentován.

Tabulka 8.2: Hodnoty kterých může nabývat proměnná flags ve struktuře BLOCKARRS. typedef struct fragarrs { ino_t ino; int8_t fragoff; struct fragarrs *frag; } FRAGARRS;

Položky struktury FRAGARRS jsou: ino Číslo inodu. fragoff Umístění fragmentu v bloku. frag Odkaz na další položku spojového seznamu. Poslední volaná funkce zabývající se identifikací bloků je fill_array_restblocks(). Ta pro každý ukazatel z blockap, který je NULL, zkontroluje příslušné bity v bitmapě bloků. Pokud je blok dle bitmapy neobsazený, tak se ponechá v blockap hodnota NULL. Pokud je dle bitmapy obsazený, tak se alokuje nová položka a vloží se do blockap. Současně se její proměnná flags nastaví na hodnotu BLCKNOMOVE a z bloku se stane nepřesunutelný blok.

8.3.1

Paměťové nároky

Když již známe všechny struktury a datové typy, které budou použity k identifikaci bloků na skupině cylindrů, tak můžeme vypočítat potřebné paměťové nároky, a to pomocí vzorce 8.1. blockap_mem = (blks ∗ ps) + (blks − hs) ∗ ss

(8.1)

Vysvětlivky: blks Počet bloků na skupině cylindrů, resp. velikost pole blockap. blkh Počet bloků které zabírá hlavička skupiny cylindrů. ps Velikost ukazatele v bytech na konkrétní architektuře. ss Velikost jedné položky pole blockap v bytech. Pokud budeme uvažovat 64 bitovou architekturu, kde je velikost ukazatele do paměti 8 bytů a současně bloky nejsou dále dělené na fragmenty, tak budeme potřebovat 449 KB operační paměti.

8.4. SEŘAZENÍ BLOKŮ

8.4

45

Seřazení bloků

Seřazení bloků v našem kontextu znamená určení cílové pozice pro každý přesunutelný blok. Seřazení se provádí ve funkci valid_blocks_order() a její hlavní náplní je přiřadit každému bloku, resp. položce, v poli blockap cílovou pozici. Pozice se ukládá do proměnné blkdest. Princip určení cílové pozice je vysvětlen pomocí obrázku 8.3. Nejprve se zvolí dvě ukazovátka do polí. Do pole slink ukazovátko spos a do pole blockap ukazovátko apindx. Ukazovátko spos ukazuje na první prvek pole slink a apindx na pozici v blockap, která reprezentuje počátek datové oblasti. Poté se v cyklu postupně inkrementuje spos, a tím se prochází pole slink. V cyklu se pro každou přesunutelnou položku z pole slink na pozici spos zkontroluje, zda-li je položka z pole blockap na pozici apindx také přesunutelná nebo neobsazená. Pokud tomu tak je, tak se z pozice na kterou ukazuje apindx, stane cílová pozice pro blok, resp. položku, na kterou ukazuje spos. Pokud tomu tak není, tak se inkrementuje apindx a spos zůstane pro následující iteraci nezměněn.

Obrázek 8.3: Určení cílové pozice bloku.

8.5

Výpis informací

Součástí programu je i stručný výpis vybraných informací. Lze vypsat některé parametry z hlavičky na konkrétní skupině cylindrů pomocí funkce print_cgblock(). Informace o inodech a informace o umístění datových bloků se vypisují pomocí funkcí print_inodes() a print_inodes_ib(). Dále je zde výpis pole blockap funkcí print_blockap(), který zobrazí aktuální pozici bloku, cílovou pozici, číslo inodu a index bloku. Funkce print_slink() vypíše pole slink a přepínačem lze také vynutit vypsání bitmapy bloků, které se provádí ve funkci print_bmap().

46


8.6

Přístup k datům

Funkce pro přístup k datům lze rozdělit na tři skupiny, kde každá skupina obsahuje vždy čtecí a zapisovací funkci. 1. Přístup k hlavičce skupiny cylindrů. Funkcemi jsou reat_cgblock(), read_cgblock_ft() a write_cgblock(). 2. Přístup k inodům. Funkcemi jsou read_inodes_block() a write_inodes_block(). 3. Přístup k blokům. Funkcemi jsou read_fs_block() a write_fs_block(). Jelikož jsou data uložená po blocích a po blocích se jak načítají, tak i ukládají, tak na nejnižší úrovni jsou vždy volány funkce pro přístup k blokům. První dvě skupiny tedy slouží jen jako mezistupeň, jak je vidět na obrázku 8.4. Funkce vyšší vrstvy z předaných parametrů vypočítají konkrétní adresu bloku a ten je dále dle potřeby načten či uložen pomocí funkcí přistupujících k blokům. V následujících dvou podkapitolách si popíšeme postup, jak se přistupuje k blokům, ať už s namapovanou či nenamapovanou skupinou cylindrů.

Obrázek 8.4: Model funkcí pro přístup k datům.

8.6.1

Přímý přístup k blokům

V případě, že nemáme namapovanou skupinu cylindrů do paměti, tak je situace poměrně snadná. Uvažujeme-li např. čtení bloku, tak se zavolá funkce read_fs_block() a jako parametry jsou jí předány číslo boku a úložiště, kam se blok načte. Číslo bloku se poté převede na konkrétní adresu a pomocí systémové funkce pread() se načte požadovaný blok.

8.6.2

Přístup k blokům s namapovanou skupinou cylindrů

V případě, že je skupina cylindrů namapovaná do paměti, tak se situace nepatrně změní. Budeme-li opět uvažovat čtení bloku, tak se nejprve zavolá funkce read_fs_block(). Ta pomocí funkce is_blockinmem() rozhodne, zda se požadovaný blok nachází v namapované oblasti či ne. To je nutné z toho důvodu, že ačkoliv je skupina cylindrů namapovaná do

8.7. PŘESUN BLOKŮ

47

paměti, tak zde stále mohou být požadavky na bloky, které se nacházejí na jiné skupině, tedy nenamapované. Jedná se o bloky s inody či bloky s nepřímými adresami. Pokud se blok nenachází v namapované oblasti, tak se pokračuje obdobně, jak bylo popsáno v 8.6.1. V případě, že se nachází v namapované oblasti, tak se zavolá funkce cgm_read_fs_block() a předají se jí stejné parametry, jako funkci read_fs_block(). Jedním z parametrů je úložiště, kam se blok načítá. Oním úložištěm je konkrétněji ukazatel na ukazatel ukazující na úložiště. Ve funkci cgm_read_fs_block() se již jen přepočítá adresa bloku na adresu do namapované oblasti a změní se ukazatel předaný parametrem. Ten bude ukazovat na požadovaný blok v namapované oblasti. Pseudokód: char *buf; char st_buf[SIZE]; buf = st_buf; read_fs_block(..., &buf, ...); /* dále již používám buf bez ohledu na to, do jaké části paměti ukazuje */ Výhody které z tohoto postupu plynou jsou ty, že pro načítání bloků se stále volá jedna funkce, a to read_fs_block(). Po návratu z funkce se používá předávaný ukazatel na úložiště stále stejným způsobem, nehledě na to, do jaké paměti ukazuje. Není potřeba kopírovat blok do jiného úložiště pomocí memcpy(), když se již v paměti nachází, tj. v namapované oblasti. Na podobném principu funguje i zápis bloků, kde se blok buď pomocí systémové funkce pwrite() zapíše na disk, nebo pomocí memcpy() překopíruje do namapované oblasti.

8.7

Přesun bloků

Pro přesuny bloků jsou implementovány dvě rozdílné metody, které jsem nazval Triple sort a Hop sort. Obě metody mohou přesouvat bloky s využitím, či bez využití namapování skupiny cylindrů. Metodu Triple sort lze považovat za bezpečnou z hlediska konzistence dat při neočekávaném ukončení programu. To platí ovšem jen v případě, že není použito namapování skupiny cylindrů do paměti, viz podkapitola . Přesouvání bloků je implementováno jen pro bloky, které jsou v poli blockap označeny jako BLCKALONE. Nepřesouvají se tedy např. nepřímé bloky s adresami či fragmentované bloky. Metody se postupně volají z funkce sortcg(), která postupně prochází pole slink a pro každý blok, který se ještě nenachází na cílové pozici, zavolá příslušnou metodu.

8.7.1

Vyhledání volného bloku

V případě metody Triple sort je potřeba před spuštěním přesunů vyhledat jeden volný blok. Ten bude sloužit jako dočasné úložiště přesouvaného bloku a musí se nacházet na jiné než aktuální skupině cylindrů. Vyhledání volného bloku má na starosti funkce find_freeblk(), která postupně prochází okolní skupiny cylindrů. Nejprve vždy vybere nejbližší předchozí

48

KAPITOLA 8. IMPLEMENTACE Parametr SWPDB SWPIB ZERODESTINO

Popis Blok je adresován přímo. Blok je adresován nepřímo. Blok cílové pozice je neobsazený.

Tabulka 8.3: Hodnoty kterých může nabývat proměnná flags ve struktuře SWPDATA. skupinu cylindrů a při neúspěchu vybere nejbližší následující. Ve funkci find_freeblk_cg() se poté z bitmapy bloků vyhledá volný blok.

8.7.2

Příprava přesouvaných bloků

Při přesunech bloků je vždy jeden z bloků považován za zdrojový, tj. src, a druhý za cílový, tj. dest. Zdrojový blok src se vždy přesouvá na pozici dest. Pro snadnější předávání parametrů mezi funkcemi jsou k oběma blokům vytvořeny proměnné typu SWPDATA. Jména proměnných jsou swpsrc a swpdest, či pokud pracujeme jen s jednou proměnnou ve funkci, tak jen swp. typedef struct swpdata { ino_t ino; uint32_t apindx; uint32_t blkindx; void *buf; uint32_t addr; uint8_t flags; } SWPDATA; ino Číslo inodu. apindx Index do blockap, resp. relativní adresa bloku od začátku skupiny cylindrů. blkindx Index datového bloku. Index je relativní k bloku s adresami. V případě nepřímé adresace je to tedy index do pole buf. buf Ukazatel na úložiště. Pokud je blok adresován pomocí přímé adresace, tak je v úložišti blok s inody. Z tohoto bloku se nejprve musí získat konkrétní dinode, a ten již obsahuje přímé odkazy na datové bloky v položce di_db. Pokud je blok adresován nepřímo, tak obsahuje blok uchovávající adresy. addr Pokud je blok adresován nepřímo, tak obsahuje adresu bloku, který je uložen v buf. U přímé adresace není adresa bloku nutná, jelikož jí snadno získáme z čísla inodu. flags Může nabývat některých bitových hodnot, popsaných v tabulce 8.3. Položky blkindx, buf a addr jsou potřebné z toho důvodu, že kromě samotného přesunu bloku se musí modifikovat i odkaz na tento blok. Jednotlivé položky v proměnné swpsrc se nastaví ve funkci prepare_swp_src() a v prepare_swp(). Hodnoty pro swpdest se nastaví v prepare_swp_dest() a prepare_swp().

8.7. PŘESUN BLOKŮ

49

Ve funkci prepare_swp_dest() se kromě nastavení hodnot musí provést kontrola zdrojového a cílového bloku, jelikož mohou nastat dvě situace, které je nutno ošetřit. • Oba bloky jsou adresovány pomocí přímé adresace a inody jsou uloženy ve stejném bloku. • Bloky jsou adresovány pomocí nepřímé adresace, ale současně se jedná o bloky jednoho inodu a adresy sdílí společný blok. Pokud jedna z možností nastane, tak musíme změnit ukazatel swpdest.buftak, aby ukazoval na stejnou oblast jako swpsrc.buf. Pokud by k tomu nedošlo, tak by swpsrc.buf i swpdest.buf obsahovaly stejné kopie bloků, ale provedené změny v nich by se navzájem neprojevily. To by vedlo k tomu, že např. při ukládání změněné swpdest.buf paměti bychom přemazali změny, které byly provedeny v swpsrc.buf.

8.7.3

Triple sort

Jedná se o implementaci algoritmu, popsaného v podkapitole 7.7.3. Algoritmus je definován ve funkci triple_sort() a skládá ze dvou fází. V první fázi se vždy zdrojový blok přesune na cílovou pozici. V druhé fázi se blok z cílové pozice stane zdrojovým a přesune se na svou cílovou pozici. V následujícím textu budeme pro přehlednost uvádět jen src nebo dest, ale jsou tím myšleny jednak bloky, ale současně i pomocné proměnné, jako např swpsrc a swpdest. Triple sort algoritmus: 1. Načti a nastav příslušné src proměnné. 2. Načti a nastav příslušné dest proměnné. 3. Zavolej funkci swap_dest_p1(), a poté swap_src_p1(). 4. Pokud je dest na cílové pozici, či dest byl prázdný, tak ukonči cyklus. 5. Nastav dest na src. 6. Načti a nastav příslušné nové dest proměnné. 7. Zavolej funkci swap_dest_p2(), a poté swap_src_p2(). 8. Pokud není dest na cílové pozici, tak nastav dest na src a pokračuj v bodě 2. Funkce swap_dest_p1() má za úkol přesunout blok z pozice A1, viz. obrázek 8.5, přičemž mohou nastat následující situace: • Pozice A1 je neobsazená. V tom případě nastav v bitmapě pozici A1 za obsazenou, jelikož se na ní bude přesouvat src blok. • Pozice B1 je neobsazená. Nastav v bitmapě pozici B1 na obsazenou a přesuň do ní dest blok.

50


Obrázek 8.5: Přesun bloků metodou Triple sort.

• Pokud nenastane žádná z výše uvedených situací, tak přesuň dest do D1. Funkce swap_src_p1() přesune src blok. Cílová pozice je vždy volná. Pokud byl dest přesunut na svou cílovou pozici, či byl neobsazený, tak se ukončí cyklus a zapíše se bitmapa. Před uložením bitmapy se ještě musí nastavit v bitmapě pozice C1 na neobsazenou. Pokud nebyl cyklus ukončen a vstupuje se do druhé fáze, tak se z dest stane src a určí se nová dest. Ve funkci swap_dest_p2() přesouvá blok z pozice B2. Při přesunu mohou nastat následující situace: • Pozice B2 je neobsazená. To mohlo nastat pouze v případě, že v první fázi byla pozice B1 totožná s C1. • Pozice E2 je neobsazená. V bitmapě se nastaví pozice E2 na obsazenou a přesune se blok. • Pozice E2 je neobsazená, ale současně je E2 totožná s C2. Přesune se pouze blok, jelikož bitmapa je již nastavená. Ve funkci swap_src_p2() se přesouvá blok z pozice D2 na pozici B2, která musí byt v tomto kroku již neobsazená. Pokud je nyní dest na cílové pozici, či byl prázdný, tak se cyklus ukončí a pomocí funkce write_cgblock() se zapíše bitmapa. V opačném případě se z dest stane src a pokračuje se v další iteraci, která v algoritmu začíná bodem 2.

8.8. UVOLNĚNÍ PROSTŘEDKŮ

8.7.4

51

Hop sort

Hop sort je upravený algoritmus popsaný v podkapitole 7.7.2, který se nachází ve funkci hop_sort(). Jediný rozdíl oproti algoritmu z analýzy je ten, že v bodě 4 nedochází k výměně bloků, ale místo toho se uloží jen zdrojový blok. Blok z cílové pozice se uloží až v následující iteraci, kdy se z něj stane blok zdrojový. Hop sort algoritmus: 1. Nastav proměnnou swpsrc. 2. Načti příslušný src blok do paměti, odeber src položku z pole blockap a nastav pozici bloku v bitmapě na neobsazeno. 3. Nastav proměnnou swpdest. (a) Pokud swpdest nemá flag ZERODESTINO, tak načti příslušný dest blok do paměti a odeber dest položku z pole blockap. 4. Ulož src blok na novou pozici. 5. Vlož src položku do pole blockap. 6. Pokud swpdest nemá flag ZERODESTINO, tak pokračuj v bodě 3 s tím, že všechny dest proměnné se stanou src. 7. Nastav dest pozici bloku v bitmapě na obsazenou. 8. Ulož bitmapu. V bodě 2 je potřeba nastavit bitmapa z toho důvodu, že v daný okamžik není jasné, jestli se na danou pozici bude přesouvat jiný blok, či jestli zůstane neobsazená. V bodě 7 se nastavuje bitmapa, jelikož cílová pozice byla neobsazena, a proto se ukončil cyklus. Bitmapa se ukládá jen jednou po ukončení cyklu. Z algoritmu je patrné, že se každý blok načte a uloží jen jedenkrát.

8.8

Uvolnění prostředků

K uvolnění operační paměti slouží funkce free_blockap(), free_blockapitem() a free_blockapfrag(), které uvolní prostředky spojené s polem blockap. Funkce free_slink() uvolní paměť spojenou s polem slink. Ve funkci cgm_unmap() se zavolá funkce munmap(), která slouží k odmapování souboru z paměti. Ještě před tím se zavolá funkce msync(), která zapíše všechny změněné bloky.

52


Kapitola 9

Testování funkčnosti Testování hrálo během vývoje důležitou roli, jelikož v případě chyby, nehrozí jen pád aplikace, ale ve většině případů i ztráta dat. To, jaké množství souborů může být ztraceno, záleží na mnoha faktorech, ale především na tom, jestli skupina cylindrů byla či nebyla mapována do paměti. V případě pádů aplikace s namapovanou skupinou cylindrů může dojít ke ztrátě v oblastech, které nebyly ještě zapsány na disk. Ty se samozřejmě nemusejí týkat jen jednoho souboru.

9.1

Testování defragmentace

Úkolem je zjistit, jestli program defragmentuje správně. Nekontrolují se obsahy jednotlivých souborů, ale to, jak jsou bloky na disku seřazeny. První test se provede pomocí systémového nástroje fsck_ffs. Ten ověří, zda-li se na disku nachází správný počet bloků a jestli je správně nastavena bitmapa bloků. Poté zkontroluje adresy na bloky, a to pro každý inode na souborovém systému. Ověří případnou duplicitu bloků, pokud by inody ukazovaly na stejné bloky. U inodů se dále ověří, jestli jejich velikosti korespondují s počtem bloků. Další test je již pomocí programu udef. Pomocí přepínače se zvolí požadovaná skupina cylindrů a vypíší se bloky, jenž se na ní nacházejí. Z výpisu je již patrné, jestli jsou bloky v požadovaném pořadí. V případě fragmentace volného místa, lze pro větší přehlednost využít i výpis bitmapy bloků. Pro ověření defragmentace souboru je také možné využít např. nástroj filestat6 . Ten pro konkrétní inode vypíše na kterých adresách, resp. skupinách cylindrů, se jeho fragmenty nacházejí a jejich velikosti.

9.2

Testování konzistence dat

Mnohem důležitějším testem je test na konzistenci dat. To znamená, že již neověřujeme kde jsou data uložená a v jakém pořadí, ale to, jestli se obsahy bloků nezměnily. Asi nejjednodušším způsobem jak to provést je pro každý soubor vypočítat kontrolní součet. Test 6 Program vznikl v průběhu psaní této diplomové práce a je volně ke stažení na http://code.google.com/p/filestat/. Inspirací mu byl stejnojmenný nástroj pro operační systém Solaris na architektuře Sparc.

53

54

KAPITOLA 9. TESTOVÁNÍ FUNKČNOSTI

byl tedy prováděn tak, že se před spuštěním defragmentace pro všechny soubory na disku spočetla hash pomocí algoritmu MD5 a uložila se do souboru. Po skončení defragmentace se provedlo totéž a pokud se soubory navzájem nelišily, tak byly soubory na disku nezměněny.

9.3

Velikost diskového oddílu

Velikost diskového oddílu, na kterém byly testy prováděny není pro samotné testování markantní, jelikož defragmentace probíhá vždy v rámci skupiny cylindrů. Podstatné pro testy bylo, aby se do testování zahrnulo několik skupin cylindrů a mohlo se např. otestovat řazení bloků, jejichž inode či bloky s nepřímými adresami, se nachází na jiné skupině cylindrů.

9.4

Testovaná data

V rámci testování bylo podstatné mít co nejvíce různorodý obsah souborového systému a tím pokrýt většinu možných případů, které mohou nastat v reálných systémech. Současně bylo nutné vytvořit uměle fragmentaci. To bylo z důvodu, že každý test se prováděl na právě naformátovaném souborovém systému a pouhé překopírování souborů by fragmentaci nevytvořilo, či ne alespoň fragmentaci takovou, k jaké dochází během stárnutí souborového systému [9]. Z toho důvodu byly soubory generovány. Při vytváření generovaných dat se uvažovalo několik případů: • Obecné generování. Probíhalo tak, že se pomocí skriptu vytvořilo několik souborů. Počet souborů byl dle potřeby v řádech stovek až tisíců. Ty se poté v různém pořadí zvětšovaly o určitý počet bloků, a tím docházelo k jejich fragmentaci. • Testování fragmentace volného místa. Provádělo se tak, že se vygeneroval větší počet menších fragmentovaných souborů. Několik souborů se poté smazalo, čímž vznikla fragmentace volného místa. • Větší soubor na více skupinách cylindrů. K tomu stačilo pouze generovat menší počet dostatečně velkých souborů.

9.5

Testovací nástroje

Pro usnadnění testování byly vytvořeny dva nástroje fragfile.sh a autofrag.sh. Oba nástroje jsou vytvořeny pomocí skriptovacího jazyka BASH. První z nich slouží ke generování fragmentovaných souborů. Hlavní parametry nástroje fragfile.sh je počet souborů, který se má generovat a počet repetic. V každé repetici se všechny soubory postupně zvětší o požadovanou velikost, což de facto znamená, že každá repetice vytvoří samostatný fragment. Nástroj autograg.sh obsahuje několik rozdílných testů. Každý test se skládá v podstatě z několika volaní fragfile.sh s rozdílnými parametry. Oba nástroje fragfile.sh a autofrag.sh jsou v dodatku B a C.

Kapitola 10

Měření V první části této kapitoly popíšeme několik testů, které byly provedeny za účelem změření času potřebného k odstranění fragmentace. Jedná se tedy o měření rychlosti programu. Čas potřebný k defragmentaci byl měřen na vygenerovaných datech v rámci jedné skupiny cylindrů, kde vygenerovaná data reprezentovala mezní případy, které mohou na souborovém systému nastat. Důvodem proč stačí provést měření jen na jedné skupině cylindrů je to, že se měření provádí na mezních případech. Proto odstranění fragmentace na každé jiné skupině cylindrů bude vyžadovat stejný nebo menší počet přesunů bloků, a tedy i stejný nebo kratší čás potřebný k defragmentaci. Fragmentace se odstraňovala pomocí obou metod, které program podporuje, tz. pomocí metody Triple sort 8.7.3 a Hop sort 8.7.4, a to s použitím i bez použití mapování skupiny cylindrů do paměti. Měření časů se zajistilo pomocí funkce gettimeofday(), která se zavolala na začátku a na konci funkce main(). V druhé části této kapitoly si ukážeme zrychlení souborového systému po provedení defragmentace. Příklady, jak se data generovala, lze najít v nástroji autofrag.sh v dodatku C.

10.1

Měření 1

V rámci tohoto měření bylo vygenerováno 1050 souborů, kde každý byl o velikosti 192 kB, tj. 12 bloků. K vygenerování souborů se použil nástroj fragfile.sh. Fragmentace se zajistila tak, že se nejprve vytvořilo 1050 souborů o velikosti jednoho bloku. Poté se každý soubor zvětšil o jeden blok a takto se zvětšovaly až do velikosti 12 bloků. Naměřené časy jsou v tabulce 10.1.

10.2

Měření 2

Bylo vytvořeno 850 souborů o velikosti 224 kB, tj. 14 bloků. Soubory byly vytvořeny pomocí nástroje fragfile.sh podobným způsobem, jako v předchozím případě. Jelikož jsou soubory

55

56

KAPITOLA 10. MĚŘENÍ

Metoda Triple sort Hop sort Triple sort s -m Hop sort s -m

Čas [s] 196.911 166.558 117.952 115.910

Tabulka 10.1: Naměřené hodnoty při defragmentaci 1050 souborů. Metoda Triple sort Hop sort Triple sort s -m Hop sort s -m

Čas [s] 192.198 161.459 124.439 122.758

Tabulka 10.2: Naměřené hodnoty při defragmentaci 850 souborů. větší jak 12 bloků, tak ke každému souboru, resp. inodu, přísluší i jeden blok s adresami. Všechny bloky jsou uloženy na stejné skupině cylindrů. Naměřené časy jsou v tabulce 10.2.

10.3

Měření 3

V tomto měření se provádělo řazení bloků, které byly adresovány nepřímo. Toho stavu se dosáhlo tak, že se nejprve vytvořilo 850 souborů o velikosti 224 kB, viz. předchozí případ. Tím se zaplnila celá jedna skupina cylindrů. Následně se opět všechny soubory zvětšily o 14 bloků. Jelikož na první skupině cylindrů již nebylo místo, tak se bloky začaly ukládat na druhou skupinu cylindrů. Porovnáním tohoto a předchozího měření, u kterého se defragmentuje stejný počet bloků, je patrné, jak se negativně projeví nepřímá adresace na čase defragmentace. Naměřené časy jsou v tabulce 10.3.

10.4

Zrychlení souborového systému po defragmentaci

V této podkapitole budeme zkoumat zrychlení souborového systému po provedení defragmentace. Měření probíhalo tím způsobem, že se na souborovém systému vygenerovaly dva Metoda Triple sort Hop sort Triple sort s -m Hop sort s -m

Čas [s] 253.140436 210.380257 172.599169 143.696910

Tabulka 10.3: Naměřené hodnoty při defragmentaci bloků, které jsou adresovány nepřímo.

10.4. ZRYCHLENÍ SOUBOROVÉHO SYSTÉMU PO DEFRAGMENTACI

57

fragmentované soubory a na jednom z nich se měřila rychlost čtení. Čtení souboru se zajistilo pomocí nástroje cat a md5. Konkrétně příkaz cat byl spouštěn následovně: time cat soubor > /dev/null. Celkem se desetkrát změřily časy pomocí nástroje time a poté se vypočítal jejich průměr. Před každým měřením byl souborový systém odpojen a byl přečten 300 MB soubor. Tím se minimalizoval vliv vyrovnávacích pamětí operačního systému. Soubory byly generovány pomocí nástroje fragfile.sh, kde jedním z parametrů byla velikost fragmentu. Pro měření byly zvoleny fragmenty o velikosti 1 bloku, 64 bloků, tj. 1 MB a pro větší soubory 640 bloků, tj. 10 MB. Velikost posledního fragmentu byla zvolena s ohledem na velikosti fragmentů souborového systému. Empiricky bylo zjištěno, že velikost fragmentu na souborovém systému je cca 60 MB. Po překročení této velikosti je fragment rozdělen a další bloky se již ukládají na jinou skupinu cylindrů. Defragmentace souboru většího než 60 MB má tedy smysl pouze tehdy, pokud jsou jeho fragmenty menší než 60 MB. Velikost souborového systému byla 5 GB, ačkoliv podstatnější pro testy bylo to, že generované soubory nebyly během vytváření limitovány nedostatkem místa. Celkem se měření provádělo na 5 souborech o velikostech 10 MB, 20 MB, 80 MB, 160 MB a 300 MB. Výsledky měření jsou v tabulce 10.4.

58

KAPITOLA 10. MĚŘENÍ

Velikost souboru [MB]

Velikost fragmentu [blok] 1

10

64 Po defragmentaci 1

20

64 Po defragmentaci 1

80

64 640 Po defragmentaci 1

160

64 640 Po defragmentaci 1

300

64 640 Po defragmentaci

Typ čtení md5 cat md5 cat md5 cat md5 cat md5 cat md5 cat md5 cat md5 cat md5 cat md5 cat md5 cat md5 cat md5 cat md5 cat md5 cat md5 cat md5 cat md5 cat

Čas [s] 0.535 0.540 0.335 0.353 0.308 0.308 1.032 1.055 0.701 0.705 0.563 0.536 4.188 4.203 2.713 2.667 2.187 2.205 2.132 2.158 8.398 8.410 5.501 5.306 4.320 4.312 4.218 4.255 15.711 15.664 10.329 10.019 8.126 8.083 7.866 7.907

Tabulka 10.4: Rychlost čtení souborů v závislosti na velikostech fragmentů.

Kapitola 11

Závěr Závěrečná kapitola obsahuje shrnutí hlavních bodů této práce.

11.1

Fragmentace souborových systémů

Součástí této práce bylo nastudovat a popsat problematiku fragmentace a také to, jak se jí moderní souborové systémy snaží předcházet. Fragmentace obecně byla popsána v kapitole 4 a popis metod, které se používají k předcházení fragmentace, v kapitole 6. Nicméně na základě těchto dvou kapitol jsem došel k závěru, že ani v moderních souborových systémech nelze fragmentaci zabránit. Důvodem je i to, že většina metod popisovaných v kapitole 6 neslouží primárně k zabránění fragmentace jako takové, ale spíše k zlepšení výkonnosti souborového sytému. Současně, pokud vezmeme v úvahu některé situace popsané v kapitole 4, které mohou nastat, tak bez následných přesunů bloků se fragmentaci zabránit nedá.

11.2

Vlastní implementace

Výsledkem této práce je nástroj na odstranění fragmentace, který byl řádně otestován a lze jej považovat za funkční. Jelikož pro souborový systém UFS neexistuje žádná jiná podobná aplikace, tak nelze výsledek práce s ničím jiným porovnat. Již to, že neexistuje žádný jiný nástroj na odstranění fragmentace, považuji za úspěch. Nicméně jsem si vědom toho, že se nalezne mnoho míst, které by bylo možné vylepšit. Při vývoji jsem se především zaměřoval na paměťové nároky celé aplikace, které pokud pomineme mapování skupiny cylindrů do paměti, jsou na dnešní poměry vcelku minimální, viz. podkapitola 8.3.1. Dále byl kladen velký důraz na to, aby po spuštění defragmentace nehrozilo žádné riziko ztráty dat, pokud by byla aplikace náhle ukončena. Tomuto kritériu vyhovuje metoda Triple sort. V neposlední řadě zde byla snaha na minimalizaci přístupů na disk, což se podařilo pomocí mapování skupiny cylindrů do paměti, ačkoliv to současně znamená potenciální riziko ztráty dat v případě náhlého ukončení aplikace. Za velmi přínosné považuji osobně také to, že jsem se podrobně seznámil s implementací souborového systému UFS, který je popsán v kapitole 3.

59

60

KAPITOLA 11. ZÁVĚR

11.2.1

Potenciální vylepšení

• Od počátku vývoje se počítalo s vícevláknovou variantou a větší část aplikace je tomu přizpůsobena. Nicméně po prvních testech bylo patrné, že vícevláknová varianta by nepřinesla výrazné zlepšení výkonu, jelikož většinu času aplikaci zaberou diskové operace. • Vylepšení, které by mohlo zlepšit výkon, by bylo použití vyrovnávacích pamětí pro již jednou načtené bloky. • Výpočet cílové pozice pro jednotlivé bloky by se mohl provádět na základě pozic ostatních bloků, resp. fragmentů. • Implementovat přesuny všech bloků, tj. např. i bloky obsahující nepřímé adresy. • V neposlední řadě by zlepšení výkonu bylo možné dosáhnout pomocí přesunů více bloků najednou.

11.3

Výsledky defragmentace

Z výsledku, které byly naměřeny a nacházejí se v tabulce 10.4 je patrné, že po defragmentaci vždy dojde k zrychlení při čtení souboru. U souborů, jejichž fragmenty jsou 10 MB, což je u fragmentovaného souborového systému vcelku reálné, se zrychlení po defragmentaci pohybuje mezi 2-3%. Otázkou ovšem vždy zůstává, do jaké míry budou data v souborových systémech fragmentována, aby se vyplatilo spouštět defragmentaci.

Literatura [1] CLEMENTS, A. Principles of computer hardware. Oxford University Press, 4th edition, 2006. [2] NĲS, G. et al. The Effects of Filesystem Fragmentation. Proceedings of the Linux Symposium. 2006. [3] HARIZOPOULOS, S. Hierarchical Caching and Prefetching for Improving the Performance of Continuous Media Servers. 1998. [4] LEFFLER, S. J. The Design and implementation of the 4.3 BSD Unix operating system. Addison-Wesley Publishing Company, 1990. [5] MARSHALL KIRK MCKUSICK, S. J. L. R. S. F. W. N. J. A Fast File System for UNIX. 1984. [6] MCDOUGALL – RICHARD. Solaris internals : Solaris 10 and OpenSolaris kernel architecture. Prentice Hall, 2nd edition, 2007. [7] MESSMER, H.-P. The indispensable PC hardware book. Addison-Wesley Publishing Company, 4th edition, 2002. [8] Přispěvatelé Wikipedie. BSD licence [online]. [cit. 29. 7. 2010]. Dostupné z: . [9] SMITH, K. A. – SELTZER, M. I. File System Aging — Increasing the Relevance of File System Benchmarks. Proceedings of the Linux Symposium. 1997. [10] SMITH, K. A. – SELTZER, M. I. File Layout and File System Performance. [11] V, A. K. K. et al. Ext4 block and inode allocator improvements. Proceedings of the Linux Symposium. 2008.

61

62

LITERATURA

Dodatek A

Seznam použitých zkratek ANSI American National Standards Institute ATA Advanced Technology Attachment BASH Bourne Again Shell BSD Berkeley Software Distribution CG Cylinder Group CVS Concurrent Version System EXT Extended File System FS File System HDD Hard Disk Drive INODE Index Node PATA Parallel ATA SSD Solid State Drive SSH Secure Shell UFS Unix File System USB Universal Serial Bus ZFS Zettabyte File System

63

64

DODATEK A. SEZNAM POUŽITÝCH ZKRATEK

Dodatek B

Nástroj fragfile.sh Nástroj fragfile.sh generuje fragmentované soubory. Generovat soubory může buď pomocí nástroje dd a čtení ze zařízení /dev/urandom či pomocí předgenerovaných souborů.

#!/usr/local/bin/bash if [ "$1" = "-h" ]; then echo "Usage: $0 filecount repeated name file" echo "filecount - # of files, only with rand" echo "repeated - # of repetition" echo "name - filename" echo "dirname - dir of copyed files" exit 1 fi if [ $# -lt 3 ]; then echo "Usage: $0 filecount repeated name [size rand | dirsrc dirdest]" exit 1 fi

START=1 FCOUNT=$1 REPEATED=$2 NAME=$3 RAND="" RNDCOUNT=20 DIRSRC="" DIRDEST="" if [ "$5" = "rand" ]; then

65

66

DODATEK B. NÁSTROJ FRAGFILE.SH

SIZE=$4 RAND=$5 elif [ "$4" = "big" ]; then DIRSRC="_big" DIRDEST=$5 elif [ "$4" = "small" ]; then DIRSRC="_small" DIRDEST=$5 elif [ "$4" = "normal" ]; then DIRDEST="$5" elif [ "$4" != "" ]; then DIRSRC="_$4" fi if [ "$DIRDEST" != "" ]; then mkdir /home/filedisk/$DIRDEST fi

RNDFILES="/home/tomas/Diplomka/udefrag/scripts/genfiles$DIRSRC/gen_" #RNDFILES=‘dirname $0‘/genfiles_big/gen_ #RNDFILES=‘dirname $0‘/genfiles_small/gen_ while [ $START -le $REPEATED ] do FI=1 while [ $FI -le $FCOUNT ] do if [ "$RAND" = "" ]; then cat $RNDFILES$((RANDOM%RNDCOUNT)) >> /home/filedisk/$DIRDEST/$NAME$FI else dd if=/dev/urandom of=/tmp/frag bs=$SIZE count=1 cat /tmp/frag >> /home/filedisk/$NAME$FI fi FI=‘expr $FI + 1‘ done START=‘expr $START + 1‘ done

Dodatek C

Nástroj autofrag.sh Nástroj autofrag.sh obsahuje řadu testů, které byly vykonány, ale také nastavení pro generování souborů, pro které se měřila rychlost defragmentace.

#!/usr/local/bin/bash DEV="" mount $DEV /home/filedisk rm -rf /home/filedisk/*

if [ "$1" == "test1" ]; then ./fragfile.sh 2 20 a_ big ./fragfile.sh 50 20 b_ ./fragfile.sh 2 20 a_ big ./fragfile.sh 50 20 c_ ./fragfile.sh 10 20 d_ big ./fragfile.sh 50 20 b_ ./fragfile.sh 10 20 e_ big ./fragfile.sh 50 20 b_ ./fragfile.sh 2 20 a_ big rm /home/filedisk/b_{5,10,15,20,25} rm /home/filedisk/c_{5,10,15,20,25} elif [ "$1" == "test2" ]; then ./fragfile.sh 5 5000 a_ elif [ "$1" == "test3" ]; then ./fragfile.sh 9 20 a_ big ./fragfile.sh 2 20 a_ big

67

68

DODATEK C. NÁSTROJ AUTOFRAG.SH

elif [ "$1" == "test4" ]; then ./fragfile.sh 9 20 a_ big ./fragfile.sh 2 20 b_ big elif [ "$1" == "test5" ]; then ./fragfile.sh 2 300 a_ big elif [ "$1" == "test6" ]; then ./fragfile.sh 100 20 a_ ./fragfile.sh 100 20 b_ ./fragfile.sh 100 20 c_ ./fragfile.sh 90 20 a_ ./fragfile.sh 90 20 b_ ./fragfile.sh 90 20 c_ elif [ "$1" == "test7" ]; then ./fragfile.sh 3 10 a_ small ./fragfile.sh 3 1 b_ small elif [ "$1" == "test8" ]; then ./fragfile.sh 30 50 a_ normal ./fragfile.sh 30 50 a_ normal ./fragfile.sh 30 50 a_ normal ./fragfile.sh 30 50 a_ normal ./fragfile.sh 30 50 a_ normal ./fragfile.sh 30 50 a_ normal ./fragfile.sh 30 50 a_ normal

dir1 dir2 dir3 dir4 dir5 dir6 dir7

elif [ "$1" == "mereni1" ]; then ./fragfile.sh 1050 12 a_ elif [ "$1" == "mereni2" ]; then ./fragfile.sh 850 14 a_ elif [ "$1" == "mereni3" ]; then ./fragfile.sh 850 14 a_ ./fragfile.sh 850 14 a_ elif [ "$1" == "zrychleni" ]; then # 10m ./fragfile.sh 2 640 a_ #./fragfile.sh 2 10 a_ big # 20m #./fragfile.sh 2 1280 a_ #./fragfile.sh 2 20 a_ big

69

# 80m #./fragfile.sh 2 5120 a_ #./fragfile.sh 2 80 a_ big #./fragfile.sh 2 8 a_ 640b # 160m #./fragfile.sh 2 10240 a_ #./fragfile.sh 2 160 a_ big #./fragfile.sh 2 16 a_ 640b # 300m #./fragfile.sh 2 19200 a_ #./fragfile.sh 2 300 a_ big #./fragfile.sh 2 30 a_ 640b else ./fragfile.sh 3 10 a_ big ./fragfile.sh 2 12 a_

fi echo ====================================== md5 /home/filedisk/* echo ====================================== umount /home/filedisk

70

DODATEK C. NÁSTROJ AUTOFRAG.SH

Dodatek D

Ukázka programu Souborový systém obsahuje 5 souborů. Každý soubor je o velikosti 5 bloků a fragmentován je po 1 bloku. === Super block === SBLOCK=16 DEV_BSIZE=512 ADR #8192 id=4d1a88fcbaecaab8 magic: 00011954 rps=60 fs_bsize=16384 fs_sblkno=8 fs_cblkno=16 fs_iblkno=24 fs_dblkno=1648 ncg = 6, fpg = 103664 ipg = 25984 fs_fragshift = 3 NINDIR = 4096 cgsblock: 8 fsbtodb: 32 inodes at: 96 data at: 6592

<--- Hlavička souborového systému.

=== Cylinder group === Cylinder: 0 cgbase 0 cgdmin 1648 cgimin 24 cgsblock 8 cgtod 16 cgstart 0 cgsize=16384

<--- Hlavička na skupině cylindrů.

71

72

DODATEK D. UKÁZKA PROGRAMU

cg_magic: 0x90255 cg_niblk: 25984 cg_ndblk: 103664 cg_iusedoff 174 (#89088) rotor 1856 irotor 7 frotor 1856 cgimin: 24 csum free block: 12725 inodes: 25976 frags: 14 inodes used:0-7 blks free: 1649-1655, 1657-1663, 1864-103663 === Inodes === 2) Adr 24 di_size: 512 di_nlink: di_db[0] 1656 (#3391488) db: 1656 3) Adr 24 di_size: 81920 di_nlink: di_db[0] 1664 (#3407872) di_db[1] 1704 (#3489792) di_db[2] 1744 (#3571712) di_db[3] 1784 (#3653632) di_db[4] 1824 (#3735552) db: 1664, 1704, 1744, 1784, 4) Adr 24 di_size: 81920 di_nlink: di_db[0] 1672 (#3424256) di_db[1] 1712 (#3506176) di_db[2] 1752 (#3588096) di_db[3] 1792 (#3670016) di_db[4] 1832 (#3751936) db: 1672, 1712, 1752, 1792, 5) Adr 24 di_size: 81920 di_nlink: di_db[0] 1680 (#3440640) di_db[1] 1720 (#3522560) di_db[2] 1760 (#3604480) di_db[3] 1800 (#3686400) di_db[4] 1840 (#3768320) db: 1680, 1720, 1760, 1800, 6) Adr 24 di_size: 81920 di_nlink: di_db[0] 1688 (#3457024) di_db[1] 1728 (#3538944) di_db[2] 1768 (#3620864) di_db[3] 1808 (#3702784) di_db[4] 1848 (#3784704) db: 1688, 1728, 1768, 1808, 7) Adr 24 di_size: 81920 di_nlink: di_db[0] 1696 (#3473408) di_db[1] 1736 (#3555328) di_db[2] 1776 (#3637248)

<--- Výpis jednotlivých inodů. 2 di_blocks: 4

1 di_blocks: 160

1824 1 di_blocks: 160

1832 1 di_blocks: 160

1840 1 di_blocks: 160

1848 1 di_blocks: 160

73

di_db[3] 1816 (#3719168) di_db[4] 1856 (#3801088) db: 1696, 1736, 1776, 1816, 1856 [ 0][ 0] block 0: 0 (0) [ 1][ 0] block 8: 0 (0) ... <--- Zde se nachází samé 0. [ 206][ 0] block 1648: 0 (0) [ 207][ 207] block 1656: 2 (0) <--- Root souborového systému. [ 208][ 208] block 1664: 3 (0) [ 209][ 212] block 1672: 4 (0) [ 210][ 216] block 1680: 5 (0) [ 211][ 220] block 1688: 6 (0) [ 212][ 224] block 1696: 7 (0) [ 213][ 209] block 1704: 3 (1) [ 214][ 213] block 1712: 4 (1) [ 215][ 217] block 1720: 5 (1) [ 216][ 221] block 1728: 6 (1) [ 217][ 225] block 1736: 7 (1) [ 218][ 210] block 1744: 3 (2) [ 219][ 214] block 1752: 4 (2) [ 220][ 218] block 1760: 5 (2) [ 221][ 222] block 1768: 6 (2) [ 222][ 226] block 1776: 7 (2) [ 223][ 211] block 1784: 3 (3) [ 224][ 215] block 1792: 4 (3) [ 225][ 219] block 1800: 5 (3) [ 226][ 223] block 1808: 6 (3) [ 227][ 227] block 1816: 7 (3) [ 228][ 228] block 1824: 3 (4) [ 229][ 229] block 1832: 4 (4) [ 230][ 230] block 1840: 5 (4) [ 231][ 231] block 1848: 6 (4) [ 232][ 232] block 1856: 7 (4) ^ ^ ^ ^ ^ | | | | | | | | | +--- Číslo bloku konkrétního inodu. | | | +------ Číslo inodu. | | +---------- Číslo fs bloku relativně k~CG. | +---------------------- Cílová pozice v~poli blockap. +---------------------------- Aktuální pozice v~poli blockap.

74

DODATEK D. UKÁZKA PROGRAMU

Dodatek E

BSD licence Překlad licence BSD:1 c Copyright , . Všechna práva vyhrazena. Redistribuce a použití zdrojových i binárních forem díla, v původním i upravovaném tvaru, jsou povoleny za následujících podmínek: • Šířený zdrojový kód musí obsahovat výše uvedenou informaci o copyrightu, tento seznam podmínek a níže uvedené zřeknutí se odpovědnosti. • Šířený binární tvar musí nést výše uvedenou informaci o copyrightu, tento seznam podmínek a níže uvedené zřeknutí se odpovědnosti ve své dokumentaci a/nebo dalších poskytovaných materiálech. • Ani jméno vlastníka práv, ani jména přispěvatelů nemohou být použita při podpoře nebo právních aktech souvisejících s produkty odvozenými z tohoto software bez výslovného písemného povolení. TENTO SOFTWARE JE POSKYTOVÁN DRŽITELEM LICENCE A JEHO PŘISPĚVATELI „JAK STOJÍ A LEŽÍ“ A JAKÉKOLIV VÝSLOVNÉ NEBO PŘEDPOKLÁDANÉ ZÁRUKY VČETNĚ, ALE NEJEN, PŘEDPOKLÁDANÝCH OBCHODNÍCH ZÁRUK A ZÁRUKY VHODNOSTI PRO JAKÝKOLIV ÚČEL JSOU POPŘENY. DRŽITEL, ANI PŘISPĚVATELÉ NEBUDOU V ŽÁDNÉM PŘÍPADĚ ODPOVĚDNI ZA JAKÉKOLIV PŘÍMÉ, NEPŘÍMÉ, NÁHODNÉ, ZVLÁŠTNÍ, PŘÍKLADNÉ NEBO VYPLÝVAJÍCÍ ŠKODY (VČETNĚ, ALE NEJEN, ŠKOD VZNIKLÝCH NARUŠENÍM DODÁVEK ZBOŽÍ NEBO SLUŽEB; ZTRÁTOU POUŽITELNOSTI, DAT NEBO ZISKŮ; NEBO PŘERUŠENÍM OBCHODNÍ ČINNOSTI) JAKKOLIV ZPŮSOBENÉ NA ZÁKLADĚ JAKÉKOLIV TEORIE O ZODPOVĚDNOSTI, AŤ UŽ PLYNOUCÍ Z JINÉHO SMLUVNÍHO VZTAHU, URČITÉ ZODPOVĚDNOSTI NEBO PŘEČINU (VČETNĚ NEDBALOSTI) NA JAKÉMKOLIV ZPŮSOBU POUŽITÍ TOHOTO SOFTWARE, I V PŘÍPADĚ, ŽE DRŽITEL PRÁV BYL UPOZORNĚN NA MOŽNOST TAKOVÝCH ŠKOD. 1

Překlad licence byl převzat z [8].

75

76

DODATEK E. BSD LICENCE

Dodatek F

Obsah přiloženého CD . |-|-|-|-|-|-|-|-|-| | | | | | |-|-|-|-|-|-|-‘--

Diplomka Makefile cgmmap.c cgmmap.h hop_sort.c hop_sort.h io.c io.h scripts |-- autofrag.sh |-- fragfile.sh |-- genfiles |-- genfiles_640b |-- genfiles_big ‘-- genfiles_small sortcg.c sortcg.h udef.c udef.h udef_stat.c udef_stat.h udefcg.c udefcg.h

Každý adresář genfiles obsahuje 20 souborů s náhodným obsahem. Soubory se jmenují gen_0 až gen_19 a používají se ke generování náhodných souborů v nástroji fragfile.sh. Adresář Diplomka obsahuje diplomovou práci.

77

Na tomto místě bude oficiální zadání vaší práce

Recommend Documents