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

Физическая организация выделяет способ размещения файлов на диске и учет соответствия блоков диска файлам. Основными критериями эффективности физиче­ской организации файлов являются:

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

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

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

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

· непрерывное размещение (непрерывные файлы);

· сводный список блоков (кластеров) файла;

· сводный список индексов блоков (кластеров) файла;

· перечень номеров блоков (кластеров) файла в структурах, называемых i-узлами (index-node - индекс-узел).

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

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

И все-таки есть ситуации, в которых непрерывные файлы могут эффективно использоваться и действительно широко используются - на компакт-дисках. Здесь всеразмеры файлов заранее известны и не могут меняться.

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

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

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

Такая таблица, называемая FAT-таблицей (File Allocation Table), используется в файловых системах MS DOS и Windows (FAT 16 и FAT 32). Файлу выделяется память на диске в виде связного списка кластеров. Номер первого кластера запоминается в за­писи каталога, где хранятся характеристики этого файла. С каждым кластером диска связывается индекс. Индексы располагаются в FAT-таблице в отдельной области диска. Когда память свободна, все индексы равны нулю. Если некоторый кластер N назначен файлу, то индекс этого кластера либо становится равным номеру М следующего класте­ра файла, либо принимает специальное значение, являющееся признаком того, что кластер является последним для файла. Вообще индексы могут содержать следующую информацию о кластере диска (для FAT 32):

• не используется (Unused) - 0000.0000;

используется файлом (Cluster in us by a file) - значение, отличное от 000.000,
FFFF.FFFF и FFFF.FFF7;
плохой кластер (Bad cluster) - FFFF.FFF7;
последний кластер файла (Last cluster in a file) - FFFF.FFFF.

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

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

Еще один метод организации файла состоит в связывании с каждым файлом структуры данных, называемой i-узлами (index node - индекс-узел). Такой узел содержит ат­рибуты файла и адреса кластеров файла (рис. 4.22). Преимущество такой схемы перед FAT-таблицей заключается в том, что каждый конкретный i-узел должен находиться в памяти только тогда, когда открыт соответствующий ему файл. Если каждый узел зани­мает п байт, а одновременно может быть открыто к фалов, то массив i-узлов займет в па­мяти к * п байт, что значительно меньше, чем ЕАТ-таблица.

Это объясняется тем, что размер FAT-таблицы растет линейно с размером диска и даже быстрее, чем линейно, так как с увеличением количества кластеров на диске может потребоваться увеличит разрядность числа для хранения их номеров.

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

Однако с такой схемой связана проблема, заключающаяся в том, что при выделении

каждому файлу фиксированного количества адресов кластеров этого количества может

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

сации.

Метод перечисления адресов кластеров файла задействован и в файловой системе NTFS, используемой в Windows NT/2000/2003. Для сокращения объема адресной ин­формации в NTFS адресуются не кластеры файла, а непрерывные области, состоящие из смежных кластеров диска. Каждая такая область называется экстентом (extent) и описывается двумя числами: номером начального кластера и количеством кластеров.