Файловые системы VFAT и FAT32

Одной из важнейших характеристик исходной файловой системы FAT было ис­пользование имен файлов формата 8.3. К стандартной системе FAT (имеется в виду прежде всего реализация FAT 16) добавились еще две разновидности, используе-

172___________________________________________ Глава 6. Файловые системы

мые в широко распространенных ОС от Microsoft (конкретно — в Windows 95 и Windows NT): VFAT (виртуальная система FAT) и система FAT32, используе­мая в одной из редакций ОС Windows 95 и Windows 98. Ныне файловая система FAT32 поддерживается и такими последними системами, как Windows Millennium Edition, Windows 2000 и Windows XP. Имеются реализации FAT32 и для Windows NT, и для Linux.

Файловая система VFAT впервые появилась в Windows 3.11 (Windows for Work­groups). С выходом Windows 95 в VFAT добавилась поддержка длинных имен файлов (Long File Name, LFN). Тем не менее, VFAT сохраняет совместимость с ис­ходным вариантом FAT; это означает, что наряду с длинными именами в ней под­держиваются имена формата 8.3, а также существует специальный механизм для преобразования имен 8.3 в длинные имена, и наоборот. Именно файловая система VFAT поддерживается исходными версиями Windows 95, Windows NT 4, Windows 2000 и Windows XP. При работе с VFAT крайне важно использовать файловые утилиты, обслуживающие VFAT вообще и длинные имена в частности. Дело в том, что более ранние файловые утилиты DOS запросто модифицируют то, что кажет­ся им исходной структурой FAT. Это может привести к потере или порче длинных имен из таблицы размещения файлов, поддерживаемой VFAT (или FAT32). Сле­довательно, для томов VFAT необходимо пользоваться файловыми утилитами, которые понимают и сохраняют файловую структуру VFAT.

Основными недостатками файловых систем FAT и VFAT, которые привели к разработке новой реализации файловой системы, основанной на той же идее (таб­лице размещения файлов), являются большие потери на кластеризацию при боль­ших размерах логического диска и ограничения на сам размер логического дис­ка. Поэтому в Microsoft Windows 95 OEM Service Release 2' на смену системе VFAT пришла файловая система FAT32, которая является полностью самостоя­тельной 32-разрядной файловой системой и содержит многочисленные усовер­шенствования и дополнения по сравнению с предыдущими реализациями FAT. Самое принципиальное отличие заключается в том, что FAT32 намного эффек­тивнее расходует дисковое пространство. Прежде всего, кластеры в этой системе меньше, чем кластеры в предыдущих версиях, в которых могло быть не более 65 535 кластеров на логический диск (соответственно с увеличением размера диска приходилось увеличивать и размер кластеров). Следовательно, даже для дисков размером до 8 Гбайт FAT32 может использовать 4-килобайтные класте­ры. В результате по сравнению с дисками FAT 16 экономится значительное дис­ковое пространство (в среднем 10-15%). В FAT32 проблема решается за счет того, что собственно сама таблица размещения файлов в этой файловой системе может содержать до 2²⁸ кластеров².

FAT32 также может перемещать корневой каталог и использовать резервную ко­пию FAT вместо стандартной. Расширенная загрузочная запись FAT32 позволяет

¹ Эту версию Windows 95 часто называют Windows 95 OSR2.

² В 32-разрядном слове FAT32, используемом для представления номера кластера, фактически учи­
тываются только 28 разрядов, что приводит к тому, что размер таблицы размещения файлов в этой
системе не может превышать 2²⁸ элементов.

Файловая система FAT________________________________________________ 173

создавать копии критически важных структур данных; это повышает устойчивость дисков FAT32 к нарушениям структуры таблицы размещения файлов по сравне­нию с предыдущими версиями. Корневой каталог в FAT32 представлен в виде обыч­ной цепочки кластеров, следовательно, он может находиться в произвольном месте диска, что снимает действовавшее ранее ограничение на размер корневого катало­га (512 элементов).

Системы Windows 95 OSR2 и Windows 98 могут работать и с разделами VFAT, созданными Windows NT. To, что говорилось ранее об использовании файловых утилит VFAT с томами VFAT, относится и к FAT32. Поскольку прежние утили­ты FAT (для FAT32 в эту категорию входят обе файловые системы, FAT и VFAT) могут повредить или уничтожить важную служебную информацию, для томов FAT32 нельзя пользоваться никакими файловыми утилитами, кроме утилит FAT32.

Рис. 6.3. Элементы каталогов для FAT, VFAT и FAT32

174__________________________________________ Глава 6. Файловые системы

Помимо повышения максимального объема логического диска и уменьшения эф­фекта кластеризации, файловая система FAT32 вносит ряд необходимых усовер­шенствований в структуру корневого каталога. Предыдущие реализации требова­ли, чтобы вся информация корневого каталога FAT находилась в одном дисковом кластере. При этом корневой каталог мог содержать не более 512 файлов. Необхо­димость представлять длинные имена и обеспечить совместимость с прежними версиями FAT привела разработчиков компании Microsoft к компромиссному ре­шению: для представления длинного имени они стали использовать элементы каталога, в том числе и корневого. По этой причине для того, чтобы компенсиро­вать сокращение элементов главного каталога при использовании длинных имен, в FAT32 было увеличено их количество с 512 до 2048. Более того, чтобы не испы­тывать возможных проблем из-за расходования элементов активного каталога на описания файлов с длинными именами, компания Microsoft не рекомендует да­вать файлам слишком длинные имена.

Рассмотрим способ представления в VFAT длинного имени файла (рис. 6.3).

Первые 11 байт элемента каталога DOS используются для хранения имени файла. Каждое такое имя разделяется на две части: в первых восьми байтах хранятся сим­волы собственно имени, а в последних трех — символы так называемого расшире­ния, с помощью которого реализуются механизмы предопределенных типов. Были введены соответствующие системные соглашения, и файлы определенного типа желательно именовать с оговоренным расширением. Например, исполняемые фай­лы с расширением СОМ определяют исполняемую двоичную программу с про­стейшей односегментной структурой. Более сложные программы имеют расши­рение ЕХЕ. Определены расширения для большого количества типов файлов и эти расширения используются для ассоциированного запуска программ, обраба­тывающих эти файлы.

Если имя файла состоит менее чем из восьми символов, то в элементе каталога оно дополняется символами пробела, чтобы полностью заполнить все восемь байтов соответствующего поля. Аналогично и расширение может содержать от нуля до трех символов. Остальные (незаполненные) позиции в элементе каталога, опреде­ляющие расширение имени файла, заполняются символами пробела. Поскольку при работе с именем файла учитываются все одиннадцать свободных мест, то не­обходимость в отображении точки, которая обычно вводится между именем фай­ла и его расширением, отпадает. В элементе каталога она просто подразумевается.

В двенадцатом байте элемента каталога хранятся атрибуты файла. Шесть из вось­ми указанных разрядов используются DOS². Они перечислены ниже.

- A (Archive — архив). Показывает, что файл был открыт программой таким об­разом, чтобы у нее была возможность изменить содержимое этого файла. DOS устанавливает этот разряд при открытии файла. Программы резервного копи­рования (или, как часто говорят, архивирования, то есть составления архивов

¹ Для программных модулей, имеющих такую структуру, может использоваться и расширение BIN.

² В некоторых операционных системах, в частности вNovell Netware, используется один или два до­
полнительных разряда атрибутов.

Файловая система FAT________________________________________________ 175

данных) нередко сбрасывают его в ходе резервного копирования файла. Если применяется подобная методика, то в следующую создаваемую по порядку ре­зервную копию будут добавлены только те файлы, в которых данный разряд установлен.

- D (Directory — каталог). Показывает, что данный элемент каталога указывает
на подкаталог, а не на файл.

- V (Volume — том). Применяется только к одному элементу каталога в корне­
вом каталоге. В нем собственно и хранится имя дискового тома. Этот атрибут
также применяется в случае длинных имен файлов, о чем можно будет узнать
из следующего раздела.

- S (System — системный). Показывает, что файл является частью операционной
системы или специально отмечен подобным образом прикладной программой,
что иногда делается для защиты от копирования.

- Н (Hidden — скрытый). К скрытым относятся также файлы с установленным атрибутом S (системный), которые не отображаются по команде DIR.

- R (Read only — только для чтения). Показывает, что данный файл не подле­жит изменению. Разумеется, поскольку это лишь разряд байта, хранящего­ся на диске, то любая программа может изменить этот разряд и, значит, разрешить изменение соответствующего файла. Этот атрибут в основном ис­пользуется для примитивной защиты от пользовательских ошибок, то есть он помогает избежать неумышленного удаления или изменения ключевых файлов.

Следует отметить, что файл, помеченный одним или более из указанных выше ат­рибутов, может иметь вполне определенный смысл. Например, большинство фай­лов, отмечаемых в качестве системных, отмечаются также атрибутами «скрытый» и «только для чтения».

На дисках FAT 12 или FAT16 следующие за именем 10 байт не используются. Обык­новенно они заполняются нулями и считаются резервными значениями. А на дис­ке с файловой системой FAT32 эти 10 байт содержат самую разную информацию о файле. При этом байт, отмеченный как зарезервированный для NT, представля­ет собой, как подразумевает его название, поле, не используемое в DOS или Win­dows 9х, но применяемое в Windows NT.

Из соображений совместимости поля, которые встречаются в элементах каталога для коротких имен формата FAT 12 и FAT 16, находятся на тех же местах и в эле­ментах каталога для коротких имен формата FAT32. Остальные поля, которые встречаются только в элементах каталога для коротких имен формата FAT32, со­ответствуют зарезервированной области длиной 10 байт в элементах каталога для коротких имен форматов FAT 12 и FAT 16.

Как видно из рис. 6.3, для длинного имени файла используется несколько элемен­тов каталога. Таким образом, появление длинных имен фактически привело к даль­нейшему уменьшению количества файлов, находящихся в корневом каталоге. По­скольку длинное имя может содержать до 256 символов, всего один файл с полным длинным именем занимает до 25 элементов FAT (1 для имени 8.3 и еще 24 для

176___________________________________________ Глава 6. Файловые системы

самого длинного имени). Таким образом, количество элементов корневого катало­га VFAT уменьшается до 21. Очевидно, что это не вполне красивое решение, по­этому компания Microsoft советует избегать длинных имен в корневых каталогах при отсутствии системы FAT32, у которой количество элементов каталога просто требуемым образом увеличено¹.

Загрузочная запись для системы FAT32 несколько отличается от загрузочной записи FAT16. Так, например, в загрузочном секторе для тома с FAT32 в блоке DPB содер­жатся дополнительные поля, а те поля, что находятся в привычном для системы FAT16 месте, перенесены. Поэтому операционная система, в которой есть возможность рабо­тать с файловой системой FAT16, но нет системы управления файлами, понимающей спецификации FAT32, не может читать данные с томов, отформатированных под фай­ловую систему FAT32. В загрузочном секторе для файловой системы FAT32 по-пре­жнему байты с ООН по ОАН содержат команду перехода и OEM ID, а в байтах с ОВН по 59Н содержатся данные блока параметров диска (PDB). Отличие заключается именно в несколько иной структуре блока DPB (табл. 6.5).

Таблица 6.5.Структура загрузочной записи для FAT32

Смещение поля, Длина поля, Обозначение Содержимое поля
байт байт поля

ООН(0) 3 JUMP 3EH Безусловный переход на начало

системного загрузчика

ОЗН (3) 8 Системный идентификатор

ОВН (11) 2 SectSize Размер сектора, байт

0DH(13) 1 ClastSize Число секторов в кластере

0ЕН(14) 2 ResSecs Число зарезервированных секторов,

для FAT32 равно 32

10Н(16) 1 FATcnt Число копий FAT

11Н(17) 2 RootSize 0000H

13Н (19) 2 TotSecs 0000H

15Н (21) 1 Media Дескриптор носителя

16Н(22) 2 FATsize 0000H

18Н(24) 2 TrkSecs Число секторов на дорожке

1АН(26) 2 HeadCnt Число рабочих поверхностей

1СН(28) 4 HidnSecs Число скрытых секторов

(располагаются перед загрузочным сектором). Используется при загрузке для вычисления абсолютного смещения корневого каталога и данных

¹ Помните и о том, что длина полной файловой спецификации, включающей путь и имя файла (длин­ное или в формате 8.3), тоже ограничивается 260 символами. FAT32 успешно справляется с пробле­мой длинных имен в корневом каталоге, но проблема с ограничением длины полной файловой спе­цификации остается. По этой причине Microsoft рекомендует ограничивать длинные имена 75-80 символами, чтобы оставить достаточно места для пути (180-185 символов).

Файловая система HPFS______________________________________________ 177

Смещение поля, Длина поля, Обозначение Содержимое поля
байт байт поля

20Н (32) 4 Число секторов на логическом диске

24Н (36) 4 Число секторов в таблице FAT

28Н (37) 2 Расширенные флаги

2АН (38) 2 Версия файловой системы

2СН (39) 4 Номер кластера для первого кластера

корневого каталога

34Н (43) 2 Номер сектора с резервной копией

загрузочного сектора

36Н (54) 12 Зарезервировано

Заметим, что загрузочная запись для диска с FAT32 занимает не один сектор, как в FAT16 и FAT12, а три. Резервная загрузочная запись, как правило, располагает­ся в секторах 7-9.

Файловая система HPFS

Файловая система HPFS (High Performance File System — высокопроизводитель­ная файловая система) впервые появилась в операционных системах OS/2 1.2 и LAN Manager. Она была разработана совместными усилиями лучших специалис­тов компаний IBM и Microsoft на основе опыта IBM по созданию файловых сис­тем MVS, VM/CMS и виртуального метода доступа¹. Архитектура HPFS начала создаваться как файловая система для многозадачного режима и была призвана обеспечить высокую производительность при работе с файлами на дисках боль­шого размера.

HPFS стала первой файловой системой для персональных компьютеров, в кото­рой была реализована поддержка длинных имен [26]. HPFS, как и FAT, как и мно­гие другие файловые системы, обладает структурой каталогов, но в ней также пре­дусмотрены автоматическая сортировка каталогов и специальные расширенные атрибуты (Extended Attributes, EAs)², упрощающие обеспечение безопасности на файловом уровне и создание множественных имен. Помимо расширенных атри­бутов, каждый из которых концептуально подобен переменной окружения, HPFS по историческим причинам поддерживает те же самые атрибуты, что и файловая система FAT. Но самым главным отличием этой системы все же являются базовые принципы хранения информации о местоположении файлов.

Принципы размещения файлов на диске, положенные в основу HPFS, увеличива­ют как производительность файловой системы, так и ее надежность и отказо­устойчивость. Для достижения этих целей предложено несколько идей:

¹ Так, со стороны компании Microsoft проектом руководил известный системщик Гордон Литвин
(Gordon Letwin).

² Расширенные атрибуты позволяют хранить дополнительную информацию о файле. Например, каж­
дому файлу может быть сопоставлено его уникальное графическое изображение (значок, миниатю­
ра), описание файла, комментарий, сведения о владельце файла и т. д.

178___________________________________________ Глава 6. Файловые системы

- размещение каталогов в середине дискового пространства;

- использование методов бинарных сбалансированных деревьев для ускорения
поиска информации о файле;

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

Действительно, прежде всего, HPFS пытается расположить файл в смежных клас­терах или, если такой возможности нет, поместить его на диск таким образом, что­бы экстенты (extents)' файла физически были как можно ближе друг к другу. Та­кой подход существенно сокращает время позиционирования (seek time) головок записи/чтения жесткого диска и время ожидания (rotational latency)². Можно ска­зать, что файловая система HPFS имеет, по сравнению с FAT, следующие основ­ные преимущества:

- высокая производительность;
- надежность;

- поддержка расширенных атрибутов, позволяющих более гибко управлять до­ступом к файлам и каталогам;

- эффективное использование дискового пространства.

Все эти преимущества обусловлены структурой диска HPFS. Рассмотрим ее более подробно (рис. 6.4).

Рис. 6.4. Структура раздела HPFS

В начале диска расположено несколько управляющих блоков. Все остальное диско­вое пространство в HPFS разбито на множество областей из смежных секторов, или полос (bands). В каждой такой области располагаются и собственно сами данные файлов, и вспомогательная служебная информация о свободных или занятых сек­торах в этой области. Каждая полоса занимает на диске пространство в 8 Мбайт и имеет собственную битовую карту (bit map) распределения секторов, которая, с од­ной стороны, напоминает таблицу размещения файлов FAT, но, с другой, суще-

' Экстент — фрагмент файла, располагающийся в смежных секторах диска. Файл имеет, по крайней мере, один экстент, если он не фрагментирован, в противном случае — несколько экстентов.

² Время ожидания — это задержка между установкой головки чтения/записи на нужную дорожку диска и началом чтения данных с диска. Эта задержка обусловлена тем, что система вынуждена ждать, пока диск не повернется таким образом, чтобы нужный сектор оказался под головкой чтения/записи.

Файловая система HPFS______________________________________________ 179

ственно от нее отличается. Эти битовые карты показывают, какие секторы данной полосы заняты, а какие свободны. Каждому сектору полосы данных соответствует один бит в ее битовой карте.

Если бит имеет значение 1, то соответствующий сектор занят, если 0 — свободен. Битовые карты двух полос располагаются на диске рядом, также располагаются и сами полосы. То есть последовательность полос и карт выглядит следующим об­разом: битовая карта, битовая карта, полоса данных, полоса данных, битовая кар­та, битовая карта и т. д. Такое расположение полос и битовых карт позволяет не­прерывно разместить на жестком диске файл размером до 16 Мбайт и в то же время не удалять от самих файлов информацию об их местонахождении.

Очевидно, что если бы на весь логический диск была бы только одна адресная струк­тура данных, как это сделано в FAT, то для работы с ней приходилось бы переме­щать головки чтения/записи в среднем через половину диска. Именно для того, чтобы избежать таких потерь, в HPFS диск разбит на полосы. Получается как бы распределенная структура данных (в данном случае — битовая карта) с информа­цией об используемых и свободных блоках.

Дисковое пространство в HPFS выделяется не кластерами, как в FAT, а блоками. В имеющейся па сегодня реализации размер блока равен одному сектору, но, в прин­ципе, он мог бы быть и иного размера. По сути дела, блок — это и есть кластер. Размещение файлов в таких небольших блоках позволяет более эффективно ис­пользовать пространство диска, так как непроизводительные потери свободного места составляют в среднем всего 256 байт на каждый файл. Вспомните, чем боль­ше размер кластера, тем больше места на диске расходуется напрасно. Например, кластер на отформатированном под FAT диске объемом от 512 до 1023 Мбайт имеет размер 16 Кбайт. Следовательно, непродуктивные потери свободного простран­ства на таком разделе в среднем составляют 8 Кбайт (8192 байт) на один файл, в то время как на разделе HPFS эти потери всегда будут составлять всего 256 байт на файл. Таким образом, на каждый файл экономится почти 8 Кбайт.

На рис. 6.4 показано, что помимо полос с записями файлов и битовых карт на томе (volume)¹ с HPFS имеются еще три информационные структуры. Это так называ­емый загрузочный блок (boot block), дополнительный блок (super block) и резерв­ный блок (spare block). Загрузочный блок OS/2 располагается в секторах с 0 по 15; он содержит имя тома, его серийный номер, блок параметров BIOS² и программу начальной загрузки. Программа начальной загрузки находит программу 0S2LDR, считывает ее в память и передает управление на эту программу загрузки операци­онной системы, которая, в свою очередь, загружает с диска в память ядро OS/2 — программу OS2KRNL И уже 0S2KRNL с помощью сведений из файла CONFIG.SYS за­гружает в память все необходимые программные модули и блоки данных.

В дополнительном блоке содержится указатель на список битовых карт (bitmap block list). В этом списке перечислены все блоки на диске, в которых расположены

¹ По сути дела, том — это не что иное, как раздел, или логический диск.

² Блок параметров BIOS содержит информацию о жестком диске — количестве цилиндров и головок
диска, числе секторов на дорожке. Эта информация используется программными модулями HPFS для
поиска конкретного сектора (блока), поскольку все блоки пронумерованы 32-разрядными числами.

180 Глава 6. Файловые системы

битовые карты, используемые для обнаружения свободных секторов. Также в до­полнительном блоке хранится указатель на список дефектных блоков (bad block list), указатель на полосу каталогов (directory band), указатель на файловый узел (File node, F-node) корневого каталога, а также дата последней проверки раздела программой CHKDSK. В списке дефектных блоков перечислены все поврежденные секторы (блоки) диска. Когда система обнаруживает поврежденный блок, он вно­сится в этот список и для хранения информации больше не используется. Кроме того, в дополнительном блоке содержится информация о размере полосы. Напом­ним, что в имеющейся реализации HPFS размер полосы равен 8 Мбайт. В принци­пе, его можно было бы сделать и больше. Дополнительный блок размещается в сек­торе с номером 16 логического диска, на котором установлена файловая система HPFS.

Резервный блок содержит указатель на карту (НotFix map), или области (HotFix areas), аварийного замещения, указатель на список свободных запасных блоков ка­талогов (directory emergency free block list), используемых для операций на почти переполненном диске, и ряд системных флагов и дескрипторов. Резервный блок размещается в 17-м секторе диска и обеспечивает высокую отказоустойчивость файловой системы HPFS, позволяя восстанавливать поврежденные данные на диске и перемещать их в надежное место.

Файлы и каталоги в HPFS базируются на фундаментальном объекте, уже упоми­навшемся файловом узле. Эта структура характерна для HPFS, и аналога в фай­ловой системе FAT у нее нет. Каждый файл и каталог диска имеет свой файловый узел. Каждый файловый узел занимает один сектор и всегда располагается побли­зости от своего файла или каталога (обычно — непосредственно перед файлом или каталогом). Файловый узел содержит размер файла и первые 15 символов имени файла, специальную служебную информацию, статистику по доступу к файлу, расширенные атрибуты файла и список управления доступом (Access Control List, ACL) или только часть этого списка, если он очень большой, ассоциативную ин­формацию о расположении и подчинении файла и т. д. Структура распределения информации в файловом узле может иметь несколько форм, в зависимости от раз­мера каталога или файлов. HPFS рассматривает файл как совокупность одного или более секторов. Из прикладной программы этого не видно; файл прикладной программе представляется как непрерывный поток байтов. Если расширенные ат­рибуты слишком велики для файлового узла, то в него записывается указатель на них.

Сокращенное имя файла (в формате 8.3) используется, когда файл с длинным име­нем копируется или перемещается на диск с системой FAT, которая не допускает подобных имен. Сокращенное имя образуется из первых 8 символов оригинально­го имени файла, точки и первых 3 символов расширения имени, если расширение имеется. Если в имени файла присутствует несколько точек, что не противоречит правилам именования файлов в HPFS, то для расширения сокращенного имени используются 3 символа после самой последней из этих точек.

¹ Файловый узел — это структура, в которой содержится информация о расположении файла и о его расширенных атрибутах.

Файловая система HPFS______________________________________________ 181

Так как HPFS при размещении файла на диске стремится избежать его фрагмен­тации, то структура информации, содержащаяся в файловом узле, достаточно про­ста. Если файл непрерывен, то его размещение на диске описывается двумя 32-разрядными числами. Первое число представляет собой указатель на первый блок файла, а второе — длину экстента, то есть число следующих друг за другом блоков, принадлежащих файлу¹. Если файл фрагментирован, то размещение его экстентов описывается в файловом узле дополнительными парами 32-разрядных чисел. Фрагментация происходит, когда на диске нет непрерывного свободного участка, достаточно большого, чтобы разместить файл целиком. В этом случае файл прихо­дится разбивать на несколько экстентов и располагать их на диске раздельно. Фай­ловая система HPFS старается разместить экстенты фрагментированного файла как можно ближе друг к другу, чтобы сократить время позиционирования головок чтения/записи жесткого диска. Для этого HPFS использует статистику, а также старается условно резервировать хотя бы 4 Кбайт места в конце файлов, которые растут. Еще один способ снижения фрагментации файлов — это размещение в раз­ных полосах диска файлов, растущих навстречу друг другу, а также файлов, от­крытых разными потоками выполнения или процессами.

В файловом узле можно разместить информацию максимум о 8 экстентах файла. Если файл имеет больше экстентов, то в его файловый узел записывается указа­тель на блок размещения (allocation block), который может содержать до 40 ука­зателей на экстенты, или, по аналогии с блоком дерева каталогов, на другие бло­ки размещения. Таким образом, двухуровневая структура блоков размещения может хранить информацию о 480 секторах, что позволяет работать с файлами размером до 7,68 Гбайт. На практике размер файла не может превышать 2 Гбайт, но это обусловлено текущей реализацией интерфейса прикладного программи­рования [26].

Упоминавшаяся выше полоса каталогов находится в центре диска и используется для хранения каталогов. Как и все остальные полосы, она имеет размер 8 Мбайт. Однако если она будет полностью заполнена, HPFS начинает располагать катало­ги файлов в других полосах. Расположение этой информационной структуры в се­редине диска значительно сокращает среднее время позиционирования головок чтения/записи, тем более что обращения к корневому каталогу достаточно часты. Действительно, для перемещения головок чтения/записи из произвольного места диска в его центр требуется в два раза меньше времени, чем для перемещения к краю диска, где находится корневой каталог в случае файловой системы FAT. Уже толь­ко одно это обеспечивает существенно более высокую производительность фай­ловой системы HPFS по сравнению с FAT. Аналогичное замечание справедливо и для системы NTFS, которая тоже располагает свою главную таблицу файлов в на­чале дискового пространства, а не в его середине (см. раздел «Файловая система NTFS»). Тестирование показывает, что HPFS является самой быстрой файловой системой.

Однако существенно больший вклад в производительность HPFS (по сравнению с размещением полосы каталогов в середине логического диска) дает использова-

¹ Из этого следует, что максимальный объем диска может составить (2³² - 1) х 512 = 2 Тбайт.

182___________________________________________ Глава 6. Файловые системы

ние метода сбалансированных двоичных деревьев для хранения и поиска информа­ции о местонахождении файлов. Как известно, в файловой системе FAT каталог имеет линейную неупорядоченную специальным образом структуру, поэтому при поиске файла требуется последовательно просматривать его с самого начала. В HPFS структура каталога представляет собой сбалансированное дерево с запи­сями, расположенными в алфавитном порядке (рис. 6.5). Каждая запись, входя­щая в состав двоичного дерева (Binary Tree, B-Tree), содержит атрибуты файла, указатель на соответствующий файловый узел, информацию о времени и дате со­здания файла, о времени и дате последнего обновления и обращения, об объеме данных, содержащих расширенные атрибуты, счетчик обращений к файлу, инфор­мацию о длине имени файла и само имя, другую информацию.

Рис. 6.5. Сбалансированное двоичное дерево

Файловая система HPFS при поиске файла в каталоге просматривает только не­обходимые ветви двоичного дерева, отбрасывая те записи каталога, про которые заведомо известно, что они не относятся к искомому файлу. Например, если имя файла начинается с символа, расположенного в первой части используемого ал­фавита, то незачем искать его среди записей каталога, описывающих файлы, име­на которых начинаются с символов, расположенных во второй части этого алфа­вита. Далее, если искомый элемент каталога расположен во второй половине первой части (то есть во второй четверти), то незачем перебирать имена файлов, располо­женных в первой четверти каталога. И так далее. Очевидно, что такой метод во много раз эффективнее, чем последовательное чтение всех записей в каталоге, что имеет место в системе FAT. Для того чтобы найти искомый файл в каталоге (точ­нее, указатель на его информационную структуру F-node), организованном на прин­ципах сбалансированных двоичных деревьев, большинство записей вообще читать не нужно. В результате для поиска информации о файле необходимо выполнить существенно меньшее количество операций чтения с диска.

Действительно, если, например, каталог содержит 4096 файлов, то файловая сис­тема FAT потребует чтение в среднем 64 секторов для поиска нужного файла внутри такого каталога, в то время как HPFS осуществит чтение всего только 2-4 секто­ров (в среднем) и найдет искомый файл. Несложные расчеты позволяют увидеть явные преимущества HPFS над FAT. Так, например, при использовании 40 вхо­дов на блок блоки дерева каталогов с двумя уровнями могут содержать 1640 вхо-

Файловая система HPFS______________________________________________ 183

дов, а дерева каталогов с тремя уровнями — уже 65 640 входов. Другими словами, некоторый файл может быть найден в типичном каталоге из 65 640 файлов макси­мум за три обращения. Это намного лучше файловой системы FAT, где в самом плохом случае для нахождения файла нужно прочитать более чем 4000 секторов.

Размер каждого из блоков, в терминах которых выделяются каталоги в текущей реализации HPFS, равен 2 Кбайт. Размер записи, описывающей файл, зависит от размера имени файла. Если имя занимает 13 байт (для формата 8.3) то 2-килобай-товый блок вмещает до 40 дескрипторов файлов. Блоки связаны друг с другом по­средством списковой структуры (как и дескрипторы экстентов) для облегчения последовательного обхода.

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

Важное значение для повышения скорости работы с файлами имеет снижение их фрагментации. В HPFS считается, что если файл содержит больше одного экстен­та, он считается фрагментированным. Снижение фрагментации файлов сокраща­ет время позиционирования и время ожидания за счет уменьшения количества перемещений головок, необходимых для доступа к данным файла. Алгоритмы ра­боты файловой системы HPFS функционируют таким образом, чтобы по возмож­ности размещать файлы в последовательных смежных секторах диска, что в по­следующем обеспечит максимально быстрый доступ к данным. В системе FAT, наоборот, запись следующей порции данных в первый же свободный кластер не­избежно приводит к фрагментации файлов. То есть HPFS записывает данные не в первый попавшийся сектор, а, если это предоставляется возможным, в смежные секторы диска. Это позволяет несколько снизить число перемещений головок чте­ния/записи от дорожки к дорожке. Когда данные дописываются в существующий файл, HPFS сразу же резервирует как минимум 4 Кбайт непрерывного простран­ства на диске. Если же часть этого пространства не потребовалась, то после закры­тия файла она высвобождается для дальнейшего использования. Файловая систе­ма HPFS равномерно размещает непрерывные файлы по всему диску для того, чтобы впоследствии без фрагментации обеспечить их возможное увеличение. Если же файл не может быть увеличен без нарушения его непрерывности, HPFS опять-таки резервирует 4 Кбайт смежных блоков как можно ближе к основной части файла с целью сократить время позиционирования головок чтения/записи и вре­мя поиска соответствующего сектора.

Очевидно, что степень фрагментации файлов на диске зависит как от числа распо­ложенных на нем файлов, их размеров и размеров самого диска, так и от характера и интенсивности самих дисковых операций. Незначительная фрагментация фай­лов практически не сказывается на быстродействии операций с файлами. Файлы, состоящие из 2-3 экстентов, практически не снижают производительности HPFS,

184___________________________________________ Глава 6. Файловые системы

так как эта файловая система следит за тем, чтобы области данных, принадлежа­щие одному и тому же файлу, располагались как можно ближе друг к другу. Файл из трех экстентов имеет только два нарушения непрерывности, и, следовательно, для его чтения потребуется всего лишь два небольших перемещения головки дис­ка. Программы (утилиты) дефрагментации, имеющиеся для этой файловой систе­мы по умолчанию, считают наличие двух-трех экстентов у файла нормой¹. Прак­тика показывает, что в среднем на диске имеется не более 2 % файлов, имеющих три и более экстентов [26]. Даже общее количество фрагментированных файлов, как правило, не превышает 3 %. Такая ничтожная фрагментация оказывает пре­небрежимо малое влияние на общую производительность системы.

Теперь кратко рассмотрим вопрос надежности хранения данных в HPFS. Любая файловая система должна обладать средствами исправления ошибок, возникаю­щих при записи информации на диск. Система HPFS для этого использует меха­низм аварийного замещения (HotFix).

Если файловая система HPFS сталкивается с проблемой в процессе записи дан­ных на диск, она выводит на экран соответствующее сообщение об ошибке. Затем HPFS сохраняет информацию, которая должна была быть записана в дефектный сектор, в одном из запасных секторов, заранее зарезервированных на этот случай. Список свободных запасных блоков хранится в резервном блоке HPFS. При обна­ружении ошибки во время записи данных в нормальный блок HPFS выбирает один из свободных запасных блоков и сохраняет эти данные в нем. Затем файловая си­стема обновляет карту аварийного замещения в резервном блоке. Эта карта пред­ставляет собой просто пары двойных слов, каждое из которых является 32-разряд­ным номером сектора. Первый номер указывает на дефектный сектор, а второй — на тот сектор среди имеющихся запасных секторов, который и был выбран для замены плохого. После замены дефектного сектора запасным карта аварийного замещения записывается на диск,