Файловые структуры

Файлы данных

 

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

 

 

Программная часть файловой системы, определяемая ее назначением, должна содержать следующие компоненты:

Ø средства взаимодействия с процессами пользователей, которые должны обеспечивать прием и интерпретацию запросов на обработку файлов, а также сообщать пользователям в приемлемой форме о результатах выполненной обработки;

Ø средства, реализующие методы доступа к внутренним составным элементам файла и к файлу в целом, а также обеспечивать синхронизацию работы с системой управления аппаратурой ввода-вывода (назовем ее СУВВ);

Ø средства, обеспечивающие распределение внешней памяти для хранения файлов, а также ее освобождение по мере уничтожения файлов;

Ø средства учета расположения как файлов в целом, так и отдельных его составных элементов.

Все перечисленные средства составляют логический уровень управления данными, а СУВВ осуществляет физический уровень управления данными. Именно в таком обобщенном виде файловая система выступает как интерфейс между программными процессами и файлами (Ошибка! Источник ссылки не найден.).

Рисунок 10.1 - Схема взаимодействия программных процессов и файлов

 

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

Ø Файловая система должна обеспечивать прежде всего удобство и простоту взаимодействия с ней пользователя.

Ø Файловая система должна обеспечивать возможность хранить произвольное число файлов без ограничений объема.

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

Ø Для каждого файла должен быть обеспечен некоторый метод доступа к его внутренним составным элементам (метод доступа - это способ адресации к составным элементам файла на основе его логической структуры).

Ø В мультипрограммных ОС одной из первостепенных задач является обеспечение эффективной (по минимуму времени и расхода оперативной памяти) работы файловой системы, обеспечение гарантии сохранности файлов, защиты от несанкционированных доступов пользователей к "чужим" файлам.

Ø Традиционная задача файловых систем - сокрытие от программистов реального расположения информации на уровне внешней памяти, обеспечение независимости программ от конкретной конфигурации ЭВМ.

Ø Файловая система должна обеспечивать стандартную реакцию на ошибки, возникающие при обмене данными между уровнями памяти.

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

Ø Несмотря на наличие больших объемов внешней памяти, ее требуется эффективно распределять, как любой другой ресурс, среди множества процессов. Файловая система должна обеспечивать не только раздельное, но и при необходимости и совместное использование файлов как критических ресурсов. Причем механизмы реализации данного требования должны быть максимально скрыты от пользователя и минимально влиять на организацию мультипрограммной работы ЭВМ.

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

Основным атрибутом файла является его имя. Имя файла- это символьная строка, длина которой зависит от конкретной файловой системы. Так, в файловой системе FAT (File Allocation Table), используемой в MS DOS, длина имени файла не может превышать 11 символов, 3 из которых предназначены для расширения. В ОС UNIX System V под имя файла отводится 14 символов, а в файловой системе NTFS (New Technology File System) для Windows NT - 255 символов. От файловой системы также зависит, какие символы могут использоваться в имени файла. Поскольку существуют различные файловые системы, перед их разработчиками встает проблема обеспечения совместимости между ними. Например, система, позволяющая присваивать файлам длинные имена, должна уметь корректно преобразовывать их в короткие. Но, к сожалению, пока не удалось решить проблему пользования единственного имени файла в различных файловых системах. Это связано, в первую очередь, с различием наборов разрешенных символов в различных системах.

Другие атрибуты файла, которые могут использоваться файловой системой, перечислены ниже:

Ø текущий размер файла;

Ø максимальный размер файла;

Ø длина записи;

Ø времена создания, последнего доступа и последнего изменения;

Ø владелец файла;

Ø создатель файла;

Ø информацияо доступе к файлу;

Ø пароль для доступа к файлу;

Ø признак "только для чтения";

Ø признак "скрытый файл";

Ø признак "системный файл";

Ø признак "архивный файл";

Ø признак "двоичный/символьный";

Ø признак "временный";

Ø признак блокировки.

Современные файловые системы ЭВМ, работающих в мультипрограммном режиме, способны обслуживать сотни и тысячи файлов. Очевидно, что роль учетного механизма в составе файловой системы очень важна. Общепринятым приемом является сведение учетной информации о местах расположения файлов в одно место. Доступ к данным файлов при этом организуется через каталог. Каталог содержит файлы, объединенные по какому-либо признаку - их создатель, их тип, тема и т. д. Каталог- это файл, который содержит информацию о входящих в него файлах. Каталогов на носителе может быть много, и они могут иметь различные степени вложенности.

В ряде ОС на каждом томе имеется единственный каталог, который содержит сведения обо всех файлах, находящихся на этом томе. Такая файловая система называется одноуровневой. Есть системы, в которых на томе имеется несколько каталогов файлов, никак между собой не связанных. Основное соглашение, которое выдерживается при организации подобных каталогов - это фиксация места расположения каталога (-ов) на томе и программная доступность к нему файловой системы.

Структура каталогов в зависимости от файловой системы может быть древовидной, когда один файл может входить только в один каталог, и сетевой, когда один файл может входить в различные каталоги. В так называемых DOS-совместимых (впрочем, и в некоторых других) системах к файлу обращаются с помощью полного имени, которое состоит:

Ø из пути (англ. Path) - последовательности имен каталогов, в которых содержится файл, разделенных символом \;

Ø собственно имени файла (англ. Name);

Ø расширения (англ. Extension), которое является необязательным элементом и, как правило, информирует о типе данных, хранимых в файле. Расширение отделяется от имени точкой (.)

В качестве примера может быть приведено следующее имя файла:

C:\DIR1\DIR2\DIR3\NAME.EXT

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

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

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

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

Основной задачей, которую решает файловая система, является обеспечение взаимодействия программ и физических устройств ввода/вывода, таких как накопители на жестких дисках, магнитных лентах и т. д.

Основные функции, выполняемые файловой системой, можно условно разделить на две группы:

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

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

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

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

В качестве примера рассмотрим файловую систему NTFS, разработанную для Windows NT.

Особенности:

Ø 64-разрядные адреса, т.е. теоретически может поддерживать 264*216 байт (1 208 925 819 Пбайт=1Yбайт).

Ø Размеры блока (кластера) от 512байт до 64 Кбайт, для большинства используется 4Кбайта.

Ø Поддержка больших файлов.

Ø Имена файлов ограничены 255 символами Unicode.

Ø Длина пути ограничивается 32 767 (215) символами Unicode.

Ø Имена чувствительны к регистру, my.txt и MY.TXT это разные файлы (но из-за Win32 API использовать нельзя), это заложено на будущее.

Ø Журналируемая файловая система, т.е. не попадет в противоречивое состояние после сбоев.

Ø Контроль доступа к файлам и каталогам.

Ø Поддержка жестких и символических ссылок.

Ø Поддержка сжатия и шифрования файлов.

Ø Поддержка дисковых квот.

Главная файловая таблица MFT(Master File Table) - главная структура данных в каждом томе, записи фиксированные по 1Кбайту. Каждая запись описывает один каталог или файл. Для больших файлов могут использоваться несколько записей, первая запись называется - базовой записью.

MFT представляет собой обычный файл (размером до 248 записей), который может располагаться в любом месте на диске.

Рисунок 10.2 - Главная файловая таблица 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 серий.

 

Рисунок 10.3 - Запись MFT для 9-блочного файла, состоящего из трех сегментов (серий).

 

Вся запись помещается в одну запись MFT (файл не сильно фрагментирован).

Заголовок содержит количество блоков (9 блоков).

Каждая серия записывается в виде пары, дисковый адрес - количество блоков (20-4, 64-2, 80-3).

Каждая пара, при отсутствие сжатия, это два 64-разрядные числа (16 байт на пару).

Многие адреса содержат большое количество нулей, сжатие делается за счет убирания нулей в старших байтах. В результате для пары требуется чаще всего 4байта.

Если файл сильно фрагментирован, требуется несколько записей MFT.

 

 

Рисунок 10.4 - Три записи MFT для сильно фрагментированного файла. В первой записи указывается индексы на дополнительные записи.

 

Может потребоваться очень много индексов MFT, так что индексы не поместятся в запись. В этом случае список хранится не в MFT, а в файле.

 

Рисунок 10.5 - Запись MFT для небольшого каталога

 

Поиск файла в каталоге по имени состоит в последовательном переборе имен файлов.

Для больших каталогов используется другой формат. Используется дерево В+, обеспечивающее поиск в алфавитном порядке.

Если файл помечен как сжатый, то система автоматически сжимает при записи, а при чтении происходит декомпрессия.

Алгоритм работы:

1. Берутся для изучения первые 16 блоков файла (не зависимо от сегментов файла).

2. Применяется к ним алгоритм сжатия.

3. Если полученные данные можно записать хотя бы в 15 блоков, они записываются в сжатом виде. Если их можно записать только в 16 блоков, то они записываются в несжатом виде.

4. Алгоритм повторяется для следующих 16 блоков.

 

 

Рисунок 10.6 - Пример 48-блочного файла, сжатого до 32 блоков

 

 

Рисунок 10.7 - Запись MFT для предыдущего файла.

 

Недостатки сжатия:

Ø Как видно из рисунка, сжатие приводит к сильной фрагментации.

Ø Чтобы прочитать сжатый блок системе придется распаковать весь сегмент. Поэтому сжатие применяют к 16 блокам, если увеличить количество блоков, уменьшится производительность (но возрастет эффективность сжатия).

Любую информацию, если она не зашифрована, можно прочитать, получив доступ. Поэтому самая надежная защита информации от несанкционированного доступа - шифрование.

Если файл помечен как шифрованный, то система автоматически шифрует при записи, а при чтении происходит дешифрация.

Шифрование и дешифрование выполняет не сама NTFS, а специальный драйвер EFS (Encrypting File System).

Каждый блок шифруется отдельно.

В Windows 2000 используется случайно сгенерированный 128-разрядный ключ для каждого файла. Этот ключ шифруется открытым ключом пользователя и сохраняется на диске.

Рисунок 10.8 - Шифрование файлов в NTFS