Загрузка...

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


Сокращение HPFS расшифровывается как «High Performance File System» — высокопроизводительная файловая система.

HPFS была первой файловой системой для ПК, в которой была реализована поддержка длинных имен. HPFS, как FAT и многие другие файловые систе­мы, обладает структурой каталогов, но в ней также предусмотрены автоматиче­ская сортировка каталогов и специальные расширенные атрибуты2, упрощающие реализацию безопасности файлового уровня и создание множественных имен. HPFS поддерживает те же самые атрибуты, что и файловая система FAT, но также поддерживает и новую форму file-associated, то есть информацию, называемую расширенными атрибутами (EAs3). Каждый ЕА концептуально подобен переменной окружения. Но самым главным отличием все же являются базовые принципы хранения информации о местоположении файлов.

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

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

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

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

HPFS стремится к тому, чтобы расположить файл в смежных кластерах, или, если такой возможности нет, разместить его на диске таким образом, чтобы экстенты (фрагменты) файла физически были как можно ближе друг к другу. Такой подход существенно уменьшает время позиционирова­ния головок записи/чтения жесткого диска и время ожидания (rotational laten­cy) — задержка между установкой головки чтения/записи на нужную дорожку диска и началом чтения данных с диска. Файловая система HPFS имеет, по сравнению с FAT, следующие основные преимущества:

  • высокая производительность;
  • надежность;
  • работа с расширенными атрибутами, что позволяет управлять доступом к фай­лам и каталогам;
  • эффективное использование дискового пространства.

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

Структура раздела HPFS

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

В начале диска расположено несколько управляющих блоков. Все остальное дис­ковое пространство в HPFS разбито на части («полосы», «ленты» из смежных секторов, в оригинале — band). Каждая такая группа данных занимает на диске пространство в 8 Мбайт и имеет свою собственную битовую карту распределе­ния секторов. Эти битовые карты показывают, какие секторы данной полосы за­няты, а какие — свободны. Каждому сектору ленты данных соответствует один бит в ее битовой карте. Если бит имеет значение 1, то соответствующий сектор занят, а если 0 — свободен.

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

Если бы на весь диск была только одна битовая карта, как это сделано в FAT, то для работы с ней приходилось бы перемещать головки чте­ния/записи в среднем через половину диска. Чтобы избежать этих потерь, в HPFS диск разбит на «полосы». Получается своего рода распре­деленная структура данных об используемых и свободных блоках.

Дисковое пространство в HPFS выделяется не кластерами, как в FAT, а блоками. В современной реализации размер блока взят равным одному сектору, но в принципе он мог бы быть и иного размера. Размещение файлов в таких небольших блоках позволяет более эффектив­но использовать пространство диска, так как непроизводительные потери сво­бодного места составляют в среднем всего 256 байт на каждый файл.

На рис. 4.10 показано, что помимо «лент» с записями файлов и битовых карт в томе с HPFS имеются еще три информационные структуры. Это так называе­мый загрузочный блок (boot block), дополнительный блок (super block) и запас­ной (резервный) блок (spare block).

Загрузочный блок (boot block) располагается в секторах с 0 по 15; он содержит имя тома, его серийный номер, блок парамет­ров BIOS и программу начальной загрузки.

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

Если файловая система HPFS сталкивается с проблемой в процессе записи дан­ных на диск, она выводит на экран соответствующее сообщение об ошибке. Затем HPFS сохраняет информацию, которая должна была быть записана в дефектный сектор, в одном из запасных секторов, заранее зарезервированных на этот слу­чай. Список свободных запасных блоков хранится в резервном блоке HPFS. При обнаружении ошибки во время записи данных в нормальный блок HPFS выби­рает один из свободных запасных блоков и сохраняет эти данные в нем. Затем файловая система обновляет карту аварийного замещения в резервном блоке. Эта карта представляет собой просто пары двойных слов, каждое из которых является 32-битным номером сектора. Первый номер указывает на дефектный сек­тор, а второй — на тот сектор среди имеющихся запасных секторов, который был выбран для его замены. После замены дефектного сектора запасным карта ава­рийного замещения записывается на диск, и на экране появляется всплывающее окно, информирующее пользователя о произошедшей ошибке записи на диск. Каждый раз, когда система выполняет запись или чтение сектора диска, она просматривает карту аварийного замещения и подменяет все номера дефектных секторов номерами запасных секторов с соответствующими данными. Следует заметить, что это преобразование номеров существенно не влияет на производи­тельность системы, так как оно выполняется только при физическом обращении к диску, но не при чтении данных из дискового кэша. Очистка карты аварийного замещения автоматически выполняется программой CHKDSK при проверке дис­ка HPFS. Для каждого замещенного блока (сектора) программа CHKDSK выде­ляет новый сектор в наиболее подходящем для файла (которому принадлежат данные) месте жесткого диска. Затем программа перемещает данные из запасно­го блока в этот сектор и обновляет информацию о положении файла, что может потребовать новой балансировки дерева блоков размещения. После этого CHKDSK вносит поврежденный сектор в список дефектных блоков, который хранится в дополнительном блоке HPFS, и возвращает освобожденный сектор в список свободных запасных секторов резервного блока. Затем удаляет запись из карты аварийного замещения и записывает отредактированную карту на диск. Все основные файловые объекты в HPFS, в том числе файловые узлы, блоки размещения и блоки каталогов, имеют уникальные 32-битные идентификаторы и указатели на свои родительские и дочерние блоки. Файловые узлы, кроме того, содержат сокращенное имя своего файла или каталога. Избыточность и взаимосвязь файловых структур HPFS позволяют программе CHKDSK полно­стью восстанавливать файловую структуру диска, последовательно анализируя все файловые узлы, блоки размещения и блоки каталогов. Руководствуясь соб­ранной информацией, CHKDSK реконструирует файлы и каталоги, а затем заново создает битовые карты свободных секторов диска.

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

Загрузка...