Cтраница 1
Сбор мусора ( scavenging), или подсматривание ( browsing), означает восстановление с помощью соответствующих утилит файлов, удаленных с гибких и жестких дисков и магнитных лент. [1]
Сбор мусора обычно распадается на две фазы. Теперь во время первой фазы отмечаются все узлы, не являющиеся мусором, отправляясь от узлов, которые непосредственно доступны из главной программы. Во второй фазе осуществляется последовательный проход по всей области пула памяти и все неотмеченные узлы заносятся в список свободного пространства. Фаза маркировки наиболее интересна, и поэтому на нее мы и обратим основное внимание. Существуют некоторые видоизменения, касающиеся второй фазы и делающие ее нетривиальной; см. упр. [2]
Поскольку сбор мусора происходит редко ( только если исчерпается список свободного пространства), то процедуре сбора мусора позволительно быть довольно Дорогостоящей. [3]
Хотя сбор мусора требует одного бита маркировки для каждого узла, можно хранить отдельную таблицу всех битов маркировки, скомпонованных вместе, в другой области памяти, установив соответствие между адресом узла и его битом маркировки. На некоторых машинах эта идея может привести к методу организации сбора мусора, который более привлекателен, чем потеря бита в каждом узле, но на многих других машинах процесс сбора мусора при этом заметно замедляется. [4]
Операция сбора мусора обычно используется в приложениях, связанных с обработкой сложных списков, когда в нескольких списках содержатся одинаковые элементы или даже группы элементов. В таких случаях при исключении элемента из одного списка неизвестно, имеются ли ссылки из других списков на тот же самый элемент, и, следовательно, соответствующую область нельзя включать в список свободных областей. Организация списка свободных областей и сбор мусора используются во время функционирования программных систем обработки списков, основанных на языках обработки списковых структур, подобных языку LISP. Все действия по управлению памятью выполняются программным путем. [5]
Алгоритмы сбора мусора интересны по нескольким причинам. Можно, например, найти все подпрограммы, к которым прямо или косвенно обращается некоторая подпрограмма; см. упр. [6]
При общем сборе мусора и его грубой сортировке до измельчения в канализацию может поступать до 100 г / cyrn на 1 человека сухого вещества. [7]
При общем сборе мусора и его грубой сортировке до измельчения в канализацию может поступать до 100 г / сут на 1 человека сухого вещества. [8]
Можно объединить сбор мусора с некоторыми другими методами возврата ячеек в свободную память; эти принципы не исключают друг друга, и в некоторых системах используются как счетчик ссылок, так и схемы сбора мусора, а кроме того, программист может явно освобождать узлы. Идея заключается в том, чтобы использовать сбор мусора, как последнюю надежду, когда непригодны все другие методы возврата ячеек. Достоинства такого подхода представляются весьма спорными, если иметь в виду неэффективность сбора мусора, когда память почти заполнена, и тот факт, что очень немногие программы не превосходят пределов памяти вскоре после того, как она стала близка к заполнению. [9]
В алгоритме сбора мусора и уплотнения, как показывают соответствующие оценки ( см. упр. Когда память загружена не очень плотно и удовлетворяются соответствующие ограничения, сбор мусора и уплотнение очень эффективны; например, на машине MIX метод сбора мусора работает быстрее, чем два других метода, если память никогда не заполняется более чем на одну треть и если узлы относительно малы. [10]
Принятая система сбора мусора в стандартные контейнеры имеет еще целый ряд существенных недостатков. Мусоросборные камеры располагаются в непосредственной близости к входам в подъезды. Все операции по вывозу контейнеров и санитарному содержанию мусороприемных камер недостаточно изолированы от населения. В каждой мусороприемной камере трудно организовать мойку контейнеров. Транспортировка их к мусоровозу практически возможна только вручную. [11]
Рассмотрим проблему сбора домашнего мусора. Допустим, что определенный район города обслуживается единственной машиной. Ребра графа О представляют дороги, а вершины - пересечения дорог. [12]
Рассмотрим проблему сбора домашнего мусора. Допустим, что определенный район города обслуживается единственной машиной. Ребра графа G представляют дороги, а вершины - пересечения дорог. Величина с ( о -) - вес ребра - будет соответствовать длине дороги. Тогда проблема сбора мусора в данном районе сводится к нахождению цикла в графе G, проходящего по каждому ребру G по крайней мере один раз. Требуется найти цикл с наименьшим километражем. В действительности емкость машины и продолжительность рабочего дня накладывают ограничения на число улиц, которые может обслужить одна машина за день. [13]
Наиболее сложной частью сбора мусора является маркировка. К сожалению, анализируя элемент, мы не можем определить его состояние, поскольку в самом элементе мусора не содержится каких-либо признаков, указывающих на его принадлежность к мусору. Таким образом, недостаточно просто просмотреть кучу, найти все указатели и отметить как активные те элементы, на которые они указывают. [14]
Наиболее интересная особенность сбора мусора состоит в том, что во время работы этого алгоритма в нашем распоряжении остается очень ограниченный объем свободной памяти, которую можно использовать для управления алгоритмом маркировки. Существо этой интригующей проблемы станет понятным из дальнейшего; большинство людей не сразу осознает все трудности, связанные со сбором мусора, и вот уже много лет не удается найти хорошего решения этой проблемы. [15]