Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 129
Текст из файла (страница 129)
В Е(ЕР, например, связанные спис- р - юа11ос1игеоН7пд)) Явный возврат — вполне естественный способ восстановления памяти при ее организации в вице кучи, но, к сожалению, не всегда его можно применить. Причиной этого являются две старые проблемы: мусор и повисшие ссылки.
Мы уже обсуждали эти проблемы в главе 5 в связи с разрушением структур данных. Если структура разрутпена (и занимаемая ее память освободилась) до разрушения всех путей доступа к этой структуре, то все оставшиеся пути доступа становятся повисшими ссылками. С другой стороны, если последний путь доступа к структуре разрушен без разруптения самой структуры и восстановления памяти, то эта структура становится мусором.
С точки зрения управления кучей повисшая ссылка — это указатель на элемент, который был возвращен в список свободного пространства (а затем мог быть повторно использован для какой-либо иной цели). Мусором с этой точки зрения является элемент, который доступен для повторного использования, но отсутствует в списке свободного пространства и, следовательно, недоступен. Если происходит накопление мусора, то объем доступной памяти постепенно уменьшается, в результате чего выполнение программы может прекратиться за неимением доступного свободного пространства памяти. При попытке программы с помощью повисшей ссылки изменить структуру данных, отведенная память под которую уже была сделана свободной, может случайно измениться содержимое элемента из списка свободного пространства.
Если в результате этого изменится указатель, связывающий этот элемент со следующим элементом списка свободного пространства, весь остаток списка может исказиться. Хуже того, последующие попытки программы, отвечающей за распределение памяти, использовать указатель в элементе такого измененного списка могут привести к совершенно непредсказуемым результатам (например, в качестве свобод)и>го пространства может быть вьщелена и позднее изменена область внутри выполняемого кода).
Аналогичные проблемы возникают в случае, если элемент, на который указывает повисшая ссылка, был уже перераспределен для других целей. Явный способ восстановления памяти, организованной в виде кучи, предрасполагает к появлению мусора и повисших ссылок, так как программист очень легко может сделать ошибку, приводящую к этим последствиям. Расслютрим, например, следующие операторы С: тпг *Р *ц: 7* р и О Являются указателвни на целью пЕРЕиенныЕ *7 470 Глава 1О. Управление памятью ки — это основная структура данных. Одна из элементарных операций Е)ЯР, сбг, получает указатель на некоторый элемент связанного списка и возвращает в качестве результата указатель на следующий элемент этого списка (рис.
10 2, а). Элемент, указанный в операции сг)г, может быть освобожден ею при условии, что исходный указатель, переданный в сог, является единственным указателем на этот элемент. Если при этом операция сг)г не возвратит элемент в список свободного пространства, то элемент станет мусором.
С другой стороны, если сг)г возвратит элемент в список свободного пространства, в то время как на него имеются другие указатели, то эти указатели становятся повисшими ссылками. Если отсутствует непосредственный способ определения наличия таких указателей, то операция сг)г потенциально должна порождать мусор или повисшие ссылки. 7 (сог Х) (1) Ввод для операции (сег Х) у (2) Результат операции (сог Х) Следует ли освободить т у — ~ к=в (1) Ввод для операции (ссг Х) (сог Х) У вЂ” в =3 7 Освободить ', если счетчик ссылок = 0 (2) Результат операции (озг Х) Рис.
10.2. Операция сог языке ь)ВР: в — модель сбора мусора; б — модель счетчика ссылок 10.4. Управление кучей 471 Поскольку явный возврат связан с описанными проблемами, желательно иметь альтернативные способы восстановления памяти. Одним из вариантов являются счетчики ссылок, которые также требуют явного возврата, ио обеспечивают возможность проверять количество указателей иа данный элемент, так чтобы ие создавались повисшие ссылки. Другой альтернативой является сбор мусора, где допускается возникновение мусора, ио ие повисших ссылок.
Когда список свободного пространства исчерпывается, активизируется механизм сборки мусора, который находит мусор и восстанавливает его, возвращая в список свободного пространства. Счетчики ссылок. Использование счетчиков ссылок — более простой из двух упомянутых методов. Внутри каждого элемента кучи выделяется некоторое дополнительное пространство для счетчика ссылок, который содержит целое число, равное количеству ссылок на этот элемент в данный момент времени. Когда этот элемент отводится под какой-либо объект (то есть когда ои выделяется из списка свободного пространства), счетчик ссылок устанавливается равным 1. Каждый раз, когда иа этот элемент создается новый указатель, значение счетчика ссылок увеличивается иа 1.
Кажлый раз, когда разрушается указатель па этот элемент, значение счетчика ссылок уменьшается иа 1. Когда счетчик ссылок достигает значения 0, элемент освобождается и может быть возвращен в список свободного пространства. Счетчики ссылок в большинстве ситуаций позволяют избежать как появления повисших ссылок, так и накопления мусора. Снова рассмотрим операцию сог языка 1ЛЯР. Если каждый элемент списка содержит счетчик ссылок, операции сог будет несложно избежать описанные выше трудности, сдг вычтет 1 из счетчика ссылок элемента, иа который первоначально указывал ее аргумент.
Если в результате получается, что счетчик ссылок становится равным О, то элемент можно возвратить в список свободного пространства, если же счетчик ссылок ие равен нулю, то иа этот элемент все еще указывают какие-то другие указатели и его нельзя считать свободным (рис. 10.2, 6). Когда программист имеет возможность использовать явный оператор освобождения или удаления структуры, то счетчики ссылок также обеспечивают защиту. Результатом выполнения оператора освобождения будет уменьшение иа 1 счетчика ссылок данной структуры.
Действительный возврат этой структуры в список свободного пространства производится, когда ее счетчик станет нулевым. Ненулевой счетчик указывает, что структура все еше доступна и оператор освобождения должен игнорироваться. Самый большой недостаток счетчиков ссылок — вто стоимость их использования.
Во время работы программы иепрергявио должны происходить проверки счетчиков ссылок, их уменьшение и увеличение, в результате чего заметно падает эффективность работы программы. Рассмотрим, к примеру, простой оператор присваивания Р:= О, где Р и 0 являются переменными-указателями. Без использования счетчиков ссылок скопировать значение указателя 0 в Р достаточно просто. Если задействованы счетчики ссылок, приходится делать следующее. 1. Обратиться к алемеиту, иа который указывает Р, и уменьшить его счетчик ссылок иа 1. 2. Проверить получившееся значение счетчика ссылок и, если оио равно 0, вернуть этот элемент в список свободного пространства.
472 Глава 10. Управление памятью 3. Скопировать 1-значение указателя из 0 в Р, 4, Обратиться к элементу, на который указывает 0, и увеличить его счетчик ссылок на 1. Общая стоимость операции присваивания значительно возрастает. Любая подобная операция, которая создает или разрушает указатели, неизбежно связана с изменением счетчиков ссылок. Помимо того, следует учитывать стоимость размещения этих счетчиков в памяти.
Если первоначально элементы занимали один или два слова, то счетчики ссылок могут значительно уменьшить объем памяти, доступный для размещения данных. Тем не менее эта технология пользуется успехом в системах параллельной обработки, в которых стоимость поддержания счетчиков распределяется между различными пользователями данных, в то время как в описаннойй ниже системе сбора мусора получение данных обходится достаточно дорого.
Сбор мусора. Возвращаясь к основным проблемам мусора и повисших ссылок, можно с уверенностью сказать, что повисшие ссылки потенциально намного опаснее мусора. Накопление мусора может привести к истощению свободной памяти, но повисшие ссылки могут привести к полному хаосу вследствие случайных изменений используемой памяти. Разумеется, эти две проблемтя взаимосвязаны: повисшие ссылки возникают, если память освобождается слишком рано, а мусор— когда память, наоборот, слишком долго не освобождается, В ситуации, когда нереально или слишком дорого избежать одновременного возникновения обеих проблем с помощью механизма, подобного счетчикам ссылок, лучше предпочесть наличие в памяти мусора, но избежать повисших ссылок.
Лучше вообще не восстанавливать память, чем сделать это слишком рано. Основная концепция сбора мусора заключается в том, что лучше допустить накопление мусора, зато избежать возникновения повисших ссылок. Когда список свободного пространства полностью исчерпан и требуются новые ресурсы памяти, то выполнение программы временно приостанавливается и активизируется специальная процедура сбора мусора, которая обнаруживает элементы кучи, ставшие мусором, и возвращает их в список свободного пространства.
Затем возобновляется выполнение программы стого места, на котором оно было прервано, и вновь начинается накопление мусора, пока не исчерпается список свободного пространства. Тогда снова будет инициирована процедура сбора мусора и т. д. Поскольку сбор мусора происходит довольно редко (а именно, когда исчерпывается список свободного пространства), то этой процедуре позволительно быть дорогостоящей. Она включает две стадии. 1, Маркировки элементов, На первой стадии должен быть помечен каждый активныйй элемент кучи (то есть тот, который является ч астьнт доступной структуры данных), Каждый элемент должен содержать биш сбори мусора, которыйй вначале устанавливается в положение «включен».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
