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

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

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

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

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

 максимально возможный размер файла.

Непрерывное размещение – простейший вариант физической организации (рис. 26, а), при котором файлу предоставляется последовательность кластеров диска, образующих непрерывный участок дисковой памяти. Основным достоин­ством этого метода является высокая скорость доступа, так как затраты на поиск и считывание кластеров файла минимальны. Также минимален объем адресной информации – достаточно хранить только номер первого кластера и объем фай­ла. Данная физическая организация максимально возможный размер файла не ограничивает. Однако этот вариант имеет существенные недостатки, которые за­трудняют его применимость на практике, несмотря на всю его логическую про­стоту. При более пристальном рассмотрении оказывается, что реализовать эту схему не так уж просто. Действительно, какого размера должна быть непрерыв­ная область, выделяемая файлу, если файл при каждой модификации может уве­личить свой размер? Еще более серьезной проблемой является фрагментация. Спустя некоторое время после создания файловой системы в результате выпол­нения многочисленных операций создания и удаления файлов пространство дис­ка неминуемо превращается в “лоскутное одеяло”, включающее большое число свободных областей небольшого размера. Как всегда бывает при фрагментации, суммарный объем свободной памяти может быть очень большим, а выбрать место для размещения файла целиком невозможно. Поэтому на практике используют­ся методы, в которых файл размещается в нескольких, в общем случае несмежных областях диска.

Рис. 26. Физическая организация файла:

а – непрерывное размещение; б – связанный список кластеров;

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

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

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

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

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

Последний подход с некоторыми модификациями используется в традиционных файловых системах ОС UNIX s5 и ufs. Для сокращения объема адресной ин­формации прямой способ адресации сочетается с косвенным.

В стандартной на сегодняшний день для UNIX файловой системе ufs использу­ется следующая схема адресации кластеров файла. Для хранения адреса файла выделено 15 полей, каждое из которых состоит из 4 байт (рис. 27). Если размер файла меньше или равен 12 кластерам, то номера этих кластеров непосредствен­но перечисляются в первых двенадцати полях адреса. Если кластер имеет размер 8 Кбайт (максимальный размер кластера, поддерживаемого в ufs), то таким обра­зом можно адресовать файл размером до 8192·12=98304 байт.

Рис. 27. Схема адресации файловой системы ufs

Если размер файла превышает 12 кластеров, то следующее 13-е поле содержит адрес кластера, в котором могут быть расположены номера следующих класте­ров файла. Таким образом, 13-й элемент адреса используется для косвенной адресации. При размере в 8 Кбайт кластер, на который указывает 13-й элемент, может содержать 2048 номеров следующих кластеров данных файла и размер файла может возрасти до 8192·(12+2048)=16875520 байт.

Если размер файла превышает 12+2048=2060 кластеров, то используется 14-е поле, в котором находится номер кластера, содержащего 2048 номеров кластеров, каж­дый из которых хранит 2048 номеров кластеров данных файла. Здесь применяет­ся уже двойная косвенная адресация. С ее помощью можно адресовать кластеры в файлах, содержащих до 8192·(12+2048+20482)=3,43766·1010байт.

И наконец, если файл включает более 12+2048+20482=4196364 кластеров, то используется последнее 15-е поле для тройной косвенной адресации, что позво­ляет задать адрес файла, имеющего следующий максимальный размер: 8192·(12+2048+20482+20483)=7,0403·l013 бaйт.

Таким образом, файловая система ufs при размере кластера в 8 Кбайт поддержи­вает файлы, состоящие максимум из 70 триллионов байт данных, хранящихся в 8 миллиардах кластеров. Для задания адресной информа­ции о максимально большом файле требуется (см. рис. 27): 15 элементов по 4 байта (60 байт) в центральной части адреса плюс 1+(1+2048)+(1+2048+20482)=4198403 кла­стера в косвенной части адреса. Несмотря на огромную величину, это число со­ставляет всего около 0,05% от объема адресуемых данных.

Файловая система ufs поддерживает дисковые кластеры и меньших размеров, при этом максимальный размер файла будет другим. Используемая в более ранних версиях UNIX файловая система s5 имеет аналогичную схему адресации, но она рассчитана на файлы меньших размеров, поэтому в ней используется 13 адрес­ных элементов вместо 15.

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

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