Операционные системы/Файловые системы

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

---

Версия 20:30, 22 января 2010

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

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

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

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

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

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

Содержание 1 Структурная организация файлов 2 Атрибуты файла 3 Основные правила работы с файлами 3.1 Модель одноуровневой файловой системы 3.2 Модель двухуровневой файловой системы 3.3 Иерархические файловые системы 4 Подходы в практической реализации файловой системы 4.1 Структура «системного» диска 4.2 Модели реализации файлов 4.2.1 Непрерывные файлы 4.2.2 Файлы, имеющие организацию связного списка 4.3 Способы хранения информации о размещении блоков файлов 4.3.1 Таблица размещения файловой системы 4.3.2 Индексные узлы (дескрипторы) 4.4 Модели организации каталогов 4.5 Варианты соответствия имя файла <–> содержимое файла 4.5.1 “Жесткая” связь 4.5.2 “Символическая” связь 5 Координация использования пространства внешней памяти 5.1 Учет свободных блоков файловой системы 5.1.1 Связный список свободных блоков 5.1.2 Использование битового массива 5.2 Квотирование пространства файловой системы 5.3 Надежность файловой системы 5.3.1 Различные модели резервного копирования 5.3.2 Проверка целостности файловой системы 5.3.2.1 Модельная стратегия контроля

Структурная организация файлов

Существует множество разновидностей структурной организации файлов. Наиболее популярные:

• Файл как последовательность байтов (обмен от 1 до фиксированного числа байтов). Т.е. файл – это набор данных, практически не имеющих никакой структуры. Соответственно, вопрос выделения логической структуры – это уже проблема пользователя. Пользователь записывает данные, как последовательность байтов, считывает их и сам уже интерпретирует. Как ни странно, на сегодняшний день это – одна из самых распространенных моделей структурной организации файлов. Таким образом организуются файловые системы Unix, Windows, т.е. файл там может быть представлен как просто последовательность байтов.

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

• Файл как последовательность записей постоянной длины (обмен в терминах записей постоянной длины). Исторически этот вариант структурной организации появился из-за использования такого носителя информации, как перфокарты. Т.е. было удобно делать файл, который был прямым аналогом колоды перфокарт. Это означает, что читать из файла или писать данные в этот файл система позволяла порциями размером в 80 байт. Понятно, что такая организации файла достаточно эффективна по скорости доступа, т.е. был прямой доступ к любой записи, потому что координаты записи внутри вычислялись всегда очень просто: (номер записи)*(размер записи). С другой стороны – внутренняя фрагментация. Один байт используется в записи и вся запись размером в 80 байтов становится занятой.

• Иерархическая организация файла (дерево) (поиск, сортировка и т.д. осуществляется по ключам). Суть: структура файла представима в виде дерева. В каждом узле этого дерева находится информация о записи. Информация о записи – это два содержательных поля: поле ключа и поле данных. Соответственно дерево организовано таким образом, что в нем оптимизирован доступ к записям по указанию ключа, т.е. записи отсортированы по одинаковым ключам, и разные ключи отсортированы по возрастанию ключей. Поле данных может быть произвольного размера. Место расположения записи может быть в общем случае произвольно, т.е. ФС может разместить запись, где захочет, по своим каким-то критериям. имеются накладные расходы, связанные с древовидной организацией - с организацией ключей. Обычно, это достаточно специализированные ФС, которые используются или могут использоваться в высокопроизводительных, либо специальных ВС.

Атрибуты файла

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

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

Основные правила работы с файлами

Операционная система и файловая система обеспечивают регистрацию возможности того или иного процесса работать с содержимым файлов. «Сеанс работы» с содержимым файла:

1. Начало. Открытие файла – регистрация в системе возможности работы процесса с содержимым файла.
   Открытие – создание внутрисистемной структуры данных, кот. описывает состояние этого файла, проверяет права доступа, объявляет операционной системе тот факт, что с данным файлом будет работать тот или иной процесс. При открытии файла система формирует внутренние наборы данных, необходимые для работы с содержимым файла.
2. Работа с содержимым файла, с атрибутами файла
3. Завершение. Закрытие файла – информация системе о завершении работы процесса с открытым файлом. Операция закрытия файла имеет 2 вида:

• закрыть и сохранить текущее содержимое файла;
• уничтожить файл.

Типовые программные интерфейсы работы с файлами

• open – открытие / создание файла
  • «r» - на чтение
  • «w» - на запись
  • … и т.д.
• close – закрытие

• read / write – читать, писать (относительно положения указателя чтения / запись, read/write по дескриптору а не по имени)

• delete – удалить файл из файловой системы (напрямую или дескриптор)

• seek – позиционирование указателя чтение/запись

• rename – переименование файла
• read / write attributes – чтение, модификация атрибутов файла.

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

Каталог – компонент файловой системы, содержащий информацию о содержащихся в файловой системе файлах.

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

Модель одноуровневой файловой системы

Традиционно-простая организация каталога – одноуровневая модель ФС. В ФС существует один каталог, в котором находятся все файлы, находящиеся в системе. Проблемы:

1. Коллизия имен. Каждое имя должно быть единственно.
2. Нагрузка на работу с системой, если много файлов.
3. Неудобно структурировать.

Модель двухуровневой файловой системы

Модель, которая появилась в реальных системах на начальных этапах после одноуровневой. В системе существует объединение каталогов пользователей, для каждого пользователя реализована одноуровневая модель. Проблемы 1 и 2 исчезают, а 3 остается.

Иерархические файловые системы

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

Остановимся на правилах именования в иерархической файловой системе. В данном случае используется механизм, основанный на понятии имени файла (name) и полного имени файла (path_name). Полное имя файла – это путь от корневого каталога до листа (такой путь всегда будет уникальным). Существует также относительное именование, т.е. когда нет необходимости указания полного пути при работе с файлами. Это происходит в случае, когда программа вызывает файл и подразумевается, что он находится в том же каталоге, что и программа. В данном случае появляется понятие текущего каталога, т. е. каталога, на работу с которым настроена файловая система в данный момент времени. В рамках одного каталога имена файлов одного уровня должны быть разными.

Подходы в практической реализации файловой системы

Структура «системного» диска

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

Блок – порция данных, фиксированного размера, в рамках которого идет обмен данными с устройством. 1ый уровень виртуализации – блок устройства HDD 2ой уровень виртуализации – блок ФС (блок виртуального диска) использует виртуальный размер блока. Размер можно варьировать. 3ий уровень виртуализации – блок файла.

Модели реализации файлов

Непрерывные файлы

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

• Простота реализации
• Высокая производительность

Недостатки:

• Фрагментация свободного пространства (прямая и косвенная)
• Увеличение размера существующего файла невозможно или каждый раз проводится операция компрессии

Файлы, имеющие организацию связного списка

Все блоки файла организованны в единый список. Это означает, что в нулевом блоке файла имеется ссылка на 1-й блок, в первом блоке файла имеется ссылка на второй блок и т.д. до последнего, в последнем блоке файла ссылка = ΝULL. Это означает, что фактически решается проблема внешней фрагментации файла, т.е. файл в этом случае может произвольным образом расширяться Достоинства:

• Отсутствие фрагментации свободного пространства (за исключением блочной блочной фрагментации)
• Простота реализации
• Эффективный последовательный доступ

Недостатки:

• Сложность (неэффективность) организации прямого доступа
• Фрагментация файла по диску
• Наличие ссылки в блоке файла (ситуации чтения 2-х блоков при необходимости чтения данных объемом один блок).

Способы хранения информации о размещении блоков файлов

Таблица размещения файловой системы

В файловых системах FAT используется т.н. таблица размещения файловой системы (File Allocation Table – FAT, откуда и название). Файл представляется как последовательность записей постоянной длины (блоков). При этом на диске они не обязательно расположены последовательно. Таблица размещения файловой системы представляет собой массив, в котором на i-м месте стоит номер блока, следующего за i-м в файле или одно из некоторых специальных значений (например, индикация того, что i-й блок свободен). В самих блоках при этом связывающая их информация не хранится. Каждому каталогу соответствует специальный файл, в котором для каждого входящего в него файла хранится имя, атрибуты, начальных блок и другая информация.

Достоинства:

• Возможность использования всего блока для хранения данных файла
• Оптимизация прямого доступа (при полном или частичном размещении таблицы в ОЗУ)

Недостатки:

• Желательно размещение всей таблицы в ОЗУ (проблема размера, например для 60 GB раздела и блоков размером 1KB потребуется 60 000 000*4B = 240 MB)

См. также про FAT в википедии.

Индексные узлы (дескрипторы)

В файловых системах, которые мы будем рассматривать, используются индексные дескрипторы (inodes).

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

Достоинства:

• нет необходимости в размещении в ОЗУ информации всей FAT о все файлах системы, в памяти размещаются атрибуты, связанные только с открытыми файлами.

Недостатки:

• размер файла и размер индексного узла (в общем случае прийти к размерам таблицы размещения). Решение:
  • ограничение размера файла
  • иерархическая организация индексных узлов

Модели организации каталогов

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

• «-» каталог очень большой по объему.

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

• «+» более гибкая организация по размеру атрибутов.

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

Варианты соответствия имя файла <–> содержимое файла

1. Содержимому любого файла соответствует единственное имя файла. Исторически было взаимноодназначное соответствие между именем и содержимым файла. Т.е. для каждого содержимого файла существовало единственное имя файла и для каждого зарегистрированного файла в ФС существовало единственное содержимое.

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

“Жесткая” связь

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

“Символическая” связь

Есть файл с именем Νame2, этому имени соответствуют атрибуты и соответствует содержимое, и есть специальный файл Νame1, который ссылается на имя Νame2. В этом случае имеет место ассиметричное именование файлов. Имя Νame2 позволяет организовывать более широкую работу с файлом, можно удалять, если файл будет удален, соответственно содержимое пропадет. Имя Νame1 имеет свои правила интепретации, оно ссылается на имя Νame2, т.е. можно осуществлять доступ к содержимому, но если удалить файл Νame1, то содержимое Νame2 останется неизменным.

Координация использования пространства внешней памяти

Проблема – размер блока файловой системы. «Большой блок»:

• "+" эффективность обмена
• "-" существенная внутренняя фрагментация ( не эффективное использование пространства ВП)

«Маленький блок»:

• "+" эффективное использование пространства ВП
• "-" фрагментация данных файла по диску

Решение – подбирать размер блока для каждой конкретной задачи.

Учет свободных блоков файловой системы

Связный список свободных блоков

Пример: Размер блока 1 Кб 1 блок = 256 х 4 б 255 номеров свободных блоков 1 ссылка на следующий блок

При использовании связного списка свободных блоков в ОЗУ размещается первый блок списка.

Использование битового массива

Состояние любого блока определяется содержимым бита с номером каждого блока.

Если блок свободен, бит равен 1, занят – 0.

Пример: Для HDD 16 Gb потребуется 2048 блоков для хранения битового массива Все пространство для хранения – битовая карта – массив битов. Номер бита от начала массива соответствует номеру блока. Если блок свободен, бит равен 1, занят – 0.

Квотирование пространства файловой системы

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

Существуют жесткие и гибкие лимиты.

Жесткие лимиты не превышаются никогда. Гибкие квоты можно превышать, но после этого включается обратный счетчик предупреждений. Пока счетчик > 0, при каждой регистрации пользователя в системе от получает предупреждение, если счетчик = 0, пользователь блокируется.

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

Надежность файловой системы

Критерий надежность файловой системы достаточно просто формулируется: нужно обеспечить работу таким образом, чтобы при возникновении внештатной ситуации объем потерянной информации был минимальным. Внештатная ситуация может быть самой разнообразной – сбой в любом из узлов компьютера, в том числе на носителе, в котором находится файловая система, физическое уничтожение информации (в том числе и случайное) и т.д. Первым и наиболее исторически традиционным путем решения этой проблемы является резервное копирование или резервное архивирование файла.

Резервное копирование должно проходить в ограниченный промежуток времени.

Различные модели резервного копирования

1. Копируются не все файлы файловой системы (избирательность архивирования по типам файлов); Не копируются *.obj и системные (те, которые можно переустановить).
2. Создается мастеркопия архива по расписанию, или в произвольные моменты времени. Копируются все файлы, которые были изменены с момента создания последней мастеркопии. Копии получаются очень большие.
3. Использование компрессии при архивировании (риск потери всего архива из-за ошибки в чтении/записи сжатых данных);
4. Проблема архивирования «на ходу» (во время копирования происходят изменения файлов, создание, удаление каталогов и т.д.). Возможность потери информации из-за внештатной ситуации (например отключение от питания)
5. Распределенное хранение резервных копий. Лучше держать много копий в разных местах – хоть где-нибудь, да останется.

Стратегии архивирования

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

Проверка целостности файловой системы

Проблема – при аппаратных или программных сбоях возможна потеря информации:

• потеря модифицированных данных в «обычных» файлах;
• потеря системной информации (содержимое каталогов, списков системных блоков, индексные узлы и т.д.)

Необходим контроль целостности или непротиворечивости файловой системы.

Модельная стратегия контроля

1. Формируются две таблицы:
   • таблица занятых блоков;
   • таблица свободных блоков;
     (размеры таблиц соответствуют размеру файловой системы – число записей равно числу блоков ФС)
     Изначально все записи таблиц обнуляются.
2. Анализируется список свободных блоков. Для каждого номера свободного блока увеличивается на 1 соответствующая ему запись в таблице свободных.
3. Анализируются все индексные узлы. Для каждого блока, встретившегося в индексном узле, увеличивается его счетчик на 1 в таблице занятых блоков.
4. Анализ содержимого таблиц и коррекция ситуаций.

Варианты анализа таблиц

1. Таблица занятых блоков и таблица свободных блоков дополняют друг друга до всех единиц, тогда все в порядке, целостность системы соблюдена.
2. Пропавший блок – не числится ни среди свободных, ни среди занятых. Можно оставить как есть и ждать претензий со стороны пользователя, но система замусоривается. Считаем свободным.
3. Таблица занятых блоков корректна, а какой-то из свободных блоков дважды или более раз посчитан свободным, т.е. список свободных блоков (таблица) не корректен. В этом случае нужно запустить процесс пересоздания списка свободных блоков. Т.е. нужно запустить процесс, который проанализирует все индексные дескрипторы и соответственно сформирует список свободных блоков.
4. Дубликат занятого блока. Блок повстречался в 2х индексных дискрипторах. Локализуем проблему на уровне файлов. Действие:
   1. Name1 ---> копируется Name1²
   2. Name2 ---> копируется Name2²
   3. Удаляются Name1, Name2
   4. Запускается переопределение списка свободных блоков
   5. Обратное переименование файлов и фиксация факта их возможной проблемности.

Также для каждого файла подсчитывается число имен N, сравнивается со счетчиком имен. Если эти числа не совпадают, то счетчику имен присваевается N.