Счетчик - ссылка
Cтраница 3
Можно объединить сбор мусора с некоторыми другими методами возврата ячеек в свободную память; эти принципы не исключают друг друга, и в некоторых системах используются как счетчик ссылок, так и схемы сбора мусора, а кроме того, программист может явно освобождать узлы. Идея заключается в том, чтобы использовать сбор мусора, как последнюю надежду, когда непригодны все другие методы возврата ячеек. Достоинства такого подхода представляются весьма спорными, если иметь в виду неэффективность сбора мусора, когда память почти заполнена, и тот факт, что очень немногие программы не превосходят пределов памяти вскоре после того, как она стала близка к заполнению. [31]
Если строка не является пустой, то данная переменная указывает на динамически размещаемый блок памяти, содержащий значение строки, на 32-битовое - значение длины строки и на 32-битовое значение счетчика ссылок на строку. [32]
Будем считать, например, что все Списки представлены, как в ( 9), за тем лишь исключением, что поле REF в каждом головном узле используется для сбора мусора, а не для счетчика ссылок. Тогда мы можем переработать алгоритм В, организовав стек в полях REF головных узлов. [33]
 |
Взвешенные счетчики ссылок. [34] |
Пример функционирования этой схемы представлен на рис. 16.17. Вначале ( рис. 16.17, а) есть ячейка с исходным счетчиком, равным 1024, и единственным указателем, хранящим такой же вес. Счетчик ссылок остается тот же, а вес исходного указателя поровну делится между четырьмя указателями. Очевидно, что никакого обращения к ячейке не требуется. [35]
Увеличение значения счетчиков ссылок происходит обычным образом. Для уменьшения значения этого счетчика нам достаточно поместить адрес данной ячейки в СД. Для размещения новой ячейки приходится прибегать к небольшой хитрости. Мы выталкиваем первое значение из СД и проверяем счетчик ссылок у адресуемой ячейки. Если же, с другой стороны, счетчик ссылок был больше единицы, то его значение уменьшается на 1, как обычно, а из СД извлекается следующее значение. Этот процесс продолжается до тех пор, пока не станет возможным требуемое размещение новой ячейки или не исчерпается СД - в этом случае придется прибегнуть к использованию свободного списка. [36]
Основным преимуществом хранения весов внутри указателей, как и в методе однобитовых счетчиков ссылок, является то, что отсутствует необходимость осуществления доступа к ячейке при увеличении числа указателей на нее. Мы должны изменить показания счетчика ссылок ячейки при удалении ссылок на нее, но при этом обычно снимаются ссылки с указывающей ( адресующей) ячейки, так что доступ к адресуемой ячейке будет осуществлен в любом случае. Именно по этой причине метод взвешенных счетчиков ссылок особенно хорошо подходит для распределенных версий реализации функциональных языков, где частота посылок сообщений сильно влияет на эффективность работы. [37]
Стандартная реализация этого метода, как и реализация, предоставляемая TlnterfacedObject, приводит к увеличению счетчика ссылок на объект. Реализация метода Release классом TlnterfacedObject уменьшает счетчик ссылок, проверяя, не имеет ли он значение ноль, и в случае необходимости уничтожает объект. Вот поэтому в предыдущем примере нет программного кода, освобождающего ресурсы, используемые созданным объектом. [38]
Счетчики ссылок позволяют во многих ситуациях избежать появления как мусора, так и висячих ссылок. Если в каждом элементе списка имеется счетчик ссылок, то в операции CDR нетрудно избежать рассмотренные выше трудности. [39]
 |
Структура объекта. [40] |
Объекты занимают важный ресурс - участки виртуального адресного пространства ядра - поэтому, когда объект более не нужен, он должен быть удален, а его адресное пространство возвращено системе. Для этого в заголовке каждого объекта содержится счетчик ссылок на объект. Этот счетчик увеличивается на единицу каждый раз, когда объект открывается, и уменьшается на единицу при закрытии объекта. Когда значение счетчика уменьшается до 0, это означает, что никто более не пользуется этим объектом. Когда объект открывается или освобождается компонентом исполняющей системы, используется второй счетчик, даже если настоящий дескриптор при этом не создается. Когда оба счетчика уменьшаются до 0, это означает, что этот объект более не используется ни одним пользователем и ни одним исполняющим процессом, то есть объект может быть удален, а его память освобождена. [41]
Каждая новая ссылка из каталогов к индексному дескриптору отмечается в специальном его поле. Это позволяет файловой системе следить за занятостью файла: как только счетчик ссылок в результате удаления файла из каталогов станет равным нулю, индексный дескриптор освобождается, а дисковое пространство может быть использовано для записи других файлов. [42]
Представим себе, что мы разрабатываем универсальную систему для обработки Списков, которая будет использоваться сотнями других программистов. Для обслуживания, списка свободного пространства предлагается два основных метода: счетчики ссылок и сбор мусора. В методе счетчиков используется специальное поле в каждом узле, в котором учитывается, сколько стрелок указывает на этот узел. За таким счетчиком довольно легко следить во время работы программы, и всякий раз, когда счетчик сбрасывается в нуль, данный узел становится свободным. В этом случае идея состоит в том, что почти все алгоритмы не возвращают узлы в список свободной памяти и программа беззаботно работает до тех пор, пока не исчерпается весь этот список; тогда алгоритм сбора мусора, используя биты маркировки, возвращает в свободную память все узлы, которые в данный момент программе недоступны, после чего программа продолжает работать. [43]
Общая стоимость операции присваивания значительно возрастает. Любая аналогичная операция, кбторая может создавать или уничтожать указатели, также должна модифицировать счетчики ссылок. Кроме того, приходится платить за дополнительную память для счетчиков ссылок. Если в элементе кучи уже есть лишнее пространство, то память для счетчиков ссылок не вызывает затруднений. Чаще однако, чтобы хранить счетчики ссылок, к каждому элементу приходится добавлять по одному слову памяти. Если первоначально элементы занимали одно или два слова, то счетчики ссылок могут существенно уменьшить объем памяти, доступный для данных. [44]
Использование счетчиков ссылок - более простой из двух упомянутых методов, поэтому мы начнем с него. Основная идея состоит в следующем: внутри каждого элемента в куче выделяется некоторое дополнительное пространство для счетчика ссылок. Счетчик ссылок элемента в любой момент времени содержит целое число, равное числу существующих указателей на этот элемент. [45]
Страницы: 1 2 3 4