Файловые системы

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

  Рисунок 4 Физическая организация файла  
а - непрерывное размещение; б - связанный список блоков;  
в - связанный список индексов; г - перечень номеров блоков 

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

  В заключение рассмотрим задание физического расположения файла путем простого перечисления номеров блоков, занимаемых этим файлом. ОС UNIX использует вариант данного способа, позволяющий обеспечить фиксированную длину адреса, независимо от размера файла. Для хранения адреса файла выделено 13 полей. Если размер файла меньше или равен 10 блокам, то номера этих блоков непосредственно перечислены в первых десяти полях адреса. Если размер файла больше 10 блоков, то следующее 11-е поле содержит адрес блока, в котором могут быть расположены еще 128 номеров следующих блоков файла. Если файл больше, чем 10+128 блоков, то используется 12-е поле, в котором находится номер блока, содержащего 128 номеров блоков, которые содержат по 128 номеров блоков данного файла. И, наконец, если файл больше 10+128+128(128, то используется последнее 13-е поле для тройной косвенной адресации, что позволяет задать адрес файла, имеющего размер максимум 10+ 128 + 128(128 + 128(128(128.  
 
 
 
 
 

  2. Общие понятия файловой системы

  2.1. Общая модель файловой системы

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

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

  Рисунок 5 Общая модель файловой системы

  В других файловых системах, в которых  один и тот же файл может иметь  несколько символьных имен, на данном уровне просматривается цепочка  каталогов для определения уникального  имени файла. В файловой системе UNIX, например, уникальным именем является номер индексного дескриптора файла (i-node).

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

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

  На  логическом уровне определяются координаты запрашиваемой логической записи в файле, то есть требуется определить, на каком расстоянии (в байтах) от начала файла находится требуемая логическая запись. При этом абстрагируются от физического расположения файла, он представляется в виде непрерывной последовательности байт. Алгоритм работы данного уровня зависит от логической организации файла. Например, если файл организован как последовательность логических записей фиксированной длины l, то n-ая логическая запись имеет смещение l((n-1) байт. Для определения координат логической записи в файле с индексно-последовательной организацией выполняется чтение таблицы индексов (ключей), в которой непосредственно указывается адрес логической записи.

  Рисунок 6 Функции физического уровня файловой системы

  Исходные  данные:  
V - размер блока  
N - номер первого блока файла  
S - смещение логической записи в файле

  Требуется определить на физическом уровне:

  n - номер блока, содержащего требуемую  логическую запись 

  s - смещение логической записи  в пределах блока 

  n = N + [S/V], где [S/V] - целая часть числа  S/V  
s = R [S/V] - дробная часть числа S/V

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

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

  2.2. Современные архитектуры файловых систем

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

  Новая файловая система имеет многоуровневую структуру (рисунок 7), на верхнем уровне которой располагается так называемый переключатель файловых систем (в Windows 95, например, такой переключатель называется устанавливаемым диспетчером файловой системы - installable filesystem manager, IFS). Он обеспечивает интерфейс между запросами приложения и конкретной файловой системой, к которой обращается это приложение. Переключатель файловых систем преобразует запросы в формат, воспринимаемый следующим уровнем - уровнем файловых систем.

  Рисунок 7. Архитектура современной файловой системы

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

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

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

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

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

  3. Виды файловых систем

  3.1 Файловая система FAT 

  Большинство существующих на сегодняшний день файловых систем построены на основе таблицы  размещения файлов (File Allocation Table - FAT), которая  содержит дорожки данных в каждом кластере на диске. Существует несколько типов файловой системы FAT - FAT 12, FAT 16 и FAT 32. Они отличаются количеством цифр, используемых в таблице размещения файлов. Другими словами, в FAT 32 используется 32-разрядное число для хранения дорожки данных в каждом кластере, в FAT 16 - 16-разрядное число и т.д. В настоящее время существуют следующие типы файловой системы FAT:

• FAT 12, используемая в разделах емкостью не более 16 Мбайт (например, дискета);
• FAT 16, используемая в разделах емкостью от 16 Мбайт до 2 Гбайт;
• FAT 32, используемая (необязательно) в разделах емкостью от 512 Мбайт до 2 Тбайт.

     Файловые системы FAT 12 и FAT 16 изначально применяются в DOS и Windows и поддерживаются практически  всеми известными на сегодняшний  день операционными системами. Большинство персональных компьютеров поставляется с жесткими дисками, на которых установлена одна из файловых систем FAT. 
     Файловая система FAT 32 поддерживается операционной системой Windows 95 и более поздними версиями, а также Windows 2000. 
     Для обеспечения пользовательским приложениям доступа к файлам независимо от типа используемого диска в операционной системе предусмотрено несколько структур. Эти структуры поддерживаются системами Windows и представлены ниже в порядке расположения на диске:

• загрузочные секторы главного и дополнительного разделов;
• загрузочный сектор логического диска;
• таблицы размещения файлов (FAT);
• корневой каталог;
• область данных;
• цилиндр для выполнения диагностических операций чтения/записи.

 Информация о  каждом разделе сохраняется в загрузочном секторе раздела (или логического диска) в начале каждого раздела. Существует также основная таблица списка разделов, помещенная в загрузочный сектор главного раздела. 
     Загрузочный сектор главного раздела (или главная загрузочная запись (Master Boot Record - MBR)) является первым сектором на жестком диске (цилиндр 0, головка 0, сектор 1) и состоит из двух элементов.