Проблема висячих ссылок

⇐ ПредыдущаяСтр 21 из 25Следующая ⇒

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

Существует несколько методов борьбы с висячими ссылками. Один из них - использование при работе с памятью счетчиков ссылок.

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

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

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

Кроме того, этот метод не годится для случая, когда элементы в куче связываются в список. Отслеживание количества ссылок в этом случае может привести к появлению “мусора “. На рис.3.15 показан пример “замусоривания” памяти.

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

При появлении мусора память системы память системы, замусориваясь, постепенно истощается, так как элементы, ставшие мусором, оказываются недоступными для использования, а занятая ими память оказывается недоступной для перераспределения.

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

Ссылка на первый

Элемент списка

2...

1...

Ссылка на первый элемент списка 2... 1... 1... б

Пустая ссылка ¨ 1... 1... 1... в

Рис.3.15. Появление мусора при использовании счетчиков ссылок

Сбор мусора

Каждый алгоритм сбора мусора выполняется в две стадии:

Маркировка активных элементов (т.е. элементов, являющихся частью доступных, используемых в данный момент структур данных).

Сбор элементов, помеченных как мусор и возврат их в список свободных блоков кучи.

Для реализации алгоритмов сбора мусора необходимо выполнение определенных условий:

¨ Система должна иметь возможность выявить все указатели на элементы кучи, находящиеся вне ее.

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

¨ Для каждого активного элемента кучи система должна иметь возможность определить все поля внутри него, содержащие указатели на элементы кучи.

Это не всегда просто, так как накладывает дополнительные ограничения на формат элементов, размещаемых в куче (все элементы должны быть либо одного формата, либо иметь фиксированные форматы для представления данных различных типов), чтобы при просмотре кучи система могла выявить поля. содержащие ссылки. Кроме того, указатели нельзя “вычислять” в программе (например, путем добавления смещения к базовому адресу), значения ссылок могут только присваиваться или сравниваться.

¨ На каждый активный элемент кучи должна быть ссылка извне кучи или из другого ее активного элемента.

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

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

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

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

if Установлен бит сбора мусора

then Добавить элемент к свободному списку

else Установить бит сбора мусора

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

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

Один из наиболее простых алгоритмов маркировки основан на использовании временного стека.

Этот алгоритм включает следующие шаги:

¨ Инициализация: поместить в стек все внешние указатели на элементы кучи.

¨ Повторять, пока стек не пуст, следующие действия:

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

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

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

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

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

Для описания алгоритма введем следующие обозначения:

· Current - ссылка на текущий элемент;

· Last - ссылка на последний элемент.

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

Поле, в которое записывается маркер (бит сбора мусора), назовем Sign. Через Pointers_Counter обозначим количество полей, содержащих указателина элементы кучи, в каждом ее элементе.

Таким образом, перед началом работы алгоритма в поле Sign бита сбора мусора каждого элемента записано значение 1 (элемент помечен как мусор), а в поле номера выбранного указателя Number - значение 0 (указатели не выбирались, данный элемент еще не просматривался).

Алгоритм может быть описан следующим образом:

{ Выбираем внешние ссылки на структуры данных, размещенных в куче: }

while Есть непустые внешние указатели на немаркированные элементы кучи do

begin { Переход к следующей маркируемой структуре данных в куче: }

Current Внешний непустой указатель на немаркированный элемент;

Last nil; { Предшествующего элемента нет }

{ Маркировка текущего элемента: }

while Current.Sign = 1 { Данный элемент отмечен пока как мусор. }

{ Следовательно, нужно его промаркировать как активный и }

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

begin { Выбрать новый элемент по ссылке из данного элемента: }

Current.Number Current.Number +1;

while ( Current.Number < Pointers_Counter ) and

( Current.Pointers [ Number ] = nil) do

{ Ищем непустую ссылку на элемент кучи: }

Current.Number Current.Number +1;

if ( Current.Number £ Pointers_Counter )

and ( Current.Pointers [ Current. Number ] ¹ nil)

then { Нашли непустую ссылку - переходим на выбранный }

{ по ней элемент, выполняя циклическую перестановку }

Current ® Last ® Current.Pointers [ Current. Number ]

{ если элемент еще не выбирался при обходе списка: }

begin

P Current.Pointers [ Current. Number ];

if ( P.Sign =1) and ( P.Number = 0) then

{ элемент еще не маркирован и ссылка не циклическая }

begin Current.Pointers [ Current. Number ] Last;

Last Current; Current P;

end;

end

else { Непройденных ссылок больше нет - маркируем элемент: }

begin Current.Sign 0; Current.Number 0;

if Last ¹ nil then

{ Возврат по цепочке к предшествующему элементу и }

{ восстановление ссылок обратной перестановкой: }

Current Last Current.Pointers [ Current. Number ]

begin P Current; Current Last;

Last Current.Pointers [ Current. Number ];

Current.Pointers [ Current. Number ] P;

End

end;

End.

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

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

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

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

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

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

Обозначим 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;

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

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

Дата добавления: 2016-01-05; просмотров: 24; Мы поможем в написании вашей работы!
Поделиться с друзьями:

⇐ Предыдущая 16 17 18 19 202122 23 24 25 Следующая ⇒

Мы поможем в написании ваших работ!