Лабораторная работа №4 «Моделирование файловых систем»

Цель работы

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

Теоретические сведения

Дополнительную информацию по данному вопросу можно найти в разделе «4.5. Файловая система» настоящего учебного пособия.

Файлы и каталоги

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

Каталог – это, файл специального вида, содержащий системную информацию о группе файлов, его составляющих.

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

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

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

- символьный;

- базовый;

- проверки прав доступа;

- логический;

- физический.

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

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

Непрерывное размещение – простейший вариант физической организации (рис. 4.13.а), при котором файлу предоставляется последовательность блоков диска, образующих единый сплошной участок дисковой памяти. Для задания адреса файла в этом случае достаточно указать только номер начального блока. Такая организация имеет два существенных недостатка:

- во время создания файла заранее не известна его длина, а значит не известно, сколько памяти надо зарезервировать для этого файла;

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

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

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

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

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

FAT применяется для дисков малой емкости. К основным недостаткам FAT могут быть отнесены следующие:

- ограничения, налагаемые на размер файлов и дискового пространства;

- ограничение длины имени файла;

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

- непроизводительные затраты памяти, вызванные большими размерами кластеров;

- подверженность потерям данных.

После форматирования диска в FAT на него наносится следующая служебная информация:

- ЗАПИСЬ СТАРТА СИСТЕМЫ (начиная с первого сектора нулевого цилиндра, состоит из таблицы, содержащей информацию о диске; машинного кода, загружающего файлы IO.SYS и MSDOS.SYS

- ТАБЛИЦА РАЗМЕЩЕНИЯ ФАЙЛОВ И КОРНЕВОЙ КАТАЛОГ.

Корневой каталог – это таблица-описание содержимого диска. Каждому файлу в таблице соответствует одна запись. Запись занимает 32 байта, разбитых на 8 полей (см. рис. 4.11.а).

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

Для чтения файла с логического диска необходимо произвести следующие действия:

1. чтение дескриптора файла и определение номера первого кластера;

2. чтение кластера;

3. использование номера прочитанного кластера в качестве индекса в FAT для извлечения номера следующего кластера;

4. чтение кластера;

5. повторение действий, начиная с п.3 до тех пор, пока извлеченное из FAT значение не будет соответствовать концу файла.

В зависимости от размера ячейки в FAT различают FAT12, FAT16 и FAT32, что определяет максимальный размер логического диска отформатированного в данной файловой системе.

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

Новая файловая система NTFS обладает лучшими показателями производительности и надежности по сравнению с FAT.

Эта файловая система поддерживает объектно-ориентированные приложения, обрабатывая все файлы как объекты, которые имеют определяемые пользователем и системой атрибуты. NTFS позволяет задавать права доступа к отдельному файлу.

Каждый файл на томе NTFS представлен записью в специальном файле, называемом Главной таблицей файлов (Master File Table, MFT).

В отличие от разделов FAT все пространство тома NTFS представляет собой либо файл, либо часть файла. Основой структуры тома NTFS является Главная таблица файлов (Master File Table, MFT), которая содержит по крайней мере одну запись для каждого файла тома, включая одну запись для самой себя. Каждая запись имеет длину 2К.

Все файлы на томе NTFS идентифицируются номером файла, который определяется позицией файла в MFT. Каждый файл и каталог на томе NTFS состоит из набора атрибутов.

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

Загрузочный сектор тома NTFS располагается в начале тома, а его копия – в середине тома. Загрузочный сектор состоит из стандартного блока параметров BIOS, количества секторов в томе, а также начального логического номера кластера основной копии MFT и зеркальной копии MFT.

Файлы NTFS делятся на (см. рис. 5.4 – 5.7):

- небольшие файлы (Small);

- большие файлы (Large);

- очень большие файлы (Huge);

- сверхбольшие файлы (Extremely huge),

что определяет их способ хранения на томе NTFS.

Аналогичным образом, имеется две формы списка файлов (см. рис. 5.8 и 5.9):

- небольшие списки файлов (Small indexes).

- большие списки файлов (Large indexes).

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

Как и во многих файловых системах в Ext2 существует загрузочная область. На первичном разделе (primary, в терминологии программы Fdisk фирмы Microsoft) она содержит загрузочную запись – фрагмент кода, который инициирует процесс загрузки операционной системы при запуске. Все остальное пространство раздела делится на блоки стандартного размера. Блок может иметь размер 1, 2 или 4 Кбайт. Блок является минимальной логической единицей дискового пространства (в других операционных системах такой блок называют кластером). Выделение места файлам осуществляется целыми блоками.

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

- суперблок (Superblock);

- описание группы блоков (Group Descriptors);

- битовая карта блока (Block Bitmap);

- битовая карта индексного дескриптора (Inode Bitmap);

- таблица индексных дескрипторов (Inode Table);

- блоки данных.

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

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

После суперблока следует являющееся массивом описание группы блоков (Group Descriptors).

Битовая карта блоков (Block Bitmap) – это структура, каждый бит которой показывает, отведен ли соответствующий ему блок какому-либо файлу. Если бит равен 1, то блок занят. Эта карта служит для поиска свободных блоков в тех случаях, когда надо выделить место под файл.

Битовая карта индексных дескрипторов (Inode Bitmap) выполняет аналогичную функцию по отношению к таблице индексных дескрипторов – показывает, какие дескрипторы заняты.

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

Таблица индексных дескрипторов (Inode Table) содержит индексные дескрипторы файлов (i-узлы). Индексные дескрипторы файлов содержат информацию о файлах группы блоков. Каждому файлу на диске соответствует один и только один индексный дескриптор файла, который идентифицируется своим порядковым номером – индексом файла. Отсюда следует, что число файлов, которые могут быть созданы в файловой системе, ограничено числом индексных дескрипторов.В i-узле хранится информация, описывающая файл: режимы доступа к файлу, время создания и последней модификации, идентификатор пользователя и идентификатор группы создателя файла, описание блочной структуры файла и т.д.

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

Система адресации данных позволяет находить нужный файл среди блоков на диске. В Ext2 система адресации реализуется полем i_block индексного дескриптора файла.

Поле i_block в индексном дескрипторе файла представляет собой массив из 15 адресов блоков. Первые 12 адресов в этом массиве представляют собой прямые ссылки на номера блоков, в которых хранятся данные из файла. Следующий адрес в этом массиве является косвенной ссылкой (адресом блока), в котором хранится список адресов следующих блоков с данными из этого файла. Следующий адрес в поле i_block индексного дескриптора указывает на блок двойной косвенной адресации (double indirect block). Этот блок содержит список адресов блоков, которые, в свою очередь, содержат списки адресов следующих блоков данных того файла, который задается индексным дескриптором.

Последний адрес в поле i_block индексного дескриптора задает адрес блока тройной косвенной адресации, то есть блока со списком адресов блоков, которые являются блоками двойной косвенной адресации.

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

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

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

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

К журналируемым файловым системам относятся ReiserFS, XFS, JFS, GFS, ext3.

Задание на лабораторную работу

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

- объем внешней памяти, используемой для хранения файловой системы – не менее 64К;

- размер кластера или блока – 512 байт.

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

- размер таблицы размещения файлов (FAT), размер суперблока, размер таблицы i-узлов и т.п. должен быть обосновано выбран в соответствии с заданными размерами кластера или блока и объемом внешней памяти.

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

Варианты заданий

Литература

1. Кирх О. Linux для профессионалов. Руководство администратора сети. – СПб.: Питер, 2000. – 368 с.

2. Пятибратов А.П., Гудыно Л.П., Кириченко А.А. Вычислительные системы сети и телекоммуникации: Учебник под ред. Пятибратова А.П. – М: Финансы и статистика, 1998. – 400 с.

3. Ресурсы Microsoft Windows NT Server 4.0. Книга 1: пер. с англ. – СПб.: ИРМ – Санкт-Петербург, 1997. – 408 с.

4. Новейшие ресурсы Microsoft Windows NT Server 4.0. Книга 2: пер. с англ. – СПб.: ИРМ – Санкт-Петербург, 1997. – 344 с.

5. Стерн М., Монти Г., Бэчман В. Сети предприятий на базе Winodws NT для профессионалов – СПб.: Питер Ком, 1999. – 448 с.

6. Microsoft Windows 2000 Server. Служба каталогов Active Directory – техническое описание. Microsoft Corporation, 1999. – 35 с.

7. Microsoft Windows 2000 Server. Active Directory: служба каталогов следующего поколения. Microsoft Corporation, 1999. – 26 с.

8. Годреев А.В. Операционные системы: Учебник для вузов. 2-е изд. – СПб.: Питер, 2004. – 416 с.

9. Вахалия Ю. Unix изнутри: Пер. с англ. – СПб.: Питер, 2003. – 844 с.: ил.

10. Таненбаум Э. Современные операционные системы. 2-е изд.: Пер. с англ. – СПб.: Питер, 2004. – 1040 с.: ил.

11. Бэкон Д., Харрис Т. Операционные системы: Параллельные и распределенные системы: Пер. с англ. – СПб.: Питер; Киев: Издательская группа BHV, 2004. – 800 с.: ил.