Главная Промышленная автоматика.

Предлагаем читателю самостоятельно рассмотреть ситуацию, когда расщепляется пустой блок размером Sj+i на используемый для хранения данных блок размером sj и пустой блок размером

Если эта информация будет поддерживаться при реорганизации блоков и списки свободных блоков будут связаны в обоих направлениях, то потребуется лищь фиксированное время на каждое расщепление блока на близнецов или объединение близнецов в более крупный блок. Поскольку количество объединений не может превосходить количество расщеплений, общий объем работы будет пропорционален количеству расщеплений. Нетрудно убедиться в том, что больщинство запросов на выделение блока вообще не требуют расщеплений, поскольку блок нужного размера уже имеется в наличии. Однако бывают нестандартные ситуации, когда каждая операция выделения требует нескольких расщеплений. Примером такой "нещтатной" (которую можно даже назвать экстремальной) ситуации являются многократно повторяющиеся запросы на получение блока минимального размера с последующим его возвращением. В этой ситуации, если в системе динамической памяти имеются блоки п различных размеров, то при использовании метода близнецов Л-го порядка потребуется по крайней мере расщеплений, а затем еще л/А: объединений при возврате блока.

12.6. Уплотнение памяти

Бывают случаи, когда даже после объединения всех смежных пустых блоков система не в состоянии выполнить запрос на выделение нового блока. Бывает, конечно, что во всей динамической памяти просто не хватает свободного пространства для выделения блока требуемого размера. Однако более типичной является ситуация, подобная той, которая показана на рис. 12.5, когда, несмотря на наличие 2 200 байт свободной памяти, мы не в состоянии выполнить запрос на выделение блока размером более 1 ООО байт. Проблема заключается в том, что свободное пространство делится между несколькими несмежными блоками. Существуют два общих подхода к рещению этой проблемы.

1. Пространство, вьщеляемое для хранения данных, состоит из нескольких пустых блоков. В таком случае можно потребовать, чтобы все блоки имели одинаковый размер и чтобы в них было предусмотрено место для указателя и данных. Указатель в используемом блоке указывает на следующий блок, используемый для хранения данных (в последнем блоке указатель равен нулю). Если бы, например, мы хранили данные, размер которых чаще всего невелик, то можно было бы выбрать блоки по 16 байт (4 - для указателя и 12 - для данных). Если же элементы данных обычно имеют больщие размеры, следовало бы выбрать блоки размером несколько сотен байт (по-прежнему 4 байта для указателя, а остальное для данных).

2. Если объединение смежных пустых блоков не позволяет получить достаточно больщой блок, данные в динамической памяти нужно переместить таким образом, чтобы все заполненные блоки сместились влево (т.е. в сторону позиций с меньщими номерами); в этом случае справа образуется один крупный блок свободной памяти.

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



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

Задача уплотнения памяту!

Типичная задача, с которой постоянно приходится сталкиваться на практике, заключается в следующем: нужно совокупность используемых бдоков (например, ту, которая показана на рис. 12.9, а), каждый из которых может иметь свой размер и на которых может указывать несколько указателей, смешать влево до тех пор, пока все свободное пространство не окажется с правой стороны динамической памяти, как показано на рис. 12.9, б. Указатели, конечно же, должны по-прежнему указывать на те же данные.

Данные 1

Данные 2

Данные 3

С D Е

а. Перед уплотнением

Данные "

Данные 2

Данные 3


б. После уплотнения Рис. 12.9. Процесс уплотнения памяти

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

Простая схема уплотнения заключается в том, что сначала нужно просмотреть все бдоки слева направо (как заполненные, так и пустые) и вычислить так называемый "адрес передачи" (forwarding address) ддя каждого заполненного бдока. Адрес передачи бдока - это его текущая позиция минус сумма всего пустого пространства слева от него, т.е. позиция, в которую в конечном счете необходимо переместить этот бдок. Адрес передачи бдока вычислить несложно. Когда мы просматриваем все бдоки слева направо, нужно суммировать объем встречающихся свободных бдоков и вычитать этот объем из позиции каждого встречающегося бдока. Эскиз соответствующего алгоритма представлен в листинге 12.6.



Листинг 12.6. Вычисление адреса передачи

(1) var

р: integer; { позиция текущего блока }

дар: integer; { накапливаюш?4Йся оЬшут объем гт/стых блоков } begin

(2) р:= левый край динамической памяти;

(3) дар:= 0;

(4) while р < правый край динамической памяти do begin

{ сделать р указателем на блок В }

(5) if В - гт/стой блок then

{6) дар:= дар + счетчик в блоке В

else { В заполнен }

(7) адрес передачи блока В := р - дар;

(8) р:= Р + счетчик в блоке В end

end;

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

for i: = р to р - 1 + счетчик в блоке В do heap[i-gap] Леар[1];

чтобы сместить блок В влево на величину ар. Обратите внимание, что перемешение заполненных блоков занимает время, пропорциональное объему используемой динамической памяти, и, по-видимому, будет преобладать над другими временными затратами, связанными с уплотнением памяти.

Алгоритм Морриса

Ф. Л. Моррис (F. L. Morris) разработал метод уплотнения динамической памяти, не предусматриваюший резервирования пространства в блоках для хранения адресов передачи. Ему, однако, требуется дополнительный бит метки конца цепочки указателей. Суть этого метода заключается в создании цепочки указателей, исходяшей из определенной позиции в каждом заполненном блоке и связываюшей все указатели с этим блоком. Например, на рис. 12.9, а мы видим три указателя. А, D и Е, указывающих на крайний слева заполненный блок. На рис. 12.10 показана требуемая цепочка указателей. Часть пространства блока, равного размеру указателя, изъята из блока и помешена в конец цепочки, где находится указатель А.

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

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

В этом коде массив heap (куча) содержит адреса блоков динамической памяти. - Прим. ред. 12.6. УПЛОТНЕНИЕ ПАМЯТИ 365





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 [117] 118 119 120 121 122 123

0.002