Функциональная схема организации файловой системы

Система хранения данных на дисках может быть представлена в виде функциональной схемы (рис. 37). Рассмотрим ее подробнее.

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

Непосредственно с устройствами (дисками) взаимодействует часть ОС, называемая системой ввода-вывода. Система ввода-вывода (она состоит из драйверов устройств и обработчиков прерываний для передачи информации между памятью и дисковой системой) предоставляет в распоряжение более высокоуровневого компонента ОС – файловой системы используемое дисковое пространство в виде непрерывной последовательности блоков фиксированного размера. Система ввода-вывода имеет дело с физическими блоками диска, которые характеризуются адресом – номерами диска, цилиндра и сектора. Файловая система имеет дело с логическими блоками, каждый из которых имеет номер (от 0 или 1 до N). Размер этих логических блоков файла совпадает или кратен размеру физического блока диска и может быть задан равным размеру страницы виртуальной памяти, поддерживаемой аппаратурой компьютера совместно с ОС.

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

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

Взаимодействие прикладной программы с файлом происходит следующим образом. От прикладной программы к логической подсистеме поступает запрос на открытие или создание файла. Логическая подсистема, используя структуру директорий, проверяет права доступа и вы-зывает базовую подсистему для получения доступа к блокам файла. После этого файл считается открытым, содержится в таблице открытых файлов, прикладная программа получает в свое распоряжение дескриптор (в системах Microsoft – handle) этого файла. Дескриптор файла является ссылкой на файл в таблице открытых файлов и используется в запросах прикладной программы на чтение-запись из этого файла. Запись в таблице открытых файлов указывает через систему кэширования блоков диска на блоки данного файла. Если к моменту открытия файл уже используется другим процессом, то есть содержится в таблице открытых файлов, то после проверки прав доступа к файлу может быть организован совместный доступ. При этом новому процессу также возвращается дескриптор файла.

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

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

Выделение непрерывной последовательностью блоков.Простейший способ – хранить каждый файл, как непрерывную последова-тельность блоков диска. При непрерывном расположении файл харак-теризуется адресом и длиной (в блоках). Файл, стартующий с блока b, занимает затем блоки b + 1, b + 2, ... b + n – 1. Этот способ имеет два преимущества:

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

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

Например, непрерывное выделение использовано в ОС IBM/CMS, RSX-11 (для исполняемых файлов).

Основная проблема, в связи с которой этот способ мало распространен – трудности в поиске места для нового файла. В процессе эксплуатации диск представляет собой некоторую совокупность свободных и занятых фрагментов. Проблема непрерывного расположения может рассматриваться как частный случай более общей проблемы выделения n блоков из списка свободных фрагментов. Наиболее распространенные стратегии решения этой проблемы – выбор первого подходящего по размеру блока (англ. first fit), наиболее подходящего, т.е. того, при размещении в котором наиболее тесно (англ. best fit), и наименее подходящего, т.е. выбирается наибольший блок (англ. worst fit).

Способ характеризуется наличием существенной внешней фрагментации (в большей или меньшей степени – в зависимости от размера диска и среднего размера файла). Кроме того, непрерывное распределение внешней памяти не применимо до тех пор, пока не известен макси- мальный размер файла. Иногда размер выходного файла оценить легко (при копировании), но чаще – трудно. Если места не достаточно, то пользовательская программа может быть приостановлена, предполагая выделение дополнительного места для файла при последующем перезапуске. Некоторые ОС используют модифицированный вариант непрерывного выделения: «основные блоки файла» + «резервные блоки». Од- нако с выделением блоков из резерва возникают те же проблемы, так как возникает задача выделения непрерывной последовательности бло- ков диска теперь уже из совокупности резервных блоков.

Выделение связным списком.Метод распределения блоков в виде связного списка решает основную проблему непрерывного выделения, то есть устраняет внешнюю фрагментацию (рис. 39). Каждый файл – связный список блоков диска. Запись в директории содержит указатель на первый и последний блоки файла. Каждый блок содержит указатель на следующий блок.

Хранение файлов в связных списках дисковых блоков

Внешняя фрагментация для данного метода отсутствует. Любой свободный блок может быть использован для удовлетворения запроса.

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

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

 прямым следствием этого является низкая надежность – наличие дефектного блока в списке приводит к потере информации в остаточной части файла и, потенциально, к потере дискового пространства отведенного под этот файл;

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

Распределение связным списком с использованием индекса.Недостатки предыдущего способа могут быть устранены путем изъятия указателя из каждого дискового блока и помещения его в индексную таблицу в памяти, которая называется таблицей размещения файлов (англ. file allocation table – FAT). Этой схемы придерживаются многие ОС (MS-DOS, OS/2, MS Windows и др.).

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

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

Индексные узлы.Четвертый и последний способ «выяснения принадлежности» блока к файлу – связать с каждым файлом маленькую таблицу, называемую индексным узлом (i-node), которая перечисляет атрибуты и дисковые адреса блоков файла (рис. 41). Каждый файл имеет свой собственный индексный блок, который содержит адреса блоков данных. Запись в директории, относящаяся к файлу, содержит адрес индексного блока. По мере заполнения файла указатели на блоки диска в индексном узле принимают осмысленные значения. Индексирование поддерживает прямой доступ к файлу, без ущерба от внешней фрагментации.

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

Эту схему распределения внешней памяти использует ОС Unix, а также файловые системы HPFS, NTFS и др. Такой подход позволяет при фиксированном, относительно небольшом размере индексного уз-ла, поддерживать работу с файлами, размер которых может меняться от нескольких байт до нескольких гигабайт. Существенно то, что для маленьких файлов используется только прямая адресация, обеспечивающая высокую производительность.