Наиболее простой файловой системой можно считать структуру, создаваемую архиватором системы UNIX — программой tar (Tape ARchive — архив на [магнитной] ленте). Этот архиватор просто пишет файлы один за другим помещая в начале каждого файла заголовок с его именем и длиной (рис. 11.5). Аналогичную структуру имеют файлы, создаваемые архиваторами типа arj; в отличие от них, tar не упаковывает файлы.
Рис. 11.5. Структура архива tar
Для поиска какого-то определенного файла вы должны прочитать первый
заголовок; если это не тот файл, то отмотать ленту до его конца, прочитать
новый заголовок и т. д. Это не очень удобно, если мы часто обращаемся
к отдельным файлам, особенно учитывая то, что цикл перемотка — считывание
— перемотка у большинства лентопротяжных устройств происходит намного
медленнее, чем простая перемотка. Изменение же длины файла в середине
архива или его стирание вообще превращается в целую эпопею. Поэтому tar
используется для того чтобы собрать файлы с диска в некую единую сущность,
например, для передачи по сети или для резервного копирования, а для работы
Рис. 11.6. Субаллокация блоков
Субаллокация требует от файловой системы
поддержания запаса свободных блоков на случай, если пользователю потребуется
увеличить длину одного из файлов, "хвост" которого был упакован
во фрагментированный блок. Учебные пособия по Netware рекомендуют поддерживать
на томах с субаллокацией не менее тысячи свободных кластеров, но не предоставляют
штатных методов обеспечения этого требования. Напротив, UFS показывает
свободное место на диске с учетом "неприкосновенного" резерва
свободного пространства, так что нулевое показываемое свободное пространство
соответствует 5% или 10% физического свободного места. Объем этого резерва
настраивается утилитами конфигурации ФС.
Но вернемся к простым файловым системам. В RT-11 каждому файлу выделяется
непрерывная область на диске. Благодаря этому в каталоге достаточно хранить
адрес первого блока файла и его длину, также измеренную в блоках. В RT-11
поступили еще проще: порядок записей в каталоге совпадает с порядком файлов
на диске, и началом файла считается окончание предыдущего файла. Свободным
участкам диска тоже соответствует запись в каталоге (рис. 11.7). При создании
файла система ищет первый свободный участок подходящего размера.
Фактически эта структура отличается от формата tar только тем, что каталог
вынесен в начало диска, и существует понятие свободного участка внутри
области данных. Эта простая организация имеет очень серьезные недостатки.
Рис. 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.