Основні вимоги до фізичної організації файлових систем

З погляду користувача файл із заданим іменем (далі вважатимемо, що інформа­цію про шлях включено в ім'я) - це неструктурована послідовність байтів, а з по­гляду фізичної структури файлової системи, файл - це набір дискових блоків, що містять його дані. Завдання файлової системи полягає у забезпеченні перетво­рення сукупності імені файла і логічного зсуву в ньому на фізичну адресу сектора всере­дині відповідного дискового блоку, щоб драйвер контролеру диска міг його знайти на дисковій поверхні.

Необхідність такого перетворення визначає основне завдання файлової систе­ми -відстежувати розміщення вмісту файлів на диску. Інформація про розмі­щення даних файла на диску зберігається у структурі даних, що називають заго­ловком файла, або в спеціальній таблиці розміщення файлів. Такі заголовки звичайно зберігають на диску разом із файлами, а таблиці розміщення файлів - у спеціальних системних областях диска. Під час розробки структури даних для такого заголовка потрібно враховувати, що більшість файлів мають малий розмір, а основну частину дискового простору розподіляють, навпаки, під файли великого розміру, із якими переважно і вико­нують операції введення-виведення.

Оскільки продуктивність файлової системи залежить від кількості операцій доступу до диска, важливо максимально її обмежити. Кілька сотень таких опера­цій можуть додатково зайняти кілька секунд часу. На практиці слід враховувати, що всі імена файлів каталогу і всі блоки у файлі зазвичай викори­стовують разом, послідовно, тому вони повинні таким же чином розташовуватись на дисковій поверхні, тобто бути суміжними

Принципи, що лежать в основі фізичної організації файлової системи, визна­чають різні способи розміщення файлів на диску. Крім обліку розміщення даних, фізичне розміщення потребує також обліку вільних кластерів.

 

 

3.

Найпростіший підхід до фізичної організації файлових систем - це неперервне розмі­щення файлів. При цьому кожному файлові відповідає набір неперервно розта­шованих кластерів на диску (рис. 12.2). Для кожного файла мають зберігатися адре­са початкового кластера і розмір файла (start, len).

 

 

Зазначимо, що розподіл дискового простору в цьому разі подібний до дина­мічного розподілу пам'яті. Для пошуку вільного блоку кластерів на диску можна викори­стати алгоритми першого підходящого або найкращого підходящого блоку.

Неперервне розміщення файлів вирізняється простотою в реалізації та ефектив­ністю (наприклад, весь файл може бути зчитаний за одну операцію), але має іс­тотні недоліки.

Під час створення файла користувач має заздалегідь задати його максимальну довжину і виділити весь простір на диску за один раз. Збільшувати розміри файлів під час роботи не можна. У багатьох ситуаціях це абсолютно неприй­нятно (наприклад, неможливо вимагати від користувача текстового редактора щоб він вказував остаточну довжину файла перед його редагуванням).

· Вилучення файлів згодом може спричинити велику зовнішню фрагментацію дис­кового простору з тих самих причин, що й за динамічного розподілу пам'яті. У сучасних ОС для організації даних на жорстких дисках неперервне розмі­щення майже не використовують, проте його застосовують у таких файлових систе­мах, де можна заздалегідь передбачити, якого розміру буде файл. Прикладом є фай­лові системи для компакт-дисків. Вони мають кілька властивостей, що роблять неперервне розміщення файлів найкращим рішенням:

· записування такої файлової системи здійснюють повністю за один раз, під час записування для кожного файла заздалегідь відомий його розмір;

· доступ до файлових систем на компакт-диску здійснюють лише для читання, файли в них ніколи не розширюють і не вилучають, тому відсутні причини появи зовнішньої фрагментації.

 

 

4.

Прості зв'язні списки.

Іншим підходом є організація кластерів, що належать файлу, у зв'язний список. Кожен кластер файла містить інформацію про те, де перебуває наступний кластер цього файла (наприклад, його номер). Найпростіший приклад такого розміщення бачимо на рис. 12.3. Заголовок файла в цьому разі має містити посилання на його перший кластер, вільні кластери можуть бути організовані в аналогічний список.

 

 

Розміщення файлів з використанням зв'язних списків надає такі переваги:

· відсутність зовнішньої фрагментації (є тільки невелика внутрішня фрагмен­тація, пов'язана з тим, що розмір файла може не ділитися націло на розмір кластера);

· мінімум інформації, яка потрібна для зберігання у заголовку файла (тільки посилання на перший кластер);

· можливість динамічної зміни розміру файла;

· простота реалізації керування вільними блоками, яке принципово не відрізня­ється від керування розміщенням файлів. Цей підхід, однак, не позбавлений і серйозних недоліків:

· відсутність ефективної реалізації випадкового доступу до файла: для того щоб одержати доступ до кластера з номером n, потрібно прочитати всі кластери файла з номерами від 1 до n-1;

· зниження продуктивності тих застосувань, які зчитують дані блоками, за роз­міром рівними степеню числа 2 (а таких застосувань досить багато): частина будь-якого кластера повинна містити номер наступного, тому корисна інфор­мація в кластері займає обсяг, не кратний його розміру (цей обсяг навіть не є степенем числа 2);

· можливість втрати інформації у послідовності кластерів: якщо внаслідок збою буде втрачено кластер на початку файла, вся інформація в кластерах, що йдуть за ним, також буде втрачена.

Є модифікації цієї схеми, які зберегли своє значення дотепер, найважливішою

з них є використання таблиці розміщення файлів.