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

Рисунок 4.6 - Схема устройства жесткого диска

Жесткий диск в общем случае состоит из пакета пластин.

На каждой стороне каждой пластины размещены дорожки (tracks), на которых хра­нятся данные. Нумерация дорожек начинается с 0 от внешнего края диска.

Совокупность дорожек одного радиуса на всех поверхностях всех пластин назы­вается цилиндром.

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

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

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

Операционная система использует логическую адресуемую единицу дискового пространства - кластер (claster). При создании файла память на диске ему выделя­ется кластерами.

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

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

Физическая организация и адресация файла

Основные критерии эффективности физической организации файла:

· скорость доступа к данным;

· объем адресной информации файла;

· степень фрагментированности дискового пространства;

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

Варианты физической организации

Основные варианты приведены на рис. 4.7 с кратким описанием и общей оценкой.

Рисунок 4.7- Физическая организация файла

Непрерывное размещение. Схема очевидна из рисунка.

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

Связанный список индексов. Может рассматриваться как усовершенствование преды­дущего варианта. Применяется в файловой системе FAT для ОС семейства Microsoft.

С каждым кластером диска связывается индекс (номер). Индексы располагаются в отдельной таблице - FAT (File Allocation Table), занимающей один кластер. Когда па­мять свободна, все индексы имеют нулевое значение.

Файлу выделяется память в виде связанного списка кластеров. Индекс первого клас­тера файла запоминается в записи каталога, где хранится файл (см. п. 2.1 темы). Если некоторый кластер не последний в файле, то соответствующий ему индекс содержит но­мер следующего кластера, в противном случае - специальный признак конца файла. При присоединении очередного кластера к файлу индекс последнего кластера файла меняет­ся на индекс присоединяемого кластера, а присоединяемый становится последним.

Сохраняются достоинства предыдущего способа плюс преимущества доступа. Но­мер любого кластера файла просто определяется по таблице индексов.

Перечисление номеров кластеров, занимаемых файлом. Этот перечень служит адре­сом файла.

Сравнительная оценка вариантов

Знаками + и - помечены достоинства и недостатки вариантов соответственно.

Модификация последнего способа, используемая в файловых системах s5 и ufs ОС Unix

Для сокращения объема адресной информации прямая адресация сочетается с кос­венной (передачей адреса по адресу). Схема организации файлов приведена на рис. 4.8.

Рисунок 4.8 - Схема адресации файловой системы uf

Для хранения адреса файла выделено 15 полей по 4 байта, отводимых на номер кластера. В первых 12 полях (с 0 по 11-е) размещаются номера первых 12 кластеров файла. 13-е поле содержит номер кластера, где могут быть расположены номера сле­дующих кластеров файла. 14 поле содержит номер кластера, в котором размещены номера кластеров, хранящих номера кластеров уже непосредственно с данными.

Пусть кластер имеет размер 8 Кб (8192 б). Тогда первыми 12 полями можно адре­совать 8192*12=98304 байтов.

Кластер, на который указывает 13-е поле, содержит 8192/4 = 2048 номеров клас­теров следующего уровня, т.е. позволяет адресовать еще 8192*2048 байтов. Анало­гично можно рассчитать объем памяти, адресуемой через посредство двойной и трой­ной косвенной адресации.

В итоге максимальный размер файла составляет 8192*(12+2048+2048²+2048³) байтов. При этом объем адресной информации равен 15 элементов по 4 байта плюс (1+(1 +2048)+(1 +2048+2048²)) = 4 198 403 кластера для косвенной части адреса, что состав­ляет около 0,05 % объема адресуемых данных, т.е. очень небольшой процент.