Физическая структура файлов

7.6. Физическая структура файлов

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

Несколько принципиально важных положений являются общими для любых способов управления дисковой памятью.

Дисковая память состоит из блоков, являющихся единицами распределения дискового пространства (например, секторов). Каждый блок имеет уникальный номер (адрес), его идентифицирующий. В каждый блок может быть записана любая информация достаточно сложной структуры, в том числе, и содержащая ссылки на другие блоки.
Каждый физический диск описывается дескриптором диска, который содержит информацию о количестве и размере блоков на диске и о свободном пространстве на диске. Дисковый дескриптор записывается на известное заранее место на диске (чаще всего - в первый блок).
Каждый файл в составе своего дескриптора имеет план своего размещения (layuot) на физическом пространстве диска.
Информация, записываемая на диск, может быть избыточной для обеспечения возможности ее восстановления при сбоях.
Дисковое пространство распределяется блоками фиксированной длины. Даже в тех дисковых архитектурах, которые допускают чтение/запись блоками переменной длины, размер единицы распределения, как правило, все равно фиксирован, например, дорожка. Возможно объединение в единицу распределения нескольких смежных блоков, такой прием носит название кластеризации (clastering), а порции распределения, состоящие из нескольких блоков, называются кластерами. Кластеризация может быть как симметричной - с заранее установленным размером кластера, так и асимметричной - с размером кластера, выбираемым для каждого распределения.
Поиск на диске управляющих структур ФС и свободных блоков может оказаться слишком времяемким. Поэтому те управляющие структуры, обращение к которым происходит наиболее часто, обычно копируются в оперативную память. Это создает дополнительные проблемы, связанные с надежностью функционирования ОС. При крахе системы изменения в управляющих структурах могут не быть перенесены из кеша на внешнюю память. Специальные системные процессы ОС обычно обеспечивают периодическое сохранение управляющих структур на внешней памяти.

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

Распределение дисковой памяти может быть классифицировано как смежное или не смежное. В первом случае файлу распределяется непрерывный участок внешней памяти, во втором - файл может быть разбросан по пространству диска. Смежное распределение весьма привлекательно по нескольким причинам. Во-первых, план размещения в этом случае получается простейшим: он состоит только из номера начального блока и количества блоков. Во-вторых, и это более важно, смежное размещение обеспечивает высокую степень локализации обращений к дорожкам при обработке файла и, следовательно, высокую эффективность обмена. Однако, и недостатки смежного распределения более чем серьезны. Во-первых, как и при распределении оперативной памяти блоками переменной длины, здесь возникают все проблемы фрагментации пространства памяти (внешних дыр). Во-вторых, такое распределение требует, чтобы необходимый размер дискового пространства указывался при создании файла - эта информация не всегда может быть предоставлена пользователем, создающим файл. В-третьих, расширение файла за пределы установленного размера невозможно - для файлов с длительным сроком существования эта проблема может стать критической. Перечисленные недостатки могут быть не радикально преодолены, но несколько сглажены, если допустить, чтобы файл занимал не один, а несколько участков дискового пространства. При создании такого файла задаются требования к размеру первичного и вторичного распределения. Файлу выделяется непрерывный участок памяти в соответствии с первичным размером. Если далее оказывается, что файл не помещается в первичный участок, ему выделяется дополнительный участок (экстент - extent), размер которого задается требованием ко вторичному распределению. Экстент занимает непрерывную область на диске, но необязательно смежную с первичным участком. Затем может быть выделен второй экстент и т.д. План файла в его дескрипторе в этом случае представляется массивом пар "начальный адрес - длина", каждый элемент которого соответствует одному экстенту. Размер этого массива в дескрипторе ограничивает допустимое число экстентов.

Очевидно, что смежное распределение является негибким. Это в первую очередь послужило причиной полного отказа от него в ОС Unix и в MS DOS. Однако, в связи с увеличением объемов дисковых накопителей вопросы повышения эффективности обмена приобретают все большее значение и локализация файлов является хорошим средством повышения этой эффективности. В последнее время наметилась тенденция к размещению файлов в смежных областях диска, пусть даже и в рамках несмежной модели распределения (см., например описание ФС HPFS, NTFS, Veritas, JFS в Части II).

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

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

списки блоков;
карта размещения;
списки указателей на блоки.

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

Метод карты размещения хорошо известен программистам в MS DOS по Таблице размещения файлов FAT. ФС для каждого диска поддерживает таблицу, каждая строка которой описывает один блок на диске. В списки связываются не сами блоки, а соответствующие им элементы карты. Карта размещения обеспечивает достаточно простой и эффективный метод управления распределением, но сосредоточение информации о размещении всех файлов в одной структуре данных делает эту структуру узким местом ФС с точки зрения безопасности.

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

Учет дискового пространства, выделенного файлу (план размещения), ведется в s5 следующим образом. Как показали исследования, на любом носителе всегда есть большое число файлов, объем которых не превышает 1 Кбайт. Для таких файлов нет никакой необходимости выделять отдельные блоки для размещения плана, а тем более - увязывать эти блоки в какие-либо списки. Поэтому непосредственно в файловом дескрипторе содержится массив из 10 номеров первых блоков файла. При размере блока 512 байт первые 5 Кбайт файла адресуются непосредственно из файлового дескриптора. Одиннадцатый элемент этого массива содержит адрес блока, в котором записано еще 128 номеров следующих блоков файла. Таким образом, доступ к следующим 64 Кбайтам файла производится путем косвенной адресации из дескриптора через этот блок адресов. Двенадцатый элемент содержит адрес блока, в котором записано еще 128 номеров блоков, каждый из которых адресует еще 128 блоков данных файла - это обеспечивает доступ к следующим 8 Мбайтам путем двухуровневой косвенной адресации. Наконец, тринадцатый элемент массива в дескрипторе обеспечивает доступ через трехуровневую косвенную адресацию еще к 2 Гбайтам файла. Структура плана размещения показана на Рисунке 7.4.

Содержание раздела