Операционная система MS-DOS

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

Сразу после загрузочного сектора на логическом диске находятся сектора, содержащие таблицу размещения файлов FAT (File Allocation Table). В отечественной литературе иногда можно встретить аббревиатуру ТРФ, однако мы будем пользоваться общепринятым сокращением - FAT.

Для того, чтобы назначение этой таблицы стало более понятным, вспомним, как организовано хранение информации на различных носителях данных.

Магнитные ленты. Этот вид носителей информации использовался еще в самых первых ЭВМ. В современных компьютерах магнитные ленты используются для разгрузки магнитных дисков.

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

Если вы попытаетесь перезаписать файл, то это может привести к потере всех файлов, расположенных на магнитной ленте после перезаписываемого.

Доступ к информации, записанной на магнитном диске, может выполняться либо последовательным, либо прямым методом доступа. Использование прямого метода доступа позволяет позиционировать головки сразу на тот файл, который вам нужен (или на нужную запись файла). Например, вы можете задать номер сектора на оперделенной дорожке и номер головки.

Но метод доступа - это еще не все. Важное значение имеет способ распределения места на диске для файлов. От правильного выбора способа распределения зависит эффективность работы программ.

Операционная система ОС ЕС для ЭВМ ряда ЕС позволяет задать начальное количество цилиндров диска для размещения набора данных и размер области диска, которая может быть использована для этого набора дополнительно. Если при записи в файл все распределенное для файла место на диске окажется исчерпанным, программа завершится аварийно, даже если на диске еще есть свободные цилиндры.

Операционные системы, подобные DOS, UNIX, OS/2 используют дисковое пространство другим способом.

В этих операционных системах при создании файла для него не задается начальное распределение памяти в дорожках или секторах. По мере того, как файл увеличивается в размерах, операционная система распределяет этому файлу сектора из числа свободных, не используемых другими файлами. При этом файл располагается не обязательно в смежных областях диска, он может быть разбросан по разным дорожкам и секторам.

Очевидно, что в этом случае операционная система должна вести учет используемых участков диска. Для каждого файла она должна хранить где-то информацию о том, какому файлу какие участки диска распределены.

В операционной системе MS-DOS для хранения этой информации используется таблица размещения файлов.

Весь диск разбивается операционной системой на участки одинакового размера, называемые кластерами. Кластер может содержать несколько секторов. Для каждого кластера FAT имеет свою индивидуальную ячейку, в которой хранится информация об использовании данного кластера. Другими словами, таблица размещения файлов - это массив, содержащий информацию о кластерах. Размер этого массива определяется общим количеством кластеров на логическом диске. (Именно кластеров, а не секторов!).

Что же хранится в таблице размещения файлов?

Все свободные кластеры помечены в ней нулями. Если файл занимает несколько кластеров, то эти кластеры связаны в список. Для связанных в список кластеров элементы таблицы FAT содержат номера следующих используемых данным файлом кластеров. Конец списка отмечен в таблице специальным значением. Номер первого кластера, распределенного файлу, хранится в элементе каталога, описывающего данный файл.

Утилиты операционной системы и некоторые специальные утилиты проверяют диск на предмет наличия дефектных областей. Кластеры, которые находятся в этих дефектных областях, отмечаются в FAT как плохие и не используются операционной системой.

Итак, FAT - массив информации об использовании кластеров диска, содержит односвязные списки кластеров, распределенных файлам. Номера начальных кластеров файлов хранятся в каталогах, о которых мы будем говорит в разделе "Файлы и каталоги". Прежде чем углубляться в тонкости таблицы размещения файлов, приведем рисунок, иллюстрирующий сказанное выше.

                                         +­­­­­+
+­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­+ ¦
¦AUTOEXECBAT¦ ... ¦Номер 1-го кластера: 11¦..¦ ¦
+­­­­­­­­­­­+­­­­­+­­­­­­­­­­­­­­­­­­­­­­­+­­¦ ¦
¦CONFIG  SYS¦ ... ¦Номер 1-го кластера: 27¦..¦ ¦
+­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­+ ¦
                                         ¦     ¦
                                         ¦     ¦
                                         +­­­­­+­­­­­­+
     +­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­+      ¦
+­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­+   ¦
¦...¦12¦13¦14¦15¦16¦17¦18¦19¦20¦FF¦ 0¦ 0¦ 0¦ 0¦...¦   ¦
+­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­+   ¦
+­­­­­­­­­­­­­­­­­­­+                                 ¦
¦...¦28¦29¦30¦FF¦...¦                                 ¦
+­­­­­­­­­­­­­­­­­­­+                                 ¦
     +­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­+

На этом рисунке показаны фрагменты корневого каталога диска С: и элементы FAT для файлов autoexec.bat и config.sys. Реально эти файлы не используют столько кластеров. Из рисунка видно, что в каталоге для файлов указаны номера первых кластеров (соответственно 11 и 27). Таблица FAT в одиннадцатой ячейке содержит число 12 - номер следующего кластера, распределенного файлу autoexec.bat. Ячейка с номером 12 содержит число 13, и так далее. Последняя ячейка, соответствующая последнему кластеру распределенному этому файлу, содержит специальное значение - FF. В этом примере все кластеры файлов расположены подряд, но это может быть и не так.

Существуют два формата FAT - 12-битовый и 16-битовый. Эти форматы используют, соответственно, 12 и 16 битов для хранения информации об одном кластере диска.

12-битовый формат удобен для дискет с небольшим количеством секторов - вся таблица размещения файлов помещается целиком в одном секторе. Если размер диска такой, что для представления всех секторов двенадцати разрядов недостаточно, можно увеличить размер кластера, например до восьми секторов. Однако большой размер кластера приводит к неэффективному использованию дискового пространства. Это происходит из-за того, что минимальный выделяемый файлу элемент - кластер - имеет слишком большой размер. Даже для файла, имеющего длину 1 байт выделяется целиком кластер. Значит, если размер кластера составляет 8 секторов, то для хранения одного байта будет использовано 4 килобайта дисковой памяти.

При использовании FAT 16-битового формата операционная система может работать с диском, который имеет размер более 32 мегабайт. DOS версии 4.0 при использовании 16-битового формата FAT и кластеров размером 4 сектора может работать с разделами, по размеру достигающими 134 мегабайтов.

Как программа может определить формат FAT?

Для DOS версии 3.0 16-битовый формат используется, если размер диска превышает 4086 кластеров. Это число получилось исходя из того, что в 12 разрядах может быть представлено максимальное число 4096, кроме того, значения, большие 0ff6, зарезервированы.

Для DOS версии 3.2 16-битовый формат FAT используется в том случае, когда размер диска превышает 20790 секторов (именно секторов, а не кластеров). Фактически это означает, что 16-битовый формат используется только для дисков, имеющих размер более 10 мегабайтов.

Сектор загрузочной записи (BOOT-сектор) диска, отформатированного в DOS версии 4.0 в поле со смещением 36h содержит восьмибайтовую строку, идентифицирующую формат FAT. Она имеет вид "FAT12 " или "FAT16 ". Вы можете использовать это поле для определения формата FAT. В структуре BOOT, описанной в файле sysp.h, это поле называетcя fat_format.

Если разделы на жестком диске создавались утилитой DOS FDISK, формат FAT можно определить, анализируя содержимое поля sys главной загрузочной записи (Master Boot Record). Если это поле содержит значение 1, используется 12-битовый формат, если 4 - 16-битовый. Однако диск, подготовленный программами диск-менеджеров, может иметь нестандартный для DOS формат таблицы разделов диска (Partition Table), и поле sys может содержать другие величины, отличные от 1 и 4.

Опишем подробно формат FAT.

Первый байт FAT называется "Описатель среды" (Media Descriptor) или байт ID идентификации FAT. Он имеет такое же значение, как и байт-описатель среды, находящийся в BOOT-секторе логического диска.

Следующие 5 байтов для 12-битового формата или 7 байтов для 16-битового формат всегда содержат значение 0ffh.

Остальная часть FAT состоит из 12-битовых или 16-битовых ячеек, каждая ячейка соответствует одному кластеру диска. Эти ячейки могут содержать следующие значения:

Непосредственный доступ к FAT может потребоваться вам для организации сканирования каталогов для поиска нужных файлов, для чтения каталогов как файлов, для организации защиты информации от несанкционированного копирования. Общая схема использования FAT такая:

• Читаем FAT целиком в память. Обычно FAT располагается сразу после BOOT-сектора (логический сектор с номером 1). Для точного определения начального сектора FAT следует прочитать в память BOOT-сектор и проанализировать содержимое блока параметров BIOS. В поле ressecs записано количество зарезервированных секторов, которые располагаются перед FAT. Поле fatsize содержит размер FAT в секторах. Кроме того, следует учитывать, что на диске может находиться несколько копий FAT. Операционная система использует только первую копию, остальные нужны для утилит восстановления содержимого диска, таких как CHKDSK. Количество копий FAT находится в поле fatcnt BOOT-сектора.
• Затем необходимо узнать номер первого кластера файла, для которого необходимо определить его расположение на диске.
• Используем номер первого кластера как индекс в FAT для извлечения номера следующего кластера.
• Повторяем предыдущую процедуру до тех пор, пока извлеченное из FAT значение не будет соответствовать концу файла.

Процедура извлечения номера кластера из FAT зависит от формата таблицы размещения файлов.

16-битовую FAT можно представить как массив 16-битовых чисел. Для определения номера следующего кластера вам надо просто извлечь 16-битовое значение из FAT, использовав в качестве индекса номер предыдущего кластера.

Для 12-битовой FAT процедура значительно сложнее. Необходимо выполнить следующие действия:

• Умножить номер начального кластера на 3.
• Разделить результат на 2 (так как каждый элемент таблицы имеет длину 1.5 байта).
• Прочитать 16-битовое слово из FAT, используя в качестве смещения значение, полученное после деления на 2.
• Если номер начального кластера четный, на выбранное из FAT слово надо наложить маску 0fffh, оставив младшие 12 битов. Если номер начального кластера нечетный, выбранное из FAT значение необходимо сдвинуть вправо на 4 бита, оставив старшие 12 битов.
• Полученный результат - номер следующего кластера в цепочке, значение 0fffh соответствует концу цепочки кластеров.

Используя описанные выше методики чтения FAT, вы сможете для каждого файла определить цепочку занимаемых им кластеров. Для чтения файла при помощи прерывания DOS INT 25h вам будет нужно установить соответствие между номерами кластеров и номерами секторов, в которых располагаются эти кластеры. Для того чтобы это сделать, необходимо определить расположение и размер корневого каталога. Поэтому следующий раздел книги будет посвящен каталогам и файлам. Там же будут приведены примеры программ для работы с FAT.