Cтраница 4
В таком случае обработка счетчиков ссылок будет необходима только для этих специальных элементов с переменными счетчиками ссылок, рассмотрим, например, систему oOj работки списков, в которой каждый связанный список считается отдельной структурой данных. Если мы снабдим каждый список специальным головным элементом и потребуем, чтобы указатели из других списков указывали только на эту голову, но не на внутренние элементы списка, то счетчик ссылок будет необходим только в головном элементе. Более того, в счетчике ссылок головы нужно подсчитывать только указатели извне данной структуры. Все это изображено на рис. 7.9. Отдельные элементы можно удалять из списка и сразу же возвращать в список свободного пространства, не учитывая счетчики ссылок. Когда счетчик ссылок головы станет нулевым ( например, в результате уничтожения указателя, записанного в другом списке), то весь наш список - голова и все элементы - может быть возвращен в список свободного пространства. [46]
Использование счетчиков ссылок - более простой из двух упомянутых методов, поэтому мы начнем с него. Основная идея состоит в следующем: внутри каждого элемента в куче выделяется некоторое дополнительное пространство для счетчика ссылок. Счетчик ссылок элемента в любой момент времени содержит целое число, равное числу существующих указателей на этот элемент. [47]
В таком случае обработка счетчиков ссылок будет необходима только для этих специальных элементов с переменными счетчиками ссылок, рассмотрим, например, систему oOj работки списков, в которой каждый связанный список считается отдельной структурой данных. Если мы снабдим каждый список специальным головным элементом и потребуем, чтобы указатели из других списков указывали только на эту голову, но не на внутренние элементы списка, то счетчик ссылок будет необходим только в головном элементе. Более того, в счетчике ссылок головы нужно подсчитывать только указатели извне данной структуры. Все это изображено на рис. 7.9. Отдельные элементы можно удалять из списка и сразу же возвращать в список свободного пространства, не учитывая счетчики ссылок. Когда счетчик ссылок головы станет нулевым ( например, в результате уничтожения указателя, записанного в другом списке), то весь наш список - голова и все элементы - может быть возвращен в список свободного пространства. [48]
Это число равно сумме весов оставшихся указателей. На рис. 16.17, г показана ситуация, возникающая после дальнейшего дублирования одного из указателей. Совершенно очевидно, что обнуление счетчика ссылок произойдет при полном удалении всех указателей, после чего ячейка может обрабатываться сборщиком мусора. [49]
Основным преимуществом хранения весов внутри указателей, как и в методе однобитовых счетчиков ссылок, является то, что отсутствует необходимость осуществления доступа к ячейке при увеличении числа указателей на нее. Мы должны изменить показания счетчика ссылок ячейки при удалении ссылок на нее, но при этом обычно снимаются ссылки с указывающей ( адресующей) ячейки, так что доступ к адресуемой ячейке будет осуществлен в любом случае. Именно по этой причине метод взвешенных счетчиков ссылок особенно хорошо подходит для распределенных версий реализации функциональных языков, где частота посылок сообщений сильно влияет на эффективность работы. [50]
Циклические структуры, однако, не самая главная трудность, связанная с применением счетчиков ссылок. Во многих случаях циклические структуры не допускаются или встречаются столь редко, что возможное появление мусора не представляет серьезной опасности. Более важным фактором является стоимость работы со счетчиками ссылок. Во время выполнения непрерывно должны происходить проверки счетчиков ссылок, их увеличение и уменьшение. Часто это вызывает значительное снижение эффективности выполняемой программы. Рассмотрим, например, простое присваивание Р: Q, где Р и Q - переменные типа указатель. [51]
Одной из поразительных черт сбора мусора как метода утилизации памяти является то, что затраты на его выполнение ( приблизительно) обратно пропорциональны объему утилизуемой памяти; сбор мусора обходится тем дороже, чем меньше памяти утилизуется. Причина этого в том, что большая часть затрат на сбор мусора приходится на фазу маркировки, а маркировка тем сложнее, чем больше активных элементов в куче. В противоположность этому стоимость утилизации памяти с использованием счетчиков ссылок строго пропорциональна объему утилизуемой памяти. Как результат такого свойства сбора мусора этот метод становится очень дорогостоящим, когда куча почти заполнена активными элементами. В действительности часто программа, которая близка к тому, чтобы использовать всю кучу ( и, следовательно, остановиться из-за нехватки памяти), перед этим инициирует ряд дорогостоящих и сравнительно бесполезных процедур сбора мусора, каждая из которых освобождает лишь несколько ячеек памяти, тут же потребляемых при возобновлении счета, что быстро приводит к новому сбору мусора. [52]
Общая стоимость операции присваивания значительно возрастает. Любая аналогичная операция, кбторая может создавать или уничтожать указатели, также должна модифицировать счетчики ссылок. Кроме того, приходится платить за дополнительную память для счетчиков ссылок. Если в элементе кучи уже есть лишнее пространство, то память для счетчиков ссылок не вызывает затруднений. Чаще однако, чтобы хранить счетчики ссылок, к каждому элементу приходится добавлять по одному слову памяти. Если первоначально элементы занимали одно или два слова, то счетчики ссылок могут существенно уменьшить объем памяти, доступный для данных. [53]
Таким образом, когда указательные переменные продвигались по Списку, они не включались в счетчики ссылок для отдельных узлов; но, поскольку программист знает правила, в соответствии с которыми ведется учет ссылок для полных Списков, ему известно ( теоретически), как избежать ссылок на любые Списки, у которых счетчик ссылок равен нулю. Программист может также явным образом сбросить счетчики ссылок и вернуть некоторые Списки в свободную память. Эти идеи требуют от программиста осторожности; в руках неопытных программистов они оказываются опасными, и отладка программы становится более трудной из-за последствий, вызванных ссылками на уже стертые узлы. Самой привлекательной частью предложенной идеи является способ работы со Списками, у которых счетчик ссылок только что стал нулевым: такой список подключается в конец имеющегося списка свободного пространства ( для списка с двумя связями это сделать совсем просто) и рассматривается как свободное пространство в последнюю очередь, если использованы все предыдущие свободные ячейки; и только когда отдельные узлы этого Списка снова отдаются в работу, счетчики ссылок в Списках, на которые они ссылаются, уменьшаются на единицу. [54]
Принципиальный недостаток метода счетчиков состоит в том, что он не всегда возвращает в список свободной памяти те узлы, которые фактически являются свободными. Он хорошо работает с частично перекрывающимися списками, но рекурсивные списки, например L и N в ( 4), никогда не будут возвращены в свободную память по методу счетчиков ссылок; их счетчики будут ненулевыми ( поскольку они ссылаются сами на себя) даже тогда, когда на них не указывает ни один из Списков, к которым обращается работающая программа. [55]
Таким образом, когда указательные переменные продвигались по Списку, они не включались в счетчики ссылок для отдельных узлов; но, поскольку программист знает правила, в соответствии с которыми ведется учет ссылок для полных Списков, ему известно ( теоретически), как избежать ссылок на любые Списки, у которых счетчик ссылок равен нулю. Программист может также явным образом сбросить счетчики ссылок и вернуть некоторые Списки в свободную память. Эти идеи требуют от программиста осторожности; в руках неопытных программистов они оказываются опасными, и отладка программы становится более трудной из-за последствий, вызванных ссылками на уже стертые узлы. Самой привлекательной частью предложенной идеи является способ работы со Списками, у которых счетчик ссылок только что стал нулевым: такой список подключается в конец имеющегося списка свободного пространства ( для списка с двумя связями это сделать совсем просто) и рассматривается как свободное пространство в последнюю очередь, если использованы все предыдущие свободные ячейки; и только когда отдельные узлы этого Списка снова отдаются в работу, счетчики ссылок в Списках, на которые они ссылаются, уменьшаются на единицу. [56]
Следовательно, программист был обязан гарантировать, что список, который стирается, неодолжен никакому другому Списку. Метод счетчиков ссылок для Списков был предложен Дж. [57]
Поскольку при явном возврате, как мы видели, возникает немало проблем, желательно иметь другие методы. В одном из них, называемом сбором мусора, допускается порождение мусора, но не висячих ссылок. Затем, если список свободного пространства исчерпается, вызывается механизм сбора мусора, который находит мусор. Вторая альтернатива, метод счетчиков ссылок, требует явного возврата, но обеспечивает способ проверки числа указателей на данный элемент с тем, чтобы предотвратить образование висячих ссылок. [58]