Фізична організація й адресація файлу
Важливим компонентом фізичної організації файлової системи є фізична організація файлу, тобто спосіб розміщення файлу на диску. Основними критеріями ефективності фізичної організації файлів є:
швидкість доступу до даних;
обсяг адресної інформації файлу;
ступінь фраґментування дискового простору;
максимально можливий розмір файлу.
Неперервне розміщення – найпростіший варіант фізичної організації (рис. 8, а), при якому файлу надається послідовність кластерів диску, що утворюють неперервну ділянку дискової пам’яті. Основним достоїнством цього методу є висока швидкість доступу, тому що витрати на пошук і зчитування кластерів файлу мінімальні. Також мінімальний обсяг адресної інформації – досить зберігати тільки номер першого кластера й обсяг файлу. Дана фізична організація максимально можливий розмір файлу не обмежує. Однак цей варіант має істотні недоліки, які утрудняють його застосовність на практиці, незважаючи на всю його логічну простоту. При більш пильному розгляді виявляється, що реалізувати цю схему не так вже й просто. Дійсно, якого розміру повинна бути неперервна область, виділювана файлу, якщо файл при кожній модифікації може збільшити свій розмір? Ще більш серйозною проблемою є фрагментація. Через деякий час після створення файлової системи в результаті виконання численних операцій створення й видалення файлів простір диска неминуче перетворюється в “клаптеву ковдру”, що включає велику кількість вільних областей невеликого розміру. Як завжди буває при фрагментації, сумарний обсяг вільної пам’яті може бути дуже великим, а вибрати місце для розміщення файлу майже неможливо. Тому на практиці використовуються методи, за якими файл розміщається в декількох, у загальному випадку несуміжних областях диска.
Рис. 8. Фізична організація файлу: - неперервне розміщення; б - зв’язаний список кластерів; в - зв’язаний список індексів; г - перелік номерів кластерів
Наступний спосіб фізичної організації – розміщення файлу у вигляді зв’язаного списку кластерів дискової пам’яті (рис. 8, б). При такому способі на початку кожного кластера міститься покажчик на наступний кластер. У цьому випадку адресна інформація мінімальна: розташування файлу може бути задано одним числом – номером першого кластера. На відміну від попереднього способу кожний кластер може бути приєднаний до ланцюжка кластерів якого-небудь файлу, отже, фрагментація на рівні кластерів відсутня. Файл може змінювати свій розмір під час свого існування, нарощуючи число кластерів. Недоліком є складність реалізації доступу до довільно заданого місця файлу – щоб прочитати п’ятий кластер файлу, необхідно послідовно прочитати чотири перших кластери, простежуючи ланцюжок номерів кластерів. Крім того, при цьому способі кількість даних файлу, що містяться в одному кластері, не дорівнює ступеню двійки (одне слово витрачене на номер наступного кластера), а багато програм читають дані кластерами, розмір яких дорівнює ступеню двійки.
Популярним способом, застосовуваним, наприклад, у файловій системі FAT, є використання зв’язаного списку індексів (рис. 8, в). Цей спосіб є деякою модифікацією попереднього. Файлу також виділяється пам’ять у вигляді зв’язаного списку кластерів. Номер першого кластера запам’ятовується в запису каталогу, де зберігаються характеристики цього файлу. Інша адресна інформація відділена від кластерів файлу. З кожним кластером диска зв’язується деякий елемент – індекс. Індекси розташовуються в окремій області диску – в MS-DOS це таблиця FAT (File Allocation Table), що займає один кластер. Коли пам’ять вільна, всі індекси мають нульове значення. Якщо деякий кластер N призначений деякому файлу, то індекс цього кластера стає рівним або номеру М наступного кластера даного файлу, або приймає спеціальне значення, що є ознакою того, що цей кластер є для файлу останнім. Індекс же попереднього кластера файлу приймає значення N, указуючи на новопризначений кластер.
При такій фізичній організації зберігаються всі достоїнства попереднього способу: мінімальність адресної інформації, відсутність фрагментації, відсутність проблем при зміні розміру. Крім того, даний спосіб має додаткові переваги. По-перше, для доступу до довільного кластеру файлу не потрібно послідовно зчитувати його кластери, досить прочитати тільки сектори диска, що містять таблицю індексів, відрахувати потрібну кількість кластерів файлу по ланцюжку і визначити номер потрібного кластера. По-друге, дані файлу заповнюють кластер повністю, і тому мають обсяг, рівний ступеню двійки.
Ще один спосіб завдання фізичного розташування файлу полягає в простому перерахуванні номерів кластерів, які займає цей файл (рис. 8, г). Цей перелік і служить адресою файлу. Недолік даного способу очевидний: довжина адреси залежить від розміру файлу і для великого файлу може скласти значну величину. Достоїнством же є висока швидкість доступу до довільного кластеру файлу, оскільки тут застосовується пряма адресація, що виключає перегляд ланцюжка покажчиків при пошуку адреси довільного кластеру файлу. Фрагментація на рівні кластерів у цьому способі також відсутня.
Останній підхід з деякими модифікаціями використовується в традиційних файлових системах ОС UNIX s5 і ufs. Для скорочення обсягу адресної інформації прямий спосіб адресації сполучається з непрямим.
У стандартній на сьогоднішній день для UNIX файловій системі ufs використовується наступна схема адресації кластерів файлу. Для зберігання адреси файлу виділено 15 полів, кожне з яких складається з 4 байт (рис. 9). Якщо розмір файлу менше або дорівнює 12 кластерам, то номери цих кластерів безпосередньо перераховуються в перших дванадцяти полях адреси. Якщо кластер має розмір 8 Кбайт (максимальний розмір кластера, підтримуваного в ufs), то в такий спосіб можна адресувати файл розміром до 8192·12=98304 байт.
Рис. 9. Схема адресації файлової системи ufs
Якщо розмір файлу перевищує 12 кластерів, то наступне 13-е поле містить адресу кластера, в якому можуть бути розташовані номери наступних кластерів файлу. Таким чином, 13-й елемент адреси використовується для непрямої адресації. При розмірі в 8 Кбайт кластер, на який указує 13-й елемент, може містити 2048 номерів наступних кластерів даних файлу і розмір файлу може зрости до 8192·(12+2048)=16875520 байт.
Якщо розмір файлу перевищує 12+2048=2060 кластерів, то використовується 14-е поле, у якому перебуває номер кластера, що містить 2048 номерів кластерів, кожний з яких зберігає 2048 номерів кластерів даних файлу. Тут застосовується вже подвійна непряма адресація. З її допомогою можна адресувати кластери у файлах, що містять до 8192·(12+2048+20482)=3,43766·1010 байт.
І нарешті, якщо файл включає більше 12+2048+20482=4196364 кластерів, то використовується останнє 15-е поле для потрійної непрямої адресації, що дозволяє задати адресу файлу, що має наступний максимальний розмір: 8192·(12+2048+20482+20483)=7,0403·l013 бaйт.
Таким чином, файлова система ufs при розмірі кластера в 8 Кбайт підтримує файли, що складаються максимум з 70 трильйонів байт даних, що зберігаються в 8 мільярдах кластерів. Для задання адресної інформації про максимально великий файл потрібно (див. рис. 27): 15 елементів по 4 байти (60 байт) у центральній частині адреси плюс 1+(1+2048)+(1+2048+20482)=4198403 кластери в непрямій частині адреси. Незважаючи на величезну величину, це число становить усього близько 0,05% від обсягу адресованих даних.
Файлова система ufs підтримує дискові кластери і менших розмірів, при цьому максимальний розмір файлу буде іншим. Використовувана в більш ранніх версіях UNIX файлова система s5 має аналогічну схему адресації, але вона розрахована на файли менших розмірів, тому в ній використовується 13 адресних елементів замість 15.
Метод перерахування адрес кластерів файлу задіяний і у файловій системі NTFS, яку використовує ОС Windows NT/2000. Тут він доповнений досить природним прийомом, що скорочує обсяг адресної інформації: адресуються не кластери файлу, а неперервні області, що складаються із суміжних кластерів диску. Кожна така область, яку називають відрізком (run), або екстентом (extent), описують за допомогою двох чисел: початкового номеру кластера і кількості кластерів у відрізку. Оскільки для скорочення часу операції обміну ОС намагається розмістити файл у послідовних кластерах диску, то у більшості випадків кількість послідовних областей файлу буде менше кількості кластерів файлу, і обсяг службової адресної інформації в NTFS скорочується порівняно із схемою адресації файлових систем ufs/s5.
Для того щоб коректно ухвалювати рішення щодо виділення файлу набору кластерів, файлова система повинна відслідковувати інформацію про стан усіх кластерів диску: вільний/зайнятий. Ця інформація може зберігатися як окремо від адресної інформації файлів, так і разом з нею.