Динамическое распределение памяти (стр. 2 из 2)
B2. [Стек пуст?] Если Т = В, перейти к B5.
BЗ. [Взять из стека верхний элемент.] Установить К¬STACK [Т],
B4.[Исследовать связи.] Если узел NODE(K) - атом, то вериуться
К B2. В противном случае, если NODЕ(АL1NK(К)) не отмечен, то отметить его и занести ALINK (К) в стек. Аналогично, если NODE (BLINK (К)) не отмечен, то отметить его и занести REF (К) в стек. Вернуться к B2.
B5. [Прочесать.] Если K1>М, то алгоритм завершен. (Переменная К1 представляет наименьший адрес, откуда имеется возможность вновь выйти на узел, который следует отметить.) В противном случае, если NODE(KI) нe отмечен, увеличить К1 на 1 и повторить этот шаг. Если NODE (К1) отмечен, то установить К¬К1, увеличить К1 на 1 и перейти к B4.
Этот алгоритм можно улучшить, если не заносить в стек X, когда NODE (X) - атом.
Алгоритм B фактически становится алгоритмом А, когда Н = 1, и очевидно, эффективность его плавно возрастает с увеличением Н. К сожалению, алгоритм B не поддается точному анализу по тем же причинам, что и алгоритм А, и мы не в состоянии указать, при каком Н этот метод будет достаточно быстрым. В качестве правдоподобного, но не очень надежного можно назвать значение Н = 50, при котором алгоритм B применим для сбора мусора в большинстве случаев.
В алгоритме В используется стек, расположенный в последовательных ячейках памяти, которые расположены в памяти непоследовательно. Этот факт наводит на мысль, что в алгоритме мы могли бы организовать стек, каким-то образом разбросав его по той же самой области памяти» в которой собирается мусор. Это нетрудно сделать, если предоставить программе сбора мусора немного больше места, чтобы она могла "вздохнуть свободнее".
Будем считать, например, что все Списки представлены, за тем лишь исключением, что поле RЕF в каждом головном узле используется для сбора мусора, а не для счетчика ссылок. Тогда мы можем переработать алгоритм организовав стек в полях REF головных узлов.
Алгоритм D (Маркировка). Пусть дано множество узлов, имеющих следующие поля
MARK (одноразрядное поле,первоначально
нулевое в каждом узле),
ATOM (еще одно одноразрядное поле),
ALINK (указательное поле),
BLINK (указательное поле),
Когда ATOM = 0, поля ALINK и BLINK могут содержать L или указатель на другой узел того же формата; когда ATOM = 1, содержимое полей ALINK и BLINK несущественно для данного алгоритма.
Если задан указатель Р0, то этот алгоритм устанавливает 1 в поле MARK в узле NODE (Р0) и во всех других узлах, до которых можно добраться по цепочке указателей ALINK и BLINK и в которых ATOM = MARK = 0. В алгоритме используются три указательные переменные, Т, Q и Р, и связи при выполнении алгоритма могут быть временно изменены, но так, что после завершения алгоритма во всех полях ATOM, ALINK и BLINK восстанавливаются их прежние значения.
D1. [Начальная установка.] Установить Т¬L, Р¬Р0. (Далее в этом алгоритме переменная Т будет использоваться в двух смыслах: если Т¹L, то она указывает на вершину того, что, по существу, является стеком, а узел, на который указывает Т, некогда содержал связь, равную Р, вместо "искусственной" стековой связи, находящейся теперь в NODE (Т).)
D2. [Отметить.] Установить MARK (Р) ¬ 1.
DЗ, [Атом?] Если ATOM (Р) = 1, то перейти к Е6.
D4. [Вниз по ALINK.] Установить Q¬ALINK (Р). Если Q¹L и MARK (Q) = 0, то установить ATOM (Р) ¬1, ALINK (Р)¬Т, Т¬Р, P¬Q и перейти к D2. (Теперь поля ATOM и ALINK на время изменены и, следовательно, довольно радикально изменилась списочная структура в некоторых отмеченных узлах. Но в шаге D6 все будет восстановлено.)
D5. [Вниз по BLINK.) Установить Q¬BLINK (Р). Если Q¹L и MARK(Q)=0, то установить BLINK (Р)¬Т, Т¬Р, Р¬Q и перейти к D2.
D6. [Вверх.] (В этом шаге устраняются изменения связей, сделанные в шагах D4 или D5; значение АТОМ (Т) говорит о том, какую из связей ALINK (Т) или BLINK (Т) следует восстановить.) Если Т=L, алгоритм завершен. В противном случае установить Q¬Т. Если АТОМ (Q)=1, то установить ATOM (Q)¬0, Т¬ALINK (Q), ALINK(Q)¬P, P¬Q и вернуться к D5. Если ATOM (Q) = 0, то установить Т¬BLINK (Q), BLINК(Q)¬Р, Р¬Q и вернуться к D6.
Блок-схема алгоритма D показана на рисунке,
После После
ALINK BLINK 
D1.Нач. D2. D3. D4. Вниз по D5. Вниз по D6. Вверх 
установка Отметить Атом? ALINK Уже BLINK Уже 
Да отмечен отмечен 
Обратим внимание на то, что в шагах 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 = rМ; тогда формула преобразуется к виду (c1r + c2)/(l — r). Следовательно, если r=3/4, т. е.
память заполнена на три четверти, то потребуется 3c1 + 4c2 единиц времени, чтобы вернуть в свободную память один узел; если r =1/4 , то соответствующая величина составляет лишь 1/3c1 + 1/4c2.
Если сбор мусора не используется, то расход времени на один возвращаемый узел равен константе c3 и, вне всяких сомнений, отношение c3/c1 будет очень велико. Отсюда мы можем видеть, до какой степени неэффективен сбор мусора, когда память становится полной, и соответственно, насколько он эффективен, когда требования к памяти невелики.
Можно объединить сбор мусора с некоторыми другими методами возврата ячеек в свободную память; эти принципы не исключают друг друга, и в некоторых системах используются как счетчик ссылок, так и схемы сбора мусора, а кроме того, программист может явно освобождать узлы.