Cтраница 1
Метод явного возврата мог бы показаться вполне естественным методом утилизации при организации памяти в виде кучи, но, к сожалению, он не всегда применим. Причина этого заключена в двух старых проблемах: проблеме мусора и проблеме висячих ссылок. Первый раз мы обсуждали эти проблемы в гл. Если структура уничтожается ( и занятая ею память освобождается) до разрушения всех путей доступа к этой структуре, то оставшиеся пути доступа становятся висячими ссылками. С другой стороны, если последний путь доступа к структуре уничтожается, а сама структура не уничтожается и память не освобождается, то эта структура становится мусором. Мусором является такой элемент, который пригоден для повторного использования, но не содержится в списке свободного пространства и потому недоступен. [1]
Поскольку при явном возврате, как мы видели, возникает немало проблем, желательно иметь другие методы. В одном из них, называемом сбором мусора, допускается порождение мусора, но не висячих ссылок. Затем, если список свободного пространства исчерпается, вызывается механизм сбора мусора, который находит мусор. Вторая альтернатива, метод счетчиков ссылок, требует явного возврата, но обеспечивает способ проверки числа указателей на данный элемент с тем, чтобы предотвратить образование висячих ссылок. [2]
Утилизация памяти в куче путем явного возврата памяти создает возможность появления мусора и висячих ссылок. [3]
Здесь наблюдаются сравнительно малые отличия от случая фиксированного размера блоков. Явный возврат освобождаемой памяти в список свободного пространства является простейшим методом, но по-прежнему возникают проблемы мусора и висячих ссылок. [4]
Под частичным уплотнением мы понимаем объединение двух или больше смежных свободных блоков в один свободный блок большего размера. Если обнаружение свободной памяти выполняется с помощью сбора мусора, то частичное уплотнение происходит автоматически ( см. упр. Если память освобождается по частям ( путем явного возврата, со счетчиками ссылок или без них), то необходимо отдельно позаботиться об уплотнении. Заметим, что поскольку блоки возвращаются в список свободного пространства в случайном, по существу, порядке, то весьма вероятно, что свободными станут соседние по памяти блоки. Однако они освобождаются в разное время, поэтому тот факт, что они смежные, сразу не виден. Нам желательно объединять такие смежные свободные блоки в один сразу, как только они возникают. Простейший способ сделать это состоит в расположении списка свободного пространства в порядке адресов памяти и поддержании его в таком состоянии во время работы, как изображено на рис. 7.11. Когда в список свободного пространства возвращается некоторый блок, то отыскивается положение этого блока в упорядоченном списке и предыдущий элемент списка проверяется на предмет смежности. [5]
Поскольку при явном возврате, как мы видели, возникает немало проблем, желательно иметь другие методы. В одном из них, называемом сбором мусора, допускается порождение мусора, но не висячих ссылок. Затем, если список свободного пространства исчерпается, вызывается механизм сбора мусора, который находит мусор. Вторая альтернатива, метод счетчиков ссылок, требует явного возврата, но обеспечивает способ проверки числа указателей на данный элемент с тем, чтобы предотвратить образование висячих ссылок. [6]