Прості файлові системи

Найбільш простий файловою системою можна рахувати структуру, що створюється архіватором системи UNIX — програмою tar (Таре ARchive — архів на [магнітною] стрічці). Цей архіватор просто пише файли один за іншим поміщаючи на початку кожного файлу заголовок з його ім'ям і довжиною (мал. 11.5). Аналогічну структуру мають файли, що створюються архіваторами типа arj; на відміну від них, tar не упаковує файли.

Мал. 11.5. Структура архіву tar

Для пошуку якогось певного файлу ви повинні прочитати перший заголовок; якщо це не той файл, то відмотати стрічку до його кінця, прочитати новий заголовок і так далі Це не дуже зручно, якщо ми часто звертаємося до окремих файлів, особливо враховуючи те, що цикл перемотування — прочитування — перемотування у більшості стрічкопротяжних пристроїв відбувається набагато повільніше, ніж просте перемотування. Зміна ж довжини файлу в середині архіву або його стирання взагалі перетворюється на цілу епопею. Тому tar використовується для того, щоб зібрати файли з диска в деяке єдине єство, наприклад, для передачі по мережі або для резервного копіювання, а для роботи файли зазвичай розпаковуються на диск або інший пристрій з довільним доступом.
Для того, щоб не займатися при кожному новому пошуку переглядом всього пристрою, найзручніше розмістити каталог у визначеному місці, наприклад на початку стрічки. Найбільш просту, із знайомих авторові, файлову систему такого типа має ОС RT-11. Це єдина відома авторові файлова система, яка з однаковим успіхом застосовувалася як на стрічках, так і на пристроях з довільним доступом. Усе більш складні ФС, обговорювані далі, використовуються лише на пристроях довільного доступу. У наш час найбільш поширений тип пристрою довільного доступу, що запам'ятовує, — це магнітний або оптичний диск, тому далі в тексті ми називатимемо такі пристрої просто дисками — скорочено, хоча таке скорочення і не цілком коректно.
У цій ФС, як і у всіх обговорюваних далі, місце на диску або стрічці виділяється блоками. Розмір блоку, як правило, збігається з апаратним розміром сектора (512 байт у більшості дискових пристроїв), проте багато фС можуть використовувати логічні блоки, що складаються з декількох секторів (так звані кластери).
Використання блоків і кластерів замість адресації з точністю до байта обумовлене двома причинами. По-перше, у більшості пристроїв довільного доступу доступ довільний лише з точністю до сектора, тобто не можна довільно вважати або записати будь-який байт — потрібно прочитувати або записувати весь сектор цілком. Саме тому в системах сімейства Unix такі пристрої називаються блоковими (block-oriented).
По-друге, використання крупних одиниць, що адресуються, дозволяє різко збільшити простір, що адресується. Так, використовуючи 16-бітовий покажчик, з точністю до байта можна адресувати всього 64 Кбайт, але якщо як одиниця адресації узяти 512-байтовий блок, то об'єм даних, що адресуються, зможе досягти 32 Мбайт; якщо ж використовувати кластер розміром 32 Кбайт, то можна працювати з даними об'ємом до 2 Гбайт. Аналогічно, 32-бітовий покажчик дозволяє адресувати з точністю до байта 4 Гбайт даних, тобто менше, ніж типовий сучасний жорсткий диск; але якщо перейти до адресації по блоках, то адресний простір виросте до 2 Тбайт, що вже сповна прийнятно для більшості сучасних пристроїв, що запам'ятовують.
Таким чином, адресація блоками і кластерами дозволяє використовувати в системних структурах даних короткі покажчики, що наводить до зменшення об'єму цих структур і до зниження накладних витрат. Під накладними витратами в даному випадку мається на увазі не лише звільнення дискового простору, але і прискорення доступу: структури меншого розміру швидше прочитуються, в них швидше виробляється пошук і так далі Проте збільшення об'єму кластера має оборотну сторону — воно наводить до внутрішньої фрагментації (див. разд. Алгоритми динамічного управління пам'яттю).
Ряд сучасних файлових систем використовує механізм, по-англійськи званий block siiballocation тобто розміщення частин блоків. У цих ФС кластери мають великий розмір, але є можливість розділити кластер на декілька блоків меншого розміру і записати в ці блоки "хвости" від декількох різних файлів (мал. 11.6). Це, безумовно, ускладнює ФС, але дозволяє одночасно використовувати переваги, властиві і великим, і маленьким блокам. Тому ряд поширених ФС, наприклад файлова система Novell Netware 4.1 і FFS (відома також як UFS і Berkley FS), використовувана в багатьох системах сімейства Unix, применяе цей механізм.

Мал. 11.6. Субаллокация блоків

Субаллокация вимагає від файлової системи підтримки запасу вільних блоків на випадок, якщо користувачеві потрібно буде збільшити довжину одного з файлів, "хвіст" якого був упакований у фрагментований блок. Навчальні посібники по Netware рекомендують підтримувати на томах з субаллокацией не менше тисячі вільних кластерів, але не надають штатних методів забезпечення цієї вимоги. Навпаки, UFS показує вільне місце на диску з врахуванням "недоторканного" резерву вільного простору, так що нульовий показуваний вільний простір відповідає 5% або 10% фізичного вільного місця. Об'єм цього резерву набудовується утилітами конфігурації ФС.
Але повернемося до простих файлових систем. У RT-11 кожному файлу виділяється безперервна область на диску. Завдяки цьому в каталозі досить зберігати адресу першого блоку файлу і його довжину, також виміряну в блоках. У RT-11 поступили ще простіше: порядок записів в каталозі збігається з порядком файлів на диску, і початком файлу вважається закінчення попереднього файлу. Вільним ділянкам диска теж відповідає запис в каталозі (мал. 11.7). При створенні файлу система шукає першу вільну ділянку відповідного розміру.
Фактично ця структура відрізняється від формату tar лише тим, що каталог винесений в початок диска, і існує поняття вільної ділянки усередині області даних. Ета проста організація має дуже серйозні недоліки.

1. 1. При створенні файлу програма повинна вказати його довжину. Часто це буває скрутно. Особливо незручно збільшувати розмір вже створеного файлу. Точніше, це просто неможливо: замість подовження старого файлу доводиться створювати новий файл потрібної довжини і копіювати вміст старого файлу в нього.
2. 2. При хаотичному створенні і видаленні файлів виникає проблема фрагментації вільного простору. Для її вирішення існує спеціальна програма SQUEESE (стискувати [диск]), яка переписує файли г так, щоб об'єднати всі вільні фрагменти (мал. 11.8). Ця програма вимагає багато часу, особливо для великих дискових томів, і потенційно небезпечна: якщо при її виконання станеться збій системи (а з машинами третього покоління таке траплялося по декілька раз на день), то значна частина даних буде необоротний зруйнована.

Мал. 11.7. Структура файлової системи RT-11

Мал. 11.8. Дефрагментація диска в RT-11

Для того, щоб вирішити обоє ці проблеми, необхідно дозволити файлам займати несуміжні області диска. Найбільш простим рішенням було бь зберігати в кінці кожного блоку файлу покажчик на наступний, тобто превра тить файл в зв'язаний список блоків (мал. 11.9). При цьому, природно в кожному блоці зберігати не 512 байт даних, а на 2 — 4 байти менше. При строго послідовному доступі до файлу таке рішення було б впотне прийнятним, але при спробах реалізувати довільний доступ виникнуть незручності. Можливо, тому, а може і по якихось причинах, що історично склалися, таке рішення не використовується ні в одній з відомих авторові ОС.

Мал. 11.9. Файл у вигляді одинзв'язного списку блоків

Частково схоже рішення було реалізоване в MS DOS і DR DOS. Ці системи створюють на диску таблицю, звану FAT (File Allocation Table, таблиця розміщення файлів). У цій таблиці кожному блоку, призначеному для зберігання даних, відповідає 12-бітове значення. Якщо блок вільний, то значення буде нульовим. Якщо ж блок належить файлу, то значення дорівнює адресі наступного блоку цього файлу. Якщо це останній блок у файлі, то значення — OXFFF (мал. 11.10). Існує також спеціальний код для позначення поганого (bad) блоку, що не читається із-за дефекту фізичного носія. У каталозі зберігається номер першого блоку і довжина файлу, вимірювана в байтах.
Ємкість диска при використанні 12-бітової FAT виявляється обмежена 4096 блоками (2 Мбайт), що прийнятно для дискет, але абсолютно не годиться для жорстких дисків і інших пристроїв великої ємкості. На таких пристроях DOS використовує FAT з 16-бітовими елементами. На ще більших (більше 32 Мбайт) дисках DOS виділяє простір не блоками. а кластерами з декількох блоків. Ета файлова система так і називається - FAT.
Вона дуже проста і має одну серйозну гідність: природжену стійкість до збоїв (fault tolerance) але про це далі. В той же час у неї є і ряд серйозних недоліків.

Мал. 11.10. Структура файлової системи FAT

Перший недолік полягає в тому, що при кожній операції над файлами система повинна звертатися до FAT. Це наводить до частих переміщень голівок дисковода і в результаті до різкого зниження продуктивності. Дійсно, виконання програми arj на одній і тій же машині під MS DOS і під DOS-эмулятором систем Unix або OS/2 розрізняється за швидкістю майже в 1,5 разу. Особливо це помітно при архівації великих каталогів.
Використання дискових кешів, а особливе приміщення FAT в оперативну пам'ять, істотно прискорює роботу, хоча зазвичай FAT кэшируется лише для читання ради стійкості до збоїв. При цьому ми стикаємося із специфічною проблемою: чим більше диск, тим більше у нього FAT, відповідно, тим більше потрібно пам'яті. Біля тому Novell Netware 3.12 розміром 1,115 Гбайт з розміром кластера 4 Кбайт розмір FAT досягає мегабайта (легко зрозуміти, що Netware використовує FAT з 32-розрядними елементами. При 16-розрядному елементі FAT дисковий том такого об'єму з таким розміром кластера просто неможливий). При монтуванні такого тому Netware займає під FAT і кеш каталогів близько 6 Мбайт пам'яті.
Для порівняння, Netware 4 використовує субаллокацию, тому можна відносно безкарно збільшувати об'єм кластера і немає необхідності робити кластер таким маленьким. Для дисків такого об'єму Netware 4 встановлює розмір кластера 16 Кбайт, що наводить до зменшення всіх структур даних в 4 рази. Зрозуміло, що для MS DOS, яка уміє адресувати всього 1 Мбайт (1088 Кбайт, якщо дозволений НМА), зберігати такий FAT в пам'яті цілком просто неможливо.
Розробники фірми MicroSoft пішли іншим шляхом: вони обмежили розрядність елементу FAT 16 бітами. При цьому розмір таблиці не може перевищувати 128 Кбайт, що сповна терпимо. Зате вся файлова система може бути розбита лише на 64 Кбайт блоків. У старих версіях MS DOS це наводило до неможливості створювати файлові системи розміром 32 Мбайт.
У версіях старше 3.11 з'явилася можливість об'єднувати блоки в кластери Наприклад, на дисках розміром від 32 до 64 Мбайт кластер складатиметься з 2 блоків і матиме розмір 1 Кбайт. На дисках розміром 128—265 Мбайт кластер буде вже розміром 4 Кбайта і так далі
Windows 95 використовує захищений режим процесора х86, тому адресний простір там значно більше одного мегабайта. Розробники фірми Microsoft вирішили скористатися цим і реалізували версію FAT з 32-бітовим елементом таблиці — так званий FAT32. Проте дисковий кеш Windows 95 не прагне утримати весь FAT в пам'яті; замість цього FAT кэшируется на загальних підставах, нарівні з призначеними для користувача даними. Оскільки робота з файлами великого (більше одного кластера) об'єму вимагає дослідження ланцюжка елементів FAT, а відповідні блоки таблиці можуть не потрапляти в кеш, то продуктивність різко падає. У супровідному файлі Microsoft визнає, що продуктивність FAT32 на операціях послідовного читання і запису може бути в півтора рази нижче, ніж біля кэшированного FAT 16.
На закінчення можна сказати, що при використанні FAT на великих дисках ми вимушені робити вибір між низькою продуктивністю, потребами в значному об'ємі оперативної пам'яті або великим розміром кластера, який наводить до істотних втрат із-за внутрішньої фрагментації.
Для ефективного управління великими об'ємами даних необхідне щось складніше, ніж FAT.