Простые файловые системы

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

Наиболее простой файловой системой можно считать структуру, создаваемую архиватором системы UNIX – программой tar. Этот архиватор просто пишет файлы один за другим, помещая в начале каждого файла заголовок с его именем и длиной. Аналогичную структуру имеют файлы, создаваемые архиваторами типа arj. Для поиска какого-то определенного файла вы должны прочитать первый заголовок; если это не тот файл, прочитать новый заголовок и т.д.

Наиболее простая файловая система такого типа ОС RT-11 с одинаковым успехом применялась как на лентах, так и на устройствах с произвольным доступом. В этой ФС место на диске или ленте выделяется блоками. Размер блока, как правило, совпадает с аппаратным размером сектора (512 байт у большинства дисковых устройств), однако многие ФС могут использовать логические блоки, состоящие из нескольких секторов (так называемые кластеры).

Использование блоков и кластеров

Использование блоков и кластеров вместо адресации с точностью до байта обусловлено двумя причинами.

• у большинства устройств произвольного доступа доступ произволен лишь с точностью до сектора, т.е. нельзя произвольно считать или записать любой байт – нужно считывать или записывать весь сектор целиком. Именно поэтому в системах семейства Unix такие устройства называются блочными (block-oriented).
• использование кластеров увеличивает адресуемое пространство. Так, используя 16-битный указатель, с точностью до байта можно адресовать всего 64 Кбайт, но если в качестве единицы адресации взять 512-битовый блок, то объем адресуемых данных сможет достичь 32 Мбайт; если же использовать кластер размером 32 Кбайт, то можно работать с длинными именами объемом до 2 Гбайт. и т.д.

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

Механизм субаллокации блоков

Ряд современных файловых систем использует механизм, по-английски называемый block suballocation, т.е. размещение частей блоков. В этих ФС кластеры имеют большой размер, но есть возможность разделить кластер на нескольких блоков меньшего размера и записать в эти блоки «хвосты» от нескольких разных файлов. Это, безусловно, усложняет ФС, но позволяет одновременно использовать преимущества, свойственные и большим, и маленьким блокам. Поэтому ряд распространенных ФС, например файловая система Nowell Netware 4.1 и FFS (известная также как UFS иBerkly FS), используемая во многих семействах Unix, применяет этот механизм. Субаллокация требует от файловой системы поддержания запаса свободных блоков на случай, если пользователю потребуется увеличить длину одного из файлов, «хвост» которого был упакован во фрагментированный блок.

Выделение памяти

В простейшей файловой системе каждому файлу выделяется непрерывная область на диске. Благодаря этому в каталоге достаточно хранить адрес первого блока файла и его длину, также измеренную в блоках. В RT-11 поступили еще проще: порядок записей в каталоге совпадает с порядком файлов на диске, и началом файла считается окончание предыдущего файла. Свободным участкам диска тоже соответствует запись в каталоге, при создании файла система ищет первый свободный участок подходящего размера.

Эта простая организация имеет очень серьезные недостатки:

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

2. При хаотическом создании и удалении файлов возникает проблема фрагментации свободного пространства. Для ее решения существует специальная программа, которая переписывает файлы так, чтобы объединить все свободные фрагменты. Эта программа требует много свободного времени, особенно для больших дисковых томов, и потенциально опасна: если при ее использовании произойдет сбой системы, то значительная часть данных будет необратимо разрушена.

Для того чтобы решить обе эти проблемы, необходимо позволить файлам занимать несмежные области диска. Наиболее простым решением было бы хранить в конце каждого блока файла указатель на следующий, т.е. превратить файл в связанный список блоков. При этом, естественно, в каждом блоке хранить не 512 байт данных, а на 2 – 4 байта меньше.

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

Отчасти похожее решение было реализовано в MS DOS. Эта система создает на диске таблицу FAT (File Allocation Table, таблица размещения файлов). В этой таблице каждому блоку, предназначенному для хранения данных, соответствует 12(16; 32)-битовое значение. Если блок свободен, то значение будет нулевым. Если же блок принадлежит файлу, то значение равно адресу следующего блока этого файла. Если это последний блок в файле, то значение – 0хFFF (рис.10). существует специальный код для обозначения плохого (bad) блока, не читаемого из-за дефекта физического носителя. В каталоге хранятся номер первого блока и длина файла, измеряемая в байтах. Эта файловая система так и называется – FAT. Она очень проста и имеет одно серьезное достоинство: врожденную устойчивость к сбоям (fault tolerance).. В то же время у нее есть и ряд серьезных недостатков.

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

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

4.“Сложные” файловые системы

Общие принципы сложных ФС

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

• Наличие суперблока системы
• Минимальная структура каталога
• Наличие специальной структуры (битовая карта, bitmap) со списком свободных блоков
• Увеличение числа системных структур данных за счет специальных таблиц (инодов, файловых записей и пр) с разнообразной информацией о файлах
• Выделение дисковой памяти различными способами, уменьшающими внешнюю фрагментацию (отрезками, блоками)
• Поддержка информационной безопасности, разграничение прав доступа к файлам
• Средства восстановления ФС, использование журнальных ФС с регистрацией намерений
• Поддержка больших дисков и пр. …

Обычно файловая система начинается с заголовка, или, как это называется в системах семейства Unix, суперблока (super block ). Суперблок хранит информацию о размерах дискового тома, отведенного под ФС, указатели на начало системных структур данных и другую информацию, зависящую от типа ФС. Например, для статических структур может храниться их размер. Часто суперблок содержит также магическое число – идентификатор типа файловой системы. Аналог суперблока существует даже в FAT – это так называемая загрузочная запись (boot record).

Практически все современные ФС разделяют список свободных блоков и структуры, отслеживающие размещение файлов.Чаще всего вместо списка свободных блоков используется битовая карта, в которой каждому блоку соответствует один бит: свободен/занят.

Список блоков для каждого файла обычно связан с описателем, который, кажется естественно хранить в каталоге, но их, как правило, выносят в отдельные области, часто собранные в специальные области диска – таблицу инодов, метафайл и т.д. Такое решение уменьшает объем каталога и, соответственно, ускоряет поиск файла по имени. К тому же многие ФС сортируют записи в каталоге по имени файла, также с целью ускорения поиска. Понятно, что сортировка записей меньшего размера происходит быстрее.

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

В файловой системе HPFS, используемой в OS/2 и Windows NT, каждая запись в каталоге содержит имя файла и указатель на fnode (файловую запись). Каталоги в этой ФС организованы в виде В-деревьев и отсортированы по именам файлов.

Файловая запись занимает один блок на диске и содержит список так называемых extent («расширений») – (у этого термина нет приемлемого русского аналога. В переводах документации по OS/360 (OC EC) так и писали: экстент.). каждый экстент описывает непрерывную последовательность дисковых блоков, выделенных файлу. Он задает начальный блок такой последовательности и ее длину. Вместо списка свободных блоков используется битовая карта диска, в которой каждому блоку соответствует один бит: занят/свободен. Нужно отметить, что идея экстентов далеко не нова: аналогичная структура используется в некоторых версиях Unix с начала 80-х годов, а истоки этой идеи теряются в глубине 60-х.

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

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

Еще одно любопытное следствие применения стратегии worst fit заключается в том, что пространство, освобожденное стертым файлом, обычно используется не сразу. Отмечались случаи, когда файл на активно используемом диске удавалось восстановить через несколько дней после стирания.

Экстенты открытых файлов и карта свободных блоков во время работы размещаются в ОЗУ поэтому производительность такой ФС в большинстве ситуации намного (в 1,5-2 раза и больше) выше, чем у FAT с тем же объемом КЭШа, при вполне приемлемых потребностях в памяти и размере кластера 512 байт.

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

ФС Unix. Наиболее интересна структура файловых систем в ОС семейства Unix. В этих ФС каталог не содержит почти никакой информации о файле. Там хранится только имя файла и номер его инода (i-node – по-видимому, сокращение от index node: индексная запись). Иноды всех файлов в данной ФС собраны в таблицу, которая так и называется: таблица инодов. В ранних версиях Unix таблица инодов занимала фиксированное пространство в начале устройства; в современных файловых системах эта таблица разбита на участки, распределенные по диску.

Например, в файловой системе BSD Unix FFS (Fast File System –быстрая файловая система), которая в Unix SVR4 называется просто UFS (Unix File System), диск разбит на группы цилиндров. Каждая группа цилиндров. Каждая группа цилиндров содержит копию суперблока, битовую карту свободных блоков для данного участка и таблицу инодов для файлов, расположенных в пределах этого участка(рис.12). такая распределенная структура имеет два преимущества.

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

Инод хранит информацию о самом файле и его размещении на диске (рис.13).

• Тип файла. Исследуя это поле, можно понять, является данный объект файлом данных или специальным файлом. В этом же поле закодированы права доступа к файлу.
• Идентификаторы владельца файла и группы. Вместе с правами доступа эти два идентификатора образуют список контроля доступа файла.
• Время: создания файла; последней модификации файла; последнего доступа к файлу.

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

Рис. 11. Каталог и файловая запись в HPFS.

суперблок

bitmap

Таблица инодов

Блоки данных

Копия суперблока

bitmap

Таблица инодов

Блоки данных

Копия суперблока

bitmap

Таблица инодов

Блоки данных

Рис.12

Рис. 13. Каталоги и иноды файловых систем семейства Unix.

Структура, описывающая физическое размещение файла на диске, недоступна пользовательским программам. Собственно, формат этой структуры может быть очень разнообразен. Например, в файловой системе Veritas это список элементов, похожий на HPFS; в файловых системах s5, Xenix и FFS это массив из 13 чисел, задающих номера физических блоков файла. Если файл в s5 содержит более десяти блоков (т.е. его длина больше 5 Кбайт), то предпоследние три указателя обозначают не блоки данных, а так называемые косвенные блоки (indirection blocks), в которых хранятся указатели на следующие блоки данных и, возможно, на следующие косвенные блоки.

Наиболее интересная особенность ФС семейства Unix состоит в том, инод не содержит имени файла. С другой стороны, он содержит счетчик связей (link) – ссылок на этот файл из каталогов. Таким образом, на один и тот же инод можно ссылаться из различных каталогов или из одного каталога под разными именами (рис.14). Иными словами, один и тот же файл в этих ФС может иметь несколько различных имен. Именно это и имелось в виду, когда говорилось, что структура каталогов в ОС Unix не обязана быть деревом.

Это свойство предоставляет неоценимые возможности для организации иерархии каталогов, но имеет и некоторые оборотные стороны:

1. создание нескольких связей для каталога потенциально опасно – оно может привести к возникновению кольца, в котором каталог является своим собственным подкаталогом. Отслеживать такую ситуацию сложно, поэтому разработчики ОС Unix запретили создавать дополнительные имена каталогов.
2. удаление файла превращается в проблему: чтобы удалить файл, нужно проследить все его связи. Поэтому UNIX не имеет средств для удаления файла, а обладает только системным вызовом unlink – удалить связь. Когда у файла не остается связей, он действительно удаляется. Этот подход вполне разумен, но также имеет неожиданную оборотную сторону: поскольку теперь стирание файла – это операция не над файлом, а над каталогом, то для удаления файла не нужно иметь никаких прав доступа к нему. Достаточно иметь право записи в каталог.

На практике, механизм защиты от стирания отдельных файлов предусмотрен – при установке в атрибутах каталога так называемого sticky bit(“липкий бит”), система запрещает стирать файлы, для которых вы не имеете права записи, но этот механизм не лишен недостатков.

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

Рис. 14. Жесткие связи вUnix.

Последнее обстоятельство резко уменьшает полезность жесткость связей для организации иерархии каталогов. Эта проблема была осознана еще в 70-е годы, и программисты из группы BSD придумали интересное новое понятие – символическую связь (symbolic link) или symlink.

Символическая связь представляет собой специальный файл. Вместо блоков данных инод такого файла содержит текстовую строку – имя того файла, с которым создана связь (рис.15). это может быть файл из другой файловой системы, в том числе и из такой, которая сама по себе не поддерживает ни жестких дисков, ни символических связей, например, FAT, HPFS или файловый сервер Nowell Netware. Такого файла может и вообще не существовать, например, потому, что его уже удалили, или потому, что файловая система, в которой он находится, не смонтирована, или просто потому, что имя было задано неправильно. Тогда попытки открыть символическую связь будут завершаться неудачей с кодом ошибки «файла не существует». Естественным недостатком символических связей является их относительно низкая «дуракоустойчивость» (fool-tolerance): глупый пользователь может не распознавать ситуации, когда символическая связь указывает в никуда. Зато они обеспечивают полную свободу в размещении и именовании файлов.

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

Рис. 15. Символическая связь.

ФС NTFS подробно описана выше, в разделе «Физическая организация ФС».