Файловая система HPFS
HPFS - сокращенное название высокопроизводительной файловой системы (high performance file system), совместно разработанной в 1989 году корпорациями IBM и Microsoft.
Эта система была разработана, чтобы преодолеть некоторые недостатки FAT, к числу которых относятся:
ограничения, налагаемые на размер файлов и дискового пространства;
ограничение длины имени файла;
фрагментация файлов, приводящая к снижению быстродействия системы и износу оборудования;
непроизводительные затраты памяти, вызванные большими размерами кластеров;
подверженность потерям данных.
Проблема непроизводительных потерь дискового пространства связана с тем, что место на диске выделяется целыми блоками - кластерами. Кластер - это единица дискового пространства, которыми оперирует файловая система при выделении места для файла. В среднем половина выделяемого кластера для каждого файла будет затрачиваться в пустую. Это может быть одной из причин нерационального использования памяти диска. Например, при емкости диска 510 Мбайт число размещенных на нем файлов может составить около 1,5 тысяч. В этом случае FAT приведет к потере 6 Мбайт пространства, обусловленной только размером выделяемого блока. Для очень распространенных сейчас дисков емкостью 850 Мбайт ситуация может оказаться еще более критической. На таком диске может разместиться около 2 тысяч файлов, что повлечет за собой потерю 20 Мбайт. Для сетевых дисков емкостью в несколько гигабайт потери достигают астрономических цифр. Чем больше размер раздела жесткого диска, тем больше объем минимальной неделимой области памяти, выделяемой файлу, тем больше потери.
Эти потери можно существенно сократить внедрением более эффективных файловых систем. Простой переход на HPFS, работающую в среде OS/2, позволяет вновь вернуться к первоначальному размеру выделяемого блока - 512 байт, причем для любых размеров диска. Размер вероятного выигрыша для диска емкостью 512 Мбайт, содержащего 8 000 файлов, составит около 30 Мбайт. Этот выигрыш связан с тем, что на каждом файле в среднем теряется не 4096 байт (половина размера кластера в FAT для диска данной емкости), а всего 256 байт.
В OS/ 2 положение осложняется применяемым методом хранения расширенных атрибутов (extended attributes). В разделе FAT файл, содержащий единственный символ, занял бы целый кластер для размещения собственно файла и еще один кластер для расширенных атрибутов.
Так как расширенные атрибуты почти всегда имеют объем меньше 300 байт, размер теряемого впустую дискового пространства изменяется от примерно половины кластера при использовании малых разделов до львиной доли объема кластер при больших разделах. В сумме на каждом файле теряется примерно кластер.
Переход на HPFS позволит сэкономить дисковое пространство. HPFS распределяет пространство, основываясь на физических 512-байтовых секторах, а не на кластерах, независимо от размера раздела. Система HPFS позволяет уменьшить и непроизводительные потери, так как в ней предусмотрено хранение до 300 байт расширенных атрибутов в F-узле файла, без захвата для этого дополнительного сектора.
Другая проблема связана с фрагментацией файлов, которая наиболее характерна для емких дисков с большим числом файлов. Фрагментация существенно сказывается на времени доступа к файлу. Другой негативный эффект фрагментации - повышенный износ диска. О серьезности этой проблемы говорит обилие утилит для дефрагментации дисков, использующих FAT.
Файловая система HPFS обеспечивает гораздо более низкий уровень фрагментации. Хотя избавиться полностью от нее не удается, снижение производительности, возникающее по этой причине, почти незаметно для пользователя.
Первые 16 секторов раздела HPFS составляют загрузочный блок. Эта область содержит метку диска и код начальной загрузки системы. Сектор 16, известный под названием суперблок, содержит много общей информации о файловой системе в целом: размер раздела, указатель на корневой каталог, счетчик элементов каталогов, номер версии HPFS, дату последней проверки и исправления раздела при помощи команды CHKDSK, а также дату последнего выполнения процедуры дефрагментации раздела. Он также содержит указатели на список испорченных блоков на диске, таблицу дефектных секторов и список доступных секторов.
Сектор 17 носит название SpareBlock (запасной блок). Он содержит указатель на список секторов, которые можно использовать для "горячего" исправления ошибок, счетчик доступных секторов для "горячего" исправления ошибок, указатель на резерв свободных блоков, применяемых для управления деревьями каталогов, и информацию о языковых наборах символов. Система HPFS использует информацию о языковых наборах, чтобы дать возможность пересылать файлы, составленные на разных языках, даже в том случае, когда имена файлов содержат уникальные для какого-либо языка символы. SpareBlock также содержит так называемый "грязный" флаг. Этот новый флаг сообщает операционной системе о том, было ли завершение предыдущего сеанса работы нормальным, либо произошло в результате сбоя электропитания, либо файлы не были закрыты должным образом по какой-то другой причине. Если этот флаг обнаружен во время начальной загрузки, то операционная система автоматически запускает утилиту CHKDSK, пытаясь обнаружить и исправить все ошибки, внесенные в файловую систему из-за неправильного выключения системы.
Рис. 9.3. Прием увеличения доступного непрерывного пространства
Во время форматирования раздела HPFS делит его на полосы по 8 Мбайт каждая. Каждая полоса - ее можно представить себе как виртуальный "мини-диск" - имеет отдельную таблицу объемом 2 Кбайт, в которой указывается , какие секторы полосы доступны, а какие заняты. Чтобы максимально увеличить протяженность непрерывного пространства для размещения файлов, таблицы попеременно располагаются в начале и в конце полос (рисунок 9.3). Этот метод позволяет файлам размером до 16 Мбайт (минус 4 Кбайта, отводимые для размещения таблицы) храниться в одной непрерывной области.
Затем файловая система HPFS оценивает размер каталога и резервирует необходимое пространство в полосе, расположенной ближе всего к середине диска. Сразу же после форматирования объем диска в HPFS кажется меньше, чем в FAT, так как заранее резервируется место для каталогов в центре диска.
Место резервируется в середине диска для того, чтобы физические головки, считывающие данные, никогда не проходили более половины ширины диска.
Тот факт, что все пространство заранее распределено, также позволяет HPFS использовать специально оптимизированное программное обеспечение для более быстрой и эффективной работы с каталогами. Сравните это с системой FAT, где головкам требуется пройти весь путь к началу диска и прочитать таблицу размещения файлов, затем найти кластер, вновь пройти к началу диска, чтобы определить в FAT местонахождения следующего кластера, и так далее. Эта процедура становится еще более неудобной по мере нарастания фрагментации. Поэтому ясно, что размещение каталогов в середине диска повышает производительность системы. Вместе с тем, такое предварительное распределение не накладывает ограничений на число файлов, которые могут быть размещены на жестком диске. В редких случаях, когда системе HPFS потребуется больше пространства, чем изначально было отведено под каталоги, она может выделить дополнительное пространство из любой доступной области диска.
Число файлов в каждом блоке каталога - переменная величина, зависящая от длины имен файлов, которые содержатся в нем. Имена файлов в HPFS могут иметь длину до 254 символов, они сортируются в порядке, определяемом последовательностью символов в текущей кодовой странице системы.
Скорость работы увеличивается также благодаря способу хранения элементов каталогов. Система FAT последовательно просматривает каждый элемент каталога, чтобы отыскать нужный файл. Поэтому в самом худшем случае приходится перебирать все файлы в каталоге, прежде, чем найдется нужный. Но HPFS использует для хранения элементов каталогов структуру данных, называемую В-деревом. Каждый элемент каталога начинается с числа, представляющего длину элемента, которая изменяется в зависимости от длины имени файла. Затем следуют время и дата создания файла, его размер и атрибуты (только для чтения, архивный, скрытый и системный), а также указатель на F-узел файла.
Каждый файл (и каталог) имеет F-узел - структуру данных, занимающую один сектор и содержащую принципиально важную информацию о файле.
F-узел содержит указатель на начало файла, первые 15 символов имени файла, дополнительные временные маркеры последней записи и последнего доступа, журнал, хранящий информацию о предыдущих обращениях к файлу, структуру распределения, описывающую размещение файла на диске, и первые 300 байт расширенных атрибутов файла. (Расширенные атрибуты редко занимают более 300 байт, что фактически означает, что HPFS для получения этой информации приходится читать на один сектор меньше, чем FAT.) Программы LAN Server и LAN Manager фирмы IBM также сохраняют в F-узле информацию об управлении пользовательским доступом (Access Control). Заметьте, что F-узлы хранятся в смежных с представляемыми ими файлами секторах, поэтому, когда файл открывается, то четыре автоматически считываемых в кэш сектора содержат F-узел и три первых сектора файла.
Структура размещения HPFS имеет дополнительные преимущества по сравнению с FAT благодаря техническому приему, называемому кодированием по длине выполнения (Run Length Encoding, RLE). Вместо того, чтобы определять в таблице каждый используемый сектор, HPFS сохраняет указатель на первый сектор и число последовательно расположенных используемых секторов. Каждая область дискового пространства, описываемая парой (сектор, длина), называется экстентом. Хотя HPFS и сводит фрагментацию к минимуму, файлы все же могут быть в некоторой степени фрагментированными. В таких ситуациях пары, описывающие экстенты, добавляются к F-узлу файла. Один F-узел может хранить до 8 экстентов, обеспечивая достаточное пространство для большинства файлов.
А если все же потребуется еще большее пространство, то HPFS изменяет структуру таким образом, что F-узел становится корнем В+-дерева секторов размещения. В+-дерево является вариантом бинарного В-дерева. Созданное как структура для более быстрого обнаружения данных по сравнению с методом последовательного перебора, бинарное дерево состоит из ветвей, каждая из которых представляет выбор одного из двух возможных продолжений.
Короткое дерево территориальных телефонных кодов может выглядеть так, как показано на рисунке 9.4,а. Здесь левая ветвь соответствует числам с меньшими значениями, чем значение в точке разветвления, а правая - с большими. Пусть выполняется поиск, например, кода 513. Вначале анализируется код в вершине дерева, поскольку 513 больше 212, то дальнейший поиск осуществляется по правой ветви. Так как 513 больше 407, то вновь поиск идет по правой ветви, где и находится нужный элемент данных. Для того, чтобы найти данные с помощью этого метода, потребовалось выполнить только два сравнения, в то время как для последовательного перебора могло бы потребоваться пять сравнений.
Рис. 9.4. Бинарные древовидные структуры
Эффективность бинарных деревьев зависит от последовательности, в которой в них добавляются новые элементы данных. Если, например, добавить код 617, то он будет следовать за кодом 513, а если добавить еще один код 714, то он последует за кодом 617. Поэтому, если элементы добавляются в порядке возрастания, то результирующее дерево становится все более похожим на последовательную структуру (рис. 9.4,б).
Структура В-дерева была разработана в целях предотвращения этой проблемы. Методы управления В-деревьями обеспечивают сбалансированность дерева. Структуру на рисунке 9.4 (б) лучше реорганизовать так, чтобы она приняла вид, показанный на рисунке 9.4 (в). Это делает дерево более эффективным, но приводит к дополнительным затратам, так как его балансировка выполняется всякий раз при добавлении или удалении элемента, либо при изменении значения элемента.
Возвращаясь к методу описания физической структуры файла, основанному на экстентах, следует учесть, что многие современные контроллеры дисков могут читать за одно обращение сразу несколько секторов. Применяемая в HPFS схема значительно повышает шансы использовать эту возможность, при этом происходит еще большее уменьшение числа требуемых операций взаимодействия между программой, файловой системой, драйвером дискового устройства и физическим диском.
HPFS имеет и другие оптимизирующие функции. Так при открытии или создании файла интеллектуальный алгоритм выделяет наиболее подходящую полосу. Программный интерфейс, используемый для создания файла, позволяет программисту сообщить операционной системе предполагаемый размер файла. С помощью этой информации HPFS может заранее выбрать для размещения файла полосу, имеющую непрерывную область наибольшего размера. Именно поэтому HPFS наиболее эффективно работает в больших разделах - больше число полос предоставляет большие возможности выбора.
Предположим, что многонитевая операционная система одновременно создает четыре новых файла на диске, использующем FAT. Так как для каждого файла нужен новый сектор, то он занимает ближайший доступный сектор в таблице размещения файлов. Это приводит к значительной фрагментации, так как кластеры между файлами распределяются вперемежку. HPFS выделила бы каждому из четырех файлов отдельную полосу, чтобы их содержимое оставалось непрерывным.
Как уже упоминалось, при открытии файла F-узел и первые три сектора считываются и помещаются в кэш. Если открываемый файл - исполняемый или если по данным журнала доступа к файлам в F-узле видно, что файл после открытия часто читается целиком, то многие секторы будут предварительно автоматически прочитаны и помещены в кэш.
Операции записи в кэш осуществляются особым образом, который называется "ленивой" записью. Когда программа посылает команду записи, HPFS помещает данные в кэш и немедленно сообщает программе, что операция выполнена, и только потом в фоновом режиме данные перемещаются из оперативной памяти на устройство. Это исключает длительную задержку, сопровождающую действительную операцию записи данных на устройство ввода-вывода. Однако при этом существует риск нарушения целостности данных. Например, уже после того, как программа получила от ОС сообщение об успешном завершении операции ввода-вывода, при попытке записать данные из кэша на диск драйвер этого устройства может сообщить об ошибке обращения к диску.
В таком случае весьма полезным является список блоков "горячего" исправления.
Если попытка записи на диск заканчивается неудачно, то HPFS отыскивает в SpareBlock блок, который можно использовать для "горячего" исправления. Данные записываются в область "горячего" исправления, а таблицы неисправных блоков обновляются, указывая испорченный сектор и блок. HPFS будет автоматически перенаправлять запросы чтения по новому адресу. Во время очередного выполнения утилиты CHKDSK файл будет скопирован в новое место, где он может храниться в непрерывной области. При обращении к нему нет необходимости переходить к блоку "горячего" исправления и обратно. Блок будет освобожден для использования в случае возникновения другой подобной проблемы. Таким образом, проблема решается автоматически без участи пользователя.
Для повышения эффективности система HPFS также предоставляет многоуровневые кэши. Например, она сохраняет в кэше подкаталоги, а также полное составное имя, записав в памяти контрольную сумму, однозначно определяющую путь к файлу. Поэтому при обращении к файлу, расположенному в глубоко вложенном каталоге, скорее всего будет возможен быстрый доступ сразу в нужный каталог без поиска по дереву каталогов.
HPFS обладает повышенной отказоустойчивостью по сравнению с FAT. Если на диске с FAT оказалась стертой таблица распределения файлов, то скорее всего окажутся потерянными все данные, которые находятся вне корневого каталога. В системе HPFS вместо таблицы размещения файлов применяется битовый массив, который содержит флаг, помечающий используемые секторы. Если область битового массива будет разрушена, пользователь этого не заметит, даже если это случится во время работы системы. F-узел файла также содержит информацию о размещении каждого файла. Поэтому область битового массива может быть восстановлена после поиска этой информации в F-узлах. Пользователь не увидит даже предупреждения - поиск выполняется автоматически. Этот процесс может быть запущен и с помощью утилиты CHKDSK, которая сравнивает битовый массив с информацией для файла о принадлежащих ему секторах.
Если при чтении битового массива обнаруживается ошибка, то создается новый битовый массив.
В системе FAT при порче каталогов теряются указатели на начало цепочки кластеров каждого файла. Можно соединить отдельные кластеры в файл, но многое придется делать в ручную. Так как утилиты, подобные CHKDSK, не знают имени файлов, то для того, чтобы восстановить их старые имена, придется загружать файлы в текстовый редактор и пытаться определить, что они из себя представляют.
При работе с HPFS в случае потери каталога у каждого файла из этого каталога теряется лишь дата последней операции записи в файл и иных изменений, дата создания и длинное имя файла (символы, следующие за первыми пятнадцатью). Элемент каталога - это всего лишь указатель на F-узел. В F-узле хранятся первые 15 символов имени файла (плюс информация о том, имелись ли в имени файла другие символы, кроме первых 15) и прочая информация, нужная для доступа к файлу. Утилиты восстановления могут впоследствии найти в F- узле сведения о том или ином файле. Эта избыточность, обеспечиваемая каталогом и F-узлами, значительно увеличивает шансы на восстановление данных. CHKDSK в настоящее время - единственная утилита восстановления, поставляемая с OS/2, которая, к сожалению, пока не использует всю имеющуюся информацию.
HPFS не налагает ограничений на максимальный размер файла, но OS/2 в настоящее время устанавливает предел в 2 Гбайта на один файл. Цель HPFS - доведение размера раздела до 2 Тбайт, но сегодня имеется ограничение в 64 Гбайта, поскольку некоторые части системы HPFS до сих пор остаются 16-разрядными.
Содержание раздела