Лекция 15. Виртуальные файловые системы

Лекция 15. Виртуальные файловые системы

План занятия:

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

 

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

Основные методы размещения файлов в файловых системах – смежное, ссылочное и индексируемое размещение.

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

В файловых системах, основанных на расширениях (extents), файл представляется как смежная область памяти и список расширений – смежных областей памяти.

При ссылочном размещении файл представляется в виде списка дисковых блоков. Например, такой метод применен в системе FAT (File Allocation Table), используемой в MS DOS и в Windows. При таком методе отсутствуют потери дискового пространства, но нет возможности произвольного доступа к файлу.

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

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

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

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

Для сохранения и восстановления файлов рекомендуется использовать резервное копирование.

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

Сетевая файловая система NFS реализована на основе механизмов и протоколов RPC (удаленный вызов процедуры) и XDR (внешнее представление данных для передачи через сеть). Система обеспечивает работу пользователя с удаленными файловыми системами с помощью тех же операций, которые используются и для локальных файловых систем. Удаленные файловые системы монтируются на локальные. При этом указывается имя машины с удаленной директорией. В реализации NFS используются процессы- демоны. NFS -сервисы не имеют состояния (stateless). Архитектура NFS трехуровневая – интерфейс системных вызовов для UNIX; уровень виртуальной файловой системы; нижний уровень реализации NFS -сервисов.

Вопросы для самопроверки:

1. Что такое виртуальная файловая система?

2. Какими способами реализуются директории в файловых системах?

3. Какие основные методы используются для размещения файлов?

4. Каковы особенности, достоинства и недостатки смежного размещения файлов?

5. Каковы особенности, достоинства и недостатки ссылочного размещения файлов?

6. Каковы особенности, достоинства и недостатки индексируемого размещения файлов?

7. Что такое расширения (extents) и как они используются для размещения файлов?

8. Как организованы файловые системы по методу File Allocation Table (FAT)?

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

10. Что такое кэширование диска?

11. Что такое унифицированная буферная кэш-память и для чего она используется?

12. Что такое опережающее считывание?

13. Что такое освобождение прочитанного?

14. Какие методы используются для восстановления файлов?

15. Что такое файловая система с журналом транзакций?

16. Что такое NFS?

17. На каких сетевых протоколах и механизмах основана реализация NFS?

18. Каковы возможности системы NFS для пользователя?

19. Каковы особенности монтирования удаленных файловых систем в NFS?

20. Каковы уровни архитектуры NFS?

Упражнения

1. Реализуйте директорию и операции над ней с использованием хеш-функции.

2. Реализуйте смежное размещение файлов и основные операции над файлами при данном размещении.

3. Реализуйте ссылочное размещение файлов и основные операции над файлами при данном размещении.

4. Реализуйте индексируемое размещение файлов и основные операции над файлами при данном размещении.

5. Реализуйте размещение файлов на основе расширений (extents) и основные операции над файлами при данном размещении.

6. Реализуйте представление информации о свободной дисковой памяти в виде битового вектора и основные операции над ним.

Лекция 15. Виртуальные файловые системы

План занятия:

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

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

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

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

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

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

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

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

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

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

 

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