Операционные системы Файловые системы (часть 1) 1.Базовые методы организации ФС 1.1.Общие концепции Структурная организация файлов Атрибуты файла Работа с файлами Модельная организация каталогов ФС 1.2.Подходы в практической реализации ФС Модели реализации файлов Таблица размещения файловой системы Модели организации каталогов Соответствие имени и содержимого файла Учёт свободных блоков ФС Квотирование пространства ФС 1.3.Надёжность файловой системы 1.4.Проверка файловой системы

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

Имя Права доступа Персонификация (создатель, владелец) Тип файла Размер записи Размер файла Указатель чтения / записи Время создания Время последней модификации Время последнего обращения Предельный размер файла … Атрибуты файла

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

open открытие / создание файла close закрытие read / write читать, писать (относительно положения указателя чтения / запись) delete удалить файл из файловой системы seek позиционирование указателя чтение/запись rename переименование файла read / write _attributes чтение, модификация атрибутов файла Типовые программные интерфейсы работы с файлами

Каталог компонент файловой системы, содержащий информацию о содержащихся в файловой системе файлах. Каталоги являются специальным видом файлов. Модельная организация каталогов файловых систем / NAME1NAME2NAME3… корневой каталог Модель одноуровневой файловой системы

Модельная организация каталогов файловых систем / USR 1 USR 2 USR M... корневой каталог каталоги пользователей …… … файлы пользователей Модель двухуровневой файловой системы

Модельная организация каталогов файловых систем имя файлаимя файла полное имя файлаполное имя файла относительное имяотносительное имя домашний каталогдомашний каталог текущий каталогтекущий каталог Иерархические файловые системы / A BA B DC F B … …… Понятия

… Подходы в практической реализации файловой системы MBR Master Boot Record основной Программный загрузчик) разделы диска Блок физического HDD Блок виртуального HDD Блок файловой системы Блок файла Структура «системного» диска Загрузчик ОС Системная информация (суперблок, индексные дескрипторы…) Файлы + Свободное пространство таблица разделов: начало 1, конец 1 начало 2, конец 2 …

Непрерывные файлы Модели реализации файлов Name 1 Name 2 Name 3 Name 4 Name 5 Name 6 Фрагментация свободного пространства Увеличение размера существующего файла Достоинства Простота реализации Высокая производительность Недостатки

Файлы, имеющие организацию связанного списка Модели реализации файлов Name: {α i } множество блоков файловой системы, в которых размещены блоки файла Name. Достоинства Отсутствие фрагментации свободного пространства (за исключением блочной фрагментации) Простота реализации Эффективный последовательный доступ Недостатки Сложность (неэффективность) организации прямого доступа Фрагментация файла по диску Наличие ссылки в блоке файла (ситуации чтения 2-х блоков при необходимости чтения данных объемом один блок) 1 й блок файла 2 й блок файла 0 й блок файла К й блок файла …

(File Allocation Table FAT) Таблица размещения файловой системы блоки файла Name: 3 – номера блоков файловой системы Возможность использования всего блока для хранения данных файла Оптимизация прямого доступа (при полном или частичном размещении таблицы в ОЗУ) … …… k–1 Достоинства Желательно размещение всей таблицы в ОЗУ Недостатки

Индексные узлы (дескрипторы) Name Размер файла и размер индексного узла (в общем случае прийти к размерам таблицы размещения). Решение: ограничение размера файла иерархическая организация индексных узлов Индексный узел (дескриптор) системная структура данных, содержащая информацию о размещении блоков конкретного файла в файловой системе. Номер 0 го блока файла Номер 1 го блока файла Номер 2 го блока файла Номер 3 го блока файла … Номер последнего блока файла Достоинства Нет необходимости в размещении в ОЗУ информации всей FAT о всех файлах системы, в памяти размещаются атрибуты, связанные только с открытыми файлами Недостатки

Записи каталога фиксированного размера, содержат имя файла и все его атрибуты. Модели организации каталогов Каталог содержит имя файла и ссылку на атрибуты файла. Размер атрибутов может варьироваться. Организация «длинных» имен файлов? Name 1 Атрибуты Name 2 Атрибуты … Name 1 Name 2 … Атрибуты файла Name 1 … Атрибуты файла Name 2 …

Взаимнооднозначное соответствие: имя файла содержимое файла 1.Содержимому любого файла соответствует единственное имя файла Name Атрибуты файла Содержимое файла / AB CDEF GH

Взаимнооднозначное соответствие: имя файла содержимое файла? 2.Содержимому файла может соответствовать два и более имен файла. Name 1 Атрибуты файла NameCount = 2 Содержимое файла Name «Жесткая» связь Содержимое файла Name 2 Name Символическая связь

Проблема размер блока файловой системы. «Большой блок»: эффективность обмена существенная внутренняя фрагментация (неэффективное использование пространства ВП) «Маленький блок»: эффективное использование пространства ВП фрагментация данных файла по диску Проблема определение оптимального размера блока. Координация использования пространства внешней памяти

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

Использование битового массива Состояние любого блока определяется содержимым бита с номером каждого блока. Если блок свободен, бит равен 1, занят

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

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

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

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

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

Проверка целостности файловой системы Варианты анализа таблиц Таблица свободных блоков Таблица занятых блоков Непротиворечивость файловой системы соблюдена

Проверка целостности файловой системы 3. Дубликат свободного блока – пересоздание списка свободных блоков Таблица свободных блоков Таблица занятых блоков Добавить в список свободных блоков файловой системы. Пропавший блок Оставить как есть, но система «замусоривается» Таблица свободных блоков Таблица занятых блоков

Проверка целостности файловой системы 4. Дубликат занятого блока автоматическое решение максимально затруднено, имеет место потеря информации в одном из файлов. 1.Name 1 копируется Name Name 2 копируется Name Удаляются Name 1, Name 2 4.Запускается переопределение списка свободных блоков 5.Обратное переименование файлов и фиксация факта их возможной проблемности Таблица свободных блоков Таблица занятых блоков Действие

Проверка целостности файловой системы Контроль непротиворечивости файлов файловой системы Атрибуты файла NameCount=M Содержимое файла Name 2 Name 1 Name 3 Name L... Возможны варианты: 1. L = M все в порядке 2. L > M 3. L < M NameCount = L