Для контролю вільного простору на диску MS-DOS веде спеціальну таблицю - таблицю розміщення файлів (File Allocation Table ‑ FAT). Одиницею виміру простору на диску є кластер ‑ група підряд розташованих секторів. Число секторів у кластері залежить від формату диску. Наприклад, для диску форматом 360К байт кластер включає два сектори. Для дисків 20М байт один кластер складається з 8 секторів по 512 байт. Кожний кластер диску має унікальний номер.
Таблиця FAT використовується MS-DOS для пошуку файлу на диску, а також відведення і звільнення кластерів. В залежності від формату диску FAT складається або з 12-бітових (1.5 байта), або 16-битовых елементів (2 байта). Кожному кластеру диску відповідає один елемент FAT. Значення, записане в елементі FAT, інтерпретується MS-DOS наступним чином (в дужках приводиться додаткова цифра для 16-битовых FAT):
(0)000 |
кластер вільний і раніше не використовуватися для зберігання файлів; |
Від (F)FF8 до (F)FFF |
Кластер є останнім в файлі, та є індикатором кінця ланцюжка кластерів ЕОС (ЕОС - End Of Chain); |
(F)FF7 |
Кластер дефектний; |
(Х)ХХХ |
Будь-які шістнадцятирічні цифри, що задають номер наступного кластера в ланцюжку кластерів файлу. |
При запиті нового кластера (створенні регулярного файлу або директорія, поповненні файлу новим вмістом) MS-DOS завжди виділяє цілий кластер. Якщо це перший кластер файлу, його номер заноситься в елемент директорія, відповідний файлу. Наступні кластери файлу, якщо він "росте", можуть розташуватися в будь-якому місці диску. Для того щоб відшукати всі кластери одного файлу, використовується однозв’язний список.
Номери кластерів |
000 |
001 |
002 |
003 |
004 |
005 |
006 |
007 |
008 |
009 |
010 |
011 |
012 |
013 |
014 |
. . . |
FAT |
Не використовуються |
EOC |
013 |
002 |
009 |
008 |
FF7 |
004 |
012 |
003 |
000 |
EOC |
EOC |
000 |
. . . |
Мал. 6. Структура таблиці розміщення файлів FAT
Сукупність зв’язних списків кластерів всіх файлів диску і утворює FAT. Друге призначення FAT – контроль вільного простору на диску. Приклад використання FAT для пошуку файлів наведений вище (Мал. 6).
У даному фрагменті FAT кластери 11 та 14 - вільні, кластер 7 - дефектний. Дефектні кластери виявляються під час форматування диску. Їхні номери заносяться у FAT, і вони не використовуються для розміщення інформації. Розглянемо, наприклад, як по FAT MS-DOS відшукує кластери файлу А. Спочатку, по маршруту файлу відшукується директорій, у якому файл А зареєстрований. По імені файлу серед елементів директорія відшукується елемент відповідний файлу А, після чого з байтів 26-27 цього елементу директорія вибирається номер першого кластера файлу А. Якщо потрібен наступний кластер файлу A, MS-DOS звертається до таблиці FAT. По номеру першого кластера файлу MS-DOS обчислює зміщення в таблиці FAT і зчитує елемент. Наприклад, для файлу А цей елемент (елемент FAT, відповідний кластеру 6) містить число 008. Це означає, що кластер 6 - не останній кластер файлу А і наступним в ланцюжку є кластер 8. Для цього номера кластера знов обчислюється зміщення в FAT і зчитується елемент, відповідний кластеру 8. Цей процес триває до тих пір, доки не зустрінеться елемент FAT, в який записаний символ ЕОС (FF8 - FFF). Кластер, відповідний такому елементу, є останнім кластером файлу.
При відведенні нових кластерів MS-DOS обирає перший вільний кластер і приєднує його до вже існуючого ланцюжка. Якщо кластери у ланцюжку мають послідовно зростаючі номери, тоді доступ до файлу буде відбуватися максимально швидко, бо або зовсім непотрібно виконувати операцію встановлення голівок (установка голівок на заданий циліндр та доріжку), або встановлення буде йти на послідовно зростаючі циліндри. Операція встановлення головок - надто повільна (від одиниць до декількох десятків мілісекунд). Якщо кластери в ланцюжку будуть мати номери що відрізняються більш ніж на 1, час "перебору" ланцюжка збільшиться. Такі файли називають фрагментованими. Якщо диск використовується достатньо довго і виконуються операції створення, поповнення вмісту і знищення файлів, такий диск рано або пізно фрагментується. Для усунення фрагментації файлів диску використовуються спеціальні програмні засоби. Їхня мета ‑ перемістити кластери фрагментованих файлів в кластери з послідовно зростаючими номерами.
Незалежно від розміру файлу завжди виділяється ціле число кластерів, тому диск використовується не повністю.
Вибір розміру кластера - суперечлива задача. З одного боку, чим менше розмір кластеру, тим вище коефіцієнт корисного використання диску. Але, з іншого боку, чим більше кластерів на диску, тим більша FAT і, отже, уповільнюється процес її сканування. Додаткові труднощі виникають із-за появи дисків великого обсягу (сотні мегабайт). Цим і пояснюється поява FAT з 16-битовыми елементами. Справа в тому, що 12 бітовому елементу FAT дозволяють пронумерувати тільки 4096 кластерів. Але тоді для диску обсягом 128М байт прийдеться робити кластери розміром по 32К байти для того, щоб мати доступ до всього простору диску. А для дисків, 128 - 256М байт цей розмір буде рівний 64К байт. Однак чим більше розмір кластера, тим нижче коефіцієнт корисного використання диску. Середній розмір файлу по матеріалам досліджень схожої з MS-DOS файлової системи ОС UNIX не перевищує 1К байт. Раз так, те, наприклад, для кластеру розміром 32К байт коефіцієнт корисного використання диску буде рівний 1/32 - не перевищить й 4%! Зменшивши розмір кластеру, ми неминуче збільшимо загальне число кластерів, і для їхньої нумерації будуть потрібні додаткові біти в елементі FAT. Так, 16-бітова FAT дозволяє пронумерувати вже 216, або 64К кластерів. В результаті навіть для диску загальним об’ємом 256М байт можна задати кластер розміром 2, або 4К байт. Такий розмір кластера дозволяє довести коефіцієнт корисного використання диску приблизно до 25%. Щоправда, при цьому збільшується обсяг FAT.
Виходячи з наведених міркувань, для користувача можна зробити принаймні три висновки:
1) файли на диску по можливості не повинні бути занадто короткими. Довжина файлу у ідеальному випадку повинна бути кратна довжині кластеру;
2) надто "гілляста" й глибока ієрархія директорій на диску нераціонально використовує дисковий простір. На кожний створений директорій буде резервуватися, як мінімум, один кластер. Але директорій рідко буває таким великим, щоб повністю використати навіть один кластер. Наприклад, для диску форматом 360К байт розмір кластеру рівного двом секторам по 512 байт. Це дозволяє зареєструвати в однокластерному директорії не менше 128 файлів (два елементи субдиректорію зарезервовані для "." та "..", і тому доступне для користувача число файлів дорівнює 126);
3) фрагментація файлів уповільнює доступ до них за рахунок додаткових операцій встановлення голівок. Для усунення фрагментації використовують спеціальні утиліти або просто копіюють файли на знову відформатований носій командою COPY (команда DISKCOPY зберігає наявну фрагментацію файлів).
![]() |
![]() |
![]() |