4.1 Основные концепции. Базовые методы организации ФС

Как орагнизовать и разместить данные при хранении?

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

Драйвера не решали проблему подгонки информации под размеры физических блоков памяти HDD. Вообще туши свет. Сиди и контролируй руками.

Базовые методы организации ФС

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

Общие концепции

1. Файл как последовательнось байтов. (Актуальная концепция)
   • Если заранее не знать, что прочтённая информация - float, можно и конспект лекции оттуда прочитать.
   • Поэтому в начале файла есть информация о том, что с ним делать.
2. Файл, как последовательность записей переменной длины.
   • Есть начало и конец.
3. Файл, как последовательность записей постоянной длины.
   • Нет необходимости в разметке.
4. Иерархическая организация файлов (дерево).
   • Файлы ссылаются на другие файлы

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

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

1. Имя
   • В UNIX это может быть несколько ссылок.
2. Права доступа
   • Для процессов
   • Для пользователей/групп пользователей
3. Персонификация (создатель, владелец)
   • Принадлежность файла
4. Тип файла
   • Признаки способа интерпретации информации из файла.
   • Специфичные (сокеты, fifo, директории, stdin).
5. Размер записи/блока
   • Размещение на блок-ориентированных устройствах требует адаптации информации под размер блоков.
6. Размер файла
   • В байтах/блоках + последние байты.
7. Указатель чтения/записи
   • Для регулярных файлов. В fifo организация иная.
8. Время создания
9. Время последней модификации
10. Время последнего обращения
11. Предельный размер файла
12. …

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

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

1. Начало
   • Проверка прав, существования файла и т.п.
   • Формирование файлового дескриптора.
2. Работа с содержимым файла и его атрибутами
   • Можно менять почти все атрибуты.
3. Завершение
   • Закрытие файла.

Открытие и закрытие файлов нужно для выделения соответствующих ресурсов.

• Количество одновременно открытых файлов в системе ограничено (в процессе тоже).

Каталоги

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

Одноуровневая файловая система:

Двухуровневая файловая система (подразделение на пользователей):

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

• В узлах этого дерева могут находиться файлы.
• Узел, отличный от листа - файл-каталог.
• Лист - любой файл.
• Имена файлов - их названия.
• Полные имена файлов - пути (относительные, абсолютные).
• В UNIX - домашний каталог, текущий каталог.

Структура системного диска и разделы

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

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

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

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

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

Недостатки:

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

Организация связным списком

$\{{\alpha }_i\}$ - множество блоков файловой системы, в которых размещены блоки файла Name.

Блок:

• Ссылка на следующий блок
• Содержательная информация файла

Плюсы:

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

Недостатки:

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

Таблица размещения ФС - FAT (File Allocation Table)

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

Недостатки:

• Желательно размещение целиком в ОЗУ.

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

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

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

• Нет необходимости размещения в ОЗУ всей информации FAT. Размещаются только атрибуты, свзяанные с открытыми файлами.
  Недостатки:
• Ограничено и регламентировано число открытых файловых дескрипторов.
• Размер файла и индексного узла (если сделать файл, сопоставимый по размеру общему объёму, файловый дескриптор будет огромного размера)
  • Решается ограничением размера файла. (ограничения. плохо.)
  • Или иерархической организацией индексных узлов.

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

Таблица с именами и всеми атрибутами

Таблица с ссылками на атрибуты

Взаимнооднозначное соответствие имён

1. Содержиму любого файла соответствует единое имя файла.
2. Содержимому файла может соответствовать два или более имё файла.
   • Жёсткая связь:
   • Символическая связь: Содержимое Name1 - название Name2. Содержимое Name2 - информация файла.

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

Какой лучше завести размер блока файловой системы?

“Большой блок”:

• Эффективность обмена
• Существенная внтуренняя фрагментация (неэффективное использование пространства.

“Маленький блок”:

• Эффективное использование пространства.
• Фрагментация файлов по диску.

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

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

В ОЗУ размещается первый блок списка.

Плюсы:

• Простая реализация.
• Держим в ОЗУ только рабочий блок.

Недостатки:

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

Битовый массив

Состояние любого блока определяется содержимым бита с номером каждого блока.
При поиске свободного пространства ищется наиболее “близкое” к логически связанным фрагментам информации.

Плюсы:

• Избегание фрагментации по диску. (частичное решение)

Недостатки:

• …

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

Учёт количества и размеров файлов, принадлежащих конкретному пользователю.

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

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

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

Деталей не будет. Реализацие бывают разные :)
В IT нет жёстких законов по реализации чего-либо.

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

На носителях может храниться критически важная информация. Она может потеряться по причинам:

• Потеря информации в результате программного или аппаратного сбоя.
• Удаление пользователем по ошибке.
  Вопрос возможности ФС противостоять таким проблемам.

$⟹$ Резервное копирование.
Но у подхода есть минусы: долго и много. Копировать всё дорого. Поэтому:

• Копировать/архивировать можно часть файлов (не сохранять софт, объектные файлы, системную информацию и т.д.)
• Второе решение - инкрементное архивирование. Единожды создаётся полная резервная копия. Далее сохраняются только изменённые/созданные файлы.

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

• Физическая архивация
  • “бит в бит”.
  • “бит в бит” только использованные блоки ОС.
  • Есть проблема обработки дефектных блоков.
• Логическая архивация
  • Копируем файлы (а не блоки).

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

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

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

Например при жёстком выключении компьютера (выдернул из розетки). В этом случае происходит потеря всего кэша системы. Если в этот момент что-то куда-то записывалось, оно не запишется и потеряется.

Системные данные быстро меняются, поэтому фиксировать их в архиве толком не выйдет.

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

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

1. Формируются две таблицы:
   • Таблица занятых блоков
   • Таблица свободных блоков

Изначально записи таблиц обнуляются. Размер таблицы соответствует размеру файловой системы. Число записей равно числу блоков ФС.

2. Анализируется список свободных блоков. Для каждого номера свободного блока увеличивается на 1 соответствующая ему запись в таблице свободных.
3. Анализируются все индексные узлы. Для каждого блока, встретившегося в индексном узле уеличивается его счётчик на 1 в таблице занятых блоков.
4. Анализ содержимого таблиц и коррекция ситуаций.

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

1. 
2. 
3. => Список свободных блоков сформирован некорректно. => Пересоздаётся список свободных блоков.
   Но как это происходит?
   Есть настройка системы, которая “знает” все занятые блоки. Берётся отрицание таблицы занятых.
4. 
   Блок обнаружен в двух файловых дескрипторах. Нужно разделить эти файлы. Для этого:
   • Cоздаём копии name1 и name2
   • Удаляем исходные name1 и name2
   • Запускается переопределение списка свободных блоков.
   • Копии переименовываются в исходные.

В данном случае важно сохранить целостность ФС. Сохранение самих файлов вторично.

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

ФС сохраняет NameCount. При проверке фактическое число имён должно совпадать с сохранённым.
При проверке приводим NameCount к реальному количеству.