Динамическое распределение памяти
Категория реферата: Рефераты по информатике, программированию
Теги реферата: легкие реферат, конспект урока 9 класс
Добавил(а) на сайт: Роберта.
Предыдущая страница реферата | 1 2
"искусственной" стековой связи, находящейся теперь в 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 будет очень
велико. Отсюда мы можем видеть, до какой степени неэффективен сбор мусора, когда память становится полной, и соответственно, насколько он эффективен, когда требования к памяти невелики.
Можно объединить сбор мусора с некоторыми другими методами возврата ячеек в свободную память; эти принципы не исключают друг друга, и в некоторых системах используются как счетчик ссылок, так и схемы сбора мусора, а кроме того, программист может явно освобождать узлы.
Скачали данный реферат: Drugov, Pchel'nikov, Velimir, Орлов, Potap, Jernst, Kotjash.
Последние просмотренные рефераты на тему: сочинения по русскому языку, скачать реферат бесплатно на тему, контрольные работы 2 класс, мцыри сочинение.
Предыдущая страница реферата | 1 2