Зв'язний список за допомогою таблиці в пам'яті

Обидва недоліки попередньої схеми організації файлів у вигляді зв'язних списків можуть бути усунені, якщо покажчики на наступні блоки зберігати не прямо в блоках, а в окремій таблиці, що завантажується в пам'ять. На мал. 6.11 показаний зовнішній вигляд такої таблиці для файлів з мал. 6.10. На обох малюнках показано два файли. Файл А використовує блоки диска 4, 7, 2,10 і 12, а файл В використовує блоки диска 6, 3,11 і 14. За допомогою таблиці, показаної на мал. 6.11, ми можемо почати з блоку 4 і слідувати по ланцюжку до кінця файлу. Те ж може бути зроблене для другого файлу, якщо почати з блоку 6. Обидва ланцюжки завершуються спеціальним маркером (наприклад - 1), що не є допустимим номером блоку. Така таблиця, що загружається в оперативну пам'ять, називається FAT – таблицею (File Allocation Table - таблиця розміщення файлів).

Фізичний блок

Мал. 6.11. Таблиця розміщення файлів

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

Основний недолік цього методу полягає в тому, що уся таблиця повинна постійно знаходитися в пам'яті. Для 20-гігабайтного диска з блоками розміром 1 Кбайт було б потрібно таблицю з 20 млн записів, по одній для кожного з 20 млн блоків диска. Кожен запис повинен складатися як мінімум з трьох байтів. Для прискорення пошуку розмір записів має бути збільшений до 4 байт. Таким чином, таблиця постійно займатиме 60 або 80 Мбайт оперативної пам'яті. Таблиця, звичайно, може бути розміщена у віртуальній пам'яті, але і в цьому випадку її розмір виявляється надмірно великим, до того ж постійне вивантаження таблиці на диск і завантаження з диска істотно понизить продуктивність файлових операцій.

I-вузли

Останній метод відстежування приналежності блоків диска файлам полягає в зв'язуванні з кожним файлом структури даних, званої i-вузлом (index node - індекс-вузол), що містить атрибути файлу і адреси блоків файлу. Простий приклад і-вузла показаний на мал. 6.12. За наявності і-вузла можна знайти усі блоки файлу. Велика перевага такої схеми перед таблицею, що зберігається в пам'яті, із зв'язних списків полягає в тому, що кожен конкретний 1-вузол повинен знаходитися в пам'яті тільки тоді, коли відповідний йому файл відкритий. Якщо кожен і-вузол займає n байт, а одночасно відкрито може бути до k файлів, то для масиву i-вузлів буде потрібно в пам'яті усього kn байтів.

Мал. 6.12. Приклад і-вузла

Зазвичай цей розмір значно менший, ніж FAT-таблиця, описана в попередньому розділі. Це легко пояснюється. Розмір таблиці, що зберігає зв'язний список усіх блоків диска, пропорційний розміру самого диска. Для диска з n блоків буде потрібно n записів в таблиці. Таким чином, розмір таблиці лінійно росте із зростанням розміру диска. Для схеми i-вузлів, навпаки, потрібно масив в пам'яті розміром, пропорційним максимальній кількості файлів, які можуть бути відкриті одночасно. При цьому не важливо, чи буде розмір диска 1 Гбайт, 10 Гбайт або 100 Гбайт.

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

Реалізація каталогів

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

З цією проблемою тісно пов'язано питання розміщення атрибутів файлу. Кожна файлова система підтримує різні атрибути файлу, такі як дату створення файлу, ім'я власника файлу і т. д., і усю цю інформацію треба десь зберігати. Один з можливих варіантів полягає в зберіганні цих відомостей прямо в каталоговому записі. Багато файлових систем саме так і поступають. Цей варіант показаний на мал. 6.13, а. У цій простій схемі каталог складається із списку елементів фіксованої довжини по одному на файл, файлів, що містять імена, структуру атрибутів файлу, а також один або декілька дискових адрес, що вказують на розташування файлу на диску.

Мал. 6.13. Простий каталог, що містить записи фіксованої довжини з атрибутами і дисковими адресами (а); каталог, в якому кожен запис являється просто посиланням на i-вузол (б)

Системи, що використовують i-вузли, можуть зберігати атрибути в і-вузлах, а не в записах каталогу. В цьому випадку запис в каталозі може бути коротше: просто ім'я файлу і номер і-вузла. Цей підхід показаний на мал. 6.13, б. Як ми побачимо пізніше, у цього методу є певні переваги в порівнянні з поміщенням атрибутів прямо в каталоговий запис. Два підходи, показані на мал. 6.13, відповідають системам MS - DOS і UNIX, про що ще буде розказано в цій главі.

Досі ми припускали, що файли мають короткі імена фіксованої довжини. У системі MS - DOS файл може мати ім'я завдовжки від 1 до 8 символів, а також розширення завдовжки до 3 символів. У системі UNIX Version 7 імен файлів можуть бути від одного до 14 символів, включаючи розширення. Проте майже усіма сучасними операційними системами підтримуються довші імена файлів змінної довжини. Як це може бути реалізовано?

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

Один з альтернативних підходів полягає у відмові від припущення про те, що усі записи в каталозі повинні мати один і той же розмір. При такому підході кожен запис в каталозі починається з порції фіксованого розміру, запису, що зазвичай починається з довжини, за яким йдуть дані у фіксованому форматі - ідентифікатор власника, дата створення, інформація про захист і інші атрибути. Слідом за заголовком фіксованої довжини йде частина запису перемінної довжини, що містить ім'я файлу (мал. 6.14, а). На малюнку показано три описувачі файлу, project - budget, personnel і fоо. Ім'я кожного файлу завершується спеціальним символом (зазвичай 0), позначеним на малюнку перекресленими квадратиками. Щоб кожен запис в каталозі міг починатися з межі слова, ім'я кожного файлу доповнюється до цілого числа слів байтами, показаними на малюнку затіненими прямокутниками.

Мал. 6.14. Два варіанти реалізації довгих імен : прямо в записі каталогу (а); у "купі" (б)

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

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

У всіх розглянутих нами досі схемах при пошуку файлу каталоги переглядаються лінійно зверху вниз. Для дуже великих каталогів, що містять багато тисяч файлів, такий пошук може зайняти досить багато часу. Один із способів прискорити пошук файлу полягає у використанні хеш-таблиці в кожному каталозі. Нехай розмір такої таблиці дорівнюватиме n. При додаванні в каталог нового файлу його ім'я повинне хешуватись в число від 0 до n-1. Як хеш-функції можуть використовуватися, наприклад, узяття залишку від ділення імені файлу на n. Як альтернатива можна ділити не саме ім'я, а суму слів, що його утворюють. Можливі і інші варіанти.

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

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

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

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