Зв’язні списки з таблицею розміщення файлів
Прості зв’язні списки
Розміщення файлів зв’язними списками
Іншим підходом є організація кластерів, що належать файлу, у зв’язний список. Кожен кластер файла містить інформацію про те, де перебуває наступний кластер цього файла. Найпростіший приклад такого розміщення бачимо на рис 1.2. Заголовок файла в цьому разі має містити посилання на його перший кластер, вільні кластери можуть бути організовані в аналогічний список.
Розміщення файлів з використанням зв’язних списків надає такі переваги:
· Відсутність зовнішньої фрагментації ( є тільки невелика внутрішня фрагментація, пов’язана з тим, що розмір файла може не ділитися націло на розмір кластера)
· Мінімум інформації, яка потрібна для зберігання у заголовку файла (n – посилання на перший кластер)
· Можливість динамічної зміни розміру файла.
· Простота реалізації керування вільними блоками, яке принципово не відрізняється від керування розміщенням файлів.
Цей підхід, однак, не позбавлений і серйозних недоліків:
· Відсутність ефективної реалізації випадкового доступу до файла: для того щоб одержати доступ до кластера з номером n, потрібно прочитати всі кластери файла з номерами від 1 до n-1.
· Зниження продуктивності тих застосувань, які зчитують дані блоками, за розміром рівними степеню числа 2: частина будь-якого кластера повинна містити номер наступного, тому корисна інформація в кластері займає обсяг, не кратний його розміру.
· Можливість втрати інформації у послідовності кластерів: якщо внаслідок збою буде втрачено кластер на початку файла, вся інформація в кластерах, що йдуть за ним, також буде втрачена.
Є модифікації цієї схеми, які зберегли своє значення дотепер, найважливішою з них є використання таблиці розміщення файлів.
Цей піді (рис 1.3) полягає в тому, що всі посилання, які формують списки кластерів файла, зберігаються в окремій ділянці файлової системи фіксованого розміру, формуючи таблицю розміщення файлів. Елемент такої таблиці відповідає кластеру на диску і може містити:
· Номер наступного кластера, якщо цей кластер належить файлу і не є його останнім кластером.
· Індикатор кінця файла, якщо цей кластер є останнім кластером файла.
· Індикатор, який показує, що цей кластер вільний.
Для організації файла достатньо помістити у відповідний йому елемент каталогу номер першого кластера файла. За необхідності прочитати файл система знаходить за цим номером кластера відповідний елемент FAT, зчитує з нього інформацію про наступний кластер ітд… Цей процес триває доти, поки не трапиться індикатор кінця файла.
Використання цього підходу дає змогу підвищити ефективність і надійність розміщення файлів зв’язними списками. Це досягається завдяки тому, що розміри FAT дозволяють керувати її в пам’яті. Зазначимо, що навіть якщо таке кешування не реалізоване, випадковий доступ до файла не призводитиме до читання всіх попередніх його кластерів – зчитані будуть тільки передні елементи FAT.
Крім того, спрощується захист від збоїв. Для цього, наприклад, можна зберігати на диску додаткову копію FAT, що автоматично синхронізуватиметься з основною. У разі ушкодження однієї з копій інформація може бути відновлена з іншої.
І нарешті, службову інформацію більше не зберігають безпосередньо у кластерах файла, вивільняючи в них місце для даних. Тепер обсяг корисних даних всередині кластера майже завжди дорівнюватиме степеню числа 2.
Однак, у разі такого способу розміщення файлів для розділів великого розміру, обсяг FAT може стати доволі великим і її кешування може потребувати значних витрат памяті. Скоротити розмір таблиці можна, збільшивши розмір кластера, але це, в свою чергу, призводить до збільшення внутрішньої фрагментації для малих файлів.
Також руйнування обох копій FAT, робить відновлення даних дуже складною задачею, яку не завжди можна розв’язати.
Базовою ідеєю ще одного підходу до розміщення файлів є перелік адрес всіх кластерів файла в його заголовку. Такий заголовок файла дістав назву індексного дескриптора, або і-вузла, а сам підхід – індексованого розміщення файлів.
За індексованого розміщення із кожним файлом пов’язують його індексний дескриптор. Він містить масив із адресами (або номерами) усіх кластерів цього файла, при цьому n-й елемент масиву відповідає n-му кластеру. Індексні дескриптори зберігають окремо від даних файла, для цього звичайно виділяють на початку розділу спеціальну ділянку індексних дескрипторів. В елементі каталогу розміщують номер індексного дескриптора відповідного файла. (рис 1.4)
Під час створення файла на диску розміщують його індексний дескриптор у якому всі покажчики на кластери спочатку є порожніми. Під час першого записування в n-й кластер файла менеджер вільного простору виділяє вільний кластер і його номер або адресу заносять у відповідний елемент масиву.
Цей підхід стійкий до зовнішньої фрагментації й ефективно підтримує як послідовний, так і випадковий доступ. Для підвищення ефективності індексний дескриптор повністю завантажують у пам’ять, коли процес починає працювати з файлом, і залишають у пам’яті доти, поки ця робота триває.
