Счетчик - ссылка
Cтраница 1
 |
Операция CDR в Лиспе с использованием счетчиков ссылок. [1] |
Счетчики ссылок позволяют во многих ситуациях избежать появления как мусора, так и висячих ссылок. Если в каждом элементе списка имеется счетчик ссылок, то в операции CDR нетрудно избежать рассмотренные выше трудности. [2]
 |
Операция CDR в Лиспе с использованием счетчиков ссылок. [3] |
Счетчики ссылок обеспечивают защиту также и в тех случаях, когда программисту предоставляется явная инструкция FREE или ERASE. [4]
Когда счетчик ссылок становится равным нулю, модуль выгружается из адресного пространства текущего процесса. [5]
Использование счетчиков ссылок - более простой из двух упомянутых методов, поэтому мы начнем с него. Основная идея состоит в следующем: внутри каждого элемента в куче выделяется некоторое дополнительное пространство для счетчика ссылок. Счетчик ссылок элемента в любой момент времени содержит целое число, равное числу существующих указателей на этот элемент. [6]
 |
Операция CDR в Лиспе с использованием счетчиков ссылок. [7] |
Метод счетчика ссылок не годится в случае циклически связанной группы элементов. Рассмотрим простой циклический список, например, такой, как на рис. 7.8, на один из элементов которого указывает извне какой-то указатель. [8]
Метод взвешенных счетчиков ссылок является обобщением метода однобитовых счетчиков. [9]
 |
Циклический список со специальным головным элементом. [10] |
Если ограничить использование счетчиков ссылок только для крупных структур, то издержки как в памяти, так и во вре-мени работы уменьшатся. Трудности возникают только при циклической связи между структурами. [11]
Сборщики на основе счетчиков ссылок работают параллельно, следя за количеством ссылок на каждую ячейку, но требуют применения дополнительных приемов для обработки циклических структур. [12]
Если исходное значение счетчика ссылок равно 2 для некоторого п, то вес в каждом указателе требует лишь Iog2 n бит памяти для хранения. Дублирование указателей соответствует уменьшению веса на 1 и помещению этого веса в оба указателя. [13]
В таком случае обработка счетчиков ссылок будет необходима только для этих специальных элементов с переменными счетчиками ссылок, рассмотрим, например, систему oOj работки списков, в которой каждый связанный список считается отдельной структурой данных. Если мы снабдим каждый список специальным головным элементом и потребуем, чтобы указатели из других списков указывали только на эту голову, но не на внутренние элементы списка, то счетчик ссылок будет необходим только в головном элементе. Более того, в счетчике ссылок головы нужно подсчитывать только указатели извне данной структуры. Все это изображено на рис. 7.9. Отдельные элементы можно удалять из списка и сразу же возвращать в список свободного пространства, не учитывая счетчики ссылок. Когда счетчик ссылок головы станет нулевым ( например, в результате уничтожения указателя, записанного в другом списке), то весь наш список - голова и все элементы - может быть возвращен в список свободного пространства. [14]
Ленивые сборщики мусора на основе счетчиков ссылок максимально оттягивают время обработки структуры и производят это по частям, а не сразу. [15]
Страницы: 1 2 3 4