Операционные системы/Примеры реализаций файловых систем. Внутренняя организация ФС.

Материал из eSyr's wiki.

Содержание 1 Структура ФС UNIX SYSTEM V 1.1 Область (пространство) индексных дескрипторов 1.2 Блоки файлов 1.2.1 Работа с массивами номеров свободных блоков 1.3 Индексные дескрипторы 1.3.1 Работа с массивом свободных ИД 1.4 Адресация блоков файла 1.5 Файл каталог 1.6 Установление связей 1.7 Достоинства и недостатки ФС модели версии System V 2 FFS BSD 2.1 Структура каталога FFS 2.2 Блокировка доступа к содержимому файла

[править] Структура ФС UNIX SYSTEM V

Файловая система Unix может занимать раздел диска (partition). Количество разделов на каждом диске, их размеры определяются при предварительной подготовке устройства (разметка). Unix рассматривает разделы как отдельные, независимые устройства.

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

• размер логического блока (512б, 1024б, 2048б);
• размер файловой системы в логических блоках (включая суперблок);
• максимальное количество индексных дескрипторов (определяет размер области индексных дескрипторов);
• число свободных блоков;
• число свободных индексных дескрипторов;
• специальные флаги;
• массив номеров свободных блоков;
• массив номеров свободных индексных дескрипторов;
• и др.

В ОП постоянно находится актуальная копия суперблока.

[править] Область (пространство) индексных дескрипторов

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

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

Содержит:

1. Тип файла
2. Права доступа к файлу
3. Число имен каталогов ФС, ассоциированных с данным индексным дискриптором.
4. Идентификатор владельца
5. Размер файла в байтах
6. Время послдней модификации
7. Массив номеров блоков файлов

[править] Блоки файлов

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

[править] Работа с массивами номеров свободных блоков

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

Все свободные блоки ФС организованы в однонаправленный список, структурная организация которого следующая: 1-й элемент этого списка – это есть массив из Ν ссылок, которые размещаются в суперблоке. Ν зависит от конкретной ОС, пусть это будет 100. 0-й элемент этого массива есть номер блока из пространства блоков ФС, в котором находится продолжение этого списка. Соответственно 0-й элемент этого блока есть ссылка на следующий массив из Ν ссылок и т.д. ФС оперативно работает с этим массивом. Если в нем есть свободные места, то при освобождении блоков, они записываются на свободные места, если требуются новые блоки, то они выбираются из этого массива. Если массив исчерпывается, то информация берется из следующего блока. Если массив полностью заполнен, т.е. освобождается много блоков, то выбирается следующий свободный блок и этот массив скидывается на этот блок. Это достаточно важная информация, которая в каждый момент отражает состояние ФС.

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

[править] Индексные дескрипторы

Индексный дескриптор (ИД) – описатель файла, содержит все необходимые для работы с файлом служебные атрибуты.

Через ИД осуществляется доступ к содержимому файлов. Любое имя файла в системе ассоциировано с единственным ИД, но это соответствие неоднозначно. Т.е. ИД может соответствовать произвольное количество имен.

Структура индексного дескриптора:

• тип файла, права, атрибуты выполнения;
• число имен, которые ассоциированы с данным ИД (если = 0, то ИД свободен);
• идентификаторы владельца-пользователя, владельца-группы;
• размер файла в байтах;
• время последнего доступа к файлу;
• время последней модификации содержимого файла;
• время последней модификации ИД (за исключением времени доступа и времени модификации файла)
• массив номеров блоков файла.

[править] Работа с массивом свободных ИД

Массив номеров свободных индексных дескрипторов содержит оперативный набор номеров свободных индексных дескрипторов. Размер массива - N_индекс.

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

[править] Адресация блоков файла

Для простоты изложения будем считать, что размер блока равен 512 байт.

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

Ключом, задающим подобное расположение служит массив номеров блоков файла, содержащий список из 13 номеров блоков на диске, хранящихся в ИД. Первые десять указывают на десять блоков некоторого файла. Если файл занимает более 10 блоков, то 11 элемент указывает на косвенный блок, содержащий до 128 адресов дополнительных блоков файла (это еще 70656 байт). Большие файлы используют 12-ый элемент, который указывает на блок, содержащий 128 указателей на блоки, каждый из которых содержит по 128 адресов блоков файла. Еще в больших файлах аналогично используется 13 элемент.

Трехкратная косвенная адресация позволяет создавать файлы длиной (10+128+128*128+128*128*128)*512 байт.

Таким образом,

• если файл меньше 512 байт, то необходимо одно обращение к диску,
• если длина файла находится в пределах 512-70565 байт, то - два и так далее.

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

При открытии файла соответствующий ИД считывается в память и системе становятся доступны все номера блоков данного файла.

Для одного и того же файла, открываемого несколько раз, в памяти находится только один ИД.

Система фиксирует число открытий данного файла и, когда этот счетчик обнуляется, резидентный образ ИД переписывается на диск. Если при этом изменений в файле не было и не модифицировался ИД, то запись не выполняется.

Указанные особенности существенно влияют на эффективность файловой системы.

[править] Файл каталог

Файл каталог для ФС System V представляет собой таблицу, каждая запись которой состоит из 16 байтов. Первые 2 байта – это номер индексного дескриптора. Последующие 14 байтов – это поле для имени файла. Соответственно, имеется предопределенные записи в этих полях – это первые две строчки. 1-я строчка – это ссылка на самого себя, т.е. в этой строчке находится имя «.» (точка) и номер индексного дескриптора этого файла каталога. Следующая запись – это ссылка на родительский каталог, соответственно в нем имеется номер индексного дескриптора и имя «..» (две точки).

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

[править] Установление связей

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

Существует две разновидности этой операции.

Жесткая связь - с одним и тем же индексным дескриптором будет ассоциироваться два или более имени, размещенных в произвольных точках ФС. При этом каждое из этих имен равноценно.

Для этого используется команда: ln …dir1/name1 …dir2/name2 – (для индексного дескриптора, с которым ассоциировано имя name1, добавляется еще одно имя – name2).

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

Установление символической связи - косвенная адресация на существующее имя файла.

В ФС можно создать специальный файл ссылку, содержимое которого размещается в индексном дескрипторе этого файла. Этим содержимым является текстовая строка, указывающая полное имя того файла, с которым нужно ассоциировать новое имя (имя файла-ссылки). Т.е. если name1 и name2 – это абсолютно равноправные файлы, то name3 – это текстовая (символьная ссылка). Для name 3 создается свой индексный дескриптор и через него организуется ссылка на файл name 1, при этом уже в индексном дескрипторе файла name 1 никакой информации о дополнительных ссылках на этот файл нет. Т.е. здесь уже некоторая асимметричная модель множественного именования содержимого файла. Если будет нужно удалить файл name 1, то система позволит это сделать, потому что нигде в информации, связанной с этим файлом, не указывается, что на него есть текстовая ссылка. И соответственно, когда после удаления этого файла произойдет обращение по ссылке /dir1/name3, то уже возникнут какие-то проблемы. Следует помнить, что не на любой файл можно установить ссылку.

Для этих целей используется команда: ln –s …dir1/name1 …dir2/name3 – в результате образуется специальный файл - ссылка.

[править] Достоинства и недостатки ФС модели версии System V

Достоинства ФС модели версии System V

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

Недостатки ФС модели версии System V

1. Концентрация важной информации в суперблоке – ключевая информация сконцентрирована в суперблоке файловой системы, физическая потеря содержимого суперблока может приводит к значительным проблемам, касающимся целостности файловой системы.
2. Проблема надежности (много ссылочных структур, возможна потеря данных при сбоях).
3. Фрагментация файла по диску – т.е. при достаточно больших размерах файла его блоки могут произвольным образом размещаться на физическом МД, что может приводить к выполнению значительного числа механических операций перемещения головок устройства при чтении/записи данных файла.
4. Организация каталога накладывает ограничения на возможную длину имени файла (14 символов).

[править] FFS BSD

В Unix 4.2 BSD разработана модель организации файловой системы, которая получила название Fast File System - FFS (быстрая файловая система).

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

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

Группа цилиндров:

• копия суперблока
• информация о свободных блоках (битовый массив) и о свободных индексных дескрипторах
• массив индексных дескрипторов (ИД)
• блоки файлов

Стратегии размещения

1. Новый каталог помещается в группу цилиндров, число свободных индексных дескрипторов в которой больше среднего значения во всей файловой системе в данный момент времени, а также имеющей минимальное число дескрипторов каталогов в себе;
2. для обеспечения равномерности использования блоков данных файл разбивается на несколько частей, при этом первая часть файла располагается в той же группе цилиндров, что и его дескриптор, при размещении последующих частей используется группа цилиндров, в которой число свободных блоков превышает среднее значение. Длина первой части выбирается таким образом, чтобы она адресовалось непосредственно индексным дескриптором (т.е. не «косвенно»), остальные части разбиваются фиксированным образом, например по 1 мегабайту;
3. последовательные блоки файлов размещаются исходя из оптимизации физического доступа (см. ниже)

Dt – технологический промежуток времени, который затрачивает система на передачу и прием устройством МД команды на чтение очередного блока. За это время диск проворачивается и головки обмена «пропускают» начало очередного блока, поэтому если мы будем читать следующий блок, то головка будет вынуждена ожидать полного поворота диска на начало блока. В связи с этим эффективнее читать не последовательные блоки (в этом случае нужно ожидать полного поворота диска), а блоки, размещенные на диске через один, два... (смещение определяется поворотом диска за время Dt).

Внутренняя организация блоков

Обмен происходит блоками. Блоки могут быть достаточно большого размера (до 64 Кб). В системе может быть принято разбиение блока на равные фрагменты (на 2, 4, 8). То есть все пространство разделяется на «маленькие блоки» - фрагменты. Фрагменты группируются по 2, 4 или 8 в блоки (т.е. если фрагмент содержит 512 байт, то блок может быть размера 1024, 2048, 4096).

При этом блоком в этой системе может называться только «выровненный» до размера кратности набор фрагментов. Т.е. при кратности 4 (см. рисунок выше), фрагменты 0 – 3 – входят в один блок, а фрагменты 1 – 4 нет.

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

Формат индексного дескриптора аналогичен, используемому в s5fs - в нём в качестве элементов по-прежнему используются блоки, а не фрагменты, но при размещении информации в файлах используется следующее простое правило: все блоки указанные в индексном дескрипторе, кроме последнего, должны использоваться только целиком; блок может использоваться для нескольких файлов только при хранении их последних байт, не занимающих всех фрагментов полного блока (cм. рисунок ниже). Т.о. для хранения информации об использовании последнего блока недостаточно только размера файла, хранимого в дескрипторе System 5, необходимо также хранить информацию об используемых фрагментах в этом блоке.

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

1. Если в уже выделенном файлу блоке есть достаточно места, то новые данные помещаются в это свободное пространство.
2. Если последний блок файла использует все фрагменты (т.е. это полный блок) и свободного в нём места не достаточно для записи новых данных, то частью новых данных заполняется всё свободное место. Если остаток данных превышает по размеру один полный блок, то выделяется новый полный блок и записываются данные в этот полный блок. Процесс повторяется до тех пор, пока остаток не окажется меньше чем полный блок. В этом случае ищется блок с необходимыми по размеру фрагментами или выделятся новый полный блок. Остаток данных записывается в этот блок.
3. Файл содержит один или более фрагмент (они естественным образом содержатся в одном блоке) и последний фрагмент недостаточен для записи новых данных. Если размер новых данных в сумме с размером данных, хранимых в неполном блоке, превышает размер полного блока, то выделяется новый полный блок. Содержимое старого неполного блока копируется в начало выделенного блока и остаток заполняется новыми данными. Процесс далее повторяется, как указано в пункте 2 выше. В противном случае (если размер новых данных в сумме с размером данных, хранимых в неполном блоке, не превышает размер полного блока) ищется блок с необходимыми по размеру фрагментами или выделятся новый полный блок. Остаток данных записывается в этот блок.

[править] Структура каталога FFS

Поддержка длинных имен файлов.

Любая запись содержит:

• номер индексного дескриптора;
• длина записи в каталоге;
• длина имени файла;
• имя файла (дополненное до кратности слова).

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

[править] Блокировка доступа к содержимому файла

Возможность блокирования области файла любого размера.

Системный вызов fcntl()

• Исключающая блокировка (exclusive lock) — «жесткая» блокировка (область может быть заблокирована единственный раз). Блокировка с монополизацией.
• Распределенная блокировка (shared lock) — «мягкая» блокировка (возможны пересечения заблокированных областей). Рекомендательная блокировка.