Лекция 1. Введение в сетевые ОС (стр. 6 )

Физическая организация файлов

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

· скорость доступа к данным;

· объем адресной информации файла;

· степень фрагментированности дискового пространства;

· максимально возможный размер файла.

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

Второй метод состоит в представлении файла в виде связного списка блоков, когда в начале каждого блока находится ссылка на следующий. Адресная информация при этом минимальна, необходимо хранить только адрес первого блока файла, фрагментация на уровне блоков отсутствует, так как такой метод позволяет использовать каждый блок диска. Недостатком метода является крайне медленная скорость произвольного доступа, так как для получения доступа к блоку N требуется прочитать N-1 дисковых блоков до него. Кроме того, подобная схема приводит к уменьшению полезного размера каждого блока на несколько байт. Этот негативный эффект особенно заметен при работе с теми программами, которые пишут данные на диск пакетами размером степени двух (для размещения данных в одном блоке будет не хватать именно тех нескольких байтов, которые расходуются на хранение ссылки на следующий блок).

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

Рис. 7.2. Таблица размещения файлов

Такая таблица называется FAT-таблицей (File Allocation Table). Подобная схема позволяет использовать для хранения данных весь блок, кроме того, произвольный доступ становится гораздо быстрее, адресная информация файла минимальна. Основной недостаток заключается в том, что вся таблица должна постоянно находиться в памяти (для 20-гигабайтного диска с размером блока в 1 Кбайт – 2*106*4 = 80 Мбайт). Местом ее размещения может быть и виртуальная память, но и в этом случае ее размер является достаточным, кроме того, постоянное обращение к диску для чтения страниц таблицы, отсутствующих в памяти, также привело бы к определенным задержкам в работе.

Последний метод отслеживания принадлежности блоков дискам состоит в связывании с каждым файлом структуры данных фиксированного размера, называемой i-узлом (индексом), содержащей атрибуты (идентификатор владельца, тип файла, права доступа к файлу, временные характеристики, число ссылок на индекс, размер файла) и адреса дисковых блоков. Большое преимущество данной схемы заключается в том, что конкретный индекс находится в памяти только тогда, когда соответствующий ему файл открыт. С данным методом связана проблема ограниченности размера индекса: в нем может не хватить места для хранения всех блоков файла, если тот достаточно велик. Решение состоит в резервировании части места в индексе для хранения адресов не блоков файла, а блоков, содержащих адреса блоков файла, другими словами, – организации косвенной адресации (рис. 7.3).

Рис. 7.3. Косвенная адресация блоков в индексе

Физическая организация каталогов

При работе с файлом ОС использует указанное пользователем имя, чтобы найти запись файла в каталоге. Запись в каталоге необходима для нахождения блоков файла, и в зависимости от системы это могут быть адрес начального блока файла и размер (для непрерывных файлов), номер первого блока файла (обе схемы связных списков) или номер i-узла. Во всех случаях основная функция системы каталогов заключается в преобразовании ASCII-имени в информацию, необходимую для нахождения данных.

Кроме адресной информации, ФС должна хранить атрибуты файла. Один из возможных вариантов заключается в помещении атрибутов прямо в каталоговую запись (так поступает, например, ФС FAT-16, FAT-32). Каталог при этом состоит из списка элементов фиксированной длины по одному на файл, содержащих имена файлов, их структуру атрибутов, а также один или несколько адресов блоков.

ФС на основе i-узлов хранят атрибуты в i-узлах, а не в записях каталога. В этом случае каталог содержит только пары «имя файла – номер узла».

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

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

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

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

В некоторых ФС, например FAT-32, длинные имена поддерживаются путем их хранения в нескольких записях каталога, каждая из которых имеет фиксированный размер.

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

Лекция 8. Примеры ФС

ФС CD-ROM (ISO 9660)

ФС для хранения данных на компакт-дисках являются самыми простыми, так как создавались для носителей, запись на которые осуществляется только один раз. Кроме того, в этих ФС отсутствует учет свободных блоков.

У CD-ROM нет концентрических цилиндров, как у магнитных дисков. Вместо этого они содержат непрерывную спираль, на которой последовательно размещены все биты (хотя перемещение поперек спирали также возможно), разделенные на логические сектора по 2352 байта, полезная нагрузка которых составляет 2048 байт.

Каждый диск начинается с 16 блоков, функция которых не определена стандартом ISO (эта область может использоваться, например, для размещения загрузчика ОС). Идущий следующим блок представляет собой основной дескриптор тома, содержащий общую информацию о диске: идентификатор системы (32 байта), идентификатор тома (32 байта), идентификатор издабайт), идентификатор компоновщика диска (128 байт). Эти поля могут быть заполнены произвольным образом, но содержат только символы верхнего регистра, цифры и ограниченное множество знаков препинания. Кроме того, дескриптор содержит имена трех файлов, в которых могут храниться краткий обзор, уведомление об авторских правах и библиографическая информация, а также некоторые характеристики диска: размер логического блока (от 2048 и больше), количество блоков на диске, дата создания и истечения годности диска, а также дескриптор корневого каталога (который позволяет найти его на диске).

Корневой и все вложенные каталоги могут иметь переменное количество записей, последняя из которых помечена специальным битом. Сами записи в каталоге имеют переменную длину и содержат от 10 до 12 полей, часть из которых представлена ASCII-строками, а часть – двоичными полями. Двоичные поля кодируются дважды: один раз в формате процессора Pentium (сначала младшие байты, затем старшие), другой – в формате процессора SPARC (сначала старшие байты, затем младшие).

Формат записи каталога представлен на рис. 8.1. Поскольку длина записи переменная, то первое поле записи содержит ее длину. Записи каталогов могут иметь расширенные атрибуты, и если они присутствуют, то второе поле содержит длину записи расширенных атрибутов.

Рис. 8.1. Структура записи каталога файловой системы ISO 9660

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

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

Поле CD # указывает расположение файла на дисках из набора. Используется, например, при создании диска-оглавления.

Поле L содержит длину имени файла в байтах. Само имя состоит из базового имени, точки, расширения и версии файла. В базовом имени (до 8 символов) и расширении (до 3 символов) могут использоваться прописные символы, цифры от 0 до 9 и символ подчеркивания. Имя файла может встречаться несколько раз, но с различными номерами версий.

Поле «заполнение» выравнивает размер записи каталога по двухбайтовой границе.

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

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

Стандарт ISO определяет 3 уровня жесткости требований:

· уровень 1 - характеризуется самыми жесткими ограничениями, имена файлов ограничиваются схемой 8 + 3, имена каталогов – до восьми символов без расширения, кроме того, файлы на диске должны быть непрерывными;

· уровень 2 - ослабляет ограничение на длину имени до 31 символа;

· уровень 3 - ослабляет ограничение на длину имени до 31 символа, кроме того, файл может состоять из нескольких разделов, каждый из которых является непрерывной последовательностью блоков. Одна и та же последовательность может несколько раз встречаться в одном файле или входить в разные файлы.

К стандарту ISO были предложены два дополнительных расширения, по-своему интерпретирующих значение неопределенного поля «SYS»:

· Рок-Ридж было разработано для того, чтобы файловая система UNIX могла быть записана на компакт-диск. Оно позволяет задавать для файла POSIX-атрибуты (права доступа, ID пользователя, группы и т. д.), символьные связи и альтернативные имена, записи специальных файлов, а также устраняет ограничение на максимальную вложенность каталогов;

· Joliet было разработано Microsoft для того, чтобы на диск могла записываться файловая система Windows. Основными нововведениями были:

1) длинные имена файлов;

2) поддержка в именах файлов набора символов Unicode;

3) глубина вложенности более восьми каталогов;

4) имена каталогов могут иметь расширения.

ФС CP/M

ФС использовалась для персональных компьютеров Intel 8080, имеющих ОЗУ объемом 4 Кбайта и дисковод для дисков объемом 180 Кбайт. Принципы, заложенные в ФС CP/M, во многом были унаследованы ФС MS-DOS.

Система поддерживает всего один каталог, содержащий записи фиксированного размера по 32 байта, в котором перечислены все файлы ФС (размеры самого каталога могли различаться в разных версиях системы). При загрузке компьютера система считывает каталог и рассчитывает битовый массив занятых и свободных блоков. Размер блока на диске равен одному килобайту, поэтому массив занимает в памяти 23 байта.

Каталог не хранится в памяти постоянно, а открывается для поиска в нем записи файла при обработке системного вызова open. Формат записи каталога представлен на рис. 8.2.

Рис. 8.2. Формат записи каталога ФС CP/M

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

Размер имени – до 8 символов, расширение – до 3.

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

Последние 16 полей содержат адреса логических блоков, занимаемых файлом (если размер блока – 1 Кбайт, то максимальный размер файла – 16 Кбайт). Так как физические сектора диска имеют размер 128 байт, а размер логического блока – 1 Кбайт, то файлам выделяются фрагменты по 8 секторов.

Для преодоления ограничения в 16 Кбайт для хранения файлов большего размера занимаются две (три и более) записи каталога: первая запись содержит номера первых 16 блоков файла, вторая – блоки от 17 до 32, и т. д. Порядковый номер записи каталога хранится в поле экстента (термин обозначает дополнительную запись), по значению которого ФС может выстроить блоки в нужном порядке.

ФС MS-DOS

ФС MS-DOS представляет собой преемницу ФС CP/M: имена файлов также ограничены схемой 8 + 3, первая версия MS-DOS также имела только один каталог. Однако, начиная с MS-DOS 2.0, ФС была значительно расширена, наиболее важным из улучшений был при этом переход на иерархическую организацию системы каталогов. В то же время из MS-DOS была изъята поддержка разных пользователей. По этой причине любой вошедший в систему пользователь получал доступ ко всем файлам.

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

Ограниченным является только размер главного каталога, размер же остальных – переменный, но записи используются одинакового размера – 32 байта, их структура показана на рис. 8.3.

Рис. 8.3. Формат записи каталога ФС MS-DOS

Имя файла выравнивается по левому краю пробелами.

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

В записи каталога хранится точный размер файла в байтах, под поле размера отводится 4 байта, что позволяло бы поддерживать файлы размером до 4 Гбайт.

Нововведением в ФС MS-DOS по отношению к ФС CP/M является то, что номера дисковых блоков хранятся не в записях каталога, а в таблице размещения файлов, постоянно находящейся в ОЗУ (в записи каталога хранится только номер первого блока файла).

Таблица размещения файлов имеет размер равный 65 535 элементам. Во всех модификация ФС MS-DOS размер дискового блока в байтах может быть установлен кратным 512. FAT-16 поддерживает блоки до 32 Кбайт, таким образом, максимальный размер дискового раздела равен 32*64 Кбайта = 2Гбайта. Файловая система FAT-32 использует 28-разрядные (а не 32-разрядные адреса), что позволяет увеличить максимальный размер дискового раздела до 2 Тбайт, а для разделов меньшего размера использовать более мелкие блоки.

ФС MS-DOS использует FAT также для учета свободных блоков, т. е. хранение информации о свободных блоках в виде битового массива или списка блоков не требуется. Недостатком является то, что FAT должна постоянно находиться в памяти.

ФС WINDOWS 98

В ОС Windows 95 OSR2, а затем Windows 98 и Windows ME была применена новая модификация ФС FAT-16, поддерживающая диски большего размера и длинные имена файлов – FAT-32.

Поддержка длинных имен файлов могла быть обеспечена двумя способами: изменением формата записи каталога (что выразилось бы в несовместимости с предыдущими версиями ФС), разработкой специальной системы хранения и интерпретации длинных имен в прежних записях каталога. Для обеспечения совместимости в FAT-32 был выбран второй вариант.

В записи каталога FAT-16 оставались незадействованными 10 байт, которые и были использованы в FAT-32 (рис. 8.4).

Рис. 8.4. Формат записи каталога FAT-32

Поле NT предназначено для совместимости с Windows NT и обеспечивает отображение имени файла в правильном регистре.

Поле «Дата/время создания» хранит дату создания файла с точностью до 10 мс.

Поле «Дата последнего доступа» хранит только дату (но не время) последнего обращения к файлу.

Так как в FAT-32 используются 32-битные адреса дисковых блоков, то и номер начального блока теперь должен занимать не 2 байта, а 4.

Для хранения длинных имен файлов предложен следующий способ: для каждого файла создается два имени, одно из которых совместимое со старой версией ФС, другое – длинное в формате Unicode.

Короткое имя образуется от длинного взятием первых 6 символов, переводом их в верхний регистр, удалением пробелов и лишних точек, заменой некоторых символов знаками подчеркивания и добавлением суффиксов ~1, ~2 и т. д. Полученное имя хранится в дескрипторе каталога.

Если у файла есть также и длинное имя, то оно хранится в одной или нескольких записях (по аналогии с экстентом в ФС CP/M), предшествующих дескриптору с коротким именем файла. Каждая запись в таком случае имеет отличную структуру и может хранить до 13 двухбайтных символов Unicode (рис. 8.5).

Рис. 8.5. Формат записи каталога ФС FAT-32 с фрагментом длинного имени

Для отличия записей каталога с фрагментами длинного имени от записи с коротким именем ФС применяет значение поля «Атрибуты» 0x0F, что соответствует невозможной комбинации атрибутов для дескриптора файла в ФС MS-DOS. Старые программы игнорируют подобные записи. Порядок следования фрагментов учитывается в первом байте, при этом последний фрагмент имеет порядковый номер, увеличенный на 64. Поле контрольной суммы предназначено для обнаружения ошибок, которые могут возникнуть по причине того, что старые версии программ повредят записи с длинными именами. Пример хранения длинного и короткого имен файла «One, one, one – little dog run, Two, two, two – cat see you!.doc» в каталоге приведены на рис. 8.6 (пробелы отмечены с помощью знака подчеркивания).

Рис. 8.6. Пример хранения длинного имени файла в FAT-32

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