Методы распределения внешней памяти

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

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

Основной внутренней функцией каталогов в файловых системах оказывается связывание имени файла с информацией о местонахождении файла на магнитном носителе (совершенно также, как для каталога в библиотеке на бумажных носителях). Таким образом внутреннюю структуру элемента каталога файловых систем (ФС) можно образно изобразить в виде

Имя файла -> Информация о месте хранения файла.

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

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

В этом методе для файла выдвигается требование его размещения в непрерывной последовательности пронумерованных секторов. Этим облегчается составление информации о местонахождении файла на магнитном диске: такая информация будет всегда включать номер начального сектора в последовательности секторов хранения и число таких секторов для данного файла (теоретически можно было бы хранить и номер последнего сектора в такой последовательности). Подобное решение предельно просто и применялось в ОС "реального времени" в 80-х годах XX в., называвшейся RT-11. К очевидным недостаткам этого метода относится невозможность увеличить файл на старом месте его хранения, если за ним размещен другой файл. В таком случае содержимое файла с увеличенным размером приходилось размещать на новом месте (если оно имелось). При периодическом пополнении файла его содержимое перемещалось с места на место. Практическое использование указанного метода требовало периодической реорганизации размещения файлов, которое приводило к "выдавливанию" неиспользуемых участков размещения файлов и размещению используемых строго один за другим. Современным аналогом такого действия, решающего хотя и несколько иные задачи, является запуск служебной программы дефрагментации в файловых системах Windows 9x.

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

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

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

Возможны два варианта построения структур размещения файлов:

- произвольное размещение файлов, допускающее какой угодно разброс блоков файла по исходной совокупности пронумерованных блоков дисковой памяти;

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

Такие участки последовательно пронумерованных блоков дисковой памяти принято называть экстентами (от слова extent).

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

- единственная таблица размещения на файл;

- таблицы размещения с несколькими уровнями;

- сцепленные таблицы размещения.

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

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

Заметим, что все таблицы размещения файлов при работе с файловой системой должны находиться в оперативной памяти для обеспечения достаточно быстрой работы с файлами.

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

В связи с этим выделяют методы распределения файлов, под которыми понимают распределение новых блоков файлу из свободных на текущий момент. Такие распределения требуют ведения детальной информации о свободных блоках области данных файловой системы. Известны четыре метода распределения файлов, называемые по структуре детальной информации о свободных блоках:

n списком свободных блоков;

n картой свободных участков;

n битовой картой;

n таблицей распределения дисковой памяти.

Список свободных блоков использует структуру связного списка, который соединяет в одну цепочку все свободные блоки (на томе дисковой памяти или логическом диске). Недостатком этого метода являются большие затраты времени на создание и расширение файла, когда ему дополнительно выделяется не один, а достаточно много новых блоков. Удаление файлов при использовании этого метода также требует значительных затрат времени от ОС, потому что файловая система в этом случае должна все блоки удаляемого файла вставить в цепочку свободных блоков (выполняя столько операций над дисками, сколько блоков в удаляемом файле).

Наиболее изящным методом из перечисленных является метод битовой карты. Битовая карта представляет собой вспомогательную таблицу, хранимую на магнитном диске, в которой k-му биту таблицы соответствует k-й блок области данных файловой системы. Одно значение этого бита (обычно единичное) отражает занятость соответствующего блока каким-то файлом, другое значение (обычно нулевое) отражает, что соответствующий блок свободен. Если в конкретной файловой системе имеется к примеру, 4 млн. распределяемых блоков хранения по 512 байтов (секторов) с общей возможностью хранения около 2 Гбайт данных, то битовая таблица будет состоять из 4 млн. битов или, иначе говоря, из 512-килобайтной битовой карты. Такой относительно небольшой объем этой карты позволяет при работе компьютера держать ее постоянно в оперативной памяти и достаточно быстро определять занятость блока дисковой памяти с любым номером. Заметим, что битовая карта дает информацию только о свободных блоках (и как несущественное следствие, о занятых), но не несет никакой информации о размещении файлов по конкретным блокам.

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

Таблица распределения дисковой памяти является структурой, объединяющей в себе свойства и битовой карты и таблицы размещения отдельных файлов. Ее английское наименование File Allocation Table дало обозначение ряду файловых систем (FAT), получивших широкое распространение в разработках фирм IBM и Microsoft, которые рассмотрим далее.

Дата добавления: 2014-01-05