Файловые системы. Лекция 6 Файловая система, ввод и вывод информации. Вводвывод и файловая система 1 Задачи ос по управлению файлами и устройствами
 Скачать 0.51 Mb.
|
|
| Boot Block | Super Block | Spare Block | Band 1 | Bit map 1 | Bit map 2 | Band 2 | Band 3 | Bit map 3 | Bit map 4 | Band 4 | …... |
Загрузочный блок Boot Block располагается в секторах с 0 по 15, содержит: имя тома, его серийный номер, блок параметров BIOS, программу начальной загрузки.
Блок Super block содержит:
- указатель на список битовых карт (bitmap block list);
- указатель на список дефектных блоков (bad block list):
- указатель на группу каталогов (directory band);
- указатель на файловый узел (F-node) корневого каталога;
-дату последней проверки раздела программой CHKDSK.
Резервный блок Spare block размещается в 17 секторе диска содержит:
- указатель на карту аварийного замещения (hotfix map или hotfix-areas);
- указатель на список свободных запасных блоков (directory emergency free block list), используемых для операций на почти переполненном диске
- ряд системных флагов и дескрипторов.
Всё остальное дисковое пространство в HPFS разбито на части («полосы», «ленты» из смежных секторов). Каждая такая группа данных занимает на диске пространство в 8 Мбайт и имеет свою собственную битовую карту распределения секторов. Эти битовые карты показывают, какие секторы данной полосы заняты (если бит имеет значение 1), а какие свободны (если бит имеет значение 0). Последовательность полос и карт выглядит следующим образом: битовая карта, битовая ката, лента с данными, лента с данными, битовая карта, битовая карта и т.д. Такое расположение «лент» позволяет непрерывно разместить на жестком диске файл размером до 16 Мбайт и в то же время не удалять от самих файлов информацию об их местонахождении.
Дисковое пространство в HPFS выделяется блоками. Размер блока- 1 сектор.
Каждый файл и каталог диска имеет свой файловый узел F-Node.
Каждый объект F-Node занимает 1 сектор и всегда располагается поблизости от своего файла или каталога. Объект F-Node содержит длину и первые 15 символов имени файла, специальную служебную информацию, статистику по доступу к файлу, расширенные атрибуты файла и список прав доступа (или его часть), ассоциативную информацию о расположении и подчинении и т.д.
HPFS старается избежать фрагментации. Если файл непрерывен, то его размещение на диске описывается двумя 32-битными числами. Первое число представляет собой указатель на первый блок файла, а второе-длину экстента, то есть число следующих друг за другом блоков, принадлежащих файлу. Фрагментация происходит, когда на диске нет непрерывного свободного участка, чтобы разместить файл целиком. В этом случае файл разбивается на несколько экстентов и располагается на диске отдельно. Алгоритм работы файловой системы HPFS работают таким образом, чтобы по возможности размещать файлы в последовательных смежных секторах диска, что обеспечивает максимально быстрый доступ к данным впоследствии.
«Полоса» находящаяся в центре диска, используется для хранения каталогов. Она называется directory band. Такое расположение информационной структуры значительно сокращает среднее время позиционирования головок чтения/записи. Сами каталоги организованы в виде бинарного дерева, что существенно сокращает время поиска.
Если файловая система HPFS сталкивается с проблемой в процессе записи данных на диск, она выводит на экран сообщение об ошибке. Затем HPFS сохраняет ту информацию, которая должна была быть записана в дефектный сектор, в одном из запасных секторов. После этого CHKDSK вносит повреждённый сектор в список дефектных блоков, который хранится в дополнительном блоке HPFS, и возвращает освобожденный сектор в список свободных запасных секторов резервного блока. Затем удаляет запись из карты аварийного замещения и записывает отредактированную карту на диск.
HPFS относится к так называемым монтируемым файловым системам. Это означает, что она не встроена в ОС, а добавляется к ней при необходимости.
Файловая система NTFS
Файловая система NTFS была разработана для Windows NT.
Особенности:
64-разрядные адреса, т.е. теоретически может поддерживать 2^64*2^16 байт (1 208 925 819 Пбайт1Йбайт(280)).
Размеры блока (кластера) от 512байт до 2 Мб, для большинства используется 4Кбайта.
Поддержка больших файлов.
Имена файлов ограничены 255 символами Unicode.
Длина пути ограничивается 32 767 (2^15) символами Unicode.
Имена чувствительны к регистру, my.txt и MY.TXT это разные файлы (но из-за Win32 API использовать нельзя), это заложено на будущее.
Журналируемая файловая система, т.е. не попадет в противоречивое состояние после сбоев.
Контроль доступа к файлам и каталогам.
Поддержка жестких и символических ссылок.
Поддержка сжатия и шифрования файлов.
Поддержка дисковых квот.
Главная файловая таблица MFT (Master File Table) - главная структура данных в каждом томе, записи фиксированные по 1Кбайту. Каждая запись описывает один каталог или файл. Для больших файлов могут использоваться несколько записей, первая запись называется - базовой записью.
MFT представляет собой обычный файл (размером до 2^48 записей), который может располагаться в любом месте на диске.
Главная файловая таблица MFT, каждая запись ссылается на файл или каталог.
Первые 16 записей MFT зарезервированы для файлов метаданных. Каждая запись описывает нормальный файл, имена этих файлов начинаются с символа "$".
Каждая запись представляет собой последовательность пар (заголовок атрибута, значение).
Некоторые записи метаданных в MFT:
0) Первая запись описывает сам файл MFT, и содержит все блоки файла MFT. Номер первого блока файла MFT содержится в загрузочном блоке.
1) Дубликат файла MFT, резервная копия.
2) Журнал для восстановления, например, перед созданием, удалением каталога делается запись в журнал. Система не попадет в противоречивое состояние после сбоев.
3) Информация о томе (размер, метка и версия)
4) Определяются атрибуты для MFT записей.
6) Битовый массив использованных блоков - для учета свободного места на диске
7) Указывает на файл начальной загрузки
Атрибуты, используемые в записях MFT:
Стандартная информация - флаговые биты (только чтение, архивный), временные штампы и т.д.
Имя файла - имя файла в кодировке Unicode, файлы могут повторятся в формате MS-DOS 8+3.
Список атрибутов - расположение дополнительных записей MFT
Идентификатор объекта - 64-разрядный идентификатор файла, уникальный для данного тома.
Точка повторного анализа - используется для символьных ссылок и монтирования устройств.
Название тома
Версия тома
Корневой индекс - используется для каталогов
Размещение индекса - используется для очень больших каталогов
Битовый массив - используется для очень больших каталогов
Поток данных утилиты регистрации - используется для шифрования
Данные - поточные данные, может повторяться, используется для хранения самого файла. За заголовком следует список дисковых адресов, определяющий положение файла на диске, если файл очень маленький (несколько сотен байт), то следует сам файл (такой файл называется - непосредственный файл).
Как привило, все данные файла не помещаются в запись MFT.
Дисковые блоки файлам назначаются по возможности в виде серий последовательных блоков (сегментов файлов). В идеале файл должен быть записан в одну серию (не фрагментированный файл), файл, состоящий из n блоков, может быть записан от 1 до n серий.
Запись MFT для 9-блочного файла, состоящего из трех сегментов (серий).
Вся запись помещается в одну запись MFT (файл не сильно фрагментирован).
Заголовок содержит количество блоков (9 блоков).
Каждая серия записывается в виде пары, дисковый адрес - количество блоков (20-4, 64-2, 80-3).
Каждая пара, при отсутствии сжатия, это два 64-разрядные числа (16 байт на пару).
Многие адреса содержат большое количество нулей, сжатие делается за счет убирания нулей в старших байтах. В результате для пары требуется чаще всего 4байта.
Если файл сильно фрагментирован, требуется несколько записей MFT.
Три записи MFT для сильно фрагментированного файла.
В первой записи указывается индексы на дополнительные записи.
Может потребоваться очень много индексов MFT, так что индексы не поместятся в запись. В этом случае список хранится не в MFT, а в файле.
Запись MFT для небольшого каталога
Поиск файла в каталоге по имени состоит в последовательном переборе имен файлов.
Для больших каталогов используется другой формат. Используется дерево В+, обеспечивающее поиск в алфавитном порядке.
2.1 Поиск файла по имени
При создании файла, программа обращается к библиотечной процедуре
CreateFile("C:\windows\readmy.txt", ...)
Этот вызов попадает в совместно используемую библиотеку уровня пользователя kernel32.dll, где \??\ помещается перед именем файла, и получается строка:
\??\C:\windows\readmy.txt
Это имя пути передается системному вызову NtFileCreate в качестве параметра.
Этапы поиска файла C:\windows\readmy.txt
2.2 Сжатие файлов
Если файл помечен как сжатый, то система автоматически сжимает при записи, а при чтении происходит декомпрессия.
Алгоритм работы:
Берутся для изучения первые 16 блоков файла (не зависимо от сегментов файла).
При меняется к ним алгоритм сжатия.
Если полученные данные можно записать хотя бы в 15 блоков, они записываются в сжатом виде.
Если их можно записать только в 16 блоков, то они записываются в несжатом виде.
Алгоритм повторяется для следующих 16 блоков.
Пример 48-блочного файла, сжатого до 32 блоков
Запись MFT для предыдущего файла.
Недостатки сжатия:
Как видно из рисунка, сжатие приводит к сильной фрагментации.
Чтобы прочитать сжатый блок системе придется распаковать весь сегмент. Поэтому сжатие применяют к 16 блокам, если увеличить количество блоков, уменьшится производительность (но возрастет эффективность сжатия).
2.3 Шифрование файлов
Любую информацию, если она не зашифрована, можно прочитать, получив доступ. Поэтому самая надежная защита информации от несанкционированного доступа - шифрование.
Даже если у вас украдут винчестер, прочесть данные не смогут (большинство не сможет).
Если файл помечен как шифрованный, то система автоматически шифрует при записи, а при чтении происходит дешифрация.
Шифрование и дешифрование выполняет не сама NTFS, а специальный драйвер EFS (Encrypting File System).
Каждый блок шифруется отдельно.
В Windows 2000 используется случайно сгенерированный 128-разрядный ключ для каждого файла. Этот ключ шифруется открытым ключом пользователя и сохраняется на диске.
Шифрование файлов в NTFS
Примеры других файловых систем
3.1 Файловая система ISO 9660
Стандарт принят в 1988 г.
По стандарту диски могут быть разбиты на логические разделы, но мы будем рассматривать диски с одним разделом.
Как вы знаете из предыдущих лекций: блоки записываются последовательно; по спирали; сектора по 2352 байта.
Порядок записи информации:
Каждый CD-ROM начинается с 16 блоков (неопределенных ISO 9660), эта область может быть использована для размещения загрузчика ОС или для других целей.
Дальше один блок основного описателя тома - хранит общую информацию о CD-ROM, в нее входит:
- идентификатор системы (32байта)
- идентификатор тома (32байта)
- идентификатор издателя (128байт)
- идентификатор лица, подготовившего данные (128байт)
- имена трех файлов, которые могут содержать краткий обзор, авторские права и библиографическая информация.
- ключевые слова: размер логического блока (как правило 2048, но могут быть 4096, 8192 и т.д.); количество блоков; дата создания; дата окончания срока службы диска.
- описатель корневого каталога (номер блока содержащего каталог).
Могут быть дополнительные описатели тома, подобные основному.
В стандарте ISO 9660 определены три уровня ограничений:
- имена файлов = 8-3
- имена каталогов 8 символов, каталоги без расширений
- глубина вложенности каталогов ограничена восемью
- файлы должны быть непрерывными
имена файлов и каталогов до 31 символа
- имена файлов и каталогов до 31 символа
- файлы могут быть не непрерывными, состоять из разделов
3.1.1 Рок-ридж расширения для UNIX
Это расширение было создано, чтобы файловая система UNIX была представлена на CD-ROM.
3.1.2 HFS расширения для Macintosh
Иерархическая файловая система компьютеров Macintosh, не совместима ни с какими другими файловыми системами и называется Hierarchical File System (HFS).
3.1.3 Файловая система UDF (Universal Disk Format)
Изначально созданная для DVD, с версии 1.50 добавили поддержку CD-RW и CD-R.
Эта файловая система позволяет дописывать диски, а также поддерживает большие размеры файлов и длинные имена файлов.
3.2 Файловая система CP/M
CP/M (Control Program for Microcomputers) - операционная система, предшественник MS-DOS.
В ее файловой системе только один каталог, с фиксированными записями по 32 байта.
Имена файлов - 8+3 символов верхнего регистра.
После каждой перезагрузки рассчитывается битовый массив занятых и свободных блоков. Массив находится постоянно в памяти (для 180Кбайтного диска 23 байта массива). После завершения работы, он не записывается на диск.
Каталоговая запись CP/M
Видно, что максимальный размер файла 16Кбайт (16*1Кбайт).
Для файлов размером от 16 до 32 Кбайт можно использовать две записи. Для до 48 Кбайт три записи и т.д.
Порядковый номер записи хранится в поле экстент.
Код пользователя - каждый пользователь мог работать только со своими файлами.
Порядок чтения файлов:
Файл открывается системным вызовом open
Читается каталоговая запись, из которой получает информацию о всех блоках.
Вызывается системный вызов read
3.3 Файловые системы LINUX
Изначально использовалась файловая система MINIX с ограничениями: 14 символов для имени файла и размер файла 64 Мбайта.
После была создана файловая система EXT с расширением: 255 символов для имени файла и размер файла 2Гбайта.
Система была достаточно медленной.
3.3.1 Файловая система EXT2
Эта файловая система стала основой для LINUX.
Вместо групп цилиндров используются группы блоков.
Размещение файловой системы EXT2 на диске
Другие особенности:
Размер блока 1 Кбайт
Размер каждого i-узла 128 байт.
i-узел содержит 12 прямых и 3 косвенных адресов, длина адреса в i-узле стала 4 байта, что обеспечивает поддержку размера файла чуть более 16Гбайт.
Особенности работы файловой системы:
Создание новых каталогов распределяется равномерно по группам блоков, чтобы в каждой группе было одинаковое количество каталогов.
Новые файлы старается создавать в группе, где и находится каталог.
При увеличении файла система старается новые блоки записывать ближе к старым.
Благодаря этому файловую систему не нужно дефрагментировать, она не способствует фрагментации файлов (в отличии от NTFS), что проверено многолетним использованием.
3.3.2 Файловая система EXT3 и EXT4
В отличие от EXT2, EXT3 является журналируемой файловой системой, т.е. не попадет в противоречивое состояние после сбоев. Но она полностью совместима с EXT2.
Разработанная в Red Hat
В данный момент является основной для LINUX.
Драйвер Ext3 хранит полные точные копии модифицируемых блоков (1КБ, 2КБ или 4КБ) в памяти до завершения операции. Это может показаться расточительным. Полные блоки содержат не только изменившиеся данные, но и не модифицированные.
Такой подход называется "физическим журналированием", что отражает использование "физических блоков" как основную единицу ведения журнала. Подход, когда хранятся только изменяемые байты, а не целые блоки, называется "логическим журналированием" (используется XFS). Поскольку ext3 использует "физическое журналирование", журнал в ext3 имеет размер больший, чем в XFS. За счет использования в ext3 полных блоков, как драйвером, так и подсистемой журналирования нет сложностей, которые возникают при "логическом журналировании".
3.3.3 Файловая система XFS
XFS - журналируемая файловая система разработанная Silicon Graphics, но сейчас выпущенная открытым кодом (open source).
XFS была создана в начале 90ых (1992-1993) фирмой Silicon Grapgics (сейчас SGI) для мультимедийных компьютеров с ОС Irix. Файловая система была ориентирована на очень большие файлы и файловые системы. Особенностью этой файловой системы является устройство журнала - в журнал пишется часть метаданных самой файловой системы таким образом, что весь процесс восстановления сводится к копированию этих данных из журнала в файловую систему. Размер журнала задается при создании системы, он должен быть не меньше 32 мегабайт; а больше и не надо - такое количество незакрытых транзакций тяжело получить.
Некоторые особенности:
Более эффективно работает с большими файлами.
Имеет возможность выноса журнала на другой диск, для повышения производительности.
Сохраняет данные кэша только при переполнении памяти, а не периодически как остальные.
В журнал записываются только мета-данные.
Используются B+ trees.
Используется логическое журналирование
3.3.4 Файловая система RFS
RFS (RaiserFS - журналируемая файловая система разработанная Namesys.
Некоторые особенности:
Более эффективно работает с большим количеством мелких файлов, в плане производительности и эффективности использования дискового пространства.
Использует специально оптимизированные b* balanced tree (усовершенствованная версия B+ дерева)
Динамически ассигнует i-узлы вместо их статического набора, образующегося при создании "традиционной" файловой системы.
Динамические размеры блоков.
3.3.4 Файловая система JFS
JFS (Journaled File System) -журналируемая файловая система разработанная IBM для ОС AIX, но сейчас выпущенная как открытый код.
Официальная информация на Journaled File System Technology for Linux
Некоторые особенности:
Журналы JFS соответствуют классической модели транзакций, принятой в базах данных
В журнал записываются только мета-данные
Размер журнала не больше 32 мегабайт.
Асинхронный режим записи в журнал - производится в моменты уменьшения трафика ввода/вывода
Используется логическое журналирование.
3.4 Сравнительная таблица некоторых современных файловых систем
| | NTFS | EXT4 | RFS | XFS | JFS |
| Хранение информации о файлах | MFT | inode | inode | inode | inode |
| Максимальный размер раздела | 16 Эбайт (260) | 1 Эбайт | 4 гигаблоков (т.к. блоки динамические) | 16 Эбайт | 32 Пбайт |
| Размеры блоков | от 512 байт до 64 Кбайт | 1 Кбайт - 4 Кбайт | До 64 Кбайт (сейчас фиксированы 4 Кбайт) | от 512 байт до 64 Кбайт | 512/1024/ 2048/4096 байт |
| Максимальное число блоков | 2^48 | 2^32 | | | 2^32 |
| Максимальный размер файла | 2^64 | 16 Тбайт (для 4Кбайт блоков) | 8 Тбайт | 8 Эбайт | 4 Пбайт (250) |
| Максимальная длина имени файла | 255 | 255 | | | |
| Журналирование | Да | Да | Да | Да | Да |
| Управление свободными блоками | | Нет | На основе битовой карты | B-деревья, индексированные по смещению и по размеру | Дерево+ Binary Buddy |
| Экстенты для свободного пространства | | Нет | Нет | Да | Нет |
| B-деревья для элементов каталогов | Да | Нет | Как поддерево основного дерева файловой системы | Да | Да |
| B-деревья для адресации блоков файлов | | Нет | Внутри основного дерева файловой системы | Да | Да |
| Экстенты для адресации блоков файлов | | Нет | Да (с 4 версии) | Да | Да |
| Данные внутри inode (небольшие файлы) | | Нет | Да | Да | Нет |
| Данные симво-льных ссылок внутри inode | | Нет | Да | Да | Да |
| Элементы каталогов внутри inode (небольшие каталоги) | | Нет | Да | Да | Да |
| Динамическое выделение inode/MFT | Да | Нет | Да | Да | Да |
| Структуры управления динамически выделяемыми inode | | Нет | Общее B*дерево | B+дерево | B+дерево с непрерывными областями inode |
| Поддержка разреженных файлов | Да | Нет | Да | Да | Да |
3.5 Файловая система NFS
NFS (NetworkFileSystem) - сетевая файловая система. Создана для объединения файловых систем по сети.
Устойчивость ФС. Устойчивость ФС к сбоям питания и пр.
Свойство устойчивости к сбоям питания (power-fault tolerance) является одной из важных характеристик файловой системы. Строго говоря, имеется в виду устойчивость не только к сбоям питания, но и к любой ситуации, при которой работа с ФС прекращается без выполнения операции размонтирования.
На самом деле, неожиданное прекращение работы с ФС может произойти не только при сбое питания, но и в следующих ситуациях:
извлечении носителя из дисковода;
нажатии кнопки RESET нетерпеливым пользователем;
фатальном аппаратном сбое;
аппаратном сбое, который сам по себе не был фатальным, но система не смогла правильно восстановиться, что привело к ее разрушению;
разрушении системы из-за чисто программных проблем.
В узком смысле слова «устойчивость» означает лишь то, что ФС после аварийной перезагрузки не обязательно нуждается в восстановлении. Такие ФС обеспечивают целостность собственных структур данных в случае сбоя, но, вообще говоря, не гарантируют целостности пользовательских данных в файлах. Поддержание целостности структур ФС обычно гораздо важнее, чем целостность неподписанных в момент сбоя пользовательских данных. Дело в том, что если при сбое оказывается испорчен создававшийся файл, это достаточно неприятно; если же окажется испорчена файловая система, в худшем случае это может привести к потере всех данных на диске, т.е. к катастрофе. Поэтому обычно обеспечению целостности структур ФС при сбоях уделяется гораздо больше внимания. Относительно пользовательских данных при серьезном обсуждении проблемы устойчивости к сбоям говорят не о гарантии их целостности, а об уменьшении вероятности их порчи.
Устойчивость ФС с FAT
Упоминавшаяся выше «врожденная» устойчивость к сбоям файловой системы FAT объясняется тем, что в этой ФС удаление блока из списка свободных и выделение его файлу производится одним действием – модификацией элемента FAT. Поэтому если во время этой процедуры произойдет сбой или диск будет вынут из дисковода, то ничего страшного не случится: просто получится файл, которому выделено на один блок больше, чем его длина, записанная в каталоге. При стирании этого файла все его блоки будут помечены как свободные, поэтому вреда практически нет.
Нужно отметить, что при активном использовании отложенной записи FAT и родственные ФС теряют это преимущество. Отложенная запись FAT является единственным способом добиться хоть сколько-нибудь приемлемой производительности от ФС с 32-битовым FAT. Поэтому после аварийной перезагрузки эти системы вынуждены запускать программу аварийного восстановления дисковых томов.
Устойчивость более сложных систем
Если же система хранит в одном месте список или карту свободных блоков, а в другом месте списки блоков, выделенных каждому файлу, как это делают HPFS или ФС систем семейства Unix, то при прерывании операции выделения места в неподходящий момент, могут либо теряться блоки (если мы сначала удаляем блок из списка свободных), либо получатся блоки, которые одновременно считаются и свободными, и занятыми (если мы сначала выделяем блок файлу).
Первая ситуация достаточно неприятна, вторая же просто недопустима: первый же файл, созданный после перевызова системы, будет «перекрещиваться» с испорченным. Поэтому все ОС, использующие файловые системы такого типа (системы семейства Unix, OS/2, Windows NT и т.д.), после аварийной перезагрузки первым делом проверяют свои ФС соответствующей программой восстановления.