с. 4. Фізична організація файлу: безперервне розміщення (а); зв'язаний список кластерів (б); зв'язаний список індексів (в); перелік номерів кластерів (г)
Наступний спосіб фізичної організації - розміщення файлу у вигляді зв'язаного списку кластерів дискової пам'яті (рис. 7.11, б). При такому способі на початку кожного кластера міститься покажчик на наступний кластер. У цьому випадку адресна інформація мінімальна: розташування файлу може бути задане одним числом - номером першого кластеру. На відміну від попереднього способу кожен кластер може бути приєднаний до ланцюжка кластерів якого файлу, отже, фрагментація на рівні кластерів відсутня. Файл може змінювати свій розмір під час свого існування, нарощуючи число кластерів. Недоліком є ​​складність реалізації доступу до довільно заданого місця файлу - щоб прочитати п'ятий по порядку кластер файлу, необхідно послідовно прочитати чотири перших кластера, простежуючи ланцюжок номерів кластерів. Крім того, при цьому способі кількість даних файлу, що містяться в одному кластері, не дорівнює ступеню двійки (Одне слово витрачено на номер наступного кластера), а багато програми читають дані кластерами, розмір яких дорівнює ступеня двійки.
Популярним способом, застосовуваним, наприклад, у файловій системі FAT, є використання зв'язаного списку індексів (Рис. 4, б). Цей спосіб є деякою модифікацією попереднього. Файлу також виділяється пам'ять у вигляді зв'язаного списку кластерів. Номер першого кластера запам'ятовується в записі каталогу, де зберігаються характеристики цього файлу. Решта адресна інформація відділена від кластерів файлу. З кожним кластером диска зв'язується деякий елемент - індекс. Індекси розташовуються в окремої області диска - в MS-DOS це таблиця FAT (File Allocation Table), що займає один кластер. Коли пам'ять вільна, всі індекси мають нульове значення. Якщо певний кластер N призначений деякому файлу, то індекс цього кластеру стає рівним або номером М наступного кластера даного файлу, або приймає спеціальна значення, що є ознакою того, що цей кластер є для файлу останнім. Індекс же попереднього кластера файлу приймає значення N, вказуючи на новопризначений кластер.
При такій фізичної організації зберігаються всі достоїнства попереднього способу: мінімальність адресної інформації, відсутність фрагментації, відсутність проблем при зміні розміру. Крім того, даний спосіб володіє додатковими перевагами. По-перше, для доступу до довільного кластеру файлу не потрібно послідовно зчитувати його кластери, досить прочитати тільки сектори диска, які містять таблицю індексів, відрахувати потрібну кількість кластерів файлу по ланцюжку і визначити номер потрібного кластеру. По-друге, дані файлу заповнюють кластер цілком, а значить, мають об'єм, рівний ступеня двійки.
ПРИМІТКА
Необхідно відзначити, що за відсутності фрагментації на рівні кластерів на диску все одно мається певну кількість областей пам'яті невеликого розміру, які неможливо використовувати, тобто фрагментація все ж існує. Ці фрагменти являють собою невикористовувані частини останніх кластерів, призначених файлів, оскільки обсяг файлу в загальному випадку не кратний розміру кластера. На кожному файлі в середньому втрачається половина кластеру. Це втрати особливо великі, коли на диску є велика кількість маленьких файлів, а кластер має великий розмір. Розміри кластерів залежать від розміру розділу і типу файлової системи Приблизний діапазон, в якому може змінюватися розмір кластера, становить від 512 байт до десятків кілобайт.
Ще один спосіб завдання фізичного розташування файлу полягає в простому перерахуванні номерів кластерів, займаних цим файлом (рис. 4, г). Цей перелік і служить адресою файлу. Недолік даного способу очевидна: довжина адреси залежить від розміру файлу і для великого файлу може скласти значну величину. Перевагою ж є висока швидкість доступу до довільного кластеру файлу, так як тут застосовується пряма адресація, яка виключає перегляд ланцюжка покажчиків при пошуку адреси довільного кластера файлу. Фрагментація на рівні кластерів у цьому способі також відсутня.
Останній підхід з деякими модифікаціями використовується в традиційних файлових системах ОС UNIX s5 і ufs. Для скорочення обсягу адресної інформації прямий спосіб адресації поєднується з непрямим.
У стандартній на сьогоднішній день для UNIX файлової системи ufs використовується наступна схема адресації кластерів файлу. Для зберігання адреси файлу виділено 15 полів, кожне з яких складається з 4 байт (рис. 5). Якщо розмір файлу менше або дорівнює 12 кластерам, то номери цих кластерів безпосередньо перераховуються в перших дванадцяти полях адреси. Якщо кластер має розмір 8 Кбайт (максимальний розмір кластера, підтримуваного в ufs), то таким чином можна адресувати файл розміром до 8192x12 = 98304 байт. br/>В
Рис. 5. Схема адресації файлової системи ufs
...
