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

Для решения проблемы фрагментации памяти в системе могут быть реализованы различные алгоритмы уплотнения. Уплотнение может быть частичным или полным. При частичном уплотнении памяти активные блоки нельзя сдвигать, поэтому уплотнение выполняется только путем объединения смежных свободных блоков. Полное уплотнение выполняется посредством сдвига активных элементов для ликвидации образовавшихся между ними “окон”.

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

На время выполнения алгоритма уплотнения вычисления приостанавливаются.

Обозначим Compaction_Pointer указатель уплотнения элемента кучи, а Size - размер элемента кучи. Для выполнения алгоритма уплотнения потребуется также два рабочих указателя: P - указатель для перемещения по элементам кучи, Q - текущий указатель уплотнения.

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

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

¨ первоначально указатели P и Q устанавливаются на начало кучи;

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

{ Инициализация: }

Q Ссылка на первый блок кучи;

P Ссылка на первый блок кучи;

{ Последовательный проход по элементам кучи: }

while P не вышел за пределы кучи do

Begin

if P.Sign = 0 { Блок не является мусором }

Then

begin { Устанавливаем его указатель уплотнения }

P.Compaction_Pointer Q;

Q Q + P.Size

end;

P P + P.Size { Переходим к следующему блоку }

End.

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

for N 1 to Pointers_Counter do

Current.Pointers [ N ] Current.Pointers [ N ]. Compaction_Pointer;

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

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