Читать реферат по информатике, вычислительной технике, телекоммуникациям: "Динамическое распределение памяти" Страница 5


назад (Назад)скачать (Cкачать работу)

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

правильности алгоритма 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 будет очень велико. Отсюда мы можем видеть, до какой степени неэффективен сбор мусора, когда память становится полной, и соответственно, насколько он эффективен, когда требования к памяти невелики. Можно объединить сбор мусора с некоторыми другими методами возврата ячеек в свободную память; эти принципы не исключают друг друга, и в некоторых системах используются как счетчик ссылок, так и схемы сбора мусора, а кроме того, программист может явно освобождать узлы.



Интересная статья: Быстрое написание курсовой работы