Физическая организация файловой системы (стр. 2 из 2)
Рис. 4. Физическая организация файла: непрерывное размещение (а); связанный список кластеров (б); связанный список индексов (в); перечень номеров кластеров (г)
Следующий способ физической организации — размещение файла в виде связанного списка кластеров дисковой памяти (рис. 7.11, б). При таком способе в начале каждого кластера содержится указатель на следующий кластер. В этом случае адресная информация минимальна: расположение файла может быть задано одним числом — номером первого кластера. В отличие от предыдущего способа каждый кластер может быть присоединен к цепочке кластеров какого-либо файла, следовательно, фрагментация на уровне кластеров отсутствует. Файл может изменять свой размер во время своего существования, наращивая число кластеров. Недостатком является сложность реализации доступа к произвольно заданному месту файла — чтобы прочитать пятый по порядку кластер файла, необходимо последовательно прочитать четыре первых кластера, прослеживая цепочку номеров кластеров. Кроме того, при этом способе количество данных файла, содержащихся в одном кластере, не равно степени двойки (одно слово израсходовано на номер следующего кластера), а многие программы читают данные кластерами, размер которых равен степени двойки.
Популярным способом, применяемым, например, в файловой системе FAT, является использование связанного списка индексов (рис. 4, б). Этот способ является некоторой модификацией предыдущего. Файлу также выделяется память в виде связанного списка кластеров. Номер первого кластера запоминается в записи каталога, где хранятся характеристики этого файла. Остальная адресная информация отделена от кластеров файла. С каждым кластером диска связывается некоторый элемент — индекс. Индексы располагаются в отдельной области диска — в MS-DOS это таблица FAT (File Allocation Table), занимающая один кластер. Когда память свободна, все индексы имеют нулевое значение. Если некоторый кластер N назначен некоторому файлу, то индекс этого кластера становится равным либо номеру М следующего кластера данного файла, либо принимает специальное значение, являющееся признаком того, что этот кластер является для файла последним. Индекс же предыдущего кластера файла принимает значение N, указывая на вновь назначенный кластер.
При такой физической организации сохраняются все достоинства предыдущего способа: минимальность адресной информации, отсутствие фрагментации, отсутствие проблем при изменении размера. Кроме того, данный способ обладает дополнительными преимуществами. Во-первых, для доступа к произвольному кластеру файла не требуется последовательно считывать его кластеры, достаточно прочитать только секторы диска, содержащие таблицу индексов, отсчитать нужное количество кластеров файла по цепочке и определить номер нужного кластера. Во-вторых, данные файла заполняют кластер целиком, а значит, имеют объем, равный степени двойки.
ПРИМЕЧАНИЕ
Необходимо отметить, что при отсутствии фрагментации на уровне кластеров на диске все равно имеется определенное количество областей памяти небольшого размера, которые невозможно использовать, то есть фрагментация все же существует. Эти фрагменты представляют собой неиспользуемые части последних кластеров, назначенных файлам, поскольку объем файла в общем случае не кратен размеру кластера. На каждом файле в среднем теряется половина кластера. Это потери особенно велики, когда на диске имеется большое количество маленьких файлов, а кластер имеет большой размер. Размеры кластеров зависят от размера раздела и типа файловой системы Примерный диапазон, в котором может меняться размер кластера, составляет от 512 байт до десятков килобайт.
Еще один способ задания физического расположения файла заключается в простом перечислении номеров кластеров, занимаемых этим файлом (рис. 4, г). Этот перечень и служит адресом файла. Недостаток данного способа очевиден: длина адреса зависит от размера файла и для большого файла может составить значительную величину. Достоинством же является высокая скорость доступа к произвольному кластеру файла, так как здесь применяется прямая адресация, которая исключает просмотр цепочки указателей при поиске адреса произвольного кластера файла. Фрагментация на уровне кластеров в этом способе также отсутствует.
Последний подход с некоторыми модификациями используется в традиционных файловых системах ОС UNIX s5 и ufs. Для сокращения объема адресной информации прямой способ адресации сочетается с косвенным.
В стандартной на сегодняшний день для UNIX файловой системе ufs используется следующая схема адресации кластеров файла. Для хранения адреса файла выделено 15 полей, каждое из которых состоит из 4 байт (рис. 5). Если размер файла меньше или равен 12 кластерам, то номера этих кластеров непосредственно перечисляются в первых двенадцати полях адреса. Если кластер имеет размер 8 Кбайт (максимальный размер кластера, поддерживаемого в ufs), то таким образом можно адресовать файл размером до 8192x12 = 98 304 байт.
Рис. 5. Схема адресации файловой системы ufs
Если размер файла превышает 12 кластеров, то следующее 13-е поле содержит адрес кластера, в котором могут быть расположены номера следующих кластеров файла. Таким образом, 13-й элемент адреса используется для косвенной адресации. При размере в 8 Кбайт кластер, на который указывает 13-й элемент, может содержать 2048 номеров следующих кластеров данных файла и размер файла может возрасти до 8192*(12+2048)=16 875 520 байт.
Если размер файла превышает 12+2048 = 2060 кластеров, то используется 14-е поле, в котором находится номер кластера, содержащего 2048 номеров кластеров, каждый из которых хранят 2048 номеров кластеров данных файла. Здесь применяется уже двойная косвенная адресация. С ее помощью можно адресовать кластеры в файлах, содержащих до 8192*(12+2048+20482) - 3,43766*1O10 байт.
И наконец, если файл включает более 12+2048+20482 = 4 196 364 кластеров, то используется последнее 15-е поле для тройной косвенной адресации, что позволяет задать адрес файла, имеющего следующий максимальный размер:
8192*(12+2048+20482+20483)=7,0403*1013байт.
Таким образом, файловая система ufs при размере кластера в 8 Кбайт поддерживает файлы, состоящие максимум из 70 триллионов байт данных, хранящихся в 8 миллиардах кластеров. Как видно на рис 7.12, для задания адресной информации о максимально большом файле требуется: 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.
Для того чтобы корректно принимать решение о выделении файлу набора кластеров, файловая система должна отслеживать информацию о состоянии всех кластеров диска: свободен/занят. Эта информация может храниться как отдельно от адресной информации файлов, так и вместе с ней.
Как показывают первые результаты тестирования SSD-дисков различных производителей, преимущество SSD-дисков над традиционными HDD-дисками отнюдь не очевидно, особенно если речь идет об операции выборочной (случайной) записи. Кроме того, до сих пор одним из наиболее слабых мест SSD-дисков является количество циклов перезаписи памяти.
Проблема заключается в том, что флэш-память типа NAND может выдержать порядка 100 тыс. циклов перезаписи информации. Для того чтобы оценить время жизни (время наработки на отказ) флэш-памяти, в которой не используются специальные технологии его продления, рассмотрим простейший случай, когда каждый логический сектор флэш-памяти жестко связан с физическим сектором. Напомним, что логический сектор — это минимальный объем памяти, доступный операционной системе. Для всех операционных систем логический сектор флэш-памяти составляет 512 байт. Под физическим сектором флэш-памяти понимают наименьший размер доступной для записи физической памяти. В случае если необходимо обновить содержимое логического сектора, первоначально нужно стереть информацию соответствующего физического сектора. Кроме того, во флэш-памяти различают еще и минимальный физический блок стираемой памяти (Physical Erase Unit), то есть блок памяти, который может быть стерт за одну операцию. Один Physical Erase Unit может содержать несколько физических секторов памяти.
Теперь рассмотрим случай, когда в ОС используется файловая система FAT. В этом случае при операциях записи на флэш-память FAT-таблицы будут постоянно модифицироваться. Проблема в том, что FAT-таблицы располагаются в строго определенном месте, то есть всегда соотносятся с одними и теми же логическими секторами памяти, а следовательно, с одними и теми же физическими секторами. Но часто повторяющиеся операции перезаписи одних и тех же физических секторов флэш-памяти приводят к тому, что время жизни всей памяти существенно сокращается.
1. Операционные системы Попов, Партыка