Какие вопросы являются основными при реализации файловых систем
Обновлено: 06.07.2024
Все что до "Загрузочного блока" и включая его одинаково у всех ОС. Дальше начинаются различия.
Суперблок - содержит ключевые параметры файловой системы.
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-узлы поближе к данным, то можно увеличить скорость доступа.
Какие утверждения относительно многопоточных приложений являются правильными?
+ 1. многопоточные приложения создают иллюзию одновременного выполнения приложением нескольких задач
2. многопоточные приложения позволяют рационально загружать ресурсы системы
+ 3. многопоточные приложения требут очень тщательной отладки
4. многопоточными являются все современные приложения
Какая структура данных используется при планировании потоков?
1. набор очередей, упорядоченный по значению приоритета
+ 2. список потоков, упорядоченных по их идентификаторам
3. набор стеков, упорядоченный по значению приоритета
4. неупорядоченный список потоков
Какую информацию обычно содержит дескриптор потока
1. состояние потока
+ 2. указатель на контекст потока
3. идентификатор потока
4. приоритет потока
+ 5. имя файла с кодом потока
Какие утверждения относительно понятия семафора являются правильными
1. семафоры применяются для отслеживания использования набора однотипных разделяемых ресурсов
+ 2. семафоры используют внутренние системные переменные с множеством возможных состояний
Что такое критическая секция
1. фрагмент кода потока, непосредственно использующий общую с другим потоком структуру данных
2. фрагмент кода потока, в котором возможно появление ошибок во время выполнения потока
3. струкутра данных, совместно используемая несколькими потоками
+ 4. фрагмент кода потока, наиболее критичный по времени выполнения
Как группируются потоки в зависимости от их приоритетов
1. потоки реального времени > системные потоки > прикладные потоки
2. системные потоки > потоки реального времени > прикладные потоки
+ 3. системные потоки > прикладные потоки > потоки реального времени
4. потоки реального времени > прикладные потоки > системные потоки
Какие состояния потоков являются основными
+ 1. состояние выполнения кода потока процессором
+ 2. состояние ожидания наступления некоторого события
+ 3. состояние готовности к выполнению
4. состояние изменения кода потока
Что содержит раздел жесткого диска
+ 1. основные параметры файловой системы
+ 2. информацию об используемых блоках и их распределении между файлами
3. главный каталог раздела
4. файлы и каталоги, входящие в раздел
Какие вопросы являются основными при реализации файловых систем
+ 1. физическая организация хранения данных на дисках
+ 2. способы определения местонахождения запрошенных данных на дисках
+ 3. алгоритмы выполнения операций с файлами
4. организация основной памяти
Какие действия выполняются при удалении файла
+ 1. извлечение из записи в каталоге адреса первого блока файла или номера индексного узла
+ 2. просмотр цепочки выделенных файлу блоков и освобождение их
3. удаление записи о файле из каталога
4. очистка всех выделенных файлу блоков от хранящейся там информации
Какие основные подходы можно использовать для распределения дискового пространства между файлами
+ 1. каждый файл занимает непрерывный набор блоков
+ 2. файл распределяется между любыми свободными блоками с созданием единой общей таблицы распределения файлов
3. файл распределяется между любыми свободными блоками с созданием для каждого файла своей структуры, хранящей номера выделенных блоков
4. в зависимости от размера файла система создает дисковый блок необходимого размера и назначает его файлу
Какие утверждения относительно индексно-узловог о способа распределения файлов являются правильными
+ 1. для каждого файла создается и поддерживается свой индексный узел
+ 2. очень легко и быстро реализуется прямой доступ к нужному фрагменту файла
3. немного замедляется обработка очень больших файлов
4. требуются большие затраты памяти для хранения индексных узлов файлов
Какие утверждения относительно разделов жесткого диска являются правильными
+ 1. раздел – это непрерывная область жесткого диска
+ 2. каждый раздел может иметь свою файловую систему
+ 3. разделы могут иметь разные размеры
4. разделы содержат только служебную информацию о файловых системах, а сами файлы разных файловых систем хранятся в общей части диска
Какие особенности характерны для дисковых блоков небольшого размера
+ 1. эффективное использование дискового пространства за счет малой фрагментации
2. большие накладные расходы на поддержку большого числа блоков
3. замедление операций чтения/записи для файлов, занимающих несмежные блоки
+ 4. более высокая скорость операций чтения/записи по сравнению с блоками большого размера
Какие утверждения относительно таблицы распределения файлов (File Allocation Table) являются правильными
+ 1. таблица используется в файловых системах FAT16/FAT32
+ 2. число j в ячейке i таблицы говорит, что за блоком i файлу выделен блок j
+ 3. после загрузки системы таблица постоянно находится в основной памяти
4. для размещения таблицы требуется очень мало памяти
Какие операции должно выполнить устройство управления диском для установки на начало заданного сектора
+ 1. выбрать необходимую головку чтения/записи (поверхность одного из дисков)
Концепция операционной системы (Глава 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-диск), чтобы улучшить производительность персонального компьютера.
Кеш страницы
- Кэширование страниц использует технологию виртуальной памяти для кэширования файловых данных в виде страниц, а не блоков, ориентированных на файловую систему.
Ввод-вывод без единого буферного кеша показан на следующем рисунке.
![]()
Изменяется ввод-вывод, использующий унифицированный буферный кеш. Например, следующие
![Типы файловых систем]()
Рядовому пользователю компьютерных электронных устройств редко, но приходится сталкиваться с таким понятием, как «выбор файловой системы». Чаще всего это происходит при необходимости форматирования внешних накопителей (флешек, microSD), установке операционных систем, восстановлении данных на проблемных носителях, в том числе жестких дисках. Пользователям Windows предлагается выбрать тип файловой системы, FAT32 или NTFS, и способ форматирования (быстрое/глубокое). Дополнительно можно установить размер кластера. При использовании ОС Linux и macOS названия файловых систем могут отличаться.
Возникает логичный вопрос: что такое файловая система и в чем ее предназначение? В данной статье дадим ответы на основные вопросы касательно наиболее распространенных ФС.
Что такое файловая система
Обычно вся информация записывается, хранится и обрабатывается на различных цифровых носителях в виде файлов. Далее, в зависимости от типа файла, кодируется в виде знакомых расширений – *exe, *doc, *pdf и т.д., происходит их открытие и обработка в соответствующем программном обеспечении. Мало кто задумывается, каким образом происходит хранение и обработка цифрового массива в целом на соответствующем носителе.
Операционная система воспринимает физический диск хранения информации как набор кластеров размером 512 байт и больше. Драйверы файловой системы организуют кластеры в файлы и каталоги, которые также являются файлами, содержащими список других файлов в этом каталоге. Эти же драйверы отслеживают, какие из кластеров в настоящее время используются, какие свободны, какие помечены как неисправные.
Запись файлов большого объема приводит к необходимости фрагментации, когда файлы не сохраняются как целые единицы, а делятся на фрагменты. Каждый фрагмент записывается в отдельные кластеры, состоящие из ячеек (размер ячейки составляет один байт). Информация о всех фрагментах, как части одного файла, хранится в файловой системе.
Файловая система связывает носитель информации (хранилище) с прикладным программным обеспечением, организуя доступ к конкретным файлам при помощи функционала взаимодействия программ A PI. Программа, при обращении к файлу, располагает данными только о его имени, размере и атрибутах. Всю остальную информацию, касающуюся типа носителя, на котором записан файл, и структуры хранения данных, она получает от драйвера файловой системы.
На физическом уровне драйверы ФС оптимизируют запись и считывание отдельных частей файлов для ускоренной обработки запросов, фрагментации и «склеивания» хранящейся в ячейках информации. Данный алгоритм получил распространение в большинстве популярных файловых систем на концептуальном уровне в виде иерархической структуры представления метаданных (B-trees). Технология снижает количество самых длительных дисковых операций – позиционирования головок при чтении произвольных блоков. Это позволяет не только ускорить обработку запросов, но и продлить срок службы HDD. В случае с твердотельными накопителями, где принцип записи, хранения и считывания информации отличается от применяемого в жестких дисках, ситуация с выбором оптимальной файловой системы имеет свои нюансы.
Основные функции файловых систем
Файловая система отвечает за оптимальное логическое распределение информационных данных на конкретном физическом носителе. Драйвер ФС организует взаимодействие между хранилищем, операционной системой и прикладным программным обеспечением. Правильный выбор файловой системы для конкретных пользовательских задач влияет на скорость обработки данных, принципы распределения и другие функциональные возможности, необходимые для стабильной работы любых компьютерных систем. Иными словами, это совокупность условий и правил, определяющих способ организации файлов на носителях информации.
Основными функциями файловой системы являются:
- размещение и упорядочивание на носителе данных в виде файлов;
- определение максимально поддерживаемого объема данных на носителе информации;
- создание, чтение и удаление файлов;
- назначение и изменение атрибутов файлов (размер, время создания и изменения, владелец и создатель файла, доступен только для чтения, скрытый файл, временный файл, архивный, исполняемый, максимальная длина имени файла и т.п.);
- определение структуры файла;
- поиск файлов;
- организация каталогов для логической организации файлов;
- защита файлов при системном сбое;
- защита файлов от несанкционированного доступа и изменения их содержимого.
![VDS Timeweb арендовать]()
Задачи файловой системы
Функционал файловой системы нацелен на решение следующих задач:
- присвоение имен файлам;
- программный интерфейс работы с файлами для приложений;
- отображение логической модели файловой системы на физическую организацию хранилища данных;
- поддержка устойчивости файловой системы к сбоям питания, ошибкам аппаратных и программных средств;
- содержание параметров файла, необходимых для правильного взаимодействия с другими объектами системы (ядро, приложения и пр.).
В многопользовательских системах реализуется задача защиты файлов от несанкционированного доступа, обеспечение совместной работы. При открытии файла одним из пользователей для других этот же файл временно будет доступен в режиме «только чтение».
Вся информация о файлах хранится в особых областях раздела (томах). Структура справочников зависит от типа файловой системы. Справочник файлов позволяет ассоциировать числовые идентификаторы уникальных файлов и дополнительную информацию о них с непосредственным содержимым файла, хранящимся в другой области раздела.
Операционные системы и типы файловых систем
Существует три основных вида операционных систем, используемых для управления любыми информационными устройствами: Windows компании Microsoft, macOS разработки Apple и операционные системы с открытым исходным кодом на базе Linux. Все они, для взаимодействия с физическими носителями, используют различные типы файловых систем, многие из которых дружат только со «своей» операционкой. В большинстве случаев они являются предустановленными, рядовые пользователи редко создают новые дисковые разделы и еще реже задумываются об их настройках.
В случае с Windows все выглядит достаточно просто: NTFS на всех дисковых разделах и FAT32 (или NTFS) на флешках. Если установлен NAS (сервер для хранения данных на файловом уровне), и в нем используется какая-то другая файловая система, то практически никто не обращает на это внимания. К нему просто подключаются по сети и качают файлы.
На мобильных гаджетах с ОС Android чаще всего установлена ФС версии ext4 во внутренней памяти и FAT32 на карточках microSD. Владельцы продукции Apple зачастую вообще не имеют представления, какая файловая система используется на их устройствах – HFS+, HFSX, APFS, WTFS или другая. Для них существуют лишь красивые значки папок и файлов в графическом интерфейсе.
Более богатый выбор у линуксоидов. Но здесь настройка и использование определенного типа файловой системы требует хотя бы минимальных навыков программирования. Тем более, мало кто задумывается, можно ли использовать в определенной ОС «неродную» файловую систему. И зачем вообще это нужно.
Рассмотрим более подробно виды файловых систем в зависимости от их предпочтительного использования с определенной операционной системой.
Файловые системы Windows
Исходный код файловой системы, получившей название FAT, был разработан по личной договоренности владельца Microsoft Билла Гейтса с первым наемным сотрудником компании Марком Макдональдом в 1977 году. Основной задачей FAT была работа с данными в операционной системе Microsoft 8080/Z80 на базе платформы MDOS/MIDAS. Файловая система FAT претерпела несколько модификаций – FAT12, FAT16 и, наконец, FAT32, которая используется сейчас в большинстве внешних накопителей. Основным отличием каждой версии является преодоление ограниченного объема доступной для хранения информации. В дальнейшем были разработаны еще две более совершенные системы обработки и хранения данных – NTFS и ReFS.
FAT (таблица распределения файлов)
Числа в FAT12, FAT16 и FAT32 обозначают количество бит, используемых для перечисления блока файловой системы. FAT32 является фактическим стандартом и устанавливается на большинстве видов сменных носителей по умолчанию. Одной из особенностей этой версии ФС является возможность применения не только на современных моделях компьютеров, но и в устаревших устройствах и консолях, снабженных разъемом USB.
Пространство FAT32 логически разделено на три сопредельные области:
- зарезервированный сектор для служебных структур;
- табличная форма указателей;
- непосредственная зона записи содержимого файлов.
К недостатком стандарта FAT32 относится ограничение размера файлов на диске до 4 Гб и всего раздела в пределах 8 Тб. По этой причине данная файловая система чаще всего используется в USB-накопителях и других внешних носителях информации. Для установки последней версии ОС Microsoft Windows 10 на внутреннем носителе потребуется более продвинутая файловая система.
С целью устранения ограничений, присущих FAT32, корпорация Microsoft разработала обновленную версию файловой системы exFAT (расширенная таблица размещения файлов). Новая ФС очень схожа со своим предшественником, но позволяет пользователям хранить файлы намного большего размера, чем четыре гигабайта. В exFAT значительно снижено число перезаписей секторов, ответственных за непосредственное хранение информации. Функция очень важна для твердотельных накопителей ввиду необратимого изнашивания ячеек после определенного количества операций записи. Продукт exFAT совместим с операционными системами Mac, Android и Windows. Для Linux понадобится вспомогательное программное обеспечение.
NTFS (файловая система новой технологии)
Стандарт NTFS разработан с целью устранения недостатков, присущих более ранним версиям ФС. Впервые он был реализован в Windows NT в 1995 году, и в настоящее время является основной файловой системой для Windows. Система NTFS расширила допустимый предел размера файлов до шестнадцати гигабайт, поддерживает разделы диска до 16 Эб (эксабайт, 10 18 байт ). Использование системы шифрования Encryption File System (метод «прозрачного шифрования») осуществляет разграничение доступа к данным для различных пользователей, предотвращает несанкционированный доступ к содержимому файла. Файловая система позволяет использовать расширенные имена файлов, включая поддержку многоязычности в стандарте юникода UTF, в том числе в формате кириллицы. Встроенное приложение проверки жесткого диска или внешнего накопителя на ошибки файловой системы chkdsk повышает надежность работы харда, но отрицательно влияет на производительность.
ReFS (Resilient File System)
Последняя разработка Microsoft, доступная для серверов Windows 8 и 10. Архитектура файловой системы в основном организована в виде B + -tree. Файловая система ReFS обладает высокой отказоустойчивостью благодаря реализации новых функций:
- Copy-on-Write (CoW) – никакие метаданные не изменяются без копирования;
- данные записываются на новое дисковое пространство, а не поверх существующих файлов;
- при модификации метаданных новая копия хранится в свободном дисковом пространстве, затем система создает ссылку из старых метаданных на новую версию.
Все это позволяет повысить надежность хранения файлов, обеспечивает быстрое и легкое восстановление данных.
Файловые системы macOS
Для операционной системы macOS компания Apple использует собственные разработки файловых систем:
![Файловые системы macOS]()
- HFS+, которая является усовершенствованной версией HFS, ранее применяемой на компьютерах Macintosh, и ее более соверешенный аналог APFS. Стандарт HFS+ используется во всех устройствах под управлением продуктов Apple, включая компьютеры Mac, iPod, а также Apple X Server.
- Кластерная файловая система Apple Xsan, созданная из файловых систем StorNext и CentraVision, используется в расширенных серверных продуктах. Эта файловая система хранит файлы и папки, информацию Finder о просмотре каталогов, положениях окна и т.д.
Файловые системы Linux
В отличие от ОС Windows и macOS, ограничивающих выбор файловой системы предустановленными вариантами, Linux предоставляет возможность использования нескольких ФС, каждая из которых оптимизирована для решения определенных задач. Файловые системы в Linux используются не только для работы с файлами на диске, но и для хранения данных в оперативной памяти или доступа к конфигурации ядра во время работы системы. Все они включены в ядро и могут использоваться в качестве корневой файловой системы.
![Файловая система Линукс]()
Основные файловые системы, используемые в дистрибутивах Linux:
Ext2, Ext3, Ext4 или Extended Filesystem – стандартная файловая система, первоначально разработанная еще для Minix. Содержит максимальное количество функций и является наиболее стабильной в связи с редкими изменениями кодовой базы. Начиная с ext3 в системе используется функция журналирования. Сегодня версия ext4 присутствует во всех дистрибутивах Linux.
JFS или Journaled File System разработана в IBM в качестве альтернативы для файловых систем ext. Сейчас она используется там, где необходима высокая стабильность и минимальное потребление ресурсов (в первую очередь в многопроцессорных компьютерах). В журнале хранятся только метаданные, что позволяет восстанавливать старые версии файлов после сбоев.
ReiserFS также разработана в качестве альтернативы ext3, поддерживает только Linux. Динамический размер блока позволяет упаковывать несколько небольших файлов в один блок, что предотвращает фрагментацию и улучшает работу с небольшими файлами. Недостатком является риск потери данных при отключении энергии.
XFS рассчитана на файлы большого размера, поддерживает диски до 2 терабайт. Преимуществом системы является высокая скорость работы с большими файлами, отложенное выделение места, увеличение разделов на лету, незначительный размер служебной информации. К недостаткам относится невозможность уменьшения размера, сложность восстановления данных и риск потери файлов при аварийном отключении питания.
Btrfs или B-Tree File System легко администрируется, обладает высокой отказоустойчивостью и производительностью. Используется как файловая система по умолчанию в OpenSUSE и SUSE Linux.
Другие ФС, такие как NTFS, FAT, HFS, могут использоваться в Linux, но корневая файловая система на них не устанавливается, поскольку они для этого не предназначены.
Дополнительные файловые системы
В операционных системах семейства Unix BSD (созданы на базе Linux) и Sun Solaris чаще всего используются различные версии ФС UFS (Unix File System), известной также под названием FFS (Fast File System). В современных компьютерных технологиях данные файловые системы могут быть заменены на альтернативные: ZFS для Solaris, JFS и ее производные для Unix.
Кластерные файловые системы включают поддержку распределенных хранилищ, расширяемость и модульность. К ним относятся:
- ZFS – «Zettabyte File System» разработана для распределенных хранилищ Sun Solaris OS;
- Apple Xsan – эволюция компании Apple в CentraVision и более поздних разработках StorNext;
- VMFS (Файловая система виртуальных машин) разработана компанией VMware для VMware ESX Server;
- GFS – Red Hat Linux именуется как «глобальная файловая система» для Linux;
- JFS1 – оригинальный (устаревший) дизайн файловой системы IBM JFS, используемой в старых системах хранения AIX.
Практический пример использования файловых систем
Владельцы мобильных гаджетов для хранения большого объема информации используют дополнительные твердотельные накопители microSD (HC), по умолчанию отформатированные в стандарте FAT32. Это является основным препятствием для установки на них приложений и переноса данных из внутренней памяти. Чтобы решить эту проблему, необходимо создать на карточке раздел с ext3 или ext4. На него можно перенести все файловые атрибуты (включая владельца и права доступа), чтобы любое приложение могло работать так, словно запустилось из внутренней памяти.
Операционная система Windows не умеет делать на флешках больше одного раздела. С этой задачей легко справится Linux, который можно запустить, например, в виртуальной среде. Второй вариант - использование специальной утилиты для работы с логической разметкой, такой как MiniTool Partition Wizard Free . Обнаружив на карточке дополнительный первичный раздел с ext3/ext4, приложение Андроид Link2SD и аналогичные ему предложат куда больше вариантов.
![Файловая система для microSD]()
Флешки и карты памяти быстро умирают как раз из-за того, что любое изменение в FAT32 вызывает перезапись одних и тех же секторов. Гораздо лучше использовать на флеш-картах NTFS с ее устойчивой к сбоям таблицей $MFT. Небольшие файлы могут храниться прямо в главной файловой таблице, а расширения и копии записываются в разные области флеш-памяти. Благодаря индексации на NTFS поиск выполняется быстрее. Аналогичных примеров оптимизации работы с различными накопителями за счет правильного использования возможностей файловых систем существует множество.
Надеюсь, краткий обзор основных ФС поможет решить практические задачи в части правильного выбора и настройки ваших компьютерных устройств в повседневной практике.
Читайте также:
.jpg)
.jpg)