Зв'язний список

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

Рис. 14.2. Зберігання файлу у вигляді зв'язного списку дискових блоків

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

Зв'язне виділення має, проте, декілька істотних недоліків.

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

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

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

Тому метод зв'язного списку зазвичай в чистому вигляді не використовується.

Таблиця відображення файлів

Одним з варіантів попереднього способу є зберігання покажчиків не в дискових блоках, а в індексній таблиці в пам'яті, яка називається таблицею відображення файлів (FAT - file allocation table) (див. мал. 12.3). Цієї схеми дотримуються багато ОС (MS-DOS, OS/2, MS Windows і ін.)

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

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

Рис. 14.3. Метод зв'язного списку з використанням таблиці в оперативній пам'яті