Динамическое распределение памяти

| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: легкие реферат, конспект урока 9 класс
| Добавил(а) на сайт: Роберта.

"искусственной" стековой связи, находящейся теперь в NODE (Т).)
D2. [Отметить.] Установить MARK (Р) ( 1.
DЗ, [Атом?] Если ATOM (Р) = 1, то перейти к Е6.
D4. [Вниз по ALINK.] Установить Q(ALINK (Р). Если Q(( и MARK (Q) = 0, то установить ATOM (Р) (1, ALINK (Р)(Т, Т(Р, P(Q и перейти к D2. (Теперь поля
ATOM и ALINK на время изменены и, следовательно, довольно радикально изменилась списочная структура в некоторых отмеченных узлах. Но в шаге D6 все будет восстановлено.)
D5. [Вниз по BLINK.) Установить Q(BLINK (Р). Если Q(( и MARK(Q)=0, то установить BLINK (Р)(Т, Т(Р, Р(Q и перейти к D2.
D6. [Вверх.] (В этом шаге устраняются изменения связей, сделанные в шагах

D4 или D5; значение АТОМ (Т) говорит о том, какую из связей ALINK (Т) или BLINK (Т) следует восстановить.) Если Т=(, алгоритм завершен. В противном случае установить 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 = (М; тогда формула преобразуется к виду (c1( + c2)/(l — ().
Следовательно, если (=3/4, т. е. память заполнена на три четверти, то потребуется 3c1 + 4c2 единиц времени, чтобы вернуть в свободную память один узел; если ( =1/4

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

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