Реализация файловой системы кратко
Обновлено: 02.07.2024
Файловая система организовывает работу с данными, хранящимися во внешней памяти, и предоставляет пользователю возможности для сохранения и выборки этих данных.
Пользователь должен форматировать диск, выделяя на нем место для структур данных, которые описывают состояние файловой системы в целом. Потом создать нужную структуру каталогов, которые — списки вложенных каталогов и файлов. Заполнить дисковое пространство файлами, приписывая их тому или иному каталогу. А у ОС есть файловые службы, которые предоставляют пользователю возможность всё это сделать, проверить целостность данных, повысить производительность работы с ними и т.п.
Общая структура файловой системы:
1. Оборудование (контролер диска, физические блоки диска – треки, сектора, цилиндры)
Магнитные диски с подвижными головками — магнитные поверхности, между которыми двигаются магнитные головки. Шаг движения головки является дискретным, и каждому её положению соответствует цилиндр магнитного диска. Цилиндры делятся на дорожки (треки), а каждая дорожка размечается на одно и то же количество блоков (секторов) таким образом, что в каждый блок можно записать максимально одно и то же число байтов. Так, для обмена с магнитным диском на уровне аппаратуры нужно указать номер цилиндра, номер поверхности, номер блока на соответствующей дорожке и число байтов, которое нужно записать или прочитать от начала этого блока. Таким образом, можно получить доступ к любому блоку в любой момент (прямой доступ к файлам). Физические блоки дисков можно записать в виде: диск 3, цилиндр 14.
2. Система ввода-вывода (драйвера устройств, обработчики прерываний)
Она предоставляет дисковое пространство в распоряжение файловой системы в виде непрерывной последовательности блоков фиксированного размера.
3. Логические блоки (разделы диска, логические диски)
Логические блоки имеют свой номер от 1 до N. Размер логических блоков совпадает или является кратным размеру физического.
4. Базисная подсистема управления файлами (Алгоритмы выделения блоков дисков, менеджер свободного пространства, системные вызовы для работы с дескрипторами, таблицы открытых файлов, монтирование файловых систем)
5. Логическая подсистема управления файлами (Поддержка древовидной структуры, работа с путями и именами, защита файлов)
Стандартные запросы открытия (open) и создания (create) файла поступает от программы к логической подсистеме. Логическая подсистема проверяет права доступа и открывает файл в соответствии с ними, получая handler. Handler (дескриптор) – ссылка на файл в таблице открытых файлов, который помогает читать и редактировать файл. Если файл был открыт ранее, то может быть организован совместный доступ.
Методы выделения дискового пространства определяют способ связывания файлов с блоками диска.
Способ 1: Непрерывная последовательность блоков
Каждый файл хранится как непрерывная последовательность блоков диска. Тогда у каждого файла есть адрес и длина в блоках, начиная от первого.
Преимущества: простота реализации, может считать целый файл за одну дисковую операцию.
Недостатки: надо искать место, куда можно полностью поместить файл, из-за чего возникает фрагментация и не рациональное его использование. Из-за этого надо часто собирать мусор, уплотнять файлы и т.п.
Использование: компакт-диски.
Способ 2: Связный список
Запись в директории содержит указатель на первый и последний (EOF) блоки файла. Каждый блок содержит указатель на следующий блок.
Преимущества: устранена проблема фрагментации, файл может неограниченно расти.
Недостатки: требуется несколько обращений для полного чтения файла, данные после дефектного блока легко могут быть утеряны, указатели на следующие блоки занимают память.
Способ 3: Файловая таблица
Хранит указатели из прошлого метода не в блоках, а в индексной таблице, записанной в отдельном месте. Запись в директории содержит указатель на первый блок, а на остальные содержатся ссылки в FAT таблице. Последний блок обозначается EOF.
Преимущества: можно оценить соседние блоки по степени свободности и записать данные по соседству.
Недостатки: надо хранить в памяти большую таблицу и часто к ней обращаться, что изнашивает диск.
Использование: FAT16, FAT32 в Windows.
Способ 4: iNode
Связывание с каждым файлом небольшой таблицы (iNode), которая знает атрибуты и дисковые адреса блоков файла. Запись в директории содержит адрес такой таблицы.
Преимущества: минимальная фрагментация, если файл большой, то одна из ячеек таблицы может хранить ссылку на другую небольшую таблицу. Та, в свою очередь, может хранить ссылку на ещё одну таблицу и т.д.
Недостатки: сложность в реализации.
Использование: Unix подобные системы.
Управление свободным и занятым дисковым пространством
Способ 1: Учёт при помощи битового вектора
Используется битовый вектор, который принимает значение 0 или 1 в зависимости от того, занят блок или нет. Пример: 1000110001
Преимущества : прост и эффективен для поиска первого свободного блока или последовательности блоков нужной длины.
Недостатки : размер битового вектора может быть очень велик для большого диска.
Использование : Apple Macintosh
Способ 2: Учёт при помощи связного списка
Связываем в список все свободные блоки, размещая указатель на первый свободный блок. Эффективен только когда нас интересует только первый свободный блок, иначе много действий с диском.
Размер блока обычно задаётся при форматировании системы. Небольшой размер приведет к тому, что большой файл будет из большого числа блоков. Большой размер блока увеличит скорость обмена с диском, но будет теряться часть полезного пространства. Компромиссный размер блока равен 4 Кбайта.
Структура файловой системы на диске на примере Unix:
- Суперблок (тип файловой системы, её размер в блоках, размер массива индексных узлов, размер логического блока). Создаётся при форматировании, командой format. Для надёжности копируется пару раз.
- Структуры, описывающие свободное пространство
- Массив индексных узлов. Определяет количество файлов, которые можно сохранить в файловой системе, задаётся при установке его размер.
- Блоки данных файлов хранят файлы и директории
Директория – файл, имеющий вид таблицы и хранящий список входящих в него директорий и файлов. Служит для поддержания древовидной структуры файловой системы.
Запись в директории связывает имя файла с блоками данных на диске.
Чтение в директории означает поиск имени в директории, извлечение атрибутов и адресов блоков данных файла.
Директория Windows содержит информацию: Имя файла, Расширение, Атрибуты, Время, Дата, Номер первого блока, размер.
Директория Unix содержит информацию: Номер индексного узла, Имя файла.
Поиск в директории:
- Линейный поиск – просматриваем директорию с самого начала, пока не найдём нужное имя файла. При создании нового файла вставляем его в конец, если другого с таким именем нет.
- Хеш-таблица – файлы так же в линейном виде, но есть еще и хеш-таблица, которая по имени файла позволяет получить указатель на имя файла в списке. Возможны коллизии, когда одинаковая хеш-функция для нескольких файлов. Тогда скорость снижается.
Монтирование файловых систем осуществляется командой mount. Отмонтирование командой umount.
Пример монтирования: mount /dev/sda1 /mnt, где /dev/sda1 – устройство, /mnt – точка его монтирования. Иногда монтирование производится автоматически, например когда подключается флешка, на ней ищется ФС и монтируется в случае обнаружения. К точке монтирования должно быть подсоединено не больше одной ФС.
Связывание файлов удобно использовать, когда хочется один файл вызывать разными именами (текстовый редактор vi командами edit, vi и проч.) Соединение между таким файлом и директорией называется линком (Link). Из-за этого возникает циклический граф.
Варианты реализации связывания файлов:
1. Дублирование информации о файле в каждой директории. Тогда информация, измененная одним пользователем, не будет доступна другому.
2. Использование Хардлинков – когда файлы перечислены не в директории, а в индексном узле. Надо считать количество ссылок i на файл, для корректной организации удаления. Пользователь закрыл, тогда i—;
3. Использование Софтлинков – создаётся новый файл, содержащий путь к связываемому файлу. Только тот, кто создал такой файл, может его удалить.
Кооперация процессов при работе с файлами
Когда различные пользователи вместе работают над одним проектом, им надо вместе использовать файлы. Причем работа одного не должна мешать работе другого.
Подходы к кооперации:
- Временный захват пользователем файла или его части. Для этого используется команда fcntl. Можно подождать и выполнить синхронизацию, когда это станет возможно. Либо сразу сказать, что сейчас нельзя и на этом закончить.
- Блокировка одного из буферов на время системного вызова
Чтобы не возникало тупиковых ситуаций и коллизий, надо тщательно проектировать файловую систему. Чтобы не потерять данные, надо задуматься об аспектах надежности файловой системы и делать бекапы важных данных.
- Операции по порядку и полностью
- Вести журнал
Если проблема всё-таки возникла, можно воспользоваться утилитой chkdsk (вообще она иногда включается при загрузке системы автоматически, после сбоя – прим. ред.)
Если существуют дефектные блоки на диске, то:
Способ 1: Найти дефектные блоки и составить их список. Каждому дефектному поставить в соответствие рабочий резервный. Когда будет обращение к дефектному, будет происходить перенаправление к резервному.
Способ 2: Создание файла, который занимает все дефектные блоки и изолирование его от других программ.
Способы увеличения производительности файловой системы:
С именем файла работают функции: create, open, link(текущее_имя_файла, новое_имя_файла), unlink.
С файловым дескриптором (handler-ом) работают: read, write, lseek.
Современные ОС могут работать с несколькими ФС одновременно. Собственно, FAT32 на флешке и NTFS на винчестере – очевидно.
Примеры современных ФС: FAT16, FAT32, NTFS, ext2, ext3, ext4.
Все что до "Загрузочного блока" и включая его одинаково у всех ОС. Дальше начинаются различия.
Суперблок - содержит ключевые параметры файловой системы.
2.2 Реализация файлов
Основная проблема - сколько, и какие блоки диска принадлежат тому или иному файлу.
2.2.1 Непрерывные файлы
Выделяется каждому файлу последовательность соседних блоков.
5 непрерывных файлов на диске и состояние после удаления двух файлов
Преимущества такой системы:
Простота - нужно знать всего два числа, это номер первого блока и число блоков.
Высокая производительность - требуется только одна операция поиска, и файл может быть прочитан за одну операцию
Диск сильно фрагментируется
Сейчас такая запись почти не используется, только на CD-дисках и магнитных лентах.
2.2.2 Связные списки
Файлы хранятся в разных не последовательных блоках, и с помощью связных списков можно собрать последовательно файл.
Размещение файла в виде связного списка блоков диска
Номер следующего блока хранится в текущем блоке.
Нет потерь дискового пространства на фрагментацию
Нужно хранить информацию только о первом блоке
Уменьшение быстродействия - для того чтобы получить информацию о всех блоках надо перебрать все блоки.
Уменьшается размер блока из-за хранения служебной информации
2.2.3 Связные списки при помощи таблиц в памяти
Чтобы избежать два предыдущих недостатка, стали хранить всю информацию о блоках в специальной таблице загружаемой в память.
FAT (File Allocation Table) - таблица размещения файлов загружаемая в память.
Рассмотри предыдущий пример, но в виде таблицы.
Таблица размещения файлов
Здесь тоже надо собирать блоки по указателям, но работает быстрее, т.к. таблица загружена в память.
Основной не достаток этого метода - всю таблицу надо хранить в памяти. Например, для 20Гбайт диска, с блоком 1Кбайт (20 млн. блоков), потребовалась бы таблица в 80 Мбайт (при записи в таблице в 4 байта).
Такие таблицы используются в MS-DOS и Windows.
2.2.4 i - узлы
С каждым файлом связывается структура данных, называемая i-узлом (index-node- индекс узел), содержащие атрибуты файла и адреса всех блоков файла.
Быстродействие - имея i-узел можно получить информацию о всех блоках файла, не надо собирать указатели.
Меньший объем, занимаемый в памяти. В память нужно загружать только те узлы, файлы которых используются.
Если каждому файлу выделять фиксированное количество адресов на диске, то со временем этого может не хватить, поэтому последняя запись в узле является указателем на дополнительный блок адресов и т.д..
Такие узлы используются в UNIX.
2. 3 Реализация каталогов
При открытии файла используется имя пути, чтобы найти запись в каталоге. Запись в каталоге указывает на адреса блоков диска.
В зависимости от системы это может быть:
дисковый адрес всего файла (для непрерывных файлов)
номер первого блока (связные списки)
Одна из основных задач каталоговой системы преобразование ASCII-имени в информацию, необходимую для нахождения данных.
Также она хранит атрибуты файлов.
Варианты хранения атрибутов:
В каталоговой записи (MS-DOS)
Варианты реализации каталогов
2. 3.1 Реализация длинных имен файлов
Раньше операционные системы использовали короткие имена файлов, MS-DOS до 8 символов, в UNIX Version 7 до 14 символов. Теперь используются более длинные имена файлов (до 255 символов и больше).
Методы реализации длинных имен файлов:
Просто выделить место под длинные имена, увеличив записи каталога. Но это займет много места, большинство имен все же меньше 255.
Применить записи с фиксированной частью (атрибуты) и динамической записью (имя файла).
Второй метод можно реализовать двумя методами:
Имена записываются сразу после заголовка (длина записи и атрибутов)
Имена записываются в конце каталога после всех заголовков (указателя на файл и атрибутов)
Реализация длинных имен файлов
2. 3.2 Ускорение поиска файлов
Если каталог очень большой (несколько тысяч файлов), последовательное чтение каталога мало эффективно.
2. 3.2.1 Использование хэш-таблицы для ускорения поиска файла.
Алгоритм записи файла:
Создается хэш-таблица в начале каталога, с размером n (n записей).
Для каждого имени файла применяется хэш-функция, такая, чтобы при хэшировании получалось число от 0 до n-1.
Исследуется элемент таблицы соответствующий хэш-коду.
Если элемент не используется, туда помещается указатель на описатель файла (описатели размещены вслед за хэш-таблицей).
Если используется, то создается связный список, объединяющие все описатели файлов с одинаковым хэш-кодом.
Алгоритм поиска файла:
Имя файла хэшируется
По хэш-коду определяется элемент таблицы
Затем проверяются все описатели файла из связного списка и сравниваются с искомым именем файла
Если имени файла в связном списке нет, это значит, что файла нет в каталоге.
Такой метод очень сложен в реализации, поэтому используется в тех системах, в которых ожидается, что каталоги будут содержать тысячи файлов.
2. 3.2.2 Использование кэширования результатов поиска файлов для ускорения поиска файла.
Алгоритм поиска файла:
Проверяется, нет ли имени файла в кэше
Если нет, то ищется в каталоге, если есть, то берется из кэша
Такой способ дает ускорение только при частом использовании одних и тех же файлов.
2.4 Совместно используемые файлы
Иногда нужно чтобы файл присутствовал в разных каталогах.
Link (связь, ссылка) - с ее помощью обеспечивается присутствие файла в разных каталогах.
А - совместно используемый файл.
Такая файловая система называется ориентированный ациклический граф (DAG, Directed Acyclic Graph).
Возникает проблема, если дисковые адреса содержатся в самих каталоговых записях, тогда при добавлении новых данных к совместно используемому файлу новые блоки будут числится только в каталоге того пользователя, который производил эти изменения в файле.
Есть два решения этой проблемы:
Использование i-узлов, в каталогах хранится только указатель на i-узел. Такие ссылки называются жесткими ссылками.
При создании ссылки, в каталоге создавать реальный Link-файл, новый файл содержит имя пути к файлу, с которым он связан. Такие ссылки называются символьными ссылками.
2.4.1 Жесткие ссылки
Может возникнуть проблема, если владелец файла удалит его (и i-узел тоже), то указатель, каталога содержащего ссылку, будет указывать на не существующий i-узел. Потом может появиться i-узел с тем же номером, а значит, ссылка будет указывать на не существующий файл.
Поэтому в этом случае при удалении файла i-узел лучше не удалять.
Файл будет удален только после того, как счетчик будет равен 0.
Иллюстрация проблемы, которая может возникнуть
2.4.2 Символьные ссылки
Удаление файла не влияет на ссылку, просто по ссылке будет не возможно найти файл (путь будет не верен).
Удаление ссылки тоже никак не скажется на файле.
Но возникают накладные расходы, чтобы получить доступ к i-узлу, должны быть проделаны следующие шаги:
Прочитать файл-ссылку (содержащий путь)
Пройти по всему этому путь, открывая каталог за каталогом
2.5 Организация дискового пространства
2.5.1 Размер блока
Если принято решение хранить файл в блоках, то возникает вопрос о размере этих блоков.
Есть две крайности:
Большие блоки - например, 1Мбайт, то файл даже 1 байт займет целый блок в 1Мбайт.
Маленькие блоки - чтение файла состоящего из большого числа блоков будет медленным.
Скорости чтения/записи и эффективность использования диска,
в системе с файла одинакового размера 2 Кбайта.
В UNIX системах размер блока фиксирован, и, как правило, равен от 1Кбайта до 4Кбайт.
В MS-DOS размер блока может быть от 512 до 32 Кбайт в зависимости от размера диска, поэтому FAT16 использовать на дисках больше 500 Мбайт не эффективно.
В NTFS размер блока фиксирован (от 512байт до 64 Кбайт), как правило, равен примерно 2Кбайтам (от 512байт до 64 Кбайт).
2.5.2 Учет свободных блоков
Основные два способа учета свободных блоков :
Связной список блоков диска, в каждом блоке содержится номеров свободных блоков столько, сколько вмешается в блок. Часто для списка резервируется нужное число блоков в начале диска.
Недостатки:
- Требует больше места на диске, если номер блока 32-разрядный, требуется 32бита для номера
- Излишние операции ввода/вывода, т.к. в памяти не хранятся все блоки, а, например, только один блок
Битовый массив (бит-карта) - для каждого блока требуется один бит.
Основные два способа учета свободных блоков
2.5.3 Дисковые квоты
Чтобы ограничить пользователя, существует механизм квот.
Два вида лимитов:
Жесткие - превышены быть не могут
Гибкие - могут быть превышены, но при выходе пользователь должен удалить лишние файлы. Если он не удалил, то при следующем входе получит предупреждение, после получения нескольких предупреждений он блокируется.
Наиболее распространенные квоты:
Объем использования диска
Количество открытых файлов
2.6 Надежность файловой системы
2.6.1 Резервное копирование
Случаи, для которых необходимо резервное копирование:
Аварийные ситуации, приводящие к потере данных на диске
Случайное удаление или программная порча файлов
Основные принципы создания резервных копий:
Создавать несколько копий - ежедневные, еженедельные, ежемесячные, ежеквартальные.
Как правило, необходимо сохранять не весь диск, а только выборочные каталоги.
Применять инкрементные резервные копии - сохраняются только измененные файлы
Сжимать резервные копии для экономии места
Фиксировать систему при создании резервной копии, чтобы вовремя резервирования система не менялась.
Хранить резервные копии в защищенном месте, не доступном для посторонних.
Существует две стратегии:
Физическая архивация - поблочное копирование диска (копируются блоки, а не файлы)
Недостатки:
- копирование пустых блоков
- проблемы с дефектными блоками
- не возможно применять инкрементное копирование
- не возможно копировать отдельные каталоги и файлы
Преимущества:
- высокая скорость копирования
- простота реализации
Логическая архивация - работает с файлами и каталогами. Применяется чаще физической.
2.6.2 Непротиворечивость файловой системы
Если в системе произойдет сбой, прежде чем модифицированный блок будет записан, файловая система может попасть в противоречивое состояние. Особенно если это блок i-узла, каталога или списка свободных блоков.
В большинстве файловых систем есть специальная программа, проверяющая непротиворечивость системы.
В Windows - scandisk.
Если произошел сбой, то во время загрузки они проверяют файловую систему (если файловая система журналируемая, такая проверка не требуется).
Журналируемая файловая система - операции выполняются в виде транзакций, если транзакция не завершена, то во время загрузки происходит откат в системе назад.
Два типа проверки на непротиворечивость системы:
проверка блоков - проверяется дублирование блоков в файле или в списке свободных блоков. Потом проверяется, нет ли блока файла, который еще присутствует в списке свободных блоков. Если блока нет в занятых и в незанятых, то блок считается не достающем (уменьшается место на диске), такие блоки добавляются к свободным. Также блок может оказаться в двух файлах.
проверка файлов - в первую очередь проверяется каталоговая структура. Файл может оказаться; либо в нескольких каталогах, либо не в одном каталоге (уменьшается место на диске).
2.7 Производительность файловой системы
Так как дисковая память достаточно медленная. Приходится использовать методы повышающие производительность.
2.7.1 Кэширование
Блочный кэш (буферный кэш) - набор блоков хранящиеся в памяти, но логически принадлежащие диску.
Перехватываются все запросы чтения к диску, и проверяется наличие требуемых блоков в кэше.
Ситуация схожа со страничной организацией памяти, можно применять те же алгоритмы.
Нужно чтобы измененные блоки периодически записывались на диск.
В UNIX это выполняет демон update (вызывая системный вызов sync).
В MS-DOS модифицированные блоки сразу записываются на диск (сквозное кэширование).
2.7.2 Опережающее чтение блока
Если файлы считываются последовательно, и когда получен к-блок, можно считать блок к+1 (если его нет в памяти). Что увеличивает быстродействие.
2.7.3 Снижение времени перемещения блока головок
Если записывать, наиболее часто запрашиваемые файлы, рядом (соседние сектора или дорожки), то перемещение головок будет меньше
В случае использования i-узлов если они расположены в начале диска, то быстродействие будет уменьшено, т.к. сначала головка считает i-узел (в начале диска), а потом будет считывать данные (где-то на диске). Если располагать i-узлы поближе к данным, то можно увеличить скорость доступа.
Концепция операционной системы (Глава 11) Реализация файловой системы
Структура файловой системы (Структура файловой системы)
Диск предоставляет большой объем внешнего дискового пространства для поддержки файловой системы. Следующие две характеристики диска делают его удобным средством для хранения нескольких файлов.
- ①Возможна перезапись на месте.
- ② Возможность прямого доступа к любой информации на диске.
Чтобы обеспечить эффективный и удобный доступ к диску, операционная система использует файловую систему для простого хранения, поиска и извлечения данных.
Файловая система имеет две проблемы с дизайном.
- ①Определите интерфейс файловой системы для пользователя
- ②Создавайте структуры данных и алгоритмы для сопоставления логической файловой системы с физическим внешним запоминающим устройством.
Сама файловая система обычно состоит из разных слоев. Например, то, что вы видите на рисунке ниже, является простым примером многоуровневого дизайна.
- Управление вводом / выводом
- Он состоит из драйвера устройства и обработчика прерываний для передачи информации между памятью и диском.
- Отправьте общие команды соответствующему драйверу устройства для чтения и записи физических блоков на диске
- Знайте файл и его логические и физические блоки.
- Менеджер свободного места
- Метаданные управления: все структурные данные файловой системы. Без фактических данных (или содержимого файла)
- Управляйте структурой папок в соответствии с заданным именем файла символов
- Логический проход файловой системыБлок управления файлами (FCB)Для поддержания файловой структуры
Типичная структура FCB показана на рисунке ниже.
![]()
Реализация файловой системы (реализация файловой системы)
Для реализации файловой системы используются несколько дисков и структур памяти.
Хотя эти структуры отличаются от операционной системы и файловой системы, они все же имеют свою регулярность.
Структура и работа файловой системы следующие:
- Структура диска.
- Структура файловой системы в памяти;
- Перегородка и установка
- Виртуальная файловая система
Структура диска
- Блок управления загрузкой (том) (блок управления загрузкой \ Громкость)
- Содержит управляющую информацию для запуска ОС
- UFS называется загрузочным блоком (boot block)
- Обычно первый блок раздела. Предположим, что на разделе нет ОС. Тогда пусто
Блок регулировки громкости (volume) (Блок регулировки громкости (/ volume))
- Содержит конкретную информацию о томе, включая
- Количество блоков и размер блоков;
- Количество и указатель свободных блоков;
- Номер и указатель свободных FCB.
Структура папки
- Используется для организации файлов
- УФС. Содержит имя файла и соответствующий номер inode
- NTFS, главная файловая таблица (master file table);
- В UFS индексный узел (inode);
- В NTFS - основная файловая таблица;
- Принять структуру реляционной базы данных, запись / файл
Структура файловой системы в памяти
- Таблица установки
- Содержит информацию обо всех установочных разделах
- Сохраните информацию о недавно посещенной папке (для папки установочного раздела она может содержать указатель на таблицу разделов)
- Содержит копию FCB и другую информацию о каждом открытом файле
- Содержит указатель на соответствующую запись и другую информацию в общесистемной таблице открытых файлов.
- Дескриптор файла (Linux / UNIX)
- Дескриптор файла (Windows)
На следующем рисунке показана операционная структура файловой системы.
![]()
Перегородка и установка
Структура диска зависит от операционной системы. Диск может быть разделен на несколько разделов или том может занимать несколько разделов на нескольких дисках.
Необработанный раздел используется там, где нет подходящей файловой системы.
Например: область подкачки в Unix, потому что она не использует файловую систему, а использует собственный формат диска.
Загрузочная информация может храниться в каждом разделе. И у него свой формат. Поскольку при загрузке в системе отсутствует драйвер конфигурации файловой системы, она не может интерпретировать формат файловой системы.
Обычно это набор упорядоченных блоков, считываемых в память как файл двоичного изображения.
В дополнение к информации о загрузке, включая информацию о том, как запустить определенную операционную систему. Также могут быть другие инструкции. (Например, BootManager bootstar 8.3, Linux GRUB, GRUB-GR и унифицированный загрузчик)
Корневой раздел содержит ядро операционной системы или другие системные файлы., Загружать память во время загрузки.
В зависимости от операционной системы другие разделы могут загружаться автоматически во время загрузки или вручную после этого.
- /root, /boot
- Таблица монтирования файловой системы (таблица монтирования файловой системы)
Виртуальная файловая система
- Виртуальная файловая система (VFS) предоставляет объектно-ориентированный метод реализации файловой системы.
- Функция VFS
- Разделение общей работы файловой системы и реализации путем определения интерфейса VFS;
- Обеспечить механизм уникального представления файла в сети (по vnode)
![]()
Первый уровень - это интерфейс файловой системы, в том числе. Вызовы open (), read (), write () и close () и дескрипторы описания файлов.
Второй уровень называется уровнем виртуальной файловой системы (VFS) и имеет две цели:
- Уровень VFS определяет четкий интерфейс VFS, чтобы отделить общие операции файловой системы от конкретной реализации. Реализация нескольких интерфейсов VFS может сосуществовать на одном компьютере и соглашается на доступ к нескольким типам файловых систем, которые были установлены, а затем локально.
- VFS предоставляет в ИнтернетеОднозначно идентифицировать файлМеханизмы.
Реализация каталога
Выбор алгоритмов распределения папок и управления папками имеет большое влияние на эффективность, производительность и надежность файловой системы.
Линейный список
Самый простой способ реализовать папку - использовать линейный список, в котором хранятся имена файлов и указатели блоков данных (массивы, связанные списки и т. Д.). Этот метод прост в программировании, но требует больше времени для выполнения.
Настоящим недостатком линейного списка записей папок является использование линейного поиска для поиска конкретной записи.
Фактически, многие операционные системы используют кэш программного обеспечения для хранения информации о недавно использованных папках. Попадания в кэш позволяют избежать постоянного чтения информации с диска, а в отсортированных списках можно использовать двоичный поиск. И сократить среднее время поиска.Хеш-таблица
Линейная таблица с использованием структуры данных Hash
- Уменьшено время поиска папки. Вставка и удаление также относительно просты.
- Просто нужен какой-то механизм, чтобы избежать столкновения (два имени файла хешируются в одно и то же место)
Самая большая сложность хеш-таблицы - это ее фиксированный размер и зависимость хеш-функции от размера.
Методы размещения
- цели
- Эффективное использование дискового пространства;
- Высокоскоростной доступ к файлам.
- Непрерывное размещение
- Назначение ссылки
- Распределение индекса
Непрерывное размещение
Метод непрерывного распределения требует, чтобы каждый файл занимал набор последовательных блоков на диске.
- Просто нужно только записать начальную позицию (номер блока) и длину файла.
- Доступ к файлам очень прост и требует наименьшего времени на поиск
- Последовательное посещение.
- прямое интервью.
- Найти место для новых файлов сложно
- Первый раз, лучший, худший
![]()
Метод отображения логического адреса на физический адрес следующий:
-
Логический адрес / размер блока = частное, остаток
Доступный блок = Q + начальный адрес (база)
позиция в блоке = RМетод непрерывного размещения на основе расширения:
- Многие новые файловые системы используют модифицированный метод непрерывного распределения.
- Расширение - это непрерывный дисковый блок
- Когда файл выделяется, ему присваивается расширение
- Также есть большое сплошное пространство
- Файл содержит одно или несколько расширений
- Нужен указатель на следующее расширение
Связанное размещение
Распределение ссылок решает все проблемы непрерывного распределения.
Используйте размещение ссылок. Каждый файл представляет собой связанный список дисковых блоков:
- Дисковые блоки распределяются в любом углу диска.
- Каждая запись папки имеет указатель на первый блок файла.
![]()
- Сильные стороны:
- Просто начальная позиция
- Создание и расширение файлов легко
- Нет произвольного доступа
- Указатель ссылки между блоками должен занимать место
- Кластер: сгруппируйте несколько последовательных блоков в кластеры. Диски размещены в кластерах
![]()
Таблица размещения файлов (FAT)
Начало каждого раздела используется для хранения таблицы FAT.
Каждый дисковый блок имеет запись в таблице, и таблица может быть проиндексирована по номеру блока.
Запись папки содержит номер блока первого блока файла.
Запись FAT, индексированная номером блока, содержит номер участка следующего блока файла.
Такая цепочка будет продолжаться до последнего блока, и значение соответствующей записи FAT этого блока будет значением конца файла. Неиспользуемые блоки представлены значением 0.
Выделение нового блока для файла означает просто найти первую запись FAT со значением 0. Замените предыдущее значение конца файла адресом нового блока. Замените 0 значением конца файла.
Предполагая, что неправильная FAT использует кеширование, схема распределения FAT может вызвать много времени поиска заголовка. Но прочитав информацию в FAT. На диске можно найти расположение любого блока для достижения произвольного доступа.
![]()
Индексированное размещение
- Собрать все указатели блоков данных в индексный блок
- I-я запись в индексном блоке указывает на i-й блок файла.
![]()
- У каждого файла есть индексный блок.
- Массив адресов дисковых блоков
- Схема ссылок: индексный блок обычно представляет собой дисковый блок. Для больших файлов. Возможность связать несколько индексных блоков.
- Многоуровневый индекс: метод косвенной адресации, аналогичный памяти (первый уровень, косвенный второй уровень . )
![]()
![]()
Управление свободным пространством (Управление свободным пространством)
Битовый вектор (n блоков)
![]()
- bit[i] = 1 → блок [i] свободное время
- bit[i] = 0 → блок [i] занят
Номер первого бесплатного блока:
Один А слово из Кусочек номер × ценить за 0 из слово номер ＋ Первый Один А ценить за 1 из Кусочек из Частичное сдвиг
- Битовые векторы требуют дополнительного места
- Пусть размер блока будет 2 12 байт
- Размер диска 2 30 Байт (1 ГБ)
- N = 2 30 / 2 12 = 218 (Т.е. 32 Кбайт)
- Процесс распределения
- Процесс переработки
Свободное время
![]()
Связанный список (пустой связанный список)
Соедините все свободные блоки диска связным списком и сохраните указатель на первый свободный блок в специальном месте на диске, а также одновременно кэшируйте его в памяти.
Непросто получить непрерывное пространство
Без траты места
![]()
Группировка (групповая ссылка)
- Сохраните адреса n свободных блоков в первом свободном блоке;
- Последний блок содержит адреса остальных n свободных блоков.
Схема групповых ссылок показана ниже.
![]()
- Группировка (групповая ссылка)
- Процесс размещения и восстановления
- Процесс распределения
- Требуемая защита
- Указатель на свободный стол
Требуемая защита
- Битовая карта
- Необходимо сохранить на диске
- Копия в памяти может отличаться от копии на диске;
- Для блока [i] ситуация не соответствует: бит [i] = 1 в памяти. На диске бит [i] = 0.
- Установите бит [i] = 1 на диске
- Выделить блок [i]
- Установите бит [i] = 1 в памяти
Эффективность и производительность (Efficiency and Performance)
эффективность
Эффективность зависит от
- Алгоритм распределения дисков и папок
- Предварительное выделение, кластер
- Недавняя дата записи / посещения
- 2 12 , 2 32 , 2 64 , 2 128
спектакль
Спектакль включает в себя следующие моменты:
- Дисковый буфер - помещает недавно использованные блоки в память
- Немедленный выпуск и последовательный доступ, оптимизированный для упреждающего чтения
- Выделите часть памяти как виртуальный диск (или RAM-диск), чтобы улучшить производительность персонального компьютера.
Кеш страницы
- Кэширование страниц использует технологию виртуальной памяти для кэширования файловых данных в виде страниц, а не блоков, ориентированных на файловую систему.
Ввод-вывод без единого буферного кеша показан на следующем рисунке.
![]()
Изменяется ввод-вывод, использующий унифицированный буферный кеш. Например, следующие
Большинство дисков делятся на несколько разделов с независимой файловой системой на каждом. Нулевой сектор диска называется главной загрузочной записью MBR - Master Boot Record и используется для загрузки. В конце главной загрузочной записи содержится таблица разделов, в которой хранятся начальные и конечные блоки каждого раздела. В MBR могут храниться данные 4 разделов. Один из разделов помечен в таблице как активный. При загрузке биос исполняет загрузочный код MBR, который определяет активный раздел, считывает с него первый сектор, который называется загрузочным, и исполняет его.
Строение раздела диска различно для каждой файловой системы.
Непрерывные файлы. Представляют собой наборы соседних блоков диска. Каждый следующий файл начинается с блока, следующего за последним блоком предыдущего файла. Преимущества системы:
- высокая производительность, так как файл может быть прочитан за одну дисковую операцию.
Недостаток: высокая фрагментированность раздела.
Для повторного использования освободившегося пространства потребуется хранить список всех свободных блоков, а при создании нового файла необходимо будет знать его точный размер. В настоящее время такая файловая система широко используется на оптических носителях.
Связанные списки. Первое слово каждого блока используется как указатель на следующий блок, остальная часть используется для хранения данных. Такой метод позволяет использовать все блоки диска без потерь на фрагментацию. В каталоговой записи нужно хранить адрес только первого блока. Недостатком является медленный произвольный доступ, так как необходимо пройти по всей цепочке используемых блоков. Кроме этого, уменьшается размер блока.
Связанный список при помощи таблицы в памяти. Оба недостатка предыдущей схемы можно устранить, если адреса следующих блоков хранить в отдельной таблице, загружаемой в памяти. Последний блок цепочки вместо номера следущего блока содержит запрещенное значение. Такая загружаемая в память таблица называется FAT-таблицей (File Allocation Table). При использовании такой схемы, для данных используется весь блок без потерь, увеличивается скорость случайного доступа: не смотря на то, что пройти придется по всей цепочке, она уже хранится в памяти и не потребуется дополнитльной дисковой операции. Недостатком является постоянное нахождение всей таблицы в памяти.
i-узлы (i-node). С каждым файлом связывается специальная структура данных, называемая индексным узлом. Она содержит атрибуты файла и адреса блоков файла. Каждый конкретный i-узел должен находится в памяти только если открыт соответствующий ему файл. Недостатком такой схемы является то, что при фиксированном размере i-узла, может не хватить места для адресации всех блоков файла. В этом случае последний указатель будет содержать номер другого i-узла, содержащего остальные адресные блоки
Структура файловой системы.
Большинство дисков делятся на несколько разделов с независимой файловой системой на каждом. Нулевой сектор диска называется главной загрузочной записью MBR - Master Boot Record и используется для загрузки. В конце главной загрузочной записи содержится таблица разделов, в которой хранятся начальные и конечные блоки каждого раздела. В MBR могут храниться данные 4 разделов. Один из разделов помечен в таблице как активный. При загрузке биос исполняет загрузочный код MBR, который определяет активный раздел, считывает с него первый сектор, который называется загрузочным, и исполняет его.
Строение раздела диска различно для каждой файловой системы.
Непрерывные файлы. Представляют собой наборы соседних блоков диска. Каждый следующий файл начинается с блока, следующего за последним блоком предыдущего файла. Преимущества системы:
- высокая производительность, так как файл может быть прочитан за одну дисковую операцию.
Недостаток: высокая фрагментированность раздела.
Для повторного использования освободившегося пространства потребуется хранить список всех свободных блоков, а при создании нового файла необходимо будет знать его точный размер. В настоящее время такая файловая система широко используется на оптических носителях.
![]()
Связанные списки. Первое слово каждого блока используется как указатель на следующий блок, остальная часть используется для хранения данных. Такой метод позволяет использовать все блоки диска без потерь на фрагментацию. В каталоговой записи нужно хранить адрес только первого блока. Недостатком является медленный произвольный доступ, так как необходимо пройти по всей цепочке используемых блоков. Кроме этого, уменьшается размер блока.
Связанный список при помощи таблицы в памяти. Оба недостатка предыдущей схемы можно устранить, если адреса следующих блоков хранить в отдельной таблице, загружаемой в памяти. Последний блок цепочки вместо номера следущего блока содержит запрещенное значение. Такая загружаемая в память таблица называется FAT-таблицей (File Allocation Table). При использовании такой схемы, для данных используется весь блок без потерь, увеличивается скорость случайного доступа: не смотря на то, что пройти придется по всей цепочке, она уже хранится в памяти и не потребуется дополнитльной дисковой операции. Недостатком является постоянное нахождение всей таблицы в памяти.
i-узлы (i-node). С каждым файлом связывается специальная структура данных, называемая индексным узлом. Она содержит атрибуты файла и адреса блоков файла. Каждый конкретный i-узел должен находится в памяти только если открыт соответствующий ему файл. Недостатком такой схемы является то, что при фиксированном размере i-узла, может не хватить места для адресации всех блоков файла. В этом случае последний указатель будет содержать номер другого i-узла, содержащего остальные адресные блоки
Читайте также:
