ROLLER (663643), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Обратим внимание на то, что в шагах D4 и D5 искусственно изменяется списочная структура. Когда происходит возврат к предыдущему состоянию, поле ATOM говорит о том, какие из связей ALINK и BLINK содержат искусственные адреса. "Вложения", показанные в нижней части рисунка служат иллюстрацией того, что в алгоритме каждый неатомарный узел посещается три раза

Доказательство правильности алгоритма D можно построить, основываясь на индукции по количеству узлов, которые подлежат маркировке. Одновременно доказывается, что в конце алгоритма Р=Р0. Алгоритм D будет работать быстрее, если исключить шаг DЗ, а вместо него выполнить проверки "ATOM (Q) = 1" и соответствующие действия в шагах D4 и D5, а также проверку "ATOM (Р0) = 1" в шаге D1.

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

Время выполнения наилучших из известных программ сбора мусора выражается, по существу, формулой c1N+c2M, где c1 и c2 — константы, N-количество маркируемых узлов, а М - общее количество узлов в памяти. Таким образом, М - N - количество найденных свободных узлов, и время, которое расходуется на возврат одного такого узла в свободную память, составляет (c1N + c2М)/(М-N). Пусть N = М; тогда формула преобразуется к виду (c1 + c2)/(l — ). Следовательно, если =3/4, т. е.

память заполнена на три четверти, то потребуется 3c1 + 4c2 единиц времени, чтобы вернуть в свободную память один узел; если  =1/4 , то соответствующая величина составляет лишь 1/3c1 + 1/4c2.

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

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

Характеристики

Список файлов реферата