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

Наиболее простой файловой системой можно считать структуру, создаваемую архиватором системы UNIX — программой tar (Tape ARchive — архив на [магнитной] ленте). Этот архиватор просто пишет файлы один за другим помещая в начале каждого файла заголовок с его именем и длиной (рис. 11.5). Аналогичную структуру имеют файлы, создаваемые архиваторами типа arj; в отличие от них, tar не упаковывает файлы.

Рис. 11.5. Структура архива tar

Для поиска какого-то определенного файла вы должны прочитать первый заголовок; если это не тот файл, то отмотать ленту до его конца, прочитать новый заголовок и т. д. Это не очень удобно, если мы часто обращаемся к отдельным файлам, особенно учитывая то, что цикл перемотка — считывание — перемотка у большинства лентопротяжных устройств происходит намного медленнее, чем простая перемотка. Изменение же длины файла в середине архива или его стирание вообще превращается в целую эпопею. Поэтому tar используется для того чтобы собрать файлы с диска в некую единую сущность, например, для передачи по сети или для резервного копирования, а для работы файлы обычно распаковываются на диск или другое устройство с произвольным доступом.
Для того чтобы не заниматься при каждом новом поиске просмотром всего устройства, удобнее всего разместить каталог в определенном месте, например в начале ленты. Наиболее простую, из знакомых автору, файловую систему такого типа имеет ОС RT-11. Это единственная известная автору файловая система, которая с одинаковым успехом применялась как на лентах, так и на устройствах с произвольным доступом. Все более сложные ФС, обсуждаемые далее, используются только на устройствах произвольного доступа. В наше время наиболее распространенный тип запоминающего устройства произвольного доступа — это магнитный или оптический диск, поэтому далее в тексте мы будем называть такие устройства просто дисками — для краткости, хотя такое сокращение и не вполне корректно.
В этой ФС, как и во всех обсуждаемых далее, место на диске или ленте выделяется блоками. Размер блока, как правило, совпадает с аппаратным размером сектора (512 байт у большинства дисковых устройств), однако многие фС могут использовать логические блоки, состоящие из нескольких секторов (так называемые кластеры).
Использование блоков и кластеров вместо адресации с точностью до байта обусловлено двумя причинами. Во-первых, у большинства устройств произвольного доступа доступ произволен лишь с точностью до сектора, т. е. нельзя произвольно считать или записать любой байт — нужно считывать или записывать весь сектор целиком. Именно поэтому в системах семейства Unix такие устройства называются блочными (block-oriented).
Во-вторых, использование крупных адресуемых единиц позволяет резко увеличить адресуемое пространство. Так, используя 16-битный указатель, с точностью до байта можно адресовать всего 64 Кбайт, но если в качестве единицы адресации взять 512-байтовый блок, то объем адресуемых данных сможет достичь 32 Мбайт; если же использовать кластер размером 32 Кбайт, то можно работать с данными объемом до 2 Гбайт. Аналогично, 32-битовый указатель позволяет адресовать с точностью до байта 4 Гбайт данных, т. е. меньше, чем типичный современный жесткий диск; но если перейти к адресации по блокам, то адресное пространство вырастет до 2 Тбайт, что уже вполне приемлемо для большинства современных запоминающих устройств.
Таким образом, адресация блоками и кластерами позволяет использовать в системных структурах данных короткие указатели, что приводит к уменьшению объема этих структур и к снижению накладных расходов. Под накладными расходами в данном случае подразумевается не только освобождение дискового пространства, но и ускорение доступа: структуры меньшего размера быстрее считываются, в них быстрее производится поиск и т. д. Однако увеличение объема кластера имеет оборотную сторону — оно приводит к внутренней фрагментации (см. разд. Алгоритмы динамического управления памятью).
Ряд современных файловых систем использует механизм, по-английски называемый block siiballocation, т. е. размещение частей блоков. В этих ФС кластеры имеют большой размер, но есть возможность разделить кластер на несколько блоков меньшего размера и записать в эти блоки "хвосты" от нескольких разных файлов (рис. 11.6). Это, безусловно, усложняет ФС, но позволяет одновременно использовать преимущества, свойственные и большим, и маленьким блокам. Поэтому ряд распространенных ФС, например файловая система Novell Netware 4.1 и FFS (известная также как UFS и Berkley FS), используемая во многих системах семейства Unix, применяе этот механизм.

Рис. 11.6. Субаллокация блоков

Субаллокация требует от файловой системы поддержания запаса свободных блоков на случай, если пользователю потребуется увеличить длину одного из файлов, "хвост" которого был упакован во фрагментированный блок. Учебные пособия по Netware рекомендуют поддерживать на томах с субаллокацией не менее тысячи свободных кластеров, но не предоставляют штатных методов обеспечения этого требования. Напротив, UFS показывает свободное место на диске с учетом "неприкосновенного" резерва свободного пространства, так что нулевое показываемое свободное пространство соответствует 5% или 10% физического свободного места. Объем этого резерва настраивается утилитами конфигурации ФС.
Но вернемся к простым файловым системам. В RT-11 каждому файлу выделяется непрерывная область на диске. Благодаря этому в каталоге достаточно хранить адрес первого блока файла и его длину, также измеренную в блоках. В RT-11 поступили еще проще: порядок записей в каталоге совпадает с порядком файлов на диске, и началом файла считается окончание предыдущего файла. Свободным участкам диска тоже соответствует запись в каталоге (рис. 11.7). При создании файла система ищет первый свободный участок подходящего размера.
Фактически эта структура отличается от формата tar только тем, что каталог вынесен в начало диска, и существует понятие свободного участка внутри области данных. Эта простая организация имеет очень серьезные недостатки.

1. 1. При создании файла программа должна указать его длину. Часто это бывает затруднительно. Особенно неудобно увеличивать размер уже созданного файла. Точнее, это просто невозможно: вместо удлинения старого файла приходится создавать новый файл нужной длины и копировать содержимое старого файла в него.
2. 2. При хаотическом создании и удалении файлов возникает проблема фрагментации свободного пространства. Для ее решения существует специальная программа SQUEESE (сжать [диск]), которая переписывает файлы г так, чтобы объединить все свободные фрагменты (рис. 11.8). Эта программа требует много времени, особенно для больших дисковых томов, и потенциально опасна: если при ее исполнении произойдет сбой системы (а с машинами третьего поколения такое случалось по нескольку раз в день), то значительная часть данных будет необратимо разрушена.

Рис. 11.7. Структура файловой системы RT-11

Рис. 11.8. Дефрагментация диска в RT-11

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

Рис. 11.9. Файл в виде односвязного списка блоков

Отчасти похожее решение было реализовано в MS DOS и DR DOS. Эти системы создают на диске таблицу, называемую FAT (File Allocation Table, таблица размещения файлов). В этой таблице каждому блоку, предназначенному для хранения данных, соответствует 12-битовое значение. Если блок свободен, то значение будет нулевым. Если же блок принадлежит файлу, то значение равно адресу следующего блока этого файла. Если это последний блок в файле, то значение — OxFFF (рис. 11.10). Существует также специальный код для обозначения плохого (bad) блока, не читаемого из-за дефекта физического носителя. В каталоге хранится номер первого блока и длина файла, измеряемая в байтах.
Емкость диска при использовании 12-битовой FAT оказывается ограничена 4096 блоками (2 Мбайт), что приемлемо для дискет, но совершенно не годится для жестких дисков и других устройств большой емкости. На таких устройствах DOS использует FAT с 16-битовыми элементами. На еще больших (более 32 Мбайт) дисках DOS выделяет пространство не блоками. а кластерами из нескольких блоков. Эта файловая система так и называется - FAT.
Она очень проста и имеет одно серьезное достоинство: врожденную устойчивость к сбоям (fault tolerance), но об этом далее. В то же время у нее есть и ряд серьезных недостатков.

Рис. 11.10. Структура файловой системы FAT

Первый недостаток состоит в том, что при каждой операции над файлами система должна обращаться к FAT. Это приводит к частым перемещениям головок дисковода и в результате к резкому снижению производительности. Действительно, исполнение программы arj на одной и той же машине под MS DOS и под DOS-эмулятором систем Unix или OS/2 различается по скорости почти в 1,5 раза. Особенно это заметно при архивировании больших каталогов.
Использование дисковых кэшей, а особенно помещение FAT в оперативную память, существенно ускоряет работу, хотя обычно FAT кэшируется только для чтения ради устойчивости к сбоям. При этом мы сталкиваемся со специфической проблемой: чем больше диск, тем больше у него FAT, соответственно, тем больше нужно памяти. У тома Novell Netware 3.12 размером 1,115 Гбайт с размером кластера 4 Кбайт размер FAT достигает мегабайта (легко понять, что Netware использует FAT с 32-разрядными элементами. При 16-разрядном элементе FAT дисковый том такого объема с таким размером кластера просто невозможен). При монтировании такого тома Netware занимает под FAT и кэш каталогов около 6 Мбайт памяти.
Для сравнения, Netware 4 использует субаллокацию, поэтому можно относительно безнаказанно увеличивать объем кластера и нет необходимости делать кластер таким маленьким. Для дисков такого объема Netware 4 устанавливает размер кластера 16 Кбайт, что приводит к уменьшению всех структур данных в 4 раза. Понятно, что для MS DOS, которая умеет адресовать всего 1 Мбайт (1088 Кбайт, если разрешен НМА), хранить такой FAT в памяти целиком просто невозможно.
Разработчики фирмы MicroSoft пошли другим путем: они ограничили разрядность элемента FAT 16 битами. При этом размер таблицы не может превышать 128 Кбайт, что вполне терпимо. Зато вся файловая система может быть разбита только на 64 Кбайт блоков. В старых версиях MS DOS это приводило к невозможности создавать файловые системы размером 32 Мбайт.
В версиях старше 3.11 появилась возможность объединять блоки в кластеры Например, на дисках размером от 32 до 64 Мбайт кластер будет состоять из 2 блоков и иметь размер 1 Кбайт. На дисках размером 128—265 Мбайт кластер будет уже размером 4 Кбайта и т. д.
Windows 95 использует защищенный режим процессора х86, поэтому адресное пространство там гораздо больше одного мегабайта. Разработчики фирмы Microsoft решили воспользоваться этим и реализовали версию FAT с 32-битовым элементом таблицы — так называемый FAT32. Однако дисковый кэш Windows 95 не стремится удержать весь FAT в памяти; вместо этого FAT кэшируется на общих основаниях, наравне с пользовательскими данными. Поскольку работа с файлами большого (больше одного кластера) объема требует прослеживания цепочки элементов FAT, а соответствующие блоки таблицы могут не попадать в кэш, то производительность резко падает. В сопроводительном файле Microsoft признает, что производительность FAT32 на операциях последовательного чтения и записи может быть в полтора раза ниже, чем у кэшированного FAT 16.
В заключение можно сказать, что при использовании FAT на больших дисках мы вынуждены делать выбор между низкой производительностью, потребностями в значительном объеме оперативной памяти или большим размером кластера, который приводит к существенным потерям из-за внутренней фрагментации.
Для эффективного управления большими объемами данных необходимо что-то более сложное, чем FAT.