Размещение файлов в дисковой памяти

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

Связное распределение памяти

1 Свободен

2

3

4

5 Свободен

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

Несвязное распределение памяти

Распределение при помощи списков секторов

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

1

2 Свободен

3

4 Свободен

5

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

Недостатком же такого способа распределения памяти является увеличение накладных расходов для создания механизма обработки ссылок-указателей, а также возможное увеличение времени доступа.

Поблочное распределение памяти

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

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

Цепочка блоков

Каталог

Файл Местоположение Данные Данные ДанныеNil

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

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

Цепочка индексных блоков

Каталог

Файл Местоположение

Цепочка индексных блоков

…

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

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

Каталог Таблица поблочного отображения файлов

Файл Местоположение

А 4

В 6 Таблица отображения

файлов

0
1
2
3 6
4 Nil
5
6 4
7
8
9

Физические блоки внешней памяти

Блок 0	Блок 1	Блок 2	Блок 3 А(1)	Блок 4 А(3)
Блок 5	Блок 6 А(2)	Блок 7	Блок 8	Блок 9

В схеме с таблицами поблочного отображения вместо указателей используются номера блоков. Обычно номера легко преобразуются в фактические адреса. Используется таблица отображения файлов, в которой содержатся по одной строке на каждый блок диска. Строка в каталоге пользователя указывает на строку таблицы отображения, соответствующей первому блоку данного файла. Каждая строка таблицы отображения содержит номер следующего блока данного файла. Таким образом, можно все блоки файла находить последовательно просматривая строки таблицы отображения файлов. В тех строках таблицы, которые соответствуют последним блокам файлов, обычно устанавливается пустой указатель Nil. В некоторых строках таблицы указывается признак “свободен”, указывающий на то, что данный блок может быть выделен по очередному запросу.

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