Способы физического размещения файла

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

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

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

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

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

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