Распределение дисковой памяти
Распределение дисковой памяти выполняется задачей АРХИВ автоматически при помощи таблиц распределения памяти. Каждый диск имеет собственную таблицу распределения памяти. Таблица создается при начальной генерации системы. В целях повышения надежности по отношению к сбоям таблица распределения на диске хранится в двух экземплярах (см. 3.3.7.). Одним из элементов таблицы распределения является карта памяти. Карта памяти представляется в виде шкалы, в которой отмечаются единицей все занятые блоки и нулем все свободные.
При запуске ОС задача АРХИВ переносит карты распределения памяти с дисков в массовую память.
Объекты ФС отображаются на внешнюю память в виде набора областей. Размер файла наращивается динамически в пределах максимального размера. Наращивание файла осуществляется по инициативе кластера соответствующего метода доступа. При попытке записи за текущую границу файла, но не за границу максимального размера файла, кластер обращается к задаче АРХИВ с командой расширения файла. АРХИВ ищет соответствующую область на том диске, где находится файл, и наращивает его таблицу отображения.
Области на диске выделяются равными степени двойки(используется разновидность известного алгоритма близнецов ). Всю память можно представить в виде дерева, листьями которого являются области памяти (свободные или занятые). Размеры листьев одного уровня равны между собой. Размеры листьев увеличиваются в два раза при переходе с некоторого уровня на предшествующий более высокий уровень. В начальном состоянии все дерево состоит из одной вершины - корня - размером в полную дисковую память (для простоты предположим, что размер дисковой памяти равен некоторой степени двойки).
При запросе области просматривается список областей уровня, соответствующего запросу. Если таких областей памяти нет, то запрашивается область удвоенного размера на более высоком уровне. Полученная область делится пополам. Половина выдается в качестве ответа на запрос, половина помечается свободной.
Возвращаемые области либо помечаются свободными (если нет свободных братьев), либо вкупе со свободным братом образуют удвоеннную область, которая возвращается на более высокий уровень. Братьями являются только те области, которые получились делением более крупной области.
Одной из проблем распределения динамической памяти является фрагментация. Одним из аргументов в пользу приведенного алгоритма является его удобство и эффективность для борьбы с фрагментацией. Фрагментация наступает, когда не удовлетворяется запрос на область при наличии достаточного объема фрагментированной свободной памяти. При возникновении фрагментации запускается системная обслуживающая программа уплотнения памяти, которая работает следующим образом.
Определяются все справочники, содержащие файлы на данном диске. Составляется таблица соответствий (область, справочник), в которой для каждой занятой области на данном диске ставится в соответствии справочник, в котором имеется ссылка на эту область. После этих подготовительных действий происходит собственно уплотнение при помощи таблицы свободной памяти. Уплотнение выполняется поэтапно. Сначала уплотняется память на самом нижнем уровне, затем на последующем и т.д. до того уровня, на котором уплотнение не требуется.
В результате перемещения на одном уровне будут находиться сначала все занятые области, а затем свободные. После перемещения модифицируются справочники, которые были затронуты уплотнением - в таблице отображения соответствующего справочника проставляются новые адреса передвинутых областей (для этого и строилась таблица соответствий). После модификаций справочники отображаются на диск. При возникновении сбоев и отказов пропажи или порчи файлов не будет (см. 3.3.7.), потому что в рамках одного этапа уплотнения переписи происходят только в свободные области. Далее все свободные блоки, собранные на конце одного уровня, укрупняются по общим правилам и возвращаются на предшествующий более высокий уровень.На следующем этапе происходит все то же самое для более высокого уровня иерархии.
Данный алогоритм более эффективен при решении проблемы уплотнения по сравнению с другими известными алгоритмами (первый подходящий, наиболее подходящий).
