System plików jest sposobem przechowywania danych w pamięci trwałej komputera, dane są przechowywane w plikach. Chcielibyśmy aby system plików zapewniał:

• rozsądną strukturyzację danych tj. umieszczenie danych w plikach, plików w katalogach

• możliwie szybki dostęp do danych

• podstawowe operacje na danych (tworzenie, modyfikacja, usuwanie)

• bezpieczeństwo danych

ponadto chcemy przetrzymywać pewne istotne informacje o danych takie jak:

• czas utworzenia modyfikacji pliku

• prawa własności

• prawa dostępu do pliku

• pewne atrybuty pliku (np. read-only, hidden etc.)

File Allocation Table (FAT)

System FAT, jak sama nazwa wskazuje, opiera się na tablicy alokacji plików, która jest jego główną i jedyną obok wskazania na boot sector (2 kopie w FAT 32) i katalog superużytkownika (tego drugiego nie ma w FAT 32) metadaną systemu plików. Dla każdego pliku pamiętany jest w niej jego pierwszy klaster (odpowiednik bloku w ext-ach), który wskazuje z kolei na kolejny klaster plików itd., co daje tak zwany łańcuch alokacji pliku. Klastry nienależące do żadnego pliku są oznaczane zerem, a ostatnie klastry pliku -specjalną wartością, równą 0xFFFF w FAT16 i 0xFFF w FAT 32. Rozmiar tablicy alokacji plików jest rozpoznawany po liczbie w zapisie FAT X (X=12, 16 lub 32) i równy 2X (X to liczba bitów, w jakiej są pamiętane numery klastrów). Rozmiar klastra jest zmienny; w FAT 12 rozmiar klastra to od 512 B do 8 kB, tabela domyślnych rozmiarów dla FAT 16 i FAT 32 w tabeli.

Rozmiary klastrów w FAT 16
Rozmiar woluminu (w MB)		Rozmiar klastra
0-32 (jeżeli mniej niż 16 MB, to Windows używa przy formatowaniu FAT 12 zamiast FAT 16)		512 B
33-64		1 KB
65-128		2 KB
129-256		4 KB
257-511		8 KB
512-1023		16 KB
1024-2047		32 KB
2048-4095		64 KB
Rozmiary klastrów w FAT 32
Rozmiar partycji	Rozmiar klastra
32 MB - 8 GB	4 KB
8 GB - 16 GB	8 KB
16 GB - 32 GB	16 KB
32 GB	32 KB

Na podstawie powyższych informacji łatwo liczymy, że maksymalny rozmiar woluminu w FAT 12 to 32 MB, w FAT 16 to 4 GB, a w FAT 32 to 8 TB (ten ostatni teoretycznie, bo obsługuje takie wielkości, ale sam potrafi stworzyć do 32 GB). Wpis katalogowy zajmuje w FAT-ach 32 B (pamięta nazwę w formacie MS-DOS 8.3 - krótką, wielkość, początkowy klaster i czasu ostatniego dostępu i modyfikacji), więc długie nazwy są obsługiwane tandetnie poprzez dodawanie sztucznych wpisów katalogowych, które pamiętają tylko ciąg dalszy nazwy. Kolejnym ograniczeniem jest maksymalna wielkość pliku do 4 GB. Ogólnie systemy FAT są dość stabilne, ale tandetnie napisane i pozbawione wielu istotnych funkcjonalności.

Informacje na dysku ułożone są po kolei w jednostkach zwanych sektorami, ponieważ te dane często ulegają modyfikacjom, nie można sztywno przydzielać obszarów w których są składowane, trzeba wiec gdzieś pamiętać gdzie umieszczony jest ciąg dalszy pliku. Tę role pełni File Allocation Table (FAT) od której wzięła się nazwa systemu plików.
Partycja jest podzielona na logiczne jednostki zwane klastrami (ang. clusters) Klaster odpowiada stałej ilości sektorów, wielkość klastra zależy od wersji FAT-a, wacha sie pomiędzy 2kB a 32kB, zazwyczaj przy sektorach wielkości 512B przypada 8 sektorów na klaster. Klaster jest przyporządkowany dokładnie jednemu plikowi, aczkolwiek jeden plik może być związany z kilkoma klastrami. Poniższy rysunek przedstawia schemat budowy partycji FAT.

Bootsector - to zawsze pierwszy sektor partycji, zawiera podstawowe informacje o partycji, między innymi:

• wielkość partycji

• wielkość sektora (w bajtach)

• ilość sektorów w klastrze

• typ partycji (np. FAT32)

• ilość kopii tablicy FAT

• wskaźniki do innych danych

• kod ładujący system operacyjny

Tablica FAT - jest to struktura danych, w której przechowywane są informacje o położeniu pliku na dysku. Każdemu klastrowi odpowiada dokładnie jeden wpis w tablicy, ten wpis to zazwyczaj informacja o tym że klaster jest jakiś specjalny bądź jest to numer klastra zawierający ciąg dalszy pliku. Szczegóły pokazane w tabelce poniżej:

FAT12	FAT16	FAT32	Znaczenie
0x000	0x0000	0x0000000	Wolny klaster
0x001	0x0001	0x0000001	Zarezerwowany klaster
0x002 - 0xFEF	0x0002 - 0xFFEF	0x0000002 - 0xFFFFFEF	Używany klaster, gdy nie jest ostatnim klastrem pliku, wartość wskazuje na następny klaster pliku
0xFF0 - 0xFF6	0xFFF0 - 0xFFF6	0xFFFFFF0 - 0xFFFFFF6	Wartości zarezerwowane
0xFF7	0xFFF7	0xFFFFFF7	Uszkodzony klaster
0xFF8 - 0xFFF	0xFFF8 - 0xFFFF	0xFFFFFF8 - 0xFFFFFFF	Koniec pliku

Kopia FAT - ze względu na dużą wartość informacji przechowywanych w tablicy warto zabezpieczyć sie na wypadek zniszczenia oryginalnej tablicy (lub jej części) poprzez duplikacje danych umieszczonych na niej. Niestety rozwiązanie nie zapewnia należytego bezpieczeństwa z co najmniej dwóch powodów. Ze względu na to że obie tablice są umieszczone obok siebie w przypadku wykrycia bad sektorów w jednej jest duża szansa, że uszkodzona jest też kopia, ponadto usterka może być zduplikowana przed wykryciem błędu.

Root directory - jest to katalog główny systemu plików, występuje w ustalonym miejscu w partycji. W FAT12 i FAT16 ma sztywno ustaloną wielkość - mieści do 512 wpisów (przy długich nazwach jeszcze mniej). W FAT32 nie ma tego ograniczenia.

Obszar danych - pliki (i katalogi) umieszczone w klastrach jeden lub więcej klastrów przypadających na plik. Reprezentowane są jako ciąg bajtów, jeśli nie starcza klastra kolejne są w następnym itd. Za poprawność operacji następnika odpowiedzialna jest tablica FAT. Katalogi są to pliki specjalnej postaci. Katalog jest podzielony na małe struktury nazywane wpisami. Każdy wpis ma rozmiar 32 bajtów i jest informacją o katalogu bądź pliku, zawartym w naszym katalogu. Wpis zawiera pola:

• 8 bajtów - nazwa pliku, (literki, cyferki i $ % @ ' - _ ( ) ~ ! # ^ & później również + , ; = [ ])

• 3 bajty - rozszerzenie,

• 1 bajt - atrybuty pliku:

• read-only, tylko do odczytu

• hidden, ukryty

• system, plik systemowy

• volume label, tak jest oznaczony jeden plik w katalogu głównym, jego nazwa jest nazwą dysku

• subdirectory, czy jest to katalog

• archive, plik, który trzeba skopiować przy następnej kopii zapasowej

• device, plik reprezentuje urządzenie

• unused, nie używane

• 1 bajt - wielkość liter nazwy i rozszerzenia pliku,

• 1 bajt - czas utworzenia w milisekundach,

• 2 bajty - czas utworzenia,

• 2 bajty - data utworzenia,

• 2 bajty - czas ostatniego dostępu,

• 2 baty - zarezerwowane,

• 2 bajty - czas utworzenia lub ostatniej modyfikacji pliku,

• 2 bajty - data utworzenia lub ostatniej modyfikacji pliku,

• 2 bajty - numer klastera gdzie rozpoczyna się plik,

• 4 bajty - rozmiar pliku.

Podsumowanie

Poniżej tabelka z ograniczeniami poszczególnych wersji FAT-a

Limits	FAT12	FAT16	FAT32
Max file size	32MB	2GB	4GB
Max number of files	4077	65517	268435437
Max volume size	32MB	4GB	2TB

Powyższe dane zależą oczywiście od wielkości klastra, większy rozmiar klastra to większy maksymalny rozmiar partycji ale też większa utrata danych (statystycznie połowa klastra jest wolna)

zalety

• działa - w dostatecznym stopniu realizuje podstawowe postulaty ze wstępu

• prostota i popularność - FAT jest wspierany przez wszystkie systemy operacyjne często służy do wymiany danych miedzy platformami

wady FAT

• sekwencyjny dostęp do plików

• podatność na awarie

• nieefektywny na dużych partycjach

New Technology File System (NTFS)

Główne założenia NTFS:

• Niezawodność - duża tolerancja błędów przy zagwarantowaniu bezpieczeństwa danych.

• Bezpieczeństwo i kontrola dostępu - system praw dostępu.

• Przełamanie bariery rozmiaru - rozmiar partycji ograniczony jedynie wymiarem dysku, macierze RAID (Redundant Arrays of Inexpesive Disks).

• Efektywność - lepsze wykorzystanie dostępnej pamięci dzięki nowym rozwiązaniom alokującym pamięć.

• Długie nazwy plików - do 255 znaków dopuszczające także znaki diakrytyczne.

• Sieciowość - właściwości ułatwiające korzystanie z sieci.

NTFS posiada własności(niektóre):

• Udoskonalone bezpieczeństwo i system praw - m. in. przydział praw do zasobów, podział na grupy użytkowników.

• Dzienniki zmian (Change Journals) - wszystkie zmiany w systemie są notowane. W przypadku awarii niedokończone akcje zostają wycofane, dzięki czemu system zawsze pozostaje w stabilnym stanie.

• Disk Quotas - kontrola i limitowanie przestrzeni dyskowej użytkowników.

• Disk Defragmenter - defragmentator dysku pozwalający redukować straty przestrzeni dyskowej spowodowane fragmentacją.

Idea

Sprostanie tym wymaganiom musiało się wiązać z zupełnie innym podejściem do problemu przechowywania informacji. Tak samo jak w FAT przestrzeń dyskowa jest podzielona na klastry. Bootsector pozostaje bez zmian. W odróżnieniu od FAT wszystkie dane są przechowywane jako pliki. Rozróżniamy:

• zwykłe pliki

• pliki z metadanymi

• foldery

Pliki z metadanymi zawierają informacje o danych. Najważniejszym z tych plików jest Master File Table (MFT). Jest to pierwszy z 16 plików specjalnych. Jego rola jest podobna do roli jaką pełni tablica FAT. MFT jest tablicą, w której każdy wpis reprezentuje w odróżnieniu od FAT-a nie klaster, ale plik. Każdy plik musi mieć wpis w tablicy MFT, w szczególności, sam MFT podobnie jak pozostałe 15 plików specjalnych mają własne wpisy. Poniżej schemat budowy partycji NTFS:




Dla MFT zarezerwowano tzw. MFT-area która jest jakąś ustaloną częścią partycji. Rozmiar MFT-area to 12,5% do 50% wielkości napędu logicznego. Dane (różne od wpisów do MFT) w MFT-zone zapisuje sie dopiero gdy nie ma miejsca w pozostałych częściach dysku. Samo MFT jest podzielone na rekordy ustalonej wielkości np. 2kB. Ze względów bezpieczeństwa, pierwsze 16 rekordów (te zawierające pliki z metadanymi), posiada swoją kopie dokładnie na środku bądź na końcu partycji.

Metapliki w NTFS

1. MFT - jest pierwszym i najważniejszym metaplikiem. W niej znajdują się informacje o niej samej, oraz o położeniu wszystkich metaplików. Tych metaplików jest 12 i zajmują one pierwsze 12 rekordów MFT, kolejne 4 są zarezerwowane na przyszłość. Rozmiar MFT zależy od liczby plików na woluminie.

2. MFT Mirror - kopia pierwszych czterech wpisów w MFT, znajdująca się w logicznym środku woluminu.

3. LogFile - dziennik służący utrzymywaniu spójności danych w razie awarii.

4. Volume - plik zawierający fizyczne informacje o woluminie oraz różne flagi do określania jego stanu - np. Dirty Flag ustawiany przy montowaniu dysku i czyszczony przy odmontowywaniu - dzięki temu można stwierdzić, czy dysk został odłączony z powodu awarii czy normalnie odmontowany.

5. Attribute definitions - wszystkie informacje o pliku są zawarte w atrybutach (które nie są niczym innym jak strumieniami danych, czyli ciągami bajtów), a wszystkie informacje o atrybutach są zawarte w tym pliku. Każdy rodzaj atrybutu musi mieć swój wpis tutaj. We wpisie, poza nazwą, trzymane są takie informacje jak np. ograniczenie na wielkość.

6. Root folder - katalog główny woluminiu.

7. Bitmap - bitmapa określająca zajętość klastrów na woluminie.

8. Boot - plik zawierający dane o fizycznych właściwościach woluminu oraz, w wypadku dysków systemowych, kod startujący system operacyjny.

9. BadClus - plik obsługujący uszkodzone klastry na dysku. Jest to rzadki plik zawierający cały obszar dysku. Uszkodzone klastry są oznaczane jedynkami, a dobre zerami - co jako że plik jest rzadki oznacza, że praktycznie zawiera tylko uszkodzone klastry (o rzadkich plikach więcej informacji można znaleźć w części prezentacji poświęconej kompresji danych). Ponieważ są one zajęte przez ten plik, to żadnemu innemu nie zostaną przydzielone. Pliki systemowe są dostępne tylko dla systemu, więc nikt nie będzie po nim pisał/czytał.

10. Secure - zawiera tablicę deskryptorów bezpieczeństwa dla wszystkich plików na dysku. Kiedyś każdy plik sam trzymał swój deskryptor, ale było to nieefektywne (więcej o tym pliku w dziale o zarządzaniu uprawnieniami).

11. Upcase - jako że NTFS tworzy pliki z wyłącznie wielkimi literami w nazwie, powstała szybka metoda konwersji małych znaków na wielkie. Ten plik zawiera tablicę konwersji - tablicę w której na miejscu o konkretnym numerze znajduje się wielka litera, odpowiadająca znakowi o tym numerze.

12. Extend - Katalog zawierający pliki $Quota, $ObjId, $Reparse i $UsnJrnl.

• $Quota - plik z informacjami o quotach wszystkich użytkowników

• $ObjId - tablica wszystkich Object_ID wszystkich plików na dysku (odpowiednik bitmapy)

• $Reparse - informacje o podmontowanych dyskach

• $UsnJrnl - odczytywalna dla użytkownika wersja dziennika

kolejne 4 numery są nieużywane, ale zarezerwowane na przyszłość - do rozwoju

Pliki

Pliki w NTFS reprezentowane są jako zbiory struktur zwanych atrybutami. Każdy atrybut może wystąpić dla jednego pliku wielokrotnie, każdy może też mieć przypisaną nazwę.

Atrybuty nie są ustalone odgórnie, lecz zapisane w pliku systemowym $AttrDef. Istnieje więc możliwość ich zmiany lub dodania nowych.

Gdzie są trzymane dane?

• Jeśli plik jest mały tj. łączny rozmiar zawartości jego atrybutów nie przekracza rozmiaru jednego wpisu do MFT to całość jest tam przechowywana.

• Dla nieco większych plików zamiast samych danych w MFT jest przechowywana lista wskaźników do klastrów zawierających te rzeczy np. atrybut $DATA zawiera numery klastrów gdzie faktycznie są te dane.

• Jeśli dane są naprawdę duże (na tyle, że same wskaźniki do nich nie zamieszczą się w jednym rekordzie MFT) to trzymany jest wskaźnik do miejsca gdzie przetrzymywane są wskaźniki.

Katalogi

Katalogi podobnie jak w FAT, traktowane są jak zwyczajne pliki, z tą różnicą że zawartość katalogu jest trzymana w B+ drzewie, co znacząco przyspiesza wyszukiwanie. Poniżej rysunek przedstawiający różnice w czasie szukania w porównaniu z liniowym przechodzeniem listy.

Bezpieczeństwo

Uprawnienia
Często istnieje potrzeba ograniczenia uprawnień w dostępie do pików poszczególnym użytkownikom systemu. Poniżej zestaw podstawowych uprawnień w NTFS

• Read - czytanie

• Write - zapis

• Execute - wykonywanie

• Delete - usuwanie

• Change Permissions - zmiana uprawnień

• Take Ownership - zmiana właściciela pliku
  

Transakcyjność i kronikowanie

Modyfikacje danych takie jak np. kopiowanie często wymagają więcej niż jednej operacji na dysku. Awaria (np. utrata zasilania) podczas wykonywania tych operacji może powodować utratę spójności danych na dysku, co więcej awaria w pewnych newralgicznych punktach np. podczas zmian struktur danych partycji, może spowodować uszkodzenie całego dysku logicznego. Są oczywiście narzędzia do naprawy i odzyskiwania danych (np. scandisc), jednakże proces ten jest bardzo czasochłonny i nie zawsze daje oczekiwane efekty.

Z punktu widzenia użytkownika dobrze by było, gdyby wszystkie logiczne operacje na plikach były realizowane w sposób atomowy. Jest to realizowane w następujący sposób. Każda operacja przed wykonaniem jest zapisywana do dziennika $LogFile. Jeśli nastąpi awaria podczas wykonywania tej operacji, przy ponownym montowaniu partycji sprawdzane jest czy wszystkie zapisane w dzienniku operacje zakończyły sie sukcesem. Jeśli tak nie było wycofywano skutki częściowo dokonanych zmian. Co 8 sekund do dziennika jest zapisywany tzw. check-point, co oznacza że wszystkie wcześniejsze wpisy do dziennika są w porządku. To co sie faktycznie zmieniło zapisywane jest w dzienniku zmian (Change Journal) zaraz po fizycznym dokonaniu zmiany. Dzięki temu można określić co się zmieniło, przy wycofywaniu transakcji.

Kronika

Aby zapewnić atomowość operacji, część systemów plików zapożyczyło metodę utrzymywania atomowości operacji (które od tego momentu będziemy nazywać transakcjami) z systemów baz danych. Wykorzystują one do tego celu dziennik zwany też częściej w przypadku systemów plików kroniką. Kronika jest miejscem, gdzie system plików zapisuje przyszłe zmiany w stosunku do systemu plików, rejestrując je zanim jeszcze operacje powodujące te zmiany zostaną faktycznie wykonane. Kronika przydatna jest szczególnie podczas awarii komputera, gdyż poprzez analizę operacji zapisanych w kronice system operacyjny może starać się przywrócić właściwy stan poprzez odtworzenie lub wycofanie przerwanych operacji. Pomaga to w spełnieniu jednego z podstawowych obowiązków systemu operacyjnego, jakim jest zapewnienie, że system plików znajduje się w spójnym stanie, przed udostępnieniem go użytkownikowi.

Głównym celem kroniki jest zachowanie abstrakcji atomowości operacji na systemie plików, co pozwala zachować jego spójność.

Kronika ma niezaprzeczalne zalety, jakimi są:

• większe bezpieczeństwo - jest to główna zaleta systemów z kroniką, która jest - przypomnijmy - jednocześnie najważniejszym z wymagań stawianych systemom plików.

• krótszy czas przeładowania systemu - jeśli system nie został zamknięty poprawnie, wówczas czas potrzebny na sprawdzenie poprawności dysku może być znaczący szczególnie przy rozmiarach dysków spotykanych w dzisiejszych czasach. Na największych serwerach proces ten mógłby dosłownie zająć kilkanaście godzin, co mogłoby być przyczyną dalszego przestoju systemu po awarii. Istnienie kroniki pozwala zaś na szybkie odtworzenie wszystkich operacji, które nie zdążyły się odbyć do końca przed momentem awarii.

Jednak kroniki mają też pewne wady, do których możemy zaliczyć m.in.:

• wydłużony czas wykonywania niektórych operacji - dalej będziemy opisywać różne sposoby zmniejszenia nakładu potrzebnego na prowadzenie kroniki, jednak ogólnie rzecz ujmując wiąże się to z tym, że część danych musimy zapisać podwójnie - raz w dzienniku, a drugi raz utrwalając je w systemie plików. Nie zawsze jest to jednak prawdą i przy pewnych konfiguracjach oraz zastosowaniach systemy plików z kroniką mogą okazać się wydajniejsze.

• większe skomplikowanie systemu plików - co może być powodem błędów w implementacji, jednak w przypadku dobrze przetestowanych systemów plików z kroniką ryzyko z tym związane jest zaniedbywalnie małe i praktycznie takie samo, jak w wypadku systemów plików bez kroniki.

• niezgodność z dotychczasowymi systemami plików - jak się później okaże, nie jest to zawsze prawdą, jednak w większości przypadków zmiana systemu plików na system plików z kroniką oznacza pracochłonne archiwizowanie wszystkich danych zawartych w danym systemie plików, zmianę systemu, a następnie ich odtworzenie, co w złośliwych przypadkach może prowadzić do uszkodzenia lub utraty części danych.

Quota (kontyngenty dyskowe)

Quota jest wygodną funkcjonalnością systemów plików, umożliwiającą limitowanie miejsca dyskowego, z którego użytkownik może korzystać. Jest to szczególnie ważne na wielkich serwerach z tysiącami użytkowników, aby użytkownicy nie mogli całkowicie zapchać dysków. W systemie Windows długo nie było wsparcia dla quoty, pojawiło się dopiero wraz NTFS-em.

Quota w systemie NTFS pozwala na ustawienie limitu dla każdego użytkownika z osobna, można również ustawić opcję logowania każdego zdarzenia które przekracza limit. Jeżeli program użytkownika przekracza limit dyskowy, to próba alokacji nowego kawałka dysku kończ y się błędem "disk full".

Ustawienie limitów w Windowsie jest bardzo proste, co pokazuje poniższy obrazek:

Rys. Ustawianie quoty w systemie operacyjnym Windows

Jak widać można ustawić "warning level", co odpowiada limitowi miękkiemu, oraz "limit disk space", co odpowiada limitowi twardemu. Dodatkowo po kliknięciu w Quota Entries możemy ustawić inne limity aktualnym użytkownikom.

NTFS przechowuje informacje o limitach w pliku \$Extend\$Quota, który zawiera tabele $O i $Q. NFTS przydziela każdemu użytkownikowi unikalny numer UserID. Kiedy administrator ustawia limit dla użytkownika, NTFS przypisuje jego Security ID (SID) numer użytkownika User ID oraz w tabeli $Q zamieszcza informacje o limitach dla danego użytkownika. Informacja w tabeli $Q zawiera nie tylko wartość limitu, ale także ilość aktualnie zajętego miejsca.

Przy liczeniu sumarycznego miejsca zajmowanego przez użytkownika, rozmiar pliku jest liczony na podstawie jego nominalnej wielkości a niekoniecznie ilości faktycznego miejsca zajętego na dysku. Chodzi tu zwłaszcza o rzadkie pliki czy sytuacje, gdy jest włączona kompresja dysku. Wtedy nawet jeżeli plik o rozmiarze 50 KB po skompresowaniu zajmuje na dysku tylko 10 KB, to cała jego wielkość (czyli 50 KB) zostanie uznana jako używana przez użytkownika.

Podsumowanie

NTFS
Około 16 KB (+rozmiar MFT) zarezerwowane na metapliki
Bardzo mała redundancja danych - tylko kopia 4 pierwszych wpisów z MFT
MFT zmiennej wielkości
Klastry wielkości od 512 B do 4 KB (można zmienić do 64 KB)
Wielkość metadanych zależy od wykorzystania dysku
Rozbudowany i duży kod źródłowy
Skomplikowane i trudne w implementacji struktury danych
Kronikowanie
Dużo różnych informacji o pliku - wpis w MFT ok. 1 KB

---