Реферат: Физическая организация файловой системы
СОДЕРЖАНИЕ
1.ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ ФАЙЛОВОЙ СИСТЕМЫ
2.ДИСКИ, РАЗДЕЛЫ, СЕКТОРЫ, КЛАСТЕРЫ
3.ФЛЭШ-ПАМЯТЬ
4.Использованная Литература
1. ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ ФАЙЛОВОЙ СИСТЕМЫ
Представлениепользователя о файловой системе как об иерархически организованном множествеинформационных объектов имеет мало общего с порядком хранения файлов на диске.Файл, имеющий образ цельного, непрерывающегося набора байт, на самом деле оченьчасто разбросан «кусочками» по всему диску, причем это разбиение никак несвязано с логической структурой файла, например, его отдельная логическаязапись может быть расположена в несмежных секторах диска. Логическиобъединенные файлы из одного каталога совсем не обязаны соседствовать на диске.Принципы размещения файлов, каталогов и системной информации на реальномустройстве описываются физической организацией файловой системы. Очевидно, чторазные файловые системы имеют разную физическую организацию.
2. ДИСКИ, РАЗДЕЛЫ, СЕКТОРЫ, КЛАСТЕРЫ
Основным типомустройства, которое используется в современных вычислительных системах дляхранения файлов, являются дисковые накопители. Эти устройства предназначены длясчитывания и записи данных на жесткие и гибкие магнитные диски. Жесткий дисксостоит из одной или нескольких стеклянных или металлических пластин, каждая изкоторых покрыта с одной или двух сторон магнитным материалом. Таким образом,диск в общем случае состоит из пакета пластин (рис. 1).
На каждой стороне каждойпластины размечены тонкие концентрические кольца — дорожки (traks), на которых хранятся данные.Количество дорожек зависит от типа диска. Нумерация дорожек начинается с 0 отвнешнего края к центру диска. Когда диск вращается, элемент, называемыйголовкой, считывает двоичные данные с магнитной дорожки или записывает их намагнитную дорожку.
/>
Рис. 1. Схема устройстважесткого диска
Головка можетпозиционироваться над заданной дорожкой. Головки перемещаются над поверхностьюдиска дискретными шагами, каждый шаг соответствует сдвигу на одну дорожку.Запись на диск осуществляется благодаря способности головки изменять магнитныесвойства дорожки. В некоторых дисках вдоль каждой поверхности перемещается однаголовка, а в других — имеется по головке на каждую дорожку. В первом случае дляпоиска информации головка должна перемещаться по радиусу диска. Обычно всеголовки закреплены на едином перемещающем механизме и двигаются синхронно.Поэтому, когда головка фиксируется на заданной дорожке одной поверхности, все остальныеголовки останавливаются над дорожками с такими же номерами. В тех же случаях,когда на каждой дорожке имеется отдельная головка, никакого перемещения головокс одной дорожки на другую не требуется, за счет этого экономится время,затрачиваемое на поиск данных.
Совокупность дорожекодного радиуса на всех поверхностях всех пластин пакета называется цилиндром (cylinder). Каждая дорожка разбивается нафрагменты, называемые секторами (sectors),или блоками (blocks), так что все дорожки имеют равноечисло секторов, в которые можно максимально записать одно и то же число байт.Сектор имеет фиксированный для конкретной системы размер, выражающийся степеньюдвойки. Чаще всего размер сектора составляет 512 байт. Учитывая, что дорожкиразного радиуса имеют одинаковое число секторов, плотность записи становитсятем выше, чем ближе дорожка к центру. Сектор — наименьшая адресуемая единицаобмена данными дискового устройства с оперативной памятью. Для того чтобыконтроллер мог найти на диске нужный сектор, необходимо задать ему всесоставляющие адреса сектора: номер цилиндра, номер поверхности и номер сектора.Так как прикладной программе в общем случае нужен не сектор, а некотороеколичество байт, не обязательно кратное размеру сектора, то типичный запросвключает чтение нескольких секторов, содержащих требуемую информацию, и одногоили двух секторов, содержащих наряду с требуемыми избыточные данные (рис. 2).
/>
Рис. 2. Считываниеизбыточных данных при обмене с диском
Операционная система приработе с диском использует, как правило, собственную единицу дисковогопространства, называемую кластером (cluster). При создании файла место на диске ему выделяетсякластерами. Например, если файл имеет размер 2560 байт, а размер кластера вфайловой системе определен в 1024 байта, то файлу будет выделено на диске 3кластера.
Дорожки и секторысоздаются в результате выполнения процедуры физического, или низкоуровневого,форматирования диска, предшествующей использованию диска. Для определенияграниц блоков на диск записывается идентификационная информация. Низкоуровневыйформат диска не зависит от типа операционной системы, которая этот диск будетиспользовать.
Разметку диска подконкретный тип файловой системы выполняют процедуры высокоуровневого, илилогического, форматирования. При высокоуровневом форматировании определяетсяразмер кластера и на диск записывается информация, необходимая для работыфайловой системы, в том числе информация о доступном и неиспользуемомпространстве, о границах областей, отведенных под файлы и каталоги, информацияо поврежденных областях. Кроме того, на диск записывается загрузчикоперационной системы — небольшая программа, которая начинает процессинициализации операционной системы после включения питания или рестартакомпьютера.
Прежде чем форматироватьдиск под определенную файловую систему, он может быть разбит на разделы. Раздел— это непрерывная часть физического диска, которую операционная системапредставляет пользователю как логическое устройство (используются такженазвания логический диск и логический раздел). Логическое устройствофункционирует так, как если бы это был отдельный физический диск. Именно слогическими устройствами работает пользователь, обращаясь к ним по символьнымименам, используя, например, обозначения А, В, С, SYS и т. п. Операционные системы разного типа используютединое для всех них представление о разделах, но создают на его основелогические устройства, специфические для каждого типа ОС. Так же как файловаясистема, с которой работает одна ОС, в общем случае не может интерпретироватьсяОС другого типа, логические устройства не могут быть использованы операционнымисистемами разного типа. На каждом логическом устройстве может создаватьсятолько одна файловая система.
В частном случае, когдавсе дисковое пространство охватывается одним разделом, логическое устройствопредставляет физическое устройство в целом. Если диск разбит на несколькоразделов, то для каждого из этих разделов может быть создано отдельноелогическое устройство. Логическое устройство может быть создано и на базенескольких разделов, причем эти разделы не обязательно должны принадлежатьодному физическому устройству. Объединение нескольких разделов в единоелогическое устройство может выполняться разными способами и преследовать разныецели, основные из которых: увеличение общего объема логического раздела,повышение производительности и отказоустойчивости. Примерами организациисовместной работы нескольких дисковых разделов являются так называемые RAID-массивы, подробнее о которых будетсказано далее. На разных логических устройствах одного и того же физическогодиска могут располагаться файловые системы разного типа. На рис. 3 показанпример диска, разбитого на три раздела, в которых установлены две файловыхсистемы NTFS (разделы С и Е) и одна файловаясистема FAT (раздел D).
Все разделы одного дискаимеют одинаковый размер блока, определенный для данного диска в результатенизкоуровневого форматирования. Однако в результате высокоуровневогоформатирования в разных разделах одного и того же диска, представленных разнымилогическими устройствами, могут быть установлены файловые системы, в которыхопределены кластеры отличающихся размеров.
Операционная системаможет поддерживать разные статусы разделов, особым образом отмечая разделы,которые могут быть использованы для загрузки модулей операционной системы, иразделы, в которых можно устанавливать только приложения и хранить файлыданных. Один из разделов диска помечается как загружаемый (или активный) Именноиз этого раздела считывается загрузчик операционной системы.
/>
Рис. 3. Разбиение дискана разделы
Важным компонентомфизической организации файловой системы является физическая организация файла,то есть способ размещения файла на диске. Основными критериями эффективностифизической организации файлов являются:
скорость доступа кданным;
объем адресной информациифайла;
степеньфрагментированности дискового пространства;
максимально возможныйразмер файла.
Непрерывное размещение —простейший вариант физической организации (рис. 4, а), при котором файлупредоставляется последовательность кластеров диска, образующих непрерывныйучасток дисковой памяти. Основным достоинством этого метода является высокаяскорость доступа, так как затраты на поиск и считывание кластеров файламинимальны. Также минимален объем адресной информации — достаточно хранитьтолько номер первого кластера и объем файла Данная физическая организация максимальновозможный размер файла не ограничивает. Однако этот вариант имеет существенныенедостатки, которые затрудняют его применимость на практике, несмотря на всюего логическую простоту. При более пристальном рассмотрении оказывается, чтореализовать эту схему не так уж просто Действительно, какого размера должнабыть непрерывная область, выделяемая файлу, если файл при каждой модификацииможет увеличить свой размер? Еще более серьезной проблемой являетсяфрагментация. Спустя некоторое время после создания файловой системы врезультате выполнения многочисленных операций создания и удаления файловпространство диска неминуемо превращается в «лоскутное одеяло», включающеебольшое число свободных областей небольшого размера. Как всегда бывает прифрагментации, суммарный объем свободной памяти может быть очень большим, авыбрать место для размещения файла целиком невозможно. Поэтому на практикеиспользуются методы, в которых файл размещается в нескольких, в общем случаенесмежных областях диска.
/>
Рис. 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.
Для того чтобы корректнопринимать решение о выделении файлу набора кластеров, файловая система должнаотслеживать информацию о состоянии всех кластеров диска: свободен/занят. Этаинформация может храниться как отдельно от адресной информации файлов, так ивместе с ней.
3. ФЛЭШ-ПАМЯТЬ
Как показывают первыерезультаты тестирования SSD-дисков различных производителей, преимуществоSSD-дисков над традиционными HDD-дисками отнюдь не очевидно, особенно если речьидет об операции выборочной (случайной) записи. Кроме того, до сих пор одним изнаиболее слабых мест SSD-дисков является количество циклов перезаписи памяти.
Проблема заключается втом, что флэш-память типа NAND может выдержать порядка 100 тыс. цикловперезаписи информации. Для того чтобы оценить время жизни (время наработки наотказ) флэш-памяти, в которой не используются специальные технологии егопродления, рассмотрим простейший случай, когда каждый логический секторфлэш-памяти жестко связан с физическим сектором. Напомним, что логическийсектор — это минимальный объем памяти, доступный операционной системе. Для всехоперационных систем логический сектор флэш-памяти составляет 512 байт. Подфизическим сектором флэш-памяти понимают наименьший размер доступной для записифизической памяти. В случае если необходимо обновить содержимое логическогосектора, первоначально нужно стереть информацию соответствующего физическогосектора. Кроме того, во флэш-памяти различают еще и минимальный физический блокстираемой памяти (PhysicalErase Unit), то есть блок памяти, который может быть стерт заодну операцию. Один PhysicalErase Unit может содержать несколько физических секторов памяти.
Теперь рассмотрим случай,когда в ОС используется файловая система FAT. В этом случае при операцияхзаписи на флэш-память FAT-таблицы будут постоянно модифицироваться. Проблема втом, что FAT-таблицы располагаются в строго определенном месте, то есть всегдасоотносятся с одними и теми же логическими секторами памяти, а следовательно, содними и теми же физическими секторами. Но часто повторяющиеся операцииперезаписи одних и тех же физических секторов флэш-памяти приводят к тому, чтовремя жизни всей памяти существенно сокращается.
ИСПОЛЬЗОВАННАЯ ЛИТЕРАТУРА
1. Операционные системы Попов, Партыка