Организация дискового пространства

Размещение информации (в том числе файлов) на том или ином устройстве характеризует порядок ее хранения на физическом уровне. В качестве примера рассмотрим организацию дискового пространства для наиболее широко используемых носителей - магнитных дисков.

Все пространство диска разбивается на дорожки в виде концентри­ческих окружностей, которые в свою очередь разделяются на секторы (рис. 38). Для их создания используется специальная процедура, которая называется форматированием и выполняется с помощью средств опера­ционной системы (например, в MS DOS это команда FORMAT). Факти­чески при этом осуществляются две различные операции, называемые форматированием низкого и высокого уровней. Низкоуровневое (физиче­ское) форматированиесостоит в нанесении на диск электронных меток для обозначения дорожек и секторов. При форматировании высокого уровня (его называют также логическим) осуществля­ется создание служебных областей на диске.

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

Рис. 38. Разметка магнитных носителей

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

В первом физическом секторе жесткого диска располагается главная загрузочная запись(master boot record, MBR) и таблица разделов диска. MBR при загрузке с жесткого диска считывает и загружает в память первый физический сектор на активном разделе диска, называемый загрузочным сектором (boot sector). Каждая запись в таблице разделов (partition table) содержит начальную позицию и размер каждого раздела на жестком диске, а также информацию о том, первый сектор какого раз­дела содержит загрузочную запись.

Базовой единицей ФС жесткого диска является раздел, создаваемый во время разметки жесткого диска и обслуживаемый какой-либо файловой системой. Некоторые операционные системы поддерживают создание томов, охватывающих несколько разделов.

Жесткий диск может содержать до четырех основных разделов. Это ограничение связано с характером организации данных на жестких дис­ках IBM-совместимых компьютеров. Многие операционные системы позволяют создавать так называемый расширенный (extended) раздел, который по аналогии с основным разделом может разбиваться на не­сколько логических дисков.

При проведении форматирования высокого уровня дискеты или раз­дела диска происходит создание служебных областей в соответствии с типом файловой системы; ниже рассмотрены наиболее распространенные из них.

FA Т. Файловая система FAT (File Allocation Table, таблица размещения файлов) была разработана Биллом Гейтсом и Марком МакДональдом в 1977 г. и первоначально использовалась в операционной системе 86-DOS. В дальнейшем она была приобретена фирмой Microsoft и стала основой для ОС MS-DOS 1.0, выпущенной в августе 1981 г. FAT была предна­значена для работы с гибкими дисками и вначале не предусматривала поддержку жестких дисков. В соответствии со спецификацией FAT16 на диске размещался сначала загрузочный сектор, затем сама таблица раз­мещения файлов, затем ее точная копия, затем корневой каталог; далее располагалась область данных.

FAT не могла контролировать каждый сектор в отдельности, по­этому она объединяла смежные секторы в кластеры (благодаря чему уменьшалось общее количество единиц хранения, за которыми должна следить файловая система). Кластер (cluster) - это группа смежных секторов, имеющая уникальный номер. Каждый кластер считывается и записывается целиком, и поэтому представляет собой минимальное пространство, которое может занимать файл. В результате значительная часть пространства диска расходуется впустую. Например, файл длиной 2 байта будет занимать весь кластер длиной 512 байт, и остальные 510 байт будут недоступны для хранения других данных.

Свое название FAT получила от одноименной таблицы размещения файлов. Каждому кластеру соответствует отдельная записьв FAT, которая показывает, свободен ли он, занят ли данными файла, или помечен как сбойный (испорченный). Номер записи соответствует номеру кластера. Если кластер занят под файл, то в соответствующей записи в таблице размещения файлов указывается номер кластера, содержащего следу­ющую часть файла. Из-за этого FAT называют файловой системой со связанными списками.

Используется следующий алгоритмсчитывания файлов. При получе­нии имени файла для выполнения операции считывания ОС обращается к корневому каталогу и считывает номер начального кластера этого файла. Затем ОС обращается в записьFAT с данным номером и анализирует его содержимое. Если в записи содержится номер следующего кластера, ОС запоминает его, переходит к записи с этим номером для ее обработки. Процесс продолжается до тех пор, пока в очередной записи FAT не встре­тится признак конца файла (EOF, End Of File). Получив таким образом цепочку кластеров, принадлежащих данному файлу, ОС производит не­посредственное чтение информации из кластеров с данными номерами, находящимися в области данных. Таким образом, из содержимого от­дельных кластеров формируется содержимое файла.

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

Для надежности FAT хранится в двух экземплярах, записанных подряд. Предполагается, что эти копии должны быть идентичны. При порче основной файловой таблицы информация о размещении файлов считывается из ее копии. Но при порче копии восстановить цепочки кла­стеров, принадлежащие конкретному фай.'.у, практически невозможно; вся информация на диске становится недоступной.

Оригинальная версия FAT, разработанная для DOS 1.00, использовала 12-битную таблицу размещения файлов и поддерживала разделы объемом до 4 Мб. Для поддержки жестких дисков размером более 32 Мб разряд­ность FAT была увеличена до 16 бит. Так как каждому кластеру должен быть присвоен уникальный 16-разрядный номер, файловая система FAT16 поддерживает максимум 2¹⁶, или 65536 кластеров на одном томе, а максимальная величина раздела составляет 2 Гбайт.

Поскольку загрузочная записьслишком мала для хранения системных файлов, они должны находиться в строго определенном месте диска, чтобы их можно было найти при загрузке. Фиксированное положение системных файлов в начале области данных накладывает жесткое огра­ничение на размеры корневого каталога и таблицы размещения файлов. Вследствие этого общее число файлов и подкаталогов в корневом каталоге файловой системы FAT ограничено 512.

Каждому файлу и подкаталогу в FAT выделяется 32-байтный элемент каталога, содержащий имя файла (каталога), его атрибуты (архивный, скрытый, системный и «только для чтения»), дату и время создания файла (или внесения в него последних изменений), номер начального кластера, в котором он размещен, и размер в байтах.

Файловая система FAT всегда заполняет свободное место на диске последовательно от начала к концу. При создании нового файла или уве­личении уже существующего она ищет самый первый свободный кластер в таблице размещения файлов. В процессе работы одни файлы удаляются, другие изменяются в размере; появляющиеся при этом пустые кластеры оказываются разбросанными по всему диску. Если данныефайлы запи­саны не в смежные кластеры, он называется фрагментированным.

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

Еще один недостаток FAT заключается в том, что ее производитель­ность сильно зависит от количества файлов, хранящихся в одном каталоге.

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

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

Поскольку FAT изначально проектировалась для однопользователь­ской операционной системы DOS, в ней не предусмотрено хранения ин­формации о владельце файла/каталога или полномочиях доступа к ним.

FAT была одной из первых файловых систем для ПК; несмотря на многочисленные недостатки, она получила широкое распространение и поэтому ее поддерживает большинство современных ОС. Хотя нет никаких препятствий для того, чтобы использовать при форматировании дискет любую другую файловую систему, большинство ОС для совмести­мости по-прежнему применяют в этом случае FAT. Отчасти это можно объяснить тем, что простая структура FAT требует меньше места для хранения служебных данных, чем остальные системы, и соответственно больше места остается под размещение данных. Преимущества других файловых систем становятся заметны только при использовании их на носителях объемом более 100 Мб.

VFAT. Файловая система VFAT (Virtual FAT), впервые реализованная в Windows NT 3.5 и Windows 95 (DOS 7.0), - это видоизмененная система FAT, дополненная поддержкой длинных имен файлов (Long File Name, LFN) в кодировке UNICODE (каждый символ имени кодируется 2 бай­тами). Схема распределения дискового пространства осталась той же, что и в FAT, но ограничения, устанавливаемые соглашениями по именам файлов, изменились:

допускаются имена длиной до 255 символов;

в имени может быть несколько пробелов и точек (при этом, однако, текст после последней точки рассматривается как расширение);

регистр символов в именах не различается, но сохраняется.

Основной проблемой при разработке VFAT было обеспечение кор­ректной работы старых программ, не поддерживающих длинные имена файлов. В итоге было принято решение для каждого файла и подкаталога в VFAT использовать два имени: длинное и короткое в формате 8.3 для совместимости со старыми программами. Длинные имена (LFN) хранят­ся в специальных записях каталога. Для любого файла или подкаталога непосредственно перед единственной записью каталога с его именем в формате 8.3 находится группа из одной или нескольких записей, пред­ставляющих длинное имя. Каждая такая записьсодержит часть длинного имени файла (не более 13 символов), из которых ОС составляет полное имя файла. Поскольку одно длинное имя может занимать до 21 записи, а корневой каталогFAT ограничен 512 записями, желательно ограничить использование длинных имен в корневом каталоге.

Короткое имя генерируется файловой системой автоматически в фор­мате 8.3. Для создания коротких имен (псевдонимов) файлов используется следующий алгоритм:

из длинного имени удаляются все символы, недопустимые в именах FAT, а также точки кроме последней;

строка, расположенная перед точкой, обрезается до 6 символов, и в ее конец добавляется «~1», строка, следующая за точкой, обрезается до 3 символов;

оставшиеся буквы преобразовываются в прописные;

если сгенерированное имя совпадает с уже существующим, увеличи­вается число в приставке «~-1».

FAT 32 - усовершенствованная версия системы VFAT, поддержива­ющая жесткие диски объемом более 32 Гб. Впервые она была включена в состав ОС Windows 95 OSR 2 и поддерживается во всех последующих версиях Windows.

В FAT32 были расширены атрибуты файлов, стало возможным хра­нить время и дату создания, модификации и последнего доступа к файлу или каталогу.

Из-за требования совместимости с ранее созданными программами структура FAT32 практически не изменилась. Главные отличия от преды­дущих версий FAT состоят в следующем:

блок начальной загрузки на разделах с FAT32 был увеличен до 2 сек­торов; он включает резервную копию загрузочного сектора, что делает систему быть более устойчивой к возможным сбоям на диске;

объем, занимаемый таблицей размещения файлов, увеличился, по­скольку теперь каждая записьв ней занимает 32 байта, и общее число кластеров на разделе FAT32 больше, чем на разделах FAT. Соответственно, выросло и количество секторов, отводимых под размещение служебной информации;

корневой каталогв FAT32 больше не располагается в определенном месте; теперь на этом месте хранится указатель на начальный кластер корневого каталога. В результате снимается ранее существовавшее огра­ничение на число записей в корневом каталоге;

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

HPFS. Эта система (High Performance File System, высокопроизво­дительная файловая система) была представлена фирмой IBM в 1989 г. вместе с операционной системой OS/2 версии 1.20. По производительно­сти она существенно превосходит FAT и позволяет использовать жесткие диски объемом до 2 Терабайт. Кроме того, она поддерживает разделы дискаразмером до 512 Гб и позволяет использовать имена файлов дли­ной до 255 символов (на каждый символ при этом отводится 2 байта). В HPFS по сравнению с FAT заметно уменьшено время доступа к файлам в больших каталогах.

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

Для нумерации единиц распределения дискового пространства HPFS использует 32 разряда, что дает 2³², или (учитывая знак числа) более 2 млрд блоков. Помимо стандартных, HPFS поддерживает расширенные атрибуты файла (Extended Attributes, EA), которые могут содержать до 64 Кб различных дополнительных сведений о нем.

Загрузочный блок в HPFS аналогичен загрузочному блоку в FAT. Си­стемные файлы, также как и в FAT, располагаются в корневом каталоге, но при этом физически могут находиться в любом месте диска.

Для обнаружения свободных секторов используется блок битовых карт (bitmap block list). Он похож на таблицу размещения файлов FAT. Каждому сектору группы соответствует один битв ее битовой карте, показывающий, занят ли он. Резервный блок (directory emergency free block list) обеспечивает высокую отказоустойчивость HPFS и позволяет восстанавливать поврежденные данныена диске. Расположение группы каталогов в центре диска значительно сокращает время позиционирова­ния головок чтения/записи.

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

Файловая система NTFS (New Technology File System) была специ­ально разработана для ОС Windows NT. В ней значительно расширены возможности по управлению доступом к отдельным файлам и каталогам, введено большое число атрибутов, реализованы отказоустойчивость и средства динамического сжатия файлов. NTFS допускает имена файлов длиной до 255 символов, при этом она использует тот же алгоритмдля генерации короткого имени, что и VFAT. NTFS обладает возможностью самостоятельного восстановления в случае сбоя ОС или оборудования, так что дисковый том остается доступным, а структура каталогов не на­рушается.

Каждый файлна разделе NTFS представлен записью в специаль­ном файле MFT (Master File Table, главная файловая таблица). NTFS резервирует около 1 Мб для размещения первых 16 записей служебной информации. 17-я и последующие записи MFT используются собственно файлами и каталогами. Первая записьсодержит саму главную файловую таблицу. За ней следует зеркальная запись MFT. Если первая запись MFT разрушена, NTFS считывает вторую запись, чтобы отыскать зеркальный файл MFT. Местоположение сегментов данных MFT и зеркального файла MFT хранится в секторе начальной загрузки. Копия сектора начальной загрузки находится в логическом центре диска. Третья запись MFT

содержит файлрегистрации, применяемый для восстановления файлов (табл. 2).