20. Лекция: Виртуальные файловые системы (vfs). Реализации файловых систем. Сетевая файловая система nfs

В лекции рассмотрены следующие вопросы: виртуальные файловые системы (VFS); реализация файлов с помощью FAT (Windows) и индексных блоков (UNIX); управление внешней памятью; кэширование; файловые системы на основе журнала транзакций; сетевая файловая система NFS.

Содержание

• Введение

• Виртуальные файловые системы

• Реализация директорий

• Методы размещения файлов

• Файловые системы, основанные на расширениях

• Ссылочное размещение файла

• Индексируемое размещение

• Управление свободной внешней памятью

• Эффективность и производительность дисковой памяти

• Кэширование диска

• Проблемы восстановления файлов

• Сетевая файловая система NFS

• Ключевые термины

• Краткие итоги

• Набор для практики

  • Вопросы

  • Упражнения

  • Темы для курсовых работ, рефератов, эссе

Введение

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

Виртуальные файловые системы

Виртуальные файловые системы (VFS) обеспечивают объектно-ориентированный способ реализации файловых систем.

VFS обеспечивает единый интерфейс системных вызовов (API) для различных типов файловых систем, которые могут быть очень разными по своей реализации, включая сетевые файловые системы.

Данный API является набором операций над самой VFS, а не над каким-либо специфическим типом файловых систем.

Схема организации виртуальной файловой системы изображена на рис. 20.1.

Рис. 20.1.  Схема организации виртуальной файловой системы.

Реализация директорий

Директория – центральная системная структура в файловой системе, на которой основан поиск файлов. Поэтому эффективная реализация директорий особенно важна.

Наиболее простой метод реализации директорий - линейный список имен с указателями на блоки данных. Такая реализация просто программируется, однако требует большого времени выполнения.

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

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

Методы размещения файлов

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

• Смежное размещение

• Ссылочное размещение

• Индексированное размещение.

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

Недостатки данного метода следующие:

• возможны потери дисковой памяти из-за фрагментации (метод аналогичен общей задаче динамического распределения памяти, рассмотренной ранее);

• невозможность увеличения размера файла.

Смежное размещение файлов иллюстрируется на рис. 20.2.

Рис. 20.2.  Смежное размещение файлов.

Файловые системы, основанные на расширениях

Многие современные файловые системы, - например, Veritas File System, или Vx-FS – основная файловая система в ОС HP-UX фирмы Hewlett-Packard, - используют модифицированное смежное размещение файлов. Дисковые блоки в такой системе размещаются в расширениях (extents). Расширение – это смежный блок на диске. Файл состоит из одного или нескольких расширений. Таким образом, если длина файла не увеличивается, он хранится в виде одной смежной области внешней памяти, что обеспечивает максимальную эффективность доступа. В случае увеличения длины файл представляется списком из основной части и расширений.

Ссылочное размещение файла

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

• Простота – необходимо хранить только начальный адрес;

• Отсутствие потерь дискового пространства; система хранит списки свободной памяти.

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

При ссылочном размещении адрес по файлу представляется в виде (Q, R), где Q – номер блока, к которому выполняется доступ, в связанном списке блоков, представляющем файл; R - смещение в блоке.

Ссылочное размещение файлов изображено на рис. 20.3.

Рис. 20.3.  Ссылочное размещение файлов.

К файловым системам, использующим ссылочное размещение, относится файловая система File-allocation table (FAT), используемая в MS-DOS и OS/2 и до сих пор используемая в Windows (рис. 20.4).

Рис. 20.4.  Файловая система File Allocation Table (FAT).

В системе FAT элемент директории содержит имя файла и адрес его начального блока (кластера) на диске. Каждый блок ссылается на следующий, кроме последнего. Система FAT разработана создателем корпорации Microsoft Биллом Гейтсом в 1976 г. Теперь читателю должно быть понятно, почему операция удаления файла в Windows не "фатальна": она означает лишь удаление элемента директории со ссылкой на начальный кластер файла. Несмотря на это, список кластеров, представляющий файл, можно обнаружить и восстановить ссылку из директории на его начало, хотя и под другим именем. В MS DOS данную функцию выполняла системная утилита unerase (отменить удаление).

Индексируемое размещение

При индексируемом размещении, в отличие от предыдущих, все указатели на блоки файла собраны вместе в индексный блок (i-node, superblock). Используется индексная таблица, ссылающаяся на блоки данных файла. Подобная система используется в системах UNIX, Linux, Solaris.

Пример индексируемого размещения приведен на рис. 20.5.

Рис. 20.5.  Индексируемое размещение файлов.

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

Определенная опасность такого размещения в том, что на индексный блок ложится критическая нагрузка: если его целостность будет нарушена, файл восстановлению не подлежит. Именно поэтому в UNIX команда rm, удаляющая файл, "фатальна" для него.

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

При отображении логического адреса в физический, если ограничить максимальный размер файла 256 K словами, а размер блока - 512 слов, то для индексной таблицы требуется только один блок. Логический адрес будет иметь вид (Q, R), где Q - смещение в индексной таблице, R - смещение в блоке.

При отображении логического адреса в физический для файла неограниченной длины (при размере блока – 512 слов) может использоваться ссылочная схема – в список связываются блоки индексной таблицы. В данном случае логический адрес будет иметь вид (Q1, R1), где Q1 = номер блока индексной таблицы; R1 = (Q2, R2), где Q2 - смещение в блоке индексной таблицы, R2 смещение в блоке файла.

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

Рис. 20.6.  Комбинированная индексная схема размещения файлов в UNIX.

Управление свободной внешней памятью

Для управления свободной памятью на диске система использует битовый вектор длины n, где n – общее число блоков на диске, каждый бит которого описывает состояние соответствующего блока: bit[i] = 0, если block[i] свободен, 1 – если блок занят. При таком представлении информации о свободных и занятых блоках, номер первого занятого блока вычисляется по простой формуле:

номер первого занятого блока = число битов в слове * число нулевых слов + номер первой 1 .

Битовые шкалы, используемые для управления блоками, требуют дополнительной памяти. Например, при размере блока в 2¹² байтов и размере диска в 2³⁰ байтов (1 GB) длина битового вектора будет равна n = 2³⁰/2¹² = 2¹⁸ битов (или 32 KB).

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

Для предотвращения ситуаций рассогласованности информации о свободной дисковой памяти, операционной системе необходимо защищать указатель на список свободной памяти, либо битовую шкалу (в зависимости от способа представления информации о свободной памяти). Битовый вектор должен храниться на диске. Однако его копии в памяти и на диске могут различаться. Нельзя допустить, чтобы block[i] имел такую ситуацию, когда bit[i] = 1 в памяти и bit[i] = 0 на диске. Решение этой проблемы в том, чтоты согласовывать значения битов на диске и в памяти по следующему алгоритму:

• Установить bit[i] = 1 на диске;

• Разместить block[i];

• Установить bit[i] = 1 в памяти.

Представление информации о свободной дисковой памяти в виде списка блоков иллюстрируется на рис. 20.7.

Рис. 20.7.  Список свободной дисковой памяти.

Эффективность и производительность дисковой памяти

Эффективность использования дисковой памяти зависит от:

• Алгоритмов распределения дисковой памяти и управления директориями;

• Типов данных, хранимых в элементе директории для файла.

Для повышения производительности работы с диском используются следующие методы:

• Кэширование диска – использование специальной области основной памяти для часто используемых блоков диска;

• Освобождение прочитанного (free-behind) и опережающее считывание (read-ahead) – методы оптимизации последовательного доступа к диску, которые заключаются в том, что основная память, в которой хранились копии прочитанных блоков, освобождается, а вместе с очередным блоком файла считываются в основную память и несколько следующих блоков;

• Организация виртуальных дисков - улучшение производительности ПК путем выделения области памяти под виртуальный диск (RAM-диск).

Кэширование диска

Буферная кэш-память. В операционных системах используются различные методы кэширования диска (рис. 20.8).

Рис. 20.8.  Различные методы размещения кэша для диска.

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

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

Рис. 20.9.  Ввод-вывод без унифицированной буферной кэш-памяти.

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

Рис. 20.10.  Ввод-вывод с использованием унифицированной буферной кэш-памяти.

Проблемы восстановления файлов

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

Еще раз повторим, что наилучший способ сохранить свои файлы – это регулярно использовать системные программы для резервного копирования (back up) данных с диска на другое устройство памяти (стример, флэшку, внешний жесткий диск, и т.д.). Восстановить испорченный файл на диске можно с помощью его резервной копии. Автор сам на себе недавно испытал ситуацию, когда по непонятной причине (видимо, из-за сбоя диска, которые случаются крайне редко) оказался испорченным файл с главой книги "Trustworthy Compilers", подготовленной для издательства John Wiley & Sons, причем копия файла на флэшке также оказалась испорченной. Проблему решила заранее предусмотрительно сделанная копия файла на вторую флэшку.

Более систематический подход к поддержанию целостности и отслеживанию состояний файлов предпринят в файловых системах с журналом транзакций (log structured filesystems). Файловые системы с журналом фиксируют любое изменение в файловой системе как транзакцию (по аналогии с системами управления базами данных и современными web-сервисами). Все транзакции записываются в журнал. Транзакция считается одобренной (committed), если она записана в журнал. Однако файловая система может быть в этот момент еще не обновлена. Транзакции из журнала асинхронно выполняются над файловой системой. Когда файловая система модифицируется, транзакция удаляется из журнала. Если имеет место сбой файловой системы, то все оставшиеся транзакции из журнала, тем не менее, должны быть выполнены.

Сетевая файловая система NFS

Система NFS (Network File System) -одна из наиболее распространенных сетевых файловых систем, разработанная фирмой Sun Microsystems и используемая в системе Solaris.

NFS – это спецификация и реализация программной системы для доступа к удаленным файлам через локальную (или глобальную) сеть.

Данная реализация является частью операционных систем Solaris и SunOS, использующих быстрый, но менее надежный асинхронный сетевой протокол, основанный на датаграммах (UDP/IP), и сеть Ethernet (сетевые протоколы подробно рассматриваются далее в соответствующих лекциях курса).

В реализации NFS используются процессы-демоны nfsd (обработка NFS-запросов клиентов) и mountd (обработка запросов монтирования), а также biod (асинхронный ввод-вывод блоков удаленных файлов на клиенте).

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

Удаленная директория монтируется на локальную директорию. Смонтированная директория трактуется как полное поддерево локальной файловой системы, заменяя поддерево локальной файловой системы.

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

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

NFS спроектирована для работы в неоднородном окружении различных машин, ОС и сетевых архитектур; спецификация NFS от них не зависит.

Эта независимость достигнута благодаря использованию примитивов RPC (Remote Procedure Call – удаленный вызов процедуры), реализованных поверх External Data Representation (XDR) – протокола – машинно-независимого представления данных для их передачи через сеть.

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

Протокол монтирования в NFS устанавливает первоначальную логическую связь между сервером и клиентом.

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

Запрос на монтирование отображается на соответствующий RPC и передается на mount-сервер, исполняемый на серверной машине.

Список экспорта (export list) указывает список файловых систем, которые сервер экспортирует для монтирования, а также имена машин, на которых разрешено их монтировать.

Исполняя запрос на монтирование, соответствующий этому списку, сервер возвращает обработчик файла (file handle)—ключ к дальнейшему доступу. File handle содержит идентификатор файловой системы и номер inode (индексного узла), идентифицирующий монтируемую директорию внутри экспортируемой файловой системы.

Операция монтирования изменяет только точку зрения клиента и не влияет на серверную часть.

Монтирование в NFS иллюстрируется рис. 20.11 и рис. 20.12: на рис. 20.11 изображены три независимых файловых системы, а на рис. 20.12 – результат монтирования в NFS одной из них (директория dir1 смонтировалась как поддиректория удаленной файловой системы /usr/local.

Рис. 20.11.  Три независимых файловых системы.

Рис. 20.12.  Монтирование в NFS.

Протокол NFS предоставляет набор RPC для удаленных операций над файлами. Процедуры поддерживают следующие операции:

• Поиск файла в директории

• Чтение набора элементов директории

• Управление ссылками и директориями

• Доступ к атрибутам файлов

• Чтение и запись файлов

NFS – серверы не имеют состояния (stateless); каждый запрос должен иметь полный набор аргументов.

Модифицированные данные должны быть направлены на диск сервера до того, как результаты вернутся к клиенту (теряется возможность кэширования).

NFS – протокол не поддерживает механизмы управления параллельным доступом.

Система NFS имеет три основных уровня архитектуры:

• UNIX – интерфейс файловой системы (основан на вызовах open, read, write и close calls и на дескрипторах файлов).

• Уровень Virtual File System (VFS) – различает локальные и удаленные файлы, и в дальнейшем локальные файлы обрабатываются в соответствии с типами их файловых систем. VFS активизирует операции, специфичные для конкретной файловой системы, для обработки локальных запросов в соответствии с типами файловых систем. Уровень VFS вызывает процедуры NFS – протокола для удаленных запросов.

• NFS – сервисный уровень – нижний уровень архитектуры; реализует NFS – протокол.

Схема архитектуры NFS приведена на рис. 20.13.

Рис. 20.13.  Схема архитектуры NFS.

Трансляция имен путей в NFS выполняется путем разбивки имени пути на последовательность имен компонент и выполнения отдельного NFS - поиска для каждой пары (компонента, vnode директории).

Для ускорения поиска на клиентской машине организуется кэш имен удаленных директорий.

Удаленные операции NFS обеспечивают почти взаимно-однозначное соответствие между обычными системными вызовами UNIX и удаленными вызовами процедур протокола NFS (за исключением открытия и закрытия файлов).

NFS основана на парадигме удаленных сервисов, но поддерживает буферизацию и кэширование для повышения эффективности.

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

Клиенты не освобождают задерживаемые блоки до тех пор, пока сервер не подтвердит, что они записаны на диск.

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