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

Федеральное агентство связи

Бурятский филиал ФГОБУ ВПО СибГУТИ

Кафедра: «Информатики и ВТ»

Реферат

 

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

 

По дисциплине: Операционные системы

 

 

 

 

 

 

 

 

 

 

Выполнил:

Ст.группы:  И-111

Плотников Г.

Проверила:

Белоусова М.В.

 

 

 

 

 

 

 

 

 

Улан-Удэ

2013

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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